Remarks on the bounds for cryptanalysis of low private key RSA  

作　　者：Haijian Zhou Ping Luo Daoshun Wang Yiqi Dai 

机构地区：[1]Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China [2]School of Software, Tsinghua University, Beijing 100084, China

出　　处：《Progress in Natural Science:Materials International》2009年第10期1327-1331,共5页自然科学进展·国际材料（英文版）

基　　金：supported by the National Key Basic Research and Development (973) of China (Grant No2003CB314805);863 Project of China (Grant No 2008AA01Z419);the National Natural Sciences Foundation of China (Grant No 60873249 and 90304014)

摘　　要：Boneh and Durfee have developed a cryptanalytic algorithm on low private key RSA. The algorithm is based on lattice basis reduction and breaks RSA with private key d 〈 N^0.292. Later on, an improved version by Blǒmer and May enhanced the efficiency, while reaching approximately this same upper bound. Unfortunately, in both the algorithms, there is a critical error in theoretical analysis, leading to the overestimated upper bound N^0.292. In this paper we present a more precise analytical model, with which the theoretical upper bound on d is modified to approximately d 〈 N^0.277 for ordinary RSA systems with a 1024-bit public key（N,e）.Boneh and Durfee have developed a cryptanalytic algorithm on low private key RSA.The algorithm is based on lattice basis reduction and breaks RSA with private key d < N0:292.Later on,an improved version by Blmer and May enhanced the efficiency,while reaching approximately this same upper bound.Unfortunately,in both the algorithms,there is a critical error in theoretical analysis,leading to the overestimated upper bound N0:292.In this paper we present a more precise analytical model,with which the theoretical upper bound on d is modified to approximately d < N0:277 for ordinary RSA systems with a 1024-bit public key eN;eT.

关 键 词：RSA CRYPTANALYSIS Low private key Lattice basis reduction 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构] TN918.2[自动化与计算机技术—计算机科学与技术]