Paper 2012/701

Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors

Noboru Kunihiro, Naoyuki Shinohara, and Tetsuya Izu

Abstract

We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. 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 and errors. In this paper, we propose a method to recover a secret key from such an erroneous version 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. This is the full version of PKC2013 paper.
Keywords
RSAcryptanalysis
Contact author(s)
kunihiro @ k u-tokyo ac jp
History
2012-12-18: received
Short URL
https://ia.cr/2012/701
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/701,
      author = {Noboru Kunihiro and Naoyuki Shinohara and Tetsuya Izu},
      title = {Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2012/701},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/701}},
      url = {https://eprint.iacr.org/2012/701}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.