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.'"
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.
I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better
Atleast she doesn't do blowfish.
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
It's been a while since I studied this so take this with a grain of salt. I believe RSA involves 2 random large primes, 'p' and 'q' which are multiplied together to form a bigger number, 'n'. There is a bunch of other math to generate two more values 'd' and 'e' from 'p' and 'q'. The public key is 'n' and 'e', the private key is 'n' and 'd'. The math works that you can't get 'd' from 'e'. Factorization means just that, finding the factors of a number. In this case you're given 'n' which you know has only 2 factors ('p' and 'q' are both prime) so if you can factor 'n' and get 'p' and 'q' you can recalculate 'd' yourself and you now have the private key.
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).
do {print "Mini-Geek Rules!\n";}
until ($TheEndOfTheWorld);
And newly generated keys for PGP/GPG are suggested to be at least 4096 bits.
The whole moon and the entire sky are reflected in one dewdrop on the grass. - Dogen
Just to be accurate, I do not believe that in RSA you pick two primes but instead pick two values that are at least psuedoprime. Testing large numbers for primality is time consuming, but quick tests can eliminate nearly all composite numbers. The set of numbers that pass these quick tests but are not prime are called psuedoprimes, and are still usually pretty hard to factor.
"His name was James Damore."
Other people have explained factorization in this thread (finding the prime factors that make up a composite number), but I just wanted to point out why making a "nice big chart" won't work.
The "nice big chart" would have to be very big. If you wanted to factor all the numbers from 1 to 2^768, you'd need a chart with 2^768 entries on it. This chart would need to be made of something, or stored on a disk that was made of something. Made of something means it needs to be made of matter, which means it needs to be made of atoms. In the observable universe, there are about 2^84 atoms, so you'd need a universe around 8x10^205 times larger than ours to store the chart in.
That's why we need to be more proactive; instead of trying to eliminate all the invalid keys, we should just pick the strongest possible key and standardize on it.
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.
In the security world, there's always a tradeoff between the cost of the security, the cost to an attacker to break the security, and the value of the thing being protected.
In the military world, there are many secrets which need to be (are seen as needing to be) kept for many years. For these, an encryption that takes a year and $10M to break may not be good enough, because after a year and $10M, an enemy might have information worth more than that. For my bank account, encryption that takes a year and $10M to break is more than sufficient, because the value to an attacker is approximately $47.32, plus the overdraft fees that they can stick me with.
There is no current concern for the average person, unless you're dealing in nuclear secrets or are protecting a politicians date book. Given a choice in the future, moving to a larger RSA key size is prudent change, but that's about it.
And the worms ate into his brain.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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, which will always pass Carmichael numbers. 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.)
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Cryptographic strength, as applied to RSA keys, is measured by the time needed to factor the public modulus. The fastest way to do this is today is using the general number field sieve. The run time of the general number field sieve can be estimated as T(b) = exp(1.923 * ln(2^b)^(1/3) * (ln( ln(2^b)))^(2/3)), where b is the size of the input in bits. See Aoki's paper on a kilobit SNFS factorization for details. Chug through this estimate for b = 1024 and b = 768, and you'll find that the ratio is approximately 1000 (I got 1221.15). That's why 1024 bit RSA keys are approximately 1000 times stronger.