July 24, 2001 6:30 AM PDT
RSA launches crypto-cracking challenge
Cryptography experts must determine the two prime numbers that have been used to generate eight "challenge" numbers, ranging in size from 576 bits to 2,048 bits. The first person to submit a correct factoring of any of the challenge numbers is eligible for a cash prize of between $10,000 for a 576-bit key to $200,000 for a 2,048-bit key.
The challenge is designed to test the strength of lengthy RSA algorithms and encourage research into computational number theory and the difficulty of properly factoring large numbers. The results of the competition will be used to determine the key lengths used in RSA encryption in the future.
"The cash prizes offered are intended as modest rewards for some of the hard work that goes into coordinating the resources and effort required to surmount some of the very difficult technical barriers encountered in factoring large integers," said Burt Kaliski, chief scientist at RSA Laboratories.
Factoring a number means representing it as the product of prime numbers--numbers that are not evenly divisible by any smaller number other than one. As the size of the number increases, the difficulty of factoring increases rapidly. To date, the largest algorithm of this type to be factored is 512 bits--RSA believes that the 576-bit value is likely to be rendered in the next year.
The Bedford, Mass.-based company said that the factoring of a challenge number of a specific length does not mean that the RSA cryptosystem is broken. "It does not even mean, necessarily, that keys of the same length as the factored challenge number must be discarded," according to the challenge guidelines.
But the outcome of the competition will establish an idea of the amount of work required to factor a number of a given size and offer an estimate of the cost of breaking a particular RSA key pair.
The new RSA Challenge replaces the RSA Laboratories' original challenge, which began in the early 1990s.
Staff writer Wendy McAuliffe reported from London.