Paper 2021/972
Partial Key Exposure Attack on Short Secret Exponent CRTRSA
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 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 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)$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2021
 Keywords
 CRTRSACoppersmith’s methodPartial Key Exposure
 Contact author(s)
 julian nowakowski @ rub de
 History
 20211115: revised
 20210722: received
 See all versions
 Short URL
 https://ia.cr/2021/972
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/972, author = {Alexander May and Julian Nowakowski and Santanu Sarkar}, title = {Partial Key Exposure Attack on Short Secret Exponent {CRT}{RSA}}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/972}, year = {2021}, url = {https://eprint.iacr.org/2021/972} }