Tim Mays writes:
I refer readers to the sci.crypt FAQ, the RSA FAQ, or books such as "Applied Cryptography." (Hint for those who don't want to: one time pads (Vernam ciphers) and things like RSA with 1000-digit moduli.)
("Enough effort" can be interpreted in a circular way to ensure the answer is 'Yes," as a truism. This is meaningless, if "enough effort" is impossible to achieve, as with OTPs, or is beyond the energy in the universe. If "enough effort" is interpreted to mean theft or rubber hose crytanalysis, all bets are off. But most people who ask the question I cited don't mean these loopholes.)
I have seen Tim posting statements to this effect many times, and because he is one of the more well respected and listened to voices on the list, I feel it important to examine this in some detail. While I agree that 1000 bit moduli in RSA is adequate protection *in all probability*, for even national security secrets, I think it is far from clear that this will definitely be true 10, or even 5 years from now. Instead of just waving vague generalities around, though, let's do some nitty gritty calculations: The people who cracked RSA-129 themselves have stated that they believe a 1024 bit modulus is at most 20,000 to 2,000,000 times more difficult to crack than RSA-129. For example, I recall Derek Atkins posting that he estimated a 1024 bit key to be 40,000 times harder than a 512 bit key, although I didn't save the posting. And Paul Leyland of Oxford posted:
RSA-129 is 425 bits; rather harder than 384-bit numbers. We estimate that 512-bit keys are about 20 times harder than RSA-129, if a more efficient but available algorithm is used. No-one knows how much harder 1024-bit numbers are, but they will be no where near a trillion times harder than 384-bit keys. Best estimates suggest that 1024-bit numbers are about 10^4 to 10^5 times harder than 512-bit numbers.
OK, so the people in the civilian world working on this today say it is possible that a 1024 bit key is only 20,000 times harder than RSA-129 *using known algorithms*. Now let's really get our hands dirty: cracking RSA-129 was estimated to take 5000 mips years. The NAL NWT 2/140 computer installed at the National Aerospace lab in Tokyo is estimated at 357 Cray YMP equivalents. I estimate this to be equivalent to 200 Gips for the purposes of this computation (this is possibly where I am most off). 5000 mips years = 1.58 X 10^17 instructions. This comes out to 9.13 days on the NAL NWT 2/140. If my estimates above are correct, scaling up to the 7400 Cray equivalent computer due to be installed 4Q95, from the 357 Cray equivalent above, we go down to 10.5 hours. This is all for the RSA-129, of course. Still sounds pretty safe so far... if it really takes at least 20,000 times as long to crack a 1024 bit modulus, then it would still take the 7400 C.E. (Cray Equivalent) computer 24 years to crack a 1024 bit number. BUT, the biggest worry is that no one knows how good the NSA's factoring algorithms are. I read recently that the NSA is the world's largest employer of mathematicians. The relative improvement in factoring algorithms since the introduction of the RSA-129 problem, to its factoring almost 20 years later, far exceed even the exponential increase in computer speed over that same period of time. (5 orders of magnitude? more?) We have no way of knowing how many orders of magnitude leeway we have, because as the moduli get larger, the factoring algorithm gets more and more important. Suppose the NSA has four orders of magnitude on us in the efficiency of their factoring algorithms. In that case, they might be able to crack a 1024 bit key as early as the end of 1995. (20,000 X 10.5)/10^4 hours = 21 hours required). Granted, this may not be likely, but I think we have to take the possibility seriously. At this point, 1024 bit keys cease to be secure for matters of critical national security (but still good for everything else). Now let's continue with our worst case scenario... suppose that computer speed doubles every 3.3 years over the next decade, and that further algorithmic breakthroughs continue to at least match this rate of doubling (not likely, perhaps, but *possible*). Then just one decade later, in 2005, the computer power of the NSA is 8 times greater, and the algorithms are 8 times faster, for a total speed increase of 64. At this point, they could crack a 1024 bit key in just 20 minutes (using all their resources), or 72 keys per day. At this point, I start to be uncomfortable trusting my security to a 1024 bit key length. So, it seems *possible*, even if by no means probable, that a 1024 bit key length is only good for the next decade or so. My intent is not to foster paranoia, but cypherpunks, of all people, should take as critical a view of key length security as possible. I suggest that people who state that the want 1200 bit or even 2000 bit key sizes in PGP be no longer ridiculed... the issue is subjective, as we have no way of knowing what the NSA's factoring algorithms are like. Doug ___________________________________________________________________ Doug Cutrell General Partner doug@OpenMind.com Open Mind, Santa Cruz ===================================================================