第5章楕円曲線の計算と暗号

この章の目標

• スカラー倍を二進法と射影座標で計算でき、その計算量を評価できる
• ECDH・エルガマル暗号・ECDSA の正しさと、ナンスの再利用で秘密鍵が漏れることを証明できる
• ベビーステップ・ジャイアントステップ法、ポラードの $\rho$ 法、ポーリッヒ–ヘルマン法の正しさと計算量を説明できる
• MOV 攻撃とアノマラス曲線への攻撃の仕組みと、secp256k1・P-256・Curve25519 が選ばれている理由を説明できる
• シューフのアルゴリズムの考え方と、レンストラの楕円曲線法で素因数が見つかる理由を説明できる
• 量子計算機と同種写像暗号について、確かなことを区別して述べられる

前提：第2章、第4章。5.4 節では第3章のヴェイユ対（定義 3.30・定理 3.31）を、5.6 節では同じく第3章の等分多項式（定義 3.17）を使い、5.4 節のアノマラス曲線の部分では第6章 6.4 節の $E_1(K)$ のフィルトレーションの結果を先取りする。中国剰余定理は 04-algebra 第1章、有限体の乗法群が巡回群であることは 04-algebra 第8章 を参照。

有限体上の楕円曲線の群 $E(\mathbb{F}_q)$ は、元が座標の組で表され、演算が第2章の加法公式（定理 2.6）で計算できる有限アーベル群である。1985 年にコブリッツとミラーがそれぞれ独立に、この群を離散対数問題にもとづく暗号に使うことを提案し、現在ではウェブの暗号通信（TLS）やビットコインの署名などで日常的に使われている。

暗号に使えるのは、$m$ から $[m]P$ を求めるのは速い（5.1 節）が、$[m]P$ から $m$ を求める問題には、一般の曲線では指数時間のアルゴリズムしか知られていないからである。後者は定理ではなく経験的な事実である。特殊な曲線には効率のよい攻撃があり（5.4 節）、その仕組みは第3章のヴェイユ対や第6章の $p$ 進的な理論そのものである。楕円曲線は点の個数の計算（5.6 節）や素因数分解（5.7 節）の道具にもなる。

本章では、5.5 節のモンゴメリー形・エドワーズ形を除き、曲線を短い形 $y^2 = x^3 + Ax + B$（標数 $\neq 2, 3$）で表す。プロトコルの細部と実装上の注意は 25 暗号と符号 第4章 で扱い、本章はアルゴリズムの正しさと計算量、攻撃が成り立つ理由を中心にする。

5.1 スカラー倍の計算

暗号では $m$ が 256 ビット程度になるので、$P$ を $m - 1$ 回足すことはできない。整数のべき乗の反復二乗法と同じく、二進展開 $m = \sum_{i=0}^{t} b_i2^i$（$b_i \in \lbrace 0, 1 \rbrace$, $b_t = 1$, $t = \lfloor \log_2 m \rfloor$）を使う。二進法 (double-and-add) では、$R = O$ から始めて $i = t, t - 1, \dots, 0$ の順に「$R \leftarrow [2]R$ とし、$b_i = 1$ ならさらに $R \leftarrow R + P$ とする」ことを繰り返す。

命題 5.1（二進法）二進法は $[m]P$ を出力する。最初の段（$O$ の 2 倍と $O + P$ で、計算は要らない）を除くと、2 倍算は $t$ 回、加算は $w(m) - 1$ 回である。ここで $w(m)$ は $m$ の二進展開の $1$ の個数である。特に群演算は $2\lfloor \log_2 m \rfloor$ 回以下である。

証明. $m_j = \sum_{i=j}^{t} b_i2^{i-j}$（$m$ の上から $t - j + 1$ 桁）とおくと $m_t = 1$, $m_j = 2m_{j+1} + b_j$, $m_0 = m$ で、$i = j$ の段の後で $R = [m_j]P$ となることが下向きの帰納法でわかる（段の始めに $R = [m_{j+1}]P$ なら、段の後は $[2m_{j+1} + b_j]P$）。回数は、$j < t$ の各段で 2 倍算が 1 回、$b_j = 1$ のときだけ加算が 1 回であることから従う。$\square$

