Using LLL-Reduction for Solving RSA and Factorization Problems

DOI10.1007/978-3-642-02295-1_10zbMath1237.94078OpenAlexW10068438MaRDI QIDQ5188546

Alexander May

Publication date: 5 March 2010

Published in: The LLL Algorithm (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02295-1_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (23)

An application of Euclidean algorithm in cryptanalysis of RSA ⋮ Factoring multi-power RSA moduli with primes sharing least or most significant bits ⋮ Approximate divisor multiples -- factoring with only a third of the secret CRT-exponents ⋮ Remarks on the cryptanalysis of common prime RSA for IoT constrained low power devices ⋮ \textit{Caveat implementor!} Key recovery attacks on MEGA ⋮ Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials ⋮ Improving bounds on elliptic curve hidden number problem for ECDH key exchange ⋮ Fast practical lattice reduction through iterated compression ⋮ Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents ⋮ Factoring multi power RSA moduli with a class of secret exponents ⋮ Recovering a sum of two squares decomposition ⋮ A Tool Kit for Partial Key Exposure Attacks on RSA ⋮ A generalized attack on some variants of the RSA cryptosystem ⋮ Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound ⋮ Cryptanalysis of the RSA variant based on cubic Pell equation ⋮ Small CRT-Exponent RSA Revisited ⋮ Small CRT-exponent RSA revisited ⋮ Smallest Reduction Matrix of Binary Quadratic Forms ⋮ Partial Key Exposure Attacks on CRT-RSA: Better Cryptanalysis to Full Size Encryption Exponents ⋮ Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding ⋮ Cryptanalysis of elliptic curve hidden number problem from PKC 2017 ⋮ Partial Key Exposure Attacks on RSA with Multiple Exponent Pairs ⋮ Generalized cryptanalysis of small CRT-exponent RSA

Cites Work

• Breaking RSA may be as difficult as factoring
• The development of the number field sieve
• Factoring polynomials and the knapsack problem
• Deterministic polynomial-time equivalence of computing the RSA secret key and factoring
• Factoring integers with elliptic curves
• Factoring polynomials with rational coefficients
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Recent advances in RSA cryptography
• Cryptanalysis of RSA with small prime difference
• On the security of RSA with primes sharing least-significant bits
• Stronger security proofs for RSA and Rabin bits.
• Low-Exponent RSA with Related Messages
• Finding a Small Root of a Univariate Modular Equation
• Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
• Factorization of Square-Free Integers with High Bits Known
• Cryptanalysis of short RSA secret exponents
• Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
• A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N 0.073
• Efficient Factoring Based on Partial Information
• Solving Simultaneous Modular Equations of Low Degree
• Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation
• A method for obtaining digital signatures and public-key cryptosystems
• Breaking RSA may not be equivalent to factoring
• Cryptanalysis of RSA with Private Key d Less than N 0.292
• Cryptanalysis of RSA with private key d less than N/sup 0.292/
• Advances in Cryptology – CRYPTO 2004
• Floating-Point LLL Revisited
• A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
• Partial Key Exposure Attacks on RSA up to Full Size Exponents
• Advances in Cryptology - CRYPTO 2003
• Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables
• Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?
• On the Provable Security of an Efficient RSA-Based Pseudorandom Generator
• On the Equivalence of RSA and Factoring Regarding Generic Ring Algorithms
• A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
• Information Security and Privacy
• The security of all RSA and discrete log bits
• Deterministic Polynomial Time Equivalence Between Factoring and Key-Recovery Attack on Takagi’s RSA
• Finding smooth integers in short intervals using CRT decoding
• Topics in Cryptology – CT-RSA 2006
• Public Key Cryptography - PKC 2006
• Public Key Cryptography – PKC 2004
• Public Key Cryptography – PKC 2004
• On polynomial congruences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Using LLL-Reduction for Solving RSA and Factorization Problems