<<

. 2
( 2)



j
public key. To decrypt S, Alice applies her n ’ 1 where the ci are coef¬cients of Ci .
reverse secret transformations. She starts with McAuley and Goodman [37] proposed in
Sn = S and by calculating the other S j, similar as December 1982 a very similar knapsack scheme
in the Merkle“Hellman case (see Section “The de- as the one proposed by Davio (see higher). The
cryption”). So she obtains a set of linear equations: differences are that no Merkle“Hellman trans-
« 1  « a1 an  « x1 
formations are used and that the x can have
... 1
S 1 more values than binary (they have to be smaller
¬.·¬. . ·¬ . ·
..
¬ . ·=¬ . . ·¬ . · than a given value and larger than or equal to
. . .
·  . (8)
. .
 S n’1   n’1 n’1   x
. . . an zero). The trapdoor information consists only in
a1 n’1
Sn ... the secrecy of the primes which were used in the
n n xn
a1 an
construction.
After the discussed transformations to ¬nd x, Alice By the end of 1982 and the beginning of 1983
only has to solve a set of linear equations. It is Desmedt, Vandewalle and Govaerts [19] general-
important to observe that the obtained public key ized Shamir™s ultimate knapsack scheme by gener-
is one-to-one, even if a1 is not an easy sequence, or alizing the Merkle“Hellman transformation, call-
even if no partially easy sequences are used. This ing it the general knapsack scheme. All previously
follows from the nonsingularity of the matrix in discussed knapsack systems are special cases of
Equation (8). this one [20]. In Shamir™s scheme one can only
Other research continued, trying to obtain choose one vector and start the transformation,
other easy (or partially easy) knapsack sequences. while here n choices of vectors are necessary (or
Petit™s [42] de¬ned lexicographic knapsacks. Let are done implicitly).
w(·) be the Hamming weight function. a is called Around the same time Brickell cryptanalyzed
lexicographic, if and only if, aT x < aT y for all bi- low density knapsacks [4, 5]. A similar attack
nary x and y, with x = y and one of the two cases was independently found by Lagarias and Odlyzko
(i) w(x) < w(y) or (ii) w(x) = w(y) and x and y sat- [30]. To perform his attack, Brickell ¬rst gen-
isfy together xk yk = 1 and xi • yi = 0 for all i < k, eralized the Merkle“Hellman dominance condi-
with • the exclusive or. The construction of the tion. The integers he used may also be negative.
public key is as in the Merkle“Hellman case, us- Brickell called a modular mapping —w mod m
ing Merkle“Hellman transformations. from a into c to have the small sum property if ci ≡
Willett [53] also came up with another easy se- ai w mod m, and m > |ci |. He called mappings
quence and a partially easy sequence, which were satisfying this property SSMM. Given xi ai one
then used similar as in the Merkle“Hellman and can easily calculate xi ci . This is done exactly
in the Desmedt“Vandewalle“Govaerts knapsack. as in the reverse Merkle“Hellman case. If the re-
We will only discuss the easy sequence. It is not to sult is greater than ci >0 ci M is subtracted from
dif¬cult to ¬gure out how it works in the case of the it. He tries to ¬nd n ’ 1 such transformations
partially easy sequence. The i th row of the matrix all starting from the public key a. He can then
in Equation (9) corresponds with the binary rep- solve a set of equations similar as in the ultimate
resentation of ai1 . scheme of Shamir (remark the difference in ob-
Cn’1 . . . taining the matrix). To obtain such transforma-
(Tn Cn On’1 Tn’1
tions in order to break, he uses the LLL algorithm
O2 T2 C2 O1 T1 C1 ). (9)
choosing a special lattice. If all the reduced lattice
In Equation (9) the Ti are randomly chosen binary basis vectors are short enough, he will succeed.
matrices, the Ci are n — 1 binary column vectors This happens probably when the density is less
such that they (Ci ) are linearly independent mod- than 1/ log2 n. In the other cases he uses some
ulo 2, and the Oi are n — li zero binary matrices, trick to transform the problem into one satisfy-
where li ≥ log2 n. Let us call the locations of the Ci ing the previous condition. Arguments were given
Knapsack cryptographic schemes 337


that this will succeed almost always when the den- the lattice. This last information will allow to de-
sity is less than 0.39. The low density attack pro- cide whether the selected subset is “good.” If it
posed by Lagarias and Odlyzko is expected to work was not, one restarts at the beginning. If it was
when the density of the knapsack is less than a good set, one can calculate the number of iter-
0.645. These attacks break the ultimate scheme ations that were used by the designer during the
of Shamir, because the density of the public key is construction of the public key. Some calculation of
small as a consequence of construction method of determinants will then return an almost super-
the public key. increasing sequence. Proceeding with almost su-
Lagarias found a good foundation for the attacks perincreasing sequences was already discussed by
on the knapsack system, by discussing what he Karnin and Hellman [28] (remarkable is the con-
called unusually good simultaneous Diophantine tradiction in the conclusion of their paper and its
approximations [31]. Lagarias used similar ideas use by Brickell!).
[32] to analyze Shamir™s attack on the basic In October 1984, Odlyzko found an effective
Merkle“Hellman scheme. The main result is that method to cryptanalyze the McAuley“Goodman
Shamir overlooked some problems, but neverthe- and the Goodman“McAuley scheme, using mainly
less his attack almost always works. gcd™s [41].
Brickell, Lagarias and Odlyzko performed an Later on Brickell [9] was able to break, with
evaluation [6] of the Adleman™s attack on multiple a similar idea as in [8], a lot of other knap-
iterated Merkle“Hellman and Graham“Shamir sack schemes, e.g., the Desmedt“Vandewalle“
schemes. They concluded that his attack on the Govaerts, the Davio, the Willett, the Petit and
basic Graham“Shamir scheme works, but that the Goodman“McAuley. The attack affects also
the version to break iterated Merkle“Hellman or the security of the so-called general knapsack
Graham“Shamir scheme failed. The main rea- scheme.
son for it was that the LLL algorithm found so- At Eurocrypt 85 Di Porto [22] presented two
called undesired vectors, which could not be used new knapsack schemes, which are very close to
to cryptanalyze the cited systems. Even in the case the Goodman“McAuley one. However they were
that only two transformations were applied (to broken during the same conference by Odlyzko.
construct the public key) his attack fails.
The Case of Usual Knapsacks with other
In 1983 Karnin proposed an improved time-
Encryption Functions
memory-processor tradeoff [29] for the knapsack
problem. The idea is related to exhaustive key
search [21] and Hellman™s time-memory trade-off In 1979 Arazi proposed a new knapsack based ad-
[26], in which an exhaustive key search is used to ditive knapsack algorithm to protect the privacy
break the system using straightforward or more of the message [2]. The main difference with the
advanced ideas. The result has only theoretical Merkle“Hellman encryption is that random noise
value if the dimension of the knapsack system n is used in the encryption function. The param-
is large. eters which are chosen during the construction
In 1984 Goodman and McAuley proposed a of the public key have to satisfy some properties
small modi¬cation [25] to their previous system (see [2]).
[37]. In the new version some modulo transforma- In 1983 Brickell also presented a new knapsack
tion was applied. system [7], which is similar to the Arazi one.
In the same year Brickell proposed how to One year later Brickell declared his own new
cryptanalyze [8] the iterated Merkle“Hellman and scheme insecure, as a consequence of his attack
Graham“Shamir scheme. As usual no proof is pro- on iterated knapsacks [8].
vided that the breaking algorithm works; argu- Chor and Rivest proposed in 1984 another knap-
ments for the heuristics are described in [8]. Sev- sack based system [13]. The encryption process
eral public keys were generated by the Merkle“ is very close to the one in the Merkle“Hellman
Hellman and Graham“Shamir scheme and then scheme. The main difference in the encryption is
that xi ¤ h for some given h. The trapdoor tech-
turned out to be breakable by Brickell™s attack.
Again the LLL algorithm is the driving part of nique does not use a modular multiplication (as do
the attack. First the cryptanalyst picks out a sub- almost all other knapsack schemes). The trapdoor
set of the sequence corresponding with the pub- uses the discrete logarithm problem [40, 43] (see
lic key. These elements are entered in a special also Section “The multiplicative knapsack scheme
way in the LLL algorithm. A reduced basis for and its history”). A study of possible attacks was
that lattice is obtained. Then one calculates the done, but it turned out that by a good choice of
linear relation between the old and new basis for parameters all attacks known at that point of time
338 Knapsack cryptographic schemes


