Cryptology ePrint Archive: Report 2017/835

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

Stephen D. Miller and Bhargav Narayanan and Ramarathnam Venkatesan

Abstract: We present a principled technique for reducing the matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. It relies on an analysis of the actual performance 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, it reduces lattice dimensions and consequently running times (sometimes by factors of two or more). We also argue that existing metrics (such as enabling condition bounds) are not as important as often thought for measuring the true performance of attacks based on Coppersmith's method. Finally, experiments are given to indicate that certain lattice reductive algorithms (such as Nguyen-Stehlé's L2) may be particularly well-suited for Coppersmith's method.

Category / Keywords: public-key cryptography / lattice techniques, RSA, cryptanalysis, factoring

Date: received 30 Aug 2017

Contact author: miller at math rutgers edu

Available format(s): PDF | BibTeX Citation

Note: 16 pages, 4 figures

Version: 20170831:184458 (All versions of this report)

Short URL: ia.cr/2017/835

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]