Small secret exponent attacks on RSA with unbalanced prime factors

摘要

Boneh and Durfee (Eurocrypt 1999) proposed two polynomial time attacks on small secret exponent RSA. The first attack works when d <; N0.284 whereas the second attack works when d <; N0.292. Both attacks are based on lattice based Coppersmith's method to solve modular equations. Durfee and Nguyen (Asiacrypt 2000) extended the attack to a variant of RSA where prime factors are not the same sizes. However, the attack extended only the first attack of the Boneh-Durfee. Hence, an open problem remains, i.e., if the Boneh-Durfee second attack can be extended to unbalanced RSA. In this paper, we propose a desired attack that extended the Boneh-Durfee second attack. Our proposed attack fully improves the Durfee-Nguyen attack for all size of prime factors. The improvement stems from our technical lattice construction. Although Durfee and Nguyen only analyzed lattices whose basis matrices are triangular, we analyze broader classes of lattices that contain non-triangular basis matrices. The analysis can be performed by using the unravelled linearization proposed by Herrmann and May (Asiacrypt 2009) and the transformation on the Boneh-Durfee lattices proposed by Takayasu and Kunihiro (PKC 2016). As a result, we can exploit useful algebraic structure compared with the Durfee-Nguyen.