Chapter 17

ディフィー・ヘルマンと楕円曲線暗号

「鍵を共有していない 2 人が、盗聴されている回線だけで秘密を共有できるか?」

常識的には不可能に見える。やりとりは全部聞かれているのだから。 ところが 1976 年、ディフィーとヘルマンはこれができることを示した。 暗号史における最大の転換点である。

そして 1985 年、その仕組みを「\(\bmod p\)の掛け算」から「楕円曲線上の点の足し算」に 移植することで、鍵長を 1/10 に縮められることが分かった。 今日の HTTPS、Signal、Bitcoin、パスキー——すべて楕円曲線で動いている。

1. ディフィー・ヘルマン鍵交換 (DH)

手順

公開パラメータ: 大きな素数\(p\)、その原始根\(g\)（どちらも公開。盗聴者も知っている）

なぜ同じ鍵になるのか

指数法則だけ ✓ 両者とも\(K = g^{ab} \bmod p\)に到達する ∎

なぜ盗聴者に分からないのか

盗聴者が知っているのは\(p, g, A=g^a, B=g^b\)。 \(K = g^{ab}\)を求めるには\(a\)または\(b\)が必要——つまり離散対数問題（15 章）を解く必要がある。

鍵が「回線を流れていない」ことに注目してほしい. 共有された\(K = g^{ab}\)は、どちらの端末でも計算されたが、一度も送信されていない。 送られたのは\(g^a\)と\(g^b\)だけで、そこから\(g^{ab}\)を作るのは（DH 仮定の下で）困難である。

これは物理的な錠前のたとえで説明されることが多い:

1. Alice が箱に手紙を入れ、自分の鍵でかけて送る
2. Bob はさらに自分の鍵をかけて送り返す（2 重ロック）
3. Alice は自分の鍵だけ外して送る
4. Bob が自分の鍵を外すと開く

鍵そのものは一度も相手に渡っていないのに、中身が伝わった。DH はこれを数学でやっている。

中間者攻撃 — DH 単独では防げない

Mallory が Alice と Bob の間に入り、それぞれと別々に DH を実行すると:

• Alice ↔ Mallory で鍵\(K_1\)
• Mallory ↔ Bob で鍵\(K_2\)

Mallory は全通信を復号・再暗号化して中継できる。両者は気づかない。

DH は「秘密の共有」はできるが「相手が誰か」は保証しない. だから実際の TLS では、DH に証明書による認証（18 章）を組み合わせる。 「暗号化されている」と「相手が本物である」は別問題——これはセキュリティ設計の基本である。

前方秘匿性 (Forward Secrecy)

毎回使い捨ての\(a, b\)を使う DH を DHE / ECDHE（E = Ephemeral）という。

長期秘密鍵が将来漏れても、過去の通信は復号できない（使い捨ての秘密は破棄済みだから）。 TLS 1.3 では ECDHE が必須になった。

2. 楕円曲線 — 「点の足し算」で群を作る

定義

体\(K\)上の楕円曲線（標数 2,3 でない場合のワイエルシュトラス形）:

（条件\(4a^3+27b^2\neq0\)は重根を持たないこと = 曲線が特異点を持たないことを保証。）

曲線上の点全体に、無限遠点\(\mathcal{O}\) を加えたものを考える。

加法の定義（幾何的に）

2 点\(P, Q\)に対し:

1. \(P\)と\(Q\)を通る直線を引く
2. その直線は曲線と必ずもう 1 点で交わる（3 次曲線なので交点は 3 つ）
3. その交点を\(x\)軸に関して折り返した点を\(P+Q\)と定める

\(P=Q\)のときは接線を使う（2 倍算）。

なぜこれが「足し算」なのか. 一見すると恣意的な規則だが、 この演算は群の公理をすべて満たす（02 章）:

• 閉性 ✓（交点は必ず曲線上）
• 単位元 ✓（無限遠点\(\mathcal{O}\)）
• 逆元 ✓（\(x\)軸対称の点\(-P\)。\(P + (-P) = \mathcal{O}\)）
• 結合律 ✓（証明は非自明。射影幾何やヤコビアンを使う）
• 可換 ✓（直線の引き方は順序に依らない）

群になっているからこそ、02 章以降の群論の道具（位数、生成元、ラグランジュ）が全部使える。 そして「べき乗」の代わりに「スカラー倍\(kP = P+P+\cdots+P\)」を考えれば、 DH と同じ構造がそのまま成立する。

加法の公式（代数的に）

\(P=(x_1,y_1)\)、\(Q=(x_2,y_2)\)、\(P+Q=(x_3,y_3)\)とすると:

