November 11, 1997 5:25 PM PST
Certicom offers crypto contest
Certicom is offering prizes of up to $100,000 for the first person to break its keys, including some it believes can be broken.
The challenge is similar to contests run by Certicom rival RSA Data Security to illustrate that weak encryption algorithms--the only kind approved for export by the U.S. government--can be cracked.
Certicom aims to publicize its encryption as an alternative to RSA's, since elliptic curve cryptography is frequently challenged as being "untested" compared to RSA's algorithms, which have been well-known for years.
"We're trying to make sure that people have the chance to slug away at our system if they want and to put some money behind it," said Certicom chief executive Philip Deck, who unveiled the contest last week before a mathematics conference at the University of Waterloo.
"We don't think the hackers are going to make too many advances on this," Deck said. "The audience we launched it to are people who really understand the deep mathematics behind the curve."
Elliptic curve cryptography is regarded as more efficient than RSA algorithms for small devices without a lot of computing power--smart cards, cellular phones, and TV set-top boxes, for example.
The easier exercises, designed to get mathematicians comfortable with the elliptic curve algebra, involve breaking key lengths of 79, 89, and 97 bits. Certicom believes its 79-bit exercise can be solved in hours, the 89-bit in days, so the first person to do so gets a crypto handbook and software.
The company figures the 97-bit key can be broken in a matter of weeks--using a network of thousands of computers. The first person to break a 97-bit key gets $5,000.
But the real challenge begins in breaking keys of 109 and 131 bits--Certicom estimates the 109-bit key can be broken in several months with a network of 100,000 computers. Prizes are $10,000 for three separate 109-bit keys and $20,000 for 131-bit keys.
To back up its claim that breaking keys of 163, 191, 239, and 359 bits is "computationally infeasible," Certicom is offering cash prizes from $30,000 for breaking a 163-bit key to $100,000 for the 359-bit key. Certicom said 163-bit elliptic curve keys are the recommended minimum key size, claiming it is as secure as RSA algorithms of 1,024 bits.
"I don't think anybody is going to work on the 163-bit challenge," said Deck. "For anyone who really knows the area, it's too large a problem, so it's silly to start. It's a bit of a fruitless task."