ディフィー・ヘルマン鍵共有 (Diffie-Hellman Key Exchange) の群論による説明

群論的基礎

ディフィー・ヘルマン鍵共有は群論の枠組みで説明すると、以下の要素を利用します。

1. 有限巡回群 ( G )

• 群 ( G ) は有限集合であり、乗法演算に関して閉じています。
• 特に、群 ( G ) は素数 ( p ) を法とする既約剰余類群 $$(\mathbb{Z}/p\mathbb{Z})^*$$で構成されます。
• ( G ) の元に対する群演算は「乗法」とし、元の逆元も存在します。

2. 生成元 ( g )

• $$( g \in G ) は ( G ) の生成元（巡回群の構造をもつ）で、以下の性質を満たします：$$
  $$[
  G = { g^0, g^1, g^2, \dots, g^{|G|-1} } \mod p
  ]$$
  $$ ここで ( |G| = p-1 ) は群の位数です。$$

3. 離散対数問題

• $$( g^x \mod p )$$ を計算することは効率的に可能ですが、逆に $$( g^x \mod p )$$ が与えられたときに$$ ( x )$$ を見つけるのは計算量的に困難です。これがアルゴリズムの安全性を支える鍵となります。

---

アルゴリズムの詳細

1. 公開された群と生成元の設定

大きな素数pとGの生成元gを準備します。

2. 秘密値の選択

• アリスはランダムな整数aを選びます。
• ボブはランダムな整数bを選びます。

3. 公開値の計算

• アリスは $$( A = g^a \mod p )$$ を計算し、ボブに送信します。
• ボブは $$( B = g^b \mod p )$$ を計算し、アリスに送信します。

4. 共通鍵の計算

• アリスはボブから受け取ったBを用いて次を計算します：
  $$[
  K_{\text{Alice}} = B^a \mod p = (g^b)^a \mod p
  ] $$
• ボブはアリスから受け取った ( A ) を用いて次を計算します：
  $$[
  K_{\text{Bob}} = A^b \mod p = (g^a)^b \mod p
  ]$$

群論におけるべき乗の結合法則により、次が成立します：
$$[
K_{\text{Alice}} = K_{\text{Bob}} = g^{ab} \mod p
]$$

---

具体例: 実際の計算

以下の値を使用します：

• $$( p = 23 ): 群の法（素数）$$
• $$( g = 5 ): 群の生成元$$
• $$アリスの秘密値 ( a = 6 )、ボブの秘密値 ( b = 15 )$$

手順

1. アリスの公開値:
   $$ [
   A = g^a \mod p = 5^6 \mod 23 = 15625 \mod 23 = 8
   ] $$

2. ボブの公開値:
   $$ [
   B = g^b \mod p = 5^{15} \mod 23 = 30517578125 \mod 23 = 19
   ]$$

3. 共通鍵の計算:

   • アリス側：
     $$ [
     K_{\text{Alice}} = B^a \mod p = 19^6 \mod 23 = 47045881 \mod 23 = 2
     ]$$
   • ボブ側：
     $$[
     K_{\text{Bob}} = A^b \mod p = 8^{15} \mod 23 = 35184372088832 \mod 23 = 2
     ]$$

$$したがって、アリスとボブは共通鍵 ( K = 2 ) を共有します。$$

---

安全性の理論

• 離散対数問題の難しさ:
  $$( g^a \mod p ) と ( g^b \mod p ) を観測しても、$$
  $$秘密値 ( a ) または ( b ) を特定するのは現実的に難しいです。$$

• Diffie-Hellman問題の困難性:
  $$( g^a \mod p ) と ( g^b \mod p ) を知っていても、$$
  $$直接 ( g^{ab} \mod p ) を計算するのは困難です。$$

---