Paper 2012/675 Original: eprint.iacr.org/2012/675 ↗
Minkowski sum based lattice construction for multivariate simultaneous Coppersmith's technique and applications to RSA
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
- Preprint.
- History
- 2013-03-04: last updated
- 2012-11-30: published
- Short URL
- https://ia.cr/2012/675
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}