ADVERTISEMENT
  About the SA Blog Network













Observations

Observations


Opinion, arguments & analyses from the editors of Scientific American
Observations HomeAboutContact

Record 232-digit number from cryptography challenge factored


Email   PrintPrint



RSA key challengeA 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

Image: ©iStockphoto/kazina





Rights & Permissions

Comments 7 Comments

Add Comment
  1. 1. candide 9:30 am 01/8/2010

    Crypto keys now are routinely 1024, 2048 or more bits.
    The fact that it took this long to factor an older standard is still impressive.

    Link to this
  2. 2. Trafalgar 12:10 pm 01/8/2010

    My world for a quantum computer.

    Link to this
  3. 3. Quinn the Eskimo 1:12 am 01/9/2010

    So, what was the message it encrypted? Was it important?

    The recipe for Bud Light?

    Link to this
  4. 4. thomasbartonjd 12:46 pm 01/9/2010

    This is an impressive achievement which only hints at what an NSA sponsored and supported Supercomputer Terabyte plus machine could achieve, especially if it is using algorithms which are not in the public sphere of discussion. These folks who think that larger encryption based keys are safe and secure should think about what is possible when several Terabyte machines are linked to crunch what they believe is uncrunchable.

    Link to this
  5. 5. atheon86 2:49 pm 01/9/2010

    It was in fact the recipe for bud light:

    (NH2)2CO + H2O

    Link to this
  6. 6. Leonard 9:01 pm 01/12/2010

    Factoring big numbers is beyond me. It looked like a challenge to check the math so I multiplied the one 116 digit number with the other 116 digit number and I got the same 232 digit number shown. Writing and debugging a Qbasic program took a few hours but the 486 gives the answer in about 30 seconds.

    Link to this
  7. 7. sir adam 8:12 am 03/19/2012

    very nice to see it and thank you for sharing it here

    Link to this

Add a Comment
You must sign in or register as a ScientificAmerican.com member to submit a comment.

More from Scientific American

Scientific American MIND iPad

Give a Gift & Get a Gift - Free!

Give a 1 year subscription as low as $14.99

Subscribe Now >>

X

Email this Article

X