ElGamal暗号のソースを表示

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

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

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

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

== 暗号方式 ==

<math>k</math> をセキュリティ・パラメータとする。

=== 鍵生成 ===

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

平文空間は''G''であり、暗号文空間は''G<sup>2</sup>''である。

=== 暗号化 ===
*''G''の元''m''を平文として受け取る。
*''r''を<math>\{0,...,q-1\}</math>からランダムに選ぶ。
*<math>c_1 = g^{r}</math>, <math>c_2 = m \cdot h^{r}</math>を計算する。
*<math>(c_1, c_2)</math>を暗号文とする。

=== 復号 ===
受け取った暗号文を<math>(c_1, c_2) \in G \times G</math>とする。
*<math>m = c_2 \cdot ({c_1}^x)^{-1}</math>とする。
実際、もし<math>(c_1, c_2)</math>が正しい方法で生成された暗号文であれば、<math>m' = c_2 \cdot ({c_1}^x)^{-1} = m \cdot (g^x)^r \cdot ((g^r)^x)^{-1} = m</math>を満たす。

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

ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文<math>m</math>に対応する<math>(c_1, c_2)</math>から、<math>2 m</math>に対応する暗号文<math>(c_1, 2 c_2)</math>を作成することができるからである。

== 巡回群''G''について ==
''p''を素数とするとき、''G'' = <math>{\mathbb Z}_p^{*}</math>としてはいけない。このような群上ではDDH仮定が破れる。
この問題を回避しつつ巡回群''G''をとる主な方法は二つある。
*巡回群''G''を<math>{\mathbb Z}_p^{*}</math>の部分群とする。
*巡回群''G''を楕円曲線上で定義する（[[楕円曲線暗号]]）。
ここでは上の方法を説明する。
*小さな自然数''k''と大きな素数''q''に対して、素数''p''を''p = kq+1''となるように取る。
**まず素数''q''を選んでから、''p = kq + 1''が素数かどうかを調べればよい。
*<math>g \in {\mathbb Z}_p^{*}</math>を、''g''の位数が''q''となるようにランダムに選ぶ。
*<math>G = <g></math>は<math>{\mathbb Z}_p^{*}</math>の部分群となっている。
尚、''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.

== 関連項目 ==
*[[暗号]]
*[[暗号理論]]
*[[ElGamal署名]]
*[[離散対数]]

{{cryptography navbox|public-key}}
{{DEFAULTSORT:えるかまるあんこう}}
[[Category:暗号]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]