Cryptology ePrint Archive: Report 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.

Category / Keywords: RSA, Coppersmith technique, lattice based attack, lattice construciton, simutaneous equations

Date: received 28 Nov 2012, last revised 3 Mar 2013

Contact author: aono at nict go jp

Available format(s): PDF | BibTeX Citation

Version: 20130304:030211 (All versions of this report)

Short URL: ia.cr/2012/675

Discussion forum: Show discussion | Start new discussion