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 dp, dq 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 dp, dq≤ N0.122. Building on the TLP attack, we show the first Partial Key Exposure attack on short secret exponent CRT-RSA. Namely, let N0.122≤ dp, dq≤ N0.5. Then we show that a constant known fraction of the least significant bits (LSBs) of both dp, dq suffices to factor N in polynomial time. Naturally, the larger dp, dq, the more LSBs are required. E.g. if dp, dq are of size N0.13, then we have to know roughly a 15 -fraction of their LSBs, whereas for dp, dq of size N0.2 we require already knowledge of a 23 -LSB fraction. Eventually, if dp, dq are of full size N0.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, dp, dq).