Cryptology ePrint Archive: Report 2012/701
Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors
Noboru Kunihiro and Naoyuki Shinohara and Tetsuya Izu
Abstract: We discuss how to recover RSA secret keys from noisy key bits with erasures
There are two known algorithms recovering original secret keys from noisy
At Crypto 2009, Heninger and Shacham proposed a method for the case
where an erroneous version of secret keys contains only erasures.
Subsequently, Henecka et al. proposed a method
for an erroneous version containing only errors at Crypto2010.
For physical attacks such as side-channel and cold boot attacks,
we need to study key recovery from a noisy secret key containing both erasures
In this paper, we propose a method to recover a secret key from such an
and analyze the condition for error and erasure rates so that
our algorithm succeeds in finding the correct secret key in polynomial time.
We also evaluate a theoretical bound to recover the secret key
and discuss to what extent our algorithm achieves this bound.
Category / Keywords: public-key cryptography / RSA, cryptanalysis
Publication Info: This is the full version of PKC2013 paper.
Date: received 13 Dec 2012
Contact author: kunihiro at k u-tokyo ac jp
Available format(s): PDF | BibTeX Citation
Version: 20121218:130252 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]