Friday, January 08, 2010

768bit RSA not safe anymore, 4096bit to go soon...

Using RSA encryption means you base your security on the lack of resources of people trying to break your code. Well, that's saying very little, as the required computational power is indeed not accessible to most individuals, yet the same is not true for some organizations. And when we are talking about "organizations trying to break your code" we are, of course, going above the few hackers that employ a few thousand bots and that normally would have no reason to crack your communication, and going directly to the more likely culprits, mainly governmental organizations. And given their propensity for secrecy and paranoia, maybe even 1024 RSA is not really safe. After all, in "lands of freedom" there are laws against exporting software that employs too powerful an encryption, like 1024bit RSA. And that's an old law.

Anyway, here is a news link about the 768bit RSA cracking and, for the math inclined, a link to the actual paper. A list of the different RSA bit lengths and the known efforts to break them is found here.

A little quote from Wikipedia, showing that the limit is not really 768: As of 2010, the largest (known) number factored by a general-purpose factoring algorithm was 768 bits long, using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 300 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. Keys of 512 bits have been shown to be practically breakable in 1999 when RSA-155 was factored by using several hundred computers and are now factored in a few weeks using common hardware. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long.