Chapter 17

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

この章の位置づけ. 事前に鍵を共有していない 2 人が、すべて盗聴されている通信路だけを使って、共通の秘密の値を持てるか。やり取りが全部聞かれているので不可能に見えるが、1976 年にディフィーとヘルマンが、それができることを示した。 1985 年には、同じ仕組みを「\(\bmod p\)の掛け算」から「楕円曲線上の点の足し算」に移すと、同じ安全性を保ったまま鍵をずっと短くできる（128 ビット安全なら 3072 ビットから 256 ビットへ）ことが Koblitz と Miller によって示された。 現在の HTTPS、メッセージアプリの Signal、Bitcoin、パスキーなどは楕円曲線暗号を使っている。

この章で使う既出の用語（定義は各リンク先）. \(a \bmod p\)と\(a \equiv b \pmod p\)（01 章 1 節）、逆元と拡張ユークリッド・繰り返し二乗法（01 章）、 群・単位元・逆元・閉性・結合律・位数・生成元・\(\mathbb{Z}_p^\ast\)（02 章 1 節）、体・標数（02 章 3 節）、\(\mathrm{GF}(p)\)（03 章）、\(\mathrm{GF}(2^m)\)（05 章）、形式的微分（11 章 3 節）、 原始根・離散対数問題・Pollard の ρ 法・Index Calculus・鍵長の比較（15 章）、RSA（16 章）、タイミング攻撃（13 章 5 節）、ハッシュ関数・証明書（18 章、この章では名前だけ使う）

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

手順

公開のパラメータは、大きな素数\(p\)と、その原始根\(g\)である。どちらも盗聴者に知られてよい。

\(a, b\)は\(1\)から\(p-2\)の範囲の乱数である。上の図で秘密の値を変えると、両者が同じ\(K\)に到達する様子が表示される。

なぜ同じ鍵になるのか

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

例: \(p = 23\)、\(g = 5\)（5 の位数は 22 で原始根）とする。Alice が\(a = 6\)を選ぶと\(A = 5^6 \bmod 23 = 8\)、Bob が\(b = 15\)を選ぶと\(B = 5^{15} \bmod 23 = 19\)である。 Alice は\(K = 19^6 \bmod 23 = 2\)、Bob は\(K = 8^{15} \bmod 23 = 2\)を計算し、同じ値 2 を得る。通信路を流れたのは 8 と 19 だけである。

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

盗聴者が知っているのは\(p, g, A=g^a, B=g^b\)である。\(A\)から\(a\)を求める離散対数問題（15 章 5 節）が解ければ\(K\)も計算できる。 逆に「\(g^a\)と\(g^b\)から\(g^{ab}\)を求める問題（DH 問題）が解ければ離散対数問題も解ける」ことは一般には証明されていないが、DH 問題も難しいと考えられている（DH 仮定）。

共有した\(K = g^{ab}\)は両方の端末で計算されたが、一度も送信されていない。送られたのは\(g^a\)と\(g^b\)だけである。

絵の具のたとえ（手順の表と対応している）:

1. 全員が公開の色\(g\)を持っている。
2. Alice は秘密の色\(a\)を\(g\)に混ぜた色\(A\)を、Bob は秘密の色\(b\)を\(g\)に混ぜた色\(B\)を送る。送るのはこの 2 つだけである。
3. Alice は受け取った\(B\)に自分の\(a\)を混ぜ、Bob は受け取った\(A\)に自分の\(b\)を混ぜる。どちらも「\(g + a + b\)」の色になる。

盗聴者は\(g, A, B\)を見ているが、混ざった絵の具から\(a\)や\(b\)を分離できないので、\(g + a + b\)を作れない。「混ぜるのは簡単、分けるのは困難」という性質を、DH は「べき乗は簡単、離散対数は困難」で実現している。

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

