Cryptanalysis of an RSA variant with moduli N=prql

Abstract

In this paper we study an RSA variant with moduli of the form N=pr⁢ql{N=p^{r}q^{l}} (r>l≥2{r>l\geq 2}). This variant was mentioned by Boneh, Durfee and Howgrave-Graham [2]. Later Lim, Kim, Yie and Lee [11] showed that this variant is much faster than the standard RSA moduli in the step of decryption procedure. There are two proposals of RSA variants when N=pr⁢ql{N=p^{r}q^{l}}. In the first proposal, the encryption exponent e and the decryption exponent d satisfy e⁢d≡1modpr-1⁢ql-1⁢(p-1)⁢(q-1)ed\equiv 1\bmod p^{r-1}q^{l-1}(p-1)(q-1), whereas in the second proposal e⁢d≡1mod(p-1)⁢(q-1)ed\equiv 1\bmod(p-1)(q-1). We prove that for the first case if d<N1-(3⁢r+l)⁢(r+l)-2{d<N^{1-({3r+l}){(r+l)^{-2}}}}, one can factor N in polynomial time. We also show that polynomial time factorization is possible if d<N(7-2⁢7)/(3⁢(r+l)){d<N^{({7-2\sqrt{7}})/{(3(r+l))}}} for the second case. Finally, we study the case when few bits of one prime are known to the attacker for this variant of RSA. We show that given min⁡(lr+l,2⁢(r-l)r+l)⁢log2⁡p{\min(\frac{l}{r+l},\frac{2(r-l)}{r+l})\log_{2}p} least significant bits of one prime, one can factor N in polynomial time.

Keywords

• coppersmith’s method
• lattices
• rsa
• rsa variants
• 94a60