Factorization of a 768-Bit RSA Modulus 192
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.'"
Re:Meanwhile in Canada... (Score:1, Informative)
Re:Meanwhile in Canada... (Score:5, Informative)
I hope this is a joke. If not, you are confusing the strength of symmetric key encryption and public key encryption. The latter requires larger key sizes because the public and private key pair are mathetmically related whereas in symmetric encryption, there is a single key, and it ought to be randomly generated, and have no mathematical relation to any other value.
The key sizes are given for RSA/DSA encryption. Elliptical curve crypto can use much smaller key sizes while maintaining equivalent security levels. Unfortunately, most ECC is patent encumbered.
Re:Meanwhile in Canada... (Score:3, Informative)
Re:Bad math... (Score:5, Informative)
They're comparing the relative strength of a 768 bit RSA key to a 1024 bit RSA key. Because of the mathematical correlation between the public and private keys, the strength is nowhere near 2^768 or 2^1024. RSA has created a comparison table for RSA -> symetric cipher strength.
1024 bit ----> 80 bit
2048 bit ----> 112 bit
3072 bit ----> 128 bit
However, "1000 times stronger" seems far too small, in any case.
Source: http://www.rsa.com/RSALABS/node.asp?id=2004 [rsa.com]
Re:Can someone explain this to me? (Score:5, Informative)
Re:Can someone explain this to me? (Score:5, Informative)
What they did was factor a 768-bit number, like one that could be used as a 768-bit RSA public key. e.g. to factor 15, you need to find that it is equal to 3*5, which can be easily done by dividing the first few primes and finding that 3 divides 15. To factor a very large number, like a 768-bit number that is semiprime with the two factors both about the same size, (as is the case with RSA public keys) is a very difficult task. It is currently best done by the General Number Field Sieve (GNFS). For more info on any of these concepts, use Wikipedia.
This demonstrates the possibility of breaking any given 768-bit RSA key by factoring the public modulus, and shows how much work that takes. Note, however, that it is still very difficult, and in this case took multiple years of calendar time and hundreds of years of CPU time to crack.
This does not mean that every 768-bit RSA key can be cracked any more easily than it could before, it just demonstrates that we have the ability to crack any 768-bit RSA key (given the time and resources).
Re:Can someone explain this to me? (Score:1, Informative)
No, solving discrete logarithms allows you to break the El Gamal public key encryption system. Like prime factorization, the discrete logarithm problem is considered "hard".
Re:Can someone explain this to me? (Score:5, Informative)
Re:Meanwhile in Canada... (Score:3, Informative)
Well, djb wrote a particular algorithm, Curve25519 [cr.yp.to], that's in the public domain.
(Yeah, yeah, save your comments about djb's personality. Like it or not, the guy's a crypto and security genius.)
Re:Can someone explain this to me? (Score:1, Informative)
Recovering an RSA secret key is no harder than the discrete logarithm problem. The RSA public key consists of the pair (e,n) and the associated secret key is (d,n) where any message 0<=m<n can be transformed into the ciphertext c=m^e mod n and the ciphertext can be decrypted as m=c^d mod n.
If one can solve the discrete logarithm problem over Z_n (integers modulo n), then one can recover the exponent d given the element m and a base c. One can simply encrypt arbitrary messages m to obtain a ciphertext c and apply the base c discrete logarithm in Z_n to obtain d.
Re:Meanwhile in Canada... (Score:4, Informative)
AES-256 uses a 256-bit key. It has a fixed block size of 128 bits, but that's unrelated to the key length.
There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively. So AES-192 is your best bet right now, though 2^119 or 2^128 are not exactly feasible attack keyspaces either.
Re:Meanwhile in Canada... (Score:5, Informative)
Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.
That is only helpful if the person sniffing the SSL connection doesn't capture the initial handshake.
The problem with symmetric crypto is key exchange. With SSL the client generates a premaster key, encrypts it with the server's public key, and sends it to the server. Then the client and server use this to derive a session key (at least, that is my reading of the relevant docs - I think the specifics depend on the exact cipher used). So, if you can crack the RSA key, then you can obtain the session key, which makes the entire session obtainable.
To use symmetric crypto you either need a shared secret, or you need to use a key-exchange technique. I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary. If factoring becomes easy we'll never be able to encrypt communications between parties unless they have a secure channel to exchange keys (typically involving plane tickets).
Disclaimer, I'm not a cryptographer and if somebody has more to add I'm all ears.
Re:Meanwhile in Canada... (Score:4, Informative)
He said patent encumbered, not copyrighted.
Something can be open source and if it implements something protected by patent in the US or in other nations with laws that allow software patents or have agreements to make US patents enforceable, then it can still be illegal to distribute, and you'd probably be liable for damages if you built commercial software, but IANAL.
I think the patent encumbrances of ECC are the reason it's mysteriously absent from a lot of commercial software that deals with security and even a lot of Linux distros and software. I'd have to double-check, but for example, I don't think Windows Certificate Services supports ECC.
P.S.: Isn't it horrible that Error Correcting Codes and Elliptic Curve Cryptography have the same acronym? IMHO, we should rename one of the TLAs before it becomes a PITA.
Re:Can someone explain this to me? (Score:5, Informative)
Testing large numbers for primality is time consuming, but quick tests can eliminate nearly all composite numbers.
More precisely probabilistic primality testing can be used to ensure that a number is not composite to any required degree of certainty. For example, with the Miller-Rabin test, each time you run the test you have a 3/4 chance of discovering that the number is not prime (assuming it's not). So, you run the test enough time to achieve the degree of certainty you desire. If you run it 100 times and each time the result is "prime", then there is only a 1 in 10^-13 chance that it is composite. Given that level of assurance, it's very reasonable to simply say "it's prime".
If it's not prime then the key will be significantly easier to break, but we just ensure that the odds of that are negligible and go about our business.
Re:Can someone explain this to me? (Score:5, Informative)
Some software, such as GPG, uses primality tests that don't actually converge to arbitrary certainty regardless of the number of iterations, because certain rare types of non-primes known as "pseudoprimes", which satisfy tests that usually only prime numbers satisfy, will pass all iterations. For example, GPG uses the Fermat primality test [wikipedia.org], which will always pass Carmichael numbers [wikipedia.org]. Since Carmichael numbers are extremely rare, though, it doesn't make a whole lot of practical difference.
(The Miller-Rabin test that you mention doesn't have any such category of pseudoprime.)
Re:Bad math... (Score:4, Informative)
Re:Can someone explain this to me? (Score:2, Informative)
No real point to this post, just a memory from 1987.
Re:Can someone explain this to me? (Score:3, Informative)
you could crack a 768-bit RSA in... roughly guessed... ...a third of a day.
Sorry, no. That doesn't take into account the fact that some parts can't be run in parallel on many home computers. Not to mention that the longest part, sieving, for a number this size, needs about 1 GB of RAM free, which I'd think people would be likely to notice and shut down pretty quickly...
Sieving is the step that takes the most time, in this case 1500 CPU years ("On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM per core, sieving would have taken about fifteen hundred years."), but can easily be run in parallel. Let's say you have access to 100,000 cores, each with at least 1 GB of RAM that you can use (read the PDF...). It will now take you 5.475 days to do the sieving.
Polynomial selection can, like sieving, be easily distributed, and is a relatively trivial task with 100,000 cores available. (roughly 20 CPU years, or under 2 botnet-hours, and a non-enormous amount of RAM)
The hard parts are the final steps: filtering, building a matrix, solving it, and finding the factors. You basically need one or more supercomputers to do it, with at least one of them having 1 TB of RAM and fast access to 5 TB of data. To do it like they did, you'd also need to write your own block Wiedmann implementation. If not, you'd have to use the block Lanczos, which can only be run on a single computer/supercomputer/cluster.
Doubtless, someone could botnet enough computing power to sieve for an RSA-768 key in a matter of weeks, but to actually finish it and get the factors would require an expensive supercomputer, be it purchased, (better hope whatever's behind that key is valuable...and thank goodness that they were stupid enough to use just a 768-bit key on it) botnetted, (good luck to get one and not have anyone notice!) or otherwise acquired.