Hacker News new | comments | ask | show | jobs | submit login

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 :-)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: