📂整数論

ディフィー・ヘルマン鍵交換アルゴリズムの証明

ビルドアップ

左から順に、アリス、ボブ、イヴと呼ぼう。アリスとボブはメッセージを送受信する当事者で、イヴはメッセージに関心がある受動的攻撃者だ。オレンジ色の箱はアリスだけが知っている情報を、水色の箱はボブだけが知っている情報を、黒い箱は公開された（イヴも知っている）情報を表している。

アリスとボブは暗号システム $( \mathcal{K} , \mathcal{M} , \mathcal{C} , e_{k} , d_{k} )$ 下でメッセージを送受信しようとする。残念ながら、イヴは暗号システムの復号関数 $d_{k}$ を知っており、鍵 $k$ をイヴに気づかれずに直接渡すことはできない状況だ。しかし、このような状況でも、アリスとボブの二人だけが共有する鍵 $K$ をそれぞれ生成できるならば、イヴは $d_{k}$ を知っていても鍵 $K$ を知らないので暗号文を解読できないだろう。この解決策がまさにディフィー・ヘルマン鍵交換アルゴリズムだ。

アルゴリズム ¹

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

---

ステップ1.

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

---

ステップ2.

アリスは任意の整数 $a$ を選び、ボブは任意の整数 $b$ を選ぶ。

---

ステップ3. 暗号化

$A \equiv g^{a} \pmod{p}$ と $B \equiv g^{b} \pmod{p}$ を計算して公開する。

---

ステップ4. 復号

$K \equiv B^{a} \equiv A^{b} \pmod{p}$ を計算して鍵 $K$ で暗号化された暗号文 $c = e_{K} (m)$ を使用すると、イヴは現実的に鍵 $K$ を知ることができないため、$m = d_{K} (c)$ を知ることができない。

説明

ステップ1. で、$\text{ord}_{p} (g)$ は位数として、可能な限り大きな素数でなければならず、$g_{n}$ が $n$ の値によって予測しにくく変化するためだ。$\text{ord}_{p} (g) = 3$ 程度しかなければ、$K$ を計算するのがあまりにも簡単だ。$\text{ord}_{p} (g) = nm$ が合成数である場合、$g^{nm} \equiv 1 \pmod{p}$ といえば、$( g^{n} ) ^{m} \equiv 1 \pmod{p}$ となるので、実質的に小さい位数の$G:=g^{n}$ を使用するのと同じことになる。

注目すべき点は、ディフィー・ヘルマン鍵交換アルゴリズム自体が何らかの暗号システムになるわけではなく、単に受動的攻撃者がいる状況で秘密鍵 $K$ を作り出す方法であるということだ。このようにして得られる$K$ 自体はメッセージとは無関係であり、暗号システムも全く変わらない。

証明

復号

$a$ と $b$ を知っているアリスとボブは、 $$\begin{align*} K & \equiv A^{b} \\ & \equiv \left(g^{a} \right)^{b} \\ & \equiv g^{ab} \\ & \equiv \left(g^{b} \right)^{a} \\ & \equiv B^{a} \pmod{p} \end{align*}$$ を簡単に計算できる。したがって、公開された $g$ があれば、$a$、$b$ のどちらか一方を知っていれば、$K$ を求めることができる。

■

暗号化

イヴは$A$ と $B$ しか知らず、$a$ と $b$ を知らないため、離散対数問題 $A^{x} \equiv K \pmod{p}$ もしくは $B^{x} \equiv K \pmod{p}$ を解かなければならない。これは非常に困難であるため、アリスとボブは鍵$K$ を使用して、イヴから安全に通信ができる。

■

一緒に見る

• 離散対数問題

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

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

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

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