Remarks on the bounds for cryptanalysis of low private key RSA
Haijian Zhou, Ping Luo, Daoshun Wang, Yiqi Dai · Progress in Natural Science Materials International · 2009
Abstract 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 Blomer 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 ) .