A New Related Message Attack on RSA
- 711 Downloads
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.
Unable to display preview. Download preview PDF.
- 1.Hopcroft, A., Ullman: The Design and Analysis of Computer Algorithms. Addison Wesley, Reading (1974) ISBN 0-201-00029-6Google Scholar
- 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
- 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