A kilobit hidden SNFS discrete logarithm computation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2016

A kilobit hidden SNFS discrete logarithm computation

Résumé

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 back-doored 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.
Fichier principal
Vignette du fichier
paper.pdf (362.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01376934 , version 1 (07-10-2016)
hal-01376934 , version 2 (18-07-2017)

Identifiants

Citer

Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. A kilobit hidden SNFS discrete logarithm computation. 2016. ⟨hal-01376934v1⟩
588 Consultations
453 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More