Cryptanalysis of an RSA variant with moduli N = p r q l

Journal of mathematical cryptology

article

Yao Lu¹  Liqiang Peng²  Santanu Sarkar³ 

[1] The University of Tokyo;Institute of Information Engineering, Chinese Academy of Sciences;Indian Institute of Technology

关键词: Coppersmith’s method;    lattices;    RSA;    RSA variants;   

DOI  :  10.1515/jmc-2016-0025

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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

【 授权许可】

CC BY|CC BY-NC-ND