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