Advertisement
Published in:
2015 | OriginalPaper | Chapter
Cryptanalysis of Variants of RSA with Multiple Small Secret Exponents
Authors : Liqiang Peng, Lei Hu, Yao Lu, Santanu Sarkar, Jun Xu, Zhangjie Huang
Published in: Progress in Cryptology -- INDOCRYPT 2015
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we analyze the security of two variants of the RSA public key cryptosystem where multiple encryption and decryption exponents are used with a common modulus. For the most well known variant, CRT-RSA, assume that n encryption and decryption exponents \((e_l,d_{p_l},d_{q_l})\), where \(l=1,\cdots ,n\), are used with a common CRT-RSA modulus N. By utilizing a Minkowski sum based lattice construction and combining several modular equations which share a common variable, we prove that one can factor N when \(d_{p_l},d_{q_l}<N^{\frac{2n-3}{8n+2}}\) for all \(l=1,\cdots ,n\). We further improve this bound to \(d_{p_l}(\mathrm {or}\,d_{q_l})<N^{\frac{9n-14}{24n+8}}\) for all \(l=1,\cdots ,n\). Moreover, our experiments do better than previous works by Jochemsz-May (Crypto 2007) and Herrmann-May (PKC 2010) when multiple exponents are used. For Takagi’s variant of RSA, assume that n key pairs \((e_l,d_l)\) for \(l=1,\cdots ,n\) are available for a common modulus \(N=p^rq\) where \(r\ge 2\). By solving several simultaneous modular univariate linear equations, we show that when \(d_l<N^{(\frac{r-1}{r+1})^{\frac{n+1}{n}}}\), for all \(l=1,\cdots ,n\), one can factor the common modulus N.