A Partial Key Exposure Attack on RSA Using a 2-Dimensional Lattice

Abstract. We describe an attack on the RSA cryptosystem when the private exponent d is chosen to be ’small’, under the condition that a suf-ficient amount of bits of d is available to the attacker. The attack uses a 2-dimensional lattice and is therefore (in the area of the keyspace where it applies) more efficient than known attacks using Coppersmith tech-niques. Moreover, we show that the attacks of Wiener and Verheul/Van Tilborg, using continued fractions techniques, are special deterministic cases of our attack, which in general is heuristic