Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA

DOI10.1016/J.JNT.2021.01.002MaRDI QIDQ1998906zbMATH OpenOpenAlexFDO

Authors Stephen D. Miller, Ramarathnam Venkatesan, Bhargav P. Narayanan

Publication date 9 March 2021

Published in Journal of Number Theory (Search for Journal in Brave)

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

zbMATH Keywords

Coppersmith's methodfactoringlattice attackslattice basis reductionsmall exponent RSA

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Cryptography (94A60)

Abstract: We present a principled technique for reducing the lattice and matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. Motivated by ideas from machine learning, it relies on extrapolating patterns from the actual behavior of Coppersmith's attack for smaller parameter sizes, which can be thought of as "focus group" testing. When applied to the small-exponent RSA problem, our technique reduces lattice dimensions and consequently running times, and hence can be applied to a wider range of exponents. Moreover, in many difficult examples our attack is not only faster but also more successful in recovering the RSA secret key. We include a discussion of subtleties concerning whether or not existing metrics (such as enabling condition bounds) are decisive in predicting the true efficacy of attacks based on Coppersmith's method. Finally, indications are given which suggest certain lattice basis reduction algorithms (such as Nguyen-Stehl'e's L2) may be particularly well-suited for Coppersmith's method.

Recommendations

• scientific article; zbMATH DE number 1852133
• A Partial Key Exposure Attack on RSA Using a 2-Dimensional Lattice
• scientific article; zbMATH DE number 1341877
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Small CRT-Exponent RSA Revisited

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
• A unified framework for small secret exponent attack on RSA
• A variant of Wiener's attack on RSA
• An LLL algorithm with quadratic complexity
• Approximate common divisors via lattices
• Cryptanalysis of RSA with private key d less than N/sup 0.292/
• Cryptanalysis of short RSA secret exponents
• Factoring polynomials with rational coefficients
• Factoring RSA keys from certified smart cards: Coppersmith in the wild
• Finding a small root of a bivariate integer equation; factoring with high bits known
• scientific article; zbMATH DE number 1182510 (Why is no real title available?)
• scientific article; zbMATH DE number 1852133 (Why is no real title available?)
• Mathematics of public key cryptography.
• Maximizing small root bounds by linearization and applications to small secret exponent RSA
• Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables

Cited in

(11)

• On the optimality of lattices for the Coppersmith technique
• On the optimality of lattices for the Coppersmith technique
• Maximizing small root bounds by linearization and applications to small secret exponent RSA
• scientific article; zbMATH DE number 1341877 (Why is no real title available?)
• Lattice Attacks on RSA-Encrypted IP and TCP
• scientific article; zbMATH DE number 1852133 (Why is no real title available?)
• Forty years of attacks on the RSA cryptosystem: a brief survey
• Lattice-based integer factorisation: an introduction to Coppersmith's method
• Lattice-based cryptanalysis of RSA cryptosystem
• Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables
• Practical attacks on small private exponent RSA: new records and new insights

Describes a project that uses

Uses Software

• NTL
• fpLLL

This page was built for publication: Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA

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