例 5.2 $\mathbb{F}_{97}$ 上の $E\colon y^2 = x^3 + 7$（5.5 節の secp256k1 と同じ式）を考える。すべての $x$ について数えると $\lvert E(\mathbb{F}_{97}) \rvert = 79$ で、これは素数なので $O$ 以外の点はすべて位数 79 である。$G = (1, 28)$ とし、$10 = 1010_2$ に沿って計算すると

となる。この曲線は以下の例でも使う。

注意 5.3 アフィン座標の群演算は $\mathbb{F}_p$ での数回の乗算と 1 回の逆元の計算からなり、どちらも（筆算と拡張ユークリッド互除法で）$O((\log p)^2)$ 回のビット演算でできる。よって $m < 2p$ なら $[m]P$ は $O((\log p)^3)$ 回のビット演算で計算できる。ただし演算の並びが $m$ のビットに依存するので、計算時間などから秘密の $m$ が漏れうる（5.5 節のラダーを参照）。

射影座標

逆元の計算は乗算よりかなり重いので、実装では第2章 2.8 節のヤコビ座標（$[X : Y : Z]$ を点 $(X/Z^2, Y/Z^3)$ と同一視し、$Z = 0$ を $O$ とする）を使い、逆元の計算を最後の 1 回だけにする。

注意 5.4 第2章 2.8 節のヤコビ座標の 2 倍算に現れる $M = 3X^2 + AZ^4$ は、$A = -3$ なら $3(X - Z^2)(X + Z^2)$ と因数分解でき、乗算を節約できる（5.5 節の P-256 は $A = -3$ をとっている）。加算も、加法公式の分母を払えば逆元を使わない式になる（計算は省略する）。また $-P = (x, -y)$ はただで求まるので、$\pm 1$ を桁に使う符号付き二進展開で加算を減らせる（問題 5.1）。

5.2 楕円曲線離散対数問題と暗号方式

定義 5.5（楕円曲線離散対数問題, elliptic curve discrete logarithm problem）$P \in E(\mathbb{F}_q)$ を位数 $n$ の点、$Q \in \langle P \rangle$ とする。$Q = [m]P$ となる $m \in \mathbb{Z}/n\mathbb{Z}$ を求める問題を楕円曲線離散対数問題（ECDLP）といい、$m$ を $Q$ の離散対数という。

暗号では、$\mathbb{F}_p$ 上の曲線 $E$、素数位数 $n$ の点 $G$（ベースポイント, base point）、余因子 (cofactor) $h = \lvert E(\mathbb{F}_p) \rvert / n$ を公開する（この $h$ は第8章の高さとは無関係）。秘密鍵は $d \in [1, n - 1]$、公開鍵は $Q = [d]G$ で、秘密鍵を求めることは ECDLP そのものである。一般の曲線に対する最良の攻撃は 5.3 節の汎用的な方法で、$n \approx 2^{256}$ なら約 $2^{128}$ 回の群演算を要する。$\mathbb{F}_p^\times$ の離散対数問題には準指数時間の方法（数体ふるい法など）があるので、同程度の安全性には 3072 ビット程度の $p$ が要る（NIST SP 800-57 Part 1 の目安。推奨は変わりうる）。

ECDH（楕円曲線ディフィー–ヘルマン鍵共有）：A さんは秘密鍵 $d_A$ を選んで $Q_A = [d_A]G$ を、B さんは $d_B$ を選んで $Q_B = [d_B]G$ を送る。$[a] \circ [b] = [ab]$ なので $[d_A]Q_B = [d_B]Q_A = [d_Ad_B]G$ で、これが共有された秘密になる。盗聴者が $G, Q_A, Q_B$ から $[d_Ad_B]G$ を求める問題（計算ディフィー–ヘルマン問題）は、ECDLP が解ければ解けるが、逆が成り立つかは一般にはわかっていない。

楕円曲線エルガマル暗号：受信者の公開鍵 $Q = [d]G$ に点 $M$ を送るには、乱数 $k$ を選んで $(C_1, C_2) = ([k]G, M + [k]Q)$ を送る。受信者は $C_2 - [d]C_1 = M + [kd]G - [dk]G = M$ で復元できる（これが正しさの証明である）。実際には、同じ考え方の鍵共有と共通鍵暗号を組み合わせた方式（ECIES など）が使われる。

ECDSA：メッセージのハッシュ値を $n$ のビット長に切り詰めた整数を $z$ とする（詳細は FIPS 186-5）。秘密鍵 $d$ による署名 $(r, s)$ は次のように作る。

1. 乱数 $k \in [1, n - 1]$（ナンス, nonce）を選ぶ。
2. $[k]G = (x_1, y_1)$ とし、$x_1$ を $0 \leq x_1 < p$ の整数とみて $r = x_1 \bmod n$ とする。$r = 0$ なら 1 に戻る。
3. $s = k^{-1}(z + rd) \bmod n$ とする。$s = 0$ なら 1 に戻る。

公開鍵 $Q = [d]G$ による検証は次のとおりである。

1. $1 \leq r, s \leq n - 1$ を確かめ、$w = s^{-1} \bmod n$, $u_1 = zw \bmod n$, $u_2 = rw \bmod n$ とする。
2. $X = [u_1]G + [u_2]Q$ を計算し、$X \neq O$ かつ $X$ の $x$ 座標を $n$ で割った余りが $r$ なら受理する。

定理 5.6（ECDSA の正しさ）上の手順で作られた署名は、検証で受理される。

