New Results for Partial Key Exposure on RSA with Exponent Blinding

In 1998, Boneh, Durfee and Frankel introduced partial key exposure attacks, a novel application of Coppersmith's method, to retrieve an RSA private key given only a fraction of its bits. This type of attacks is of particular interest in the context of side-channel attacks. By applying the exponent blinding technique as a countermeasure for side-channel attacks, the private exponent becomes randomized at each execution. Thus the attacker has to rely only on a single trace, significantly incrementing the noise, making the exponent bits recovery less effective. This countermeasure has also the side-effect of modifying the RSA equation used by partial key exposure attacks, in a way studied by Joye and Lepoint in 2012. We improve their results by providing a simpler technique in the case of known least significant bits and a better bound for the known most significant bits case. Additionally, we apply partial key exposure attacks to CRT-RSA when exponent blinding is used, a case not yet analyzed in literature. Our findings, for which we provide theoretical and experimental results, aim to reduce the number of bits to be recovered through side-channel attacks in order to factor an RSA modulus when the implementation is protected by exponent blinding.