楕円曲線暗号（ECC）の数学と Python 実装：有限体上の点加算・ECDLP・ECDH・ECDSA・X25519 まで解説

なぜ楕円曲線暗号を学ぶか

楕円曲線暗号 (Elliptic Curve Cryptography; ECC) は、1985 年に Neal Koblitz と Victor Miller が独立に提案した公開鍵暗号の枠組みです。RSA 暗号 が素因数分解、Diffie-Hellman 鍵交換 が有限体上の離散対数問題に依拠するのに対し、ECC は楕円曲線上の離散対数問題 (ECDLP) の困難性に依拠します。ECDLP には準指数時間アルゴリズムが知られていないため、256 bit の鍵で 3072 bit RSA と同等の安全性を達成でき、計算量・帯域・メモリのすべてで有利です。

この効率性ゆえに、現代インフラの公開鍵暗号はほぼ ECC に置き換わりました。TLS 1.3 の鍵交換は ECDHE (X25519 / P-256) が事実上の標準、Bitcoin / Ethereum の署名は secp256k1 上の ECDSA、SSH / Signal / WireGuard は X25519 と Ed25519 を採用しています。一方で、楕円曲線の数学は RSA や DH に比べて一段抽象的で、「点を足す」「点を整数倍する」という演算のイメージが掴みにくいのも事実です。

本記事では、Weierstrass 形式の定義から点加算の幾何学、ECDLP、主要曲線の比較、ECDH / ECDSA のプロトコルまでを数式で整理し、Python で (1) フルスクラッチの点演算、(2) cryptography.hazmat による実用 ECDH / ECDSA、(3) X25519 の 3 段階を実装します。暗号領域全体の俯瞰は暗号技術ロードマップを参照してください。

楕円曲線の定義

標数が 2, 3 でない体 \(K\) 上の楕円曲線は、Weierstrass 形式 (short Weierstrass form) と呼ばれる方程式

を満たす点 \((x, y)\) の集合に、無限遠点 \(\mathcal{O}\) を加えたものとして定義されます。ただし曲線が特異点 (尖点や自己交差) を持たないために、判別式

が必要です。\(\Delta = 0\) だと \(x^3 + ax + b\) が重根を持ち、後述の群構造が壊れるため暗号には使えません。

