Diffie-Hellman鍵交換の理論と実装：離散対数問題・Safe Prime・MITM対策・X25519までPythonで解説

なぜ Diffie-Hellman を学ぶか

Diffie-Hellman 鍵交換 (DH) は 1976 年に Whitfield Diffie と Martin Hellman が提案した、現代公開鍵暗号の原点となるプロトコルです。それ以前の暗号は、通信前にあらかじめ秘密鍵を共有しておく共通鍵暗号しか存在せず、「鍵をどう安全に渡すか」という根本問題が未解決のままでした。DH は公開された通信路だけで共通の秘密鍵を確立できることを示し、その翌年に登場する RSA 暗号 と並んで公開鍵暗号時代の幕を開けました。

DH と RSA は混同されがちですが、目的が異なります。RSA は「メッセージ自体を暗号化する」公開鍵暗号方式であり、DH は「メッセージは暗号化せず、共通鍵を作るためだけに使う」鍵共有プロトコルです。実運用では、DH で共有した鍵を AES などの共通鍵暗号に渡してメッセージを暗号化する、というハイブリッド方式が標準です。

現代の DH の応用は広く、TLS 1.3 の鍵交換は ECDHE (Ephemeral ECDH) が必須、SSH では DH group exchange または curve25519-sha256、Signal プロトコルでは Triple Diffie-Hellman (3DH/X3DH) が採用されています。いずれも DH の数学的核心は同じで、本記事ではそれを Python 実装と共に深掘りします。基盤となる高速指数計算については繰り返し二乗法による高速べき乗剰余計算を、暗号領域全体の俯瞰は暗号技術ロードマップを参照してください。

離散対数問題 (DLP)

DH の安全性は離散対数問題 (Discrete Logarithm Problem; DLP) の計算困難性に基づきます。素数 \(p\) と \(\mathbb{Z}_p^*\) の生成元 (原始根) \(g\) を固定したとき、ある \(h \in \mathbb{Z}_p^*\) に対して

を満たす整数 \(x\) を離散対数と呼びます。順方向の \(g^x \bmod p\) は繰り返し二乗法 によって \(O(\log x)\) で計算できますが、逆方向の \(x\) の復元は、現在知られている最速のアルゴリズム (Number Field Sieve, Pollard’s rho) でも準指数時間 (\(L_p[1/3, c]\) ) を要し、\(p\) を 2048 bit 以上にすれば事実上解けないとされています。この指数計算は易しく、対数計算は困難という非対称性こそが、RSA 暗号 における素因数分解と同じく、公開鍵暗号の数学的基盤となります。

原始根 (primitive root)

\(\mathbb{Z}_p^*\) の位数は \(p-1\) で、\(g\) が原始根であるとは、\(g\) の冪 \(\{g^0, g^1, \dots, g^{p-2}\}\) が \(\mathbb{Z}_p^*\) 全体を尽くすことを言います。これは \(g\) の位数が \(p-1\) に等しいことと同値です。原始根が存在する \(\mathbb{Z}_p^*\) は巡回群となり、後述のように共通鍵 \(K = g^{ab} \bmod p\) が \(\mathbb{Z}_p^*\) 全体に均等に分布することが保証されます。

プロトコル本体

通信したい Alice と Bob は、まず公開パラメータ \((p, g)\) を合意します。\(p\) は十分大きな素数、\(g\) は \(\mathbb{Z}_p^*\) の原始根です。これらは秘密にする必要はなく、RFC 3526 / RFC 7919 で標準化された値を使うのが実務的です。

Step 1. Alice はランダムに秘密整数 \(a \in [2, p-2]\) を選び、公開鍵 \(A\) を計算します。

Step 2. Bob も同様に秘密整数 \(b\) を選び、公開鍵 \(B\) を計算します。

Step 3. Alice と Bob は公開鍵 \(A, B\) を公開通信路上で交換します。盗聴者 Eve は \((p, g, A, B)\) を全て観測できる前提です。

Step 4. Alice は Bob から受け取った \(B\) と自身の秘密 \(a\) から共通鍵 \(K\) を計算します。

Step 5. Bob も同様に \(A\) と自身の秘密 \(b\) から共通鍵を計算します。

冪指数の交換則により \(K_A = K_B = g^{ab} \bmod p\) となり、両者は同じ共通鍵 \(K\) を共有できます。実運用ではこの \(K\) をそのまま AES の鍵に使うのではなく、SHA-256 などのハッシュ関数 / KDF に通して鍵導出するのが標準です (後述)。