could be avoided. New attacks were set up by the ¬nd q and b. He also assumes that b, q and the
authors [13] but this did not change the above ai consist of approximately m bits. His attack will
take a polynomial time if m = O(n log n). Also in
conclusion.
In 1985 Brickell broke the Arazi knapsack sys- this attack the LLL algorithm is the driving force.
tem [9]. In 1985 Cooper and Patterson [14] also A special choice [39] of the lattice is used to attack
proposed some new trapdoor knapsack algorithm, the system. Once the b and q are found the crypt-
which can however be cryptanalyzed by Brickell analyst can easily cryptanalyze ciphertexts as the
[9]. The same attack of Brickell can break this receiver can decrypt them.
knapsack as well as the Lagger knapsack [33].
Since 1985 interest in public key knapsacks The Trapdoor Knapsack Schemes to
almost vanished completely. In 1998 the Chor“ Protect Signatures and Authenticity
Rivest scheme was ¬nally cryptanalyzed [52].
To make a digital signature the sender applies the
The Multiplicative Knapsack Scheme decryption function on the plaintext. From this
and its History point of view it is easy to understand that the
higher discussed knapsack schemes are not well
suited for this purpose. Indeed if the decryption
The so called multiplicative knapsack here uses
function is not “enough” (pseudo) invertible the
exactly the same encryption function as the
sender has to perform other trials in order to gen-
Merkle“Hellman additive knapsack scheme. How-
erate a signature. Such a scheme was presented in
ever the trapdoor is completely different in nature,
the original Merkle“Hellman paper [38]. Shamir
because it is mainly based on a transformation
suggested a more practical one [46] in 1978.
from an additive knapsack problem into a mul-
In 1982 Sch¨ bi and Massey proposed another
o
tiplicative one. It was presented by Merkle and
version of [45] as a fast signature scheme.
Hellman in their original paper [38].
In 1982“1983 Odlyzko broke [39] the Shamir™s
Let us ¬rst explain the construction of the public
fast signature and the Sch¨ bi-Massey one. Here
o
key. One chooses n relative prime positive num-
bers ( p1 , p2 , . . . , pn ), some prime number q, such also the LLL algorithm plays an important role.
that q ’ 1 has only small primes and such that
SOME DETAILS: A small encyclopedia is required
n
q> to discuss all schemes, weaknesses and attacks in
pi (10)
details. Only three issues are discussed in more
i=1
depth, these being: (i) why the Merkle“Hellman
and some primitive root b modulo q (see modu-
transformation leads to the possibility of more
lar arithmetic). One then ¬nds integers ai , where
than one decryption key to break, (ii) the LLL
1 ¤ ai ¤ q ’ 1, such that pi ≡ bai mod q. So, ai is
algorithm and (iii) its use in the low density at-
the discrete logarithms of pi base b modulo q. This
tack of Brickell.
explains why q ’ 1 was chosen as the product of
small primes, since the Pohlig“Hellman algorithm
The Existence of In¬nitely Many
(see discrete logarithm problem) can easily calcu-
Decryption Keys
late these discrete logarithms in that case [43].
To decrypt one calculates S = b S mod q, be-
Let us focus on the basic Merkle“Hellman scheme.
cause b S = b xi ·ai = b xi ·ai = pixi mod q. The
Suppose w ’1 and m correspond with the re-
last equality is a consequence of the condition in
verse Merkle“Hellman transformation and that
Equation (10). One can easily ¬nd the correspond-
ai was the used superincreasing sequence. We will
ing x starting from S , using the fact that the num-
demonstrate that other values allow to break (call
bers pi are relative prime. This last point is im-
these V, M, and ai ). In order to analyze for which
portant, because in the general case the subset
V and M Equations (3)“(5) (see also Equation (6))
product problem is NP-complete [24].
holds let us reformulate the Merkle“Hellman
This scheme can be cryptanalyzed by a low den-
transformation in terms of linear inequalities.
sity attack [5, 30]. However the disadvantage is
ai ≡ ai · V mod M and 0 < ai < M can be refor-
that it requires a separate run of the lattice reduc-
mulated into:
tion algorithm (which takes at least on the order
of n4 operations) to attack each n bit message. To 0 < ai = (ai · V ’ si · M) < M, si integer. (11)
overcome that problem, Odlyzko tried another at-
Note that si is equal to (ai · V)/M with · the
tack [39]. Herein he starts from the assumption
that some of the pi are known. He then tries to ¬‚oor function.
Knapsack cryptographic schemes 339


