New Partial Key Exposure Attacks on RSA

In 1998, Boneh, Durfee and Frankel [4] presented several attacks on RSA when an adversary knows a fraction of the secret key bits. The motivation for these so-called partial key exposure attacks mainly arises from the study of side-channel attacks on RSA. With side channel attacks an adversary gets either most significant or least significant bits of the secret key. The polynomial time algorithms given in [4] only work provided that the public key e is smaller than $N^{\frac{1}{2}}$. It was raised as an open question whether there are polynomial time attacks beyond this bound. We answer this open question in the present work both in the case of most and least significant bits. Our algorithms make use of Coppersmith’s heuristic method for solving modular multivariate polynomial equations [8]. For known most significant bits, we provide an algorithm that works for public exponents e in the interval [$N^{\frac{1}{2}}$, N0.725]. Surprisingly, we get an even stronger result for known least significant bits: An algorithm that works for all $e < N^{\frac{7}{8}}$.We also provide partial key exposure attacks on fast RSA-variants that use Chinese Remaindering in the decryption process (e.g. [20,21]). These fast variants are interesting for time-critical applications like smart-cards which in turn are highly vulnerable to side-channel attacks. The new attacks are provable. We show that for small public exponent RSA half of the bits of d _p = d mod p-1 suffice to find the factorization of N in polynomial time. This amount is only a quarter of the bits of N and therefore the method belongs to the strongest known partial key exposure attacks.