秘密鍵の背後にある数学（第1回/全2回）

楕円曲線は暗号技術のあちこちに登場する。何年も避けてきたが、Ethereumのロールアップアーキテクチャを調べているうちに、ついに立ち止まって実際に何が起きているのかを理解することにした。驚いたのは、すべてが群論の上に成り立っているということだ。大学で学んで、現実と無関係に思えてすぐに忘れてしまった、あの抽象代数だ。とんでもない思い違いだった。

この記事を読み終える頃には、公開鍵と秘密鍵の背後にある核心的な数学が理解できるだろう。楕円曲線からどう構築されるのか、そしてなぜその構築が安全なのか。第2回では、この数学が実際にどう応用されるかを扱う。

体：算術を備えた数の集合

ラッセルのパラドックについての記事で、集合とは何かを説明した。体とは、二項演算である加法と乗法を備え、9つの公理を満たす集合 $F$ のことだ。各演算に4つずつ、さらに両者をつなぐ分配法則で1つ。「二項」とは、各演算が2つの要素を取り、同じ集合から1つの要素を返すという意味だ。

$$+: F \times F \to F$$ $$\cdot: F \times F \to F$$

公理の例を2つ挙げる（完全なリストは付録を参照）。

• 結合法則：$(a + b) + c = a + (b + c)$
• 乗法の逆元：$\forall a \neq 0,\ \exists\ a^{-1}$ であって $a \cdot a^{-1} = 1$

実は、体は線形代数、微積分、その他の学部数学を支えるのに必要な最小限の構造だ。実数 $\mathbb{R}$ は体を成す。有理数 $\mathbb{Q}$ も同様だ。しかし整数 $\mathbb{Z}$ は違う。$2 \cdot n = 1$ を満たす整数 $n$ は存在しない。2の乗法逆元は $\frac{1}{2}$ だが、これは $\mathbb{Z}$ に含まれない。

暗号技術では有限体がよく使われる。Ethereumのsecp256k1曲線は $\mathbb{F}_p$ 上で動作する。

$$\mathbb{F}_p = \lbrace 0, 1, 2, \ldots, p-1 \rbrace$$

ここで $p$ は大きな素数（$p \approx 2^{256}$）だ。算術は $p$ を法として行われる。$p = 7$ を小さな例として使うと、

• $5 + 4 = 9 \equiv 2 \pmod{7}$
• $3 \cdot 5 = 15 \equiv 1 \pmod{7}$（つまり $3$ と $5$ は $\mathbb{F}_7$ で乗法逆元の関係にある）

なぜ $p$ は素数でなければならないのか。$p = 6$ だと $2 \cdot 3 \equiv 0$ になる。もし $2$ に逆元 $2^{-1}$ があれば、両辺に掛けて $2^{-1} \cdot 2 \cdot 3 = 2^{-1} \cdot 0$、つまり $3 = 0$ となり、矛盾する。したがって $2$ には乗法逆元がなく、体の公理が満たされない。素数ならこの問題を回避できる。

群：体より単純な構造

群は体より単純な構造だ。二項演算が2つではなく1つ、公理が9つではなく4つ。群は $(G, \circ)$ と書く。$G$ は集合、$\circ$ は演算（加法、乗法、合成など何でもよい）だ。

4つの公理は次の通り。

1. 閉包性：$\forall a, b \in G:\ a \circ b \in G$
2. 結合法則：$(a \circ b) \circ c = a \circ (b \circ c)$
3. 単位元：$\exists\ e \in G$ であって $e \circ a = a \circ e = a$
4. 逆元：$\forall a \in G,\ \exists\ a^{-1} \in G$ であって $a \circ a^{-1} = a^{-1} \circ a = e$

公理は $G$ が何を含むか、$\circ$ が何をするかを指定しない。群一般について何かを証明すれば、それはすべての群に当てはまる。整数でも、対称性でも、曲線上の点でも。

例：$(\mathbb{Z}, +)$（加法に関する整数）

• 閉包性：$3 + 5 = 8 \in \mathbb{Z}$
• 結合法則：$(2 + 3) + 4 = 2 + (3 + 4) = 9$
• 単位元：$e = 0\ $（1ではない！）
• 逆元：$a^{-1} = -a$（$a + (-a) = 0$ だから）

楕円曲線は群である

体 $\mathbb{F}_p$ 上の楕円曲線とは、次を満たす点 $(x, y)$ の集合だ。

$$y^2 = x^3 + ax + b$$

これに特別な無限遠点 $\mathcal{O}$ を加える。定数 $a, b \in \mathbb{F}_p$ が曲線の形状を決める。