暗号で使うのは実数上の曲線ではなく、素数 \(p\) に対する有限体 \(\mathbb{F}_p\) 上の曲線 \(E(\mathbb{F}_p)\) です。点の個数 \(\#E(\mathbb{F}_p)\) は Hasse の定理により

の範囲に収まり、おおむね \(p\) と同程度になります。安全な曲線では \(\#E(\mathbb{F}_p) = h \cdot n\) （\(n\) は大きな素数、余因子 \(h\) は 1, 4, 8 程度）となるよう設計されます。

点の加算と 2 倍算

ECC の核心は、「曲線上の 2 点を足すと曲線上の点が返る」という群演算です。幾何学的には弦と接線の方法 (chord-and-tangent method) で定義されます。

• 加算 \(P + Q\) : 相異なる 2 点 \(P, Q\) を通る直線は曲線と第 3 の点で交わる。その点を \(x\) 軸で折り返した点が \(P + Q\) 。
• 2 倍算 \(2P\) : \(P\) での接線が曲線と交わるもう 1 点を \(x\) 軸で折り返した点が \(2P\) 。
• 単位元: 無限遠点 \(\mathcal{O}\) 。\(P + \mathcal{O} = P\) 、\(P + (-P) = \mathcal{O}\) （\(-P\) は \(P\) の \(x\) 軸対称点）。

\(P = (x_1, y_1)\) , \(Q = (x_2, y_2)\) , \(P + Q = (x_3, y_3)\) とすると、直線の傾き \(\lambda\) を使って加算公式は次のようになります。

加算（\(P \neq \pm Q\) ）:

2 倍算（\(P = Q\) , \(y_1 \neq 0\) ）:

有限体 \(\mathbb{F}_p\) 上では「割り算」は \(p\) を法とする逆元の乗算になります。Python では pow(x, -1, p)（内部は拡張ユークリッド互除法）で計算できます。実数上の幾何学的な直感がそのまま \(\bmod p\) の世界に移植される点が、楕円曲線の美しさです。

この演算のもとで \(E(\mathbb{F}_p)\) は可換群 (アーベル群) をなします。結合法則の証明は非自明ですが、暗号への応用ではこの群構造 (特に位数 \(n\) の巡回部分群) を使います。

スカラー倍算と double-and-add

秘密鍵にあたる整数 \(k\) と、ベースポイント \(G\) に対して、

をスカラー倍算と呼びます。\(k\) は 256 bit 級の巨大な整数なので愚直に足すことはできず、double-and-add 法を使って \(O(\log k)\) 回の点演算で計算します。これは繰り返し二乗法（バイナリ法）の加法群版で、対応は次の通りです。

\(k\) を 2 進展開し、ビットを下位から見て「1 なら加算、毎回 2 倍」を繰り返せば、256 bit の \(k\) でも高々 511 回の点演算で済みます。なお、素朴な double-and-add は \(k\) のビットパターンで処理時間が変わるサイドチャネル攻撃の標的になるため、実用実装では Montgomery ladder などの定数時間アルゴリズムが使われます。

楕円曲線離散対数問題 (ECDLP)

ECC の安全性の根拠は、スカラー倍算の逆演算の困難性です。

を楕円曲線離散対数問題 (Elliptic Curve Discrete Logarithm Problem; ECDLP) と呼びます。順方向は \(O(\log k)\) ですが、逆方向に対する既知の最速アルゴリズム (Pollard’s rho) は \(O(\sqrt{n})\) の完全指数時間を要します。有限体の DLP や素因数分解に有効な指数計算法 (index calculus) や数体篩 (NFS) が楕円曲線には適用できないため、同じ安全性をはるかに短い鍵で達成できるのです。

NIST SP 800-57 に基づく等価安全性の比較は次の通りです。

256 bit の ECC 鍵が 3072 bit の RSA 鍵に相当します。鍵長比は安全性を上げるほど開いていき、128 bit 強度で 12 倍、256 bit 強度では 30 倍です。署名サイズ・ハンドシェイク帯域・組み込み機器のメモリで ECC が圧倒的に有利な理由がここにあります。ただし RSA / DH と同様、Shor のアルゴリズムを実行できる量子計算機には ECDLP も破られるため、耐量子暗号 (PQC) への移行が並行して進んでいます（暗号技術ロードマップ 参照）。

主要曲線の比較: P-256 / secp256k1 / Curve25519

実務で遭遇する 3 曲線の特徴を整理します。

• P-256 は TLS 証明書と FIDO2 / WebAuthn のデファクトです。NIST 曲線はパラメータ選定過程の不透明さが批判されることもありますが、既知の脆弱性はありません。
• secp256k1 は \(a = 0\) の Koblitz 曲線で、\(p = 2^{256} - 2^{32} - 977\) という特殊素数により剰余演算が高速です。Satoshi Nakamoto が Bitcoin に採用したことで、ブロックチェーン界の標準になりました。
• Curve25519 は Montgomery 形式を採用し、\(x\) 座標のみの Montgomery ladder で常に定数時間のスカラー倍算ができます。無効曲線攻撃や低位数部分群攻撃を設計レベルで排除しており、「実装者が間違えにくい」ことを最優先した現代的な曲線です。詳細は Diffie-Hellman 記事の X25519 節 も参照してください。

ECDH 鍵交換と ECDSA 署名

ECDH: 楕円曲線 Diffie-Hellman

DH 鍵交換の \(g^a \bmod p\) をスカラー倍算 \(aG\) に置き換えたものが ECDH です。

1. Alice は秘密鍵 \(a \in [1, n-1]\) を選び、公開鍵 \(A = aG\) を送る。
2. Bob は秘密鍵 \(b\) を選び、公開鍵 \(B = bG\) を送る。
3. 両者は共有点を計算する。

スカラー倍算の可換性 \(a(bG) = b(aG)\) により両者は同じ点 \(abG\) に到達し、その \(x\) 座標を HKDF に通してセッション鍵を導出します。盗聴者は \(A = aG\) と \(B = bG\) から \(abG\) を計算できません（ECDH 仮定）。TLS 1.3 では一時鍵を毎回生成する ECDHE として使われ、前方秘匿性を実現します。

ECDSA: 楕円曲線デジタル署名

ECDSA は「秘密鍵の持ち主だけが署名でき、公開鍵で誰でも検証できる」署名方式です。秘密鍵 \(d\) 、公開鍵 \(Q = dG\) 、メッセージハッシュ \(e = H(m)\) とします。

署名生成:

1. 一時乱数 (nonce) \(k \in [1, n-1]\) を選ぶ。
2. \(R = kG\) を計算し、\(r = R_x \bmod n\) （\(r = 0\) ならやり直し）。
3. \(s = k^{-1}(e + rd) \bmod n\) （\(s = 0\) ならやり直し）。署名は \((r, s)\) 。

署名検証:

\(x \bmod n = r\) なら受理します。\(u_1 G + u_2 Q = s^{-1}(e + rd) G = kG = R\) となることから正当性が確認できます。

ECDSA 最大の落とし穴は nonce \(k\) の再利用・偏りです。同じ \(k\) で 2 つのメッセージに署名すると、連立方程式から秘密鍵 \(d\) が即座に復元されます（2010 年の PlayStation 3 の署名鍵漏洩事故が有名）。現代の実装は RFC 6979 の決定的 nonce（\(d\) と \(H(m)\) から HMAC で導出）を使い、この事故を構造的に防ぎます。乱数品質への依存をさらに減らした後継が Ed25519 (EdDSA) です。

Python 実装

1. フルスクラッチ: \(\mathbb{F}_p\) 上の点加算とスカラー倍算

まず外部ライブラリなしで、secp256k1 上の点演算を式 (4), (5) の通りに実装します。逆元は pow(x, -1, p)、スカラー倍算は double-and-add です。

import secrets

# --- secp256k1 のドメインパラメータ ---
p = 2**256 - 2**32 - 977  # 基礎体の素数
a, b = 0, 7               # y^2 = x^3 + 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = (Gx, Gy)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # G の位数

assert (-16 * (4 * a**3 + 27 * b**2)) % p != 0  # 判別式条件 (2)

O = None  # 無限遠点 (単位元)


def ec_add(P, Q):
    """楕円曲線上の点加算: 式 (4), (5) の実装"""
    if P is O:
        return Q
    if Q is O:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O  # P + (-P) = O
    if P == Q:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p  # 接線の傾き
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p  # 弦の傾き
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)


def scalar_mult(k, P):
    """double-and-add による k*P: O(log k) 回の点演算"""
    R, Q = O, P
    while k:
        if k & 1:
            R = ec_add(R, Q)  # ビットが 1 なら加算
        Q = ec_add(Q, Q)      # 毎ステップ 2 倍算
        k >>= 1
    return R


def is_on_curve(P):
    if P is O:
        return True
    x, y = P
    return (y * y - (x**3 + a * x + b)) % p == 0


# --- ECDH デモ ---
alice_priv = secrets.randbelow(n - 1) + 1
bob_priv = secrets.randbelow(n - 1) + 1

alice_pub = scalar_mult(alice_priv, G)  # A = aG
bob_pub = scalar_mult(bob_priv, G)      # B = bG
assert is_on_curve(alice_pub) and is_on_curve(bob_pub)

shared_alice = scalar_mult(alice_priv, bob_pub)  # aB = abG
shared_bob = scalar_mult(bob_priv, alice_pub)    # bA = abG
assert shared_alice == shared_bob

print(f"共有秘密の x 座標: {hex(shared_alice[0])[:18]}...")

ポイントは 3 点です。

1. pow(x, -1, p) で逆元: Python 3.8+ は組み込み pow でモジュラ逆元を計算できます。\(\mathbb{F}_p\) の「割り算」はすべてこれに置き換わります。
2. scalar_mult は繰り返し二乗法と同型: 「2 乗 → 2 倍算」「乗算 → 点加算」に読み替えただけで、コード構造は完全に同じです。
3. この実装は教育用: 処理時間が秘密鍵に依存するためサイドチャネル攻撃に弱く、無効曲線攻撃のチェック (is_on_curve を受信点に必ず適用する等) も最小限です。本番では次の cryptography を使います。

2. 実用ライブラリ: cryptography.hazmat で ECDH / ECDSA

本番コードでは検証済みライブラリの cryptography.hazmat.primitives.asymmetric.ec を使います。曲線は ec.SECP256R1() (P-256) や ec.SECP256K1() を指定するだけです。

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from cryptography.exceptions import InvalidSignature

# --- ECDH (P-256) ---
alice_private = ec.generate_private_key(ec.SECP256R1())
bob_private = ec.generate_private_key(ec.SECP256R1())

alice_shared = alice_private.exchange(ec.ECDH(), bob_private.public_key())
bob_shared = bob_private.exchange(ec.ECDH(), alice_private.public_key())
assert alice_shared == bob_shared

# 生の共有秘密は HKDF-SHA256 でセッション鍵に変換する
session_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b"ecdh handshake",
).derive(alice_shared)
print(f"セッション鍵: {session_key.hex()[:32]}...")

