[Turkmath:4243] Sabanci Mathematics Colloquium - Thursday 28 Nov - 10:40

[Michel Lavrauw]

You are cordially invited to the Sabanci Mathematics Colloquium.

Guest: Andrej Dujella
Title: Applications of Diophantine approximations algorithms in cryptanalysis of RSA
Room / Date / Time: FENS G055 / 28 Nov / 10:40-11:30

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.  

Bio: Andrej Dujella is professor at the University of Zagreb and Fellow of the Croatian Academy of Sciences and Arts. He received a PhD in mathematics from the University of Zagreb in 1996 and Doctor Honoris
Causa of University of Debrecen in 2017. His research interests include Diophantine equations, elliptic curves, polynomial root separation, and applications of Diophantine approximation to
cryptography.  


Kind regards,
Michel Lavrauw