CRYPTREC EX-3001-2020

ディジタル署名 EdDSA で使われている曲線の安全性に関する調査及び評価
安田 雅哉（立教大学理学部）

2020 年 11 月 24 日

1

目次

第1章

本報告書の目的と構成概要

2

1.1

目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

構成概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2第2章

調査結果・評価結果の概要

3

第3章

一般の楕円曲線と Edwards 曲線における加法演算の調査

53.1

一般の楕円曲線における加法演算と座標表現 . . . . . . . . . . . . . . . . . . . .

5

3.2

Edwards 曲線とその加算公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

楕円曲線暗号に対する攻撃法調査

18

4.1

一般の楕円曲線に適用可能な攻撃法 . . . . . . . . . . . . . . . . . . . . . . . . .

18

4.2

特殊な曲線にのみ有効な攻撃法 . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.3

ECDLP に対する攻撃手法のまとめ . . . . . . . . . . . . . . . . . . . . . . . . .

28

EdDSA で利用される曲線の安全性評価と効率性に関する考察

29

5.1

EdDSA で利用される曲線に関する解説 . . . . . . . . . . . . . . . . . . . . . . .

29

5.2

EdDSA で利用される曲線に対する攻撃計算量評価 . . . . . . . . . . . . . . . . .

34

5.3

ECDSA と比較した場合の曲線としての効率性に関する考察 . . . . . . . . . . . .

38

第4章

第5章

参考文献

42

2

第1章

本報告書の目的と構成概要
1.1 目的
Edwards 曲線ディジタル署名アルゴリズム（Edwards-curve Digital Signature Algorithm,
EdDSA）とは，効率的な点の加算公式を持つ特殊な楕円曲線である Edwards 曲線またはそのツイスト曲線を利用したディジタル署名である．近年のディジタル署名 EdDSA の市場への普及を鑑み，EdDSA がディジタル署名として十分な安全性を有するか否かを判断するために，本報告書では EdDSA で利用される曲線の安全性に関する調査を行うことを目的とする.

1.2 構成概要
Edwards 曲線を利用したディジタル署名 EdDSA で利用される曲線の安全性に関わる脆弱性について，公開されている攻撃方法の有無を調査し，存在する場合はその影響の範囲などについてまとめるなど，対象となる曲線の安全性評価を実施する. 本報告書の構成概要は以下である：

 第 2 章で，本報告書における調査結果・評価結果の概要を述べる．
 第 3 章では，一般の楕円曲線における加算公式をまとめると共に，ディジタル署名 EdDSAで利用される（ツイスト）Edwards 曲線における加算公式をまとめる．

 第 4 章では，ディジタル署名を含む楕円曲線暗号の安全性を支える楕円曲線離散対数問題（Elliptic Curve Discrete Logarithm Problem, ECDLP）に対する既存の攻撃手法を調査した結果をまとめる．ただし，既存の攻撃手法の調査については，2020 年 8 月末までに公開された攻撃手法を調査対象とした．

 第 5 章では，EdDSA で利用される（ツイスト）Edwards 曲線の具体的なパラメータ選択法
について解説すると共に，暗号攻撃の観点からこれらの曲線がどの程度安全なのか解析評価する．また，通常の楕円曲線を利用するディジタル署名 ECDSA と比べて EdDSA がどの程度効率的なのか考察する．

3

第2章

調査結果・評価結果の概要■EdDSA で利用される曲線に関する解説

ディジタル署名 EdDSA では Edwards 曲線と呼ばれる特殊な楕円曲線やそのツイスト曲線を利用する. Edwards 曲線は xy 座標平面内の方程式

x2 + y 2 = 1 + dx2 y 2 (d 6= 0, 1) で定義される曲線で，その曲線上の点の加算と 2 倍算を効率的に計算することができる. RFC8032 [31] によると，EdDSA では（古典計算機による）暗号攻撃に対して約 128 ビットのセキュリティレベルの Ed25519 と約 224 ビットのセキュリティレベルの Ed448の 2 種類の実装のどちらかを安全性要件に応じて利用するよう推奨されている. また，Ed25519 では “Curve25519”，Ed448 では “Curve448”と呼ばれるツイスト Edwards 曲線パラメータを利用する. これらの曲線では，可能性のある暗号攻撃を避けるため，元の曲線とそのツイスト曲線の両方の位数が 4r または 8r （ただし，r は巨大素数）の形となるように係数パラメータが選択されている．
（ツイスト Edwards 曲線は位数 4 のねじれ点を持つので，4 以上の余因子を必ず持つことに注意する．）特に，Curve25519 は高速実装に適した 255 ビット素数 p = 2255 − 19 による素体 Fpを基礎体に持つ．
■EdDSA で利用される曲線に関して公開されている攻撃・脆弱性の調査

ディジタル署名を含む

楕円曲線暗号の安全性は楕円曲線離散対数問題 (ECDLP) の求解困難性に基づく. ECDLP に対する攻撃法は，Pollard のρ法や指数計算法などの任意の楕円曲線に適用できる汎用攻撃アルゴリズ
ムと，MOV 攻撃法や SSSA 攻撃などの特殊な楕円曲線にのみ適用可能な特殊攻撃アルゴリズムに大別される（攻撃法のまとめは 4.3 節を参照）. EdDSA で利用される Curve25519 や Curve448
では，MOV 攻撃法や SSSA 攻撃法が有効とならないような曲線パラメータが選択されているため，汎用攻撃アルゴリズムの中で最良のρ法が EdDSA に対する最良の攻撃法である.
■EdDSA で利用される曲線の安全性評価

EdDSA に対する最良の攻撃法であるρ法攻撃は誕生日の逆理に基づく確率的アルゴリズムであるが，Edwards 曲線上の ECDLP に対するρ法は通常の楕円曲線とほぼ同じ振る舞いをすることが本報告書内の実験結果（後述の図 5.2）から分かる.
これより，Edwards 曲線上の位数 r を持つ ECDLP のρ法による平均攻撃計算量は，誕生日の逆
理から

√

√
πr
· Edadd ≈ 0.8862 r · Edadd2

第 2 章 調査結果・評価結果の概要

4と見積もれる. ここで，Edadd は Edwards 曲線上の点の加算コストとする. （ただし，攻撃者有利な条件として，Edwards 曲線上の逆元計算によるCurve25519 の位数は r ≈ 2
約 0.8862 · 2

126

=2

125.8257

252√

2 倍の高速化も考慮した.）具体的には，より，Curve25519 における ECDLP を攻撃するには，平均的に回の点の加算が必要となる．また，Curve448 の位数は r ≈ 2446 より，Curve448 における ECDLP を攻撃するには，平均的に約 0.8862 · 2223 = 2222.8257 回の点の加算が必要となる．一方，128 ビットセキュリティレベルの ECDSA での利用が推奨されている P-256曲線に関して，P-256 の位数が r ≈ 2256 より，P-256 における ECDLP を攻撃するには，平均的に約 0.8862 · 2128 = 2127.8257 回の点の加算が必要となる．これより，P-256 と同程度のセキュリ
ティレベルに設定されている Curve25519 と安全性比較すると，Curve25519 上の方が平均的に約4 倍少ない回数の楕円加算で攻撃できる．さらに，ツイスト Edwards 曲線は効率的な点の加算公式を持つため，P-256 よりも Curve25519 上の方がより効率的に点の加算が可能であり，ECDLP
をより高速に攻撃できる．例えば，P-256 よりも Curve25519 の方が最大 2 倍高速に楕円加算ができたと想定すると，P-256 よりも Curve25519 における ECDLP の方が平均的に最大 8 倍高速に攻撃できる．ただし，Curve25519 における ECDLP を攻撃するには，少なくとも 2125.8257 回の楕円加算が必要であり，ほぼ 128 ビットのセキュリティレベルを持つと結論付けれる．
■ECDSA と比較した場合の曲線としての効率性に関する考察

通常の楕円曲線と Edwards 曲線

上の点の加算と 2 倍算の計算コスト比較は表 3.1 にまとめた. 具体的には，基礎体上の乗算コスト

M と 2 乗算コスト S の比が S/M = 0.8 の場合，通常の楕円曲線で標準的に利用する射影座標表
現における点の加算コストは 10.8M で 2 倍算コストは 9.8M であるのに対し，Edwards 曲線の射
影座標表現における点の加算コストは 9.8M で 2 倍算コストは 6.2M である. これより，同一の基礎体を利用した場合，射影座標表現では Edwards 曲線の方が点の加算で約 9.4%，点の 2 倍算で約 36.7% 効率的に計算できる. また，楕円曲線を利用したディジタル署名では，署名生成時に楕円曲線の点 P のスカラー倍算 nP を行い，署名検証時には楕円曲線の点 P1 , P2 の複数スカラー倍算

n1 P1 + n2 P2 を主に行う. 表 3.1 と同じように，表 5.1 に座標表現による楕円曲線上のスカラー倍
算 nP の計算コスト比較をまとめた. 表 5.1 より，同一の基礎体を利用した場合，スカラー倍算 nPに関しては Edwards 曲線の方が最大 33% 程度効率的に行うことができる. 一方，表 5.2 に座標表
現による楕円曲線上の複数スカラー倍算 n1 P1 + n2 P2 の計算コスト比較をまとめた. 表 5.2 より，同一の基礎体を利用した場合，複数スカラー倍算 n1 P1 + n2 P2 に関しても Edwards 曲線の方が最大 28% 程度効率的に行うことができることが分かる. 特に，EdDSA で利用される Curve25519
においては，高速実装に適した基礎体 Fp を選択しており，基礎体上の演算の高速化分を考慮すれば，更に効率的に（複数）スカラー倍算を行うことが可能となる. 実際，図 5.3 に P-256 曲線による ECDSA と Curve25519 による EdDSA のハードウェア実装による処理時間の比較を示す. ただし，処理時間は鍵生成・署名生成・署名検証の合計時間で，その単位は cycles 数とする（詳細は[13] を参照）. ハードウェアの実装方法により処理時間が大きく異なるため参考程度ではあるが，図 5.3 より Curve25519 による EdDSA の方が最大 2 倍程度高速であることが分かる.

5

第3章

一般の楕円曲線と Edwards 曲線における加法演算の調査
楕円曲線暗号は Koblitz [32] と Miller [37] がほぼ同時期かつ独立に考案した暗号技術で，射影平面内の斉次 3 次曲線として定義される楕円曲線上の点集合における特殊な加算法に基づき暗号化・復号を行う暗号方式である. 本章では，一般の楕円曲線における加法演算をまとめると共に，
本報告書の調査対象である EdDSA で利用される Edwards 曲線における加法演算をまとめる.

3.1 一般の楕円曲線における加法演算と座標表現
本節では，一般の楕円曲線の加法演算をまとめる. 特に，楕円曲線暗号で利用される代表的な座
標表現とその表現における加法演算についてまとめる.

3.1.1 楕円曲線における加法演算
標数 p ≥ 5 の体 k 上の楕円曲線は（短い）Weierstrass 方程式

E : y 2 = x3 + ax + b (a, b ∈ k, ∆(E) = 4a3 + 27b2 6= 0)(3.1)

で表せる*1 . 無限遠点 ∞ を含めた楕円曲線 E 上の点の集合全体は，次で定義する加法演算において可換群をなす（証明は [51, 56] などを参照）：(i) 無限遠点 ∞ と無限遠点を含めた E 上の任意の点 P との加算について P + ∞ = ∞ + P = Pと定める. （つまり，無限遠点 ∞ が群における零元の役割を果たす.）(ii) 無限遠点ではない E 上の点 P = (x, y) の逆元を −P = (x, −y) と定める. (一方，無限遠点∞ の逆元は ∞ 自身と定める.)(iii) 無限遠点ではない E 上の 2 つの点 P1 = (x1 , y1 ), P2 = (x2 , y2 ) が P1 6= −P2 を満たすとする. このとき，2 つの点 P1 と P2 の加算点 P3 = P1 + P2 = (x3 , y3 ) の座標を以下で定める：*1∆(E) は楕円曲線の判別式であり，∆(E) = 0 の場合は曲線が特異点を持つ．

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

6

 P1 6= P2 の場合*2 ：y2 − y1x = m2 − x − x
m=
,
3
1
2
x2 − x1y3 = m(x1 − x3 ) − y1 .

(3.2)

 P1 = P2 の場合：y1 = 0 なら P3 = ∞ と定める. 一方，y1 6= 0 なら，P1 の 2 倍点

P3 = 2P1 = (x3 , y3 ) の座標を以下で定める：
x = m2 − 2x31
 y = m(x − x ) − y .
3
1
3
1



3x21 + a
m=
,
2y1

(3.3)

特に，無限遠点ではない E 上の 2 つの点 P1 = (x1 , y1 ), P2 = (x2 , y2 ) の座標 xi , yi (i = 1, 2) が体k の元であれば，P1 と P2 の加算点 P3 = (x3 , y3 ) の座標 x3 , y3 も体 k の元である. ここで，体 kの座標を持つ楕円曲線 E 上のすべての点に無限遠点を含めた集合をE(k) = (x, y) ∈ k 2 : y 2 = x3 + ax + b ∪ {∞}とする. このとき，上記で定めた楕円曲線上の加法演算により，集合 E(k) は可換群となる.

3.1.2 楕円曲線における代表的な座標表現とその加算公式
楕円曲線の点の表現を変更することで，楕円曲線上の加法演算を効率的に行うことができる．ここでは，楕円曲線における代表的な座標系とその点の表現での加法演算の代表例を紹介する．

2 つの正の整数 c, d を用いて，集合 k 3 \ {(0, 0, 0)} における同値関係を次のように定める：2 つの元 (X1 , Y1 , Z1 ), (X2 , Y2 , Z2 ) ∈ k 3 \ {(0, 0, 0)} に対して，(X1 , Y1 , Z1 ) ∼ (X2 , Y2 , Z2 ) ⇐⇒ X1 = λc X2 , Y1 = λd Y2 , Z1 = λZ2 (∃λ ∈ k × )と定める．元 (X, Y, Z) を含む同値類を (X : Y : Z) =
λc X, λd Y, λZ : λ ∈ k × と表し，射影点と呼ぶ*3 . すべての射影点の集合を射影平面と呼び，P2 (k) と表す．特に，射影平面 P2 (k) の部
分集合
P2 (k)∗ = (X : Y : Z) ∈ P2 (k) : Z 6= 0と座標平面上の点集合と 1 対 1 に対応する．具体的には，座標平面上の点 (x, y) は射影点 (x : y : 1)に対応する．逆に，Z 6= 0 なる射影点 (X : Y : Z) は座標平面上の点 (X/Z c , Y /Z d ) に対応させる．この座標平面上と射影平面における対応を利用することで，座標平面上の代数方程式 (3.1) で定義される楕円曲線を射影平面内の曲線として楕円曲線を表すことができる．以下で，射影平面内
で定義される楕円曲線とその加法演算の代表例を紹介する：*2

幾何学的なイメージ図については，[51, Figure 3.3 in Chapter III] を参照. また，通常の Weierstrass 方程式で定義される楕円曲線上の点の加算公式については，[51, Section III.2] を参照.
*3 逆に言い換えると，元 (X, Y, Z) は射影点 (X : Y : Z) の代表元である．

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

7■（標準）射影座標表現 c = d = 1 とする．この場合，座標平面上の Weierstrass 方程式 (3.1) で定義される楕円曲線は，（標準）射影平面内の（斉次）3 次曲線

E : Y 2 Z = X 3 + aXZ 2 + bZ 3

(3.4)

として表せる．特に，Z = 0 を満たす E 上の射影点は (0 : 1 : 0) のみであり，楕円曲線の無限
遠点 ∞ を射影点 (0 : 1 : 0) に対応させておく．これにより，楕円曲線の点の加算が定まる. 具
体的に，楕円曲線 E 上の 2 つの射影点を P1 = (X1 : Y1 : Z1 ) と P2 = (X2 : Y2 : Z2 ) とし，その加算点を P3 = P1 + P2 = (X3 : Y3 : Z3 ) とする.（特に，各射影点 Pi は方程式 (3.4) を満た
す.）このとき，Weierstrass 方程式で表現された楕円曲線の加算公式 (3.2) と 2 倍算公式 (3.3) より，射影点 P3 = P1 + P2 の各射影座標 X3 , Y3 , Z3 は以下で定まる（ただし，楕円曲線上の射影点

