Abstract
Using a number field sieve, discrete logarithms modulo primes of special forms can be found faster than standard primes. This has raised concerns about trapdoors in discrete log cryptosystems, such as the Digital Signature Standard. This paper discusses the practical impact of these trapdoors, and how to avoid them.
Chapter PDF
Similar content being viewed by others
References
T. Beth, M. Frisch and G.J. Simmons, eds., Public-key Cryptography, State of the Art and Future Directions, LNCS #578. Springer, 1992.
M. Blum. Coin flipping by telephone: A protocol for solving impossible problems, (Proceedings of the 24th IEEE Computer Conference, 1982, pp. 133–137.
E.F. Brickell and K.S. McCurley, An Interactive Identification Scheme Based on Discrete Logarithms and Factoring, Journal of Cryptology, to appear.
J. Buchmann and A. Pethö. Computation of independent units in number fields by Dirichlet’s method, Math. Comp., 52 (1989), pp. 149–159.
D. Coppersmith, A.M. Odlyzko and R. Schroeppel, Discrete logarithms in GF(p), Algorithmica, 1 (1986), pp. 1–15.
W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans. Info. Theory, 22 (1976), pp. 644–654.
D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM Journal on Discrete Math., to appear.
D.E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Second Edition, Addison-Wesley, Massachusetts, 1981.
B. LaMacchia and A.M. Odlyzko. Computation of discrete logarithms in prime fields, Designs, Codes and Cryptography, 1 (1991), pp. 47–62.
B. LaMacchia and A.M. Odlyzko, Solving large sparse linear systems over finite fields. Advances in Cryptology: Proceedings of Crypto’ 90, (A. Menezes, S. Vanstone, eds.), Lecture Notes in Computer Science. Springer-Verlag, New York, 1991.
H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math., 126 (1987), pp. 649–673.
A.K. Lenstra, H.W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 515–534.
A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard, The number field sieve, Proc. 22nd ACM Symposium on Theory of Computing (1990) pp. 564–572.
A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard. The factorization of the ninth Fermat number, preprint, 1991.
U.M. Maurer and Y. Yacobi, A non-interactive public-key distribution system, Advances in Cryptology: Proceedings of Eurocrypt’ 91, (D.W. Davies, ed.), Lecture Notes in Computer Science, Springer-Verlag, New York, 1991, pp. 498–507.
M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge University Press, Cambridge, 1989.
O. Schirokauer, On pro-finite groups and on discrete logarithms, Ph.D. thesis, University of California, Berkeley, May 1992.
C.P. Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, to appear.
M.E. Smid and D.K. Branstad. Response to comments on the NIST Proposed Digital Signature Standard, Advances in Cryptology: Proceedings of Crypto’ 92, to appear.
D.H. Wiedemann. Solving sparse linear equations over finite fields, IEEE Trans. Info. Theory. 32 (1986), pp. 54–62.
Specifications for a digital signature standard, National Institute for Standards and Technology, Federal Information Processing Standard Publication XX, draft, August 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gordon, D.M. (1993). Designing and Detecting Trapdoors for Discrete Log Cryptosystems. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_5
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive