Paper 2016/961

A kilobit hidden SNFS discrete logarithm computation

Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé

Abstract

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software. Our chosen prime $p$ looks random, and $p-1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our $p$ has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\mathbb{F}_p^*$, yet detecting that $p$ has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of backdoored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild.

Note: Final version as published in proceedings.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Eurocrypt 2017
Keywords
Discrete logarithmSpecial number field sieveTrapdoor
Contact author(s)
nadiah @ cis upenn edu
History
2017-07-18: last of 2 revisions
2016-10-05: received
See all versions
Short URL
https://ia.cr/2016/961
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/961,
      author = {Joshua Fried and Pierrick Gaudry and Nadia Heninger and Emmanuel Thomé},
      title = {A kilobit hidden SNFS discrete logarithm computation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/961},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/961}},
      url = {https://eprint.iacr.org/2016/961}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.