The solution to what is being called the most difficult public-key cryptographic challenge ever has been solved. After four months of number-crunching, a large distributed network of computers worldwide has cracked an encryption method that will likely secure the next generation of wireless phones and other devices.
The challenge, which was dubbed ECC2K-108, was set by Canadian cryptographic company Certicom Corp. and was designed to encourage researchers to test the security of elliptic curve cryptography (ECC), which calculates the number of points on a curve and uses that information to generate keys that secure data. The cryptographic challenge was solved by Irish mathematician Robert Harley and Damien Doligez, Daniel de Rauglaudre and Xavier Leroy of the French National Institute for Research in Computer Science and Control (INRIA).
The INRIA team revealed a brute-force collaborative effort by 9,500 computers on the Internet had found the 109-bit key that had been used to scramble a message. The effort, which was completed on April 4, included 1,300 volunteers in 40 countries. Two-thirds of the work was done on Unix workstations, while the other third was done on Windows PCs. On a single 450MHz machine, the computation might have taken up to 500 years to complete.
ECC could be useful for mobile devices built around low-power processors, because the algorithms require less computational power to encode and decode data.
Rohit Khare, president of security research group 4K Associates in Irvine, Calif., notes ECC keys can be up to 100 times faster and five times smaller than 1,024-bit RSA keys. “It’s very important to find faster and smaller encryption codes, and this demonstration shows elliptic-curve technology that can be a fraction of the size and done much more quickly on more limited computers is just as strong,” Khare says.
But the cryptographic challenge highlighted the relative weaknesses of some curves with special properties and confirmed that random curves are best for optimal security. Harley notes the computation was only about one-tenth of what normally should be required to crack a 109-bit curve because Certicom chose a curve with properties that helped speed up the attack.
