5 ms·
> Our computations show that trapdoored primes are entirely feasible with current computing technology. Can anyone explain to me what is the risk with such tra
by Cynddl 9y ago
> 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!
- falcolas 9y agoIf 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.
- weinzierl 9y ago>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.
- tptacek 9y agoSee 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.
- schoen 9y agoAlso 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.
- tptacek 9y agoThe problems are closely related, and, in fact, the NFS algorithms are really IFP algorithms.
- AlexCoventry 9y agoFor 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.
- tptacek 9y agoNo, that's not what this paper says.
- AlexCoventry 9y agoYou're right. Thanks for the correction.