[Infowarrior] - 768-bit RSA cracked

[Richard Forno]

768-bit RSA cracked, 1024-bit safe (for now)
Researchers have posted a preprint that describes their method for  
factoring a number used for RSA 768-bit encryption.

By John Timmer | Last updated January 7, 2010 5:20 PM

http://arstechnica.com/security/news/2010/01/768-bit-rsa-cracked-1024-bit-safe-for-now.ars

With the increasing computing power available to even casual users,  
the security-conscious have had to move on to increasingly robust  
encryption, lest they find their information vulnerable to brute-force  
attacks. The latest milestone to fall is 768-bit RSA; in a paper  
posted on a cryptography preprint server, academic researchers have  
now announced that they factored one of these keys in early December.

Most modern cryptography relies on single large numbers that are the  
product of two primes. If you know the numbers, it's relatively easy  
to encrypt and decrypt data; if you don't, finding the numbers by  
brute force is a big computational challenge. But this challenge gets  
easier every year as processor speed and efficiency increase, making  
"secure" a bit of a moving target. The paper describes how the process  
was done with commodity hardware, albeit lots of it.

Their first step involved sieving, or identifying appropriate  
integers; that took the equivalent of 1,500 years on one core of a  
2.2GHz Opteron; the results occupied about 5TB. Those were then  
uniqued and processed into a matrix; because of all the previous work,  
actually using the matrix to factor the RSA value only took a cluster  
less than half a day. Although most people aren't going to have access  
to these sorts of clusters, they represent a trivial amount of  
computing power for many organizations. As a result, the authors  
conclude, "The overall effort is sufficiently low that even for short- 
term protection of data of little value, 768-bit RSA moduli can no  
longer be recommended." 1024-bit values should be good for a few years  
still.

Given that these developments are somewhat inevitable, even the  
authors sound a bit bored by their report. "There is nothing new to be  
reported for the square root step, except for the resulting  
factorization of RSA-768" they write. "Nevertheless, and for the  
record, we present some of the details." Still, they manage to have a  
little fun, in one place referencing a YouTube clip of a Tarantino  
film following their use of the term "bingo."