Advertisement

A New Related Message Attack on RSA

  • Oded Yacobi
  • Yacov Yacobi
Chapter
  • 711 Downloads
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)

Abstract

Coppersmith, Franklin, Patarin, and Reiter show that given two RSA cryptograms x e mod N and (ax+b) e mod N for known constants a,b ∈ ℤ N , one can usually compute x in O(elog 2 e) ℤ N -operations (there are O(e 2) messages for which the method fails).

We show that given e cryptograms c i ≡ (a i x+b i ) e mod N, i=0,1,...e–1, for any known constants a i ,b i  ∈ ℤ N , one can deterministically compute x in O(e) ℤ N -operations that depend on the cryptograms, after a pre-processing that depends only on the constants. The complexity of the pre-processing is O(elog 2 e) ℤ N -operations, and can be amortized over many instances. We also consider a special case where the overall cost of the attack is O(e) ℤ N -operations. Our tools are borrowed from numerical-analysis and adapted to handle formal polynomials over finite-rings. To the best of our knowledge their use in cryptanalysis is novel.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Hopcroft, A., Ullman: The Design and Analysis of Computer Algorithms. Addison Wesley, Reading (1974) ISBN 0-201-00029-6Google Scholar
  2. 2.
    Boneh, D.: Twenty Years of Attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46(2), 203–213 (1999)zbMATHMathSciNetGoogle Scholar
  3. 3.
    Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)CrossRefGoogle Scholar
  4. 4.
    Coppersmith, D., Franklin, M., Patarin, J., Reiter, M.: Low-Exponent RSA with related Messages. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 1–9. Springer, Heidelberg (1996)Google Scholar
  5. 5.
    Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP Is Secure Under the RSA Assumption. J. Crypt. 17(2), 81–104 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Rivest, R., Shamir, A., Adleman, L.M.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM 21(2), 120–126 (1978)zbMATHMathSciNetGoogle Scholar
  7. 7.
    Volkov, E.A.: Numerical Methods, p. 48. Hemisphere Publishing Corporation, New York (1987)zbMATHGoogle Scholar
  8. 8.
    Whittaker, E.T., Robinson: The Calculus of Observations: A Treatise on Numerical Mathematics, 4th edn., pp. 20–24. Dover, New York (1967)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Oded Yacobi
    • 1
  • Yacov Yacobi
    • 2
  1. 1.Department of MathematicsUniversity of California San DiegoLa JollaUSA
  2. 2.Microsoft ResearchRedmondUSA

Personalised recommendations