Hacker News Reader

Comment by smegel | Hacker News Reader

Can someone explain what "breaking a prime" means? What is the output after your year of computation?

Assuming they are using an index-calculus attack, the output is the discrete logarithms of a set of small primes. (But who knows, they may have much better attacks.)

This is how that attack works. You generate a set of small primes called the base primes:

    2, 3, 5, 7, 11, ...

Then you generate powers of p which all factor in only the base primes. This creates a set of linear equations, which can be solved to find the discrete logarithm of all base primes.

This was all pre-computation. After this, to find the discrete logarithm of x, you generate powers of x until it factors in the set of base primes. Once that is found, calculating the logarithm is easy.

This requires a trade-off: the larger the set of base primes, the longer the first step takes, but the faster the second step is.

To clarify, I made an error: you generate powers of g (or just any group element whose discrete log you know), not p.

The output is a giant table of A= g^X mod p where given A you can look up x.

There's more to it than that, though - a table that could let you directly look up the discrete log of an arbitrary A would require on the order of 2^1024 entries (for a 1024 bit group).

It's a table specifically of the discrete logs of a large (but tractable) number of small primes. Those discrete logs can be used as the input to a separate stage that can calculate the discrete log of any value in the field.

The paper mentioned in the article shows how a few complex steps reduces to very large polynomial time, most of which can be precomputed given "45 million computer-years", the rest computed on a per-session basis very quickly.

Sounds like my PMATH assignment for this week :-)

Reply on news.ycombinator.com