P = (X : Y : Z) の逆元は −P = (X : −Y : Z) となる.）： P1 6= ±P2 の場合(
u = Y2 Z1 − Y1 Z2 ,X3 = vw,
 P1 = P2 の場合(

v = X2 Z1 − X1 Z2 ,w = u2 Z1 Z2 − v 3 − 2v 2 X1 Z2 ,Y3 = u(v 2 X1 Z2 − w) − v 3 Y1 Z2 ,t = aZ12 + 3X12 ,X3 = 2uw,

u = Y1 Z1 ,

Z 3 = v 3 Z1 Z2 .

v = uX1 Y1 ,Y3 = t(4v − w) − 8Y12 u2 ,w = t2 − 8v,

Z3 = 8u3 .

 P1 = −P2 の場合は P3 = P1 + P2 = (0 : 1 : 0) となる.
特に，Weierstrass 方程式の表現による公式 (3.2) と (3.3) では割り算の操作が必要なのに対し，上記の射影座標による表現では割り算が一切必要ない. また，計算の順序を工夫することで，射影座
標による点の加算 P1 + P2 では（体 k における演算として）12 回の乗算と 2 回の 2 乗算を必要とし，点の 2 倍算 2P1 では 5 回の乗算と 6 回の 2 乗算を必要とする [11].
■Jacobi 座標表現

c = 2, d = 3 とする．この場合，座標平面上の Weierstrass 方程式 (3.1) で定義される楕円曲線は，射影平面内の方程式

E : Y 2 = X 3 + aXZ 4 + bZ 6として表せる. 特に，Z = 0 を満たす E 上の射影点は (1 : 1 : 0) が代表的で，楕円曲線の無限遠点∞ を射影点 (1 : 1 : 0) に対応させておく. これにより，楕円曲線の点の加算が定まる. 具体的に，楕円曲線 E 上の 2 つの射影点を P1 = (X1 : Y1 : Z1 ) と P2 = (X2 : Y2 : Z2 ) とし，その加算点をP3 = P1 + P2 = (X3 : Y3 : Z3 ) とする. このとき，Weierstrass 方程式で表現された楕円曲線の加算公式 (3.2) と 2 倍算公式 (3.3) より，射影点 P3 = P1 + P2 の各射影座標 X3 , Y3 , Z3 は以下で定まる（ただし，楕円曲線上の射影点 P = (X : Y : Z) の逆元は −P = (X : −Y : Z) となる.）：

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

 P1 6= ±P2 の場合(
r = X1 Z22 ,s = X2 Z12 ,

X3 = −v 3 − 2rv 2 + w2 ,
 P1 = P2 の場合(

v = 4X1 Y12 ,t = Y1 Z23 ,u = Y2 Z13 ,8v = s − r,

Y3 = −tv 3 + (rv 2 − X3 )w,

w = u − t,

Z3 = vZ1 Z2 .

w = 3X12 + aZ14 ,X3 = −2v + w2 ,Y3 = −8Y14 + (v − X3 )w,

Z3 = 2Y1 Z1 .

 P1 = −P2 の場合は P3 = P1 + P2 = (1 : 1 : 0) となる.
上述の標準射影座標と同様に，Jacobi 座標による表現では体 k における割り算が一切必要ない. また，計算の順序を工夫することで，Jacobi 座標による点の加算 P1 + P2 では 11 回の乗算と 5 回の2 乗算を必要とし，点の 2 倍算 2P1 では 1 回の乗算と 8 回の 2 乗算を必要とする [11].

3.2 Edwards 曲線とその加算公式
標数が 2 以外の体を k とする. xy 座標平面における方程式

C : x2 + y 2 = c2 (1 + dx2 y 2 )(c, d ∈ k, cd(c4 d − 1) 6= 0)(3.5)

で定義される曲線を（一般化された）Edwards 曲線という*4 . この曲線 C は，変数変換u = −2c(w − c) (w = (c2 dx2 − 1)y)x2
4c2 (w − c) + 2c(c4 d + 1)x2

v =
x3
を通して，uv 座標平面における Weierstrass 方程式

v 2 = (u − c4 d − 1)(u2 − 4c4 d)で定まる楕円曲線と同型である [56, Proposition 2.18]. （特に，対応する楕円曲線の判別式が 0 以外となるためには条件 c4 d 6= 1 が必要である.）この楕円曲線との同型により，曲線 C 上の点集合
は群をなす. 具体的には，曲線 C 上の点集合における群法則において点 (0, c) は零元であり，曲線

C 上の 2 点 P1 = (x1 , y1 ), P2 = (x2 , y2 ) の加算点は

x1 y2 + x2 y1
y1 y2 − x1 x2
P1 + P2 =,c(1 + dx1 x2 y1 y2 ) c(1 − dx1 x2 y1 y2 )(3.6)

で与えられる. また，曲線 C 上の点 (x, y) の逆元は (−x, y) で与えられる. 特に，この加算公式では 2 倍算 2P と異なる 2 点の加算 P1 + P2 の区別なく計算できる.

*4

Edwards [20] が d = 1 の場合の曲線を紹介した後，その一般形である方程式 (3.5) が [9] で紹介されている.

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

93.2.1 射影座標表現による加算公式
加算演算 (3.6) を効率的に行うために，3.1.2 節で説明した（標準）射影座標表現を Edwards 曲
線 C に適用する. 方程式 (3.5) で定義される Edwards 曲線 C 上の点 (x, y) を射影平面 P2 内の斉次 4 次曲線(X 2 + Y 2 )Z 2 = c2 (Z 4 + dX 2 Y 2 )(3.7)

上の射影点 (X : Y : Z) に対応させる. ただし，任意の λ 6= 0 に対し (X : Y : Z) = (λX : λY : λZ)
Yを満たし，Z 6= 0 の射影点 (X : Y : Z) を x = X
Z , y = Z に対応させる. このとき，Edwards 曲線上の群の零元は射影点 (0 : c : 1) で，(X : Y : Z) の逆元は (−X : Y : Z) で与えられる. 以下に，
この射影座標表現による Edwards 曲線上の加算公式の具体的な計算手順を示す [9, Section 4]：■加算 方程式 (3.7) で定まる射影座標表現による Edwards 曲線上の 2 つの射影点 (X1 : Y1 : Z1 ),(X2 : Y2 : Z2 ) の加算点 (X3 : Y3 : Z3 ) は以下の手順で計算できる：
2
 A = Z1 · Z2 ; B = A ; C = X1 · X2 ; D = Y1 · Y2 ; E = dC · D;
F = B − E; G = B + E; X3 = A · F · ((X1 + Y1 ) · (X2 + Y2 ) − C − D) ;
Y3 = A · G · (D − C); Z3 = cF · G.

(3.8)

体 k 上の 1 回の乗算コストを M，2 乗算コストを S，定数 c, d を掛ける計算コストをそれぞれC, D，加減算コストを add とする. このとき，上記の計算コストは 10M + 1S + 1C + 1D + 7addである. 特に，X1 Y2 + X2 Y1 は (X1 + Y1 )(X2 + Y2 ) − X1 X2 − Y1 Y2 と表し，X1 X2 や Y1 Y2 などの項を演算中に使いまわすことで計算の効率化を図っている.
特に Z2 = 1 の場合は一回の乗算 A = Z1 · Z2 の計算コストを省ける. ゆえに，この場合の計算コストは 9M + 1S + 1C + 1D + 7add である.
■2 倍算

ここでは (X1 : Y1 : Z1 ) = (X2 : Y2 : Z2 ) の場合を考える. この場合，曲線 C の方程式

(3.5) を利用することで，c(1 + dx21 y12 ) を (x21 + y12 )/c，c(1 − dx21 y12 ) を (2c2 − (x21 + y12 ))/c とそ
れぞれ表せる. これより，(3.6) による 2 倍算公式は

2(x1 , y1 ) =とかける.

2x1 y1y12 − x21,
c(1 + dx21 y12 ) c(1 − dx21 y12 )=(y12 − x21 )c
2x1 y1 c,
x21 + y12 2c2 − (x21 + y12 )


(3.9)

これより，方程式 (3.7) で定まる射影座標表現による Edwards 曲線上の射影点(X1 : Y1 : Z1 ) の 2 倍点 (X3 : Y3 : Z3 ) は以下の手順で計算できる：(
B = (X1 + Y1 )2 ; C = X12 ; D = Y12 ; E = C + D; H = (cZ1 )2 ;J = E − 2H; X3 = c(B − E) · J; Y3 = cE · (C − D); Z3 = E · J.

(3.10)

この計算コストは 3M + 4S + 3C + 6add である.（ただし，2H は H + H と計算する.）特に，

2X1 Y1 を (X1 + Y1 )2 − X12 − Y12 と表し，(X1 + Y1 )2 ，X12 や Y12 の項を演算中に使いまわすこと
で計算の効率化を図っている.

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

10

表 3.1 様々な座標表現による楕円曲線上の加算と 2 倍算の計算コスト比較 [9, Section 5]（各座標表現による具体的な計算手順とその計算コストについては [11] を参照）

座標表現

加算 (Z2 = 1 の時)

加算

2 倍算

計算コスト

S/M = 0.8

計算コスト

S/M = 0.8

計算コスト

S/M = 0.8

(1)

12M + 2S

13.6M

9M + 2S

10.6M

5M + 6S

9.8M(2)

11M + 5S

15M

7M + 4S

10.2M

1M + 8S

7.4M(3)

10M + 3S

12.4M

8M + 3S

10.4M

2M + 6S

6.8M(4)

13M + 2S

14.6M

11M + 2S

12.6M

3M + 4S

6.2M

(5)

12M

12M

10M

10M

7M + 1S

7.8M(6)

12M + 5S

16M

8M + 4S

11.2M

2M + 5S

6M(7)

11M + 6S

15.8M

7M + 4S

10.2M

2M + 7S

7.6M(8)

10M + 1S

10.8M

9M + 1S

9.8M

3M + 4S

6.2M(1)

Projective: 無限遠点 ∞ が零元の楕円曲線 y 2 = x3 + ax + b 上の点 (x, y) を Y 2 Z =X 3 + aXZ 2 + bZ 3 上の点 (X : Y : Z) に対応させる. 任意の λ 6= 0 に対し (X : Y : Z) =Y
(λX : λY : λZ) を満たし，Z 6= 0 で x = X
Z , y = Z に対応させる.（3.1.2 節を参照）(2)

Jacobi: 無限遠点 ∞ が零元の楕円曲線 y 2 = x3 + ax + b 上の点 (x, y) を Y 2 = X 3 +aXZ 4 + bZ 6 上の点 (X : Y : Z) に対応. 任意の λ 6= 0 に対し (X : Y : Z) = (λ2 X : λ3 Y :λZ) を満たし，Z 6= 0 において x = ZX2 , y = ZY3 に対応させる.（3.1.2 節を参照）(3)

Jacobi quartic:

点 (0, 1) が零元の楕円曲線 y 2 = x4 + 2ax2 + 1 上の点 (x, y) をY 2 = X 4 + 2aX 2 Z 2 + Z 4 上の点 (X : Y : Z) に対応させる. 任意の λ 6= 0 に対しY(X : Y : Z) = (λX : λ2 Y : λZ) を満たし，Z 6= 0 で x = X
Z , y = Z 2 に対応.
(4)

Jacobi intersection: 点 (0, 1, 1) が零元の楕円曲線 s2 + c2 = 1, as2 + d2 = 1 上の点(s, c, d) を S 2 + C 2 = Z 2 , aS 2 + D2 = Z 2 上の点 (S : C : D : Z) に対応にさせる. 任意のS
λ 6= 0 に対し (S : C : D : Z) = (λS : λC : λD : λZ) を満たし，Z 6= 0 において s = Z,D
c= C
Z , d = Z に対応させる.
(5)

Hessian: 無限遠点 ∞ が零元の楕円曲線 x3 + y 3 + 1 = 3axy 上の点 (x, y) を X 3 + Y 3 +

Z 3 = 3aXY Z 上の点 (X : Y : Z) に対応させる. 任意の λ 6= 0 に対し (X : Y : Z) = (λX :Y
λY : λZ) を満たし，Z 6= 0 において x = X
Z , y = Z に対応.
(6)

Doubling-oriented Doche/Icart/Kohel: 無限遠点 ∞ が零元の楕円曲線 y 2 = x3 +ax2 + 16ax 上の点 (x, y) を Y 2 = X 3 Z + aX 2 Z 2 + 16aXZ 3 上の点 (X : Y : Z : Z 2 ) に対応させる. 任意の λ 6= 0 に対し (X : Y : Z : Z 2 ) = (λX : λ2 Y : λZ : λ2 Z 2 ) を満たし，
Y
Z 6= 0 において x = X
Z , y = Z 2 に対応させる.
(7)

Tripling-oriented Doche/Icart/Kohel: 無限遠点 ∞ が零元の楕円曲線 y 2 = x3 +3a(x + 1)2 上の点 (x, y) を Y 2 = X 3 Z + 3a(X + Z)2 Z 2 上の点 (X : Y : Z : Z 2 ) に対応させる. 任意の λ 6= 0 に対し (X : Y : Z : Z 2 ) = (λ2 X : λ3 Y : λZ : λ2 Z 2 ) を満たし，Z 6= 0
において x = ZX2 , y = ZY3 に対応させる.
(8)

Edwards: 射影座標表現による c = 1 の Edwards 曲線上の加算公式.（3.2.1 節を参照）

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査■他の座標表現による楕円曲線上の加算コストとの比較

11

表 3.1 に，上述した射影座標表現による

Edwards 曲線上の加算 (3.8)・2 倍算 (3.10) と他の座標表現による様々な加算公式の計算コストの比較表を示す. （詳細は [9, Section 5] を参照. また，各座標表現による具体的な計算手順とその計算コストについては [11] を参照.）今回の比較では，計算コストが小さい定数 c, d との掛け算コスト C, D や体 k 上の加減算コスト add は無視し，乗算コスト M と 2 乗算コスト S のみで比較する. 表 3.1 から，2 乗算と乗算のコスト比率が S/M = 0.8 の時，他の座標表現に比べて射影座標
表現による Edwards 曲線上の加算の計算コストが最も小さいことが分かる. また，2 倍算に関しても Edwards 曲線上の計算コストはかなり小さいことが分かる（ただし，最も小さいわけではない）. このように計算コストの観点から Edwards 曲線の利用は非常に有用である.

3.2.2 反転座標表現による加算公式
簡単のため，これ以降は c = 1 の場合の Edwards 曲線

Ed : x2 + y 2 = 1 + dx2 y 2(d ∈ k, d 6= 0, 1)(3.11)

を扱う. ここでは，Edwards 曲線上の点 (x, y) を射影平面 P2 内の斉次 4 次曲線(X 2 + Y 2 )Z 2 = X 2 Y 2 + dZ 4

(3.12)

上の射影点 (X : Y : Z) に対応させる. 具体的には，任意の λ 6= 0 に対し (X : Y : Z) = (λX :λY : λZ) を満たすが，前述の射影座標表現を反転させて，XY Z 6= 0 を満たす射影点 (X : Y : Z)Z
をx= X
, y = YZ に対応させる. ただし，対応する射影点に関する制限条件 XY Z 6= 0 により，

xy = 0 を満たす Edwards 曲線 (3.11) 上の点 (x, y) はこの反転座標では表現できないことに注意する必要がある. 具体的には，xy = 0 を満たす Edwards 曲線上の零元 (0, 1)，位数 2 の点 (0, ±1)，
位数 4 の点 (±1, 0) は反転座標では表せないため，以下で紹介する反転座標表現における Edwards
曲線上の加算公式ではこれらの特別な点は除外する（詳細は [10, Section 4] を参照）：
■加算

反転座標表現による Edwards 曲線 (3.12) 上の制約条件 Xi Yi Zi 6= 0 (i = 1, 2) を満たす

2 つの射影点を (X1 : Y1 : Z1 ), (X2 : Y2 : Z2 ) とし，その加算点を (X3 : Y3 : Z3 ) とする. このとき，Edwards 曲線上の加算公式 (3.6) と反転座標表現により，



Z1 Z1
,
X1 Y1




+

Z2 Z2
,
X2 Y2




=

(X2 Y1 + X1 Y2 )Z1 Z2 (X1 X2 − Y1 Y2 )Z1 Z2,
X1 X2 Y1 Y2 + dZ12 Z22 X1 X2 Y1 Y2 − dZ12 Z22が成り立つ. ただし，

2 2

X3 = (X1 X2 − Y1 Y2 )(X1 X2 Y1 Y2 + dZ1 Z2 )Y3 = (X2 Y1 + X1 Y2 )(X1 X2 Y1 Y2 − dZ12 Z22 )

Z3 = (X1 X2 − Y1 Y2 )(X2 Y1 + X1 Y2 )Z1 Z2




=

Z3 Z3
,
X3 Y3



第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査12とする. また，反転座標表現による加算点 (X3 : Y3 : Z3 ) の効率的な計算手順は以下である：

2 A = Z1 · Z2 ; B = dA ; C = X1 · X2 ; D = Y1 · Y2 ; E = C · D;
H = C − D; I = (X1 + Y1 ) · (X2 + Y2 ) − C − D;
X3 = (E + B) · H; Y3 = (E − B) · I; Z3 = A · H · I.

(3.13)

この計算コストは 9M + 1S + 1D + 7add で，前述した射影座標表現による加算の計算コスト

10M + 1S + 1D + 7add より少ない. （ここでは，Edwards 曲線の係数として c = 1 と設定しているため，定数 c を掛ける計算コストは C = 0 であることに注意する.）■2 倍算

反転座標表現による Edwards 曲線 (3.12) 上の制約条件 X1 Y1 Z1 6= 0 を満たす射影点を(X1 : Y1 : Z1 ) とし，その 2 倍点を (X3 : Y3 : Z3 ) とする. このとき，Edwards 曲線上の 2 倍算公式 (3.9) と反転座標表現により，


2

Z1 Z1
,
X1 Y1

が成り立つ. ただし，

=

X12 − Y12
2X1 Y1,
X12 + Y12 X12 + Y12 − 2dZ12




=

Z3 Z3
,
X3 Y3




X = (X12 + Y12 )(X12 − Y12 ) 3
Y3 = 2X1 Y1 (X12 + Y12 − 2dZ12 )

Z3 = 2X1 Y1 (X12 − Y12 )とする. また，反転座標表現による 2 倍点 (X3 : Y3 : Z3 ) の効率的な計算手順は以下である：(

A = X12 ; B = Y12 ; C = A + B; D = A − B; E = (X1 + Y1 )2 − C;

Z3 = D · E; X3 = C · D; Y3 = E · (C − 2dZ12 ).

(3.14)

この計算コストは 3M + 4S + 1D + 6add である. （ただし，2dZ12 は dZ12 + dZ12 と計算する.）前
述した射影座標表現による 2 倍算の計算コスト 3M + 4S + 6add と比べて，この計算コストは定数 d を掛ける計算コスト D が 1 回分多いことが分かる.
以上の議論から，射影座標表現に比べて，反転座標表現による Edwards 曲線上の加算は乗算コ
スト M が 1 回分少ない一方，2 倍算では定数 d を掛ける計算コスト D が一回分多いというトレードオフの関係にある（後述の表 3.2 を参照）.

3.2.3 ツイスト Edwards 曲線
方程式 (3.11) で定義される Edwards 曲線の集合を拡張するために，ここでは Edwards 曲線の（2 次）ツイストを紹介する. 方程式

Ea,d : ax2 + y 2 = 1 + dx2 y 2(a 6= 0, d 6= 0, a 6= d)(3.15)

で定義される曲線をツイスト Edwards 曲線という [5]. 特に，a = 1 の場合の曲線 E1,d は通常のEdwards 曲線 (3.11) である. 変数変換 x̄ =√ax, ȳ = y により，ツイスト Edwards 曲線 Ea,d は

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

13√

通常の Edwards 曲線 E1,d/a : x̄2 + ȳ 2 = 1 + (d/a)x̄2 ȳ 2 と拡大体 k( a) 上で同型である*5 . （特に，元 a が体 k 上平方である場合は，これら 2 つの曲線は体 k 上で同型である.）この同型により，ツイスト Edwards 曲線上の点集合は群をなす*6 . 具体的に，ツイスト Edwards 曲 Ea,d 上の加算



公式は(x1 , y1 ) + (x2 , y2 ) =で与えられる. 実際，変数変換 x̄ =√x1 y2 + y1 x2
y1 y2 − ax1 x2,
1 + dx1 x2 y1 y2 1 − dx1 x2 y1 y2

(3.16)

ax, ȳ = y を経由して，通常の Edwards 曲線 E1,d/a 上の加算公式 (3.6) と一致する. 以下で，通常の Edwards 曲線と同様に，効率的な加算計算を可能とする
ツイスト Edwards 曲線上の座標表現をまとめておく（詳細は [5, Section 6] を参照）：■ツイスト Edwards 曲線における射影座標表現

3.2.1 節と同様に，ツイスト Edwards 曲線 Ea,d

上の点 (x, y) を射影平面 P 内の斉次 4 次曲線2(aX 2 + Y 2 )Z 2 = Z 4 + dX 2 Y 2(3.17)

上の射影点 (X : Y : Z) に対応させる．特に，λ 6= 0 に対し，(X : Y : Z) = (λX : λY : λZ) を満Yたし，Z 6= 0 で x = X
Z , y = Z に対応させる．この射影座標表現により，ツイスト Edwards 曲線

Ea,d 上の加算公式 (3.16) は下記のように計算できる：
 加算：方程式 (3.17) で定義される射影座標表現によるツイスト Edwards 曲線上の 2 つの射
影点 (X1 : Y1 : Z1 ), (X2 : Y2 : Z2 ) の加算点を (X3 : Y3 : Z3 ) とする. このとき，加算点(X3 : Y3 : Z3 ) は次の計算手順で求まる：
2 A = Z1 · Z2 ; B = A ; C = X1 · X2 ; D = Y1 · Y2 ; E = dC · D;
F = B − E; G = B + E; X3 = A · F · ((X1 + Y1 ) · (X2 + Y2 ) − C − D) ;
Y3 = A · G · (D − aC); Z3 = F · G.

(3.18)

この計算コストは 10M + 1S + 2D + 7add である. （ただし，2D は定数 a と d を掛ける

2 回の計算コストとする.）
 2 倍算：射影点 (X1 : Y1 : Z1 ) の 2 倍点 (X3 : Y3 : Z3 ) は次の計算手順で求まる：(
B = (X1 + Y1 )2 ; C = X12 ; D = Y12 ; E = aC; F = E + D; H = Z12 ;J = F − 2H; X3 = (B − C − D) · J; Y3 = F · (E − D); Z3 = F · J.

(3.19)

この計算コストは 3M + 4S + 1D + 7add である. （ただし，D は定数 a を掛ける 1 回の計算コストとし，2H は H + H と計算する.）*5

さらに，ツイスト Edwards 曲線 Ea,d は Ed,a の 2 次ツイストである．実際，有理写像 (x, y) 7−→)(
x, y1 はEa,d と Ed,a の間の双有理同値を与える. より一般には，d′ /a′ = a/d であれば，Ea,d は Ea′ ,d′ の 2 次ツイスト
である [5, Section 2]．
16(a2 + 14ad + d2 )36*
ツイスト Edwards 曲線を楕円曲線と見なすとき，その j-不変量はである．
ad(a − d)4

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

14

表 3.2 座標表現による通常/ツイスト Edwards 曲線上の加算と 2 倍算の計算コスト比較

Edwards 曲線の種類

方程式 (3.11) で定義される
通常 Edwards 曲線

方程式 (3.15) で定義されるツイスト Edwards 曲線

座標表現
射影座標
反転座標

射影座標
反転座標

■ツイスト Edwards 曲線における反転座標表現

加算

2 倍算

10M + 1S + 1D

3M + 4S計算手順 (3.8)

計算手順 (3.10)

9M + 1S + 1D

3M + 4S + 1D

計算手順 (3.13)

計算手順 (3.14)

10M + 1S + 2D

3M + 4S + 1D

計算手順 (3.18)

計算手順 (3.19)

9M + 1S + 2D

3M + 4S + 2D

計算手順 (3.21)

計算手順 (3.22)

3.2.2 節と同様に，ツイスト Edwards 曲線 Ea,d

上の点 (x, y) を射影平面 P 内の斉次 4 次曲線2(X 2 + aY 2 )Z 2 = X 2 Y 2 + dZ 4

(3.20)

上の射影点 (X : Y : Z) に対応させる. 上記の射影座標表現とは異なり，XY Z 6= 0 を満たす射影
Z
点 (X : Y : Z) を x = X, y = YZ に対応させる．（3.2.2 節で説明したように，下記で紹介する加算

公式では XY Z = 0 を満たす特殊な射影点 (X : Y : Z) は除外する.） 加算：方程式 (3.20) で定義される反転座標表現によるツイスト Edwards 曲線上の 2 つの射
影点 (X1 : Y1 : Z1 ), (X2 : Y2 : Z2 ) の加算点を (X3 : Y3 : Z3 ) とする. このとき，加算点(X3 : Y3 : Z3 ) は次の計算手順で求まる：
2 A = Z1 · Z2 ; B = dA ; C = X1 · X2 ; D = Y1 · Y2 ; E = C · D;
H = C − aD; I = (X1 + Y1 ) · (X2 + Y2 ) − C − D;
X3 = (E + B) · H; Y3 = (E − B) · I; Z3 = A · H · I.

(3.21)

この計算コストは 9M + 1S + 2D + 7add である．（ただし，2D は定数 a と d を掛ける 2
回の計算コストとする.）

 2 倍算：射影点 (X1 : Y1 : Z1 ) の 2 倍点 (X3 : Y3 : Z3 ) は次の計算手順で求まる：(
A = X12 ; B = Y12 ; U = aB; C = A + U ; D = A − U ;E = (X1 + Y1 )2 − A − B; X3 = C · D; Y3 = E · (C − 2dZ12 ); Z3 = D · E.

(3.22)

この計算コストは 3M + 4S + 2D + 6add である．
（ただし，2D は定数 a と 2d を掛ける 2
回の計算コストとする.）

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査■座標表現による通常/ツイスト Edwards 曲線上の計算コストの比較

15
表 3.2 に，座標表現による

通常/ツイスト Edwards 曲線上の加算と 2 倍算の計算コストの比較表を示す（[5, Section 7] も参照）. 表 3.2 から通常/ツイストの Edwards 曲線共に，加算は一回の乗算コスト M の分だけ反転座
標表現の方が効率的である一方，2 倍算に関しては一回の定数を掛ける計算コスト D の分だけ射影
座標表現の方が効率的であることが分かる．また，ツイスト Edwards 曲線よりも通常 Edwards 曲
線の方が加算・2 倍算共に一回の定数を掛ける計算コスト D の分だけ効率的であることが分かる．

3.2.4 Montgomery 曲線とツイスト Edwards 曲線との関係
ここでは，楕円曲線の点のスカラー倍算を効率的に計算できる Montgomery 曲線を紹介すると共に，ツイスト Edwards 曲線との関係をまとめる.
■Montgomery 曲線

uv 座標平面における方程式(M )EA,B : Bv 2 = u3 + Au2 + u (A, B ∈ k, B(A2 − 4) 6= 0)(3.23)

で定義される曲線を Montgomery 曲線という（詳細は [22, Section 9.12.1] や [19, Section 13.2.3]などを参照）．単純な変数変換 x = Bu, y = B 2 v により，方程式 (3.23) は Weierstrass 方程式

y 2 = x3 + ABx2 + B 2 xに変換できるため，Montgomery 曲線は楕円曲線の一種であることが分かる．
（特に，上記の楕円曲線の判別式が 16B 6 (A2 −4) であるため，対応する楕円曲線が特異点を持たないように Montgomery
曲線の係数に関する条件 B(A2 − 4) 6= 0 が必須である．）ゆえに，対応する楕円曲線の加算公式
を用いることで，Montgomery 曲線上の点集合は群をなす．特に，Montgometry 曲線においては
点 P のスカラー倍算を効率的に計算できる．（標準）射影座標表現により，P = (U1 : V1 : W1 ),nP = (Un : Vn : Wn ) と表す．このとき，スカラー倍点 (n + m)P = nP + mP の射影座標(Un+m : Vn+m : Wn+m ) は次の計算式から，逐次的に求めることが可能である（下記の逐次的な計算において Vn の値は一切必要ない）：

 n 6= m の場合(
2
Um+n = Wm−n ((Um − Wm )(Un + Wn ) + (Um + Wm )(Un − Wn )) ,2

Wm+n = Um−n ((Um − Wm )(Un + Wn ) − (Um + Wm )(Un − Wn )) .
加減算コストを無視すると，この計算コストは 4M + 2S である．

 n = m の場合


4U W = (Un + Wn )2 − (Un − Wn )2 ,
 n n
U2n = (Un + Wn )2 (Un − Wn )2 ,

W2n = 4Un Wn (Un − Wn )2 + ((A + 2)/4)(4Un Wn ) .
計算手順を工夫すると，この計算コストは 3M + 2S である（加減算コストは無視する）．

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

16

これらの計算式から，次のスカラー倍算における Montgomery 乗法公式を得る [17, Chapter 4]：










U2n = (Un − Wn )2 (Un + Wn )2 ,W2n = (Un +Wn ) −(Un −Wn )
2

2







A−2
2
2
(Un +Wn ) −(Un −Wn ),(Un +Wn ) +
4
2


2


U2n+1 = ((Un − Wn )(Un+1 + Wn+1 ) + (Un + Wn )(Un+1 − Wn+1 )) W1 ,




2
W2n+1 = ((Un − Wn )(Un+1 + Wn+1 ) + (Un + Wn )(Un+1 − Wn+1 )) U1 .

(3.24)■ツイスト Edwards 曲線との関係 Montgomery 曲線全体とツイスト Edwards 曲線全体との間には次の関係がある [5, Theorem 3.2]（また，[17, Chapter 4] も参照）：
定理 3.2.1. 標数が 2 でない体を k とする. このとき，以下が成り立つ：(M )(i) すべての k 上のツイスト Edwards 曲線 Ea,d は Montgomery 曲線 EA,B に体 k 上双有理同(M )値*7 である．ただし，対応する Montgomery 曲線 EA,B の定義方程式の係数はA=

2(a + d)
,
a−d

B=

4
a−d

とする. 具体的には，k 上定義された 2 つの有理写像

(M )Ea,d −→ EA,B ;(M )EA,B −→ Ea,d ;1+y 1+y(x, y) 7−→,
1 − y (1 − y)x


u u−1
(u, v) 7−→
,
v u+1



は双有理同値を与える．
(M )(ii) 逆に，すべての k 上の Montgomery 曲線 EA,B はツイスト Edwards 曲線 Ea,d に体 k 上双有理同値である. ただし，対応するツイスト Edwards 曲線 Ea,d の定義方程式の係数は

a=

A+2
,
B

d=

A−2
B

とする. （具体的には，上記 (i) と同様の有理写像により双有理同値となる.）

3.2.2 節で紹介したように，すべての（ツイスト）Edwards 曲線は位数 4 のねじれ点を持つ. （ツイスト Edwards 曲線との双有理同値性から，すべての Montgomery 曲線も位数 4 のねじれ点を持つ.）一方で，位数 4 のねじれ点を持つ楕円曲線に関して以下が知られている [9, Theorem 2.1]：
定理 3.2.2. 標数が 2 でない体 k 上の楕円曲線 E が k-有理な位数 4 のねじれ点を持つとする．このとき，以下が成り立つ：(i) 通常 Edwards 曲線 x2 + y 2 = 1 + dx2 y 2 が E の 2 次ツイストと k 上双有理同値になるような元 d ∈ k \ {0, 1} が存在する.
*7 双有理同値とは，ほとんど至るところ定義された 2 つの有理写像が存在し，互いに逆写像の関係にあるときをいう.

第 3 章 一般の楕円曲線と Edwards 曲線における加法演算の調査

17(ii) もし楕円曲線 E が k-有理な位数 2 のねじれ点を唯 1 つ持つなら，通常 Edwards 曲線
x2 + y 2 = 1 + dx2 y 2 が E の 2 次ツイストと k 上双有理同値になる非平方元 d ∈ k が存在す
る. さらに，k が有限体であるとき，通常 Edwards 曲線 x2 + y 2 = 1 + dx2 y 2 が E と k 上双有理同値になる非平方元 d ∈ k が存在する.

18

第4章

楕円曲線暗号に対する攻撃法調査
楕円曲線暗号の安全性を支える楕円曲線離散対数問題（Elliptic Curve Discrete Logarithm

Problem, ECDLP）とは次の計算問題である：「有限体 Fq 上の楕円曲線 E とその曲線上の 2 点
S, T ∈ E(Fq ) が与えられたとき，T = dS を満たす整数 d を見つけよ. ただし，基点 S の位数は素数 r とし*1 ，目標点 T は基点 S が生成する巡回群 hSi の元とする.」特に，法 r において ECDLPの解 d は一意的に定まる. また，暗号の安全性のため，楕円曲線暗号では基点 S の位数 r が巨大な素数となるような曲線パラメータを用いる.（具体的には，条件 r ≈ q を満たす曲線パラメータを利用する．
）さらに，楕円曲線暗号では，標数が巨大な素数 p の素体 Fp または標数 2 の拡大体 F2n上定義された楕円曲線がよく利用される．特に，標数 2 の素数次拡大体 F2n 上定義される Koblitz
曲線 y 2 + xy = x3 + ax2 + 1 (a ∈ F2 ) も利用されることがある*2 ．本章では，EdDSA で利用される曲線の攻撃評価のため，主に素体上の ECDLP に対する攻撃手法を調査する.

4.1 一般の楕円曲線に適用可能な攻撃法
本節では，一般の楕円曲線上の ECDLP に適用可能な攻撃手法についてまとめる. （本節の内容をまとめるに際し，ECDLP に対する攻撃法に関するサーベイ論文 [23] を主に参考にした.）

4.1.1 Shanks の Baby-Step Giant-Step（BSGS）法BSGS 法の基本的な計算手順√
BSGS 法の基本的なアイデアは，楕円曲線 E 上の基点 S の位数 r に対し m = d re とおくこと

により，ECDLP の解を d = d0 + d1 m (0 ≤ d0 , d1 < m) と一意的に表すことである [49] *3 ．さ*1

基点 S の位数 r が合成数の場合は Pohlig-Hellman 法 [40] により r の冪を含めた各素因子に関する ECDLP に帰着できるため，簡単のため本章では基点 S の位数 r は素数とする.（Pohlig-Hellman 法の詳細については [27,Section 4.1.1] や [15, Section V.1] を参照.）*2 楕円曲線暗号の安全性検証のため，Certicom ECC Challenge [45] では素体・2 冪体上の楕円曲線に加え Koblitz
曲線に関する 3 種類の ECDLP インスタンス (E/Fq , S, T, r) を公開している．（また，各 ECDLP インスタンス
に対して，初めて求解された際の懸賞金が用意されている．
）*3 整数 d を m で割った際の商が d1 で余りが d0 とみなせ，m の選択の仕方から整数の組 (d0 , d1 ) は一意的である．

第 4 章 楕円曲線暗号に対する攻撃法調査

19

らに，整数の組 (d0 , d1 ) を探索するために，以下の計算手順を行う：

1. まず，楕円曲線 E 上の点 a0 S (a0 = 0, 1, 2, . . . m − 1) を計算し（この計算を “baby steps”と呼ぶ），それらすべての点を以下の集合リスト L に格納する：

L = {a0 S ∈ E(Fq ) : a0 = 0, 1, 2, . . . , m − 1}
2. 次に，基点 S の m 倍点 R = mS ∈ E(Fq ) を計算し，楕円曲線 E 上の点 T − a1 R (a1 =0, 1, 2, . . . , m − 1) を順次計算しながら（この計算を “giant steps”と呼ぶ），リスト L に含まれるか確認する. 実際，T = (d0 + d1 m)S より，リスト L に含まれる点 d0 S が点 T − d1 Rに一致するので，d = d0 + d1 m を満たす組 (d0 .d1 ) を探索することができる.

√√

この計算手順では，O( r) 回の楕円曲線 E 上の演算を必要とし，O( r) 個の楕円曲線の点を格納する必要がある. Pollard による逐次点に関する生成法 [42, Section 3] により BSGS 法の平均計算量を削減でき，その平均計算量は 43√

r 回の楕円曲線上の演算が必要である.

逆元計算による BSGS 法の高速化
楕円曲線上の点の逆元計算を利用して BSGS 法を改良することができる．具体的には，無限遠点∞ ではない楕円曲線上の点が P = (x, y) で表される場合，その逆元は −P = (x, −y) と簡単に計√ 
算できることと，2 点 ±P の x 座標が同じであることを利用する．より具体的には，m′ =2rとおき，求めたい ECDLP の解を d = d′0 + d′1 m′ (−m′ /2 ≤ d′0 ≤ m′ /2, 0 ≤ d′1 < r/m′ ≈p

r/2 ≈ m′ /2) と一意的に表す．整数の組 (d′0 , d′1 ) を探索するために，以下の計算手順を行う：
1. まず，楕円曲線 E 上の a0 S の形の点の x 座標の集合リスト
L′ = {x(a0 S) : a0 = 0, 1, 2, . . . , bm′ /2c}を作成する．ただし，無限遠点 ∞ では楕円曲線上の点 P の x 座標を x(P ) と表す．今回求
めたい整数 d′0 は区間 [−m′ /2, m′ /2] に含まれるが，リスト L′ には非負整数 a0 に関するス
カラー倍点 a0 S (a0 = 0, 1, 2, . . . ) の x 座標の情報だけを格納する．これにより，今回のリスト L′ のサイズがおよそ m′ /2 ≈√p

r/2 となり，上記で説明したリスト L のサイズよりp√
2 倍程度小さくなっていることに注意する（つまり，#L ≈ r, #L′ ≈ r/2 である）．

2. 次に，上記で説明した基本的な BSGS 法と同じように，基点 S の m′ 倍点 R′ = m′ S ∈ E(Fq )を計算し，楕円曲線 E 上の点 T − a1 R′ (a1 = 0, 1, 2, . . . , br/m′ c) を順次計算しながら，各点の x 座標がリスト L′ に含まれるか確認する．実際，T = (d′0 + d′1 m′ )S より，点 T − d′1 R′の x 座標はリスト L′ に含まれ x(d′0 S) ∈ L′ に一致する．これより，整数の組 (d′0 , d′1 ) を探索することができる．
この改良版の BSGS 法で必要な楕円曲線上の平均演算回数は 43
法に比べて

√

p

√
r/2 ≈ 0.943 r で，通常の BSGS

2 倍の高速化が実現できる. （BSGS 法タイプのアルゴリズムに関するより詳細な計

算量や改良方式については，[23, Section 4] を参照.）

第 4 章 楕円曲線暗号に対する攻撃法調査

20

4.1.2 Pollard のρ法
Pollard のρ法は ECDLP を含む一般の離散対数問題に対する攻撃法である [41]．上記で説明し√た BSGS 法は膨大なデータを格納する必要があるのに対し（O( r) の空間計算量），ρ法では非常に少ないデータの格納だけで ECDLP を求解できる．さらに，大規模な並列化計算も比較的簡単に実現できるため，100 ビット以上の巨大な位数 r を持つ ECDLP の求解にはすべて並列化ρ法が利用されている. 実際，現時点での各種曲線における ECDLP 求解の世界記録は以下で，すべて並列化ρ法により解かれている（特に，ECDLP の解読計算量は位数 r の大きさに依存する）：

 素体においては，112 ビット素数 p の有限体 Fp 上定義された 111.78 ビットの位数 r を持つ

ECDLP インスタンスが 2009 年に解かれた [16] *4 . （一般に楕円曲線暗号で利用される曲線ではないが，114 ビット素体上で 113.20 ビットの位数 r を持つペアリング暗号で利用される Barreto-Naehrig 曲線に関する ECDLP インスタンスが 2017 年に解かれている [34].）

 2 冪体においては，127 ビットの拡大体 F2127 上定義された 117.35 ビットの位数 r を持つ

ECDLP インスタンスが 2016 年に解かれた [7]，
 2 冪体上の Koblitz 曲線においては，113 ビットの拡大体 F2113 上定義された 112.00 ビッ
トの位数 r を持つ Koblitz 曲線 y 2 + xy = x3 + x2 + 1 に関する ECDLP インスタンスが2014 年に解かれた [57]. （解読されたわけではないが，Certicom ECC Challenge [45] で公開されている 131 ビットの拡大体 F2131 上定義された Koblitz 曲線に関する ECDLP イ
ンスタンス ECC2K-130 の求解に必要な計算量が [3] で見積もられている.）反復関数の選択ECDLP インスタンス (E/Fq , S, T, r) に対し，ρ法では巡回群 hSi 上の自己写像 f : hSi −→ hSi
を f (X) = X + aS + bT, X ∈ hSi となる整数 a, b が効率的に計算できる関数を固定する．このf を反復関数（iteration function）と呼ぶ. 例えば，自然数 L に対し，適当な写像 H : hSi −→{1, 2, . . . , L} をとる*5 . ここでは，L を分割数，H を分割関数と呼ぶ．次に，基点 S と目標点 Tを用いて，L 個の組 (Ri , ai , bi ), i = 1, 2, . . . , L を用意する．ただし，ai , bi ∈ [0, r) はランダム整数とし，Ri = ai S + bi T を楕円曲線 E 上の点とする．このとき，任意の点 X ∈ hSi に対し，

f (X) = X + Ri ,i = H(X)(4.1)と定めると反復関数が構成できる*6 （その他の関数は [53, 54] を参照）．一方，Koblitz 曲線上のECDLP に対しては，後述の自己同型写像による高速化に適した反復関数を選択する必要がある*7 ．
*4

具体的には，“secp112r1”[43] と呼ばれる楕円曲線に関する ECDLP インスタンスが，ゲーム機 PlayStation3 による計算機クラスターにより求解された.（SEC2 [43] を含めた様々な楕円曲線パラメータについては [12] を参照.）*5 具体的には，点 P ∈ hSi に対し H(P ) = x(P ) (mod L) + 1 と定めれば良い．
*6 構成の仕方から，f (X) = X + Ri = X + ai S + bi T を満たす整数の組 (ai , bi ) は既知である．
*7 Koblitz 曲線上の ECDLP に適した反復関数の構成は少し複雑で，詳しくは [24, 57, 59] を参照．

第 4 章 楕円曲線暗号に対する攻撃法調査21

ρ法の基本的な計算手順
反復関数 f を用いて，ρ法では次の計算手順で ECDLP を求解する：

1. ランダムに 2 つの整数 u0 , v0 ∈ [0, r) をとり，初期点 X0 = u0 S + v0 T ∈ hSi を生成する．
2. 次に，Xi+1 = f (Xi ) (i = 0, 1, 2, . . . ) により逐次的に巡回群 hSi の元 Xi を生成していく．
特に，反復関数の性質から，Xi = ui S + vi T を満たす整数の組 (ui , vi ) が効率的に計算できる．（実際，初期点 X0 が u0 S + v0 T という基点 S と目標点 T の線形和の形なので，反復関数 f の性質から Xi も ui S + vi T という点 S, T の線形和の形で表せる．
）

3. 巡回群 hSi の位数は r（つまり有限集合）だから，点 Xi を順に計算していくと，やがて既に得られた点と等しくなる.（この現象を衝突と呼ぶ*8 .）衝突した点 Xi = Xj (i 6= j) を考えると，関係式 ui S + vi T = uj S + vj T が成り立つ. これより，vi 6≡ vj (mod r) なら*9 ，d ≡ (ui − uj ) · (vj − vi )−1(mod r)となる整数 d は ECDLP の解である.

ρ法の計算量と並列化
反復関数 f が巡回群 hSi 上でランダムな振る舞いをする場合*10 ，衝突が起こるまでに必要な点
列 {X0 , X1 , X2 , . . . } の個数の期待値は誕生日の逆理（birthday paradox）より，r√
πr≈ 1.2533 r
2

(4.2)

である（証明については，例えば [51, Section XI.5] を参照）
．よって，ρ 法を用いて ECDLP を解くのにかかる計算時間の期待値はr

πr· t(f )
2

(4.3)

である. ただし，t(f ) は反復関数 f の計算時間とする．（式 (4.1) の反復関数を用いた場合，t(f ) は
楕円曲線上の点の加算の計算時間である．
）また，ρ 法は比較的簡単に並列化でき，M 台の計算機を用いれば M 倍の高速化を実現することができる [55]．具体的には，M 台の計算機が独立に初期点
(k)

(k)

(k)

(k)

X0 , k = 1, 2, . . . , M を生成し，同じ反復関数 f を用いて点列 {X0 , X1 , X2 , . . . } を生成し
(k)

(k)

(k)

ていく．このとき，M 台の計算機が独立に生成する点列 {X0 , X1 , X2 , . . . }, k = 1, 2, . . . , M
において衝突を探索することで，ECDLP の解が得られる．
ちなみに，「ρ法」という名前は，衝突を引き起こす点列 {X0 , X1 , . . . } がギリシャ文字の “ρ” の形のように点在することに由来している.（例えば [27, Figure 4.1] の図を参照．）*9 点列 {X0 , X1 , X2 , . . . } が巡回群 hSi 上ほぼランダムに点在する限り，vi ≡ vj (i 6= j) となることは実用上ほぼない．つまり，vi ≡ vj (i 6= j) となる自明な衝突の発生確率は実用上無視できる．
*10 正確には，反復関数 f によって生成される点列 {X0 , X1 , X2 , . . . } が巡回群 hSi 上ランダムに点在する場合を指す．また，式 (4.1) の反復関数 f を利用する場合は，分割数 L を 16 以上に設定すると f がほぼランダムに振る舞うことが実験的に示されている [54]．（また，[60, Section 3.2] の実験報告も参照．）*8

第 4 章 楕円曲線暗号に対する攻撃法調査

22

代表的なρ法の改良法
ここでは，ECDLP 求解におけるρ法の改良方法を 2 つ紹介する：■識別点の導入と衝突探索 識別点（distinguished points）を導入することで，衝突を探索するための空間計算量を劇的に削減できる. まず，楕円曲線の点が識別点であるかの基準を定める. （例えば，楕円曲線の点の x 座標の最初の t ビットがすべて 0 であるものを識別点と定める.）複数の計算機が独立に点列を生成する際，識別点が現れたら，その点を衝突探索サーバに送信する. 衝突
探索サーバ上では識別点だけを格納しており，識別点間の衝突を探索する. 巡回群 hSi における識別点の割合を 0 < θ < 1 とする. M 台の計算機でρ法を計算する際，識別点での衝突が起こるま
(k)

(k)

(k)

でに各計算機が生成する点列 {X0 , X1 , X2 , . . . } の個数の期待値は

1
M

r

πr 1
+
2
θ

である. 特に， θ1 は識別点とは限らない衝突が起こった後に識別点での衝突が起こるまでに必要な点列の個数の期待値である.
■自己同型写像による高速化

楕円曲線上の自己同型写像によるρ法の高速化が [24, 58] により提案されている（[27, Section 4.1.2] も参照）. 効率的に計算可能な巡回群 hSi 上の位数 t の自己同型写像 ψ が存在すると仮定する*11 . ここで，巡回群 hSi 上の同値関係を P ∼ Q ⇐⇒ P =ψ j (Q) (∃j ∈ [0, t)) と定める. この同値類による集合全体を hSi/ ∼ とし，[P ] を点 P を含む同値類とする. 自己同型写像 ψ によるρ法の高速化の基本的なアイデアは，同値類による集合

hSi/ ∼ 上の反復関数を構成することである. 具体的には，巡回群 hSi 上の反復関数 f に対して，
f¯([P ]) = f ([P ]) と定めることで同値類による集合 hSi/ ∼ 上の反復関数 f¯ を構成する. このとき，# (hSi/ ∼) ≈ r/t より，反復関数 f¯ で生成された点列間で衝突が起こるまでに必要な点の個数のp
期待値はおよそ πr
2t である. つまり，位数 t の自己同型写像 ψ によるρ法の高速化により，およ√そ t 倍少ない個数で衝突を引き起こすことが期待できる.
 すべての楕円曲線上では逆元計算による位数 2 の自己同型写像 ψ が存在する（つまり，√
ψ(P ) = −P ）. 自己同型写像 ψ は効率的に計算できるため，ρ法を 2 倍高速化できる*12 .
 Koblitz 曲線 E 上では Frobenius 写像

ϕ : E(F2n ) −→ E(F2n ),(x, y) 7−→ (x2 , y 2 ), ∞ 7−→ ∞による位数 n の自己同型写像 ϕ があり，効率的に計算することができる. 上記に説明した逆元計算による位数 2 の自己同型写像 ϕ との合成写像を考えることで，Koblitz 曲線上では位
数 2n の自己同型写像が考えることができるので，およそ
*11
*12

√

2n 倍の高速化が可能となる.

自己同型写像 ψ の位数とは楕円曲線上の自己同型写像全体がなす群 Aut(E) の元としての位数を指す.
√
しかし，実用的に 2 倍の高速化を実現するには，適切な反復関数 f の選択や自明な衝突の回避対処など様々な工夫が必要である [14].

第 4 章 楕円曲線暗号に対する攻撃法調査

23

注意 4.1.1. 反復関数の構成方法から，ρ法は楕円曲線上の加算の繰り返しが本質的演算であり，加算演算操作自体には多くのメモリーを必要としないことに加え，衝突探索部は識別点を利用することで省メモリ化が可能である．このことから，ρ法は大規模分散計算に向けた実装が可能な攻撃
アルゴリズムであり，これまでの ECDLP の解読実験のようにインターネット上の有志による不統一な計算環境でも，比較的うまく機能させることができる．ただし，ρ法を用いて ECDLP を求解する際には，反復関数の選択や数多くの実装パラメータに依存して，解読計算量が変化する可能性がある（具体的なアルゴリズム並びに理論検討・実験評価の詳細については [60, 63] を参照）.

4.1.3 指数計算法（Index Calculus Method）
指数計算法は，ECDLP に限らず一般の離散対数問題（Discrete Logarithm Problem, DLP）
を効率的に求解する方法である. 以下では，まず ECDLP を指数計算法で求解するために必要なSemaev の summation 多項式について説明する．
Semaev の summation 多項式
Semaev の summation 多項式は楕円曲線に付随する多変数多項式で，具体的には次のように構成する [48]．標数が 2, 3 以外の体 k 上の楕円曲線 E : y 2 = x3 + ax + b において，m = 2, 3 における summation 多項式 Sm を

S2 (x1 , x2 ) =x1 − x2
S3 (x1 , x2 , x3 ) =(x1 − x2 )2 x23 − 2 {(x1 + x2 )(x1 x2 + a) + 2b} x3
+ (x1 x2 − a)2 − 4bx1 x2と定める. また，m ≥ 4 における summation 多項式は

Sm (x1 , . . . , xm ) = Resx (Sm−j (x1 , . . . , xm−j−1 , x), Sj+2 (xm−j , xm−j+1 , . . . , xm , x))と再帰的に定める. ただし，Resx は変数 x における終結式とし，j を 1 ≤ j ≤ m − 3 を満たす整数とする. 任意の m ≥ 2 に対し，Sm (x1 , x2 , . . . , xm ) は既約かつ対称な多変数多項式
で，各変数において 2m−2 の次数を持つ. また，summation 多項式は次の性質を持つ*13 ：体 kの代数閉体 k̄ における m 個の元 α1 , . . . , αm に対して，Sm (α1 , . . . , αm ) = 0 であることと，

Pi = (αi , βi ) ∈ E(k̄) (1 ≤ i ≤ m) かつ P1 + · · · + Pm = ∞ を満たす m 個の元 β1 , . . . , βm ∈ k̄ が存在することは同値である*14 ．

ECDLP に対する指数計算法の計算手順
ECDLP インスタンス (E/Fq , S, T, r) に対する指数計算法の基本的な計算手順は以下である（ただし，簡単のため E(Fq ) = hSi と仮定する）
：
*13
*14

逆に，この性質を持つように summation 多項式は構成されている．
特に，summation 多項式の零点 (α1 , . . . , αm ) ∈ k̄m は P1 + · · · + Pm = ∞ を満たす点 Pi の x-座標を与える．

第 4 章 楕円曲線暗号に対する攻撃法調査24

1.（因子基底の選択ステップ）群 E(Fq ) の部分集合 F を選択する．集合 F は因子基底（factorbase）と呼ばれる. 例えば，ランダムに選択した有限体 Fq の部分集合 V に対し，V の元をx-座標に持つ楕円曲線 E 上の点集合 F = {(x, y) ∈ E(Fq ) : x ∈ V } を因子基底と定めればよい．
（この他にも様々な定め方があるが，ここでは最も基本的な因子基底を取る．）

2.（関係式の生成ステップ）（a）ランダムに 2 つの整数 u, v を選び，楕円曲線上の点 R = uS + vT ∈ E(Fq ) を計算する.
（b）次に，点 R を因子基底 F の元の和で分解する. 分解に成功した場合，関係式

X

uS + vT =e i PiPi ∈Fを満たす整数の組 (u, v) とベクトル (ei ) を関係行列の行として格納する. 具体的には，固定した自然数 m に対し，summation 多項式を含めた変数 x1 , . . . , xm に関する連立方程式


Sm+1 (x1 , . . . , xm , x(R)) = 0F (x1 ) = 0

..


.




F (xm ) = 0(4.4)

を考える．ただし，F (x) は集合 V のすべての元を根に持つ一変数多項式

F (x) =

Y(x − α)α∈V*15とする．この連立方程式を解いて，解 (α1 , . . . , αm ) ∈ Fm
q が得られた場合，summa-tion 多項式の性質から P1 + · · · + Pm = ±R を満たす因子基底 F の元 P1 , . . . , Pm が必ず存在する*16 ．（因子基底の取り方により，連立方程式の解を得られないこともある．）（c）少なくとも #F 個の異なる関係式を見つけるまで，この操作を続ける.

3.（線形代数ステップ）上記のステップで構成した関係行列に対する線形代数操作により*17 ，
λS + µT = 0 を満たす等式を見つける. 特に，法 r において整数 µ が可逆であれば*18 ，
ECDLP の解として
d≡−

λ
µ

(mod r)が得られる.

ECDLP に対する指数計算法における研究課題と研究進展
上記の計算手順において，ステップ 2-(b) の点 R の因子基底 F の元の和の分解が最も計算コストが大きく，summation 多項式の対称性や S3 などの次数が小さい summation 多項式を組み合わ*15

連立方程式を解くのにグレブナー基底計算アルゴリズムを適用するのが一般的である.
より具体的には，すべての 1 ≤ i ≤ m に対して点 Pi の x-座標 x(Pi ) は αi に一致する．
*17 具体的には，関係行列に対して Gauss の消去法を適用すれば良い．
*18 可逆でない場合は，別の関係式を生成し，関係行列に追加することで関係行列を構成し直せばよい．
*16

第 4 章 楕円曲線暗号に対する攻撃法調査

25

せた連立方程式を利用する改良がある（詳しくは [23, Section 9] を参照）. しかし，ECDLP に対する指数計算法においては，次の 2 点が主な研究課題である：

 連立方程式を解くためのグレブナー基底計算アルゴリズムの評価・解析が困難なため，指数計算法の計算量見積もりが非常に難しい.（さらに，指数計算法の計算量は因子基底の取り方
やそのサイズに依存するが，最良の因子基底の取り方が現状明らかではない.）

 暗号で利用される実用サイズの ECDLP を効率的に解くアルゴリズムが整備されていない.
（実際，ECDLP に対する指数計算法に関しては，小さなサイズの実験データしかない.）
以下で，これらの研究課題に対する近年の研究進展紹介する：■素体 Fp の場合

2016 年，Petit ら [39] は因子基底の元による点の分解を効率的に行える素数 pの条件を提案した. 具体的には，p − 1 が滑らかな場合（特に 2 冪の場合），グレブナー基底計算アルゴリズムで点の分解に関する連立方程式を効率的に解けるような因子基底の取り方を提案した.
しかしその後，Peit らが提案した指数計算法にとって優位な条件下ですら，20〜30 ビットの小さな標数 p において BSGS 法やρ法の方が効率的であることが実験的に示された [33]. また近年では，連立方程式 (4.4) に対するグレブナー基底計算アルゴリズム内の振る舞いを解析することにより，上記で説明した基本的な指数計算法は全数探索法よりも悪い計算量を持つことが示された [61].
■2 冪体の場合 2 冪体上の ECDLP に対しては，Weil descent と呼ばれる技法と組み合わせた指数計算法に関する研究が数多くある（詳しくは [23, 62] を参照*19 ）. しかし，Weil descent を利用した指数計算法よりも，ρ法の方が計算効率が良いと [62] で結論付けられている. また近年では，合成次数の拡大体の ECDLP に対し，因子基底の選択を工夫することで，全数探索よりも効率的解く方法が提案された [29]. （しかし，これも BSGS 法やρ法より効率的ではないことに注意する.）
注意 4.1.2 (Xedni 計算法). 指数計算法の変種として，有限体上の楕円曲線 E と 2 点 S, T をある
代数体上の楕円曲線と有理点に持ち上げてから ECDLP を解く Xedni 計算法 [50] がある*20 . しかし，[30] の解析によると，基礎体の標数のサイズが大きくなるごとに Xedni 計算法は ECDLP の求解に失敗し，実用サイズの ECDLP には適用できないと報告されている. （また，比較的小さな標数でさえ，Xedni 計算法が成功する確率は高くないことが実験的に示されている.）

4.2 特殊な曲線にのみ有効な攻撃法
前節で紹介した攻撃法はすべての楕円曲線に適用可能な攻撃法である一方，本節では特殊な楕円曲線にのみ有効な攻撃法をまとめておく．（本節の内容をまとめるにあたり，[51, Section XI.6] や[56, Sections 5.3, 5.4] などを主に参考にした．）また，本節では素体 Fp 上の ECDLP に着目する．

*19
*20

本章の序文で述べたように，素体上の ECDLP が主な調査対象であるため，2 冪体については詳しくは説明しない.
ちなみに，“Xedni”は英単語 “Index”のアルファベットを逆から並べた造語である.

第 4 章 楕円曲線暗号に対する攻撃法調査

26

4.2.1 Menezes-Okamoto-Vanstone（MOV）攻撃法
MOV 攻撃法は楕円曲線上のペアリングを利用して ECDLP を乗法群上の DLP に帰着させる攻撃法である [36] *21 ．まず，ECDLP の帰着先の乗法群を定める上で重要な役割を果たすパラメー
タを定義する．ECDLP インスタンス (E/Fp , S, T, r) に対して，楕円曲線 E における位数 r のね
じれ群

E[r] = {P ∈ E(Fp ) | rP = ∞}を考える．条件 E[r] ⊆ E(Fpm ) を満たす最小の自然数 m を埋め込み次数（embedding degree）と呼ぶ．特に，r ∤ p − 1 の条件下で*22 ，埋め込み次数 m は条件 r | pm − 1 を満たす最小の自然数と一致する（証明については，例えば [51, Lemma 6.2 in Chapter XI] を参照）．
数学的準備
ガロア群 G = Gal(Fp /Fpm ) に対して，G-加群の短完全系列
r0 −→ E[r] −→ E(Fp ) −→ E(Fp ) −→ 0から（上記の “r” は r 倍算を意味する），ガロアコホモロジーによる群の長完全系列

0

−→
δ

E[r]G

−→

E(Fpm )r−→r

E(Fpm )−→ H (G, E[r]) −→ H (G, E(Fp )) −→ H (G, E(Fp )) −→ · · ·111が得られる. これより，単射準同型写像

δE : E(Fpm )/rE(Fpm ) −→ H 1 (G, E[r]) = Hom(G, E[r])が得られる. ただし，δE (P ) = [G 3 σ 7−→ σ(Q) − Q ∈ E[r]] ∈ Hom(G, E[r]) とする（P = rQ
なる点 Q を固定）. さらに，単射準同型写像 δE と Weil ペアリング er : E[r] × E[r] −→ µr を組
み合わせて，双線形写像× r
κ : E(Fpm )/rE(Fpm ) × E[r] −→ Hom(G, µr ) ' F×pm /(Fpm )が得られる. ただし，µr を 1 の r 乗根の集合 α ∈ Fp : αr = 1 とし，

κ(P, Q) = [G 3 σ 7−→ er (δE (P ), Q) ∈ µr ] ∈ Hom(G, µr )とする. この双線形写像 κ は Tate-Lichtenbaum ペアリングと呼ばれる（詳細は [51, Section XI.9]
を参照）．特に，双線形写像 κ は非退化で，Miller アルゴリズムにより効率的に計算可能である（詳細は [19, Chapter 16] を参照）.
*21

*22

元々は Menezes-岡本-Vanstone が Weil ペアリングを利用した攻撃法を提案し [36]，その後 Frey-Rück が TateLichitenbaum ペアリングを利用した攻撃法を提案した [21]．ここでは，後者の Tate ペアリング-Lichitenbaumを利用した攻撃法を説明する．
楕円曲線暗号における ECDLP では，2 つの巨大素数 p, r は p ≈ r を満たすので，r | p − 1 となることはない．

第 4 章 楕円曲線暗号に対する攻撃法調査

27

計算手順と適用曲線
上記で構成した非退化な双線形写像 κ を用いて，ECDLP インスタンス (E/Fp , S, T, r) に対す
る MOV 攻撃法では以下の計算手順を行う：

1. E[r] ⊆ E(Fpm ) を満たす埋め込み次数 m を計算する.
2. κ(P, S) 6= 1 となる点 P ∈ E(Fpm ) を 1 つ固定する*23 .
3. ζ1 = κ(P, S) と ζ2 = κ(P, T ) を計算する.
d*24 .（つまり，乗法群 F×m におけ
4. 乗法群 F×pm において ζ1 = ζ2 を満たす整数 d を見つけるp

る DLP を解く．
）
埋め込み次数 m が大きいと，乗法群 F×pm における DLP を求解することが困難になる. ゆえに，
埋め込み次数が十分小さい ECDLP インスタンスに限り MOV 攻撃法は有効である. 特に，E が超特異楕円曲線のとき，m = 2 であり MOV 攻撃法が有効である.

4.2.2 Semaev-Smart-Satoh-Araki（SSSA）攻撃法
有限体 Fp 上の楕円曲線 E の Fp -有理点全体がなす群の位数 #E(Fp ) がちょうど p となるとき，楕円曲線 E を anomalous と呼ぶ. Semaev [47]，Smart [52]，佐藤-荒木 [46] はほぼ同時期かつ独立に anomalous 楕円曲線上の ECDLP を非常に効率的に求解するアルゴリズムを提案した. こ
こでは，その攻撃アルゴリズムを SSSA 攻撃法と呼ぶ. SSSA 攻撃法のアイデアは，anomalous 楕*25 .
円曲線上の ECDLP を加法群 F+
p 上の DLP に帰着させることである

数学的準備
ここでは，まず anomalous とは限らない有限体 Fp 上の楕円曲線 E を考える. SSSA 攻撃法では，有限体 Fp 上の楕円曲線 E の方程式の各係数を p-進数体 Qp に持ち上げることで Qp 上の楕円e を構成する. このとき，群の短完全列
曲線 Eπe p ) −→
0 −→ ker π −→ E(Q
E(Fp ) −→ 0

e に付随する形式群とすると，群の同型を考える. ただし，π は還元写像とする. また，E を E
ker π ' E(pZp ) = pZp ,(x, y) 7−→ −xye p ) に対して*26 （この写像は群としが存在する. ここで，任意の持ち上げ写像 u : E(Fp ) −→ E(Qてはではなく単なる集合としての写像），合成写像
mod p2e p ) −→ ker π ' E(pZp ) = pZp −→ pZp /p2 Zp = F+λ(u) : E(Fp ) −→ E(QpuN

双線形写像 κ の非退化性より，κ(P, S) 6= 1 を満たす点 P は必ず存在する．
写像 κ の双線形性から，ζ1d = ζ2 を満たす整数 d は ECDLP の解と一致する．
+*25 記号 F+
p は有限体 Fp を加法群とみなすことを意味する. また，加法群 Fp 上の DLP の求解は非常に簡単である.
*26 具体的には，Hensel の補題による持ち上げ写像を構成すれば良い.
*23

*24

第 4 章 楕円曲線暗号に対する攻撃法調査

28

e における N 倍写像を考える. ただし，N = #E(Fp ) に対し，上記の “N ”は Qp 上の楕円曲線 Eとする. 特に，楕円曲線 E が anomalous のとき（つまり，N = p のとき），持ち上げ写像 u により定まる写像 λ(u) は群の同型写像か零写像である（証明については，例えば [51, Proposition 6.5

in Chapter XI] を参照）.
計算手順
以下に，anomalous 楕円曲線上の ECDLP インスタンス (E/Fp , S, T, p) に対する SSSA 攻撃法の計算手順を示す*27 ：1. 写像 λ(u) が同型写像となる持ち上げ写像 u を固定する*28 .
2. 加法群 F+
p 上の 2 つの元 s = λ(u)(S), t = λ(u)(T ) を計算する.
3. 加法群 F+
p 上の DLP を解くことにより，t = ds を満たす整数 d を見つける.（写像 λ(u) が群の同型写像により，整数 d は ECDLP の解と一致する.）

4.3 ECDLP に対する攻撃手法のまとめ
本章で説明した ECDLP に対する攻撃手法の特徴を，以下の表にまとめておく：
攻撃手法

特徴

BSGS 法

位数 r の ECDLP を O( r) 回の楕円曲線上の演算回数で求解できる攻撃√√法. ただし，O( r) 個の楕円曲線の点を格納する必要があり，暗号で利用される実用サイズの ECDLP を解くのは空間計算量の観点から困難である.
ρ法√
BSGS 法と同様，位数 r の ECDLP を O( r) の計算量で求解できる.BSGS
法と異なり，識別点の導入により少ない空間計算量で求解できると共に，大規模並列計算も比較的容易である. MOV 法や SSSA 法の攻撃対象となる特殊な曲線を除き，一般の ECDLP を解く現在最良の攻撃法である.（実際，

100 ビット以上の位数 r の ECDLP はすべて並列化ρ法で求解されている.）
指数計算法

ECDLP を含む一般の DLP を解く方法. しかし現状では，暗号で利用される実用サイズの ECDLP を効率的に解くアルゴリズムが整備されていない.

MOV 攻撃法

楕円曲線上のペアリングを利用して，ECDLP を乗法群 F×pm 上の DLP に帰着する方法. 帰着先の乗法群 F×pm のサイズが小さい場合のみ有効（例えば，超特異楕円曲線の場合は m = 2 で非常に有効）.

SSSA 攻撃法

有限体 Fp 上の anomalous 曲線における ECDLP を加法群 F+
p 上の DLPに帰着する非常に有効な攻撃法.

*27
*28

写像 λ(u) が log(p) の多項式時間で計算可能なので，SSSA 攻撃法は多項式時間アルゴリズムである.
実用的に，巨大な素数 p に対しては，ほとんどの場合 λ(u) は同型写像となる.

29

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察
公開鍵暗号において Edwards 曲線ディジタル署名アルゴリズム（Edwards-curve Digital Sig-nature Algorithm, EdDSA）とは，3.2.3 節で説明したツイスト Edwards 曲線を利用した Schnorr
によるディジタル署名の変種の一つである. EdDSA は他の楕円曲線上のディジタル署名方式におけるいくつかの問題点を回避すると共に*1 ，ツイスト Edwards 曲線上の点の加算・2 倍算公式により効率的な暗号化処理が可能なように設計されている（詳細は [6] を参照）. 本章では，EdDSA で利用される曲線に関して解説すると共に，暗号攻撃の観点からこれらの曲線がどの程度安全なのか
解析評価する. さらに，通常の ECDSA と比べて EdDSA がどの程度効率的なのかを考察する.

5.1 EdDSA で利用される曲線に関する解説
RFC 8032 [31] によると，EdDSA では（古典計算機による）暗号攻撃に対して約 128 ビットのセキュリティレベルの “Ed25519”と約 224 ビットのセキュリティレベルの “Ed448”の 2 種類の実装のどちらかを適用先の安全性要件に応じて利用するよう推奨されている*2 . 特に，Ed25519 では“Curve25519” [4]，Ed448 では “Curve448” [26] *3 と呼ばれるツイスト Edwards 曲線パラメータを利用するよう推奨されている（その他の候補曲線のパラメータについては [8] を参照）. 本節では，Curve25519 と Curve448 のツイスト Edwards 曲線パラメータとその特徴について解説する（具体的な曲線パラメータについては，RFC 7748 [35] も参考にした）.

5.1.1 Curve25519 の曲線パラメータと特徴
ここでは，Ed25519 で利用する Curve25519 の曲線パラメータとその特徴について解説する.
*1

サイドチャンネル攻撃耐性などの安全性を考慮している（詳しくは [31, Section 8] を参照）.
具体的には，128 ビットのセキュリティレベルで十分である限り，Ed25519 の利用が推奨されている.
*3 RFC 7748 [35] では “Curve448”と呼んでいるが，原論文 [26] では “Ed448-Goldilocks”という名称で曲線パラメータを提案している.（特に，Curve448 を定める基礎体の標数 p = 2448 − 2224 − 1 を Goldilocks 素数と呼ぶ.）
*2

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

30

Curve25519 の曲線パラメータ
Curve25519 は，255 ビット素数 p = 2255 − 19 による素体 Fp 上の方程式 (3.15) で定義されるツイスト Edwards 曲線 Ea,d である. ただし，係数 a, d は


a=−1





d = − 121665 (mod p)121666

=370957059346694393431380835087545651895421138798432

19016388785533085940283555とする. また，約 128 ビットのセキュリティレベルの署名アルゴリズム Ed25519 を構成するためのツイスト Edwards 曲線上の基点 S = (x(S), y(S)) ∈ Ea,d (Fp ) はx(S) = 1511222134953540077250115140958853151145401269304

1857206046113283949847762202

y(S) = 4631683569492647816942839400347516314130799386625

6225615783033603165251855960
で与えられている. さらに，Curve25519 上の Fp -有理点がなす群の位数は#Ea,d (Fp ) = 23 · r
r = 2252 + 27742317777372353535851937790883648493 (素数)(5.1)

で，基点 S の位数は素数 r である.（つまり，Curve25519 は余因子 8 を持つ．
）
他の曲線との関係

Curve25519 を定めるツイスト Edwards 曲線 Ea,d の係数 a = −1 が素体 Fp 上平方なので*4 ，3.2.3 節で説明したようにツイスト曲線 Ea,d は通常 Edwards 曲線
E1,d/a : x̄2 + ȳ 2 = 1 +121665 2 2x̄ ȳ
121666と Fp 上同型である*5 ．さらに，定理 3.2.1 節で説明したように，この通常 Edwards 曲線 E1,d/a
は Montgomery 曲線

v 2 = u3 + 486662u2 + u(5.2)と Fp 上双有理同値である．具体的な変数変換は√x̄ =486664u
,
v

ȳ =

u−1
u+1

RFC [31] によると，係数 a は Fp における平方元で，具体的には p ≡ 1 (mod 4) の場合は a = −1，p ≡ 3(mod 4) の場合は a = 1 と設定するよう推奨している．
√√*5 具体的には，x̄ =−1x, ȳ = y と変数変換すれば良い（ −1 ∈ Fp に注意）．

*4

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

31

で，特に 486664 が Fp における平方元であることに注意する．また，逆の変換変換は

1 + ȳ
,u=
1 − ȳ

√v=

486664ux̄で与えられる．

Curve25519 の曲線パラメータの選択法
ここでは，Curve25519 の曲線パラメータがどのような理由で選択されているのかを説明する．
まず，Montgomery 曲線に関する下記の定理を紹介する [4, Theorem 2.1] *6 ：定理 5.1.1. p ≥ 5 を素数とし，A2 − 4 (mod p) が平方でない整数を A とする．有限体 Fp 上のMontgomery 曲線 E : v 2 = u3 + Au2 + u に対し，写像 X0 : E(Fp2 ) −→ Fp2 を次のように定める：

X0 (∞) = 0,

X0 ((u, v)) = u

このとき，任意の整数 n と元 q ∈ Fp に対して，X0 (Q) = q を満たすすべての点 Q ∈ E(Fp2 ) に対し X0 (nQ) = s を満たす元 s ∈ Fp が唯一存在する．

Curve25519 を定めるツイスト Edwards 曲線 Ea,d と双有理同値になる Montgomery 曲線 (5.2)
が上記の定理の条件を満たすように，素数 p = 2255 − 19 と A = 486662 が選択されている．より
具体的な選択理由は以下である（詳細は [4] を参照）：
■標数 p の選択理由

安全性を考慮しつつ，32 · 8 = 256 ビットより小さい 2 冪に近い素数を選択している．
（公開鍵情報を 32 ビットのワードに変換するために，32k の型のビットが適している．
）
標数 p の候補として，2255 + 95, 2255 − 19, 2255 − 31, 2254 + 79, 2253 + 51, 2253 + 39 があるが，19 が 31, 39, 51, 79, 95 よりも小さいため p = 2255 − 19 が選択されている．
■係数 A の選択理由

様々な可能性のある暗号攻撃を避けるため*7 ，楕円曲線とそのツイストの両方の位数が 4r または 8r（ただし r は巨大素数）の形となるように係数 A を選択している*8 ．また，Montgomery 型の楕円曲線 E 上の点のスカラー倍演算を効率的に行えるように，(A − 2)/4 が十分小さい整数となることが望ましい（詳しくは Montgomery 乗法公式 (3.24) を参照）. これらの条件を満たす係数 A の候補として，小さい順に 358990, 464586, 486662 がある．A = 358990と 464586 の場合は上記の r の値が 252 ビットよりほんの小さいのに対し，A = 486662 の場合はそうはならない（正確な位数 (5.1) を参照）．そのため，A = 486662 が選択されている．

*6

この定理における性質は Diﬃe-Hellman 鍵共有などの暗号方式の構成 [4] に有用である一方，暗号攻撃に利用した文献は今のところ見当たらない．
*7 楕円曲線上のツイストを利用した暗号攻撃などを想定している.
*8 実際，Curve25519 の（2 次）ツイスト曲線の位数は22 · 14474011154664524427946373126085988481603263447650325797860494125407373907997
である. つまり，4 を余因子として持つ.

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

32

Curve25519 上の点の加算
RFC 8032 [31] では，Curve25519 を定めるツイスト Edwards 曲線 Ea,d 上の点の加算・2 倍算においては拡張版の射影座標表現の利用を推奨している. 具体的には，ツイスト Edwards 曲線

Ea,d 上の点 (x, y) を射影空間 P3 内の斉次 2 次曲線 aX 2 + Y 2 = Z 2 + dT 2 上の拡張版の射影点(X : Y : T : Z) に対応させる. 特に，任意の λ 6= 0 に対し，(X : Y : T : Z) = (λX : λY : λT : λZ)Y
Tを満たし，Z 6= 0 で x = X
Z , y = Z , xy = Z に対応させる. （特に，ツイスト Edwards 曲線上の零元 (0, 1) は射影点 (0 : 1 : 0 : 1) に対応し，拡張版の射影点 P = (X : Y : T : Z) の逆元は

−P = (−X : Y : −T : Z) で与えられる.）以下に，拡張版の射影座標表現によるツイスト Edwards
曲線上の加算公式の具体的な計算手順を示す [31, Section 5.1.4]（詳細は [11, 28] を参照）：■加算

拡張版の射影座標表現によるツイスト Edwards 曲線上の 2 つの射影点 (X1 : Y1 : T1 :Z1 ), (X2 : Y2 : T2 : Z2 ) の加算点 (X3 : Y3 : T3 : Z3 ) は次の計算手順で求まる：
 A = (Y1 − X1 ) · (Y2 − X2 ); B = (Y1 + X1 ) · (Y2 + X2 ); C = 2dT1 · T2 ;D = 2Z1 · Z2 ; E = B − A; F = D − C; G = D + C; H = B + A;

X = E · F ; Y = G · H; T = E · H; Z = F · G;
3

3

3

3

この計算コストは 8M + 8add である.（ただし，定数との掛け算コストは無視する.）表 3.2 から
拡張版の射影座標表現による加算は他の座標表現よりも効率的であることが分かる.
■2 倍算

拡張版の射影座標表現によるツイスト Edwards 曲線上の射影点 (X1 : Y1 : T1 : Z1 ) の2 倍点 (X3 : Y3 : T3 : Z3 ) は次の計算手順で求まる：

2
2
2

 A = X1 ; B = Y1 ; C = 2Z1 ; H = A + B;
E = H − (X1 + Y1 )2 ; G = A − B; F = C + G;
X3 = E · F ; Y3 = G · H; T3 = E · H; Z3 = F · G;
この計算コストは 4M + 4S + 5add である.（ただし，定数との掛け算コストは無視する.）加算の場合とは異なり，拡張版の射影座標表現による 2 倍算は他の座標表現より必ずしも効率的とは限らないことが表 3.2 から分かる.

5.1.2 Curve448 の曲線パラメータと特徴
ここでは，約 224 ビットのセキュリティレベルの署名アルゴリズム Ed448 で利用する Curve448の曲線パラメータとその特徴について解説する.

Curve448 の曲線パラメータ
Curve448 は，448 ビット素数 p = 2448 − 2224 − 1 による素体 Fp 上の方程式 (3.11) で定義される通常 Edwards 曲線 Ed である. ただし，係数は d = −39081 とする. また，署名アルゴリズム

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

33

Ed448 を構成するための通常 Edwards 曲線上の基点 S = (x(S), y(S)) ∈ Ed (Fp ) はx(S) = 22458004029592430018760433409989603624678964163

25641342461254616869504154674060329090291928693





57953282578032075146446173674602635247710
y(S) = 29881921007848149267601793044393067343754404015





40802420959282413723315061898358760035368786554

18784733982303233503462500531545062832660で与えられている. さらに，Curve448 上の Fp -有理点がなす群の位数は#Ed (Fp ) =22 · r
r = 2446 − 13818066809895115352007386748515(5.3)

426880336692474882178609894547503885 (素数)で，基点 S の位数は素数 r である.（つまり，Curve448 は余因子 4 を持つ.）

Curve448 の曲線パラメータの選択法
ここでは，Curve448 の曲線パラメータがどのような理由で選択されているのかを説明する.
■標数 p の選択理由

有限体上の四則演算を効率的に行えるよ 3 項式の Solinas 素数*9 である

p = 2448 − 2224 − 1 を選択している. 特に，素数 p は [26] で Goldilocks 素数と呼ばれ，ϕ = 2224に対し法 p による整数を a + bϕ の形で表すことにより，高速な Karatsuba 乗算などが可能となる[26, Section 3.2].（ただし，a, b は ϕ 未満の非負整数とする.）特に，224 = 32 · 7 = 28 · 8 = 56 · 4
により，28 ビット・32 ビットや 56 ビットなどの様々なサイズのワードを利用した有限体 Fp 上の高速演算が可能である.
■Edwards 曲線の選択理由

Curve448 を定める有限体 Fp 上の通常 Edwards 曲線 Ed の中で，係数パラメータ d の絶対値が十分小さく，Ed とそのツイストの位数が共に 4r（ただし r は巨大素数）の形になるよう d = −39081 を選択している（正確な位数は (5.3) を参照*10 ）. 特に，選択された Edwards 曲線 Ed は SafeCurves [12] における安全性要件*11 をすべて満たしている.

Curve448 上の点の加算
RFC 8032 [31] では，Curve448 を定める通常 Edwards 曲線 Ed 上の点の加算・2 倍算においては，3.2.1 節で説明した射影座標表現の利用を推奨している.
*9*10

2k − 2ℓ ± · · · ± 1 の形の素数を Solinas 素数と呼ぶ.
また，Curve448 を定める通常 Edwards 曲線 Ed のツイストの位数は()
4 · 2446 + 338093476319795454673879205005611543518120263611892369342742379277*11で，4 を余因子として持つ.
安全性要件として，ρ法による解読計算量，一般の離散対数問題に帰着した場合の解読計算量，虚数乗法における判別式の大きさ，ツイスト楕円曲線における安全性などの項目がある.

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

34

5.2 EdDSA で利用される曲線に対する攻撃計算量評価
本節では，EdDSA で利用される Curve25519 と Curve448 の 2 つの曲線上の ECDLP に対して，現時点で知られている最良の攻撃法を選択すると共に，その攻撃計算量を評価する.

5.2.1 最良の攻撃法の選択
ここでは，EdDSA で利用される Curve25519 と Curve448 の 2 つの曲線に対して，現時点で知られている最良の攻撃法を選択する．まず，Curve25519 と Curve448 の 2 つの曲線に対して，

MOV 攻撃法や SSSA 攻撃法の特殊攻撃法が有効になり得るのか議論する：■MOV 攻撃法に対して

4.2.1 節で説明したように，MOV 攻撃法では ECDLP を乗法群 F×pm 上の DLP に帰着するが（ただし，m は埋め込み次数とする*12 ），帰着先の乗法群のサイズが小さい場合のみ有効である．具体的には，楕円曲線暗号の安全性のため，IEEE P1363 [38] では 30 以上，

ANSI X9.62 [1] では少なくとも 100 以上*13 の埋め込み次数を推奨している．また，より十分な安
全性を担保するため，ECC Brainpool [18] では

m=

r−1
100

(5.4)

以上の埋め込み次数を推奨している.（ただし，r は ECDLP における基点の位数とする．
）さらに，

SafeCurves [12] では，乗法群上の DLP 解法に関するこれまでの研究進展から IEEE P1363 や
ANSI X9.62 の基準では安全性に対する懸念があるとする一方，ECC Brainpool の基準は過度な安
全性レベルとしている．しかし，十分な安全性担保の観点から，SafeCurves では ECC Brainpoolの基準を推奨している*14 ．一方，本報告書の評価対象である Curve25519 における埋め込み次数は

m=r−1=12061675962220437023288644271738323734
676186059896651267666991823047575708498

であり，Curve448 における埋め込み次数は

m=r−1=9085484053695086131866547598600056679420517008591475753518627489757
23001980769792858097877645846187981655146854545831152386877929824889

具体的には，ECDLP インスタンス (E/Fp , S, T, r) に対して，埋め込み次数 m は条件 r | pm − 1 を満たす最小の自然数である.
*13 ANSI X9.62 (1998) では埋め込み次数の基準を 20 以上としていた（SEC1 [44] も参照）.
*14 SafeCurves [12] における ECDLP の安全性要件として，ρ法による攻撃計算量や MOV 攻撃法や SSSA 攻撃法による帰着攻撃以外に，楕円曲線における虚数乗法の判別式の絶対値の大きさや曲線生成に関する詳細な説明の有無に関する項目がある. しかし，これらの項目は ECDLP に対する直接的な攻撃と関係が薄いため，本報告書では取り上げない事とした.（ちなみに，EdDSA で利用される Curve25519 と Curve448 の 2 つの曲線は共に，SafeCurvesの安全性要件をすべて満たしている.）
*12

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

35

である．つまり，Curve25519 と Curve448 の 2 つの曲線は共に ECC Brainpool の基準 (5.4) よりも大きな埋め込み次数を持つので，これらの 2 つの曲線に対しては MOV 攻撃法は有効ではない．
■SSSA 攻撃法に対して前節の曲線パラメータ説明で述べたように，Curve25519 と Curve448の 2 つの曲線は共に anomalous ではないので，そもそも SSSA 攻撃法は適用できない．
上記の議論より，EdDSA で利用される Curve25519 と Curve448 の 2 つの曲線に対しては，

MOV 攻撃法や SSSA 攻撃法の特殊な攻撃法は有効ではない．一方，4.3 節のまとめから，特殊な攻撃法を除けば，ρ法が現時点での最良の攻撃法である．

5.2.2 EdDSA で利用される曲線に対するρ法による攻撃計算量評価
ここでは，EdDSA で利用される Curve25519 と Curve448 の 2 つの曲線に対するρ法による攻撃計算量評価を行う.

Edwards 曲線に対する ρ 法による攻撃実験
ρ法は誕生日の逆理に基づく確率的な攻撃アルゴリズムであるため，攻撃対象となる曲線の違いにより計算量が大きく変化する可能性がある. ここでは，攻撃実験可能なサイズの Edwards 曲線
に対するρ法攻撃の振る舞いを実験的に解析する.
■攻撃実験用の Edwards 曲線パラメータ生成

ρ法の攻撃実験用に，40 ビット程度の素数 p による有限体 Fp 上の（ツイストなしの）Edwards 曲線 Ed を生成する*15 . 特に，Curve25519 とCurve448 と同じように，曲線とそのツイストの位数が共に 4r（ただし r は素数）の形となる
Edwards 曲線を選択する. 3.2 節で説明したように，Edwards 曲線 Ed は Weierstrass 方程式
Cd : y 2 = (x − d − 1)(x2 − 4d)= x3 − (d + 1)x2 − 4dx + 4d(d + 1)

(5.5)

で定まる楕円曲線に同型であることに注意する*16 . さらに，Edwards 曲線 Ed 上の点の加算は，Weierstrass 方程式 (5.5) で定まる楕円曲線 Cd 上の点の加算と一致するため，2 つの曲線 Ed と Cdに対するρ法攻撃の振る舞いも一致する. 本実験では，楕円曲線に関する機能を豊富に持つ数式処
理ソフトウェア SageMath [25] を利用するので*17 ，Weierstrass 方程式 (5.5) で定める曲線 Cd 上の ECDLP インスタンスを生成し，ρ法による攻撃実験を行う.
攻撃実験用に生成した具体的な ECDLP インスタンス (Cd /Fp , S, T, r) は以下である（下記のECDLP インスタンスを作成する際に利用した Sage スクリプトを図 5.1 に示しておく）：*15

Edwards 曲線 Ed を定める方程式は (3.11) である.
Edwards 曲線と同型なので，曲線 Cd も位数 4 のねじれ点を必ず持つ.
*17 SageMath では Weierstrass 方程式で定まる楕円曲線に関して非常に多くの関数を利用することができる.
*16

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

36

p = next_prime(2^40); print("p = ", p)
while(1):d = randint(0, p)
E = EllipticCurve(GF(p), [0, -d-1, 0, -4*d, 4*d*(d+1)])
t = E.trace_of_frobenius()r = ZZ((p+1-t)/4)# p+1-t: order of E

rr = ZZ((p+1+t)/4) # p+1+t: order of twist of E
if is_prime(r) == True and is_prime(rr) == True:
print("d = ", d); print("r = ", r)
P = E.gens()[0]S = 4*P; print("S = ", S)
T = randint(0, r)*S; print("T = ", T)
break
図 5.1 ECDLP インスタンス (5.6) の生成用 Sage スクリプト
p = 1099511627791 (≈ 240 )






 d = 416824108313

S = (176845795840, 980148948053) ∈ Cd (Fp )
T = (697615400391, 406954616758) ∈ Cd (Fp )r = 274878050303■Edwards 曲線に対するρ法攻撃の実験データ(5.6)

上記で生成した Edwards 曲線上の ECDLP イン

スタンス (5.6) に対して，ρ法攻撃アルゴリズムを実装し，攻撃実験を行った. ρ法攻撃アルゴリズ
ムの実装においては，分割数を L = 16 に設定した (4.1) で定義された反復関数 f を用いた*18 . 図

5.4 に ECDLP に対するρ法攻撃アルゴリズムの Sage スクリプトを示しておく. （ただし，簡単のため，本攻撃実験では楕円曲線上の逆元写像を利用したρ法の高速化手法は用いなかった.）また，
図 5.2 に，ρ法攻撃において衝突が起こるまでに必要した楕円曲線の点列の個数に関するヒストグ
ラムを示す. 具体的には，ρ法における初期点をランダムに入れ替え，10,000 回の攻撃実験から得られた度数分布を図 5.2 に示した. （ただし，横軸は誕生日の逆理に基づく期待値 (4.2) で正規化した.）図 5.2 から，横軸がほぼ期待値 (4.2) において分布の山の頂点となることが分かる. さらに，
分布の山のすその広がり方は，一般の楕円曲線上に対するρ法攻撃における分布図 [60, Figures 3,4] とほぼ同じであることが分かる. これより，Edwards 曲線上のρ法攻撃で必要となる楕円曲線の点列の個数は，一般の楕円曲線上の個数とほぼ同じであると結論付けることができる*19 .
*18

4.1.2 節で説明したように，分割数 L ≥ 16 で反復関数 (4.1) は楕円曲線上ランダムな振る舞いをする.

*19

ρ法攻撃で必要となる楕円曲線の点列の個数に関する度数分布は，楕円曲線を定める基礎体のサイズに依存しないことが [60] の実験で示されている. これより，EdDSA で利用される Edwards 曲線に対しても，図 5.2 とほぼ同様の度数分布が得られると期待できる.

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

37

図 5.2 Edwards 曲線上の ECDLP インスタンス (5.6) に対するρ法攻撃において，衝突が起こるまでに必要とした楕円曲線の点列の個数に関するヒストグラム（ただし，横軸は誕生日の逆理に基づく期待値 (4.2) で正規化した）Curve25519 と Curve448 に対する ρ 法による攻撃計算量評価
前述の実験結果と式 (4.3) から，Edwards 曲線上の位数 r を持つ ECDLP に対するρ法による平均攻撃計算量は√√πr· t(f ) ≈ 0.8862 r · t(f )2と見積もれる. ただし，攻撃者有利な条件として，逆元計算による

(5.7)
√

2 倍の高速化も考慮した.

また，t(f ) は反復関数 f の計算時間で，反復関数の定め方から本質的には Edwards 曲線上の加算コストに一致する. 具体的には，Curve25519 の位数は r ≈ 2252 より，Curve25519 における

ECDLP を攻撃するには，平均的に約 0.8862 · 2126 = 2125.8257 回の点の加算が必要となる．また，Curve448 の位数は r ≈ 2446 より，Curve448 における ECDLP を攻撃するには，平均的に約 0.8862 · 2223 = 2222.8257 回の点の加算が必要となる．一方，128 ビットセキュリティレベルのECDSA での利用が推奨されている P-256 曲線に関して，P-256 の位数が r = 2256 より P-256 における ECDLP を攻撃するには，平均的に約 0.8862 · 2128 = 2127.8257 回の点の加算が必要となる（P-256 の具体的な曲線パラメータは [1] を参照）. これより，P-256 と同程度のセキュリティレベ
ルに設定されている Curve25519 と安全性比較すると，Curve25519 上の方が平均的に約 4 倍少な

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

38

表 5.1 様々な座標表現による楕円曲線上のスカラー倍算 nP の計算コスト比較 [9, Section 6]（項目 (1)–(8) は表 3.1 と同じ座標表現. 項目 (8) が Edwards 曲線における射影座標表現）

座標

NAF アルゴリズム

符号付 sliding window 法（幅は 4）

表現

計算コスト

S/M = 0.8

計算コスト

S/M = 0.8

(1)

8M + 6.67S + 1D

13.3M

7.17M + 6.28S + 0.98D

12.2M

(2)

3.33M + 9.33S + 1D

10.8M

2.85M + 8.64S + 0.98D

9.77M

(3)

4.67M + 7S + 2.33D

10.3M

3.69M + 6.48S + 2.16D

8.87M

(4)

6.67M + 4.67S + 0.33D

10.4M

5.09M + 4.32S + 0.19D

8.54M

(5)

10.3M + 1S

11.1M

9.16M + 0.98S

9.94M

(6)

4.67M + 6.33S + 2.33D

9.73M

4.2M + 5.86S + 2.16 D

8.88M

(7)

4.33M + 8.33S + 2.33D

11M

3.84M + 7.99S + 2.16D

10.2M

(8)

6M + 4.33S + 0.33D

9.47M

4.86M + 4.12S + 0.194D

8.16M

い回数の楕円加算で攻撃できる．さらに，ツイスト Edwards 曲線は効率的な点の加算公式を持つ
ため，P-256 よりも Curve25519 上の方がより効率的に点の加算が可能であり，ECDLP をより効率的に攻撃できる．例えば，P-256 よりも Curve25519 の方が最大 2 倍高速に楕円加算ができたと想定すると，P-256 よりも Curve25519 における ECDLP の方が平均的に最大 8 倍高速に攻撃できる．ただし，Curve25519 における ECDLP を攻撃するには，少なくとも 2125.8257 回の楕円加算が必要であり，ほぼ 128 ビットのセキュリティレベルを持つと結論付けれる．

5.3 ECDSA と比較した場合の曲線としての効率性に関する考察
本節では，ECDSA と比較した場合，EdDSA で利用される Edwards 曲線の効率性に関する考察を行う. まず，通常の楕円曲線と Edwards 曲線上の点の加算と 2 倍算の計算コスト比較は表 3.1にまとめてある. 具体的には，基礎体上の乗算コスト M と 2 乗算コスト S の比が S/M = 0.8 の場合，通常の楕円曲線で標準的に利用する射影座標表現における点の加算コストは 10.8M で 2 倍算コストは 9.8M であるのに対し，Edwards 曲線の射影座標表現における点の加算コストは 9.8M
で 2 倍算コストは 6.2M である. これより，同一の基礎体の演算を利用した場合，射影座標表現においては Edwards 曲線の方が点の加算で約 9.4%，点の 2 倍算で約 36.7% 効率的に計算できると見積もれる. また，楕円曲線を利用したディジタル署名では，署名生成時に楕円曲線の点 P のスカ
ラー倍算 nP を行い，署名検証時には楕円曲線の点 P1 , P2 の複数スカラー倍算 n1 P1 + n2 P2 を主に行う. 表 3.1 と同じように，表 5.1 に座標表現による楕円曲線上のスカラー倍算 nP の計算コス
ト比較をまとめておく（詳細は [9, Section 6] を参照*20 ）. 表 5.1 より，同一の基礎体を利用した
場合，スカラー倍算 nP に関しては Edwards 曲線の方が最大 33% 程度効率的に行うことができ*20

NAF アルゴリズムなどの具体的なスカラー倍算アルゴリズムについては [2, 19] を参照.

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

39

表 5.2 様々な座標表現による楕円曲線上の複数スカラー倍算 n1 P1 + n2 P2 の計算コスト比較[9, Section 7]（座標表現は表 3.1 と同じ. 項目 (8) が Edwards 曲線における射影座標表現）

座標

JSF アルゴリズム

加速化 ECDSA 検証アルゴリズム

表現

計算コスト

S/M = 0.8

計算コスト

S/M = 0.8

(1)

10.2M + 7S + 1D

15.8M

6.92M + 3S + 0.33D

9.32M

(2)

5.25M + 10S + 1D

12.8M

4.58M + 4.67S + 0.33D

8.32M

(3)

6.25M + 7.5S + 2.5D

12.2M

4.92M + 3.5S + 1.17D

7.72M

(4)

8.5M + 5S + 0.5D

12.5M

6.5M + 2.33S + 0.5D

8.37M

(5)

12.5M + 1S

13.3M

7.83M + 0.33S

8.1M

(6)

7M + 7.25S + 2.5D

12.8M

5.67M + 3.92S + 1.17D

8.8M

(7)

6.25M + 9.5S + 2.5D

13.8M

4.92M + 4.83S +1.17D

8.78M

(8)

7.75M + 4.5S + 0.5D

11.3M

5.75M + 1.83S + 0.5D

7.22M

ることが分かる. 一方，表 5.2 に座標表現による楕円曲線上の複数スカラー倍算 n1 P1 + n2 P2 の計算コスト比較をまとめておく（詳細は [9, Section 7] を参照*21 ）. 表 5.2 より，同一の基礎体を利用した場合，複数スカラー倍算 n1 P1 + n2 P2 に関しても Edwards 曲線の方が最大 28% 程度効率的に行うことができることが分かる. 特に，EdDSA で利用される Curve25519 においては，高速実装に適した基礎体 Fp を選択しており，基礎体上の演算の高速化分を考慮すれば，更に効率的に（複数）スカラー倍算を行うことが可能となる. 実際，図 5.3 に P-256 曲線*22 による ECDSAと Curve25519 による EdDSA のハードウェア実装による処理時間の比較を示す. ただし，処理時間は鍵生成・署名生成・署名検証の合計時間で，その単位は cycles 数とする（詳細は [13] を参照）. ハードウェアの実装方法により処理時間が大きく異なるため参考程度ではあるが，図 5.3 よりCurve25519 による EdDSA の方が最大 2 倍程度高速であることが分かる.（実際，縦軸が amd64
Zen2 の項目で比べると，図左側の P-256 曲線による ECDSA の処理が約 524288cycles であるのに対し，図右側の Curve25519 による EdDSA の処理が約 262144cycles である.）*21

表 5.2 には JSF アルゴリズムと加速化 ECDSA 検証アルゴリズムの計算コスト比較しかまとめなかったが，[9,Section 7] では他にも Bos-Coster アルゴリズムと point-comb アルゴリズムの計算コスト比較が示されている.
*22 P-256 曲線の基礎体 Fp を定める素数 は p = 2256 − 2224 + 2192 + 296 − 1 であり [1, Annex B]，そのサイズはCurve25519 の基礎体サイズと同程度である.

•

•

•

•

amd64 KabyLake

amd64 Skylake

amd64 BW+AES

Time

•

•

524288

•
•

•

•

•

•
•

•

•
•

•

•

•

•

2097152

•

•
•

••

•

•

•

T:opensslnew

•

•

•

•

•

•

8388608

•

•

•

•

?:openssl••

berry2; 4 x 900MHz; 2016 Broadcom BCM2836; armeabi; Cortex-A7 (410fc075); supercop-20200826

tonido; 1 x 1200MHz; 2010 Marvell Armada 310; armeabi; Armada (562f1311); supercop-20170718

33554432

pmnod145; 64 x 2500MHz; 2018 Cavium ThunderX2 CN9980; aarch64; ThunderX2 (431f0af1); supercop-20191017

a72; 2 x 2100MHz; 2015 Mediatek MT8173; aarch64; A72+crypto (418fd080); supercop-20170904

rpi4ubuntu64; 4 x 1500MHz; 2019 Broadcom BCM2711; aarch64; A72 (410fd083); supercop-20191221

warbear0; 8 x 2000MHz; 2016 AMD Opteron A1100; aarch64; A57+crypto (411fd072); supercop-20200826

jetsontx1; 4 x 1734MHz; 2015 NVIDIA Tegra X1; aarch64; A57+crypto (418fd071); supercop-20191017

googlecoraldev; 4 x 1500MHz; 2018 NXP i.MX 8M; aarch64; A53+crypto (410fd034); supercop-20191221

lepotatoamls905xcc; 4 x 1512MHz; 2016 Amlogic S905X; aarch64; A53+crypto (410fd034); supercop-20191221

par3; 4 x 2000MHz; 2015 Amlogic S905; aarch64; A53+crypto (410fd034); supercop-20170718

pi3bplus; 4 x 1400MHz; 2018 Broadcom BCM2837B0; aarch64; A53 (410fd034); supercop-20200702

gcc116; 8 x 1600MHz; 2014 APM 883208-X1; aarch64; X-Gene (500f0000); supercop-20171218

jetsontk1; 4 x 2065MHz; 2014 NVIDIA Tegra K1; armeabi; Cortex-A15 (413fc0f3); supercop-20170725

novenaimx6; 4 x 1200MHz; 2011 Freescale i.MX6 Quad; armeabi; Cortex-A9+NEON (412fc09a); supercop-20191221

artik; 4 x 1200MHz; 2012 Samsung Exynos 4412?; armeabi; Cortex-A9+NEON (413fc090); supercop-20191221

novenablue; 4 x 1200MHz; 2011 Freescale i.MX6 Quad; armeabi; Cortex-A9+NEON (412fc09a); supercop-20200702•

erpro8fsf2; 2 x 2000MHz; 2011 Cavium Octeon II CN6120; mipso32; Octeon II (cnmips64v2); supercop-20200618

hifiveunleashedriscv; 4 x 1400MHz; 2017 SiFive Freedom U540; riscv64; U54 (sifive,u54-mc); supercop-20191221

nintendowiilinuxngx; 1 x 729MHz; 2006 IBM PowerPC Broadway; ppc32; G3 (G3); supercop-20191221

h8atom; 2 x 1866MHz; 2011 Intel Atom D2500; amd64; Atom (30661); supercop-20200618

h4e450; 2 x 1650MHz; 2011 AMD E-450; amd64; Bobcat (500f20); supercop-20200618

h8bobcat; 2 x 1650MHz; 2011 AMD G-T56N; amd64; Bobcat (500f10); supercop-20171218

mace; 2 x 2000MHz; 2006 AMD Athlon 64 X2; amd64; K8 (40fb2); supercop-20170105

scw1b63b1; 16 x 2100MHz; 2017 Intel Atom C3955; amd64; Goldmont (506f1); supercop-20191017

gcc16; 8 x 2194MHz; 2008 AMD Opteron 8354; amd64; K10 65nm (100f23); supercop-20171218

h3neo; 1 x 1700MHz; 2010 AMD Athlon II Neo K125; amd64; K10 45nm (100f63); supercop-20170105

morningstar; 4 x 3200MHz; 2009 AMD Phenom II X4 955; amd64; K10 45nm (100f42); supercop-20170904

hydra3; 6 x 3300MHz; 2010 AMD Phenom II X6 1100T; amd64; K10 45nm (100fa0); supercop-20171218

hydra5; 4 x 2900MHz; 2011 AMD A8-3850; amd64; K10 32nm (300f10); supercop-20191221

margaux; 4 x 2404MHz; 2007 Intel Core 2 Quad Q6600; amd64; C2 65nm (6fb); supercop-20200618

latour; 4 x 2394MHz; 2007 Intel Core 2 Quad Q6600; amd64; C2 65nm (6fb); supercop-20201018

katana; 2 x 2137MHz; 2006 Intel Core 2 Duo E6400; amd64; C2 65nm (6f6); supercop-20170105

glyme; 2 x 3200MHz; 2010 Intel Core i5-650; amd64; Westmere (20652); supercop-20170105

hydra6; 4 x 3100MHz; 2011 AMD FX-8120; amd64; Bulldozer (600f12); supercop-20171218

calvin; 4 x 4000MHz; 2012 AMD FX-8350; amd64; Bulldozer (600f20); supercop-20171218

hobbes; 4 x 4000MHz; 2012 AMD FX-8350; amd64; Bulldozer (600f20); supercop-20171218

h9trinity; 2 x 2000MHz; 2012 AMD A10-4655M; amd64; Piledriver (610f01); supercop-20200618

hydra9; 2 x 3800MHz; 2012 AMD A10-5800K; amd64; Piledriver (610f01); supercop-20171218

h6sandy; 2 x 2100MHz; 2011 Intel Core i3-2310M; amd64; Sandy Bridge (206a7); supercop-20200618

robin281; 8 x 2600MHz; 2012 Intel Xeon E5-4650L; amd64; SB+AES (206d7); supercop-20170228

hydra8; 4 x 3500MHz; 2012 Intel Xeon E3-1275 V2; amd64; IB+AES (306a9); supercop-20201018

manny613; 12 x 2700MHz; 2013 Intel Xeon E5-2697 v2; amd64; IB+AES (306e4); supercop-20180818

genji460; 20 x 2300MHz; 2014 Intel Xeon E5-2650 v3; amd64; HW+AES (306f2); supercop-20180818
genji202; 24 x 2500MHz; 2014 Intel Xeon E5-2680 v3; amd64; HW+AES (306f2); supercop-20171020
robin204; 12 x 2500MHz; 2014 Intel Xeon E5-2680 v3; amd64; HW+AES (306f2); supercop-20170228
titan0; 4 x 3500MHz; 2013 Intel Xeon E3-1275 V3; amd64; HW+AES (306c3); supercop-20201018
hiphop; 4 x 3100MHz; 2013 Intel Xeon E3-1220 v3; amd64; HW+AES (306c3); supercop-20201018

genji441; 28 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20180818
manny357; 14 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20170228
genji122; 28 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20171020
bolero; 8 x 1700MHz; 2016 Intel Xeon E5-2609 v4; amd64; BW+AES (406f1); supercop-20201018

samba; 4 x 3000MHz; 2015 Intel Xeon E3-1220 v5; amd64; Skylake (506e3); supercop-20201018

sand; 2 x 3300MHz; 2015 Intel Pentium G4400; amd64; Skylake (506e3); supercop-20171218

intelnuci7; 2 x 3500MHz; 2017 Intel Core i7-7567U; amd64; KabyLake (806e9); supercop-20191017

intelnuci8; 4 x 3100MHz; 2018 Intel Core i7-8809G; amd64; KabyLake (906e9); supercop-20191017

kizomba; 4 x 3000MHz; 2017 Intel Xeon E3-1220 v6; amd64; KabyLake (906e9); supercop-20201018

bitvise; 6 x 3200MHz; 2017 Intel Core i7-8700; amd64; CoffeeLake (906ea); supercop-20190910

r24000; 4 x 3300MHz; 2018 Intel Xeon E-2124; amd64; CoffeeLake (906ea); supercop-20201018

cannon; 2 x 2200MHz; 2018 Intel Core i3-8121U; amd64; CannonLake (60663); supercop-20190910

icelake; 4 x 1100MHz; 2020 Intel Core i5-1030NG7; amd64; IceLake (706e5); supercop-20200826

manny1024; 18 x 2700MHz; 2017 Intel Xeon Gold 6150; amd64; SL+512x2 (50654); supercop-20170904
oki; 6 x 3500MHz; 2017 Intel Core i7-7800X; amd64; SL+512x2 (50654); supercop-20181123
pmnod003; 20 x 2400MHz; 2017 Intel Xeon Gold 6148; amd64; SL+512x2 (50654); supercop-20190910
genji548; 40 x 2400MHz; 2017 Intel Xeon Gold 6148; amd64; SL+512x2 (50654); supercop-20191017
genji239; 32 x 2100MHz; 2017 Intel Xeon Gold 6130; amd64; SL+512x2 (50654); supercop-20191017

pmnod076; 20 x 2500MHz; 2019 Intel Xeon Gold 6248; amd64; CascadeLake (50657); supercop-20191017

genji154; 64 x 1300MHz; 2016 Intel Xeon Phi 7210; amd64; KnLanding (50671); supercop-20170228

genji291; 68 x 1400MHz; 2016 Intel Xeon Phi 7250; amd64; KnLanding (50671); supercop-20180818

ryzen; 8 x 2994MHz; 2017 AMD Ryzen 7 1700; amd64; Zen (800f11); supercop-20170904
rumba7; 8 x 3000MHz; 2017 AMD Ryzen 7 1700; amd64; Zen (800f11); supercop-20201018
rumba5; 6 x 3200MHz; 2017 AMD Ryzen 5 1600; amd64; Zen (800f11); supercop-20201018
rumba3; 4 x 3100MHz; 2017 AMD Ryzen 3 1200; amd64; Zen (800f11); supercop-20200906

colossus6; 64 x 2250MHz; 2019 AMD EPYC 7742; amd64; Zen2 (830f10); supercop-20201018

genji346; 64 x 2000MHz; 2019 AMD EPYC 7702; amd64; Zen2 (830f10); supercop-20191017

https://bench.cr.yp.to20201019

Timeaarch64 ThunderX2

aarch64 A72+crypto

aarch64 A72

aarch64 A57+crypto

aarch64 A53+crypto

aarch64 A53

aarch64 X-Genearmeabi Cortex-A15

262144

•

••

••
••

••
••••
••••
••••
•••
••
•

••
••
••
••
••

••
•••
••
•
••

••

amd64-64-24k
••
••
•• ••
•
•
• •

armeabi Cortex-A9+NEON

armeabi Cortex-A7

armeabi Armada

mipso32 Octeon II

riscv64 U54

ppc32 G3

amd64 Atomamd64 Bobcat

amd64 K8

amd64 Goldmont

amd64 K10 65nm

amd64 K10 45nm

amd64 K10 32nm

amd64 C2 65nm

amd64 Westmere

amd64 Bulldozer

amd64 Piledriver

amd64 Sandy Bridge

amd64 SB+AES

amd64 IB+AES

amd64 HW+AES

amd64 BW+AES

amd64 Skylake

amd64 KabyLake

amd64 CoffeeLake

amd64 CannonLake

amd64 IceLake

amd64 SL+512x2

amd64 CascadeLake

amd64 KnLanding

amd64 Zen

amd64 Zen2

crypto_sign
ed25519
implementations

•

•

•
•

•

•

••

•

•

•

•
•

•

•

•
•

•

•

•

•
•

•

••
••
••
•

•
•
•

•
•
•
•
•

•
•
•

•

•
•

•

4194304

•

•

•
•

•

•

•

•

•

•

•

•

•
•
•
•
•

•

•

•

•

•

•
•

•
•

•

•

•
•

•

•

?:ref1016777216

•
•

•

•

•

•
•
•

•

•

•

•
•

•

•
•

•

•

•

•

•
•
••
•••
•
•

•

•
•
•
•
•

•

•

•

ref10

•

•
•

•

•
•

•

1048576

•

•

•
•
•
•
•
•
•
•
•
•

••

•
•

•
•
•
•
•
•
•
••
••
••
•
••

•

•

•
•
••
••

•

•

• ••
• ••

•
••
•
•

?:amd64-51-30k?:amd64-64-24k

•• •
••

•
•
••
•
•

amd64-51-30k

67108864

•

•

ref

https://bench.cr.yp.to20201019

tonido; 1 x 1200MHz; 2010 Marvell Armada 310; armeabi; Armada (562f1311); supercop-20170718

berry2; 4 x 900MHz; 2016 Broadcom BCM2836; armeabi; Cortex-A7 (410fc075); supercop-20200826

pmnod145; 64 x 2500MHz; 2018 Cavium ThunderX2 CN9980; aarch64; ThunderX2 (431f0af1); supercop-20191017

a72; 2 x 2100MHz; 2015 Mediatek MT8173; aarch64; A72+crypto (418fd080); supercop-20170904

rpi4ubuntu64; 4 x 1500MHz; 2019 Broadcom BCM2711; aarch64; A72 (410fd083); supercop-20191221

warbear0; 8 x 2000MHz; 2016 AMD Opteron A1100; aarch64; A57+crypto (411fd072); supercop-20200826

jetsontx1; 4 x 1734MHz; 2015 NVIDIA Tegra X1; aarch64; A57+crypto (418fd071); supercop-20191017

googlecoraldev; 4 x 1500MHz; 2018 NXP i.MX 8M; aarch64; A53+crypto (410fd034); supercop-20191221

lepotatoamls905xcc; 4 x 1512MHz; 2016 Amlogic S905X; aarch64; A53+crypto (410fd034); supercop-20191221

par3; 4 x 2000MHz; 2015 Amlogic S905; aarch64; A53+crypto (410fd034); supercop-20170718

pi3bplus; 4 x 1400MHz; 2018 Broadcom BCM2837B0; aarch64; A53 (410fd034); supercop-20200702

gcc116; 8 x 1600MHz; 2014 APM 883208-X1; aarch64; X-Gene (500f0000); supercop-20171218

jetsontk1; 4 x 2065MHz; 2014 NVIDIA Tegra K1; armeabi; Cortex-A15 (413fc0f3); supercop-20170725

novenaimx6; 4 x 1200MHz; 2011 Freescale i.MX6 Quad; armeabi; Cortex-A9+NEON (412fc09a); supercop-20191221

artik; 4 x 1200MHz; 2012 Samsung Exynos 4412?; armeabi; Cortex-A9+NEON (413fc090); supercop-20191221

novenablue; 4 x 1200MHz; 2011 Freescale i.MX6 Quad; armeabi; Cortex-A9+NEON (412fc09a); supercop-20200702•

erpro8fsf2; 2 x 2000MHz; 2011 Cavium Octeon II CN6120; mipso32; Octeon II (cnmips64v2); supercop-20200618

hifiveunleashedriscv; 4 x 1400MHz; 2017 SiFive Freedom U540; riscv64; U54 (sifive,u54-mc); supercop-20191221

nintendowiilinuxngx; 1 x 729MHz; 2006 IBM PowerPC Broadway; ppc32; G3 (G3); supercop-20191221

h8atom; 2 x 1866MHz; 2011 Intel Atom D2500; amd64; Atom (30661); supercop-20200618

h4e450; 2 x 1650MHz; 2011 AMD E-450; amd64; Bobcat (500f20); supercop-20200618

h8bobcat; 2 x 1650MHz; 2011 AMD G-T56N; amd64; Bobcat (500f10); supercop-20171218

mace; 2 x 2000MHz; 2006 AMD Athlon 64 X2; amd64; K8 (40fb2); supercop-20170105

scw1b63b1; 16 x 2100MHz; 2017 Intel Atom C3955; amd64; Goldmont (506f1); supercop-20191017

gcc16; 8 x 2194MHz; 2008 AMD Opteron 8354; amd64; K10 65nm (100f23); supercop-20171218

h3neo; 1 x 1700MHz; 2010 AMD Athlon II Neo K125; amd64; K10 45nm (100f63); supercop-20170105

morningstar; 4 x 3200MHz; 2009 AMD Phenom II X4 955; amd64; K10 45nm (100f42); supercop-20170904

hydra3; 6 x 3300MHz; 2010 AMD Phenom II X6 1100T; amd64; K10 45nm (100fa0); supercop-20171218

hydra5; 4 x 2900MHz; 2011 AMD A8-3850; amd64; K10 32nm (300f10); supercop-20191221

margaux; 4 x 2404MHz; 2007 Intel Core 2 Quad Q6600; amd64; C2 65nm (6fb); supercop-20200618

latour; 4 x 2394MHz; 2007 Intel Core 2 Quad Q6600; amd64; C2 65nm (6fb); supercop-20201018

katana; 2 x 2137MHz; 2006 Intel Core 2 Duo E6400; amd64; C2 65nm (6f6); supercop-20170105

glyme; 2 x 3200MHz; 2010 Intel Core i5-650; amd64; Westmere (20652); supercop-20170105

hydra6; 4 x 3100MHz; 2011 AMD FX-8120; amd64; Bulldozer (600f12); supercop-20171218

calvin; 4 x 4000MHz; 2012 AMD FX-8350; amd64; Bulldozer (600f20); supercop-20171218

hobbes; 4 x 4000MHz; 2012 AMD FX-8350; amd64; Bulldozer (600f20); supercop-20171218

h9trinity; 2 x 2000MHz; 2012 AMD A10-4655M; amd64; Piledriver (610f01); supercop-20200618

hydra9; 2 x 3800MHz; 2012 AMD A10-5800K; amd64; Piledriver (610f01); supercop-20171218

h6sandy; 2 x 2100MHz; 2011 Intel Core i3-2310M; amd64; Sandy Bridge (206a7); supercop-20200618

robin281; 8 x 2600MHz; 2012 Intel Xeon E5-4650L; amd64; SB+AES (206d7); supercop-20170228

hydra8; 4 x 3500MHz; 2012 Intel Xeon E3-1275 V2; amd64; IB+AES (306a9); supercop-20201018

manny613; 12 x 2700MHz; 2013 Intel Xeon E5-2697 v2; amd64; IB+AES (306e4); supercop-20180818

genji460; 20 x 2300MHz; 2014 Intel Xeon E5-2650 v3; amd64; HW+AES (306f2); supercop-20180818
genji202; 24 x 2500MHz; 2014 Intel Xeon E5-2680 v3; amd64; HW+AES (306f2); supercop-20171020
robin204; 12 x 2500MHz; 2014 Intel Xeon E5-2680 v3; amd64; HW+AES (306f2); supercop-20170228
titan0; 4 x 3500MHz; 2013 Intel Xeon E3-1275 V3; amd64; HW+AES (306c3); supercop-20201018
hiphop; 4 x 3100MHz; 2013 Intel Xeon E3-1220 v3; amd64; HW+AES (306c3); supercop-20201018

genji441; 28 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20180818
manny357; 14 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20170228
genji122; 28 x 2400MHz; 2016 Intel Xeon E5-2680 v4; amd64; BW+AES (406f1); supercop-20171020
bolero; 8 x 1700MHz; 2016 Intel Xeon E5-2609 v4; amd64; BW+AES (406f1); supercop-20201018

samba; 4 x 3000MHz; 2015 Intel Xeon E3-1220 v5; amd64; Skylake (506e3); supercop-20201018

sand; 2 x 3300MHz; 2015 Intel Pentium G4400; amd64; Skylake (506e3); supercop-20171218

intelnuci7; 2 x 3500MHz; 2017 Intel Core i7-7567U; amd64; KabyLake (806e9); supercop-20191017

intelnuci8; 4 x 3100MHz; 2018 Intel Core i7-8809G; amd64; KabyLake (906e9); supercop-20191017

kizomba; 4 x 3000MHz; 2017 Intel Xeon E3-1220 v6; amd64; KabyLake (906e9); supercop-20201018

bitvise; 6 x 3200MHz; 2017 Intel Core i7-8700; amd64; CoffeeLake (906ea); supercop-20190910

r24000; 4 x 3300MHz; 2018 Intel Xeon E-2124; amd64; CoffeeLake (906ea); supercop-20201018

cannon; 2 x 2200MHz; 2018 Intel Core i3-8121U; amd64; CannonLake (60663); supercop-20190910

icelake; 4 x 1100MHz; 2020 Intel Core i5-1030NG7; amd64; IceLake (706e5); supercop-20200826

manny1024; 18 x 2700MHz; 2017 Intel Xeon Gold 6150; amd64; SL+512x2 (50654); supercop-20170904
oki; 6 x 3500MHz; 2017 Intel Core i7-7800X; amd64; SL+512x2 (50654); supercop-20181123
pmnod003; 20 x 2400MHz; 2017 Intel Xeon Gold 6148; amd64; SL+512x2 (50654); supercop-20190910
genji548; 40 x 2400MHz; 2017 Intel Xeon Gold 6148; amd64; SL+512x2 (50654); supercop-20191017
genji239; 32 x 2100MHz; 2017 Intel Xeon Gold 6130; amd64; SL+512x2 (50654); supercop-20191017

pmnod076; 20 x 2500MHz; 2019 Intel Xeon Gold 6248; amd64; CascadeLake (50657); supercop-20191017

genji154; 64 x 1300MHz; 2016 Intel Xeon Phi 7210; amd64; KnLanding (50671); supercop-20170228

genji291; 68 x 1400MHz; 2016 Intel Xeon Phi 7250; amd64; KnLanding (50671); supercop-20180818

ryzen; 8 x 2994MHz; 2017 AMD Ryzen 7 1700; amd64; Zen (800f11); supercop-20170904
rumba7; 8 x 3000MHz; 2017 AMD Ryzen 7 1700; amd64; Zen (800f11); supercop-20201018
rumba5; 6 x 3200MHz; 2017 AMD Ryzen 5 1600; amd64; Zen (800f11); supercop-20201018
rumba3; 4 x 3100MHz; 2017 AMD Ryzen 3 1200; amd64; Zen (800f11); supercop-20200906

colossus6; 64 x 2250MHz; 2019 AMD EPYC 7742; amd64; Zen2 (830f10); supercop-20201018

genji346; 64 x 2000MHz; 2019 AMD EPYC 7702; amd64; Zen2 (830f10); supercop-20191017?:refの比較（詳細は [13] を参照. 処理時間は鍵生成・署名生成・署名検証の合計時間）

図 5.3 P-256 曲線による ECDSA（図左側）と Curve25519 による EdDSA（図右側）のハードウェア実装による処理時間（cycle 数）

aarch64 ThunderX2

aarch64 A72+crypto

aarch64 A72

aarch64 A57+crypto

aarch64 A53+crypto

aarch64 A53

aarch64 X-Genearmeabi Cortex-A15

armeabi Cortex-A9+NEON

armeabi Cortex-A7

armeabi Armada

mipso32 Octeon II

riscv64 U54

ppc32 G3

amd64 Atomamd64 Bobcat

amd64 K8

amd64 Goldmont

amd64 K10 65nm

amd64 K10 45nm

amd64 K10 32nm

amd64 C2 65nm

amd64 Westmere

amd64 Bulldozer

amd64 Piledriver

amd64 Sandy Bridge

amd64 SB+AES

amd64 IB+AES

amd64 HW+AES•

amd64 CoffeeLake

amd64 CannonLake

amd64 IceLake

•

•
••

•
••

amd64 SL+512x2•

amd64 CascadeLake

amd64 KnLanding

amd64 Zen

amd64 Zen2

crypto_sign
ecdonaldp256
implementations

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察
40

第5章

EdDSA で利用される曲線の安全性評価と効率性に関する考察

def rho(E, S, T, r):
L = 16 # Partition number of L-adding addition walka = vector(ZZ, L); b = vector(ZZ, L); R = []for j in range(L):a[j] = randint(0, r)
b[j] = randint(0, r)
R.append(a[j]*S + b[j]*T)# Generation of an initial pointu = randint(0, r); v = randint(0, r); P = u*S + v*T# Main loop
List=[]; List1=[]; flag = 0; count = 0
while (1):j = lift(mod(lift(P[0]), L))u += a[j]; v += b[j]; P += R[j]; count += 1
if lift(mod(lift(P[0]), 1000)) == 0: # Distinguished points
if (P in List1) == True:for i in range(len(List)):if List[i][0] == P:
P1 = List[i][0]; u1 = List[i][1]; v1 = List[i][2]flag=1; # A collision occurs
break
if flag==1:
break
else:
List.append([P, u, v]); List1.append(P)# After a collision between P =u*S + v*T and P1 = u1*S + v1*T
if v==v1:
return False
else:
k = mod(u1-u, r)*(v-v1).inverse_mod(r); # The solution of ECDLP
print("count = ", count)# Number of elliptic additions

return k
図 5.4 ECDLP に対するρ法攻撃アルゴリズムの Sage スクリプト

41

42

参考文献
[1] American National Standards Institute. American National Standard for Financial Services X9.62-2005, Public key cryptography for the ﬁnancial services industry: The elliptic
curve digital signature algorithm (ECDSA), 2005.
[2] Roberto M Avanzi. The complexity of certain multi-exponentiation techniques in cryptography. Journal of Cryptology, Vol. 18, No. 4, pp. 357–373, 2005.
[3] Daniel V Bailey, Lejla Batina, Daniel J Bernstein, Peter Birkner, Joppe W Bos, HsiehChung Chen, Chen-Mou Cheng, Gauthier Van Damme, Giacomo de Meulenaer, Luis
J Dominguez Perez, et al. Breaking ECC2K-130. IACR ePrint Archive 2009/541, 2009.
[4] Daniel J Bernstein. Curve25519: New Diﬃe-Hellman speed records. In Public Key
Cryptography–PKC 2006, Vol. 3958 of Lecture Notes in Computer Science, pp. 207–228.
Springer, 2006.
[5] Daniel J Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters.
Twisted Edwards curves. In Progress in Cryptology–AFRICACRYPT 2008, Vol. 5023
of Lecture Notes in Computer Science, pp. 389–405. Springer, 2008.
[6] Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. Highspeed high-security signatures. Journal of Cryptographic Engineering, Vol. 2, No. 2, pp.
77–89, 2012.
[7] Daniel J Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann. Faster elliptic-curve discrete logarithms on FPGAs.
IACR ePrint Archive 2016/382, 2016.
[8] Daniel J Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, and Bo-Yin Yang.
EdDSA for more curves. IACR ePrint Archive 2015/677, 2015.
[9] Daniel J Bernstein and Tanja Lange. Faster addition and doubling on elliptic curves.
In Advances in Cryptology–ASIACRYPT 2007, Vol. 4833 of Lecture Notes in Computer
Science, pp. 29–50. Springer, 2007.
[10] Daniel J Bernstein and Tanja Lange. Inverted Edwards coordinates. In Applied Algebra,
Algebraic Algorithms, and Error-Correcting Codes (AAECC 2007), Vol. 4851 of Lecture
Notes in Computer Science, pp. 20–27. Springer, 2007.

参考文献

43

[11] Daniel J Bernstein and Tanja Lange. Explicit-formula database (EFD). https://www.
hyperelliptic.org/EFD/, since 2007.
[12] Daniel J Bernstein and Tanja Lange. SafeCurves: Choosing safe curves for elliptic-curve
cryptography. https://safecurves.cr.yp.to/, since 2014.
[13] Daniel J Bernstein and Tanja Lange. eBACS: ECRYPT benchmarking of cryptographic
systems. http://bench.cr.yp.to/, version 2019.08.05.
[14] Daniel J Bernstein, Tanja Lange, and Peter Schwabe. On the correct use of the negation
map in the Pollard rho method. In Public Key Cryptography–PKC 2011, Vol. 6571 ofLecture Notes in Computer Science, pp. 128–146. Springer, 2011.
[15] Ian Blake, Gerald Seroussi, Gadiel Seroussi, and Nigel Smart. Elliptic Curves in Cryptography, Vol. 265. Cambridge university press, 1999.
[16] Joppe W Bos, Marcelo E Kaihara, Thorsten Kleinjung, Arjen K Lenstra, and Peter L
Montgomery. Solving a 112-bit prime elliptic curve discrete logarithm problem on game
consoles using sloppy reduction. International Journal of Applied Cryptography, Vol. 2,
No. 3, pp. 212–228, 2012.
[17] Joppe W Bos and Arjen K Lenstra. Topics in Computational Number Theory Inspiredby Peter L. Montgomery. Cambridge University Press, 2017.
[18] ECC Brainpool. ECC Brainpool standard curves and curve generation. https://www.
teletrust.de/fileadmin/files/oid/oid_ECC-Brainpool-Standard-curves-V1.
pdf, 2005.
[19] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim
Nguyen, and Frederik Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC press, 2005.
[20] Harold Edwards. A normal form for elliptic curves. Bulletin of the American mathematicalsociety, Vol. 44, No. 3, pp. 393–422, 2007.
[21] Gerhard Frey and Hans-Georg Rück. A remark concerning m-divisibility and the discrete
logarithm in the divisor class group of curves. Mathematics of computation, Vol. 62, No.
206, pp. 865–874, 1994.
[22] Steven D Galbraith. Mathematics of Public Key Cryptography. Cambridge University
Press, 2012.
[23] Steven D Galbraith and Pierrick Gaudry. Recent progress on the elliptic curve discrete
logarithm problem. Designs, Codes and Cryptography, Vol. 78, No. 1, pp. 51–72, 2016.
[24] Robert Gallant, Robert Lambert, and Scott Vanstone. Improving the parallelized Pollard
lambda search on anomalous binary curves. Mathematics of Computation, Vol. 69, No.
232, pp. 1699–1705, 2000.
[25] The Sage Group. SageMath: Open-source mathematical software system. https://www.
sagemath.org/.

参考文献

44

[26] Mike Hamburg. Ed448-Goldilocks, a new elliptic curve. IACR ePrint Archive 2015/625,
2015.
[27] Darrel Hankerson, Alfred J Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Science & Business Media, 2006.
[28] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards
curves revisited. In Advances in Cryptology–ASIACRYPT 2008, Vol. 5350 of Lecture
Notes in Computer Science, pp. 326–343. Springer, 2008.
[29] Ming-Deh Huang, Michiel Kosters, Christophe Petit, Sze Ling Yeo, and Yang Yun. Quasisubﬁeld polynomials and the elliptic curve discrete logarithm problem. Journal of Mathematical Cryptology, Vol. 14, No. 1, pp. 25–38, 2020.
[30] Michael J Jacobson, Neal Koblitz, Joseph H Silverman, Andreas Stein, and Edlyn Teske.
Analysis of the xedni calculus attack. Designs, Codes and Cryptography, Vol. 20, No. 1,
pp. 41–64, 2000.
[31] Simon Josefsson and Ilari Liusvaara. RFC 8032: Edwards-curve digital signature algorithm (EdDSA). Internet Engineering Task Force (IETF). https://tex2e.github.io/
rfc-translater/html/rfc8032.html, 2017.
[32] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation, Vol. 48, No.
177, pp. 203–209, 1987.
[33] Momonari Kudo, Yuki Yokota, Yasushi Takahashi, and Masaya Yasuda. Acceleration ofindex calculus for solving ECDLP over prime ﬁelds and its limitation. In Cryptology and
Network Security (CANS 2018), Vol. 11124 of Lecture Notes in Computer Science, pp.
377–393. Springer, 2018.
[34] Takuya Kusaka, Sho Joichi, Ken Ikuta, Md Al-Amin Khandaker, Yasuyuki Nogami,
Satoshi Uehara, Nariyoshi Yamai, and Sylvain Duquesne. Solving 114-bit ECDLP for
a Barreto-Naehrig curve. In Information Security and Cryptology (ICISC 2017), Vol.
10779 of Lecture Notes in Computer Science, pp. 231–244. Springer, 2017.
[35] A Langley, M Hamburg, and S Turner. RFC 7748: Elliptic curves for security. Internet
Engineering Task Force (IETF). https://tools.ietf.org/pdf/rfc7748.pdf, 2016.
[36] Alfred J Menezes, Tatsuaki Okamoto, and Scott A Vanstone. Reducing elliptic curve
logarithms to logarithms in a ﬁnite ﬁeld. IEEE Transactions on information Theory,
Vol. 39, No. 5, pp. 1639–1646, 1993.
[37] Victor S Miller. Use of elliptic curves in cryptography. In Advances in Cryptology–
CRYPTO 1985, Vol. 218 of Lecture Notes in Computer Science, pp. 417–426. Springer,
1985.
[38] Institute of Electrical and Electronics Engineers. IEEE 1363-2000: Standard speciﬁcations for public key cryptography. https://perso.telecom-paristech.fr/guilley/
recherche/cryptoprocesseurs/ieee/00891000.pdf, 2000.

45

参考文献

[39] Christophe Petit, Michiel Kosters, and Ange Messeng. Algebraic approaches for theelliptic curve discrete logarithm problem over prime ﬁelds. In Public-Key Cryptography–
PKC 2016, Vol. 9615 of Lecture Notes in Computer Science, pp. 3–18. Springer, 2016.
[40] Stephen Pohlig and Martin Hellman. An improved algorithm for computing logarithms
over GF(p) and its cryptographic signiﬁcance. IEEE Transactions on information Theory,
Vol. 24, No. 1, pp. 106–110, 1978.
[41] John M Pollard. Monte carlo methods for index computation (mod p). Mathematics ofcomputation, Vol. 32, No. 143, pp. 918–924, 1978.
[42] John M Pollard. Kangaroos, monopoly and discrete logarithms. Journal of cryptology,
Vol. 13, No. 4, pp. 437–447, 2000.
[43] Certicom Research. Standards for eﬃcient crytography 2: Recommended elliptic curve
domain parameters. https://www.secg.org/SEC2-Ver-1.0.pdf, 2000.
[44] Certicom Research. Standards for eﬃcient crytography, SEC1: Elliptic curve cryptography (version 2.0). https://www.secg.org/sec1-v2.pdf, 2009.
[45] Certicom Research.

The Certicom ECC Challenge.

https://www.certicom.com/

content/certicom/en/the-certicom-ecc-challenge.html, since 1997.
[46] Takakazu Satoh, Kiyomichi Araki, et al. Fermat quotients and the polynomial time
discrete log algorithm for anomalous elliptic curves. Rikkyo Daigaku sugaku zasshi, Vol. 47,
No. 1, pp. 81–92, 1998.
[47] Igor Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic
curve in characteristic p. Mathematics of computation, Vol. 67, No. 221, pp. 353–356, 1998.
[48] Igor A Semaev. Summation polynomials and the discrete logarithm problem on elliptic
curves. IACR ePrint Archive 2004/31, 2004.
[49] Daniel Shanks. Class number, a theory of factorization, and genera. In Symposia in Pure
Mathematics, Vol. 20, pp. 415–440, 1971.
[50] Joseph H Silverman. The xedni calculus and the elliptic curve discrete logarithm problem.
Designs, Codes and Cryptography, Vol. 20, No. 1, pp. 5–40, 2000.
[51] Joseph H Silverman. The Arithmetic of Elliptic Curves, Vol. 106. Springer Science &Business Media, second edition, 2009.
[52] Nigel P Smart. The discrete logarithm problem on elliptic curves of trace one. Journalof cryptology, Vol. 12, No. 3, pp. 193–196, 1999.
[53] Edlyn Teske. Speeding up Pollard’s rho method for computing discrete logarithms. In Algorithmic Number Theory (ANTS 1998), Vol. 1423 of Lecture Notes in Computer Science,
pp. 541–554. Springer, 1998.
[54] Edlyn Teske. On random walks for Pollard’s rho method. Mathematics of computation,
Vol. 70, No. 234, pp. 809–825, 2001.
[55] Paul C Van Oorschot and Michael J Wiener. Parallel collision search with cryptanalytic

46

参考文献

applications. Journal of cryptology, Vol. 12, No. 1, pp. 1–28, 1999.
[56] Lawrence C Washington. Elliptic Curves: Number Theory and Cryptography. CRC press,
second edition, 2008.
[57] Erich Wenger and Paul Wolfger. Solving the discrete logarithm of a 113-bit Koblitz curvewith an FPGA cluster. In Selected Areas in Cryptography (SAC 2014), Vol. 8781 of
Lecture Notes in Computer Science, pp. 363–379. Springer, 2014.
[58] Michael J Wiener and Robert J Zuccherato. Faster attacks on elliptic curve cryptosystems.
In Selected Areas in Cryptography (SAC 1998), Vol. 1556 of Lecture Notes in Computer
Science, pp. 190–200. Springer, 1998.
[59] Masaya Yasuda, Tetsuya Izu, Takeshi Shimoyama, and Jun Kogure. On random walks of
Pollard’s rho method for the ECDLP on Koblitz curves. Journal of Math-for-Industry,
Vol. 3, No. 3, pp. 107–112, 2011.
[60] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, and Tetsuya Izu. Computational
hardness of IFP and ECDLP. Applicable Algebra in Engineering, Communication andComputing, Vol. 27, No. 6, pp. 493–521, 2016.
[61] Kazuhiro Yokoyama, Masaya Yasuda, Yasushi Takahashi, and Jun Kogure. Complexity
bounds on Semaev’s naive index calculus method for ECDLP. Journal of Mathematical
Cryptology, Vol. 14, No. 1, pp. 460–485, 2020.
[62] 篠 原 直 行, 野 呂 正 行, 横 山 和 弘.
数 計 算 法.

楕円曲線上の離散対数問題に関する指CRYPTREC-EX-2602-2016:

https://www.cryptrec.go.jp/exreport/

cryptrec-ex-2602-2016.pdf, 2016.
[63] 富 士 通 株 式 会 社, 株 式 会 社 富 士 通 研 究 所.
全 性 比 較.

楕 円 曲 線 暗 号 と RSA 暗 号 の 安

https://www.fujitsu.com/jp/group/labs/documents/resources/tech/external-activities/crypto/eccvsrsa-20100820.pdf, 2010 年 8 月 20 日.