Side-Channel Attacks on Textbook RSA and ElGamal Encryption

  • Ulrich Kühn
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


This paper describes very e.cient attacks on plain RSA encryption as usually described in textbooks. These attacks exploit side channels caused by implementations that, during decryption, incorrectly make certain assumption on the size of message. We highlight different assumptions that are easily made when implementing plain RSA decryption and present corresponding attacks.

These attacks make clear that plain RSA is a padding scheme that has to be checked carefully during decryption instead of simply assuming a length of the transported message.

Furthermore we note that the attacks presented here do also work against a similar setting of ElGamal encryption with only minimal changes.


RSA encryption ElGamal encryption Side-channel attack 


  1. [1]
    E. Bach and R. Peralta. Asymptotic semismoothness probabilities. Mathematics of Computation, 65(216):1701–1715, 1996. 331, 332zbMATHCrossRefMathSciNetGoogle Scholar
  2. [2]
    D. Balenson. RFC 1423: Privacy enhancement for Internet electronic mail: Part III: Algorithms, modes, and identifiers, Feb. 1993. Obsoletes RFC1115 [11]. 335, 336Google Scholar
  3. [3]
    D. Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standards PKCS #1. In H. Krawczyk, editor, Advances in Cryptology–CRYPTO’ 98, volume 1462 of Lecture Notes in Computer Science, pages 1–12. Springer Verlag, 1998. 324, 325, 334, 335CrossRefGoogle Scholar
  4. [4]
    D. Bleichenbacher. Decrypting ElGamal messages. Message to ietf-openpgp mailing list on, April 1999. 333
  5. [5]
    D. Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2):203–213, February 1999. 324zbMATHMathSciNetGoogle Scholar
  6. [6]
    D. Boneh, A. Joux, and P.Q. Nguyen. Why Textbook ElGamal and RSA Encryption Are Insecure. In T. Okamoto, editor, Advances in Cryptology–ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 30–43. Springer Verlag, 2000. 324, 333CrossRefGoogle Scholar
  7. [7]
    Bremen Online Services. OSCI–Online-Services-Computer-Interface. Candidate for Version 1.0, November 2000. 1.html. 334
  8. [8]
    T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G.R. Blakley and D. Chaum, editors, Advances in Cryptology: Proceedings of CRYPTO 84, volume 196 of Lecture Notes in Computer Science, pages 10–18. Springer-Verlag, 1985, 19–22 Aug. 1984. 333Google Scholar
  9. [9]
    HBCI — Home Banking Computer Interface. Specification Version 2.2, May 2000. 334
  10. [10]
    HBCI–Home Banking Computer Interface. Draft Specification Version 3.0, July 2002. 334
  11. [11]
    J. Linn. RFC 1115: Privacy enhancement for Internet electronic mail: Part III—algorithms, modes, and identifiers, Aug. 1989. Obsoleted by RFC1423 [2]. 335, 336Google Scholar
  12. [12]
    J. Manger. A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0. In J. Kilian, editor, Advances in Cryptology — Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pages 230–238. Springer Verlag, 2001. 324, 325, 327, 331Google Scholar
  13. [13]
    OSCI Leitstelle. OSCI-Transport Version 1.2, June 2002. See 335
  14. [14]
    H. Riesel. Prime Numbers and Computer Methods for Factorization. Birkhäuser, 2nd edition, 1994. 331, 333Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Ulrich Kühn
    • 1
  1. 1.Dresdner BankIS-STA 5, Information SecurityFrankfurtGermany

Personalised recommendations