この集合は点の加算と呼ばれる二項演算の下で群を成す。この構成は恣意的に見えるかもしれないが、まさにこれが群の公理を満たすのに必要な定義だ。仕組みはこうだ。

1. $P$ と $Q$ を通る直線を求める（つまり $y = mx + c$ の傾き $m$ と切片 $c$ を解く）。$P = Q$ の場合は $P$ での接線を使う。
2. この直線は曲線とちょうど3点で交わる（重複度を数える。接線は2回分）。3番目の交点 $R$ を求める。
3. 結果を計算する。
   • $R$ が有限点の場合：x軸に関して反転し、$P + Q = -R$ を得る。ここで $-R = (x, -y)$。
   • 直線が垂直の場合：有限の3番目の交点がない。結果は無限遠点 $\mathcal{O}$ になる。

もう1つのルール：任意の点 $P$ について $P + \mathcal{O} = P$。無限遠点は単位元として機能する。

群の公理の検証：

• 閉包性：点の加算は常に曲線上の別の点（または $\mathcal{O}$）を与える
• 結合法則：成り立つ（証明は非自明）
• 単位元：上で定義した $\mathcal{O}$
• 逆元：$(x, y)$ の逆元は $(x, -y)$（和が $\mathcal{O}$ になるから）

なぜ暗号学者が注目するのか

これで群ができた。楕円曲線上の点、加算演算、4つの公理が満たされている。しかし群は数学のあらゆるところにある。この群が暗号に役立つのはなぜか。

答えは非対称性にある。この群上のある操作は計算が簡単だが、逆方向は事実上不可能だ。これを理解するには、もう1つの概念が必要だ。

スカラー倍は加算の繰り返しだ。群演算があるので、繰り返し適用できる。$nP$ は $P$ を $n$ 回足すことを意味する。

$$nP = \underbrace{P + P + \cdots + P}_{n \text{ 回}}$$

暗号のセキュリティには大きな数が必要だ。Ethereumは $n \approx 2^{256}$（78桁の数）を使う。素朴に $nP$ を計算すると $n - 1$ 回の加算が必要で、これは不可能だ。

しかし、どんな整数も二進表現を持つ。$n = 13$ を例にとると、

$$13 = 1101_2 = 8 + 4 + 1$$

したがって $13P = 8P + 4P + P$。重要な洞察は $8P = 2(4P) = 2(2(2P))$ だ。$2P$、$4P$、$8P$ を繰り返し倍算で計算し（3回の演算）、関連する項を足す（さらに2回）。合計：12回ではなく5回の演算。

これがダブル・アンド・アッド（double-and-add）だ。任意の $n$ に対して $O(\log n)$ 回の演算で済み、$n$ のビット数程度だ。$n \approx 2^{256}$ でも、約256回の倍算と加算で済む。高速だ。

逆方向は難しい。 $P$ と $Q = nP$ が与えられたとき、$n$ を求めるのが離散対数問題（DLP）だ。「対数」は $b^n = x \Rightarrow n = \log_b(x)$ との類推から。「離散」は有限群だから。

総当たりより大幅に速いアルゴリズムは知られていない。$n \approx 2^{256}$ では、これは実行不可能だ。

この非対称性こそが公開鍵暗号に必要なものだ。 各曲線仕様には、全員が使う標準的な基点 $P$（ジェネレーターとも呼ばれる）が含まれている。

• 秘密の整数 $n$ を選ぶ。これが秘密鍵。
• $Q = nP$ を計算する。これが公開鍵。
• $Q$ を公開する。署名や暗号化のプロトコルはこの鍵ペアの上に構築される。
• あなたになりすますには、攻撃者は $Q$ と $P$ から $n$ を復元しなければならない。しかしそれはDLPであり、実行不可能だ。

これが楕円曲線暗号の核心だ。実際の実装にはさらなる層がある。Ethereumは公開鍵をハッシュしてアドレスを導出し、ECDSAのような署名方式には追加のステップがある。しかし、そのすべてのセキュリティはDLPの困難さに依存している。

まとめ

多くの内容を扱った。体は有限空間での算術を与える。群はより単純な構造（1つの演算、4つの公理）で、あらゆるところに現れる。楕円曲線は点の加算の下で群を成し、これらの曲線上の離散対数問題は秘密鍵を守るのに十分難しい。

構成はエレガントだ。秘密の数 $n$ を選び、既知の点 $P$ をそれで掛け、結果 $Q = nP$ を公開する。誰でも $Q$ を使って検証できるが、$n$ を復元するのは計算上は手の届かないところにある。第2回では、この基盤が2つの実用的なプロトコルをどう可能にするかを見る。鍵交換のためのECDHと、デジタル署名のためのECDSAだ。

付録：体の公理