main issues subscribe advertise contact links

RSA Contest

174 Digits Away From $10,000

by Eric Caron

Want $10,000? If you answered no, check your pulse. RSA Security, a security consulting firm, is offering $10,000 to whoever can find two factors of a 174-digit number, and if you're feeling exceedingly adventurous (not to mention like a super-genius), they will give $200,000 for factoring a 617-digit number. Unfortunately, this is by no means a get-rich-quick scheme.

One contender in the contest, distributed.net (both the organization's name and its web address) is combining the donated computing power of over 307,744 computers to try and solve the problem. Testing 18,446,744,073,709,551,616 possible factors takes a long time, and distributed.net anticipates breaking the code in 504 days at their computing rate as of October 9th, 2001.

Easiest number to decode:
188198812920607963838697239461650
439807163563379417382700763356422
988859715236654853190606065047430
453173880113033967161996923212057
34031879550656996221305168759307650257059

RSA defines security standards of data encryption used everywhere from the encoding of government messages to security for online personal shopping. RSA hosts these contests because they give RSA and the government an idea about how much it would cost to buy the computing power needed to decrypt a single message. Finding the factors for the contest does not break any real encryption scheme, but the speed with which the factors are found provides an estimate of what level of security various encryption schemes provide. By current estimates, factoring the 174-digit number would take 95,000 500 MHz Pentiums, each with 4 gigabytes of RAM, a year to compute. Therefore encoded messages that are worth more than the set-up of 95,000 computers would need a higher level encryption scheme, and messages worth less than that can use shorter numbers for encryption.

While RSA expects the 174-digit problem to be solved in a year, they expect the 617-digit problem to stand for at least a decade. If you’re bored, with time to kill, the 174-digit number is on this page, and links to helpful web sites to get you started are on the Technolog's web site. If you do manage to discover the factors and win the prize, don't forget what magazine told you about the contest and gave you that helping hand.

Interesting Note: Method & Security Used To Generate The 8 Contest Numbers: First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port. The random bytes were used as the seed values for the B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file. The moduli were extracted from the DER files and converted to decimal for posting on the Web page. The laptop's hard drive was destroyed.

FOR MORE INFORMATION:
stats.distributed.net/rc5-64/
www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
www.rsasecurity.com/rsalabs/faq/
n0cgi.distributed.net/faq/index.cgi?file=28
www.rsasecurity.com/rsalabs/challenges/factoring/faq.html