ElGamal暗号#

ElGamal暗号#

ElGamal暗号はDH鍵配送法に基づく公開鍵暗号である。

  • 鍵生成

  1. \(k\)ビットの大きな素数\(q\)と秘密鍵\(x \in \mathbf{Z}_q\)をランダムに選択し、原始元\(g\space (2< g< q)\)を選ぶ。

  2. \(y=g^x \pmod{q}\)として公開鍵\((g,q,y)\)を公開する。

  • 暗号化

  1. 平文\(m\in \langle g \rangle\)に対して\(r\in \mathbf{Z}_q\)をランダムに選択する。

  2. \(c_1 = g^r \pmod{q}\),　\(c_2 = my^r \pmod{q}\)を計算する。

  3. 暗号文を\((c_1,c_2)\)とする。

  • 復号化

  1. 受け取った暗号文(\(c_1,c_2\))および秘密鍵\(x\)から、平文\(m\)を

\[ c2(c_1^x)^{-1} \pmod{q} =m(y^r)(g^{rx})^{-1} \pmod{q}=m(g^{rx})(g^{rx})^{-1} \pmod{q}=m \pmod{q} \]

と計算し，暗号文を復号する。

DH問題との等価性#

公開鍵\((g,y)\)と暗号文\((c_1,c_2)\)から平文\(m\)を求める問題は、\((g,g^x,g^r)\)から\(g^{xr}\)を求めるDH問題と等価である。以下は等価性の証明である。

  • 定理1 DH \(\rightarrow\) ELG

DH問題を解く効率的なアルゴリズムAが存在すると仮定する。このとき、ElGamal暗号の一方向性を破る効率的なアルゴリズムBが存在する。

証明:
Bへの入力を公開鍵\((g,y)\)と暗号文\((c_1,c_2)\)としたとき、BはAに\((g,y=g^x,c_1=g^r)\)を与えることで\(g^{xr}\)を得ることができる。これを用いて

\[ \frac{c_2}{g^{xr}} = \frac{my^r}{g^{xr}}=\frac{mg^{xr}}{g^{xr}} = m \]

よりElGamal暗号の一方向性を破ることができる。

  • 定理2 ELG \(\rightarrow\) DH

ElGamal暗号の一方向性を破る効率的なアルゴリズムが存在すると仮定する。このとき、DH問題を解く効率的なアルゴリズムが存在する。

証明：
Aへの入力を\((g,g^x,g^r)\)とする。このときAは\(c_2 \in \langle g \rangle \)をランダムに選択し、公開鍵\((g,y=g^x)\)と暗号文\((c_1=g^r,c_2)\)をBに与える。すると、Bは平文\(m\)を返すので

\[ \frac{c_2}{m} = y^r = g^{xr} \]

によってAは\(g^{xr}\)を求めることができDH問題を解くことができる。