Abstract
We consider the problem of solving systems of equations P i(x) ≡ 0 (mod n i) i = 1...k where P i are polynomials of degree d and the n i are distinct relatively prime numbers and x < min n i. We prove that if k > d(d+1)/2 we can recover x in polynomial time provided n i > > 2k. This shows that RSA with low exponent is not a good alternative to use as a public key cryptosystem in a large network. It also shows that a protocol by Broder and Dolev [4] is insecure if RSA with low exponent is used.
Supported by an IBM fellowship, partially supported by NSF grant DCR-8509905
Chapter PDF
Similar content being viewed by others
References
Alexi W., Chor B., Goldreich O. and Schnorr C.P. “RSA/Rabin Bits are 1/2 + 1/poly(logN) Secure” FOCS 1984 pp 449–457
Awerbuch B., Chor B., Goldwasser S. and Micali S. “Provably Secure Coin Flip in a Byzantine Environment”, manuscript in preparation.
Blum M. and Goldwasser S. “An efficient Probabilistic Public Key Encryption Scheme which Hides all Partial Information” Presented in Crypto 1984
Broder A.Z. and Dolev D. “Flipping Coins in Many Pockets” FOCS 1984 pp 157–170
Cassels J.W.S. “Geometry of Numbers” Springer 1959
Goldwasser S. and Micali S. “Probabilistic Encryption” JSCC 28 270–299
Lenstra A.K., Lenstra H.W. and Lovasz L. “Factoring Polynomials with Integer Coefficients” Matematische Annalen 261 (1982) 513–534
Rivest R.L., Shamir A. and Adleman L. “A Method for Obtaining Digital Signatures and Public Key Cryptosystems” CACM 21–2 February 1978.
Schnorr C.P. “A Hierarchy of Polynomial Basis Reduction Algorithms”, manuscript
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hastad, J. (1986). N Using RSA with Low Exponent in a Public Key Network. In: Williams, H.C. (eds) Advances in Cryptology — CRYPTO ’85 Proceedings. CRYPTO 1985. Lecture Notes in Computer Science, vol 218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39799-X_29
Download citation
DOI: https://doi.org/10.1007/3-540-39799-X_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16463-0
Online ISBN: 978-3-540-39799-1
eBook Packages: Springer Book Archive