Welcome to the resource topic for 2012/675
Title:
Minkowski sum based lattice construction for multivariate simultaneous Coppersmith’s technique and applications to RSA
Authors: 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.
ePrint: https://eprint.iacr.org/2012/675
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .