Record 232-Digit Number from Cryptography Challenge Factored

By John Matson
Scientific American
Friday, January 8, 2010

http://www.scientificamerican.com/blog/post.cfm?id=record-232-digit-number-from-crypto-2010-01-08

A team of researchers has successfully factored a 232-digit number into its two composite prime-number factors, but too late to claim a $50,000 prize once attached to the achievement. The number, RSA-768, was part of a cryptography challenge that technically ended in 2007 that had been sponsored by RSA Laboratories, a prominent computer-security firm. RSA-768, so named because its binary representation is 768 bits long, is the largest number from the now-defunct challenge to be cracked.

Thorsten Kleinjung of the Swiss Federal Institute of Technology in Lausanne, Switzerland, and his colleagues announced their result in a paper posted to the Cryptology ePrint Archive Wednesday. He and his colleagues note that larger numbers have been factored into primes but that those numbers are special cases that allow simpler factorization. (Prime numbers are divisible only by themselves and 1.)

The RSA Factoring Challenge offered up a list of massive semiprimes—numbers composed of two prime factors—representative of the sort used in RSA encryption, along with cash prizes of up to $200,000 for factoring them. RSA says that the challenges, which in the early days of computer security helped assess the robustness of encryption protocols, are no longer necessary to the field. "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common...algorithms, these challenges are no longer active," a statement on the company's Web site reads.

RSA cryptography relies on the fact that factoring numbers into large component primes is a difficult and time-consuming process—the new result required the equivalent of 2,000 years of computing on a single-core 2.2-GHz machine. In RSA cryptography, a large composite number can be shared publicly and used to encode encrypted messages, but the messages' decryption can only be quickly accomplished if the composite number's prime factors are known.

A famous demonstration appeared in Martin Gardner's Mathematical Games column in Scientific American in 1977. Gardner published an encoded message from the inventors of RSA cryptography, Ronald Rivest, Adi Shamir and Leonard Adleman, along with the large composite number (the product of a 64-digit and a 65-digit prime) used to encode it. Rivest, Shamir and Adleman, all then at the Massachusetts Institute of Technology, offered a $100 reward for cracking it, which Rivest estimated would have taken 40 quadrillion years with the technology of the day. But what seemed impossible in 1977 was accomplished in 1994, when a consortium including hobbyists and Internet-sourced volunteers claimed the prize.

Kleinjung and his colleagues note in their paper that the factoring of RSA-768 is a far cry from factoring a 1,024-bit encryption key such as those currently in wide use—such a factorization problem, they say, is about 1,000 times harder.

In any event, for those curious to see what 2,000 years of computing time can yield, the factorization of RSA-768 appears below:

1230186684530117755130494958384962720772853569595
3347921973224521517264005072636575187452021997864
6938995647494277406384592519255732630345373154826
8507917026122142913461670429214311602221240479274
737794080665351419597459856902143413

=

3347807169895689878604416984821269081770479498371
3768568912431388982883793878002287614711652531743
087737814467999489

x

3674604366679959042824463379962795263227915816434
3087642676032283815739666511279233373417143396810
270092798736308917

For further reading:
"768-bit RSA cracked, 1024-bit safe (for now)", John Timmer, Worlds Tech News, January 7, 2010
"768-bit RSA Keys Factored. 1024-bit Next", PC Magazine Security Watch, January 7, 2010