鍵交換(Diffie–Hellman)

実装: crypto/dh/ / 実行: go test ./crypto/dh/

対称暗号は速いが、同じ鍵を両者が持たねばならない。その鍵をどう配るか。会ったこともない相手に、盗聴されている通信路で共有鍵を渡す。Diffie–Hellmanはこれを解く。剰余べき乗g^a mod pは簡単だが逆算は難しい。この一方向性を使い、互いの公開値を自分の秘密でべき乗すると、二人だけがg^(ab)にたどり着く。鍵交換を自作し、素のDHが中間者攻撃に無力で、相手の認証が要ることまで示す。

この章で作るもの

対称暗号は速くて本文の暗号化に向くが、弱点がある。暗号化と復号が同じ鍵なので、その鍵を両者が事前に共有していなければならない。では鍵をどう配るか。手渡しできる相手ならいいが、初めて通信する相手に、しかも盗聴されているかもしれない通信路で、共有鍵を渡さねばならないことがほとんどだ。鍵を平文で送れば盗聴者に筒抜けだ。かといって鍵を暗号化するには、その暗号化のための鍵がまた要る。堂々巡りに見える。

Diffie–Hellman 鍵交換は、この鍵配布問題を鮮やかに解く。鍵そのものを一度も通信路に流さずに、両者が同じ共有秘密にたどり着く。仕掛けは剰余べき乗の一方向性だ。g^a mod p の計算は速いが、その結果と g・p を知っても、指数 a を逆算する(離散対数を解く)のは p が十分大きいと現実的な時間では解けない。Alice は秘密 a から g^a を、Bob は秘密 b から g^b を、それぞれ公開する。あとは互いの公開値を自分の秘密でべき乗するだけで、二人とも g^(ab) mod p という同じ値に着く。

       Alice(秘密 a)                Bob(秘密 b)
公開 →  A = g^a mod p  ──────────→   A を受け取る
        B を受け取る   ←──────────   B = g^b mod p  ← 公開
共有 →  B^a = g^(ab)                 A^b = g^(ab)   ← 同じ!
       盗聴者は g^a と g^b は見えるが、a も b も分からない → g^(ab) を作れない

Diffie–Hellman。秘密 a・b は手元に置いたまま、公開値 g^a・g^b だけを交換する。互いの公開値を自分の秘密でべき乗すると、両者が g^(ab) に一致する

順に見ていく。

剰余べき乗の一方向性: g^a mod p は速いが逆算は難しい。この非対称が鍵交換を成り立たせる
公開値だけ交換する: 秘密 a・b は手元に残す。通信路を流れるのは g^a・g^b だけで、共有鍵は一度も流れない
素の DH は認証がない: 相手が本当に Bob かは確かめていない。間に割り込む中間者には無力で、認証が別に要る

① 剰余べき乗: 速い計算と難しい逆算

まず土台の g^a mod p を作る。素朴に a 回掛けると、a が巨大なとき(実物は数百ビット)終わらない。二乗法を使う。指数のビットを下から見て、1 のビットで結果に現在の底を掛け、毎回底を二乗する。これで指数のビット数ぶんの掛け算に減る:


// Rand は決定的な擬似乱数源(テスト再現性のため実乱数を使わない)。
type Rand struct{ state uint64 }

// NewRand は seed から擬似乱数源を作る。
func NewRand(seed uint64) *Rand { return &Rand{state: seed*2862933555777941757 + 1} }

func (r *Rand) next() uint64 {
	r.state = r.state*6364136223846793005 + 1442695040888963407
	return r.state >> 11
}

// ModExp は base^exp mod mod を二乗と乗算の繰り返しで計算する。
// 指数のビットを下から見て、1 のビットで結果に現在の底を掛け、毎回底を二乗する。
// 指数が巨大でもビット数ぶんの掛け算で済む(素朴に exp 回掛けるのとは桁違い)。
func ModExp(base, exp, mod *big.Int) *big.Int {
	result := big.NewInt(1)
	b := new(big.Int).Mod(base, mod)
	e := new(big.Int).Set(exp)
	for e.Sign() > 0 {
		if e.Bit(0) == 1 {
			result.Mul(result, b)
			result.Mod(result, mod)
		}
		b.Mul(b, b)
		b.Mod(b, mod)
		e.Rsh(e, 1)
	}
	return result
}

