楕円曲線暗号 — 曲線上の足し算が作る、短くて強い鍵

RSA は「大きな数の素因数分解の難しさ」を鍵にしていました。楕円曲線暗号（ECC）は、まったく別の難しさ — 曲線上の点を何回足したか（スカラー倍の逆算）の困難性 — を鍵にします。同じ安全性をはるかに短い鍵で実現できるため、スマホ・IoT・ブロックチェーンの標準になりました。まずは「点の足し算」という不思議な演算から動かして掴みます。

1. 楕円曲線と「点の足し算」

楕円曲線とは y² = x³ + ax + b という形の曲線です（4a³+27b² ≠ 0 で滑らか）。この曲線上の点には、幾何的に定義された足し算を入れられます。ルールはこうです：2点 P, Q を通る直線を引くと、曲線と必ずもう1点 R で交わる。その R をx軸で反転した点を P + Q と定めます。

下のデモで a, b と2点 P, Q を動かしてください。直線 → 第3交点 R → x軸反転 → P+Q、という作図が描かれます。P = Q のとき（チェックON）は直線が接線になり、これが「2P」の計算になります。

曲線上の足し算 — 直線 → 第3交点 → 反転で P+Q を作図

点 P

点 Q

P = Q（接線で 2P）

水色＝曲線、白点＝P と Q、破線＝2点を通る直線（接線）、灰点＝第3交点 R、オレンジ＝反転した P+Q。P と Q が上下対称（同じ x）に来ると直線が垂直になり、和は「無限遠点 O」＝足し算の単位元になる。この足し算の下で、曲線上の点全体は群（グループ）をなす。

λ = (y_Q − y_P)/(x_Q − x_P)， x_R = λ² − x_P − x_Q， y_R = λ(x_P − x_R) − y_P P = Q（二倍算）のときは傾きを λ = (3x_P² + a)/(2y_P) に置き換える（接線の傾き）

2. 有限体の上へ — 整数だけの離散版とスカラー倍

暗号で使うのは、なめらかな実数の曲線ではなく、有限体 F_p 上の曲線です。座標を「mod p の整数」に限定すると、曲線は連続な線ではなく散らばった格子点の集まりになります。足し算のルール（直線と反転）は同じ式のまま mod p で計算します。

ここで鍵になるのがスカラー倍 kG = G + G + … + G（k回）。下のデモで k を動かすと、点 kG が曲線上をまったく予測できない順序で飛び回るのが見えます。この「規則性のなさ」こそが暗号の強さの源です。

有限体上のスカラー倍 kG — 予測不能な軌跡とダブル&アッド

各点は F_p 上の曲線点。色付きの点が G, 2G, …, kG の軌跡で、線は計算順につないだもの。隣り合う倍数がまるで無関係な場所に跳ぶことに注目。右上の計算欄はダブル&アッド法のコスト — 例えば k=13 なら 13回の足し算ではなく、二倍算と加算あわせて5手で kG に到達できる。「kG から k を逆算する」のは、この飛び回りを逆にたどることに等しく、桁が大きいと事実上不可能になる。

POINT — 「掛けるのは速い、割るのは絶望的」という非対称スカラー倍 kG はダブル&アッド法で、k のビット数に比例した手数（約 log₂k 回）で計算できる。逆に、G と Q = kG だけを知って k を求める問題を楕円曲線離散対数問題（ECDLP）と呼び、既知の最良アルゴリズムでも点の個数の平方根（√n）に比例する手数がかかる。256ビットの曲線なら約 2¹²⁸ 回 — 宇宙が終わっても終わらない。RSA の「掛け算は簡単・素因数分解は困難」に対応する、ECC の一方向性がこれだ。

Q = kG （k回の足し算）　⟸ 簡単　／　困難 ⟹　Q, G から k を求める（ECDLP） F_p 上で y² ≡ x³ + ax + b (mod p)。点の個数 n に対し ECDLP は約 √n の手数 — 鍵長 t ビットで安全性 t/2 ビット

3. なぜ鍵が短くて済むのか — RSA との比較

RSA を破る素因数分解には準指数時間の巧妙なアルゴリズム（数体ふるい法）が存在します。一方 ECDLP には、そうした「近道」が今のところ見つかっていません。攻撃コストが鍵長に対して素直に（指数的に）伸びるため、同じ安全性をずっと短い鍵で達成できます。下のスライダーで安全性レベルを変え、必要な鍵長の差を見てください。

同じ安全性に必要な鍵長 — RSA vs ECC

安全性レベル

棒の長さ＝鍵のビット長（同じ横軸スケール）。安全性を上げるほど RSA の鍵は急激に肥大するが、ECC はゆるやかにしか伸びない。128ビット安全性（現在の標準的な目標）では RSA 3072 ビットに対し ECC はわずか 256 ビット — 鍵・署名が小さく、計算も軽い。

項目	RSA-3072	ECC（256ビット曲線）
安全性レベル	約128ビット	約128ビット（同等）
公開鍵サイズ	約384バイト	約32〜64バイト
署名サイズ	約384バイト	約64バイト
鍵生成コスト	重い（大きな素数探し）	軽い（乱数×スカラー倍1回）
署名生成の速さ	遅い	速い
署名検証の速さ	速い（小さな公開指数）	やや遅い
主な採用例	従来のTLS証明書・既存資産	スマホ・IoT・TLS 1.3・ビットコイン/イーサリアム

鍵と署名が小さいことは、通信量・保存領域・電力が限られるスマホや IoT 機器で決定的に効きます。ブロックチェーンが ECC（secp256k1 など）を採用するのも、全取引に署名が付き、それが恒久的にチェーンへ刻まれるため、署名の小ささがそのまま容量とコストの節約になるからです。

4. ECDH と ECDSA — 実運用での使われ方

ECC は魔法の暗号アルゴリズムそのものではなく、「鍵となる難問」を提供する土台です。その上に、用途別のプロトコルが載ります。

ECDH（鍵共有）：DH鍵交換を楕円曲線上で行う版。アリスが aG、ボブが bG を公開し、共有秘密 abG を各自で計算する。TLS 1.3 の鍵交換はこれ（ECDHE）が主役。
ECDSA（電子署名）：電子署名を楕円曲線で実現する版。秘密鍵 d（スカラー）と公開鍵 Q = dG を使い、メッセージのハッシュに署名する。

いずれも「Q = dG から d は求められない（ECDLP）」という一方向性の上に成り立っています。攻撃と防御の章で見た認証（攻撃と防御）と組み合わせて、はじめて安全な通信になります。

一歩先へ — 実装の落とし穴：乱数（ノンス）の再利用 ECDSA は署名ごとに使い捨ての乱数 k（ノンス）を必要とする。この k は毎回ユニークで秘密でなければならない。もし2つの異なるメッセージへの署名で同じ k を使い回すと、2本の署名式が k と秘密鍵 d の連立方程式になり、初等的な計算で秘密鍵 d が丸ごと露出してしまう。過去、家庭用ゲーム機や暗号資産ウォレットで、乱数生成の不備からこの事故が実際に起きた。数学は完璧でも、乱数生成という「土台の土台」が崩れれば鍵は守れない。対策として、メッセージと秘密鍵からノンスを決定的に導く RFC 6979 や、設計段階で誤用を防ぐ EdDSA（Ed25519） が使われる。「乱数を疑え」はサイドチャネルと並ぶ実装暗号の鉄則。

5. まとめと限界

点の足し算：直線と第3交点、x軸反転。曲線上の点は群をなす。
有限体上のスカラー倍：kG はダブル&アッドで高速、逆算（ECDLP）は √n で絶望的。この非対称が鍵。
短くて強い：128ビット安全性が RSA 3072 に対し ECC 256 で済む。スマホ・IoT・ブロックチェーンの標準。
使われ方：ECDH（鍵共有）と ECDSA/EdDSA（署名）。認証と組み合わせて安全になる。

注意 — 量子コンピュータには弱い ECC の安全性は ECDLP の困難性に依存するが、これはショアのアルゴリズムを積んだ大規模な量子コンピュータの前では崩れる — RSA と同様に多項式時間で破られてしまう（むしろ鍵が短いぶん必要な量子ビットは RSA より少ない）。「掛けるのは速く割るのは困難」という一方向性は、量子には通用しない。だから次章では、量子計算でも解けないと期待される新しい難問（格子問題など）に基づく耐量子暗号へ進む。ECC は今日の主役だが、移行の設計はすでに始まっている。