第4章楕円曲線暗号

この章の目標

• 有限体上の楕円曲線の加法公式とハッセの定理を使って、小さい曲線で点の計算と群の位数の見積もりができる
• 楕円曲線の離散対数問題に汎用的な攻撃しか知られていないことから、鍵が RSA より短くてすむ理由を説明できる
• ECDH・ECDSA・EdDSA の手順を述べ、正しさを証明できる
• ナンスの再利用・漏洩・偏りから秘密鍵が求まることを証明し、決定的なナンスの意味を説明できる
• 公開鍵の検証を怠ったときの無効曲線攻撃・小部分群攻撃と、余因子の役割を説明できる
• 安全な曲線の条件と、秘密に依存しない（定数時間の）実装の考え方を説明できる

前提：第2章、第3章、04-algebra 第2章。楕円曲線の群法則とハッセの定理は 21 第2章・21 第4章 の結果を証明なしで引用する。4.9 節では有限体 $\mathbb{F}_{p^k}$（04-algebra 第8章）を使う。

TLS 1.3 の規格 RFC 8446 は、用途ごとの別の定めがない限り、実装は鍵共有に楕円曲線 P-256 を使えなければならず（MUST）、X25519 にも対応すべき（SHOULD）としている。ビットコインの取引の署名には secp256k1 という曲線の上の ECDSA が使われ、米国の署名規格 FIPS 186-5（2023 年）が承認する 3 つの署名方式のうち 2 つ（ECDSA と EdDSA）は楕円曲線を使う。楕円曲線暗号が広く使われる理由は、第3章で見たとおり、同じ安全性を RSA よりずっと短い鍵で実現できることにある。

一方で、楕円曲線暗号は数学的には正しいのに実装で破れることが多い。署名のたびに選ぶ乱数（ナンス）を 2 回使えば秘密鍵が計算され、受け取った点が曲線上にあるかを確かめなければ秘密鍵が少しずつ漏れる。本章では、ECDH・ECDSA・EdDSA の手順とその正しさを証明したうえで、こうした落とし穴がなぜ鍵の漏洩につながるのかを数学で説明する。攻撃が成り立つ理由の数学的な詳細（MOV 帰着、アノマラス曲線、点の個数の計算など）は 21 第5章 で扱う。

4.1 有限体上の楕円曲線

$p > 3$ を素数、$A, B \in \mathbb{F}_p$ を $4A^3 + 27B^2 \neq 0$ をみたす元とし、

とおく。$O$ は無限遠点である。条件 $4A^3 + 27B^2 \neq 0$ は、右辺の 3 次式が重根をもたない（曲線が特異点をもたない）ことを表す。

定理 4.1（群法則と加法公式）$E(\mathbb{F}_p)$ は $O$ を単位元とするアーベル群であり、$(x, y)$ の逆元は $(x, -y)$ である。$P_1 = (x_1, y_1)$, $P_2 = (x_2, y_2)$ について、$x_1 = x_2$ かつ $y_1 = -y_2$ なら $P_1 + P_2 = O$、そうでなければ

$$\lambda = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1} & (x_1 \neq x_2) \\[2ex] \dfrac{3x_1^2 + A}{2y_1} & (P_1 = P_2) \end{cases}, \qquad x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1$$

として $P_1 + P_2 = (x_3, y_3)$ である。

（主張のみ。$\lambda$ は 2 点を通る直線または接線の傾きで、直線と曲線の 3 つ目の交点を $x$ 軸について折り返したものが和になる。公式の導出と結合法則の証明は 21 第2章 の定理 2.6（加法公式）と定理 2.10（群法則）を参照。）

整数 $k$ と点 $P$ について、$P$ を $k$ 回足したものを $[k]P$ と書く（$[0]P = O$, $[-k]P = -[k]P$）。$[k]P$ は反復二乗法（第1章）と同じ「2 倍と加算」で $O(\log k)$ 回の群演算で計算できる。

定理 4.2（ハッセの定理）$\bigl\lvert \lvert E(\mathbb{F}_p) \rvert - (p + 1) \bigr\rvert \leq 2\sqrt{p}$。

（主張のみ。証明は 21 第4章 定理 4.7 を参照。）点の個数はおよそ $p$ で、$a_p = p + 1 - \lvert E(\mathbb{F}_p) \rvert$ をフロベニウスのトレースという。$\lvert E(\mathbb{F}_p) \rvert$ そのものは、シューフのアルゴリズムとその改良により $\log p$ の多項式時間で計算でき（21 第5章 5.6 節）、暗号では位数が素数（またはその小さい倍数）になる曲線を選ぶ。

例 4.3（この章の小さい曲線）$p = 211$, $E\colon y^2 = x^3 + x + 1$ とする（$4A^3 + 27B^2 = 31 \neq 0$）。各 $x$ について $x^3 + x + 1$ が平方剰余かどうかを調べて数えると $\lvert E(\mathbb{F}_{211}) \rvert = 223$ で、これは素数である。$a_p = 212 - 223 = -11$ で、確かに $\lvert a_p \rvert \leq 2\sqrt{211} \approx 29.05$。ラグランジュの定理により $O$ 以外のすべての点は位数 $223$ で、群を生成する。点 $G = (0, 1)$ をとると、$[2]G$ は $\lambda = 1/2 = 106$（$2 \cdot 106 = 212 \equiv 1$）より

で $[2]G = (53, 78)$ である。同様に $[3]G = (72, 189)$。以下、この $G$ と $n = 223$ を使う（数値はすべて計算機で確かめた）。

4.2 楕円曲線上の離散対数問題と鍵の長さ

暗号に使う曲線は、ドメインパラメータ $(p, A, B, G, n, h)$ で指定する。$G \in E(\mathbb{F}_p)$ は素数位数 $n$ の点（ベースポイント）、$h = \lvert E(\mathbb{F}_p) \rvert / n$ は余因子 (cofactor) である。秘密鍵は整数 $d \in [1, n - 1]$、公開鍵は $Q = [d]G$ で、公開鍵から秘密鍵を求める問題が楕円曲線離散対数問題（ECDLP）である。

第3章の汎用的な攻撃はそのまま使える。ポーリッヒ–ヘルマン法があるので $n$ は大きな素数でなければならず、そのうえでベビーステップ・ジャイアントステップ法や $\rho$ 法で約 $\sqrt{n}$ 回の群演算がかかる（$\rho$ 法では $P$ と $-P$ を同一視して約 $\sqrt{\pi n/4}$ 回）。一方、素体上の一般の楕円曲線には、$\mathbb{F}_p^\times$ の指数計算法にあたる準指数時間の方法が知られていない。そのため安全性ビット数は $n$ のビット数のほぼ半分になり、128 ビットの安全性に必要な大きさは、RSA の法の 3072 ビットに対し $n$ が 256 ビットである（NIST SP 800-57 Part 1 Rev. 5 の目安。表は第3章 3.11 節。推奨は改訂されうる）。

ただし、これはよく選んだ曲線についての話である。特別な性質をもつ曲線では ECDLP が易しくなる（4.9 節）。また鍵が短くても、実装を誤れば数学の安全性は意味を失う（4.4〜4.10 節）。

4.3 ECDH 鍵共有

ディフィー–ヘルマン鍵共有（第2章）を楕円曲線の群で行うのが ECDH である。アリスは秘密鍵 $d_A$ を選んで $Q_A = [d_A]G$ を、ボブは $d_B$ を選んで $Q_B = [d_B]G$ を送る。アリスは $[d_A]Q_B$、ボブは $[d_B]Q_A$ を計算する。冪の法則 $[a]\bigl([b]P\bigr) = [ab]P$ より

なので 2 人は同じ点 $S$ を得る。実際には $S$ の $x$ 座標だけを鍵導出関数（ハッシュ関数による変換）に入れて共通鍵を作る（TLS 1.3 で P-256 を使う場合も、共有される値は $x$ 座標である）。

例 4.4 例 4.3 の曲線で $d_A = 37$, $d_B = 158$ とすると $Q_A = (169, 115)$, $Q_B = (59, 145)$。$d_Ad_B = 5846 \equiv 48 \pmod{223}$ で、2 人とも $S = [48]G = (185, 171)$ を得る。

盗聴者が $G, Q_A, Q_B$ から $S$ を求める問題（楕円曲線版の計算ディフィー–ヘルマン問題）は、ECDLP が解ければ解ける。ECDH そのものは相手を認証しないので、中間者攻撃を防ぐには署名などと組み合わせる（第2章）。

4.4 公開鍵の検証と無効曲線攻撃

ECDH の実装は、相手から受け取った点 $Q$ に自分の秘密鍵を掛ける。$Q$ が本当に $E$ の点かどうかを確かめないと何が起こるか。鍵になるのは、定理 4.1 の公式が $B$ を含まないという観察である。

命題 4.5（$B$ を使わない計算）定理 4.1 の公式だけを使って $[d]Q'$ を計算する実装に、$E$ 上にない点 $Q' = (x_0, y_0) \in \mathbb{F}_p^2$ を与える。$B' = y_0^2 - x_0^3 - Ax_0$ とおき、$4A^3 + 27B'^2 \neq 0$ とすると、実装の出力は曲線 $E'\colon y^2 = x^3 + Ax + B'$ の群 $E'(\mathbb{F}_p)$ における $[d]Q'$ である。

証明. $Q'$ は $E'$ の点である。$E'$ に定理 4.1 を適用すると、$E'(\mathbb{F}_p)$ の加法公式は $A$ だけを含み $B'$ を含まないので、実装が使う式と文字どおり一致する。したがって実装が途中で計算する点はすべて $E'(\mathbb{F}_p)$ の中にあり、2 倍と加算を正しく行っている。帰納法により、出力は $E'(\mathbb{F}_p)$ での $[d]Q'$ である。$\square$

攻撃者は、$\lvert E'(\mathbb{F}_p) \rvert$ が小さい素因数 $r$ をもつような $B'$ を探し、$E'$ 上の位数 $r$ の点 $Q'$ を公開鍵として送る。被害者の計算結果 $[d]Q'$ は $\langle Q' \rangle$ の $r$ 個の元のどれかで、それは $d \bmod r$ で決まる。被害者がこの結果から作った鍵で応答を暗号化すれば、攻撃者は $r$ 通りの候補を試して $d \bmod r$ を知る（共有値が $x$ 座標だけなら、$[j]Q'$ と $[-j]Q'$ の区別がつかず $\pm$ を除いて）。異なる $r$ について繰り返し、中国剰余定理でまとめれば $d$ が求まる（$\pm$ が残る場合も、$d^2 \bmod r$ は確定するので、$r$ の積が $n^2$ を超えるまで集めて $d^2$ を中国剰余定理で求め、その平方根をとればよい）。これを無効曲線攻撃 (invalid curve attack) という。手間は $\sqrt{n}$ ではなく、使う小さい素数 $r$ の和の程度である。

例 4.6 例 4.4 のボブの秘密鍵 $d_B = 158$ を、攻撃者が無効曲線攻撃で求める。$B' = 9$ の曲線 $E'\colon y^2 = x^3 + x + 9$ は $\lvert E'(\mathbb{F}_{211}) \rvert = 210 = 2 \cdot 3 \cdot 5 \cdot 7$ で、位数 $2, 3, 5, 7$ の点をもつ。それぞれをボブに送ると、ボブの計算結果は次のようになる。

（$x$ 座標が $126$ の点は $[2]Q'$ と $[3]Q'$、$x$ 座標が $158$ の点は $[3]Q'$ と $[4]Q'$ である。）符号の組み合わせは $2^3 = 8$ 通りで、中国剰余定理で $d_B \bmod 210$ の候補 $32, 38, 52, 88, 122, 158, 172, 178$ を得る。$d_B < 223$ なので候補はこれだけで、公開鍵 $Q_B = [d_B]G$ と照合すると $d_B = 158$ が決まる。曲線の位数 $223$ の総当たりに比べれば小さいが、実際の 256 ビットの曲線では、この差が $2^{128}$ 回の計算と数十個の小さい素数の和との差になる。

対策は単純で、受け取った点を使う前に検証することである。NIST SP 800-56A Rev. 3 の「完全な公開鍵の検証」は次の 4 段階からなる。

1. $Q \neq O$ を確かめる。
2. 座標 $x_Q, y_Q$ が $0$ 以上 $p - 1$ 以下の整数であることを確かめる。
3. $y_Q^2 \equiv x_Q^3 + Ax_Q + B \pmod{p}$（曲線上にあること）を確かめる。
4. $[n]Q = O$（正しい部分群にあること）を確かめる。

$h = 1$ の曲線では 3 までで十分で（$O$ 以外の点はすべて位数 $n$）、TLS 1.3 も P-256 などについて 1〜3 の検証を義務づけている。なお $4A^3 + 27B'^2 = 0$ となる $B'$ を使われると、計算は特異 3 次曲線の非特異点の群（$\mathbb{F}_p$ の加法群、$\mathbb{F}_p^\times$、または $\mathbb{F}_{p^2}^\times$ の部分群と同型。21 第2章 定理 2.19）の中で行われ、そこでは離散対数がさらに易しい。これも 3 の検証で防げる。

4.5 余因子と小部分群

$h > 1$ の曲線では、曲線上の点でも位数の小さい成分を含みうる。

命題 4.7（余因子による分解）$\lvert E(\mathbb{F}_p) \rvert = hn$、$n$ は素数で $n \nmid h$ とし、$G$ を位数 $n$ の点とする。

1. $[n]Q = O$ となる点 $Q$ 全体は $\langle G \rangle$ に一致する。
2. すべての $Q \in E(\mathbb{F}_p)$ は $Q = Q_1 + T$（$Q_1 \in \langle G \rangle$, $[h]T = O$）とただ一通りに書ける。
3. $h \mid k$ ならば $[k]Q = [k]Q_1$ である。特に $[h]Q \in \langle G \rangle$。

証明. (1) $[n]Q = O$ で $Q \notin \langle G \rangle$ となる $Q$ があるとする。$Q$ の位数は $n$ で、$\langle G \rangle \cap \langle Q \rangle$ は素数位数の群 $\langle Q \rangle$ の部分群で $Q$ を含まないので $\lbrace O \rbrace$ である。すると $(U, V) \mapsto U + V$ は $\langle G \rangle \times \langle Q \rangle$ から $E(\mathbb{F}_p)$ への単射となり、$n^2$ 個の元の部分群ができる。ラグランジュの定理より $n^2 \mid hn$、すなわち $n \mid h$ となって矛盾する。(2) $uh + vn = 1$ となる整数 $u, v$ をとり、$Q_1 = [uh]Q$, $T = [vn]Q$ とおくと $Q = Q_1 + T$ である。$[n]Q_1 = [u][hn]Q = O$ なので (1) より $Q_1 \in \langle G \rangle$、また $[h]T = [v][hn]Q = O$。一意性：$Q_1 + T = Q_1' + T'$ なら $Q_1 - Q_1' = T' - T$ は $[n]$ でも $[h]$ でも $O$ になり、$\gcd(n, h) = 1$ より $O$ である。(3) $[k]T = O$ による。$\square$

攻撃者が正しい公開鍵 $Q$ の代わりに $Q + T$（$T$ は位数の小さい点）を送ると、被害者の結果 $[d](Q + T) = [d]Q + [d]T$ は $d \bmod \operatorname{ord}(T)$ に依存し、その情報が漏れうる（小部分群攻撃）。漏れるのは $\operatorname{ord}(T) \mid h$ の分だけで、命題 4.7 (3) により、スカラーを $h$ の倍数にすれば $T$ の成分は消える。SP 800-56A の ECDH（余因子つき ECDH）は $P = [hd_A]Q_B$ の $x$ 座標を共有値とし、$P = O$ なら中止する。

Curve25519（$h = 8$）の ECDH である X25519（RFC 7748）は、秘密鍵の 32 バイトの整数の最下位 3 ビットと最上位ビットを $0$、その次のビットを $1$ にした値（$2^{254}$ に $8$ の倍数を足した形）をスカラーとして使う。これをクランプ (clamping) という。スカラーが $8$ の倍数なので、位数が $8$ を割る点を送られると結果は $O$ になり、X25519 はそれを全ビット $0$ の値として出力する。この共有値は受け取った側の秘密鍵に依存しないので、RFC 7748 はこれを確かめて中止してよい（MAY）とし、TLS 1.3（RFC 8446）は確かめて中止しなければならない（MUST）としている。

次のコードは RFC 7748 の手順を Python で書いたもので（安全な実装ではない）、規格のテストベクトルとの一致と、位数 2 の点 $u = 0$ に対する出力が全ビット $0$ になることを確かめる。

p = 2**255 - 19
A24 = 121665                                    # (486662 - 2) / 4

def x25519(k_bytes, u_bytes):
    k = bytearray(k_bytes)
    k[0] &= 248; k[31] &= 127; k[31] |= 64      # クランプ：8 の倍数、最上位は 2^254
    k = int.from_bytes(k, "little")
    u = int.from_bytes(u_bytes, "little") & ((1 << 255) - 1)
    x2, z2, x3, z3 = 1, 0, u, 1                  # (x2:z2) = O, (x3:z3) = P
    for t in reversed(range(255)):               # モンゴメリー・ラダー（4.10 節）
        bit = (k >> t) & 1
        if bit:                                  # 実装では定数時間の cswap にする
            x2, z2, x3, z3 = x3, z3, x2, z2
        a, b = (x2 + z2) % p, (x2 - z2) % p
        c, d = (x3 + z3) % p, (x3 - z3) % p
        da, cb = d * a % p, c * b % p
        x3, z3 = (da + cb) ** 2 % p, u * (da - cb) ** 2 % p      # 差が P の 2 点の和
        aa, bb = a * a % p, b * b % p
        x2, z2 = aa * bb % p, (aa - bb) * (aa + A24 * (aa - bb)) % p  # 2 倍
        if bit:
            x2, z2, x3, z3 = x3, z3, x2, z2
    return (x2 * pow(z2, p - 2, p) % p).to_bytes(32, "little")

k = bytes.fromhex("a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4")
u = bytes.fromhex("e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c")
print(x25519(k, u).hex())
print(x25519(k, (0).to_bytes(32, "little")).hex())   # u = 0 は位数 2 の点 (0, 0)

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552
0000000000000000000000000000000000000000000000000000000000000000

1 行目は RFC 7748 のテストベクトルの出力と一致する。X25519 は $u$ 座標（$x$ 座標にあたる）だけで計算するので、どんな $u \in \mathbb{F}_p$ も受け付け、$u$ が $E$ の点の座標でなければ二次ツイストと呼ばれる別の曲線の上で計算が進む（命題 4.5 と同じ現象）。Curve25519 はツイストの位数も $4 \times$（素数）になるように選ばれており、ツイスト上で計算させても漏れうるのは $d \bmod 4$ だけで、それもクランプで消える。この性質をツイスト安全性 (twist security) という。

4.6 ECDSA

ECDSA は DSA（第2章）を楕円曲線の群に移した署名方式で、FIPS 186-5 に定められている。メッセージのハッシュ値を $n$ のビット長に切り詰めた整数を $z$ とする。

• 署名：秘密鍵 $d$ で署名するには、(1) ナンス (nonce) $k \in [1, n - 1]$ を一様ランダムに選ぶ。(2) $[k]G = (x_1, y_1)$ とし、$r = x_1 \bmod n$ とする（$x_1$ は $0 \leq x_1 < p$ の整数とみる）。(3) $s = k^{-1}(z + rd) \bmod n$ とする。$r = 0$ または $s = 0$ なら (1) に戻る。署名は $(r, s)$ である。
• 検証：公開鍵 $Q = [d]G$ について、(1) $1 \leq r, s \leq n - 1$ を確かめる。(2) $w = s^{-1}$, $u_1 = zw$, $u_2 = rw$（すべて $\bmod n$）とし、$X = [u_1]G + [u_2]Q$ を計算する。(3) $X \neq O$ かつ $X$ の $x$ 座標を $n$ で割った余りが $r$ なら受理する。

定理 4.8（ECDSA の正しさ）正しく作られた署名は受理される。

証明. $1 \leq r, s \leq n - 1$ は作り方から成り立ち、$n$ は素数なので $w = s^{-1} \bmod n$ が定まる。$sk \equiv z + rd \pmod{n}$ より

$G$ の位数は $n$ なので $X = [u_1]G + [u_2]\bigl([d]G\bigr) = [u_1 + u_2d]G = [k]G$ である。$1 \leq k \leq n - 1$ より $X \neq O$ で、その $x$ 座標 $x_1$ について $x_1 \bmod n = r$ だから受理される。$\square$

例 4.9 例 4.3 の曲線で秘密鍵を $d = 97$ とすると $Q = [97]G = (95, 38)$。$z = 41$ にナンス $k = 150$ で署名すると、$[150]G = (33, 177)$ より $r = 33$、$s = 150^{-1}(41 + 33 \cdot 97) \bmod 223 = 90$。検証では $w = 90^{-1} \equiv 57$, $u_1 = 41 \cdot 57 \equiv 107$, $u_2 = 33 \cdot 57 \equiv 97$ で、$[107]G + [97]Q = (33, 177)$ の $x$ 座標が $r = 33$ に一致する。

これは正しさの証明であって、偽造できないこと（安全性）の証明ではない。正しく作られた署名 $(r, s)$ があれば $(r, n - s)$ も受理される（問題 4.3）ので、署名の値そのものを取引の識別子などに使う場合は、$s \leq n/2$ のものだけを受け付けるといった約束が要る。

4.7 ナンスの事故

ECDSA の安全性は、ナンス $k$ が秘密で、一様で、使い回されないことに全面的に依存している。

定理 4.10（ナンスの漏洩と再利用）$(r, s)$ をハッシュ値 $z$ に対する秘密鍵 $d$ の署名とする。

1. その署名のナンス $k$ がわかれば、$d \equiv r^{-1}(sk - z) \pmod{n}$ である。
2. 同じ $d$ と同じ $k$ で、$z_1 \not\equiv z_2 \pmod{n}$ に署名した $(r, s_1)$, $(r, s_2)$ があれば、$s_1 \not\equiv s_2$ であり、$k \equiv (z_1 - z_2)(s_1 - s_2)^{-1} \pmod{n}$ である。したがって (1) により $d$ が求まる。

証明. (1) $sk \equiv z + rd$ を $d$ について解く。$1 \leq r \leq n - 1$ と $n$ が素数であることから $r$ は可逆である。(2) $s_ik \equiv z_i + rd$（$i = 1, 2$）を辺々引くと $(s_1 - s_2)k \equiv z_1 - z_2 \not\equiv 0$。よって $s_1 \not\equiv s_2$ で、$s_1 - s_2$ は可逆である。$\square$

同じ $k$ なら同じ $r$ になるので、再利用は署名を見るだけでわかる。

例 4.11 例 4.9 の署名者が、同じ $k = 150$ で $z_2 = 179$ にも署名したとする。$s_2 = 150^{-1}(179 + 33 \cdot 97) \bmod 223 = 82$ である。攻撃者は公開された $(33, 90)$, $(33, 82)$ と $z_1, z_2$ だけから

を得る（$8^{-1} \equiv 28$, $33^{-1} \equiv 196$）。

これは机上の話ではない。2010 年末には、ある家庭用ゲーム機のソフトウェアの署名で毎回同じ $k$ が使われており、定理 4.10 (2) によって署名鍵が計算されたことが公表された。

ナンスは「使い回さない」だけでは足りない。

• 範囲が狭い：点 $R = [k]G$ は、検証と同じ計算 $[u_1]G + [u_2]Q$（定理 4.8 の証明）で誰でも求められる。$k$ が $[0, K)$ にあるとわかっていれば、範囲を制限したベビーステップ・ジャイアントステップ法で $O(\sqrt{K})$ 回の群演算で $k$ が求まり（第3章 問題 3.5）、定理 4.10 (1) で $d$ がわかる。$k$ を 64 ビットの乱数から作れば、群がどれほど大きくても約 $2^{33}$ 回で破られる。上位のビットの多くが $0$ に偏ったナンスは、範囲の狭いナンスにほかならない。
• 関係がある：連続する署名で $k_2 = k_1 + 1$ のようにナンスが既知の関係にあれば、2 つの署名の式は $(k_1, d)$ についての連立一次合同式になり、$d$ が求まる（問題 4.5）。
• 偏りがある：ナンスの上位の数ビットが $0$ に偏るだけでも、多数の署名から格子の手法（第7章の LLL アルゴリズム。隠れた数の問題と呼ばれる問題に帰着される）で秘密鍵が求まることが知られている。計算時間の差からナンスのビット長が漏れ、この方法で鍵が復元された実例も報告されている。$k$ を「256 ビットの乱数を $n$ で割った余り」として作るだけでもわずかな偏りが生じるので、FIPS 186-5 は 64 ビット以上余分に乱数をとってから余りをとるか、範囲外の値を捨てて選び直す方法を定めている。

決定的なナンス　乱数の質に依存しないように、ナンスを秘密鍵とメッセージから決定的に作る方法がある。RFC 6979 の決定的 ECDSA は、$d$ とハッシュ値を種とする、HMAC にもとづく擬似乱数生成器（HMAC_DRBG）から $k$ を作り、FIPS 186-5 でも承認されている。同じメッセージには同じ署名が出るが（それは無害である）、異なるメッセージのナンスは秘密鍵を知らない者には予測できず、一致することもまずない。秘密を含まずにメッセージだけから $k = H(m)$ のように作るのは致命的な誤りである（問題 4.4）。

4.8 EdDSA と Curve25519

曲線　Curve25519 は $p = 2^{255} - 19$ 上のモンゴメリー形の曲線

で、$\lvert E(\mathbb{F}_p) \rvert = 8n$, $n = 2^{252} + 27742317777372353535851937790883648493$（素数）、ベースポイントの $u$ 座標は $9$ である（RFC 7748）。これはツイストエドワーズ形 (twisted Edwards form) の曲線 edwards25519

と $(u, v) = \bigl((1 + y)/(1 - y), \sqrt{-486664} \cdot u/x\bigr)$ で双有理同値で（RFC 7748。この $d$ は ECDSA の秘密鍵とは別物）、ベースポイントは $y = 4/5$ の点（$u = (1 + 4/5)/(1 - 4/5) = 9$ に対応）である。エドワーズ形の加法公式は

で、単位元は $(0, 1)$、$-(x, y) = (-x, y)$ である（主張のみ。一般の $ax^2 + y^2 = 1 + dx^2y^2$ の場合が 21 第5章 5.5 節にある）。$-1$ が $\mathbb{F}_p$ の平方数（$p \equiv 1 \pmod 4$）で $d$ が平方数でない（計算機で確認）ので、曲線上のどんな 2 点についても分母は $0$ にならない（問題 4.8）。2 倍算も単位元も場合分けなしに同じ式で計算できる公式を完全な加法公式 (complete addition law) といい、秘密に依存する分岐をなくすのに役立つ。

Ed25519（RFC 8032）　 $H$ を SHA-512 とし、ハッシュ値は 512 ビットの整数とみる。ベースポイントを $G$（位数 $n$）とする。

• 鍵：秘密鍵は 32 バイトの乱数 $k_0$。$H(k_0)$ の前半を X25519 と同様にクランプした整数を秘密のスカラー $s$、後半を $\mathit{prefix}$ とし、公開鍵を $Q = [s]G$ とする。
• 署名：メッセージ $M$ に対し、$r = H(\mathit{prefix} \mathbin{\Vert} M) \bmod n$, $R = [r]G$, $c = H(R \mathbin{\Vert} Q \mathbin{\Vert} M) \bmod n$, $S = (r + cs) \bmod n$ とし、署名を $(R, S)$ とする（$\Vert$ は連結。点はバイト列に符号化してから入れる）。
• 検証：$0 \leq S < n$ を確かめ、$c = H(R \mathbin{\Vert} Q \mathbin{\Vert} M) \bmod n$ として $[8][S]G = [8]R + [8][c]Q$ が成り立てば受理する（$[S]G = R + [c]Q$ を確かめてもよい）。

（RFC 8032 では基点を $B$、公開鍵を $A$、位数を $L$ と書く。）

定理 4.12（EdDSA の正しさ）正しく作られた署名は受理される。

証明. $S \equiv r + cs \pmod{n}$ で $G$ の位数は $n$ なので、$[S]G = [r]G + [c]\bigl([s]G\bigr) = R + [c]Q$。両辺に $[8]$ を施せば 2 つ目の式も成り立つ。$0 \leq S < n$ は作り方から成り立つ。$\square$

なぜナンスを決定的に作るのか　EdDSA の $r$ も ECDSA の $k$ と同じ役割をもち、同じ $r$ で異なるメッセージに署名すると、$c_1 \not\equiv c_2$ のとき $s \equiv (S_1 - S_2)(c_1 - c_2)^{-1} \pmod{n}$ で秘密のスカラーが求まる（定理 4.10 と同じ計算）。EdDSA は $r$ を秘密の $\mathit{prefix}$ とメッセージのハッシュから作るので、(1) 署名のときに乱数が要らず、乱数生成器の欠陥の影響を受けない。(2) 同じメッセージなら同じ $r$ で、署名も同じになるので害はない。(3) 異なるメッセージで $r$ が一致するのは $H$ の出力が $\bmod n$ で一致する場合に限られ、$H$ がランダムな関数のようにふるまうなら、その確率は 1 組あたり約 $1/n$ で無視できる。(4) $\mathit{prefix}$ を知らない者には $r$ が予測できない。RFC 8032 は「EdDSA の署名は決定的であり、質の悪い乱数で署名することから生じる攻撃を防ぐ」と述べている。

検証で $S < n$ を確かめるのは、$S + n$ も同じ式をみたしてしまい、同じメッセージに別の有効な署名が作れる（展性）のを防ぐためである。また余因子 $8$ を掛ける式と掛けない式は、位数の小さい成分を混ぜた悪意のある署名に対して判定が分かれうる。RFC 8032 はどちらを使ってもよいとしているが、複数の実装が同じ判定をしなければならない用途（合意形成など）ではどちらかに統一する必要がある。

4.9 安全な曲線の条件

ECDLP が易しくなる曲線の性質と、規格の曲線が満たしている条件をまとめる。ここで $n$ はベースポイントの位数、$h$ は余因子である。

1. $n$ が大きな素数で、$h$ が小さい：ポーリッヒ–ヘルマン法と $\sqrt{n}$ の汎用攻撃への対策。$h$ は 1, 4, 8 程度にする（4.5 節）。
2. 埋め込み次数が大きい：$n \mid p^k - 1$ となる最小の $k$ を埋め込み次数という。ヴェイユ対などを使うと ECDLP は $\mathbb{F}_{p^k}^\times$ の離散対数問題に帰着され（MOV 帰着。主張のみ、21 第5章 定理 5.15）、$k$ が小さければ指数計算法系の方法で解ける。超特異曲線は $k$ が小さい（素体 $\mathbb{F}_p$, $p \geq 5$ 上では $k \leq 2$。同 命題 5.16。問題 4.7 は一例）。
3. アノマラスでない：$\lvert E(\mathbb{F}_p) \rvert = p$ の曲線（アノマラス曲線）では ECDLP が多項式時間で解ける（主張のみ、21 第5章 定理 5.18）。
4. ツイスト安全性：$x$ 座標だけで計算する実装を想定するなら、二次ツイストの位数も大きな素因数をもつようにする（4.5 節）。NIST SP 800-186 は、P-224 のツイストの位数の最大の素因数が約 $2^{117}$ しかないので、ツイスト上で計算させられないよう検証が欠かせないと注意している。
5. 作り方が検証できる：パラメータに意図的な弱点が仕込まれていないことを第三者が確かめられるようにする。P-256 の $B$ は公開された種から SHA-1 で導かれる（SEC 2 の「検証可能なランダム」。ただし種そのものがどう選ばれたかは公表されていない）。Curve25519 の係数 $486662$ は条件をみたす最小の値として決められている（RFC 7748 付録 A。そこではフロベニウスのトレースが $0, 1$ でないこと、埋め込み次数が $(n - 1)/100$ より大きいこと、虚数乗法の判別式が $2^{100}$ より大きいことも条件にしている）。

実際に広く使われている 3 つの曲線のパラメータを、規格（SEC 2、FIPS 186-5 / SP 800-186、RFC 7748）と照合して示す。$\lvert E(\mathbb{F}_p) \rvert = hn$ と $n$ が素数であること、トレースが $0, 1$ でないこと、埋め込み次数（それぞれ $(n - 1)/6$, $(n - 1)/3$, $(n - 1)/6$）を PARI/GP で確かめた。

secp256k1（SEC 2）：ビットコインなど
  p = 2^256 - 2^32 - 977,   y^2 = x^3 + 7,   h = 1
  n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

P-256（FIPS 186-5 / SP 800-186。SEC 2 では secp256r1）：TLS など
  p = 2^256 - 2^224 + 2^192 + 2^96 - 1,   y^2 = x^3 - 3x + B,   h = 1
  B = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
  n = FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551

Curve25519（RFC 7748）：X25519、Ed25519（edwards25519 として）
  p = 2^255 - 19,   v^2 = u^3 + 486662 u^2 + u,   h = 8
  n = 2^252 + 27742317777372353535851937790883648493

secp256k1 は $j$ 不変量が $0$ の曲線で、位数 6 の自己同型（効率的に計算できる自己準同型）をもつ。これはスカラー倍の高速化に使える一方、$\rho$ 法も約 $\sqrt{6}$ 倍速くできることが知られているが、ビット数にして 1〜2 ビットの差で、128 ビット程度の安全性は保たれる。

4.10 秘密に依存しない実装

数学的に正しい計算も、計算のしかたが秘密に依存すると漏れる。2 倍と加算によるスカラー倍は、$k$ の 2 進表示の $1$ のビットでだけ加算を行うので、処理時間や消費電力の波形から加算の有無、すなわち $k$ のビットが読み取れる。秘密に依存する分岐・メモリの参照位置・可変時間の命令をなくした実装を定数時間実装 (constant-time implementation) という。

命題 4.13（モンゴメリー・ラダー, Montgomery ladder）$k = \sum_{i=0}^{t} b_i2^i$（$b_i \in \lbrace 0, 1 \rbrace$）とし、$(R_0, R_1) = (O, P)$ から始めて $i = t, t - 1, \dots, 0$ の順に、$b_i = 0$ なら $(R_0, R_1) \leftarrow ([2]R_0, R_0 + R_1)$、$b_i = 1$ なら $(R_0, R_1) \leftarrow (R_0 + R_1, [2]R_1)$ とする。すると各段の後で $R_1 - R_0 = P$ であり、最後に $R_0 = [k]P$ となる。