Partial Key Exposure Attack on Short Secret Exponent CRT-RSA

Let (N, e) be an RSA public key, where \(N=pq\) is the product of equal bitsize primes p, q. Let \(d_p, d_q\) be the corresponding secret CRT-RSA exponents.Using a Coppersmith-type attack, Takayasu, Lu and Peng (TLP) recently showed that one obtains the factorization of N in polynomial time, provided that \(d_p, d_q \le N^{0.122}\). Building on the TLP attack, we show the first Partial Key Exposure attack on short secret exponent CRT-RSA. Namely, let \(N^{0.122} \le d_p, d_q \le N^{0.5}\). Then we show that a constant known fraction of the least significant bits (LSBs) of both \(d_p, d_q\) suffices to factor N in polynomial time.Naturally, the larger \(d_p,d_q\), the more LSBs are required. E.g. if \(d_p, d_q\) are of size \(N^{0.13}\), then we have to know roughly a \(\frac{1}{5}\)-fraction of their LSBs, whereas for \(d_p, d_q\) of size \(N^{0.2}\) we require already knowledge of a \(\frac{2}{3}\)-LSB fraction. Eventually, if \(d_p, d_q\) are of full size \(N^{0.5}\), we have to know all of their bits. Notice that as a side-product of our result we obtain a heuristic deterministic polynomial time factorization algorithm on input \((N,e,d_p,d_q)\).