IACR News item: 30 November 2012
Yoshinori Aono
ePrint Reportfor 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
(i) a new RSA cryptanalysis for multiple short secret exponents,
(ii) its partial key exposure situation,
and (iii) investigating the hardness of finding a certain amount of LSBs of the RSA secret exponent.
More precisely,
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 $N^{(3\\ell-1)/(4\\ell+4)}$ by Sarkar and Maitra \\cite{SM10a,SM10b}.
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 $/n$ of the secret exponent and its exposed LSBs,
respectively.
Particularly, letting $\\beta=1$, which means that the secret exponent is full-sized,
the necessary amount of exposed bits is $[5/2 - 2(3\\ell -1)/(3\\ell +1)]n$, which is less than $n$ for $\\ell \\ge 3$.
Suppose we have an algorithm that recovers the above amount of $d$ from $e$ and $N$ satisfying $e\\approx N$.
We showed that $N$ can be factored
in polynomial time in $\\log N$ under a heuristic assumption that the Coppersmith technique works.
When $\\ell$ becomes large, the necessary amount becomes $0.5 n$ bits.
Hence, we conclude that recovering the lower half of LSBs of $d$ is polynomial time equivalent to the factoring
under the heuristic assumption.
From the last result,
we propose {\\it a half-amount conjecture}
that roughly, factoring RSA modulus is polynomial-time equivalent to
any continued bits of secret information such as $p,q,d,p+q$ and $p-q$
(or $d_p$ and $d_q$ for RSA-CRT).
It is supported from several results, e.g.,
Coppersmith \\cite{Co96b} shows that recovering the upper half of $p$ is equivalent to factoring.
Additional news items may be found on the IACR news page.