Eve は \(A, B\) から \(g^{ab}\) を直接計算する手段を持ちません。これを計算的 Diffie-Hellman 仮定 (CDH 仮定) と呼び、より強い判定 Diffie-Hellman 仮定 (DDH 仮定) と合わせて DH の安全性の根拠になっています。CDH が解ければ DLP も解けますが、その逆は自明ではないことに注意してください。

安全性の根拠と Safe Prime

DH の安全性は単に「\(p\) が大きい」だけでは担保されません。攻撃者は部分群攻撃 (small subgroup attack) によって、\(g\) の位数が小さい部分群に共通鍵を閉じ込め、Pohlig–Hellman アルゴリズムで離散対数を高速に解けてしまいます。これを防ぐために、\(p-1\) の素因数分解に小さな素因数が混ざらないようにする必要があります。

最も標準的な対策は Safe Prime の使用です。素数 \(p\) が

の形をとるとき、\(p\) を Safe Prime、\(q\) を Sophie Germain 素数と呼びます。このとき \(p-1 = 2q\) なので \(\mathbb{Z}_p^*\) の位数 \(p-1\) の素因数は \(2\) と \(q\) だけになり、攻撃可能な小部分群が存在しなくなります。生成元としては位数 \(q\) の元を選び、\(\mathbb{Z}_p^*\) の位数 \(q\) の部分群 (平方剰余の集合) 上で DH を行うのが現代的な作法です。

鍵長の目安は次の通りです。

NIST SP 800-57 では、現代の用途には最低 2048 bit、できれば 3072 bit 以上を推奨しています。1024 bit DH は 2015 年の Logjam 攻撃で実用的に破られたため、現在は使用すべきではありません。

MITM 攻撃と認証付き鍵交換

DH 単体の最大の弱点は中間者攻撃 (Man-in-the-Middle; MITM) です。Eve が Alice/Bob の間に介在し、\(A\) を \(A' = g^{a'}\) に、\(B\) を \(B' = g^{b'}\) に置き換えれば、Alice は Eve と \(g^{a b'}\) を、Bob は Eve と \(g^{a' b}\) を共有してしまい、Eve は両者の通信を平文で読めてしまいます。

この攻撃が成立する根本原因は、DH では公開鍵 \(A, B\) が「相手のもの」である保証がないことです。対策は公開鍵の真正性を別途認証することで、実務では以下のいずれかを組み合わせます。

1. 署名付き DH (Signed DH): Alice は \(A\) を秘密鍵で署名 (RSA や ECDSA) し、Bob は対応する公開鍵証明書 (PKI) で検証します。TLS 1.2 の ECDHE-RSA がこれに該当します。
2. PAKE (Password-Authenticated Key Exchange): 共有パスワードを使って DH を補強します。SPAKE2, OPAQUE などが代表例で、低エントロピーの秘密でも MITM 耐性を持たせます。
3. STS プロトコル (Station-to-Station): DH の公開鍵交換に署名と認証を組み込んだ古典的設計。
4. TLS 1.3 / Noise Protocol: 証明書認証と ECDHE を統合し、ハンドシェイクの 1RT 化と前方秘匿性を両立。

OAuth 2.0 / OIDC の文脈での認証アーキテクチャは OAuth 2.0/OIDC 入門 に、組織レベルのゼロトラスト設計は ゼロトラストセキュリティ にまとめています。

Python による実装

教育向け最小実装

sympy の素数判定・原始根計算と、Python 組み込みの pow(g, a, p) (内部で繰り返し二乗法 を使用) だけで、Safe Prime ベースの DH を素直に実装できます。

import secrets
import hashlib
from sympy import isprime, primitive_root


def gen_safe_prime(bits: int) -> tuple[int, int]:
    """p = 2q + 1 を満たす Safe Prime (p, q) を生成"""
    while True:
        q = secrets.randbits(bits - 1) | (1 << (bits - 2)) | 1
        if not isprime(q):
            continue
        p = 2 * q + 1
        if isprime(p):
            return p, q


def derive_key(shared_secret: int) -> bytes:
    """共通鍵 g^{ab} mod p から SHA-256 で 256bit セッション鍵を導出"""
    # 整数をバイト列にエンコードしてからハッシュ
    nbytes = (shared_secret.bit_length() + 7) // 8
    return hashlib.sha256(shared_secret.to_bytes(nbytes, "big")).digest()


# --- パラメータ生成 (Safe Prime) ---
p, q = gen_safe_prime(512)  # 教育用に 512 bit、実用では 2048 bit 以上
g = primitive_root(p)

# --- Alice ---
a = secrets.randbelow(p - 2) + 2
A = pow(g, a, p)

