ElGamal暗号

ElGamal暗号（エルガマルあんごう、ElGamal encryption）とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。1984年Taher Elgamalが発表した。

概要

Diffie-Hellman鍵共有方式で共有した乱数を使ってワンタイムパッド (OTP) を行うと暗号通信ができる。ElGamal暗号は、これを利用してDiffie-Hellman鍵共有方式を暗号方式として利用できるように変形したものである。

ElGamal暗号は暗号 (cipher) であるが、これとは別にデジタル署名 (digital signature) に応用することができるElGamal署名も発表されている。

用語については、暗号の用語、暗号理論の用語を参照。

暗号方式

$k$ をセキュリティ・パラメータとする。

鍵生成

巡回群Gで、位数qが素数であり、かつ $q$ のビット数が $k$ であるものを選ぶ。
Gの生成元 $g$ を選ぶ。
xを $\{0,...,q-1\}$ からランダムに選ぶ。
$h=g^{x}$ とする。
$(G,q,g,h)$ を公開鍵とし、xを秘密鍵とする。

平文空間はGであり、暗号文空間はG²である。

暗号化

Gの元mを平文として受け取る。
rを $\{0,...,q-1\}$ からランダムに選ぶ。
$c_{1}=g^{r}$ , $c_{2}=m\cdot h^{r}$ を計算する。
$(c_{1},c_{2})$ を暗号文とする。

復号

受け取った暗号文を $(c_{1},c_{2})\in G\times G$ とする。

$m=c_{2}\cdot ({c_{1}}^{x})^{-1}$ とする。

実際、もし $(c_{1},c_{2})$ が正しい方法で生成された暗号文であれば、 $m'=c_{2}\cdot ({c_{1}}^{x})^{-1}=m\cdot (g^{x})^{r}\cdot ((g^{r})^{x})^{-1}=m$ を満たす。

安全性

上で"離散対数問題が困難であることを基にした"と書いたがこれは正確な表現では無い。実際には、DLP仮定ではなく、Computational Diffie-Hellman仮定（CDH仮定）およびDecisional Diffie-Hellman仮定（DDH仮定）を基にしている。 ElGamal暗号が選択平文攻撃に対して完全解読できないということ（OW-CPAであるということ）と、CDH仮定とが同値である。また、ElGamal暗号が選択平文攻撃のもとIndistinguishabillityをもつということ（IND-CPAであるということ）と、DDH仮定とが同値である。

ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文 $m$ に対応する $(c_{1},c_{2})$ から、 $2m$ に対応する暗号文 $(c_{1},2c_{2})$ を作成することができるからである。

巡回群Gについて

pを素数とするとき、G = ${\mathbb {Z} }_{p}^{*}$ としてはいけない。このような群上ではDDH仮定が破れる。この問題を回避しつつ巡回群Gをとる主な方法は二つある。

巡回群Gを ${\mathbb {Z} }_{p}^{*}$ の部分群とする。
巡回群Gを楕円曲線上で定義する（楕円曲線暗号）。

ここでは上の方法を説明する。

小さな自然数kと大きな素数qに対して、素数pをp = kq+1となるように取る。
- まず素数qを選んでから、p = kq + 1が素数かどうかを調べればよい。
$g\in {\mathbb {Z} }_{p}^{*}$ を、gの位数がqとなるようにランダムに選ぶ。
$G=<g>$ は ${\mathbb {Z} }_{p}^{*}$ の部分群となっている。

尚、k=2に対してp = 2q + 1が成り立つ素数の組(p,q)が無限に存在するかどうかは未解決問題である（ソフィー・ジェルマン問題、素数#未解決問題）。

参考文献

原論文

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.