Far Eastern Mathematical Journal

To content of the issue

On Wiener's attack on RSA cryptosystem

Illarionov A.A., Chepurko S.A.

2018, issue 2, P. 189-194

Abstract

We propose a modification of Wiener’s attack on the RSA cryptosystem. The algorithm uses only continuous fractions. It's complexity is not greater than $O(d^2 m^{-1/2} \ln m)$, where $m$ is the modulus, $d$ is the secret exponent of RSA.

Keywords: RSA, Wiener’s attack, cryptanalysis of RSA

Download the article (PDF-file)

References

[1] R. L. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and publi- key cryptosystems”, Communications of the ACM, 21, (1978), 120–126. [2] M., J. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Trans. Inform. Theory, 36, (1990), 553–558. [3] E. R. Verheul, H. C. A. van Tilborg, “Cryptanalysis of “less short” RSA secret exponents”, Appl. Algebra Engrg. Comm. Computing, 8, (1997), 425–435. [4] Dujella, “Continued fractions and RSA with small secret exponent”, Tatra Mt. Math. Publ., 29, (2004), 101–112. [5] Dujella, “A variant of Wiener’s attack on RSA”, Computing, 85, (2009), 77–83. [6] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than 0.292”, in Advances in Cryptology-EUROCRYPT ’99, Lecture Notes in Computer Science, v. 1592, Springer, Berlin, Germany, 1999, 1–11. [7] J. Blomer, A. May, “Low secret exponent RSA revisited”, Cryptography and Lattice - Proceedings of CaLC 2001, Lecture Notes in Comput. Sci., v. 2146, 2001, 4–19.

To content of the issue