New Results for Partial Key Exposure on RSA with Exponent Blinding
Stelvio Cimato, Silvia Mella, Ruggero Susella · 2015
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.