flackc@stolaf.UUCP (Chap Flack) (02/10/86)
*** ERCYNPR GUVF YVAR JVGU LBHE ZRFFNTR *** I just gave my senior comps talk on the RSA public key cipher, and after my talk, someone mentioned reading about a new factoring algorithm which is very efficient (i.e. much better than O(exp(sqrt(ln(n)*ln(ln(n)))))). This, of course, would have devastating implications for the security of the RSA code. Anybody else know about this? I think the person told me it had been developed by someone at MIT.
flackc@stolaf.UUCP (Chap Flack) (02/10/86)
For whatever reason, my last posting appeared without my .signature and with the wrong ORGANIZATION. Until I get this figured out (and, indeed, thereafter) I am (Chap Flack @ Carleton College, Northfield, MN) --------------------- Chap Flack ihnp4!stolaf!agnes!flackc Carleton College ihnp4!stolaf!flackc Northfield, MN 55057
plw@panda.UUCP (Pete Williamson) (02/12/86)
> >I just gave my senior comps talk on the RSA public key >cipher, and after my talk, someone mentioned reading about >a new factoring algorithm which is very efficient (i.e. >much better than O(exp(sqrt(ln(n)*ln(ln(n)))))). > >This, of course, would have devastating implications for >the security of the RSA code. Anybody else know about this? >I think the person told me it had been developed by someone >at MIT. > I recently heard (second hand) that RSA has been rendered effectively useless due to an advance in the strategy of factoring large numbers. Apparently the general factoring problem remains "difficult", but factoring large numbers that contain large prime factors is now provably "easy". I believe that the advance comes from MIT but I do not know who the researchers are. The National Security Agency also has known about this for some time, I have heard. Hope this helps. -- Pete Williamson "By hook or by crook, we will !!" ... #2
bs@faron.UUCP (Robert D. Silverman) (02/14/86)
> > > >I just gave my senior comps talk on the RSA public key > >cipher, and after my talk, someone mentioned reading about > >a new factoring algorithm which is very efficient (i.e. > >much better than O(exp(sqrt(ln(n)*ln(ln(n)))))). > > > >This, of course, would have devastating implications for > >the security of the RSA code. Anybody else know about this? > >I think the person told me it had been developed by someone > >at MIT. > > > > I recently heard (second hand) that RSA has been rendered effectively > useless due to an advance in the strategy of factoring large numbers. > Apparently the general factoring problem remains "difficult", but > factoring large numbers that contain large prime factors is now provably > "easy". I believe that the advance comes from MIT but I do not know > who the researchers are. The National Security Agency also has known > about this for some time, I have heard. > > Hope this helps. > > > -- > Pete Williamson > "By hook or by crook, we will !!" ... #2 Let me throw water on this nonsense before it goes any further. This information is first hand, not rumor or second hand. I currently possess the fastest factoring algorithm in the world today. I am in constant contact with the many researchers doing work on factoring and primality testing. The fastest known algorithms, of which there are several, all have complexity function: L(n) = exp( sqrt( ln(n) lnln(n))). Lenstra's elliptic curve algorithm, since it finds small factors first actually does better than this, on average, but still has the same worst case. The fastest algorithm for factoring a number which is the product of two nearly equal primes is a modification of Pomerance's Quadratic Sieve. The current record for factoring a number with two large prime factors is the 71 digit number (10^71-1)/9. It was done in 9.5 hours on a CRAY XMP in 1984 by a group of mathematicians at Sandia Labs. I anticipate announcing to the net in the next couple of days a new record, accomplished with an improved version of the algorithm running on a VAX!. It is a 75 digit cofactor of 6^128 + 1. Despite this, 100 digit numbers are still beyond practical reach. Maybe 10 CRAY 2's could do a 100 digit number in 1 or two months. I am publishing a paper on the implementation of the improved algorithm in "Mathematics of Computation". I'll be happy to provide pre-prints for those SERIOUSLY interested but please keep in mind that I can't handle too many requests. Just send me your US mail address. I have checked this rumor about a new algorithm with people at MIT and with others. Perhaps you are mistaking Shaffi Goldwasser's new primality test which uses elliptic curves with a factoring algorithm. Her new method runs in random polynomial time except for all but a few abnormal cases. Bob Silverman
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/16/86)
In article <1404@panda.UUCP> plw@panda.UUCP (Pete Williamson) writes: >I recently heard (second hand) that RSA has been rendered effectively >useless due to an advance in the strategy of factoring large numbers. >Apparently the general factoring problem remains "difficult", but >factoring large numbers that contain large prime factors is now provably >"easy". I believe that the advance comes from MIT but I do not know >who the researchers are. The National Security Agency also has known >about this for some time, I have heard. Yet another illustration of the folly of basing cryptosystems on the presumed ignorance of the "enemy".
jim@randvax.UUCP (Jim Gillogly) (02/17/86)
In article <1404@panda.UUCP> plw@panda.UUCP (Pete Williamson) writes: >I recently heard (second hand) that RSA has been rendered effectively >useless due to an advance in the strategy of factoring large numbers. >Apparently the general factoring problem remains "difficult", but >factoring large numbers that contain large prime factors is now provably >"easy". I believe that the advance comes from MIT but I do not know >who the researchers are. The National Security Agency also has known >about this for some time, I have heard. > >Hope this helps. It doesn't, actually. I know that there are recent results in proving that large numbers are prime (rather than "statistically almost certainly prime"), but haven't seen anything authoritative that tells who's come up with this algorithm, what it's based on, or in fact whether it really exists. Would somebody who would know whether it's been done (like David Cantor at UCLA, for example) please post either positive or negative *real* information? Thanks. -- Jim Gillogly {decvax, vortex}!randvax!jim jim@rand-unix.arpa
bs@faron.UUCP (Robert D. Silverman) (02/19/86)
> In article <1404@panda.UUCP> plw@panda.UUCP (Pete Williamson) writes: > >I recently heard (second hand) that RSA has been rendered effectively > >useless due to an advance in the strategy of factoring large numbers. > >Apparently the general factoring problem remains "difficult", but > >factoring large numbers that contain large prime factors is now provably > >"easy". I believe that the advance comes from MIT but I do not know > >who the researchers are. The National Security Agency also has known > >about this for some time, I have heard. > > > >Hope this helps. > > It doesn't, actually. I know that there are recent results in proving > that large numbers are prime (rather than "statistically almost certainly > prime"), but haven't seen anything authoritative that tells who's come > up with this algorithm, what it's based on, or in fact whether it really > exists. Would somebody who would know whether it's been done (like > David Cantor at UCLA, for example) please post either positive or negative > *real* information? > > Thanks. > -- > Jim Gillogly > {decvax, vortex}!randvax!jim > jim@rand-unix.arpa The Cohen-Lenstra prime proving algorithm can handily primes up to 200 digits quite readily on most mainframes in about (say) 1/2 hour and 300 digit numbers in several hours. Read their paper in Mathematics of Computation (1985, I don't recall offhand which issue). In fact it is possible to do 50% better than their paper describes by a fairly simple change. The complexity of this algorithm is ln(n) ^ (ln ln ln(n) ). Shaffi Goldwasser at MIT has turned recent interest in elliptic curves into a prime proving algorithm that runs in probabilistic polynomial time but it is not (currently) believed to be practical. It uses a theorem by Mordell that the group of rational points on an elliptic curve taken MOD p is finitely generated. We have an O( ln(p)^9) algorithm due to Schoof for computing the order of the curve MOD p but its relatively high exponent makes the method impractical. No paper on Professor Goldwasser's paper has yet appeared (I've requested but not yet received one). Bob Silverman
jlg@lanl.ARPA (Jim Giles) (02/19/86)
In article <476@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >... The current record for factoring a number with two large prime >factors is the 71 digit number (10^71-1)/9. It was done in 9.5 hours >on a CRAY XMP in 1984 by a group of mathematicians at Sandia Labs. >.... >Bob Silverman A minor correction: the number was factored on an X/MP-24 here at Los Alamos. The Sandia team wrote the code. (I had a very slight interest in this - I rewrote the Fortran intrinsic MOD function for this code to gain a 5% speed-up.) J Giles Los Alamos (10^71 - 1)/9 = 241,573,142,393,627,673,576,957,439,049 * 45,994,811,347,886,846,310,221,728,895,223,034,301,839
greg@utcsri.UUCP (Gregory Smith) (02/19/86)
In article <980@brl-smoke.ARPA> gwyn@brl.ARPA writes: >In article <1404@panda.UUCP> plw@panda.UUCP (Pete Williamson) writes: >>I recently heard (second hand) that RSA has been rendered effectively >>useless due to an advance in the strategy of factoring large numbers. >>... >Yet another illustration of the folly of basing cryptosystems >on the presumed ignorance of the "enemy". What else do you base them on?
falk@sun.uucp (Ed Falk) (02/20/86)
> > > > The Cohen-Lenstra prime proving algorithm can handily primes up to 200 > digits quite readily on most mainframes in about (say) 1/2 hour and 300 > digit numbers in several hours. Read their paper in Mathematics of > Computation (1985, I don't recall offhand which issue). In fact it is > possible to do 50% better than their paper describes by a fairly simple > change. The complexity of this algorithm is ln(n) ^ (ln ln ln(n) ). > > Shaffi Goldwasser at MIT has turned recent interest in elliptic curves If I remember correctly, the original RSA paper published by MIT asserted that proving whether or not a number is prime doesn't help you at all to factor one that isn't. I realize that that paper is out of date now, but I also remember that an earlier posting by Bob mentioned that the current record for factoring was a 71 digit number in 9.5 hours and that he expected that current state-of-the-art technology and the latest algorithms might be able to factor a 100-digit number in 1 or 2 months. I haven't got a calculator handy, but I suspect that O(exp(sqrt(ln(n) * ln(ln(n))))) is probably a lot larger for a 200-digit number than for a 100-digit number. ed falk
flackc@stolaf.UUCP (Chap Flack) (02/23/86)
> >Yet another illustration of the folly of basing cryptosystems > >on the presumed ignorance of the "enemy". > What else do you base them on? Well, suppose the problem of factoring a product of two large primes were *provably* hard. In that case, the security of the system would not depend on the enemy's ignorance. A more knowledgeable enemy would simply know better than to try to break it. In this particular case, the problem is not provably hard (at least, I haven't heard of a proof), but the idea is that you *can* imagine a cryptosystem that would not depend on the enemy's ignorance. -- --------------------- Chap Flack ihnp4!stolaf!agnes!flackc Carleton College ihnp4!stolaf!flackc Northfield, MN 55057
phillips@cisden.UUCP (Tom Phillips) (02/26/86)
In article <5119@stolaf.UUCP> flackc@stolaf.UUCP (Chap Flack) writes: >> >Yet another illustration of the folly of basing cryptosystems >> >on the presumed ignorance of the "enemy". >> What else do you base them on? >Well, suppose the problem of factoring a product of two large primes were >*provably* hard. In that case, the security of the system would not >depend on the enemy's ignorance. A more knowledgeable enemy would simply >know better than to try to break it. >In this particular case, the problem is not provably hard (at least, I >haven't heard of a proof), but the idea is that you *can* imagine >a cryptosystem that would not depend on the enemy's ignorance. Almost right. You ARE depending on the enemy's ignorance of your private key, aren't you?-- Tommy Phillips From the banks of the great grey-green greasy Limpopo River, all set about with fever-trees. cisden!phillips
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/03/86)
>>Yet another illustration of the folly of basing cryptosystems >>on the presumed ignorance of the "enemy". >What else do you base them on? How about information theory?
flackc@stolaf.UUCP (Chap Flack) (03/08/86)
> >In this particular case, the problem is not provably hard (at least, I > >haven't heard of a proof), but the idea is that you *can* imagine > >a cryptosystem that would not depend on the enemy's ignorance. > Almost right. You ARE depending on the enemy's ignorance of your private > key, aren't you?-- What's more, I'm depending on the enemy's ignorance of the original plaintext of the message I'm trying to send! :-) Does this mean that cryptology is a useless field? No. Through cryptology we are trying to protect information that has to be distributed and is therefore subject to interception. There are all sorts of ways to protect information that doesn't have to go anywhere (such as my original message and your private key)--these are physical security considerations, and needn't concern cryptologists. As for the physical security of the private key, Rivest, Shamir, and Adleman suggested one approach in their original paper: All of the logic for generating keys and {en/de}crypting messages is put into a dedicated piece of hardware with a physically secure cabinet. It generates your two keys for you, tells you one of them, and saves the other one internally in order to do the decryption. Your private key never leaves the box. If the cabinet is tampered with, the memory is erased. -- --------------------- Chap Flack ihnp4!stolaf!agnes!flackc Carleton College ihnp4!stolaf!flackc Northfield, MN 55057