5 ms·
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 reas
by falcolas 9y ago
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.
- 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.