Posted by: **jonkatz** | July 13, 2009

## 112-bit EC discrete logarithm problem solved

As recently announced on the cryptography mailing list, a discrete logarithm problem on an elliptic curve over a 112-bit prime field was recently solved using a cluster of over 200 PlayStation 3(!) game consoles. (The group order was also 112 bits.)

The computation was done using a parallelized version of Pollard’s rho method, with some speedups that they will describe in a forthcoming research paper.

Some things that struck me while reading the details:

- The computational time was estimated to be only 3.5 months.
- The computational effort was estimated to be additions/multiplications of 112-bit integers. This is significantly more than bit operations.
- The computation required 0.6 Terabyte of disk space.
- I could not find out the cost of the cluster, but 200 PlayStation 3 consoles would cost roughly $70,000.
- By my calculations, they were carrying out roughly additions/multiplications of 112-bit integers per second.
- They claim that the computational effort was equivalent to 14 brute-force key searches of DES. If true, that means that DES keys can be brute-forced in 1 week.

Of course, the natural question is what this means for elliptic curve parameters used in practice. They claim that for 160-bit prime fields the computation is expected to take 16 million times as long (and so there is no immediate threat). The current ECC standard uses 160-bit fields, though this is being phased out in favor of longer key lengths.

### Like this:

Like Loading...

*Related*

Hi,

Maybe it’s because I do not know the meaning of computational effort. But, to me the it translated that they needed 10^18 operations in total which divided by 105 days and 86400 seconds per day and 200 game consoles, means roughly 550 million operations per second per game console but not 10^36

Am I right?

Shahab

By:

Shahabon July 15, 2009at 7:15 pm

Thanks. You are right; I meant .

By:

jonkatzon July 15, 2009at 8:05 pm