Lausanne, Switzerland (GenevaLunch) - Mathematicians at EPFL, the Swiss federal polytechnic institute, used a cluster of more than 200 PlayStation 3 game consoles to spend six months solving an encryption problem, breaking a previous record set in 2002. The laboratory for cryptologic algorithms cracked a 112-bit encryption based on elliptical curves. The significance of the work is that it “may serve to boost our confidence in the strength of elliptic curve cryptography (ECC),” say the authors, led Joppe Bos and Marcelo Kaihara. Encryption is widely used in banking and other industries for security. The encryption industry struggles to stay ahead of code-cracking hackers, who are using increasingly sophisticated methods and calculators.

A 160-bit elliptical curve standard is scheduled to be phased out by the industry in 2010, but the EPFL calculation shows that “for the next decade no regular user needs to be overly concerned about the security of 160-bit ECC.”

The calculations began 13 January 2009 and were completed 8 July, with other work interspersed. The authors note that had the machines been free to run the calculations continually it would have taken 3.5 months. The 112-bit parameters are relatively small compared to the 160-bit and are used to “better understand how hard it would be to solve the supposedly hard mathematical problems underlying ECC.” The authors estimate that it would require an effort 16 million times as great to crack a 160-bit ECC.

The team says that “as far as we know our calculation is a new record for ECDLP (elliptic curve discrete logarithm problem) over prime fields. It beats the previous record of a curve over a 109-bit prime field which was set in 2002 requiring 549 days of computing by more than 10,000 members in almost 250 teams, spending the 2002 equivalent of a year of full time computing on 4000 to 5000 PCs.”

Details of the computation will be published later.

EPFL authors’ report, July 2009

Background

• “ID Quantique’s advanced encryption to help banks stay step ahead of cyber crooks”, 20 June 2007, GenevaLunch
• “Geneva Security Forum warns that quantam computers will signal end to today’s security”, 20 June 2007, GenevaLunch

You can leave a response, or trackback from your own site.