Continued fractions and RSA with small secret exponent

Year, pages: 2004, 101 - 112

Extending the classical Legendre's result, we describe all solutions of the inequality |alpha - a/b| < c/b² in terms of convergents of continued fraction expansion of alpha. Namely, we show that a/b = (rp_m+1 pm sp_m) / (rq_m+1 pm 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.

Dujella, A. 2004. Continued fractions and RSA with small secret exponent. In Tatra Mountains Mathematical Publications, vol. 29, no.3, pp. 101-112. 1210-3195.

Dujella, A. (2004). Continued fractions and RSA with small secret exponent. Tatra Mountains Mathematical Publications, 29(3), 101-112. 1210-3195.