At 03:28 PM 4/17/00 -0400, Perry E. Metzger wrote:
>
>Anyone know anything about this?
Hi Perry,
This brief compilation might help. This has been an impressive
achievement.
The comments of Harley and Morain in the InRIA press release, below,
are striking, given Certicom's historic committment to particular (as
opposed to random) Elliptic Curves. Other vendors (e.g., my friends at RSA)
sell ECC with random Elliptic Curves only, and have long argued that ECC
with particular curves is an unnecessarily risk. Individual critics like
Len Adleman have been even more pointed in their remarks.
Surete,
_Vin
---------------------------------
From the Elliptic Curve Discrete Logrithm (ECDL) Project webpage:
<http://cristal.inria.fr/~harley/ecdl/>
The biggest public-key crypto crack ever has just finished! Certicom
have confirmed that the solution is correct.
There is press coverage by Slashdot, National Post, ZDNet, Impress
(Japanese), Developer.com, Yahoo, Crypto-News (French), Punto Informatico
(Italian). [Links off the ECDL Project Website] More soon!
--------------------------------
A useful fact-sheet.
<http://cristal.inria.fr/~harley/ecdl7/factsheet.html>
--------------------------------
A technical FAQ.
<http://cristal.inria.fr/~harley/ecdl7/FAQ.html>>
Index
1. Why is this interesting? Is it all about cracking a code?
2. What is a discrete logarithm?
3. Remind me what a finite group is.
4. What is an elliptic curve and what is the group of points on it?
5. What is a finite field?
6. What is the ECC2K-108 problem?
7. What algorithm can we use to solve ECDL problems like ECC2K-108?
8. What are the iterations in "iterations per second"?
9. What are distinguished points?
10. What are the initial and current expectations?
11. How hard is the ECC2K-108 problem anyway?
12. How can I participate?
------------------------------------------------------------
>From the 4K Associates Press Release <http://www.4K-Associates.com/Press.html>
PARIS -- 13th April 2000 -- Irish mathematician Robert Harley and three
colleagues at INRIA, the French National Institute for Research in Computer
Science and Control, announced the solution to the most difficult public key
cryptographic challenge ever solved after a huge calculation on close to
10000 computers throughout the Internet. The challenge, called ECC2K-108,
was set by Canadian cryptographic company Certicom in 1997 to encourage
researchers to test the security of cryptography based on elliptic curves.
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.
<snip>
----------------------------------------
>From the InRIA press release at:
http://www.inria.fr/Presse/pre67-eng.html
<snip>
Arjen Lenstra, vice president at Citibank's Corporate Technology
Office in
New York and a participant in the project, noted "The amount of computation
we did is more than what is needed to crack a secret-key system like DES and
enough to crack a public-key system like RSA of at least 600 bits".
Harley remarked "Even so, it was only about one tenth of what should
normally be required for a 109-bit curve. That's because Certicom chose a
particular curve with some useful properties but we used those same
properties to speed up our algorithm".
He went on to say "This underlines the danger in adopting particular
curves and the need to pick random ones with no special characteristics. I'm
concerned about Koblitz curves and complex-multiplication curves, which
some people advocate using in order to avoid the point-counting problem".
François Morain, Professor of Computer Science at École Polytechnique,
explained:
"To use a curve for ECC one first has to calculate the number of
points on it,
which is quite a difficult task. To improve security one should use arbitrary
curves picked at random and change them frequently, but currently most
cryptosystems use fixed curves chosen to have particular properties which
make it easy to compute the cardinality. These very properties could one day
endanger them, as happened with super-singular curves. There have been
dramatic improvements in point-counting algorithms and good
implementations are now becoming available. Recent progress should soon
undermine any remaining argument in favour of special curves".
<snip>
----------------------------------------
>From the Cericom Press Release at:
http://www.certicom.com/news/00/apr1700.html
Hayward, Calif., April 17, 2000 - Dr. Scott Vanstone, Chief
Cryptographer
for Certicom Corp., is pleased to announce that a team of researchers led by
Robert Harley, Damien Doligez, Daniel de Rauglaudre and Xavier Leroy of
INRIA (France) have solved Certicom's ECC2K-108 Challenge. For this
achievement, Certicom is pleased to award them a cash prize of $10,000.
<snip>
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.
<snip>
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.
<snip>
-------------------------------------------------------
The ECC2K-108 Timeline:
April 4th:
- Solved! We got the matching points.
March 22nd:
- N.A.P.L.M. virtual pilots merged with the INRIA team - competition is
heating up at the top!
March 17th:
- St. Patrick's day: join us for a virtual pint!
March 9th:
- We passed the 50% chance-of-having-finished mark last night. There's no
sign of matching points just yet though...
February 26th:
- Version 1.1.1 of the 32-bit code is out. Main difference: it's slightly
faster.
February 21st:
- HTTP connections with our server failed briefly this weekend. Some people
may have points that were not sent.
Grep your ecdl.log file for "send by hand". See here for details.
February 16th:
- Apache is going from strength to strength. Read all about it at the
Netcraft Web Server Survey.
January 16th:
- Distributed.net just announced that they found the CS-Cipher key.
Congratulations, guys!
January 11th:
- There are now more than 1000 people participating. We have found 300000
points using over 3500 machines!
January 1st:
- Happy new year to everybody!
- OK, so there was no Y2K disaster. Now let's switch those machines back on
and get the daily rate back up again...
December 31st, midday:
- Happy new year to ECDL-ers in New Zealand!
- Let's see what this Y2K thingie does to our statistics. Not the "bug" of
course, but people turning off machines to
"solve" it.
December 25th:
- We have more than 100000 points already.
- Merry Christmas everybody!
December 21st:
- Passed 5% and we're accelerating fast!
- Watch out Debian: here comes No Team Yet, the team of people who aren't in
any team. =:-)
December 13th:
- Version 1.1.0 ready for the big time.
- We now need as much publicity as we can get.
- If you are reading this and can do something about it, then please help!
December 10th:
- Windows port with nice installer.
December 7th:
- HTTP mode added.
December 3rd:
- Version 1.0.0 announced on ecdl-announce.
December 1st:
- Call for testers of version 0.99.0.