攻撃者 Mallory が Alice と Bob の間に入り、それぞれと別々に DH を行うと、Alice と Mallory の間で鍵\(K_1\)、Mallory と Bob の間で鍵\(K_2\)が共有される。 Mallory はすべての通信を\(K_1\)で復号して読み、\(K_2\)で暗号化し直して中継できる。Alice と Bob は気づかない。

DH は秘密の共有はできるが、相手が誰かは保証しない。そのため実際の TLS では、DH に証明書による認証（18 章）を組み合わせる。「暗号化されている」ことと「相手が本物である」ことは別の問題である。

前方秘匿性 (Forward Secrecy)

サーバは自分が本物であることを示すために、証明書に対応する秘密鍵を何年も使い続ける。これを長期秘密鍵という（上の\(a, b\)とは別物）。 以前の TLS では、この長期鍵を使って共有鍵を決めていたため、長期鍵が後で漏れると、録音しておいた過去の通信がすべて復号できた。

これに対し、毎回使い捨ての\(a, b\)を乱数で作り、通信が終わったら捨てる DH をDHE / ECDHE（E は Ephemeral、一時的の意）という。長期秘密鍵は相手の認証（署名）にだけ使い、共有鍵\(K\)の計算には関わらない。 したがって長期秘密鍵が将来漏れても、\(K\)を作るのに必要な\(a, b\)はもう残っていないので、過去の通信は復号できない。この性質を前方秘匿性という。TLS 1.3 では DHE / ECDHE による鍵交換が必須になった。

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

定義

体\(F\)（標数が 2 でも 3 でもないもの）の上の楕円曲線を

で定める（ワイエルシュトラス形）。\(a, b\)は\(F\)の要素である。 条件\(4a^3+27b^2\neq0\)は、3 次式\(x^3 + ax + b\)が重根（同じ値の根が 2 つ以上）を持たないための条件である。重根があると、曲線に尖った点や自分自身と交わる点（特異点）ができ、そこでは接線が 1 本に決まらないので、下で定める足し算が壊れる。 標数 2 の体\(\mathrm{GF}(2^m)\)では\(y^2 + xy = x^3 + ax^2 + b\)など別の形の式を使う。この章では標数 2, 3 以外の場合だけを扱う。

曲線上の点\((x, y)\)全体に、無限遠点と呼ぶ特別な点\(\mathcal{O}\)を 1 つ加えた集合を考える。\(\mathcal{O}\)は座標を持たない約束上の点で、すべての垂直な直線（\(x = \)定数）が通る点と考える。下の足し算で、垂直な直線を引いたときの「3 つ目の交点」の役を担い、足し算の 0（単位元）になる。

上の図は、素数\(p\)と\(a, b\)を選ぶと、\(\mathrm{GF}(p)\)上の曲線の点を並べ、1 つの点のスカラー倍（下で定義）がどう動くかを表示する。

足し算の定義（図形的に）

曲線は\(y^2 = \cdots\)の形なので\(x\)軸に関して対称で、\(P = (x, y)\)が曲線上なら\((x, -y)\)も曲線上にある。この点を\(-P\)と書く。

2 点\(P, Q\)に対し、次のように\(P + Q\)を定める。

1. \(P\)と\(Q\)を通る直線を引く。\(P = Q\)のときは\(P\)での接線を引く。
2. その直線は曲線ともう 1 点で交わる。3 次曲線と直線の交点は、重なりも数えてちょうど 3 つだからである。
3. その交点を\(x\)軸に関して折り返した点を\(P+Q\)とする。

\(Q = -P\)のときは直線が垂直になり、曲線上に 3 つ目の交点は無い。この場合は 3 つ目の交点を\(\mathcal{O}\)とみなし、\(P + (-P) = \mathcal{O}\)と定める。\(P = Q\)で\(y = 0\)の点も、接線が垂直なので\(P + P = \mathcal{O}\)である。 また\(P + \mathcal{O} = P\)と定める（\(P\)と\(\mathcal{O}\)を通る「直線」は\(P\)を通る垂直線で、3 つ目の交点は\(-P\)、折り返すと\(P\)になる）。

