📂整数論

エルガマル公開鍵暗号方式の証明

ビルドアップ

左から順に、アリス、ボブ、イブとしよう。アリスとボブはメッセージを交換する当事者で、イブはメッセージに興味を持つ消極的な攻撃者だ。オレンジ色の箱はアリスだけが知っている情報を、水色の箱はボブだけが知っている情報を、黒色の箱は公開されている（イブも知っている）情報を示している。

アリスにはボブから受け取るべきメッセージ$m \in \mathbb{N}$がある。

アルゴリズム ¹

$\mathbb{F}_{p}^{ \ast } = \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left\{ 1, g , g^2 , \cdots , g^{p-2} \right\}$ は要素数が$(p-1)$個の巡回群としよう。

---

キー設定: 非常に大きな素数$p$と$\text{ord}_{p} (g)$が大きな素数である$g \in \mathbb{F}_{p}^{ \ast }$を選んで公開する。

アリスは自分だけが知っているキー$1 \le a \le p-1$を決めて、$A \equiv g^{a} \pmod{p}$を計算して公開する。

---

暗号化: 一回用のランダムキー$k$を生成する。ボブは$c_{1} \equiv g^{k} \pmod{p}$と$c_{2} \equiv m A^{k} \pmod{p}$を計算して$(c_{1} , c_{2})$をアリスに送信する。

---

復号化: アリスが$(c_{1} , c_{2})$を使って$x \equiv (c_{1}^{a} )^{-1} c_{2} \equiv m \pmod{p}$を計算すると$x = m$を得る。イブは現実的に$a$を知ることができないため、$m$を知ることができない。

説明

実際、体系自体で$g$の位数$\text{ord}_{p} (g)$が大きくなければならない理由はないが、単純に計算する場合の偶然の可能性を下げるためには、位数が大きい数を選ぶ方が良い。

証明

復号化

アリスは$a$を知っており$c_{1} \equiv g^{k} \pmod{p}$と$c_{2} \equiv m A^{k} \pmod{p}$であるため$k$を知らなくても $$\begin{align*} (c_{1}^{a} )^{-1} c_{2} & \equiv \left( g^{ak} \right)^{-1} \cdot c_{2} \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m A^{k} \right) \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m \left( g^{a} \right)^{k} \right) \\ & \equiv m \left( g^{ak} \right)^{-1} \cdot g^{ak} \\ & \equiv m \pmod{p} \end{align*}$$ を簡単に計算することができる。

■

暗号化

イブは$c_{1}$と$c_{2}$しか知らず$a$と$k$を知らないため、離散対数問題${g}^{x} \equiv c_{1}^{a} \pmod{p}$を知ることができず、知ったとしても直接解かなければならない。これは非常に難しいため、ボブはメッセージ$m$を安全にアリスに伝えることができる。

■

参照

• 離散対数問題

離散対数問題の困難さを利用したセキュリティアルゴリズム

• ディフィー・ヘルマン鍵交換アルゴリズム
• エルガマル公開鍵暗号体系

離散対数問題に対する攻撃アルゴリズム

• シャンクスのアルゴリズム
• ポラードのロー アルゴリズム
• 離散対数問題が簡単に解ける条件