THEOREM 2. Let (v1 , . . . , vn ) be a basis of a lattice
Using Equation (11) the conditions in Equa-
L and let v i be the points
tions (3)“(5) (see also Equation (6)) and the
condition of superincreasing of a can be expressed
i
v= zijv j, for 1 ¤ i ¤ n
as linear inequalities on V/M:
j
1 + si
si V
1 ¤ j ¤ n,
< < ¤1 and
Equation (11) gives:
ai M ai
where zij are integers, then the set (v 1 , . . . , v n ) is
(12)
n also a base for the same lattice L, if and only if
1+ i=1 si
V
<
Equation (3) gives: (13) det(zij) = ±1. An integer matrix Z with det(zij) =
n
M ai
i=1
±1 is called an unimodular matrix.
the condition requiring a be superincreasing
gives for all j, with 2 ¤ j ¤ n: PROOF. See [12].
j’1
j’1
sj ’ i=1 si
V
if a j < < As a consequence of Theorem 2 | det(v1 , . . . , vn )|
ai : (14)
j’1
M aj ’ i=1 ai is independent of a particular basis for the
i=1
lattice.
j’1
j’1
sj ’ i=1 si
V
if a j > > . For a lattice L there does not necessarily exist a
ai : (15)
j’1
M aj ’ i=1 ai set of n vectors that form an orthogonal basis for
i=1
the lattice. The Lenstra Lenstra Lovasz (LLL, see
Observe that the condition in Equation (4) does
shortest vector problem or [35, pp. 515“525]) algo-
not impose an extra condition on the ratio V/M.
rithm ¬nds in polynomial time a basis for a lattice
Indeed, for any V/M which satis¬es the conditions
L, which is nearly orthogonal with respect to a
in Equations (12)“(14) one can take coprime V, M
certain measure of non-orthogonality. The LLL al-
in order to satisfy Equation (4).
gorithm does however not ¬nd in general the most
orthogonal set of n independent vectors. As a con-
THEOREM 1. For each encryption key (a1 , a2 , . . . ,
sequence of Theorem 2 it ¬nds short (probably not
an ) constructed using Equations (3)“(5) from a su-
the shortest) vectors. A basis is called reduced if it
perincreasing sequence (a1 , a2 , . . . , an ), there exist
contains relatively short vectors.
in¬nitely many superincreasing sequences satisfy-
Let us brie¬‚y describe LLL. Let v1 , v2 , . . . , vn
ing the conditions in Equations (3)“(5).
belong to the n-dimensional real vector space. To
initialize the algorithm an orthogonal real basis
PROOF. The conditions Equations (3) and (5) and vi is calculated, together with µij (1 ¤ j < i ¤ n),
superincreasing reformulated as Equations (12)“ such that
(15) can be summarized as: L < M < U, where
V
i’1
L and U are rational numbers. Since there ex-
vi = vi ’ µijv j (16)
ists a superincreasing decryption key, which sat-
j=1
is¬es Equations (3)“(5) there exists an L and U
(vi , v j)
such that L < U. So, in¬nitely many (V, M) sat-
µij = , (17)
(v j, v j)
isfy the bound conditions and the condition that
gcd(V, M) = 1.
where (·, ·) denotes the ordinary inner (scalar)
It is easy to generalize Theorem 1 to knapsack se- product. In the course of the algorithm the vec-
tors v1 , v2 , . . . , vn will be changed several times,
quences a obtained by multiple Merkle“Hellman
transformations [16, 17, 20, 23]. but will always remain a basis for L. After ev-
ery change the vi and µij are updated using Equa-
The LLL Algorithm tions (16) and (17). A current subscript k is used
during the algorithm. LLL starts with k = 2. If
k = n + 1 it terminates. Suppose now k ¤ n, then
First we de¬ne a lattice (in the geometrical sense
we ¬rst check that |µk | ¤ 1/2 if k > 1. If this
of the word). k’1
does not hold, let r be the integer nearest to µk , k’1
DEFINITION 3. Let (v1 , . . . , vn ) be a linearly in- and replace vk by vk ’ r vk’1 , (do not forget the up-
dependent set of real vectors in a n-dimensional date). Next we distinguish two cases. Suppose that
real Euclidean space. The set {u1 v1 + · · · + un vn | k ≥ 2 and |vk + µk vk’1 |2 < (3/4)|vk’1 |2 , then we
k’1
u1 , . . . , un ∈ Z}, is called the lattice with basis interchange vk’1 and vk , (do not forget the update),
(v1 , . . . , vn ). afterwards replace k by k ’ 1 and restart. In the
340 Knapsack cryptographic schemes


