Drugi kriptosistemi (nadaljevanje 5. poglavja)
Sheme za digitalne podpise (pričetek 6. poglavja)
Novembra 2002 je bil razbit 109-bitni izziv [ECCp-109]:
Chris Monico will receive a $10,000 US prize for solving the ECC 109
Challenge. We issued the ECC 109 challenge to demonstrate a real world
example of how difficult it would be to solve a single instance of an
ECC key even at a low strength, said Dr. Scott Vanstone, Founder and
Executive VP Strategic Technology for Certicom. The ECC 109-bit problem
was solved in the manner and timeframe we predicted. This challenge
also validates the security strength of ECC because the key solved was
well below the commercial standards our clients use today which is ECC
163 or higher. If someone were to try and solve ECC 163, it would be
approximately one hundred million times harder to solve than ECC 109.
Aprila 2000 je bil razbit še en izziv za diskretni logaritem
na eliptični krivulji [ECC2K-108] , ki ga je zastavil Certicom:
Robert Harley and colleagues, Damien Doligez, Daniel de Rauglaudre and
Xavier Leroy, found the 109-bit cryptographic key after four months of
computation distributed on 9500 computers with the help of 1300 volunteers
in 40 countries (Certicom's a cash prize for this was $10,000).
Two thirds of the computation were done on Unix workstations and one
third on Windows PCs.
On a single 450 MHz machine the computation would have taken 500 years.
The amount of work required to solve the ECC2K-108 challenge was about
50 times that required to solve the 512-bit RSA cryptosystem.
The method Harley's team used for solving ECC2K-108 is well known, having been introduced independently by Certicom researchers and Harley's team in 1998. Although the effort therefore provides no fundamental advances, it is nonetheless an impressive computational achievement that demonstrates the strength of distributed computer networks.
"Harley's team's accomplishment is an impressive example of the power of modern distributed computing," said Neal Koblitz, Professor of Mathematics at the University of Washington and co-inventor of ECC. "Their work shows the accuracy of Certicom's estimates of the amount of time required to solve the Certicom Challenges, and in this way reinforces our confidence in the security of ECC."
This extraordinary achievement demonstrates the high level of security that ECC (elliptic-curve cryptography) can offer with much shorter keys than RSA. It also highlights the relative weakness of some curves with special properties and confirms that for optimal security one should pick random curves with no special characteristics.
Harley's team's effort also supports Certicom's recommendation that keys of at least 160 bit ECC encryption should be deployed in practice. Solving a 163-bit ECC challenge is estimated to require about 100 million times the work expended to solve the 108-bit challenge. Več o tem najdete na http://cristal.inria.fr/~harley/ecdl/.