Cryptanalysis of an RSA variant with moduli N = p r q l
Yao Lu, Liqiang Peng, Santanu Sarkar · Journal of Mathematical Cryptology · 2017
Abstract In this paper we study an RSA variant with moduli of the form N = p r q l {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 = p r q l {N=p^{r}q^{l}} . In the first proposal, the encryption exponent e and the decryption exponent d satisfy e d ≡ 1 mod p r - 1 q l - 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 ≡ 1 mod ( p - 1 ) ( q - 1 ) ed\equiv 1\bmod(p-1)(q-1) . We prove that for the first case if d < N 1 - ( 3 r + l ) ( r + l )