証明. $s \not\equiv 0$ より $w$ が定まり、$z + rd \equiv sk \pmod{n}$ なので $u_1 + u_2d \equiv w(z + rd) \equiv s^{-1}sk \equiv k \pmod{n}$。$G$ の位数は $n$ なので $X = [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$

これは正しさの証明で、偽造できないこと（安全性）の証明ではない。一方、使い方を誤ると安全性が失われることは証明できる。

定理 5.7（ナンスの再利用）同じ秘密鍵 $d$ で、ハッシュ値 $z_1 \not\equiv z_2 \pmod{n}$ の 2 つのメッセージに同じナンス $k$ を使って署名 $(r, s_1)$, $(r, s_2)$ を作ったとする。このとき $s_1 \not\equiv s_2$ であり、

$$k \equiv (z_1 - z_2)(s_1 - s_2)^{-1}, \qquad d \equiv (s_1k - z_1)r^{-1} \pmod{n}$$

である。したがって公開された情報だけから秘密鍵が計算できる。

証明. $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$ で、$n$ は素数なので $s_1 - s_2$ は可逆であり、$k$ の式を得る。$rd \equiv s_1k - z_1$ で $1 \leq r \leq n - 1$ も可逆なので $d$ の式を得る。$\square$

ナンスが同じなら $r$ も同じなので、使い回しは署名を見ればわかる。ナンスの一部のビットが偏るだけでも、多数の署名から格子の手法で秘密鍵が復元できることが知られており、実装ではナンスを秘密鍵とメッセージから決定的に作る方式（RFC 6979）なども使われる（25 第4章）。

例 5.8 例 5.2 の曲線（$n = 79$, $G = (1, 28)$）で秘密鍵を $d = 29$ とすると、公開鍵は $Q = [29]G = (78, 61)$。ハッシュ値 $z_1 = 31$, $z_2 = 56$ に同じナンス $k = 10$ で署名すると、$[10]G = (32, 59)$ より $r = 32$、$k^{-1} \equiv 8$ で

検証者は $(32, 9)$ について $w \equiv 9^{-1} \equiv 44$, $u_1 \equiv 31 \cdot 44 \equiv 21$, $u_2 \equiv 32 \cdot 44 \equiv 65$ を求め、$[21]G + [65]Q$ の $x$ 座標が $32$ であることを確かめる（$21 + 65 \cdot 29 \equiv 10$ なので確かに $[10]G$）。攻撃者は定理 5.7 により $k \equiv (31 - 56)(9 - 51)^{-1} \equiv 54 \cdot 47 \equiv 10$、$d \equiv (9 \cdot 10 - 31) \cdot 32^{-1} \equiv 59 \cdot 42 \equiv 29$ を得る。

5.3 汎用的な攻撃

この節では $\langle P \rangle$ を位数 $n$ の巡回群、$Q \in \langle P \rangle$ とし、群演算と元の比較（ハッシュ表の登録・検索を含む）だけを使う汎用的な (generic) アルゴリズムを考える。どんな群でも同じように働く。

定理 5.9（ベビーステップ・ジャイアントステップ法, baby-step giant-step）$M = \lceil \sqrt{n} \rceil$ とする。点 $[j]P$（$0 \leq j < M$）を計算して表に登録し（ベビーステップ）、$i = 0, 1, \dots, M - 1$ の順に $Q - [iM]P$ が表にあるかを調べる（ジャイアントステップ）。このとき $Q - [iM]P = [j]P$ となる $(i, j)$ が必ず見つかり、$m = iM + j$ は $Q$ の離散対数である。群演算は $2\sqrt{n} + O(\log n)$ 回以下、記憶する点は $M$ 個である。

証明. $Q = [m_0]P$（$0 \leq m_0 < n$）とし $m_0 = iM + j$（$0 \leq j < M$）と割ると、$n \leq M^2$ より $i \leq (n - 1)/M < M$ なので、この $(i, j)$ で一致が起こる。逆に $Q - [iM]P = [j]P$ なら $Q = [iM + j]P$。演算はベビーステップ $M - 2$ 回、$[M]P$ の計算 $O(\log n)$ 回、ジャイアントステップ高々 $M - 1$ 回で、$M < \sqrt{n} + 1$ である。$\square$

例 5.10 例 5.8 の公開鍵 $Q = (78, 61)$ に適用する。$M = 9$ で、$[9]G = (96, 43)$ を引いていくと $Q - [9]G = (45, 7)$, $Q - [18]G = (65, 5)$, $Q - [27]G = (68, 81) = [2]G$ となり、$d = 27 + 2 = 29$ が求まる。

ポラードの $\rho$ 法 (Pollard's rho method) は、ほぼ同じ手間をわずかな記憶で実現する。$\langle P \rangle$ を（例えば $x$ 座標を 3 で割った余りで）3 つに分け、どれに属するかに応じて $f(R) = R + P, [2]R, R + Q$ とおく。$R_{i+1} = f(R_i)$ で点列を作ると、$R_i = [a_i]P + [b_i]Q$ となる $a_i, b_i$ も同時に追跡できる。群は有限なので、いつか $R_i = R_j$（$i < j$）となり以後は周期的になる（形が文字 $\rho$ に似ている）。このとき $a_i - a_j \equiv m(b_j - b_i) \pmod{n}$ で、$n$ が素数で $b_i \not\equiv b_j$ なら $m$ が求まる。一致は $R_i$ と $R_{2i}$ を並行して計算して比べれば見つかる（フロイドの方法。点列が添字 $\mu$ から周期 $\lambda$ で繰り返すなら、$\lambda \mid i$, $i \geq \mu$ で $R_i = R_{2i}$）ので、記憶は $O(1)$ ですむ。

命題 5.11（誕生日の議論, birthday paradox）$S$ を $n$ 元集合、$f\colon S \to S$ を一様ランダムに選んだ写像、$x_0 \in S$, $x_{i+1} = f(x_i)$ とし、$x_T \in \lbrace x_0, \dots, x_{T-1} \rbrace$ となる最小の $T$ を考えると

$$\Pr(T > k) = \prod_{i=1}^{k}\Bigl(1 - \frac{i}{n}\Bigr) \leq \exp\Bigl(-\frac{k(k+1)}{2n}\Bigr), \qquad \mathbb{E}[T] = \sum_{k \geq 0}\Pr(T > k) = \sqrt{\frac{\pi n}{2}} + O(1)$$

証明の概略. $x_0, \dots, x_{i-1}$ が相異なるとき、$x_{i-1}$ での $f$ の値はまだ使われていないので $f(x_{i-1})$ は一様に分布し、$x_i$ がそれまでの $i$ 個と異なる確率は $1 - i/n$。これを掛けて第 1 式を、$1 - t \leq e^{-t}$ から不等式を得る。不等式の右辺は $e^{-k^2/(2n)}$ 以下で、これは $k$ について減少するから、$k \geq 1$ の項を区間 $[k - 1, k]$ での積分で上から押さえて $\mathbb{E}[T] \leq 1 + \int_0^\infty e^{-x^2/(2n)} dx = 1 + \sqrt{\pi n/2}$ を得る（攻撃の手間の評価にはこの上界で足りる）。和を同じ積分で近似すると期待値の主要項が得られる（下からの評価と誤差の評価は省略する。実際には $\sqrt{\pi n/2} - 1/3 + o(1)$ である）。$\square$

$\rho$ 法の $f$ がランダムな写像のようにふるまうと仮定すると、約 $\sqrt{\pi n/2} \approx 1.25\sqrt{n}$ 段で一致が起こる。フロイドの方法でも手間は $O(\sqrt{n})$ のままで、実際にもほぼこの程度の手間で一致が見つかり、並列化もできる。逆に、群を「ブラックボックス」としてしか使わないアルゴリズムは、$n$ の最大の素因数 $\ell$ について $\sqrt{\ell}$ の定数倍程度の群演算を必要とすることが証明されている（ネチャエフ、ショウプ）。

定理 5.12（ポーリッヒ–ヘルマン法, Pohlig–Hellman）$n = \prod_{i=1}^{r} \ell_i^{e_i}$ とする。位数 $n$ の巡回群の離散対数問題は、位数 $\ell_i$ の群の離散対数問題を合計 $\sum_i e_i$ 個解くことと $O(\sum_i e_i \log n)$ 回の群演算に帰着される。各段をベビーステップ・ジャイアントステップ法で解けば、群演算は $O\bigl(\sum_i e_i(\log n + \sqrt{\ell_i})\bigr)$ 回である。

証明. $Q = [m]P$ とする。(1) $n$ の素因数 $\ell$ について $\ell^e$ を $n$ を割る $\ell$ の最大べきとし、$P' = [n/\ell^e]P$, $Q' = [n/\ell^e]Q$ とおくと、$P'$ の位数は $\ell^e$ で $Q' = [m]P'$ なので、$Q'$ の $P'$ を底とする離散対数は $m \bmod \ell^e$ である。すべての $\ell_i^{e_i}$ についてこれを求めれば、中国剰余定理（04-algebra 第1章 定理 1.28）で $m \bmod n$ が定まる。(2) $x = m \bmod \ell^e = c_0 + c_1\ell + \dots + c_{e-1}\ell^{e-1}$（$0 \leq c_j < \ell$）とし、位数 $\ell$ の点 $T = [\ell^{e-1}]P'$ をとる。$c_0, \dots, c_{j-1}$ がわかったとして $x_j = c_0 + \dots + c_{j-1}\ell^{j-1}$ とおくと、$x - x_j - c_j\ell^j$ は $\ell^{j+1}$ の倍数なので

となり、$c_j$ は位数 $\ell$ の群 $\langle T \rangle$ での離散対数である。$j = 0, \dots, e - 1$ の順に求まり、各段のスカラー倍は $O(\log n)$ 回の演算である。$\square$

したがって離散対数問題の難しさは位数の最大の素因数で決まる。ベースポイントの位数 $n$ を素数にとり、$\rho$ 法に耐えるよう大きくするのはこのためである。

例 5.13 $\mathbb{F}_{103}$ 上の $y^2 = x^3 + 4x + 2$ では $E(\mathbb{F}_{103}) \cong \mathbb{Z}/108\mathbb{Z}$（$108 = 2^2 \cdot 3^3$）で、$P = (4, 44)$ が生成元である。$Q = (90, 15) = [m]P$ とする。$\ell = 2$ では $P' = [27]P = (24, 74)$, $Q' = [27]Q = (24, 29) = -P'$ より $m \equiv 3 \pmod{4}$。$\ell = 3$ では $P' = [4]P = (11, 48)$, $Q' = [4]Q = (32, 91)$, $T = [9]P' = (3, 12)$, $[2]T = (3, 91)$ で、$[9]Q' = [2]T$, $[3]\bigl(Q' - [2]P'\bigr) = [2]T$, $Q' - [8]P' = T$ より $(c_0, c_1, c_2) = (2, 2, 1)$、$m \equiv 2 + 2 \cdot 3 + 9 = 17 \pmod{27}$。中国剰余定理より $m = 71$ である。

5.4 特殊な曲線への攻撃

定義 5.14（埋め込み次数, embedding degree）$\lvert E(\mathbb{F}_q) \rvert$ を割る素数 $n$（$n \nmid q$）について、$n \mid q^k - 1$ となる最小の $k \geq 1$ を埋め込み次数という。$\mathbb{F}_{q^k}^\times$ は位数 $q^k - 1$ の巡回群なので（04-algebra 第8章 定理 8.40）、これは $\mu_n \subset \mathbb{F}_{q^k}^\times$ となる最小の $k$ である。

第3章のヴェイユ対 $e_n\colon E[n] \times E[n] \to \mu_n$（定義 3.30）は双線形・交代的・非退化である（定理 3.31）。メネゼス、岡本、ヴァンストーンは 1991 年に、これで ECDLP を有限体の乗法群の離散対数問題に移せることを示した（3 人の頭文字から MOV 帰着という）。

定理 5.15（MOV 帰着, MOV reduction）$P \in E(\mathbb{F}_q)$ を素数位数 $n$（$n \nmid q$）の点とし、埋め込み次数 $k$ は 2 以上とする。このとき $E[n] \subset E(\mathbb{F}_{q^k})$ であり、$e_n(P, T) \neq 1$ となる $T \in E[n]$ をとると、$R \mapsto e_n(R, T)$ は単射準同型 $\langle P \rangle \to \mu_n \subset \mathbb{F}_{q^k}^\times$ である。特に $Q = [m]P$ なら $e_n(Q, T) = e_n(P, T)^m$ で、ECDLP は $\mathbb{F}_{q^k}^\times$ の離散対数問題に帰着される。

証明の概略. $E[n] \subset E(\mathbb{F}_{q^k})$ はバラスブラマニアン–コブリッツの定理（$n \nmid q - 1$ なら $E[n] \subset E(\mathbb{F}_{q^r}) \iff n \mid q^r - 1$）による（主張のみ）。非退化性より $e_n(P, T) \neq 1$ となる $T$ があり、写像は第 1 変数について準同型で、$P$ の像は位数 $n$ の元（$n$ は素数）なので単射である。$e_n$ はミラーのアルゴリズムで $k\log q$ の多項式時間で計算でき、$T$ も効率よく作れる（詳細は省略する）。$\square$

$\mathbb{F}_{q^k}^\times$ の離散対数問題には準指数時間の方法があるので、$k$ が小さいと ECDLP はずっと易しくなる（フライとリュックは 1994 年に、テイト対で同様の帰着を与えた）。ランダムな曲線では $k$ は $n$ と同程度に大きいのが普通である。逆に $k$ が小さく $n$ が大きい曲線は、ペアリングを使う暗号（ID ベース暗号や短い署名など）に使われる。

命題 5.16（超特異曲線の埋め込み次数）超特異な $E/\mathbb{F}_q$ の埋め込み次数は 6 以下である。$q = p \geq 5$ が素数なら $\lvert E(\mathbb{F}_p) \rvert = p + 1$ で、埋め込み次数は 2 以下である。

証明. $q = p^r$, $N = \lvert E(\mathbb{F}_q) \rvert = q + 1 - a_q$ とし、素数 $n \mid N$（$n \neq p$）をとる。$n \mid q^j - 1$ となる $j$ があれば、埋め込み次数は $j$ 以下である。第4章の超特異性の同値条件（定理 4.17）より $p \mid a_q$ である。

$q = p \geq 5$ なら、ハッセの定理（定理 4.7）より $\lvert a_p \rvert \leq 2\sqrt{p} < p$ なので $a_p = 0$、すなわち $N = p + 1$ で、$n \mid p + 1 \mid p^2 - 1$ より埋め込み次数は 2 以下である。

一般の場合は、$p \mid a_q$ とウォーターハウスの定理（定理 4.21）から $a_q$ は次のいずれかである（定理 4.17 と 4.21 は第4章で主張として述べたもので、ここではそれを認める）。$a_q = 0$ なら $n \mid q + 1 \mid q^2 - 1$。$a_q = \pm 2\sqrt{q}$（$r$ は偶数）なら $N = (\sqrt{q} \mp 1)^2$ なので $n \mid \sqrt{q} \mp 1 \mid q - 1$。$a_q = \pm\sqrt{q}$（$r$ は偶数）なら $(\sqrt{q} \pm 1)N = q\sqrt{q} \pm 1$ は $q^3 - 1$ を割る。$a_q = \pm\sqrt{pq}$（$r$ は奇数で $p = 2, 3$）なら $N(q + 1 \pm \sqrt{pq}) = (q + 1)^2 - pq$ で、これは $p = 2$ なら $q^2 + 1$ で $q^4 - 1$ を割り、$p = 3$ なら $q^2 - q + 1$ で $q^3 + 1$ を、したがって $q^6 - 1$ を割る。いずれの場合も $j \leq 6$ がとれる。$\square$

例 5.17 $\mathbb{F}_{67}$ 上の $E\colon y^2 = x^3 + x$ では $\lvert E(\mathbb{F}_{67}) \rvert = 68 = 4 \cdot 17$（第4章 定理 4.18(2)。問題 5.5 も参照）で、$P = (62, 2)$ は位数 17 の点である。$Q = [11]P = (59, 63)$ とする。$67 \equiv -1 \pmod{17}$ より $k = 2$。$\mathbb{F}_{67^2} = \mathbb{F}_{67}(i)$（$i^2 = -1$）上の自己同型 $[i](x, y) = (-x, iy)$（第3章 例 3.35(1) と同じ形の自己同型）について $[i]P = (5, 2i) \notin \langle P \rangle$ なので、$E[17] \cong (\mathbb{Z}/17\mathbb{Z})^2$（第3章 定理 3.23）より $E[17] = \langle P \rangle \oplus \langle [i]P \rangle$ で、$e_{17}(P, P) = 1$ と非退化性から $e_{17}(P, [i]P) \neq 1$。定義 3.30 の値は $e_{17}(P, [i]P) = 11 - 9i$, $e_{17}(Q, [i]P) = 7 - 35i$ で、確かに $(11 - 9i)^{11} = 7 - 35i$ である。なお PARI/GP の ellweilpairing(E, P, Q, n) は定義 3.30 の $e_n(Q, P) = e_n(P, Q)^{-1}$ を返す流儀なので（第3章 定理 3.31 の後の注意）、その出力はこれらの逆数 $11 + 9i$, $7 + 35i$ になる（逆数どうしでも同じ関係式 $(11 + 9i)^{11} = 7 + 35i$ が成り立つ）。

定理 5.18（アノマラス曲線の ECDLP）$\lvert E(\mathbb{F}_p) \rvert = p$（$a_p = 1$）をみたす $E/\mathbb{F}_p$ をアノマラス曲線 (anomalous curve) という。アノマラス曲線の離散対数問題は $\log p$ の多項式時間で解ける。

1990 年代の終わりに、セマエフ、佐藤–荒木、スマートがそれぞれ独立に示した。スマートの方法の概略を述べる。

証明の概略. $p \geq 5$ とし、$E$ の係数を $\mathbb{Z}$ に持ち上げて、還元が $E$ になる $\mathbb{Q}_p$ 上の曲線 $\mathcal{E}$ を作る（判別式は $p$ 進単数なので、これは良い還元をもつ極小モデルである）。第6章の記号で、還元写像 $\mathcal{E}(\mathbb{Q}_p) \to E(\mathbb{F}_p)$ は全射準同型で核は $E_1(\mathbb{Q}_p)$ である（定理 6.13）。$z = -x/y$ について、$U_1, U_2 \in E_1(\mathbb{Q}_p)$ なら $z(U_1 + U_2) \equiv z(U_1) + z(U_2) \pmod{p^2}$ であり（命題 6.17(2)）、$U \mapsto z(U)/p \bmod p$ は単射準同型 $E_1(\mathbb{Q}_p)/E_2(\mathbb{Q}_p) \to \mathbb{F}_p$ を与える（系 6.18）。特に $[p]E_1(\mathbb{Q}_p) \subset E_2(\mathbb{Q}_p)$ で、$E_2(\mathbb{Q}_p)$ の点の $z$ は $p^2$ で割り切れる。$R \in E(\mathbb{F}_p)$ の持ち上げ $\mathcal{R} \in \mathcal{E}(\mathbb{Q}_p)$ をとると、$[p]R = O$ より $[p]\mathcal{R} \in E_1(\mathbb{Q}_p)$ である。持ち上げを $\mathcal{R} + S$（$S \in E_1(\mathbb{Q}_p)$）に替えても $[p]S \in E_2(\mathbb{Q}_p)$ なので $z([p]\mathcal{R}) \bmod p^2$ は変わらず、$\lambda(R) = z([p]\mathcal{R})/p \bmod p$ は $R$ だけで決まる。$z$ の $\bmod p^2$ での加法性から $\lambda\colon E(\mathbb{F}_p) \cong \mathbb{Z}/p\mathbb{Z} \to \mathbb{F}_p$ は準同型で、$0$ か同型である。同型なら、$Q = [m]P$ について $\lambda(Q) = m\lambda(P)$ より $m \equiv \lambda(Q)\lambda(P)^{-1} \pmod{p}$ となり、離散対数が割り算になる。$\lambda = 0$ となるのは $\mathcal{E}(\mathbb{Q}_p)$ が位数 $p$ の点をもつ特別な持ち上げの場合で、そのときは持ち上げを取り替える。$p$ 進数の計算は $p$ の小さなべきを法とする精度で足りる（細部は省略する）。$\square$

以上から、暗号に使う曲線は少なくとも、(i) ベースポイントの位数 $n$ が素数で十分大きい（128 ビットの安全性には $n \approx 2^{256}$）、(ii) 余因子 $h$ が小さい、(iii) 埋め込み次数が大きい、(iv) $n \neq p$、をみたすように選ぶ。

5.5 実際に使われている曲線

次の値は規格に載っているもので、本章の執筆にあたり PARI/GP で、$p$ と $n$ が素数であること、ベースポイント $G$ が曲線上にあること、$[n]G = O$、$\lvert E(\mathbb{F}_p) \rvert = hn$（ellcard は 5.6 節の SEA アルゴリズムを使う）を確かめた。

secp256k1（SEC 2）：ビットコインなど
  p = 2^256 - 2^32 - 977,   E : y^2 = x^3 + 7
  G = (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798,
       483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8)
  n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141,  h = 1

P-256（FIPS 186-5, SP 800-186。secp256r1 とも呼ばれる）：TLS など
  p = 2^256 - 2^224 + 2^192 + 2^96 - 1,   E : y^2 = x^3 - 3x + b
  b = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
  G = (6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296,
       4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5)
  n = FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551,  h = 1

Curve25519（RFC 7748）：TLS 1.3 の鍵共有 X25519 など
  p = 2^255 - 19,   E : y^2 = x^3 + 486662 x^2 + x（モンゴメリー形）
  ベースポイントの x 座標 = 9
  n = 2^252 + 27742317777372353535851937790883648493,  h = 8

同じく PARI/GP で確かめると、3 つとも $n \neq p$ で、埋め込み次数はそれぞれ $(n - 1)/6$, $(n - 1)/3$, $(n - 1)/6$ と巨大なので、5.4 節の攻撃は当てはまらない。$\rho$ 法の手間は約 $2^{128}$, $2^{128}$, $2^{126}$ 回である（$R$ と $-R$ を同一視するなどの改良で定数倍は縮むが、桁はほとんど変わらない）。