# --- ECDSA (secp256k1) ---
signing_key = ec.generate_private_key(ec.SECP256K1())
message = b"transfer 1 BTC to Bob"

signature = signing_key.sign(message, ec.ECDSA(hashes.SHA256()))

# 検証: 失敗時は InvalidSignature 例外
try:
    signing_key.public_key().verify(signature, message, ec.ECDSA(hashes.SHA256()))
    print("署名は正当")
except InvalidSignature:
    print("署名が不正")

cryptography の exchange() は受信公開鍵が曲線上にあるかを自動検証し、sign() は RFC 6979 系の安全な nonce 生成を内部で処理します。フルスクラッチ実装で踏みがちな地雷 (nonce 再利用、無効曲線攻撃) をライブラリ層で吸収してくれるのが、本番でライブラリを使うべき最大の理由です。

3. X25519: 現代のデファクト鍵交換

TLS 1.3 / SSH / Signal / WireGuard が採用する X25519 は、専用モジュール cryptography.hazmat.primitives.asymmetric.x25519 で使えます。曲線の選択肢すら存在しない、ミニマルな API です。

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

alice_private = X25519PrivateKey.generate()
bob_private = X25519PrivateKey.generate()

alice_shared = alice_private.exchange(bob_private.public_key())
bob_shared = bob_private.exchange(alice_private.public_key())
assert alice_shared == bob_shared

