エルガマル公開鍵暗号方式の証明
ビルドアップ
左から順に、アリス、ボブ、イブとしよう。アリスとボブはメッセージを交換する当事者で、イブはメッセージに興味を持つ消極的な攻撃者だ。オレンジ色の箱はアリスだけが知っている情報を、水色の箱はボブだけが知っている情報を、黒色の箱は公開されている（イブも知っている）情報を示している。
アリスにはボブから受け取るべきメッセージ$m \in \mathbb{N}$がある。
アルゴリズム 1
$\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$を安全にアリスに伝えることができる。
■
参照
離散対数問題の困難さを利用したセキュリティアルゴリズム
離散対数問題に対する攻撃アルゴリズム
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p70. ↩︎