群になること: この足し算は群の条件（02 章 1 節）をすべて満たす。

• 閉性: 下の公式のとおり、3 つ目の交点の座標は\(F\)の要素の四則演算で求まり、曲線上の点になる。
• 単位元: 無限遠点\(\mathcal{O}\)。
• 逆元: \(x\)軸について対称な点\(-P\)。\(P + (-P) = \mathcal{O}\)。
• 結合律: \((P+Q)+R = P+(Q+R)\)。下の公式で両辺を展開すれば確かめられるが、長い計算になるのでここでは事実として使う。
• 可換: \(P\)と\(Q\)を通る直線は順番によらないので\(P + Q = Q + P\)。

群になっているので、02 章以降の群の道具（位数、生成元、ラグランジュの定理）がすべて使える。べき乗\(g^a\)の代わりにスカラー倍\(kP = P+P+\cdots+P\)（\(k\)個）を考えれば、DH と同じ仕組みがそのまま作れる。

足し算の公式（計算で）

\(P=(x_1,y_1)\)、\(Q=(x_2,y_2)\)、\(P+Q=(x_3,y_3)\)とし、\(Q \neq -P\)とする。直線の傾きを

とすると

である。接線の傾きは、実数なら曲線の式の両辺を\(x\)で微分した\(2y \dfrac{dy}{dx} = 3x^2 + a\)から得られる。有限体では極限は使えないが、11 章 3 節の形式的微分と同じく、この式をそのまま接線の傾きの定義として使う。

方針: 直線の式を曲線の式に代入すると\(x\)の 3 次方程式になり、その 3 つの根が 3 つの交点の\(x\)座標である。3 根の和は\(x^2\)の係数から読み取れる。

導出（\(x_3\)の式）: \(P\)を通る傾き\(\lambda\)の直線\(y = \lambda(x-x_1)+y_1\)を曲線の式に代入すると

左辺を展開すると\(\lambda^2 x^2 + (x \text{ の 1 次以下の項})\)なので、右辺に移して整理すると

という\(x\)の 3 次方程式になる。\(x^2\)の項は左辺の\(\lambda^2 x^2\)からしか出ない。 3 次方程式\(x^3 + c_2 x^2 + c_1 x + c_0 = 0\)の 3 根を\(r_1, r_2, r_3\)とすると、\((x - r_1)(x - r_2)(x - r_3)\)を展開して\(x^2\)の係数を比べることで\(r_1 + r_2 + r_3 = -c_2\)が分かる（解と係数の関係）。 いまの方程式の 3 根は直線と曲線の 3 つの交点の\(x\)座標で、そのうち 2 つは\(P, Q\)の\(x_1, x_2\)である（\(P = Q\)なら接点なので\(x_1\)が 2 回数えられる）。3 つ目を\(x_3\)とおくと

\(x\)軸で折り返しても\(x\)座標は変わらないので、これが\(P+Q\)の\(x\)座標である。3 つ目の交点の\(y\)座標は直線の式から\(\lambda(x_3 - x_1) + y_1\)で、折り返して符号を反転したものが\(y_3 = \lambda(x_1 - x_3) - y_1\)である ∎

この公式には割り算（\(\lambda\)の分母）が現れるので、係数を体から取る必要がある。実際には\(\mathrm{GF}(p)\)（\(p\)は 256 ビット程度の素数）や\(\mathrm{GF}(2^m)\)を使い、割り算は逆元を掛けること（01 章の拡張ユークリッド、または\(a^{-1} = a^{p-2}\)）で行う。

例: GF(17) 上の曲線

\(p = 17\)、\(y^2 = x^3 + 2x + 2\)（\(4 \cdot 8 + 27 \cdot 4 = 140 \not\equiv 0 \pmod{17}\)）を考える。\(G = (5, 1)\)は\(5^3 + 2 \cdot 5 + 2 = 137 = 8 \times 17 + 1\)、\(1^2 = 1\)なので曲線上の点である。以下の計算はすべて\(\bmod 17\)で行う。

