New type of encryption cracked

Experiment proves the difficulty of cracking an elliptic-curve discrete logarithm, which could be useful for business.

The most difficult asymmetric encryption problem ever tackled has been cracked by a horde of crypto-enthusiasts under the leadership of Irish mathematician Robert Harley.

This problem was the seventh and most difficult problem posed by the French National Institute for Research in Computer Science (INRIA) as part of the Elliptic Curve Cryptosystem (ECC) Challenge, sponsored by Canadian encryption technology firm Certicom.

Cracking it took a formidable combined effort from 195 volunteers in 20 different countries across the globe and took no less the 40 days of solid computation by 740 separate computers.

Asymmetric encryption is encryption that uses both a public and a private key. Symmetric, utilising two private keys, takes more number crunching, but the use of public and private keys is vital to commercial encryption methods.

Harley, who organised this mammoth effort, and also coded the computer program needed to combine such far-flung computing power, was clearly pretty chuffed with his achievement. "This is the most difficult asymmetric encryption ever broken. Although people have used more computational power to break stuff, this was a massive effort."

Harley also not only paid tribute to the volunteers involved but commended the spirit of free software saying: "There was everything from guys sitting in front of their Windows systems to the most powerful workstations you can buy, working in Australia. One reason why things worked well is that $4000 of the $5000 prize money was going to the Free Software Foundation, and everyone felt that this was a really good cause."

This feat has more than just philanthropic connotations however. It confirmed that solving a 97-bit elliptic-curve discrete logarithm is indeed more difficult than factoring 512-bit RSA asymmetric encryption, the industry standard at the moment. And far from implying this type of encryption is flawed, the experiment actually strengthens the argument for elliptic-curve encryption to replace the RSA method as standard.

Harley obviously holds this view, adding, "Our results increase confidence in the difficulty of breaking elliptic curve codes, and should be taken into account in standards for Internet security."

British encryption expert Brian Gladman, who in fact wrote the software for Windows users taking part in the project, says that this is an important development in the field of cryptography. "This is a significant step forward," he says. "The point is to prove that elliptic-curve encryption is secure. It's much newer than RSA encryption and people are naturally concerned about how hard it is to break."

Harley, Galdman and company are now working on software that will be used for the next challenge: breaking 108-bit elliptic curve encryption. Galdman is obviously looking forward to this contest: "108-bit is the next one, and that is going to be really big," he says. "I'm actually working on the Windows software, and hopefully we should be recruiting teams in the next couple of weeks."

Anyone wishing to get involved need only contribute spare computing power on their PC, which is only used when the computer is dormant. The software required will be available for download from Harley's Web site.