# --- Bob ---
b = secrets.randbelow(p - 2) + 2
B = pow(g, b, p)

# --- 共通鍵計算 ---
K_alice = pow(B, a, p)
K_bob = pow(A, b, p)
assert K_alice == K_bob

session_key = derive_key(K_alice)
print(f"共通鍵 (先頭 16 byte): {session_key[:16].hex()}")

ポイントは 4 点です。

1. 乱数は secrets: random モジュールは暗号用途には不適切で、CSPRNG である secrets.randbits / secrets.randbelow を使います。
2. pow(g, a, p) で繰り返し二乗法: Python の pow は C 実装のバイナリ法 なので追加実装は不要です。
3. hashlib.sha256 で KDF: 生の \(g^{ab}\) をそのまま鍵に使わず、SHA-256 で正規化することで \(\mathbb{Z}_p^*\) 内の偏り (位数 \(q\) の部分群に閉じる) や整数長の不均一を吸収します。
4. sympy.primitive_root は小さな \(p\) 用です。2048 bit の本格運用では、Safe Prime に対し \(g=2\) が原始根になることが多く、明示的に固定パラメータ (RFC 3526) を使うのが標準です。

gmpy2 による高速化

\(p\) が 2048 bit を超えると CPython の pow でも体感できる程度に遅くなります。gmpy2.powmod は GMP ライブラリの mpz 演算を呼ぶため、大きな指数で数倍〜十数倍速くなります。

import gmpy2
import secrets

p = gmpy2.mpz("FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" ...)  # RFC 3526 group 14
g = gmpy2.mpz(2)

a = gmpy2.mpz(secrets.randbits(256))
A = gmpy2.powmod(g, a, p)
# ... 以下同様

実用ライブラリ (cryptography.hazmat)

実運用では自前実装ではなく、検証済みライブラリ (cryptography, PyNaCl, OpenSSL) を使うべきです。Python では cryptography.hazmat.primitives.asymmetric.dh が標準的です。

from cryptography.hazmat.primitives.asymmetric import dh
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

# 2048 bit の Safe Prime を含む DH パラメータ生成 (RFC 7919 推奨)
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Alice の鍵ペア
alice_private = parameters.generate_private_key()
alice_public = alice_private.public_key()

# Bob の鍵ペア
bob_private = parameters.generate_private_key()
bob_public = bob_private.public_key()

# 共通鍵 (生の DH 出力)
alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)
assert alice_shared == bob_shared

# HKDF-SHA256 で 32 byte セッション鍵を導出
session_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b"handshake data",
).derive(alice_shared)

cryptography は exchange() 内部で公開鍵の妥当性検証 (部分群攻撃のチェック、\(1, p-1\) の排除など) を自動で行います。自前実装ではこの検証を忘れがちで、これだけで本番運用に踏み切る理由になります。

DH vs RSA vs ECDH の比較

3 方式の特徴を整理します。

ECDH は同じセキュリティ強度を桁違いに短い鍵長で達成できるため、現在の TLS / Signal / WireGuard では ECDH (特に X25519) が標準です。一方で、楕円曲線の実装は手元で書くと脆弱になりがちで、\(\mathbb{Z}_p^*\) 上の DH に比べて検証が難しいというトレードオフがあります。

なお、楕円曲線版の ElGamal 暗号については楕円曲線 ElGamal 暗号を参照してください。基礎版の DH 鍵交換はDiffie-Hellman 鍵交換プロトコル：理論と Python 実装にもまとめてあります。

派生プロトコル

DH の枠組みは数十年にわたって拡張され続けています。

ECDH (楕円曲線 Diffie-Hellman)

有限体 \(\mathbb{Z}_p^*\) の代わりに楕円曲線 \(E(\mathbb{F}_p)\) の有理点群を使います。DH における冪乗 \(g^a\) がスカラ倍 \(aG\) に置き換わり、ECDLP の困難性に依拠します。同じ強度に対して鍵が短く、TLS 1.3 では secp256r1 / secp384r1 / x25519 が標準曲線です。楕円曲線の数学（点加算・スカラー倍算・ECDLP）と Python 実装の詳細は楕円曲線暗号（ECC）の数学と Python 実装を参照してください。

X25519 / X448 (Curve25519 系)

Daniel J. Bernstein が設計した Montgomery 曲線 Curve25519 上の ECDH を X25519 と呼びます。設計の特徴は次の通りです。

• クランプ処理: 秘密鍵の特定ビットを固定して低位部分群攻撃を完全に排除。
• 定数時間性: スカラ倍を定数時間で実装でき、サイドチャネル攻撃に強い。
• 公開鍵が一律 32 byte: シリアライズが単純で実装ミスの余地が少ない。

