ElGamal暗号（エルガマルあんごう、ElGamal encryption）とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。1984年Taher Elgamal
が発表した。Diffie-Hellman鍵共有方式で共有した乱数を使ってワンタイムパッド (OTP) を行うと暗号通信ができる。ElGamal暗号は、これを利用してDiffie-Hellman鍵共有方式を暗号方式として利用できるように変形したものである。
ElGamal暗号は暗号 (cipher) であるが、これとは別にデジタル署名 (digital signature) に応用することができるElGamal署名も発表されている。
用語については、暗号の用語、暗号理論の用語を参照。 k {\displaystyle k} をセキュリティ・パラメータとする。 平文空間はGであり、暗号文空間はG2である。 受け取った暗号文を ( c 1 , c 2 ) ∈ G × G {\displaystyle (c_{1},c_{2})\in G\times G} とする。 実際、もし ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} が正しい方法で生成された暗号文であれば、 m ′ = c 2 ⋅ ( c 1 x ) − 1 = m ⋅ ( g x ) r ⋅ ( ( g r ) x ) − 1 = m {\displaystyle m'=c_{2}\cdot ({c_{1}}^{x})^{-1}=m\cdot (g^{x})^{r}\cdot ((g^{r})^{x})^{-1}=m} を満たす。 上で"離散対数問題が困難であることを基にした"と書いたがこれは正確な表現では無い。実際には、DLP仮定ではなく、Computational Diffie-Hellman仮定 ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文 m {\displaystyle m} に対応する ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} から、 2 m {\displaystyle 2m} に対応する暗号文 ( c 1 , 2 c 2 ) {\displaystyle (c_{1},2c_{2})} を作成することができるからである。 pを素数とするとき、G = Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} としてはいけない。このような群上ではDDH仮定が破れる。この問題を回避しつつ巡回群Gをとる主な方法は二つある。 ここでは上の方法を説明する。 尚、k=2に対してp = 2q + 1が成り立つ素数の組(p,q)が無限に存在するかどうかは未解決問題である（ソフィー・ジェルマン問題、素数#未解決問題）。
暗号方式
鍵生成
巡回群Gで、位数qが素数であり、かつ q {\displaystyle q} のビット数が k {\displaystyle k} であるものを選ぶ。
Gの生成元 g {\displaystyle g} を選ぶ。
xを { 0 , . . . , q − 1 } {\displaystyle \{0,...,q-1\}} からランダムに選ぶ。
h = g x {\displaystyle h=g^{x}} とする。
( G , q , g , h ) {\displaystyle (G,q,g,h)} を公開鍵とし、xを秘密鍵とする。
暗号化
Gの元mを平文として受け取る。
rを { 0 , . . . , q − 1 } {\displaystyle \{0,...,q-1\}} からランダムに選ぶ。
c 1 = g r {\displaystyle c_{1}=g^{r}} , c 2 = m ⋅ h r {\displaystyle c_{2}=m\cdot h^{r}} を計算する。
( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} を暗号文とする。
復号
m = c 2 ⋅ ( c 1 x ) − 1 {\displaystyle m=c_{2}\cdot ({c_{1}}^{x})^{-1}} とする。
安全性
巡回群Gについて
巡回群Gを Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} の部分群とする。
巡回群Gを楕円曲線上で定義する（楕円曲線暗号）。
小さな自然数kと大きな素数qに対して、素数pをp = kq+1となるように取る。
まず素数qを選んでから、p = kq + 1が素数かどうかを調べればよい。
g ∈ Z p ∗ {\displaystyle g\in {\mathbb {Z} }_{p}^{*}} を、gの位数がqとなるようにランダムに選ぶ。
G =< g > {\displaystyle G=<g>} は Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} の部分群となっている。
参考文献
原論文
A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms; Taher Elgamal; IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp. 469?472 or CRYPTO 84, pp. 10?18, Springer-Verlag.
関連項目
暗号
暗号理論
ElGamal署名
離散対数
表
話
編
歴
表
話
編
歴
暗号
暗号史
暗号解読
Cryptography portal
en:Outline of cryptography
共通鍵暗号
ブロック暗号
ストリーム暗号
暗号利用モード
公開鍵暗号
暗号学的ハッシュ関数