Paper 2021/972

Partial Key Exposure Attack on Short Secret Exponent CRT-RSA

Alexander May, Julian Nowakowski, and Santanu Sarkar

Abstract

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 $$, the more LSBs are required. E.g. if $$ are of size $$, then we have to know roughly a $$-fraction of their LSBs, whereas for $$ of size $$ we require already knowledge of a $$-LSB fraction. Eventually, if $$ are of full size $$, 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 $$.