Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Cryptanalysis of Variants of RSA with Multiple Small Secret Exponents
verfasst von : Liqiang Peng, Lei Hu, Yao Lu, Santanu Sarkar, Jun Xu, Zhangjie Huang
Erschienen in: Progress in Cryptology -- INDOCRYPT 2015
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.