Paper 2004/147

Key Recovery Method for CRT Implementation of RSA

Matthew J. Campagna and Amit Sethi

Abstract

This paper analyzes a key recovery method for RSA signature generation or decryption implementations using the Chinese Remainder Theorem (CRT) speed up. The CRT-based RSA implementation is common in both low computing power devices and high speed cryptographic acceleration cards. This recovery method is designed to work in conjunction with a side-channel attack where the CRT exponents are discovered from a message decryption or signature generation operation, the public exponent is assumed small and the public modulus is unknown. Since many RSA implementations use the small, low hamming weight public exponent 65537 this turns out to be a realistic method. An algorithm for recovering the private key, modulus and prime factorization candidates is presented with a proof of correctness. Runtime estimates and sample source code is given.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
key recovery
Contact author(s)
matthew campagna @ pb com
History
2004-06-23: received
Short URL
https://ia.cr/2004/147
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/147,
      author = {Matthew J.  Campagna and Amit Sethi},
      title = {Key Recovery Method for CRT Implementation of RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2004/147},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/147}},
      url = {https://eprint.iacr.org/2004/147}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.