You are looking at a specific version 20130304:030211 of this paper. See the latest version.

Paper 2012/675

Minkowski sum based lattice construction for multivariate simultaneous Coppersmith's technique and applications to RSA

Yoshinori Aono

Abstract

We investigate a lattice construction method for the Coppersmith technique for finding small solutions of a modular equation. We consider its variant for simultaneous equations and propose a method to construct a lattice by combining lattices for solving single equations. As applications, we consider a new RSA cryptanalyses. Our algorithm can factor an RSA modulus from $\ell \ge 2$ pairs of RSA public exponents with the common modulus corresponding to secret exponents smaller than $N^{(9\ell -5)/(12\ell + 4)}$, which improves on the previously best known result by Sarkar and Maitra. For partial key exposure situation, we also can factor the modulus if $\beta - \delta/2 + 1/4 < (3\ell-1)(3\ell + 1)$, where $\beta$ and $\delta$ are bit-lengths $/ \log N$ of the secret exponent and its exposed LSBs, respectively.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSACoppersmith techniquelattice based attacklattice construcitonsimutaneous equations
Contact author(s)
aono @ nict go jp
History
2013-03-04: last of 2 revisions
2012-11-30: received
See all versions
Short URL
https://ia.cr/2012/675
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.