Paper 2022/271
Approximate Divisor Multiples  Factoring with Only a Third of the Secret CRTExponents
Alexander May, Julian Nowakowski, and Santanu Sarkar
Abstract
We address Partial Key Exposure attacks on CRTRSA on secret exponents $d_p, d_q$ with small public exponent $e$. For constant $e$ it is known that the knowledge of half of the bits of one of $d_p, d_q$ suffices to factor the RSA modulus $N$ by Coppersmith's famous {\em factoring with a hint} result. We extend this setting to nonconstant $e$. Somewhat surprisingly, our attack shows that RSA with $e$ of size $N^{\frac 1 {12}}$ is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both $d_p, d_q$ suffices to factor $N$ in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB). Let $ed_p = 1 + k(p1)$ and $ed_q = 1 + \ell(q1)$. On the technical side, we find the factorization of $N$ in a novel twostep approach. In a first step we recover $k$ and $\ell$ in polynomial time, in the MSB case completely elementary and in the LSB case using Coppersmith's latticebased method. We then obtain the prime factorization of $N$ by computing the root of a univariate polynomial modulo $kp$ for our known $k$. This can be seen as an extension of HowgraveGraham's {\em approximate divisor} algorithm to the case of {\em approximate divisor multiples} for some known multiple $k$ of an unknown divisor $p$ of $N$. The point of {\em approximate divisor multiples} is that the unknown that is recoverable in polynomial time grows linearly with the size of the multiple $k$. Our resulting Partial Key Exposure attack with known MSBs is completely rigorous, whereas in the LSB case we rely on a standard Coppersmithtype heuristic. We experimentally verify our heuristic, thereby showing that in practice we reach our asymptotic bounds already using small lattice dimensions. Thus, our attack is highly efficient.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in EUROCRYPT 2022
 Keywords
 Coppersmith's methodCRTRSAPartial Key Exposure.
 Contact author(s)
 julian nowakowski @ rub de
 History
 20220302: received
 Short URL
 https://ia.cr/2022/271
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/271, author = {Alexander May and Julian Nowakowski and Santanu Sarkar}, title = {Approximate Divisor Multiples  Factoring with Only a Third of the Secret {CRT}Exponents}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/271}, year = {2022}, url = {https://eprint.iacr.org/2022/271} }