<< . .

. 5
( : 6)



. . >>

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-

<< . .

. 5
( : 6)



. . >>