New Results for Partial Key Exposure on RSA with Exponent Blinding

Stelvio Cimato, Silvia Mella, Ruggero Susella

2015

Abstract

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.

Paper Citation

in Harvard Style

Cimato S., Mella S. and Susella R. (2015). New Results for Partial Key Exposure on RSA with Exponent Blinding . In Proceedings of the 12th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2015) ISBN 978-989-758-117-5, pages 136-147. DOI: 10.5220/0005571701360147

in Bibtex Style

@conference{secrypt15,
author={Stelvio Cimato and Silvia Mella and Ruggero Susella},
title={New Results for Partial Key Exposure on RSA with Exponent Blinding},
booktitle={Proceedings of the 12th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2015)},
year={2015},
pages={136-147},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005571701360147},
isbn={978-989-758-117-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 12th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2015)
TI - New Results for Partial Key Exposure on RSA with Exponent Blinding
SN - 978-989-758-117-5
AU - Cimato S.
AU - Mella S.
AU - Susella R.
PY - 2015
SP - 136
EP - 147
DO - 10.5220/0005571701360147