\(2G = G + G\): 接線の傾きは\(\lambda = (3 \cdot 5^2 + 2)/(2 \cdot 1) = 77/2\)である。\(77 \equiv 9\)、\(2^{-1} \equiv 9\)（\(2 \times 9 = 18 \equiv 1\)）なので\(\lambda = 9 \times 9 = 81 \equiv 13\)。

より\(2G = (6, 3)\)。

\(3G = 2G + G\): \((6,3)\)と\((5,1)\)を通る直線の傾きは\(\lambda = (1 - 3)/(5 - 6) = (-2)/(-1) = 2\)。

より\(3G = (10, 6)\)。

同じ計算を続けると、\(G\)のスカラー倍は次のようになる。

\(19G = \mathcal{O}\)で、\(G\)の位数は 19 である。この曲線の点は無限遠点を含めて 19 個なので、\(G\)のスカラー倍ですべての点が現れる。\(18G = (5, 16) = -G\)になっていることも確かめられる。

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

問題

曲線上の点\(G\)（ベースポイント）を 1 つ決める。\(G\)の位数、すなわち\(nG = \mathcal{O}\)となる最小の\(n\)を\(n\)と書く。曲線を設計するときに、\(n\)が大きな素数になるように選ぶ。\(G\)のスカラー倍は\(G, 2G, \dots, nG = \mathcal{O}\)の\(n\)個を巡る。

ECDLP: \(G\)と\(Q = kG\)（\(1 \le k < n\)）が与えられたとき、\(k\)を求める問題。

• \(k\)から\(kG\): 繰り返し二乗法と同じ要領で、\(k\)の 2 進表現に沿って「2 倍する」と「\(G\)を足す」を繰り返す（ダブル・アンド・アッド）。点の演算は\(O(\log k)\)回で済む。
• \(Q\)から\(k\): 最良の方法でも約\(\sqrt n\)回の点の演算が必要である（Pollard の ρ 法）。\(n \approx 2^{256}\)なら\(2^{128}\)回で、現実には不可能である。

2 節の例では\(n = 19\)なので、\(Q = (0, 6)\)を見て表を引けば\(k = 7\)が分かる。\(n\)が\(2^{256}\)程度になると、この表を作ることはできない。

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

\(\mathbb{Z}_p^\ast\)の離散対数問題には Index Calculus という準指数時間の方法が使える（15 章 5 節）。これは、小さな素数の積に分解できる数（滑らかな数）を集めて連立方程式を作る方法である。 楕円曲線の点には「小さな素数の積に分解する」に当たる操作が無く、一般の楕円曲線では同じような準指数時間の方法は知られていない。攻撃の最良の手段は、どの群にも使える\(O(\sqrt n)\)の方法だけである。

したがって安全性\(2^{128}\)を得るには\(n \approx 2^{256}\)、つまり 256 ビットで十分である。一方 RSA には GNFS という準指数時間の攻撃があるので、3072 ビットが必要になる。 ただし特殊な性質を持つ曲線には効率のよい攻撃が知られているものもあるので、実際には安全性が検証された標準の曲線（4 節）を使う。

4. 楕円曲線暗号の応用

ECDH（鍵交換）

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

例（2 節の曲線、\(G = (5, 1)\)、\(n = 19\)）: \(d_A = 3\)なら\(Q_A = 3G = (10, 6)\)、\(d_B = 7\)なら\(Q_B = 7G = (0, 6)\)である。 Alice は\(3Q_B = 21G\)、Bob は\(7Q_A = 21G\)を計算する。\(21 \equiv 2 \pmod{19}\)なので、どちらも\(2G = (6, 3)\)になる。

ECDSA（署名）

