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

JOURNAL OF NUMBER THEORY

卷:222

Article

Miller, Stephen D.¹  Narayanan, Bhargav¹  Venkatesan, Ramarathnam² 

[1] Rutgers State Univ, Dept Math, 110 Frelinghuysen Rd, Piscataway, NJ 08854 USA

[2] Microsoft Corp, 1 Microsoft Way, Redmond, WA 98052 USA

关键词: Factoring;    Small exponent RSA;    Lattice attacks;    Lattice basis reduction;    Coppersmith's method;   

DOI  :  10.1016/j.jnt.2021.01.002

来源: Elsevier

【 摘 要 】

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. 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-Stehle's L2) may be particularly well-suited for Coppersmith's method. (C) 2021 Elsevier Inc. All rights reserved.

【 授权许可】

Free