112-bit prime ECDLP solved

Tanja Lange tanja at hyperelliptic.org
Tue Jul 14 19:07:20 EDT 2009

> >We are pleased to announce that we have set a new record for the elliptic
> >curve discrete logarithm problem (ECDLP) by solving it over a 112-bit
> >finite field. The previous record was for a 109-bit prime field and
> >dates back from October 2002.
First of all congratulations to the team at EPFL!

> Which suggests that existing deployments should default to 128 bits. 
> with 160 bits being overkill.  Of course overkill does not cost much. 
> If one shoots someone the head, it is wise to follow up with a second 
> shot through the head at very short range just to be on the safe side.
James, do I really have to point out the obvious that just because 112 
bits is a new record this does not mean that 113 is undoable today. The 
coolness of this result is that a smallish cluster of low cost machines 
could do this computation in only half a year. 200 PS3s cost you no more 
than 200 x 400 USD at published prices - and less if you buy that many 
at once. So with about 1 000 000 USD and a full year you would get 122 bits 
already now and agencies have a bit more budget than this! Furthermore,
the algorithm parallelizes extremely well and can handle a batch of 100
targets at only 10 times the cost. 

So, yes, we sure will be able to break 130 bits in 2033 - but certainly
much sooner if anyone tries.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list