Partial key exposure attacks on RSA with exponent blinding

Partial key exposure attacks, introduced by Boneh, Durfee and Frankel in 1998, aim at retrieving an RSA private key when a fraction of its bits is known. These attacks are of particular interest in the context of side-channel attacks, where the attacker can retrieve bits of the key exploiting leakages in the implementation. In this work we analyze the effectiveness of partial key exposure when a countermeasure for side-channel attacks is adopted. In particular, we consider the exponent blinding technique, which consists in randomizing the private exponent at each execution. We address our analysis to both RSA and CRT-RSA, providing theoretical proofs and experimental results.