ElGamal暗号（エルガマルあんごう、ElGamal encryption）とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。1984年が発表した。Diffie-Hellman鍵共有方式で共有した乱数を使ってワンタイムパッド (OTP) を行うと暗号通信ができる。ElGamal暗号は、これを利用してDiffie-Hellman鍵共有方式を暗号方式として利用できるように変形したものである。ElGamal暗号は暗号 (cipher) であるが、これとは別にデジタル署名 (digital signature) に応用することができるElGamal署名も発表されている。用語については、暗号の用語、暗号理論の用語を参照。formula_1 をセキュリティ・パラメータとする。平文空間は"G"であり、暗号文空間は"G"である。受け取った暗号文をformula_12とする。実際、もしformula_11が正しい方法で生成された暗号文であれば、formula_15を満たす。上で"離散対数問題が困難であることを基にした"と書いたがこれは正確な表現では無い。実際には、DLP仮定ではなく、Computational Diffie-Hellman仮定（CDH仮定）およびDecisional Diffie-Hellman仮定（DDH仮定）を基にしている。ElGamal暗号が選択平文攻撃に対して完全解読できないということ（OW-CPAであるということ）と、CDH仮定とが同値である。また、ElGamal暗号が選択平文攻撃のもとIndistinguishabillityをもつということ（IND-CPAであるということ）と、DDH仮定とが同値である。ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文formula_16に対応するformula_11から、formula_18に対応する暗号文formula_19を作成することができるからである。"p"を素数とするとき、"G" = formula_20としてはいけない。このような群上ではDDH仮定が破れる。主な方法は二つある。ここでは上の方法を説明する。尚、"k=2"に対して"p = 2q + 1"が成り立つ素数の組("p,q")が無限に存在するかどうかは未解決問題である（ソフィー・ジェルマン問題、素数#素数に関連する未解決の問題）。

出典:wikipedia