Attacking RSA with a Composed Decryption Exponent Using Unravelled Linearization

摘要

Recently, Nitaj and Douh presented a new attack on RSA with a composed decryption exponent. To be specific, they assumed that the decryption exponent in RSA is of the form d = Md_1 + d_0 where M is a known positive integer and d_0 and d_1 are two suitably small unknown integers. They gave a lattice-based decryption exponent recovery attack on this kind of RSA when the exponent d is under a larger bound than the well-known one N~(0.292) given by Boneh and Durfee. In this paper, we reconsider the same problem and present a new attack by using the unravelled linearization technique proposed by Herrmann and May at Asiacrypt 2009. Our result is theoretically better than that of Nitaj and Douh and more importantly, is more efficient in terms of the dimension of lattice involved in the attack.