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 .