j j j j j j
other case we want to achieve that gers (y1 , . . . , yn ) such that v1 = y1 and vi = yi na1 +
j j j j
y1 nai for 2 ¤ i ¤ n. Since n divides vi let ui = vi /n
|µk | ¤ 1 , for 1 ¤ j ¤ k ’ 1. (18)
j 2
j
for 2 ¤ i ¤ n. This implies evidently that 0 ≡ a1 y1
If the condition in Equation (18) does not hold, j j
and ui ≡ ai y1 for 2 ¤ i ¤ n. As a consequence of
then let l be the largest index < k with µl > 1/2,
k
the short enough property we have indeed the
let r be the nearest to µl and replace bk by bk ’ r bl
k
small sum property. The independence of the n ’ 1
(do not forget the update), repeat until the condi-
vectors so obtained with SSMM, is then easy to
tions Equation (18) hold, afterwards replace k by
prove.
k + 1 and restart. Remark that if the case k = 1
appears one replaces it by k = 2.
Arguments are given in [5] that the condition
in Theorem 3 are almost satis¬ed if the density is
The Use of the LLL Algorithm in Brickell™s low enough.
Low Dense Attack
CONCLUSION: The encryption in the Merkle“
In Section “The trials to avoid weaknesses and at- Hellman knapsack is based on NP-completeness,
tacks for the class of usual knapsacks” we brie¬‚y however, its trapdoor was not. In secure public
discussed Brickell™s low dense attack. We intro- key cryptosystems the encryption process must be
duced the concept of SSMM and have given a hard to invert but it must also be hard to ¬nd
sketch of Brickell™s low density attack. Remem- the original trapdoor or another trapdoor. Non-
ber also that if the density is not low enough public key use of knapsack was investigated, e.g.
(>1/ log2 n) it has to be arti¬cially lowered. We will in [18, 44].
only discuss the case that it is indeed low enough. For further details on the research on public key
This last part is always used as the main technique knapsack before 1992, consult [11].
of the breaking algorithm.
Yvo Desmedt
The breaking is based on Theorem 3. Hereto we
¬rst have to de¬ne short enough vector.
References
DEFINITION 4. A vector c in a lattice L is called
short enough related to a1 if
[1] Adleman, L.M. (1983). “On breaking the iterated
n Merkle“Hellman public-key cryptosystem.” Ad-
|ci | < a1 , vances in Cryptology”CRYPTO™82, Lecture Notes
in Computer Science, eds. D. Chaum, R.L. Rivest,
i=2
and A.T. Sherman, Santa Barbara, CA, August 23“
where c1 = 0 and ci = ci /n for 2 ¤ i ¤ n.
25. 1982, Plenum, New York, 303“308. More de-
tails appeared in “On breaking generalized knap-
THEOREM 3. If all vectors in the reduced basis for sack public key cryptosystems.” TR-83-207, Com-
the lattice, with basis vectors ti de¬ned in Equa- puter Science Dept., University of Southern Cali-
tion (19), are short enough related to a1 , then we fornia, Los Angeles, March 1983.
can ¬nd n ’ 1 independent SSMM for a1 , . . . , an . [2] Arazi, B. (1980). “A trapdoor multiple mapping.”
IEEE Trans. Inform. Theory, 26 (1), 100“102.
= ...
t1 (1 na2 na3 na4 nan ) [3] Brickell, E.F., J.A. Davis, and G.J. Simmons
= ...
t2 (0 na1 0 0 0) (1983). “A preliminary report on the cryptanaly-
= ...
t3 (0 0 na1 0 0) sis of the Merkle“Hellman knapsack cryptosys-
(19)
= ...
t4 (0 0 0 na1 0) tems.” Advances in Cryptology”CRYPTO™82, Lec-
. . . . . . ture Notes in Computer Science, eds. D. Chaum,
..
. . . . . .
.
. . . . . . R.L. Rivest, and A.T. Sherman, Santa Barbara,
tn = (0 ...
0 0 0 na1 ). CA, August 23“25, 1982. Plenum, New York, 289“
301.
[4] Brickell, E.F. (1983). “Solving low density knap-
PROOF. Call the vectors of the reduced basis
sacks in polynomial time.” IEEE Intern. Symp.
v1 , v2 , . . . , vn . We will ¬rst prove that a mod-
Inform. Theory, St. Jovite, Quebec, Canada,
j
ular mapping by v1 mod a1 has the small sum September 26“30, 1983. Abstract of papers, 129“
property (see Section “The trials to avoid weak- 130.
nesses and attacks for the class of usual knap- [5] Brickell, E.F. (1984). “Solving low density knap-
sacks”). Since v j is an integral linear combination sacks.” Advances in Cryptology”CRYPTO™83, Lec-
of the vectors in Equation (19), there exist inte- ture Notes in Computer Science, ed. D. Chaum,
Knapsack cryptographic schemes 341


Les Arcs, France, June 1982, Abstract of papers,
Santa Barbara, CA, August 21“24, 1983. Plenum,
115“116.
New York, 25“37.
[18] Desmedt, Y., J. Vandewalle, and R. Govaerts
[6] Brickell, E.F., J.C. Lagarias, and A.M. Odlyzko
(1982). “A highly secure cryptographic algorithm
(1984). “Evaluation of the Adleman attack on mul-
for high speed transmission.” GLOBECOM™82,
tiple iterated Knapsack cryptosystems.” Advances
IEEE, Miami, FL, November 29“December 2,
in Cryptology”CRYPTO™83, Lecture Notes in
1982, 180“184.
Computer Science, ed. D. Chaum, Santa Barbara,
[19] Desmedt, Y., J. Vandewalle, and R. Govaerts
CA, August 21“24, 1983. Plenum, New York, 39“
(1983). “Linear algebra and extended mappings
42.
generalise public key cryptographic knapsack
[7] Brickell, E.F. (1983). “A new knapsack based
algorithms.” Electronics Letters, 19 (10), 379“
cryptosystem.” Presented at CRYPTO™83, Santa
381.
Barbara, CA, August 21“24, 1983.
[20] Desmedt, Y. (1984). “Analysis of the security and
[8] Brickell, E.F. (1985). “Breaking iterated knap-
new algorithms for modern industrial cryptog-
sacks.” Advances in Cryptology”CRYPTO™84, Lec-
raphy.” Doctoral Dissertation, Katholieke Univer-
ture Notes in Computer Science, vol. 196, eds.
siteit Leuven, Belgium.
G.R. Blakley and D. Chaum, Santa Barbara, CA,
[21] Dif¬e, W. and M.E. Hellman (1977). “Exhaustive
August 19“22, 1984. Springer-Verlag, Berlin, 342“
cryptanalysis of the NBS data encryption stan-
358.
dard.” Computer, 10 (6), 74“84.
[9] Brickell, E.F. (1985). “Attacks on generalized knap-
[22] Di Porto, A. (1985). “A public key cryptosystem
sack schemes.” Presented at EUROCRYPT™85,
based on a generalization of the knapsack prob-
Linz, Austria, April 9“11, 1985.
lem.” Presented at EUROCRYPT™85, Linz, Austria,
[10] Brickell, E. and A.M. Odlyzko (1988). “Cryptanaly-
April 9“11, 1985.
sis: A survey of recent results.” Proc. IEEE, 76 (5),
[23] Eier, R. and H. Lagger (1983). “Trapdoors in knap-
578“593.
sack cryptosystems.” Cryptography. Proc. Burg
[11] Brickell, E.F. and A.M. Odlyzko (1992). “Crypt-
Feuerstein 1982, Lecture Notes in Computer Sci-
analysis: A survey of recent results.” Contemporary
ence, vol. 149, ed. T. Beth. Springer-Verlag, Berlin,
Cryptology, ed. G.J. Simmons. IEEE Press, New
316“322.
York, 501“540.
[24] Garey, M.R. and D.S. Johnson (1979). Comput-
[12] Cassels, J.W.S. (1971). An Introduction to the Ge-
ers and Intractability: A Guide to the Theory of
ometry of Numbers. Springer-Verlag, Berlin.
NP”Completeness. W.H. Freeman, San Francisco,
[13] Chor, B. and R.L. Rivest (1985). “A knapsack type
CA.
public key cryptosystem based on arithmetic in ¬-
[25] Goodman, R.M. and A.J. McAuley (1985). “A new
nite ¬elds.” Advances in Cryptology”CRYPTO™84,
trapdoor knapsack public key cryptosystem.” Ad-
Lecture Notes in Computer Science, vol. 196, eds.
vances in Cryptology”EUROCRYPT™84, Lecture
G.R. Blakley and D. Chaum, Santa Barbara, CA,
Notes in Computer Science, vol. 209, eds. T. Beth,
August 19“22, 1984. Springer-Verlag, Berlin, 54“
N. Cot and I. Ingemarsson, Paris, France, April 9“
65.
11, 1984. Springer-Verlag, Berlin, 150“158.
[14] Cooper, R.H. and W. Patterson (1985). “Eliminat-
[26] Hellman, M.E. (1980). “A cryptanalytic time-
ing data expansion in the Chor-Rivest algorithm.”
memory trade-off.” IEEE Trans. Inform. Theory, IT-
Presented at EUROCRYPT™85, Linz, Austria, April
26 (4), 401“406.
9“11, 1985.
[27] Henry, P.S. (1981). “Fast decryption algorithm for
[15] Davio, M. (1983). “Knapsack trapdoor functions:
the knapsack cryptographic system.” Bell Syst.
An introduction.” Proceedings of CISM Summer
Tech. J., 60 (5), 767“773.
School on: Secure Digital Communications, ed.
[28] Karnin, E.D. and M.E. Hellman (1983). “The
J.P. Longo, CISM Udine, Italy, June 7“11, 1982.
largest super-increasing subset of a random set.”
Springer-Verlag, Berlin, 41“51.
IEEE Trans. Inform. Theory, IT-29 (1), 146“148.
[16] Desmedt, Y., J. Vandewalle, and R. Govaerts
Also presented at IEEE Intern. Symp. Inform. The-
(1982). “The use of knapsacks in cryptogra-
ory, Les Arcs, France, June 1982, Abstract of pa-
phy public key systems (Critical analysis of the
pers, 113.
security of Knapsack Public Key Algorithms).”
[29] Karnin, E.D. (1984). “A parallel algorithm for the
Presented at Groupe de Contact Recherche Op-
knapsack problem.” IEEE Trans. on Computers,
erationelle du F.N.R. S., Mons, Belgium, Febru-
C-33 (5), 404“408. Also presented at IEEE Intern.
ary 26, 1982. Appeared in Fonds National de la
Symp. Inform. Theory, St. Jovite, Quebec, Canada,
Rechereche Scienti¬que, Groupes de Contact, Sci-
September 26“30, 1983, Abstract of papers, 130“
ences Math´ matiques.
e
131.
[17] Desmedt, Y.G., J.P. Vandewalle, and R.J.M.
[30] Lagarias, J.C. and A.M. Odlyzko (1983). “Solving
Govaerts (1984). “A critical analysis of the se-
low density subset sum problems.” Proc. 24th An-
curity of knapsack public key algorithms.” IEEE
nual IEEE Symposium on Foundations of Com-
Trans. Inform. Theory, IT-30 (4), 601“611. Also
puter Science, 1“10.
presented at IEEE Intern. Symp. Inform. Theory,
342 Known plaintext attack


