Applications of Diophantine approximations algorithms in cryptanalysis of RSA

Előadó:
Prof. Andrej Dujella


Időpont:
2017. november 24. (péntek) 13:00

Helyszín:
Debreceni Egyetem Informatikai Kar
(4028 Debrecen, Kassai út 26.)

Szervezők:
Debreceni Egyetem Informatikai Kar
MTA DAB Informatikai Munkabizottság

Program:

Prof. Andrej Dujella előadása: Applications of Diophantine approximations algorithms in cryptanalysis of RSA

Abstract:
To speed up the RSA decryption one may try to use small secret decryption exponent d. The choice of a small d is especially interesting when there is a large difference in computing power between two communicating devices. However, in 1990, Wiener showed that if d < n^(1/4), where n = pq is the modulus of the cryptosystem, then there exist a polynomial time attack on the RSA. He showed that d is the denominator of some convergent p_m/q_m of the continued fraction expansion of e/n, and therefore d can be computed efficiently from the public key (n,e). In this talk, we will discuss similar attacks on RSA and its variants  which use results and algorithms from Diophantine approximations, such as Worley's extension of the classical Legendre's theorem on continued fractions and LLL-algorithm for computing short vectors in lattices.