ElGamal暗号 ElGamal暗号の概要

ウィキペディア

ElGamal暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/20 21:39 UTC 版)

概要

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

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

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

暗号方式

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

鍵生成

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

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

暗号化

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

復号

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

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

実際、もし${\displaystyle (c_{1},c_{2})}$が正しい方法で生成された暗号文であれば、${\displaystyle 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暗号は、選択暗号文攻撃に対しては安全ではない。平文${\displaystyle m}$に対応する${\displaystyle (c_{1},c_{2})}$から、${\displaystyle 2m}$に対応する暗号文${\displaystyle (c_{1},2c_{2})}$を作成することができるからである。