Hacker News Reader

Comment by Cynddl | Hacker News Reader

> Our computations show that trapdoored primes are entirely feasible with current computing technology.

Can anyone explain to me what is the risk with such trapdoored primes? Thanks!

If I understand it correctly, it means that keys derived from such a prime number (such as via DH Key Exchange) can be factored and messages decrypted in a reasonable amount of time, where reasonable is less than a day.

I welcome correction.

EDIT: Time squeezed per tptacek, computation space reference removed per schoen.

>in a reasonable amount of time and space, where reasonable is less than a year, and 1kb.

I think kilobit refers to the prime field of 1024 bit. If you look at last page of the paper there is a table with the details of the cluster they used. Roughly 28 nodes with 512 GiB, 48 nodes with 64 GiB and a few bits and pieces.

See page 13. Given an SNFS-weakened 1024 bit prime, a single discrete log (ie, a break of a single handshake or signature) cost 80 minutes.

Also not "factored", but rather a discrete logarithm can be taken.

The apparent difficulty of factorization underlies some public-key systems (like RSA), while the apparent difficulty of extracting discrete logarithms underlies others (like Diffie-Hellman key exchange and DSA). This research is about the second problem.

The problems are closely related, and, in fact, the NFS algorithms are really IFP algorithms.

For instance, Private Internet Access recommended using 1024-bit certificates to linux users for a long time. This meant that the NSA probably had the resources to MITM your proxy through them.

No, that's not what this paper says.

You're right. Thanks for the correction.

Reply on news.ycombinator.com