Cryptanalysis of Prime Power RSA with two private exponents  

作　　者：ZHENG MengCe HU HongGang 

机构地区：[1]Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences [2]School of Information Science and Technology, University of Science and Technology of China

出　　处：《Science China(Information Sciences)》2015年第11期55-62,共8页中国科学（信息科学）（英文版）

基　　金：supported partially by National Natural Science Foundation of China(Grant Nos.61271271,61522210);100 Talents Program of Chinese Academy of Sciences,and Fundamental Research Funds for the Central Universities in China(Grant No.WK2101020005)

摘　　要：In this paper, we consider a variant of RSA schemes called Prime Power RSA with modulus N= prq for r ≥2, where p, q are of the same bit-size. May showed that when private exponent d〈N^r/（r＋1）^2 or d〈N^（r-1/r＋1）^2,N can be factored in polynomial time in PKC 2004. Later in 2014, Sarkar improved the bound for r ≤5. We propose a new cryptanalytic method to attack this RSA variant when given two pairs of public and private exponents, namely （e1, d1） and （e2, d2） with the same modulus N. Suppose that we know d1 〈 N^δ1 and d2 〈 N^δ2. Our results show that when δ1δ2〈（r-1/r＋1）^3,Prime Power RSA is insecure.In this paper, we consider a variant of RSA schemes called Prime Power RSA with modulus N= prq for r ≥2, where p, q are of the same bit-size. May showed that when private exponent d〈N^r/（r＋1）^2 or d〈N^（r-1/r＋1）^2,N can be factored in polynomial time in PKC 2004. Later in 2014, Sarkar improved the bound for r ≤5. We propose a new cryptanalytic method to attack this RSA variant when given two pairs of public and private exponents, namely （e1, d1） and （e2, d2） with the same modulus N. Suppose that we know d1 〈 N^δ1 and d2 〈 N^δ2. Our results show that when δ1δ2〈（r-1/r＋1）^3,Prime Power RSA is insecure.

关 键 词：CRYPTANALYSIS Prime Power RSA two private exponents LLL algorithm Coppersmith＇s techniques 

分 类 号：TN918.4[电子电信—通信与信息系统]