テストで 5^3 mod 23 = 10 などの既知の値と、x^0 = 1 を固定した。ここで大事なのは計算の非対称性だ。g^a mod p はこの二乗法で一瞬で出る。だが逆に、g・p・g^a mod p を全部知っていても、a を求める効率的な方法は知られていない。p が大きいほど、総当たり以外の手がなくなる。この「順は速く逆は絶望的」という差が、次の鍵交換の安全性そのものになる。

② 鍵交換: 秘密を送らずに共有する

鍵交換の本体はごく短い。秘密鍵を無作為に選んで公開鍵を作る Generate と、相手の公開鍵を自分の秘密でべき乗する Shared だけだ:


// Params は共有する公開パラメータ。素数 P と生成元 G。
type Params struct {
	P *big.Int // 大きな素数(法)
	G *big.Int // 生成元
}

// Generate は秘密鍵 priv を無作為に選び、公開鍵 pub = G^priv mod P を返す。
// priv は決して送らない。pub だけを相手に渡す。
func (pr Params) Generate(r *Rand) (priv, pub *big.Int) {
	// priv を [2, P-2] から選ぶ。
	span := new(big.Int).Sub(pr.P, big.NewInt(3))
	priv = new(big.Int).SetUint64(r.next())
	priv.Mod(priv, span)
	priv.Add(priv, big.NewInt(2))
	pub = ModExp(pr.G, priv, pr.P)
	return priv, pub
}

// Shared は相手の公開鍵 otherPub を自分の秘密鍵 priv でべき乗し、共有秘密を導く。
// Alice が Shared(a, B)、Bob が Shared(b, A) を計算すると、どちらも G^(ab) mod P。
func (pr Params) Shared(priv, otherPub *big.Int) *big.Int {
	return ModExp(otherPub, priv, pr.P)
}

Alice が Shared(a, B) を計算すると B^a = (g^b)^a = g^(ab)。Bob が Shared(b, A) を計算すると A^b = (g^a)^b = g^(ab)。べき乗の順番が違うだけで、着く先は同じだ。テストで、公開鍵だけを交換した Alice と Bob が同じ共有秘密に到達すること、その秘密がどちらの公開鍵とも違うこと(秘密が実際に混ざっていること)を固定した。盗聴者は g^a と g^b を手に入れても、g^(ab) を作るには a か b が要る。テストで、公開値を掛けたり足したりべき乗したりといった素朴な合成では、どれも共有秘密に一致しないことも確かめた。

③ 素のDHはなりすましに弱い: 中間者攻撃

ここに大きな落とし穴がある。DH は盗聴者(通信を傍受するだけの受動的攻撃者)には強い。だが、通信路に割り込んで書き換えられる能動的攻撃者(中間者、MITM)には無力だ。Alice が「Bob の公開鍵」として受け取ったものが、本当に Bob のものである保証がどこにもないからだ。

間に Mallory がいるとする。Alice が送った A を Mallory が横取りし、自分の M を Bob へ渡す。Bob が送った B も横取りし、M を Alice へ渡す。Alice は M を Bob の公開鍵だと信じて g^(am) を共有秘密にする。Bob も M を Alice のものと信じて g^(bm) を使う。Mallory は両方の鍵を自分で計算できるので、Alice からの暗号文を復号して読み、書き換えて Bob へ再暗号化して中継できる。二人は Mallory の存在に気づかない。テストで、Alice と Bob が実は同じ鍵を共有していないこと、Mallory が両者それぞれと鍵を共有していることを固定した。

対策は、公開鍵が本当にその相手のものだと確かめること、つまり認証だ。相手の公開鍵に署名を付けて本人性を保証する。これが証明書であり、後の TLS ハンドシェイクの章で、証明書で相手を認証してから DH を行う形を作る。鍵交換と認証は別の問題で、両方揃って初めて安全になる。

動かす

