<< . .

. 6
( : 6)



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

<< . .

. 6
( : 6)