Paper 2017/835

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

Stephen D. Miller, Bhargav Narayanan, and Ramarathnam Venkatesan

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é's L2) may be particularly well-suited for Coppersmith's method.

Note: 21 pages, 5 figures

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
lattice techniquesRSAcryptanalysisfactoring
Contact author(s)
miller @ math rutgers edu
History
2020-12-16: last of 3 revisions
2017-08-31: received
See all versions
Short URL
https://ia.cr/2017/835
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/835,
      author = {Stephen D.  Miller and Bhargav Narayanan and Ramarathnam Venkatesan},
      title = {Coppersmith's lattices and ``focus groups'': an   attack on small-exponent RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2017/835},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/835}},
      url = {https://eprint.iacr.org/2017/835}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.