Aw, but 8000 is easy-peasy. Now 40000 is another matter altogether. =:-)
ObRelevantPlug: http://pauillac.inria.fr/~harley/ecdl6/readMe.html
Eugene Leitl wrote:
>Brute-force is walking through search space vs. a
>cryptoanalysis. There is no point in brute-force, period.
I tend to agree with this. Exhaustive search of DES is long but
relatively uninteresting, requiring no mathematics and no algorithm
other than "try all possibilities".
However this elliptic curve thingie is a really interesting
mathematical problem. If it was used as a code then the key-length
would be 97-bits so brute force is out of the question. There is a
smart algorithm in there.
Also coordination of all the workers is essential. Unlike brute force
no individual will find the solution, although two individuals will
find the first match between two 'distinguished points' which will
allow the solution to be computed. There is a slightly strange effect
that if we leave the calculation running a bit longer, then the
solution will be found over and over, faster and faster by other pairs
of people.
Rohit Khare wrote:
>Just like the DES Cracker proving once and for all that DES-56 is
>inadequate, Rob's work will have repurcussions.
I like to think so. For the last calculation, called ECC2K-95, we
used a new smart algorithm that solved it in a tenth of the expected
time. The only reason it didn't cause shock-waves is luck and good
spin-control by Certicom: they independantly found a similar method
just in time, rushed out a paper about it and silently down-graded the
difficulty estimates on their Web pages. Now everyone thinks they
invented the method even though Ari Singer (a mathematician at Pitney
Bowes) and myself found it about two months before.
The reason that method worked was because the elliptic curve had a
special form that is particularly vulnerable, but Certicom kept
pushing that form because they have a few relevant patents (including
ridiculous things like "how to multiply"). However in recent
conferences they seem to have finally conceded that picking such
special curves is Probably Not A Very Good Idea.
This ECC2-97 problem doesn't have the required special form but the
next one, ECC2K-108, does. If we manage that we will be within a
hair's breadth of the 112-ish bits that Wassenaar limits you and me to
(and the NSA limits 'merkuns to).
The DES cracks may not have had much influence on American policy but
they sure did in other places. I don't doubt that they played a role
in convincing Jospin to free up the use of cryptography in France and
tell French spooks to get lost.
I hope that solving these elliptic curve problems will have a positive
effect on policy in at least some enlightened countries.
Plus, the Free Software Foundation gets to collect a bunch of cash.
Bye,
Rob.
PS: Plus, it helps me get my thesis done.