Diffie-Hellman鍵交換プロトコル：理論とPython実装

2 min read

概要

Diffie-Hellman（ディフィー・ヘルマン）鍵交換は、1976年にWhitfield DiffieとMartin Hellmanによって発表された、公開鍵暗号の概念を初めて具体化したプロトコルです。このプロトコルを用いることで、事前に秘密の情報を共有していなくても、盗聴の危険がある公開された通信路を通じて、安全に共通の秘密鍵を確立することができます。

このプロトコルは、**前方秘匿性（Forward Secrecy）**を確保する上で重要です。前方秘匿性とは、たとえ将来的に秘密鍵が漏洩したとしても、過去の通信内容が解読されないようにする性質を指します。DH鍵交換では、セッションごとに新しい共通鍵を生成するため、この性質が実現されます。

アルゴリズムの原理

Diffie-Hellman鍵交換は、離散対数問題の困難性を安全性の根拠としています。

  1. 公開パラメータの合意: 通信を行うアリスとボブは、まず以下の2つの公開パラメータに合意します。

    • 大きな素数 $p$
    • $p$ を法とする原始根（または生成元）$g$

  2. 秘密鍵の生成:

    • アリスは秘密の整数 $a$ をランダムに選びます。
    • ボブは秘密の整数 $b$ をランダムに選びます。 これらの $a$ と $b$ は、それぞれアリスとボブの秘密鍵となります。

  3. 公開鍵の計算と交換:

    • アリスは自身の公開鍵 $A = g^a \pmod{p}$ を計算し、ボブに送信します。
    • ボブは自身の公開鍵 $B = g^b \pmod{p}$ を計算し、アリスに送信します。 この $A$ と $B$ は公開された通信路を流れるため、盗聴者も知ることができます。

  4. 共通鍵の計算:

    • アリスは、ボブから受け取った公開鍵 $B$ と自身の秘密鍵 $a$ を使って、共通鍵 $S_A = B^a \pmod{p}$ を計算します。
    • ボブは、アリスから受け取った公開鍵 $A$ と自身の秘密鍵 $b$ を使って、共通鍵 $S_B = A^b \pmod{p}$ を計算します。

ここで、$S_A = (g^b)^a \pmod{p} = g^{ba} \pmod{p}$ であり、$S_B = (g^a)^b \pmod{p} = g^{ab} \pmod{p}$ となるため、$S_A = S_B$ となり、アリスとボブは同じ秘密の共通鍵を共有できます。

離散対数問題

盗聴者が公開されている $g, p, A, B$ を知っていたとしても、秘密鍵 $a$ や $b$ を計算することは非常に困難です。

$A = g^a \pmod{p}$ という式において、$A, g, p$ が既知のときに $a$ を求める問題は離散対数問題と呼ばれます。この問題は、大きな素数 $p$ を用いると、現在の計算能力では現実的な時間で解くことが非常に難しいとされています。この困難性がDiffie-Hellman鍵交換の安全性の根拠となっています。

Pythonによる簡易実装

以下のPythonコードは、Diffie-Hellman鍵交換の原理を簡潔に示したものです。実際の暗号通信では、より大きな素数や安全な乱数生成器を使用する必要があります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import random

# 1. 公開パラメータの合意
# 実際には非常に大きな素数と原始根を使用
p = 23  # 大きな素数 (例: 23)
g = 5   # pを法とする原始根 (例: 5)

print(f"公開パラメータ: p = {p}, g = {g}\n")

# 2. 秘密鍵の生成
# アリスとボブがそれぞれ秘密の整数をランダムに選ぶ
# 実際には、p-1よりも小さい範囲でランダムに選ぶ
alice_private_key = random.randint(1, p - 1)
bob_private_key = random.randint(1, p - 1)

print(f"アリスの秘密鍵 (a): {alice_private_key}")
print(f"ボブの秘密鍵 (b): {bob_private_key}\n")

# 3. 公開鍵の計算と交換
# アリスの公開鍵 A = g^a mod p
alice_public_key = pow(g, alice_private_key, p) # pow(base, exp, mod) は (base**exp) % mod を計算
# ボブの公開鍵 B = g^b mod p
bob_public_key = pow(g, bob_private_key, p)

print(f"アリスの公開鍵 (A): {alice_public_key}")
print(f"ボブの公開鍵 (B): {bob_public_key}\n")

# 4. 共通鍵の計算
# アリスが計算する共通鍵 S_A = B^a mod p
shared_secret_alice = pow(bob_public_key, alice_private_key, p)
# ボブが計算する共通鍵 S_B = A^b mod p
shared_secret_bob = pow(alice_public_key, bob_private_key, p)

print(f"アリスが計算した共通鍵: {shared_secret_alice}")
print(f"ボブが計算した共通鍵: {shared_secret_bob}\n")

# 共通鍵が一致することを確認
if shared_secret_alice == shared_secret_bob:
    print(f"共通鍵が一致しました: {shared_secret_alice}")
else:
    print("共通鍵が一致しませんでした。")