[44] Schaumuller-Bichl, I. (1982). “On the design and
[31] Lagarias, J.C. (1984). “Knapsack public key
analysis of new cipher systems related to the DES.”
cryptosystems and diophantine approximation.”
IEEE Intern. Symp. Inform. Theory, Les Arcs,
Advances in Cryptology”CRYPTO™83, Lecture
France, 115.
Notes in Computer Science, ed. D. Chaum, Santa
[45] Sch¨ bi, P. and J.L. Massey (1983). “Fast authenti-
o
Barbara, CA, August 21“24, 1983. Plenum, New
cation in a trapdoor knapsack public key cryptosys-
York, 3“23.
tem.” Cryptography, Proc. Burg Feuerstein 1982,
[32] Lagarias, J.C. (1984). “Performance analysis of
Lecture Notes in Computer Science, vol. 149, ed.
Shamir™s attack on the basic Merkle“Hellman
T. Beth. Springer-Verlag, Berlin, 289“306. See also
knapsack cryptosystem.” Proc. 11th Intern. Collo-
Proc. Int. Symp. Inform. Theory, Les Arcs, June
quium on Automata, Languages and Programming
1982, 116.
(ICALP), Lecture Notes in Computer Science, vol.
[46] Shamir, A. (1978). “A fast signature scheme.” Inter-
172, ed. J. Paredaens. Antwerp, Belgium, July 16“
nal Report. MIT, Laboratory for Computer Science
20, 1984. Springer-Verlag, Berlin.
Report RM-107, Cambridge, MA.
[33] Lagger, H. “Public key algorithm based on knap-
[47] Shamir, A. (1979). “On the cryptocomplexity of
sack systems.” Dissertation, Technical University
knapsack systems.” Proc. Stoc 11 ACM, 118“
Vienna, Austria (in German).
129.
[34] Lenstra, Jr., H.W., (1981). “Integer programming
[48] Shamir, A. and R. Zippel (1980). “On the
with a ¬xed number of variables.” Technical Re-
security of the Merkle“Hellman cryptographic
port, University of Amsterdam, Dept. of Mathe-
scheme.” IEEE Trans. Inform. Theory, 26 (3), 339“
matics, 81“03.
340.
[35] Lenstra, A.K., H.W. Lenstra, Jr., and L. Lo-
[49] Shamir, A. (1983). “A polynomial time algorithm
vasz (1982). “Factoring polynomials with ratio-
for breaking the basic Merkle“Hellman cryptosys-
nal coef¬cients.” Mathematische Annalen, 261,
tem.” Advances in Cryptology”CRYPTO™82, Lec-
515“534.
ture Notes in Computer Science, eds. D. Chaum,
[36] Lenstra, Jr., H.W., (1983). “Integer programming
R.L. Rivest, and A.T. Sherman, Santa Barbara,
with a ¬xed number of variables.” Math. Oper. Res.,
CA, August 23“25, 1982. Plenum, New York, 279“
8 (4), 538“548.
288.
[37] McAuley, A.J. and R.M. Goodman (1983). “Mod-
[50] Shamir, A. (1982). “The strongest knapsack-based
i¬cations to the Trapdoor“Knapsack public key
cryptosystem.” Presented at CRYPTO™82, Santa
cryptosystem.” IEEE Intern. Symp. Inform. The-
Barbara, CA, August 23“25, 1982.
ory, St. Jovite, Quebec, Canada, September 26“30,
[51] Shamir, A. (1984). “A polynomial time algorithm
1983. Abstract of papers, 130.
for breaking the basic Merkle“Hellman cryptosys-
[38] Merkle, R.C. and M.E. Hellman (1978). “Hid-
tem.” IEEE Trans. Inform. Theory, IT-30 (5), 699“
ing information and signatures in trapdoor knap-
704.
sacks.” IEEE Trans. Inform. Theory, 24 (5), 525“
[52] Vaudenay, S. (1998). “Cryptanalysis of the chor-
530.
rivest cryptosystem.” Advances in Cryptology”
[39] Odlyzko, A.M. (1984). “Cryptanalytic attacks on
CRYPTO™98, Lecture Notes in Computer Science,
the multiplicative knapsack cryptosystem and on
vol. 1462, ed. H. Krawczyk, Santa Barbara, CA,
Shamir™s fast signature system.” IEEE Trans. In-
August 23“27, 1998. Springer-Verlag, Berlin, 243“
form. Theory, IT-30 (4), 594“601. Also presented
256.
at IEEE Intern. Symp. Inform. Theory, St. Jovite,
[53] Willett, M. (1983). “Trapdoor knapsacks without
Quebec, Canada, September 26“30, 1983. Abstract
superincreasing structure.” Inform. Process. Let-
of papers, 129.
ters, 17, 7“11.
[40] Odlyzko, A.M. (1985). “Discrete logarithms in ¬-
nite ¬elds and their cryptographic signi¬cance.”
Advances in Cryptology”EUROCRYPT™84, Lec-
ture Notes in Computer Science, vol. 209, eds. T.
Beth, N. Cot and I. Ingemarsson, Paris, France,
KNOWN PLAINTEXT
April 9“11, 1984. Springer-Verlag, Berlin, 225“
ATTACK
314.
[41] Odlyzko, A.M. Personal communication.
[42] Petit, M. “Etude math´ matique de certains
e Known plaintext attack is a scenario in which the
`
syst` mes de chiffrement: les sacs a dos” (Mathe-
e
attacker has access to pairs (Pi , Ci ), i = 1, . . . , N
matical study of some enciphering systems: The
of known plaintexts and their corresponding ci-
knapsack, in French). Doctorates Thesis, Univer-
phertexts. This attack is considered to be highly
sit´ de Rennes, France.
e
practical, especially if the amount of pairs N is
[43] Pohlig, S.C. and M.E. Hellman (1978). “An im-
not too large. This attack scenario is more prac-
proved algorithm for computing logarithms over
tical than the chosen plaintext attack. Probable
GF(p) and its cryptographic signi¬cance.” IEEE
word method which is a popular technique for
Trans. Inform. Theory, 24 (1), 106“110.
Known plaintext attack 343


solving classical simple substitution or transposi- cryptanalysis is a typical example of a known
tion ciphers is an example of a known-plaintext plaintext attack.
attack. Another example is the cryptanalysis of
Alex Biryukov
the German Enigma cipher (see cryptomachines
or [1]) using the so called bombs. It relied Reference
heavily on properly guessed opening words of
the cryptograms (which were at the time called [1] Deavours, C.A. and L. Kruh (1985). Machine Cryp-
cribs). One of the most popular cribs was “Noth- tography and Modern Cryptanalysis. Artech House,
ing to report”. In modern cryptography linear Boston, MA.
344

<<

. 2
( 2)