Generalized cryptanalysis of RSA with small public exponent

作     者：Mengce ZHENG Honggang HU Zilong WANG 

作者机构：Key Laboratory of Electromagnetic Space Information Chinese Academy of Sciences (CAS) School of Information Science and Technology University of Science and Technology of China 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2016年第59卷第3期

页      面：97-106页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

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

主　　题：cryptanalysis RSA LLL algorithm Coppersmith’s techniques unravelled linearization 

摘      要：In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent e = NαN0.5. In 1999, Boneh and Durfee showed that when α≈ 1 and the private exponent d = Nβ N0.292, the system is insecure. Moreover, their attack is still effective for 0.5 α *** propose a generalized cryptanalytic method to attack the RSA cryptosystem with α≤0.5. For c = [（1-α）/α] and eγc≡ d（mod ec）, when γ, β satisfy γ 1+1/c-1/（2αc） and β αc +7/6- αγc-1/3（6α + 6αc + 1- 6αγc）1/2, we can perform cryptanalytic attacks based on the LLL algorithm. The basic idea is an application of Coppersmith s techniques and we further adapt the technique of unravelled linearization, which leads to an optimized *** advantage is that we achieve new attacks on RSA with α 0.5 and consequently, there exist weak keys in RSA for most α.