Wiener attack and weak keys of RSA cryptosystem
Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 71-80.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that the generalized Wiener attack on the RSA cryptosystem permits to find not only small, but also some large secret exponents d, and the fraction of exponents d, which are weak with respect to this attack is heuristically estimated as O(N1/2).
Mots-clés : RSA cryptosystem, continued fractions, small secret exponent, Weiner attack.
@article{DM_2023_35_3_a6,
     author = {A. E. Trishin},
     title = {Wiener attack and weak keys of {RSA} cryptosystem},
     journal = {Diskretnaya Matematika},
     pages = {71--80},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2023},
     language = {ru},
     url = {https://geodesic-test.mathdoc.fr/item/DM_2023_35_3_a6/}
}
TY  - JOUR
AU  - A. E. Trishin
TI  - Wiener attack and weak keys of RSA cryptosystem
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 71
EP  - 80
VL  - 35
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DM_2023_35_3_a6/
LA  - ru
ID  - DM_2023_35_3_a6
ER  - 
%0 Journal Article
%A A. E. Trishin
%T Wiener attack and weak keys of RSA cryptosystem
%J Diskretnaya Matematika
%D 2023
%P 71-80
%V 35
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DM_2023_35_3_a6/
%G ru
%F DM_2023_35_3_a6
A. E. Trishin. Wiener attack and weak keys of RSA cryptosystem. Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 71-80. https://geodesic-test.mathdoc.fr/item/DM_2023_35_3_a6/

[1] Bukhshtab A. A., Teoriya chisel, Prosveschenie, M., 1966, 384 pp.

[2] Vinogradov I. M., Osnovy teorii chisel, Nauka, M., 1972, 168 pp. | MR

[3] Blömer J., May A., “Low secret exponent RSA revisited”, CaLC 2001, Lect. Notes Comput. Sci., 2146, 2001, 4–19 | DOI | MR | Zbl

[4] Blömer J., May A., “A generalized Wiener attack on RSA”, PKC 2004, Lect. Notes Comput. Sci., 2947, 2004, 1–13 | DOI | MR | Zbl

[5] Boneh D., “Twenty years of attacks on the RSA cryptosystem”, Notices AMS, 46:2 (1999), 203–213 | MR | Zbl

[6] Boneh D., Durfee G., “Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$”, Eurocrypt 1999, Lect. Notes Comput. Sci., 1592, 1999, 1–11 | DOI | MR | Zbl

[7] Boneh D., Durfee G., “Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$”, IEEE Trans. Inf. Theory, 46:4 (2000), 1339–1349 | DOI | MR | Zbl

[8] Coppersmith D., “Small solutions to polynomial equations, and low exponent RSA vulnerabilities”, J. Cryptology, 10:4 (1997), 233–260 | DOI | MR | Zbl

[9] Dujella A., “Continued fractions and RSA with small secret exponent”, Tatra Mt. Math. Publ., 29 (2004), 101–112 | MR | Zbl

[10] Hardy G. H., Wright E. M., An Introduction to the Theory of Numbers, fourth edition, Oxford Univ. Press, 1960, 421 pp. | MR | Zbl

[11] Hinek M. J., Cryptanalysis of RSA and its variants, Chapman and Hall/CRC, New York, 2009, 272 pp. | MR

[12] Maitra S., Sarkar S., “Revisiting Wiener's attack — new weak keys in RSA”, ISC 2008, Lect. Notes Comput. Sci., 5222, 2008, 228–243 | DOI | Zbl

[13] Nitaj A., “Diophantine and lattice cryptanalysis of the RSA cryptosystem”, Artificial Intelligence, Evolutionary Computing and Metaheuristics, Stud. Comput. Intelligence, 427, Springer, 2013, 139–168 | Zbl

[14] Rivest R. L., Shamir A., Adleman L., “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

[15] Ruzai W. N., Nitaj A., Ariffin M. R. K., Mahad Z., Asbullah M. A., “Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis”, Comput. Stand. Interfaces, 80 (2022), 27 pp.

[16] Steinfeld R., Contini S., Wang H., Pieprzyk J., “Converse results to the Wiener attack on RSA”, PKC 2005, Lect. Notes Comput. Sci., 3386, 2005, 184–198 | DOI | MR | Zbl

[17] Verheul E. R., van Tilborg H. C. A., “Cryptanalysis of ‘less short’ RSA secret exponents”, Appl. Algebra Eng. Commun. Comput., 8:5 (1997), 425–435 | DOI | MR | Zbl

[18] de Weger B., “Cryptanalysis of RSA with small prime difference”, Appl. Algebra Eng. Commun. Comput., 13:1 (2002), 17–28 | DOI | MR | Zbl

[19] Wiener M., “Cryptanalysis of short RSA secret exponents”, IEEE Trans. Inf. Theory, 36:3 (1990), 553–558 | DOI | MR | Zbl