Welcome to the resource topic for 2022/271
Title:
Approximate Divisor Multiples – Factoring with Only a Third of the Secret CRT-Exponents
Authors: Alexander May, Julian Nowakowski, Santanu Sarkar
Abstract:We address Partial Key Exposure attacks on CRT-RSA 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 non-constant 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(p-1) and ed_q = 1 + \ell(q-1). On the technical side, we find the factorization of N in a novel two-step 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 lattice-based 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 Howgrave-Graham’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 Coppersmith-type 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.
ePrint: https://eprint.iacr.org/2022/271
Talk: https://www.youtube.com/watch?v=4USR_wlFpg8
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/94/slides.pdf
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 .