## Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA

*Mathias Herrmann, Alexander MayTo appear In Practice and Theory in Public Key Cryptography (PKC 2010), Lecture Notes in Computer Science, Springer-Verlag, 2010.*

Download - PDF

Abstract:

We present an elementary method to construct optimized lattices that are used for finding small roots of polynomial equations. Former methods first construct some large lattice in a generic way from a polynomial f and then optimize via finding suitable smaller dimensional sublattices. In contrast, our method focuses on optimizing f first which then directly leads to an optimized small dimensional lattice.

Using our method, we construct the first elementary proof of the Boneh-Durfee attack for small RSA secret exponents with d ≤ N^0.292. Moreover, we identify a sublattice structure behind the Jochemsz-May attack for small CRT-RSA exponents dp, dq ≤ N^0.073. Unfortunately, in contrast to the Boneh-Durfee attack, for the Jochemsz-May attack the sublattice does not help to improve the bound asymptotically. Instead, we are able to attack much larger values of dp, dq in practice by LLL reducing smaller dimensional lattices.

BibTex:

@INPROCEEDINGS{DBLP:conf/pkc/HerrmannM10,

author = {Herrmann, Mathias and May, Alexander},

title = {Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA},

booktitle = {Public Key Cryptography},

year = {2010},

pages = {53--69},

crossref = {DBLP:conf/pkc/2010},

}

crossreferenced publications:

@proceedings{DBLP:conf/pkc/2010,

editor = {Phong Q. Nguyen and

David Pointcheval},

title = {Public Key Cryptography - PKC 2010, 13th International Conference

on Practice and Theory in Public Key Cryptography, Paris,

France, May 26-28, 2010. Proceedings},

booktitle = {Public Key Cryptography},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {6056},

year = {2010},

}