outer@utcsrgv.UUCP (Richard Outerbridge) (09/21/83)
Awhile ago someone asked for references on the cracking of the Merkle/Hellman knapsack (it takes awhile for net.crypt to get here). Anyway, the references I've seen are: 1) Kahn, David "The Crypto '82 Conference, Santa Barbara - A Report on a Conference", CRYPTOLOGIA Volume 7 Number 1 January 1983 pp1-5. Kahn describes the conference in general and the demonstration by Adleman with the Apple in particular. 2) Chaum, David; Rivest, Ronald and Sherman, Alan T. ADVANCES IN CRYPTOLOGY PROCEEDINGS OF CRYPTO 82, (New York: Plenum Press 1983). Three papers presented at the conference discuss the technique in some - but not all - detail. They are (pp279-308): 2a) Shamir, Adi "A Polynomial Time Algorithm for Breaking the Basic Merkle- Hellman Cryptosystem (Extended Abstract)" 2b) Brickell, Ernest F., Davis, J.A. and Simmons, Gustavus J "A Preliminary Report on the Cryptanalysis of the Merkle-Hellman Knapsack Cryptosystems" 2c) Adleman, Leonard M. "On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem" Referenced by 2b) is: Shamir, A., "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem", PROC. 23RD ANNUAL FOUNDATIONS OF COMPUTER SCIENCE, 1982. As far as the RSA system goes I too have heard unsubstantiated rumours that some government's gnomes have managed to crack it. Talk is cheap. On the other hand D.E. Knuth has stated "So far all that can be said for certain is that all of the ordinary ways to discover [the] roots will fail. (ACP Vol.2, 2nd Ed., p387)" utcsrgv/outer