傾き:

座標:

導出（\(x_3\)の式）: 直線\(y = \lambda(x-x_1)+y_1\)を曲線の式に代入:

整理すると\(x\)の 3 次方程式になり、その最高次の係数は 1、\(x^2\)の係数は\(-\lambda^2\)。 解と係数の関係より 3 根の和は\(\lambda^2\)。3 根のうち 2 つは\(x_1, x_2\)（\(P,Q\)の\(x\)座標）なので

これが「もう 1 つの交点」の\(x\)座標。折り返しても\(x\)は変わらないので\(x_3 = x_3'\) ∎

重要: この公式には割り算（\(\lambda\)の分母）が現れる. だから係数を体から取る必要がある——02・03 章で「体でなければ困る」と述べた理由がここでも生きる。 実際には\(\mathrm{GF}(p)\)（\(p\)は 256 ビット程度の素数）や\(\mathrm{GF}(2^m)\)を使い、 割り算は逆元の掛け算（01 章の拡張ユークリッド、または\(a^{p-2}\)）で実行する。

3. 楕円曲線上の離散対数 (ECDLP)

問題

点\(G\)（ベースポイント）と\(Q = kG\)が与えられたとき、\(k\)を求めよ。

• \(k \to kG\): 繰り返し二乗法と同じ「ダブル・アンド・アッド」で\(O(\log k)\)——高速
• \(Q \to k\): 最良でも\(O(\sqrt n)\)（Pollard ρ）——実質不可能

なぜ RSA/DH より鍵が短くて済むのか

15 章で触れた決定的な違い. \(\mathbb{Z}_p^\ast\)上の離散対数には Index Calculus という準指数時間アルゴリズムが効く。 これは「小さな素数の積に分解できる数（滑らかな数）」を集めて連立方程式を作る手法だが、 楕円曲線の点には『素因数分解』に相当する概念が無いため適用できない。

結果として、楕円曲線を攻撃する最良手段は汎用の\(O(\sqrt n)\)アルゴリズムだけ。 安全性\(2^{128}\)を得るには\(n \approx 2^{256}\)、つまり256 ビットで十分。 一方 RSA は Index Calculus 系（GNFS）があるため 3072 ビット必要になる。

4. 楕円曲線暗号の応用

ECDH（鍵交換）

DH の\(g^a\)を\(aG\)に置き換えるだけ:

ECDSA（署名）

署名（秘密鍵\(d\)、メッセージハッシュ\(z\)）:

1. 乱数\(k\)を選び、\((x_1,y_1) = kG\)
2. \(r = x_1 \bmod n\)
3. \(s = k^{-1}(z + rd) \bmod n\)
4. 署名 = \((r,s)\)

検証（公開鍵\(Q = dG\)）:

1. \(u_1 = zs^{-1}\)、\(u_2 = rs^{-1}\)
2. \((x_1,y_1) = u_1G + u_2Q\)
3. \(r \equiv x_1 \bmod n\) なら有効

検証が通る理由:

（\(s = k^{-1}(z+rd)\)より\(z+rd = sk\)。）

ECDSA の乱数\(k\)は絶対に再利用してはいけない. 同じ\(k\)で 2 つのメッセージ\(z_1,z_2\)に署名すると、\(r\)が同じになり:

$$s_1 - s_2 = k^{-1}(z_1-z_2) \Longrightarrow k = \frac{z_1-z_2}{s_1-s_2}$$

\(k\)が分かれば\(d = r^{-1}(sk - z)\)で秘密鍵が完全に露出する。

実際の事故:

• 2010 年、ソニー PlayStation 3: ECDSA の\(k\)を定数にしていたため、 マスター署名鍵が抽出され、任意のソフトが実行可能になった
• 2013 年、Android の Bitcoin ウォレット: 乱数生成器の不具合で\(k\)が衝突し、資金が盗まれた

対策として、\(k\)を秘密鍵とメッセージから決定論的に導出する RFC 6979 や、 設計段階でこの問題を回避した EdDSA (Ed25519) が推奨される。

代表的な曲線

Curve25519 が支持される理由. 設計者 Daniel J. Bernstein が、実装ミスを起こしにくいことを最優先に設計した:

• すべての入力値に対して安全（無効曲線攻撃が起きない）
• 分岐やテーブル参照が不要 → タイミング攻撃に本質的に強い
• パラメータの選定根拠が完全に公開されている（NIST 曲線には「定数の出所が不明」という批判がある）

「理論的に安全」だけでなく「実装しても壊れにくい」ことを設計目標にする—— 現代の暗号設計の重要な潮流である。

5. まとめ