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.'"

Comments

Can someone explain this to me?

[Monkeedude1212]

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"?

Re:Can someone explain this to me?

[Digital_Quartz]

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.

Re:Can someone explain this to me?

[Sir_Lewk]

That is like saying RSA-16 (if such a thing existed) is not broken because the fasted way of cracking it is factorization. Brute force is a legitimate form of cryptoanalysis, particularly when it is computationally feasible. Calling an encryption scheme "broken" when an attack such as this is demonstrated is quite reasonable, no matter how inelegant you may find the attack.

Suggesting that DES is not broken is very silly because "not being broken" implies on some level that it is still acceptable to use.

New algorithms?

[Jonas Buyl]

1024 bit RSA keys are already considered insecure due to the possibility of finding more efficient algorithms. 2048 is considered secure enough.

The real scary part is 3 years to obsolecence

[DRAGONWEEZEL]

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?