Paper 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.

Note: 16 pages, 4 figures