楕円曲線暗号（ECC）の原理：点加算・スカラー倍と離散対数問題

ECC が解こうとしている問題

公開鍵暗号 の安全性は、いずれも「一方向は簡単だが、逆方向は計算的に困難」な数学的問題に根ざしています。RSA は「掛けるのは簡単／素因数分解は困難」を使います。**楕円曲線暗号（ECC）**が使うのは、楕円曲線上の点を何度も足す操作です。「足すのは簡単／何回足したかを逆算するのは困難」――この非対称性が、短い鍵で高い安全性を実現します。

本質は、曲線上に基準点 G を固定し、秘密の整数 k（秘密鍵）を選んで k 回足し合わせた点 Q = kG（公開鍵）を公開する点にあります。G と Q を知っても k を求められない――これが後述する ECDLP です。

有限体上の楕円曲線

ECC で使う楕円曲線は、y^2 = x^3 + ax + b という形（ワイエルシュトラス型）で定義されます。実数上ではなめらかな曲線ですが、暗号では座標を素数 p で割った余りの世界、すなわち有限体 GF(p)（mod p）上で考えます。座標が 0 から p-1 の整数だけになるため、点は連続した曲線ではなく離散した点の集まりになります。

曲線が暗号に使える条件として、重複根を持たない（判別式 4a^3 + 27b^2 が 0 でない）必要があります。これを満たすと、曲線上の点全体が、ある特別な点を単位元とする有限のアーベル群を成します。その単位元が**無限遠点 O**で、群演算（点加算）における「ゼロ」の役割を果たします。

点の加算と2倍算

楕円曲線の「足し算」は、通常の数の加算とは別物の幾何学的に定義された演算です。直感的には次のように決まります。

• 異なる2点 P + Q：P と Q を通る直線を引くと、曲線と必ずもう1点で交わる。その交点を x 軸で反転（y の符号を反転）した点が P + Q。
• 同じ点の2倍 2P（2倍算）：P における接線を引き、曲線との別の交点を求め、同様に反転する。
• 特殊ケース：P と -P（y 座標が逆符号）を足すと、直線が垂直になり交点が無限遠に飛ぶ。結果は単位元 O と定める（P + (-P) = O）。

有限体上では「直線」「接線」も mod p の演算で表され、傾き λ を介して座標が計算されます。

# 点加算 P=(x1,y1), Q=(x2,y2) → R=(x3,y3)  すべて mod p
# 異なる2点（x1 != x2）の場合:
lambda = (y2 - y1) * inverse(x2 - x1)   mod p   # 直線の傾き
x3 = lambda^2 - x1 - x2                 mod p
y3 = lambda * (x1 - x3) - y1            mod p

# 2倍算（P == Q）の場合は接線の傾きを使う:
lambda = (3*x1^2 + a) * inverse(2*y1)   mod p

ここで inverse(...) は乗法逆元（mod p での「割り算」）で、拡張ユークリッド互除法で求めます。重要なのは、加算・2倍算がすべて整数の四則演算と mod p に帰着することです。浮動小数点の誤差はなく、結果は厳密に曲線上の点になります。

スカラー倍算：高速に「k 回足す」

公開鍵の計算 Q = kG は、G を k 回足すスカラー倍算です。k は256ビット級（10進で約77桁）にもなるため、素朴に G + G + ... + G と1回ずつ足したのでは k 回＝天文学的な回数になり、現実時間で終わりません。

そこで使うのが**2倍と加算（double-and-add）**です。k を2進展開し、各ビットに対して「2倍する／必要なら G を足す」を繰り返します。これは指数計算の繰り返し2乗法と同じ発想で、計算量は k のビット長に比例（O(log k)）まで激減します。256ビットなら、たかだか数百回程度の点演算で kG に到達します。

# double-and-add: Q = k * G を計算
Q = O                      # 無限遠点（単位元）から開始
for bit in binary(k):      # k の上位ビットから順に
    Q = double(Q)          # まず2倍
    if bit == 1:
        Q = add(Q, G)      # ビットが立っていれば G を足す
return Q

ECDLP：逆算が困難な理由

ここまでで「G と k から Q = kG を求めるのは速い（O(log k)）」とわかりました。問題は逆方向です。G と Q が与えられたとき、Q = kG となる k を求める――これが**楕円曲線離散対数問題（ECDLP）**です。

足し算の世界なので「Q を G で割れば k」と思いがちですが、群上に「割り算」に相当する逆演算は存在しません。点は加算のたびに曲線上を不規則に飛び回り、kG の座標から k の手がかりは得られません。k を総当たりするしかなく、適切に選ばれた曲線では既知の汎用解法（Pollard's rho 等）でも計算量が群の位数の平方根程度かかります。256ビット曲線なら約 2^128 回――現実的に解読不能です。

なぜ RSA より鍵長が短いのか

同じ安全性で ECC の鍵が圧倒的に短いのは、それぞれの問題に対する最良アルゴリズムの効率差に由来します。

RSA が依存する素因数分解には、数体ふるい法（GNFS）という準指数時間の解法があり、鍵長を増やしても解読コストの伸びが比較的緩やかです。一方、適切に選んだ楕円曲線の ECDLP には GNFS のような汎用の準指数アルゴリズムが見つかっていません。最良でも平方根時間（指数時間）しかなく、ビットを増やした分だけ解読コストが急峻に伸びます。結果として、より少ないビット数で同等の強度に達します。

鍵が短いことは単なる節約ではありません。署名・鍵交換の計算が軽く、消費電力・帯域・証明書サイズが小さいため、TLS ハンドシェイクの高速化や、IoT・モバイル端末での実装に直結します。TLS で ECDHE 鍵交換と ECDSA 署名が主流になったのも、この効率が大きな理由です。

Curve25519 と secp256r1 の選定背景

実務で使う曲線は、自作せず標準化された既知の曲線から選びます。広く使われる2つが対照的な背景を持ちます。

• secp256r1（NIST P-256）：NIST が標準化したワイエルシュトラス型曲線。古くから普及し、TLS 証明書や多くの政府・企業システムで採用されています。ただし曲線パラメータの生成過程に検証不能な定数が含まれ、「バックドアがないと証明できない」という不信が指摘されてきました。また実装で定数時間性を保つのが難しく、サイドチャネルに弱い実装が生まれやすい構造です。
• Curve25519：D. Bernstein が設計したモンゴメリ型曲線（鍵交換は X25519）。パラメータが説明可能な根拠で選ばれ（nothing-up-my-sleeve）、高速かつ定数時間実装が容易になるよう設計されています。y 座標を使わず x 座標だけで鍵交換でき、無効な点を渡す攻撃にも頑健です。RFC 7748 で標準化され、TLS 1.3・SSH・Signal などで広く使われます。

まとめ

ECC は、有限体上の楕円曲線が成す群の上で「点を k 回足す」演算を土台にします。点加算・2倍算は mod p の四則演算で定義され、スカラー倍算は double-and-add で O(log k) に高速化されます。安全性は、kG から k を逆算する**楕円曲線離散対数問題（ECDLP）**の困難さに依存し、これに RSA の素因数分解ほど効率的な汎用解法がないため、256ビットで RSA 3072ビット相当の強度を短い鍵で達成します。

実装ではアルゴリズムの強度以上に定数時間性・サイドチャネル耐性が重要で、ここが ECC 運用の勘所です。鍵と署名の基礎は 暗号の基礎、公開鍵を本人と結びつける仕組みは 公開鍵基盤（PKI） を合わせて押さえると、ECC が実システムのどこで効いているかが立体的に見えてきます。