Continued fractions and RSA with small secret exponent

zbMATH1114.11008MaRDI QIDQ3369002FDOQ3369002

Authors Andrej Dujella

Publication date 22 March 2007

Full work available at URL https://arxiv.org/abs/cs/0402052

zbMATH Keywords

continued fractionscryptanalysisDiophantine approximationsRSA cryptosystem

Mathematics Subject Classification ID

Cryptography (94A60) Continued fractions (11A55)

Abstract: Extending the classical Legendre's result, we describe all solutions of the inequality |x - a/b| < c/b^2 in terms of convergents of continued fraction expansion of x. 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.

Recommendations

• Cryptanalysis of `less short' RSA secret exponents
• Cryptanalysis of RSA with Private Key d Less than N 0.292
• A variant of Wiener's attack on RSA
• Another Generalization of Wiener’s Attack on RSA
• Public Key Cryptography - PKC 2005

Cited in

(23)

• On the sum of two divisors of \((n^2+1)/2\)
• Pellian equations of special type
• On the Diophantine equation \(X^2 - (1 + a^2)Y^4 = - 2a\)
• An application of Euclidean algorithm in cryptanalysis of RSA
• Establishing the minimal index in a parametric family of bicyclic biquadratic fields
• On the Diophantine equation \(2^x=x^2+y^2-2\)
• Solutions of a class of quartic Thue inequalities
• Solutions of a class of quartic Thue inequalities
• A variant of Wiener's attack on RSA
• On a generalization of the Dujella method
• Forty years of attacks on the RSA cryptosystem: a brief survey
• Improved Partial Key Exposure Attacks on RSA by Guessing a Few Bits of One of the Prime Factors
• On the distribution of nonprimitive lattice points in the plane
• A variation of a congruence of Subbarao for \(n=2^\alpha 5^\beta\)
• Revisiting Wiener’s Attack – New Weak Keys in RSA
• A cryptanalytic attack on the LUC cryptosystem using continued fractions
• Compact representation of quadratic integers and integer points on some elliptic curves
• On fundamental units of real quadratic fields of class number 1
• Improving small private exponent attack on the Murru-Saettone cryptosystem
• A Pellian equation with primes and applications to \(D(-1)\)-quadruples
• On Wiener's attack on RSA cryptosystem
• Approximate common divisor problem and continued fractions
• Topics in Cryptology – CT-RSA 2006

This page was built for publication: Continued fractions and RSA with small secret exponent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3369002)