Slashdot Mirror
Factorization of a 768-Bit RSA Modulus
dtmos writes "The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"
We are forced to use 128-bit encryption for online banking!
Obama's legacy: (N)othing (S)ecure (A)nywhere and (T)error (S)imulation (A)dministration
WTF? 2^1024 != 2^768*1000
Screw you slashdot for making me type more than my perfectly concise statement above that gets the effing point across just fine.
So I just did a Wikipedia Crash course on RSA (I knew it was for public/private key encryption) and how it all works mathematically.
But I still don't know what they mean by Factorization, or what that exactly means.
I'm guessing they found all and compiled and tested the possible values and now have a nice big chart? Is 768-bit RSA now considered "broken"?
1024 bit RSA keys are already considered insecure due to the possibility of finding more efficient algorithms. 2048 is considered secure enough.
I'd agree with that for government and it's true that the military should phase out 1024, but does the general public need to worry?
How much is your data worth? Back it up now.
The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus.
In fact, the challenge list is defunct, the challenge having been canceled by RSA. The challenges are still scientifically interesting, so to call them obsolete is factually inaccurate.
Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
Or immediately if you are encrypting things now which you want to remain secret throughout the decade and beyond.
Ceci n'est pas une signature.
Or you could just use tiny atoms...but have you priced those lately? I'm not made of money!
Whenever something comes up involving work with very large numbers, I have to try to explain this seemingly simple concept to people and usually they look at me like I'm either insane or an idiot. The people that have a decent grasp of math and some common sense, though, get their minds blown and have a new respect for encryption, which is rewarding.
RSA Labs explains the meaning of factorization in the old Challenge FAQ:
http://www.rsa.com/rsalabs/node.asp?id=2094
Look at the section, "What does it mean when a Challenge Number is factored?"
It is interesting to note that this section of the FAQ makes an example of RSA-768 being cracked in 2010 -- turns out they were very close, whether they tried to be or not (the article states that the number was actually factored in Dec 2009).
GNFS doesn't work by trivial division by all possible divisors. In fact, GNFS is exponentially faster than trial division.
Factoring N with GNFS works by searching for a collection of square equations, i.e. ones trivially factorable into two parts, which are equal mod N. Once several of these are found you take the GCD of their values and the result is one of the factors. For an RSA number there are four possible results, two are useful (the factors) two are not (1 and N). GCD is very very easily to calculate fast. If you get a trivial result you try another set. It only takes a few candidates before the chance of failure is acceptably infinitesimal.
There are potentially three sets of crypto used - RSA, optional ephemeral Diffie-Hellman for more secure key exchange, and the symmetric crypto for message body encryption (typically 3DES or AES.) Symmetric crypto uses relatively short keys, typically 128 or equivalent-to-112 bits; the public-key algorithms use longer keys, but they have special forms so they _need_ to be longer.
Diffie-Hellman key exchange is roughly similar in strength to RSA encryption or signatures.
More importantly, if the Bad Guy can crack your RSA keys, then the Bad Guy can impersonate you in Diffie-Hellman key exchanges by doing a man-in-the-middle attack and forging signatures on the DH key parts.
So if you're using a 768-bit certificate for some reason, or a 1024-bit certificate and the NSA is out to get you, you're vulnerable. (If the KGB is out to get you, it's moot, because they'll sneak into your house or data center and put a keylogger in your keyboard. And if the Mafia's out to get you, they'll just threaten to break your kneecaps.)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
No, that's not the problem. Yeah, one time in a million or billion you might have RSA key parts that aren't really primes, but you can decide how paranoid you want to be, and that's not a practical attack. This factoring is taking the RSA public key n=pq and using a combination of good algorithms and lots of brute force to find p and q, and works even when p and q are genuine primes. If p were a fake prime, it might take less horsepower to find it, but this is cracking the hard problem, not just the occasionally-lucky case.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
This isn't just brute force - the algorithm research has meant that our ability to factor large numbers has been growing a *lot* faster than Moore's law. That doesn't directly apply to breaking DH, except to the extent that factoring is useful in breaking discrete logarithms or the algorithms used are useful for it.
The catch is that you usually keep an RSA key around for a while; DH is often used with ephemeral parameters as well as ephemeral keys, so even if you had a year-long DH crack, it might only let you steal one message. On the other hand, cracking RSA signatures lets you do a man-in-the-middle attack where you substitute your forged DH parameters (which you know) for the target's supposedly-securely-signed parameters.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Something like 256bits extra bits of encryption for every 5 or 10 years.
So well probably need approx 25Kbit keys if we are even to have a chance of keeping something encrypted for 100 years. 3Mbit keys for a 1000 years...
It's generally believed that if you can attack factoring, you can attack discrete logarithms, so Diffie-Hellman in integer prime-number bases is still risky, so if Quantum Computers ever get good enough to bother RSA, they'll be a real pain. On the other hand, Elliptic Curves may still be safe. Nobody's sure quite how safe (right now EC keys can be significantly shorter than factoring-based RSA or DH, but that may fall if there are theoretical breakthroughs, which is much less likely with factoring), but they may be enough, and at least the patents will have run out before Quantum Computers get good enough to factor numbers more interesting than 15.
But otherwise you're stuck with secret-key symmetric cryptography, or One-Time Pads. Remember Kerberos and the various other systems that depend on a Master Key locked safely in a Key Distribution Center? Remember couriers with briefcases handcuffed to their arms? Yuk! There were good reasons to use public keys instead!
There has been some work done on quantum-computer attacks on symmetric key systems, but AFAIK the best that it looks like they'll do in general is to effectively halve the key length, so that's easy enough to work around.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The basic Elliptic Curve Crypto math was published in 1986 and isn't patented, but there have been a lot of implementation techniques that let you use the stuff efficiently which have been patented. However, even many of those patents have expired already or will soon (plus some of them have problems with prior art that could sink them, but the prime example of that is the Apple/NeXT patent which expires Real Soon.) There are a bunch of patents that issued in 2001 that may be a problem, but even those expire in 2021 unless the US does a Disney and extends them.
The good news is that effective Quantum Cryptography is a ways off - it's unlikely that the next decade will give us widespread effective QC that can reliably factor big numbers, so we aren't likely to need wholesale replacement of free crypto with patented crypto before then.
On the other hand, if QC can also crack ECC, that'd be annoying.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
nm
So, 10^80 atoms in the universe, which is around 2^265, so 2^768/2^265 = 2^503, or a universe 2.6x10^151 times larger than ours (with all of the caveats I've pointed out elsewhere in this thread about how that's a very rough guesstimate.)
Thanks for pointing out my craziness. :)