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

Yoshinori Aono

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: RSA Coppersmith technique lattice based attack lattice construciton simutaneous 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: CC BY

BibTeX

@misc{cryptoeprint:2012/675,
      author = {Yoshinori Aono},
      title = {Minkowski sum based lattice construction for multivariate simultaneous Coppersmith's technique and applications to {RSA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/675},
      year = {2012},
      url = {https://eprint.iacr.org/2012/675}
}