# Partial Key Exposure Attack on Short Secret Exponent CRT-RSA, by Alexander May and Julian Nowakowski and Santanu Sarkar

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 leq 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} leq d_p, d_q leq 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)\$.