engleski

Continued fractions and RSA with small secret exponent

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.

Continued fractions; Diophantine approximations; RSA cryptosystem; cryptanalysis

nije evidentirano