Abstract
We propose a variation of the Diffie and Hellman key distribution scheme for which we can prove that decryption of a single key requires the ability to factor a number that is the product of two large primes. The practical advantage of such a scheme is that it will still be secure if the cryptanalyst knows a very fast algorithm for either factoring or computing discrete logarithms, but not for both. Using these keys in the ElGamal public-key cryptosystem provides a scheme for which the decryption of a message requires the ability to factor the modulus and break the original Diffie and Hellman scheme.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Bach, Discrete Logarithms and Factoring, Technical Report UCB/CSD 84/186, Computer Science Division (EECS), University of California, Berkeley, California, June, 1984.
P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers,Mathematics of Computation,16 (1962), 363–367.
M. Blum, Coin flipping by telephone,Proc. IEEE Spring COMPCON, 1982, pp. 133–137.
D. Coppersmith, Fast evaluation of discrete logarithms in fields of characteristic 2,IEEE Transactions on Information Theory,30, (1984), 587–594.
D. Coppersmith and J. H. Davenport, An application of factoring,Journal of Symbolic Computation,1 (1985), 241–243.
D. Coppersmith, A. Odlyzko, and R. Schroeppel, Discrete logarithms in GF(p),Algorithmica,1 (1986), 1–15.
W. Diffie and M. Hellman, New directions in cryptography,IEEE Transactions on Information Theory,22 (1976), 472–492.
T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms,IEEE Transactions on Information Theory,31 (1985), 469–472.
M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
S. Goldwasser, S. Micali, and R. Rivest, A digital signature scheme secure against adaptive chosen message attack (extended abstract),Discrete Algorithms and Complexity; Proceedings of the Japan-U.S. Joint Seminar, Academic Press, Orlando, FL, 1987.
D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
N. Koblitz, Elliptic curve cryptosystems,Mathematics of Computation,48 (1987).
H. W. Lenstra, Jr., Factoring integers with elliptic curves,Annals of Mathematics, to appear.
K. S. McCurley, Digital Signatures and Public-key Cryptosystems Based on Discrete Logarithms and Factoring, Unpublished manuscript, 1986.
G. Miller, Riemann's hypothesis and tests for primality,Journal of Computer and System Science,13 (1976), 300–317.
V. Miller, Use of elliptic curves in cryptography,Advances in Cryptology (Proceedings of Crypto '85), Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, New York, 1986, pp. 417–426.
A. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance,Advances in Cryptology (Proceedings of Eurocrypt 84), Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, New York, 1985, pp. 224–314.
S. Pohlig and M. Hellman, An improved algorithm for computing discrete logarithms over GF(p) and its cryptographic significance,IEEE Transactions on Information Theory,24 (1978), 106–110.
J. M. Pollard, Monte Carlo methods for index computation (modp),Mathematics of Computation,32 (1978), 918–924.
R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public key cryptosystems,Communications of the ACM,21 (1978), 120–126.
Z. Shmuely, Composite Diffie-Hellman Public-Key Generating Systems Are Hard To Break, Technical Report No. 356, Computer Science Department, Technion-Israel Institute of Technology, February, 1985.
H. C. Williams, A modification of the RSA public key encryption system,IEEE Transactions on Information Theory,26 (1979), 726–729.
Author information
Authors and Affiliations
Additional information
Research supported in part by grants from the USC Faculty Research and Innovation Fund and the National Security Agency.
Rights and permissions
About this article
Cite this article
McCurley, K.S. A key distribution system equivalent to factoring. J. Cryptology 1, 95–105 (1988). https://doi.org/10.1007/BF02351718
Issue Date:
DOI: https://doi.org/10.1007/BF02351718