109-bit Elliptic Curve Cryptography knocked over with brute force

Source: Geeknews

Academics yesterday scooped a $10,000 prize after using a
distributed computing network to decrypt a message scrambled using an 109-bit implementation of Elliptic Curve Cryptography. The success of Chris Monico and his team of mathematicians from Notre Dame in solving the Certicom ECCp-109 challenge was achieved using raw computing power to brute force the key. There's no suggestion that either Certicom's algorithm or Elliptic Curve Cryptography itself is flawed. Commercial versions of Certicom's wireless encryption technology use 163-bit keys, which the firm estimates be one hundred million times harder to solve than ECC 109. Certicom's higher strength 163-bit encryption toolkits are used by many firms in the IT industry including Cisco, Motorola and Palm.

The Certicom ECCp-109 challenge, first posed in 1997, was solved by the Notre Dam team using a network of 10,000 computers (mostly PCs) running 24 hours a day for 549 days. $8,000 of their $10,000 prize money was donated to the Free Software Foundation. The challenge was designed to encourage further research into security standards while placing ECC under third party scrutiny. It is hoped the experience gained from this challenge will help confirm comparisons of the security levels of public key systems such as ECC, RSA and DSA that have been based primarily on theoretical considerations. Certicom is offering $20,000 in prize money for the solution to the next challenge, which involves solving a 131-bit key that is expected to require several thousand times more computing power than the ECCp-109 Challenge.

Of course, RSA has been running factoring challenges relating to its encryption technology for some time. Prizes ranging from $10,000 for the 576-bit challenge to $200,000 for a 2048-bits conundrum. The RSA algorithm is based on mathematics of prime numbers. Its security relies on the well established difficulty of factorising the products of two large prime number, against the ease of multiplying these numbers in the first place.

ECC uses a similar idea taken from the mathematics of elliptic curves. ECC is particularly beneficial in applications where bandwidth, processing, or battery power is constrained such as security for handhelds, mobile middleware and other embedded devices.