署名する対象は、メッセージをハッシュ関数（任意の長さのデータを決まった長さの値に変換する関数、18 章）で\(n\)未満の整数にした値\(z\)である。 以下の計算はすべて\(\bmod n\)で行い、\(k^{-1}, s^{-1}\)は法\(n\)での逆元である。小文字の\(k\)は署名ごとに選ぶ乱数で、1 節の共有鍵\(K\)とは別物である。

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

1. 乱数\(k\)（\(1 \le k < n\)）を選び、\((x_1,y_1) = kG\)を計算する。
2. \(r = x_1 \bmod n\)とする。
3. \(s = k^{-1}(z + rd) \bmod n\)とする。
4. 署名は\((r,s)\)である（\(r = 0\)や\(s = 0\)になったら\(k\)を選び直す）。

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

1. \(u_1 = z s^{-1} \bmod n\)、\(u_2 = r s^{-1} \bmod n\)を計算する。
2. \((x_1,y_1) = u_1G + u_2Q\)を計算する。
3. \(x_1 \bmod n = r\)なら署名は有効である。

検証が通る理由: \(s = k^{-1}(z+rd)\)より\(z+rd = sk\)なので

となり、署名のときと同じ点\(kG\)が得られる ∎

例（\(n = 19\)）: 秘密鍵\(d = 7\)、公開鍵\(Q = 7G = (0, 6)\)とする。\(z = 10\)に、乱数\(k = 5\)で署名する。

• \(5G = (9, 16)\)なので\(r = 9\)。\(5^{-1} \equiv 4\)（\(5 \times 4 = 20 \equiv 1\)）なので\(s = 4 \times (10 + 9 \times 7) = 4 \times 73 = 292 \equiv 7\)。署名は\((9, 7)\)。
• 検証: \(7^{-1} \equiv 11\)（\(77 = 4 \times 19 + 1\)）なので\(u_1 = 10 \times 11 = 110 \equiv 15\)、\(u_2 = 9 \times 11 = 99 \equiv 4\)。\(15G + 4Q = 15G + 28G = 43G = 5G = (9, 16)\)で、\(x\)座標 9 が\(r\)と一致する。

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

で\(k\)が分かる。\(k\)が分かれば\(d = r^{-1}(sk - z)\)で秘密鍵がそのまま求まる。 上の例で、同じ\(k = 5\)を使って\(z_2 = 4\)にも署名すると\(s_2 = 4 \times (4 + 63) = 268 \equiv 2\)になる。攻撃者は\(k = (10 - 4)/(7 - 2) = 6 \times 5^{-1} = 6 \times 4 = 24 \equiv 5\)、\(d = 9^{-1}(7 \times 5 - 10) = 17 \times 25 \equiv 7\)と、秘密鍵を計算できてしまう。

実際の事故:

• 2010 年、ソニー PlayStation 3: ECDSA の\(k\)を固定値にしていたため、ソフトウェアに署名するための秘密鍵が計算され、任意のソフトが実行できるようになった。
• 2013 年、Android の Bitcoin ウォレット: 乱数生成器の不具合で\(k\)が重複し、資金が盗まれた。

対策として、\(k\)を秘密鍵とメッセージから決定的に計算するRFC 6979や、この問題が起きないように設計されたEdDSA（Ed25519）が推奨されている。

代表的な曲線

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

• 入力の検査が不要: 相手が曲線上に無い点を送ってきたとき、検査せずに計算すると別の弱い曲線の上で計算したことになり、秘密鍵が漏れる無効曲線攻撃がある。Curve25519 の鍵交換は\(x\)座標だけで計算するので、曲線上に無い\(x\)は「ツイスト」と呼ばれる別の曲線上の計算になるが、そのツイストも安全になるようにパラメータが選ばれている。
• 処理時間が一定: 秘密の値による分岐や表の参照が要らない計算方法を使うので、タイミング攻撃に強い。
• パラメータの選び方が公開されている: NIST の曲線には、定数の選び方の根拠が不明だという批判がある。

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

5. まとめ