X25519 は OpenSSH、TLS 1.3、Signal、WireGuard、Tor v3 など、現代プロトコルのほぼ全てで採用されています。X448 はより高い強度 (224 bit) が必要な場面用です。

Triple DH (3DH) / X3DH

Signal Protocol で使われる非同期な認証付き鍵交換です。受信者がオフラインでも初回メッセージを送れるよう、3 個 (X3DH では 4 個) の DH 出力を連結して鍵を導出します。

ここで \(IK\) は長期 ID 鍵、\(SPK\) は署名済み prekey、\(OPK\) は使い捨て prekey、\(EK\) は揮発的鍵です。X3DH の後段に Double Ratchet を接続することで、E2E 暗号メッセンジャの安全性が成立します。

ハイブリッド DH (PQC 移行)

量子計算機の登場に備えて、古典 ECDH と耐量子鍵カプセル化機構 (CRYSTALS-Kyber 等) を併用するハイブリッド鍵交換が TLS 1.3 で議論されています。両方が破られない限り安全という設計で、Cloudflare や Google が 2023 年から実験運用を始めています。

まとめ

DH 鍵交換は半世紀にわたり公開鍵暗号の中心であり続け、TLS / SSH / Signal といった現代インフラの安全性を支えています。本記事の要点は次の通りです。

• 共通鍵 \(K = g^{ab} \bmod p\) が指数の可換性で成立する、エレガントな構造。
• 安全性は離散対数問題 と CDH/DDH 仮定に依拠する。
• Safe Prime \(p = 2q+1\) と原始根の選択で部分群攻撃を防ぐ。
• MITM 対策には RSA や ECDSA 署名による認証が必須で、DH 単体では使わない。
• 実装は繰り返し二乗法 を内部で使い、pow(g, a, p) や gmpy2.powmod で高速化できる。
• 本番では cryptography.hazmat の dh モジュールを使い、HKDF-SHA256 で鍵を導出する。
• 現代のデファクトは ECDH、特に X25519 で、量子時代に向けてハイブリッド方式へ移行中。

DH を完全に理解するには、隣接領域 (RSA, ElGamal, 楕円曲線, KDF, PKI) を縦横に行き来する必要があります。次に学ぶ題材は暗号技術ロードマップから選んでください。

関連記事

• RSA 暗号の理論・鍵生成・暗号化・復号を Python 実装 - 同じ公開鍵暗号の枠組みで、素因数分解問題に依拠する代表的方式。
• Diffie-Hellman 鍵交換プロトコル：理論と Python 実装 - 基礎版の DH 解説。前方秘匿性の入門に。
• 繰り返し二乗法による高速べき乗剰余計算の Python 実装 - DH/RSA の根幹を支える \(O(\log k)\) 指数計算アルゴリズム。
• 楕円曲線暗号（ECC）の数学と Python 実装 - ECDH / X25519 の数学的基盤。点加算・スカラー倍算・ECDLP・主要曲線比較を詳解。
• 楕円曲線 ElGamal 暗号の原理と Python による簡易実装 - 楕円曲線上の DLP に基づく公開鍵暗号。ECDH の隣接領域。
• 暗号技術ロードマップ：DLP・素因数分解・楕円曲線から PQC まで - 暗号領域全体の俯瞰。
• OAuth 2.0/OIDC 入門 - DH/RSA を用いた認証認可プロトコルの実例。
• ゼロトラストセキュリティの概要と導入 - DH/PKI を組織レベルのセキュリティ設計にどう組み込むか。
• セキュリティ資格比較：CISSP vs 情報処理安全確保支援士 - 暗号技術を含むセキュリティ資格の比較。

関連ツール

• ハッシュ生成ツール (DevToolBox) - SHA-256 / SHA-512 などの鍵導出に使えるハッシュ計算
• 進数変換ツール (CalcBox) - 大きな整数を 16 進表記に変換し DH パラメータを確認

参考文献

• Diffie, W., & Hellman, M. (1976). “New Directions in Cryptography”. IEEE Transactions on Information Theory, 22(6), 644–654.
• Kivinen, T., & Kojo, M. (2003). “More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE)”. RFC 3526.
• Gillmor, D. K. (2016). “Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS”. RFC 7919.
• Adrian, D., et al. (2015). “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (Logjam attack). CCS 2015.
• Bernstein, D. J. (2006). “Curve25519: new Diffie-Hellman speed records”. PKC 2006.
• Marlinspike, M., & Perrin, T. (2016). “The X3DH Key Agreement Protocol”. Signal Foundation.