Solo Desktop Factorization of an RSA-512 Key

It was recently announced that Benjamin Moody has factored an RSA-512 bit key in 73 days using only public software and his desktop computer. The first RSA-512 factorization in 1999 required the equivalent of 8,400 MIPS years over an elapsed time of about 7 months. The announcement was made all the more intriguing in that it came from a mailing list associated with a user forum for Texas Instruments calculators.

The public key in question is used to verify signed OS binaries for the TI 83 Plus and the factorization means that

… any operating system can be cryptographically signed in a manner identical to that of the original TI-OS. Third party operating systems can thus be loaded on any 83+ calculators without the use of any extra software (that was mentioned in recent news). Complete programming freedom has finally been achieved on the TI-83 Plus!

The original post from Moody was not very informative, but the subsequent Q & A thread drew out more details. Moody used public source factoring software on a dual-core Athlon64 at 1900 MHz. Just under 5 gigabytes of disk was required and about 2.5 gigabytes of RAM for the sieving process. The final computation involved finding the null space of a 5.4 million x 5.4 million matrix.

Most security people would rightly claim that RSA-512 is known to provide little security as a key length, however this does not mean that 512-bit public keys are not in use today by companies other than Texas Instruments. By the way, someone is offering an RSA 512 factoring service with a “price indication” of $5000.

CORRECTION, Feb 19, 2010: The original post said the factoring was done in 73 hours when the correct value is 73 days, as pointed out in the comment below. Thank you to Samuel for pointing out the mistake.