International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 30 November 2012

Yoshinori Aono
ePrint Report ePrint Report
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

(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.

Expand

Additional news items may be found on the IACR news page.