By John Matson
Friday, January 8, 2010
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:
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