Naslov
Continued fractions and RSA with small secret exponent

Autori
Dujella, Andrej

Izvornik
Tatra mountains mathematical publications (1210-3195) 29 (2004); 101-112

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Continued fractions; Diophantine approximations; RSA cryptosystem; cryptanalysis

Sažetak
Extending the classical Legendre's result, we describe all solutions of the inequality |alpha - a/b| < c/b^2 in terms of convergents of continued fraction expansion of alpha. Namely, we show that a/b = (rp_{;m+1}; +- sp_m) / (rq_{;m+1}; +- sq_m) for some nonnegative integers m, r, s such that rs < 2c. As an application of this result, we describe a modification of Verheul and van Tilborg variant of Wiener's attack on RSA cryptosystem with small secret exponent.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA