1. はじめに
この記事は、前編の続きとして、楕円曲線暗号（ECC）と楕円曲線署名（ECDSA）をPythonを使って実装する。
前編では、
- 楕円曲線の定義
- 有限体
- 点の加算と2倍算
- スカラー倍算と離散対数問題
を数学的に説明した。
ここでは、それらを実際に実装していく。
楕円曲線暗号は次の式で定義される。
$$
E: y^2 = x^3 + ax + b
$$
この楕円曲線は有限体 $\mathbb{F}_{p}$ 上で定義されるため、計算結果は素数 $p$ で余りを取る必要がある。
1.1. 群としての楕円曲線
定義される加算は、楕円曲線上での特別な単位元（$=$ 無限遠点と呼ばれ $O_{\infty}$ とあらわす）を使って、次のような法則が成り立つ。
- 結合法則：$(P_1 + P_2) + P_3 = P_1 + (P_2 + P_3)$
- 単位元の存在：$P + O_{\infty} = O_{\infty} + P = P$
- 逆元の存在：$P + (-P) = (-P) + P = O_{\infty}$
- 交換法則：$P + Q = Q + P$
1.2. スカラー倍算
ある整数 $m (\ge 1)$ に対して、楕円曲線上の点 $P$ に対して、次のように定義される。
$$
mP = \underbrace{P + P + \cdots + P}_{m \ 回 \phantom{}}
$$
$m = 0$ のときは次のように定義される。
$$
mP = 0 \times P = O_{\infty}
$$
$m < 0$ のときは $|m|$ 個の $(-P)$ の加算として考える。
$$
mP = \underbrace{(-P + (-P) + \cdots + (-P)}_{m \ 回 \phantom{}}
$$
2. 楕円曲線を実装する
楕円曲線暗号を Python を用いて実装する。構成は3つのクラスからなる。
- 有限体の演算（
Fieldクラス） - 楕円曲線（
EllipticCurveクラス） - 有限体上の点（
Pointクラス）
Field クラスでは有限体上の演算や逆元計算を実装し、EllipticCurve クラスで曲線のパラメータを管理し、Point クラスで楕円曲線上の点とその加算・スカラー倍算を実装する。
また、一部のメソッドは今回の実装では使用しないが、楕円曲線を数学的に正しい構造で扱うために定義している。
2.1. 有限体の演算（Field クラス）
Field クラスは、素数 $p$ を法とする有限体 $\mathbb{F}_{p}$ の演算を行う。加算、減算、乗算は計算後に法 $p$ で余りを取ったものを返す。逆元は、$x \ne 0$ に対してフェルマーの小定理から、
$$
x^{-1} \equiv x^{p-2} \pmod{p}
$$
が成り立つため、pow(x, p-2, p) により計算を行っている。
Python による実装を次に示す。
class Field:
def __init__(self, p: int):
self.p = p # 法 p
def add(self, x: int, y: int) -> int:
return (x + y) % self.p
def sub(self, x: int, y: int) -> int:
return (x - y) % self.p
def mul(self, x: int, y: int) -> int:
return (x * y) % self.p
def inv(self, x: int) -> int:
return pow(x, self.p - 2, self.p)
2.2. 楕円曲線（EllipticCurve クラス）
EllipticCurve クラスは楕円曲線
$$
E: y^2 = x^3 + ax + b \pmod{p}
$$
のパラメータを保持する役割を持つ。係数 $a, b$ と計算を行う有限体の法 $p$ を管理し、同時に有限体演算を扱う Field インスタンスも内部に持つ。
このクラスは曲線そのものの定義を行い、この後に説明する Point クラスは必ずこの曲線上の点として扱われる。
また、単位元である無限遠点 $O$ を返すための infinity() メソッドも持つ。
Python による実装を次に示す。
class EllipticCurve:
def __init__(self, a: int, b: int, p: int):
self.a = a
self.b = b
self.field = Field(p)
@property
def p(self) -> int:
return self.field.p
def infinity(self) -> "Point":
# 無限遠点 O を返す
return Point(None, None, self)
2.3. 有限体上の点（Point クラス）
Point クラスは、楕円曲線上の点とその演算を表す。どの曲線上の点であるかを示す curve を持ち、無限遠点は x = None として表している。
楕円曲線の加算は、点を結ぶ直線が曲線と交わる3つ目の点を利用する操作で、それを有限体上の計算に落とし込んだものが __add__ と double() である。
-
__add__：異なる2点の加算 -
double()：同じ点を2倍する操作
これにより、コードでは通常の演算と同じように $P + Q$ と書くだけで楕円曲線上の加算が実行できる。
Python による実装を次に示す。
from dataclasses import dataclass
@dataclass(frozen=True)
class Point:
x: int | None
y: int | None
curve: "EllipticCurve"
def is_infinity(self) -> bool:
return self.x is None
def __neg__(self) -> "Point":
if self.is_infinity():
return self
p = self.curve.field.p
return Point(self.x, (-self.y) % p, self.curve)
def __add__(self, other) -> "Point":
E = self.curve
F = self.curve.field
P = self
Q = other
# 単位元処理
if P.is_infinity():
return Q
if Q.is_infinity():
return P
# P + (-P) = O
if P.x == Q.x and (P.y + Q.y) % F.p == 0:
return E.infinity()
# 2倍算
if (self.x, self.y) == (other.x, other.y):
return self.double()
# 通常加算
lam = (self.y - other.y) * F.inv(self.x - other.x) % F.p
x3 = (lam ** 2 - self.x - other.x) % F.p
y3 = (lam * (self.x - x3) - self.y) % F.p
return __class__(x3, y3, E)
def double(self) -> "Point":
E = self.curve
F = self.curve.field
P = self
# 無限遠点
if P.is_infinity():
return P
p = F.p
# 接続が垂直 => O
if P.y % p == 0:
return E.infinity()
lam = (3 * P.x * P.x + E.a) * F.inv(2 * P.y) % p
x3 = (lam * lam - 2 * P.x) % p
y3 = (lam * (P.x - x3) - P.y) % p
return __class__(x3, y3, E)
def __rmul__(self, k) -> "Point":
E = self.curve
R = E.infinity()
P = self
# k が負の場合は -k * (-P)
if k < 0:
return (-self).__rmul__(-k)
# k = 0 => O
if k == 0:
return R
# k > 0
while k > 0:
if k & 1:
R = R + P
P = P.double()
k >>= 1
return R
3. 楕円曲線暗号と署名
前編では、楕円曲線の加算やスカラー倍算など、ECC の数学的な土台を解説した。
ここでは、その数学的構造を使って
- 楕円曲線ディフィー・ヘルマン鍵共有（ECDH、以下楕円曲線鍵共有）
- 楕円曲線署名（ECDSA）
の実装を行う。
3.1. 楕円曲線鍵共有（ECDH）
楕円曲線鍵共有（ECDH）は暗号化方式ではなく、通信路上で安全に鍵を配送する仕組みである。このとき配送される鍵は AES などの共通鍵暗号にそのまま利用できる。
ここでは、楕円曲線上の生成点 $G$ を使って、Alice と Bob が安全に共有鍵を作る手順をシミュレーションする。
実装の際に使用するパラメータは、ECDH と ECDSA で異なるものを使用する。
具体的には、鍵共有（ECDH）には広く標準化されている SECP256R1（P-256） を用い、署名（ECDSA）では Bitcoin で採用されている secp256k1 を利用する。
3.1.1. ECDH手順
楕円曲線 Diffie-Hellman では、まず公開してよいパラメータとして、次の3つをあらかじめ定義している。
- 使用する楕円曲線 $E$
- 生成点 $G$
- $G$ の位数 $n$
これらは secp256k1 のように標準化されている場合が多い。
Alice は秘密にする整数 $a$ をランダム（$1 \le a \le n - 1$）に選び、楕円曲線上で $A = aG$ を計算する。これが Alice の公開鍵となる。同じように Bob も秘密整数 $b$ （$1 \le b \le n - 1$）を選び、$B = bG$ を計算して公開鍵として送る。
公開鍵を交換した後、Alice は Bob の公開鍵 $B$ に対して、
$$
aB = a(bG)
$$
を計算し、Bob は Alice の公開鍵 $A$ に対して
$$
bA = b(aG)
$$
を計算する。楕円曲線上の演算は可換であるため、どちらも同じ点 $(ab)G$ となり、これが共有の秘密点となる。
外部から見ることができるのは、
- 生成点 $G$
- Alice の公開鍵 $A = aG$
- Bob の公開鍵 $B = bG$
の3点のみである。
そのため、秘密点 $(ab)G$ を計算するには、公開鍵から $a$ や $b$ を取り出す必要があるがそのためには離散対数問題を解く必要がある。
しかし適切なパラメータのもとでは現実的な時間で解くことが不可能と考えられているので、Alice と Bob のみが同じ共有の秘密点に到達できるとされている。
3.1.2. ECDH の Python 実装
ここでは、2章で実装したコードを用いて、鍵配送の流れを操作する。
ここではパラメーターは次のように定義している。
import random
import hashlib
# SECP256R1 (P-256) のパラメータ
# 1. 素数 p (曲線の有限体を定義)
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
# 2. 曲線 y^2 = x^3 + ax + b の係数 a, b
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC # (p - 3)
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
# 3. 生成点 G = (Gx, Gy)
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
# 4. Gの位数 n (秘密鍵の最大値)
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
Python で実装したコードを次に示す。
# 1. 楕円曲線 E とベースポイント G をインスタンス化
E = EllipticCurve(a, b, p)
G = Point(Gx, Gy, E)
print("--- 鍵共有プロセス開始 ---")
# 2. アリスの鍵ペア生成
d_A = random.randint(1, n - 1)
P_A = d_A * G
print(f"アリスの秘密鍵 d_A : {d_A:x}")
print(f"アリスの公開鍵 P_A : {P_A.x:x}")
print()
# 3. ボブの鍵ペア生成
d_B = random.randint(1, n - 1)
P_B = d_B * G
print(f"ボブの公開鍵 d_B : {d_B:x}")
print(f"ボブの公開鍵 P_B : {P_B.x:x}")
print()
print("--- 公開鍵の交換と共有秘密の計算 ---")
# 4. アリスが共有秘密を計算
S_A = d_A * P_B
print(f"アリスが計算した共有秘密 : S_A = {S_A.x:x}")
# 5. ボブが共有秘密を計算
S_B = d_B * P_A
print(f"ボブが計算した共有秘密 : S_B = {S_B.x:x}")
print()
# 6. 結果の検査用
if S_A == S_B:
print("アリスとボブは同じ共有秘密 S を取得しました。")
else:
print("共有秘密が一致しません。")
実行結果を次に示す。
--- 鍵共有プロセス開始 ---
アリスの秘密鍵 d_A : 4ad241392c65fc3703deaacb4b56cefe0db4de61d39207c6660fbc6a1439c6d6
アリスの公開鍵 P_A : 40aa825c89b93619dddcff6214bc82306f872b694fbb13e175a625ed10c0c494
ボブの公開鍵 d_B : 680e5d676ed7a5ab996b2e17898c4d6325eb3031af7d03d67ace7421e87e167f
ボブの公開鍵 P_B : 3422432d242bbe56e7d2581c2ff09179491a3cd08030a6ac15563ec058cda033
--- 公開鍵の交換と共有秘密の計算 ---
アリスが計算した共有秘密 : S_A = ce75173bd7b6d01dd963326ae080c65bc034fb06d9b31a7b80a3607f596554af
ボブが計算した共有秘密 : S_B = ce75173bd7b6d01dd963326ae080c65bc034fb06d9b31a7b80a3607f596554af
アリスとボブは同じ共有秘密 S を取得しました。
3.2. 楕円曲線署名（ECDSA）
ここでは、楕円曲線を用いた電子署名方式である ECDSA を実装し、署名の生成と検証の一連の流れを示す。ECDH が「鍵の共有」を目的とするのに対し、ECDSA は「メッセージが正しい送信者によって生成されたことを証明する」ための仕組みである。
楕円曲線署名では、楕円曲線のパラメータに加えて、ハッシュ関数（ここでは SHA-256）を利用する。メッセージをハッシュ化して整数に変換した後、秘密鍵を用いることで署名を生成し、公開鍵を用いて署名の正当性を検証する。
3.2.1. 署名の仕組み
署名は3つのステップから構成されている。
(1). 署名鍵と検証鍵の準備
(2). 署名の生成
(3). 署名の検証
署名鍵と検証鍵の準備では、ECDH と同様に、秘密鍵 $d$ をランダムに選び、公開鍵として
$$
P = dG
$$
を計算する。
署名の生成では、メッセージ $M$ を SHA-256 により整数 $z$ に変換した後、ランダムな整数 $k$ を選び、次の手順で署名のペア $(r, s)$ を計算する。
\left\{
\begin{aligned}
R &= kG \\
r &= R_{x} \bmod n \\
s &= k^{-1}(z + rd)\bmod n
\end{aligned}
\right.
署名の検証では、公開鍵 $P$、メッセージのハッシュ値 $z$ 、署名（$r, s$）を使って、次の点
$$
u_1G + u_2P
$$
を計算し、その $x$ 座標が $r$ と一致すれば署名が正しい。ここで、
$$
u_1 = zs^{-1} \mod{n}, \quad u_2 = rs^{-1} \mod{n}
$$
である。
3.2.2. ECDSA の実装（Python）
ここでは、2章で実装した楕円曲線クラスを使って、署名生成と署名検証を実装する。楕円曲線のパラメータには、Bitcoin で標準として使われている secp256k1 を用いる。
構成は次の2つのクラスからなる。
- PrivateKey
- PublicKey
PrivateKeyはメッセージに署名を行い、PublicKeyは署名を検証するためのクラスである。
Python による PrivateKey クラスの実装を次に示す。
import hashlib
import random
class PrivateKey:
def __init__(self, d: int, G: "Point", n: int):
self.d = d
self.G = G
self.n = n
self.public_key = self.d * self.G
def inv(self, x):
return pow(x, self.n - 2, self.n)
def sign(self, message: str) -> tuple[int, int]:
message_bytes = message.encode('utf-8')
# 1. メッセージのハッシュ値を取得
z = int.from_bytes(hashlib.sha256(message_bytes).digest(), "big")
# 2. 一時的な秘密鍵 k の生成と署名rの計算
while True:
k = self.generate_k()
R = k * self.G
r = R.x % self.n
if r != 0:
break
# 3. 署名sの計算
k_inv = self.inv(k)
s = k_inv * (z + r * self.d) % self.n
if s == 0:
return self.sign(message)
return (r, s)
def generate_k(self):
return random.randint(1, self.n - 1)
Python による PublicKey クラスの実装を次に示す。
class PublicKey:
def __init__(self, G: "Point", P: "Point", n: int):
self.G = G
self.public_key = P
self.n = n
def inv(self, x):
return pow(x, self.n - 2, self.n)
def verify(self, message: str, signature: tuple[int, int]) -> bool:
r, s = signature
message_bytes = message.encode('utf-8')
# 1. メッセージのハッシュ値を計算
z = int.from_bytes(hashlib.sha256(message_bytes).digest(), "big")
# 2. w の計算（s の n を法とするモジュラ逆算）
w = self.inv(s)
# 3. u1, u2 の計算
u1 = z * w % self.n
u2 = r * w % self.n
# 4. 点Xの計算
X = (u1 * self.G) + (u2 * self.public_key)
if X.is_infinity():
return False
# 5. 計算した点Xのx座標を法nの下で取り出す
x1 = X.x % self.n
return x1 == r
Python による検証コードを次に示す。
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
"""
Alice が署名を行い、Bob が検証を行う
"""
# --- 公開情報 ---
E = EllipticCurve(a, b, p)
G = Point(Gx, Gy, E)
""" Aliceによる署名 """
# --- 秘密鍵 da を生成 ---
da = random.randint(1, n - 1)
message = "Hello ECDSA with my own ECC!"
# --- 鍵ペア作成 ---
priv = PrivateKey(da, G, n)
pub = PublicKey(G, priv.public_key, n)
# --- 署名 ---
sig = priv.sign(message)
print("秘密鍵 d =", hex(priv.d))
print("公開鍵 Px =", hex(priv.public_key.x))
print("公開鍵 Py =", hex(priv.public_key.y))
print("署名 (r, s) =", sig)
""" Bobによる検証 """
# --- 検証 ---
ok = pub.verify(message, sig)
print("署名検証:", ok)
コードの実行結果を次に示す。
秘密鍵 d = 0xce1b84a3ea048429807554c46cb25c28716a1336c35bdaf66938610013b11fb1
公開鍵 Px = 0x6b527d78e43fc272039ac332b159a64d1697f485f2647d9137ad3febc85c6788
公開鍵 Py = 0xe61486b8654c5db7126d2aa5659821725109d13ea03f82765a97feb2caa37002
署名 (r, s) = (75988856702777085006085150083563409835091394405822062527572561461725637561989, 107946780550039443978896391751879916585209383848670946430062585171853215856821)
署名検証: True
結果から署名と検証が正しく動作したことがわかる。
4. まとめ
この記事では、ECC の数学的構造の上に、
- 点の加算と2倍算
- スカラー倍算
- 鍵共有（ECDH）
- 署名と検証（ECDSA）
を Python で実装した。
5. 参考資料
[1]. secp256k1
[2]. Pythonで学ぶ暗号理論