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