ijk@hou5e.UUCP (08/24/83)
About two months ago, there was an article posted by sibley at psuvax (Penn. State University) on cracking the RSA code. Also, I seem to remember some articles in the N.Y. Times that a version was crackable. I'm interested in the reaction and followup on this topic. Is anyone using an RSA code and considering changing it?? Is the knapsack method being investigated as an alternative (see Sci. Am, Aug 79, pp 146-157) since it is considered to be an NP-complete problem (the breaking of which would conceptually allow the solution to all problems in this class, if I understand correctly). Considering the great need for better computer security, (even the casual reader of newspapers is probably aware that a significant problem exists), this area should be of great concern to all of us, but little attention seem to have been paid to it. Any comments or references to current articles will be greatly appreciated Ihor Kinal AT&T Information Systems hou5e!ijk
stewart@ihldt.UUCP (08/25/83)
The knapsack public key cryptosystem (R. Merkle & M. Hellman, 1978) will not make a very good substitute for the RSA cryptosystem, since it has been broken by A. Shamir (the S of RSA). It turns out that while the knapsack problem is NP-complete, the special case of the problem used in the cryptosystem is not. Shamir found a way to transform the cyphertext into a simpler problem that can be solved without the secret key. It is still possible to further scramble the system so that Shamir's method does not work, but breaking the basic version casts doubts on variations. I don't have references (sorry about that). This was told to me by Marty Hellman, and I don't have much other information. Bob Stewart
paulsc@tekecs.UUCP (Paul Scherf) (08/26/83)
I don't know if this is the same thing you are talking about, but last Fall I heard about a scheme that seemed to cause a big to-do at the time. (Sorry, I don't have a reference. The scheme was told to me by someone who heard it from someone who received a phonecall from the originator.) The scheme as told to me was a way to figure out the (public) modulus given that you could get a bunch of "special" messages signed. (I guess it is supposed to be easy to get someone who signs lots of stuff to go for a "here, sign this". I guess then it wouldn't be too hard to get a bunch of these.) Before you hear the details (assuming I heard them right) it sounds like someone broke RSA, but afterward you realize someone figured out how to compute something that was already public information anyway. Paul Scherf, Tektronix, Wilsonville, Oregon, USA decvax!tektronix!tekecs!paulsc
chongo@nsc.uucp (Curt Noll) (08/27/83)
from my understanding on this topic, the RSA system has not been cracked, nor has a `proof' shown it to have a given level of security. the knapsack system as been smashed to bits by methods using repeating fractions. (an APPLE cracked the knapsack cypher challenge in a matter of hours to give you an idea of how bad it was cracked) i have used the RSA system quite a bit. while i dont have my notes in front of me, i do seem to recall alot of misinformation, and disinformation (some by our government) given about RSA. i offer some thoughts: 1) every non-trivial RSA system will generate a cyphertext which is the same as the plaintext. some systems using primes can result in every cyphertext being the same as every message! (not a very good security eh?) one can select a subset (a sizeable fraction of the primes) which will generate only 9 `non-mixed' cypertexts. 2) in general, not much is known about how well mixed the cyphertexts are from an RSA system. #1 deals with totally non-mixed items, but where the encode function is equivalent to a trivial function. chongo /\../\
ewa@gatech.UUCP (08/30/83)
In 1982, George Davide wrote a paper entitled "Chosen Signature Cryptanalysis
of the RSA (MIT) Public Key Cryptosystem." (Available as TR-CS-82-2,
University of Wisconsin -- Milwaukee, October, 1982.)
In that paper, Davida showed, in effect, that the following scenario is
possible, using the RSA Cryptosystem to digitally "sign" messages.
(Essentially the same techniques allow one to decrypt messages.)
SCENARIO:
Bob is a bad guy. He would like to get Alice to sign the message
"I Alice will pay you Bob ten million dollars."
Bob cunningly gets Alice to sign the messages
"I Bob will pay you Alice one million dollars." and
"I Bob will pay you Alice two million dollars."
(Note that Alice is likely to sign.)
Using the information in the signatures Alice gave, Bob is now able to
forge Alice's signature on the message
"I Alice will pay you Bob ten million dollars."
In a followup article, Richard DeMillo and Michael Merritt wrote
"Chosen Signature Cryptanalysis of Public Key Cyptosystems."
(Technical Memorandum, October 25, 1982, Georgia Institute of Technology.
This is available by writing DeMillo or myself at Georgia Tech,
School of Information and Computer Science, Atlanta, GA 30332, or by
writing Mike Merritt at Bell Labs, Murrray Hill, NJ.)
In that article, DeMillo and Merritt showed that the same flaw was shared
by a wide class of Cryptosystems.
(Note -- some of this info may be scheduled to appear in journals sometime.)
--
Eric Allender
CSNet: EWA @ GATech ARPA: EWA.GATech @ UDel-Relay
uucp: ...!{sb1,allegra,ut-ngp}!gatech!ewa ...!duke!mcnc!msdc!gatech!ewa