An application of Euclidean algorithm in cryptanalysis of RSA

DOI10.4171/EM/411MaRDI QIDQ827545zbMATH OpenWikidataFDO

Authors Dimitros Poulakis

Publication date 13 January 2021

Published in Elemente der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/EM/411

zbMATH Keywords

extended Euclid algorithmRSA cryptosystemWiener attac

Mathematics Subject Classification ID

Cryptography (94A60)

Review text

Summary: In this paper, we have presented a new attack on the RSA cryptosystem based only on the extended Euclid algorithm. It computes the factorization of \(n\) in deterministic \(O((\log n)^2)\) bit operations, in the case where the public exponente has the same order of magnitude as \(n\) and one of the integer \(sk=(ed-1)/ \phi (n)\) and \(e-k\) has at most one-quarter as many bits as \(e\). Comparing with Wiener's classical attack and its presentation as a bivariate linear equation problem, our attack is quite simpler, since it avoids the use of continuous fractions and lattices. Its efficiency is comparable to that of Wiener's attack,and its time complexity the same as that of the solution of the corresponding bivariate linear equation problem but better than that of the classical Wiener attac.

Recommendations

• On Wiener's attack on RSA cryptosystem
• A variant of Wiener's attack on RSA
• Another Generalization of Wiener’s Attack on RSA
• New Attacks on the RSA Cryptosystem
• Cryptanalysis of RSA with Private Key d Less than N 0.292

Cites work

• A computational introduction to number theory and algebra
• A variant of Wiener's attack on RSA
• Another Generalization of Wiener’s Attack on RSA
• Application of ECM to a class of RSA keys
• Continued fractions and RSA with small secret exponent
• Cryptanalysis of `less short' RSA secret exponents
• CRYPTANALYSIS OF RSA WITH CONSTRAINED KEYS
• Cryptanalysis of RSA with private key d less than N/sup 0.292/
• Cryptanalysis of RSA with small prime difference
• Estimating the Prime-Factors of an RSA Modulus and an Extension of the Wiener Attack
• scientific article; zbMATH DE number 1852133 (Why is no real title available?)
• Large decryption exponents in RSA
• Public Key Cryptography – PKC 2004
• Using LLL-reduction for solving RSA and factorization problems

Cited in

(4)

• scientific article; zbMATH DE number 5635243 (Why is no real title available?)
• On Wiener's attack on RSA cryptosystem
• An effective algorithm to private-key in the RSA cryptosystem
• A complete and explicit security reduction algorithm for RSA-based cryptosystems

This page was built for publication: An application of Euclidean algorithm in cryptanalysis of RSA

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