Approximate Divisor Multiples -- Factoring with Only a Third of the Secret CRT-Exponents
Alexander May, Julian Nowakowski, and Santanu Sarkar
Abstract
We address Partial Key Exposure attacks on CRT-RSA on secret exponents with small public exponent . For constant it is known that the knowledge of half of the bits of one of suffices to factor the RSA modulus by Coppersmith's famous {\em factoring with a hint} result. We extend this setting to non-constant . Somewhat surprisingly, our attack shows that RSA with of size is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both suffices to factor in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB).
Let and . On the technical side, we find the factorization of in a novel two-step approach. In a first step we recover and 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 by computing the root of a univariate polynomial modulo for our known . 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 of an unknown divisor of . 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 .
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.
@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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.