On Sun, Sep 20, 2015 at 11:26:23PM +0100, Peter Fairbrother wrote:
On 20/09/15 14:53, Georgi Guninski wrote:
Found this from a DJB paper:
http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf
Parallel Collision Search with Cryptanalytic Applications
Paul C. van Oorschot and Michael J. Wiener
CHECK THE DATE:
1996 September 23
Both authors are well-known.
Google says the paper was published in the Journal of Cryptology in 1999.
days...
The present day open ECC dlog record stands at about 114 bits, iirc: that method used ~2014 custom hardware, but not $10 million worth.
Thanks for the answer. So the DLOG records (Wikipedia gives 113 bits [1] as of 2010) break these in libressl/openssl: $ ./inst/libressl-2.2.3/apps/openssl ecparam -list_curves secp112r1 : SECG/WTLS curve over a 112 bit prime field secp112r2 : SECG curve over a 112 bit prime field And these are in quite gray area? secp128r1 : SECG curve over a 128 bit prime field secp128r2 : SECG curve over a 128 bit prime field And what is the computational power of the Bitcoin network (Allegedly they do 2^80 SHA hashes per week) in terms of DSA/ECC operations? AFAIK, for DSA this is just multiplication/squaring modulo prime for rho. [1] https://en.wikipedia.org/w/index.php?title=Discrete_logarithm_records&oldid=663284373#Elliptic_curves
I'd guess Oorschot and Wiener got something in the numbers wrong. It happens.
However the parallel collision search technique they describe is very real, and has been used to effect. At a guess, the ECC dlog record above probably used it, as will most modern collision search algorithms.
As DJB quoted them, I'd guess that they invented the technique (though I knew of the technique, I thought Knuth described/invented it).
It's one of those things which are obvious in hindsight; but which can be dev'lishly hard to come up with in the first place.
-- Peter Fairbrother