下のデモは Alice と Bob の鍵交換を追う。互いの公開鍵から同じ共有秘密が導かれる様子を見て、次に中間者 Mallory を割り込ませると、二人の共有鍵が食い違い、Mallory が両方を握る様子が見える。

デモDiffie–Hellman 鍵交換共有秘密が一致

正常な鍵交換中間者(MITM)

公開パラメータ: p = 2147483647, g = 5

Alice

秘密 a = 60001

公開 A = g^a = 97853509

共有 B^a = 1936412795

Bob

秘密 b = 150007

公開 B = g^b = 1989498438

共有 A^b = 1936412795

両者の共有秘密が一致 → g^(ab) mod p。この鍵は通信路を流れていない

Alice は Bob の公開鍵を自分の秘密でべき乗し(B^a)、Bob は A^b を計算する。どちらも g^(ab) mod p に着き、共有秘密が一致する。この鍵は一度も通信路を流れていない

剰余べき乗を BigInt で実際に計算している。g^a mod p は速く計算できるが、結果から a を逆算する (離散対数)のは p が大きいと解けない。この一方向性で、秘密を送らずに共有秘密を作る。ただし素の DH は相手が本物かを確かめない。中間者には無力で、証明書などの認証と組み合わせて初めて安全になる。

設計の観点

鍵交換 ≠ 認証: DH は共有秘密を作るだけ。相手が誰かは保証しない。認証(証明書・署名)と必ずセットで使う
前方秘匿性(forward secrecy): 交換ごとに使い捨ての秘密鍵を使う(ephemeral、DHE/ECDHE)と、後で長期鍵が漏れても過去の通信は復号されない。TLS 1.3 はこれを必須にした
群の選び方: 弱い素数や小さな群は攻撃される。実運用は名前付きの安全な群(RFC 7919)か、楕円曲線(X25519)を使う。パラメータを自作しない
楕円曲線 DH(ECDH): 同じ発想を楕円曲線上で行うと、はるかに短い鍵で同等の強度になる。現代の主流
中間者を防ぐ現実の層: 証明書と認証局(CA)、証明書の検証。鍵交換の安全は、この認証基盤に支えられている

対照と実例

方式	鍵配布	速度	用途
事前共有鍵	手渡し等が必要	速い	閉じた系・少数の相手
RSA 鍵輸送	公開鍵で鍵を暗号化して送る	中	旧 TLS。前方秘匿性なし
DH / DHE	公開値の交換で共有	中	鍵交換の基本形
ECDH / X25519	楕円曲線で交換	速い(短い鍵)	現代の主流(TLS 1.3)

裏どり:

New Directions in Cryptography (Diffie & Hellman, 1976): 公開鍵暗号と鍵交換の概念を打ち立てた原典
TLS 1.3: RSA 鍵輸送を廃し、(EC)DHE による前方秘匿性を必須にした。この章の DH が実運用でどう使われるかの到達点
X25519 (Curve25519): 現代の標準的な鍵交換。実装が安全側に倒しやすく、広く使われる
Logjam 攻撃: 弱い・共通の DH パラメータを突いた実際の攻撃。群の選び方が安全性に直結することの実例

簡略化したこと

小さな素数: 教科書用に 2^31-1 など。実物は 2048bit 以上、または楕円曲線
静的パラメータ: P・G を固定。実物は名前付き群や X25519
鍵導出関数なし: 共有秘密をそのまま扱う。実物は KDF に通して対称鍵にする
前方秘匿性は概念のみ: 使い捨て鍵(ephemeral)の運用は設計の観点で述べるに留めた

参考資料

New Directions in Cryptography (Diffie–Hellman) — 鍵交換の原典
RFC 7919: Negotiated FFDHE Parameters — 安全な DH 群の標準
X25519 (RFC 7748) — 現代の楕円曲線鍵交換
実装: crypto/dh

鍵交換(Diffie–Hellman) ​

この章で作るもの ​

① 剰余べき乗: 速い計算と難しい逆算 ​

② 鍵交換: 秘密を送らずに共有する ​

③ 素のDHはなりすましに弱い: 中間者攻撃 ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​