Дальневосточный математический журнал

К содержанию выпуска


Об атаке Винера на шифр RSA


А.А. Илларионов, C.А. Чепурко

2018, выпуск 2, С. 189-194


Аннотация
Предлагается элементарная модификация атаки Винера на шифр RSA. Алгоритм использует только аппарат непрерывных дробей. Его сложность равна $O(d^2 m^{-1/2} \ln m)$ (при условии $m^{1/4}\ll d \ll m^{1/2}$, $e\le m$), где $m$, $d$ и $e$ – модуль, секретная и открытая экспоненты

Ключевые слова: RSA, атака Винера, криптоанализ RSA

Полный текст статьи (файл PDF)

Библиографический список

[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.

К содержанию выпуска