Geodesic
On a generalization of the Dujella method
Matematičeskie voprosy kriptografii, Tome 4 (2013) no. 3, pp. 7-19 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

As a rule, large secret exponents are used in practical realizations of RSA cryptosystem with modulus $N=pq$. Nevertheless, there are many theoretical results on the cryptanalysis of RSA system with a small secret exponent. A method suggested by Dujella recovers secret exponents $d$ with a run-time complexity $O(D\ln D)$ and space complexity $O(D)$. Weger have suggested an attack on the secret exponents $d\frac{N^{0.75}}{p-q}$. We describe a generalization of the Dujella method to attack the exponents $d$ with run-time complexity $O(D\ln D)$ and space complexity $O(D)$. 
@article{MVK_2013_4_3_a1,
     author = {K. D. Zhukov},
     title = {On a~generalization of the {Dujella} method},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {7--19},
     year = {2013},
     volume = {4},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2013_4_3_a1/}
}
TY  - JOUR
AU  - K. D. Zhukov
TI  - On a generalization of the Dujella method
JO  - Matematičeskie voprosy kriptografii
PY  - 2013
SP  - 7
EP  - 19
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2013_4_3_a1/
LA  - ru
ID  - MVK_2013_4_3_a1
ER  - 
%0 Journal Article
%A K. D. Zhukov
%T On a generalization of the Dujella method
%J Matematičeskie voprosy kriptografii
%D 2013
%P 7-19
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2013_4_3_a1/
%G ru
%F MVK_2013_4_3_a1
K. D. Zhukov. On a generalization of the Dujella method. Matematičeskie voprosy kriptografii, Tome 4 (2013) no. 3, pp. 7-19. http://geodesic.mathdoc.fr/item/MVK_2013_4_3_a1/

[1] Bukhshtab A. A., Teoriya chisel, Prosveschenie, M., 1966 | MR | Zbl

[2] Khinchin A. Ya., Tsepnye drobi, Fizmatgiz, L., 1961

[3] Hinek M. J., Cryptanalysis of RSA and Its Variants, CRC Press, 2009 | MR

[4] Pogorelov B. A., Sachkov V. N., Slovar kriptograficheskikh terminov, MTsNMO, M., 2006

[5] Boneh D., Durfee G., “Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$”, Advances in Cryptology, Proceedings of Eurocrypt' 99, LNCS, 1952, 1999, 1–11 | MR

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

[7] Verheul E. R., van Tilborg H. C. A., “Cryptanalysis of “less short” RSA secret exponents”, Appl. Algebra Eng. Comm. Computing, 8 (1997), 425–435 | DOI | MR | Zbl

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

[9] Dujella A., “A variant of Wiener's attack on RSA”, Computing, 85 (2009), 77–83 | DOI | MR | Zbl

[10] Weger B., “Cryptanalysis of RSA with small prime difference”, Appl. Algebra Eng. Comm. Computing, 13 (2002), 17–28 | DOI | MR | Zbl

[11] The GNU Multiple Precision Arithmetic Library, http://gmplib.org/

[12] The Multiple Precision Floating-Point Reliable Library, http://www.mpfr.org/