CryptoDB
Partial Key Exposure Attack on Short Secret Exponent CRTRSA
Authors: 


Download:  
Presentation:  Slides 
Conference:  ASIACRYPT 2021 
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 CRTRSA exponents. Using a Coppersmithtype 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 {\em Partial Key Exposure} attack on short secret exponent CRTRSA. 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 sideproduct of our result we obtain a heuristic deterministic polynomial time factorization algorithm on input $(N,e,d_p,d_q)$. 
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt202131362, title={Partial Key Exposure Attack on Short Secret Exponent CRTRSA}, publisher={SpringerVerlag}, doi={10.1007/9783030920623_4}, author={Alexander May and Julian Nowakowski and Santanu Sarkar}, year=2021 }