Continued fractions and RSA with small secret exponent

zbMATH Open1114.11008arXivcs/0402052MaRDI QIDQ3369002FDOQ3369002

Andrej Dujella

Publication date: 22 March 2007

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.

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

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

zbMATH Keywords

continued fractionscryptanalysisDiophantine approximationsRSA cryptosystem

Mathematics Subject Classification ID

Cryptography (94A60) Continued fractions (11A55)

Cited In (23)

• Forty years of attacks on the RSA cryptosystem: A brief survey
• A variation of a congruence of Subbarao for \(n=2^\alpha 5^\beta\)
• An application of Euclidean algorithm in cryptanalysis of RSA
• Solutions of a class of quartic Thue inequalities
• Solutions of a class of quartic Thue inequalities
• On the sum of two divisors of \((n^2+1)/2\)
• Topics in Cryptology – CT-RSA 2006
• Об обобщении метода Дюжелла
• A variant of Wiener's attack on RSA
• Compact representation of quadratic integers and integer points on some elliptic curves
• On fundamental units of real quadratic fields of class number 1
• Title not available (Why is that?)
• Improved Partial Key Exposure Attacks on RSA by Guessing a Few Bits of One of the Prime Factors
• On the Diophantine equation \(X^2 - (1 + a^2)Y^4 = - 2a\)
• On the distribution of nonprimitive lattice points in the plane
• Improving small private exponent attack on the Murru-Saettone cryptosystem
• Pellian equations of special type
• Задача о приближенном общем делителе и цепные дроби
• Establishing the minimal index in a parametric family of bicyclic biquadratic fields
• A cryptanalytic attack on the LUC cryptosystem using continued fractions
• A Pellian equation with primes and applications to \(D(-1)\)-quadruples
• Revisiting Wiener’s Attack – New Weak Keys in RSA
• On the Diophantine equation \(2^x=x^2+y^2-2\)

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)