Welcome to the resource topic for 2021/972
Title:
Partial Key Exposure Attack on Short Secret Exponent CRT-RSA
Authors: Alexander May, Julian Nowakowski, 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 \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).
ePrint: https://eprint.iacr.org/2021/972
Talk: https://www.youtube.com/watch?v=ibdS6JXSmTg
Slides: https://iacr.org/submit/files/slides/2021/asiacrypt/asiacrypt2021/29/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .