Continued fractions and RSA with small secret exponent

Original · EN

Extending the classical Legendre's result, we describe all solutions of the inequality |x - a/b| < c/b² in terms of convergents of continued fraction expansion of x. Namely, we show that a/b = (rpₘ₊₁ +- spₘ) / (rqₘ₊₁ +- sqₘ) 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.