session_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b"x25519 handshake",
).derive(alice_shared)
print(f"X25519 セッション鍵: {session_key.hex()[:32]}...")

X25519 は公開鍵・共有秘密が常に 32 byte 固定で、クランプ処理により低位数部分群攻撃が設計レベルで排除されています。「新規プロトコルの鍵交換は迷わず X25519」が 2026 年現在のベストプラクティスです。署名が必要なら兄弟の Ed25519 (cryptography.hazmat.primitives.asymmetric.ed25519) を使います。

まとめ

• 楕円曲線は Weierstrass 形式 \(y^2 = x^3 + ax + b\) と判別式条件 \(-16(4a^3 + 27b^2) \neq 0\) で定義され、弦と接線の方法で可換群をなす。
• スカラー倍算 \(kG\) は double-and-add で \(O(\log k)\) 回の点演算に落ち、繰り返し二乗法と完全に同型。
• 安全性の根拠は ECDLP で、指数計算法が使えないため 256 bit ECC ≈ 3072 bit RSA の効率を実現する。
• 主要曲線は P-256（TLS / FIDO2）、secp256k1（Bitcoin / Ethereum）、Curve25519（X25519 / Ed25519）で、用途に応じて使い分ける。
• ECDH はスカラー倍算の可換性 \(abG\) 、ECDSA は nonce を使った署名方程式 (9), (10) で成立する。nonce 再利用は秘密鍵漏洩に直結する。
• Python 実装は、学習にはフルスクラッチ（pow(x, -1, p) + double-and-add）、本番には cryptography.hazmat の ec / x25519 モジュールを使う。
• ECC も量子計算機の Shor アルゴリズムには耐えられないため、PQC ハイブリッドへの移行が進行中。全体像は暗号技術ロードマップを参照。

関連記事

• 暗号技術ロードマップ：DLP・素因数分解・楕円曲線から PQC まで - 暗号領域全体の学習マップ。本記事はこのハブの楕円曲線パートを深掘りしたもの。
• Diffie-Hellman 鍵交換の理論と実装 - 有限体版 DH の詳説。ECDH はその楕円曲線版。
• RSA 暗号の理論・鍵生成・暗号化・復号を Python 実装 - 素因数分解に依拠する公開鍵暗号。鍵長比較の相手方。
• 繰り返し二乗法による高速べき乗剰余計算の Python 実装 - double-and-add の乗法群版。スカラー倍算の理解の前提。
• 楕円曲線 ElGamal 暗号の原理と Python による簡易実装 - 楕円曲線上で「暗号化」を行う方式。ECDH / ECDSA の隣接領域。
• Diffie-Hellman 鍵交換プロトコル：理論と Python 実装 - DH の入門記事。前方秘匿性の基礎に。
• OAuth 2.0/OIDC 入門 - ECDSA 署名 (ES256) が JWT で使われる実例。
• ゼロトラストセキュリティの概要と導入 - ECC ベースの PKI / mTLS を組織設計に組み込む文脈。
• セキュリティ資格比較：CISSP vs 情報処理安全確保支援士 - ECC を含む暗号分野が出題されるセキュリティ資格。

関連ツール

• ハッシュ生成ツール (DevToolBox) - ECDSA のメッセージハッシュ H(m) の計算に
• 進数変換ツール (CalcBox) - 曲線パラメータの 16 進表記の確認に

参考文献

• Koblitz, N. (1987). “Elliptic Curve Cryptosystems”. Mathematics of Computation, 48(177), 203–209.
• Miller, V. S. (1986). “Use of Elliptic Curves in Cryptography”. CRYPTO ‘85.
• Bernstein, D. J. (2006). “Curve25519: new Diffie-Hellman speed records”. PKC 2006.
• Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer.
• Pornin, T. (2013). “Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)”. RFC 6979.
• NIST (2020). “Recommendation for Key Management: Part 1 – General”. SP 800-57 Part 1 Rev. 5.
• Certicom Research (2010). “SEC 2: Recommended Elliptic Curve Domain Parameters”. Version 2.0.