離散対数問題の困難性に関する計算量についての調査・研究報告書

2007 年 1 月

1

はじめに

ここでは, 暗号技術の基礎となる数学的なアルゴリズムが持つ困難性, 特に有限体上の離散対数問題及び有限体上の楕円曲線上の離散対数問題の困難性について，最近の研究について調査した結果について報告する。本レポートの構成は次の通りである：第２節では, 有限体上の離散対数問題について述べる. 次に, 第３節では,有限体上の楕円曲線上の離散対数問題について述べる.

2有限体上の離散対数問題

素因数分解問題と有限体上の離散対数問題は, 古くから知られている代表的な計
算量的に困難な問題である. 素因数分解問題とは, 合成数 N が与えられた時, その非自明な約数 d (d | N, 1 < d < N ) を求める問題である. （一般的には, N を素数の冪積で表示することを言うが, 非自明な約数が存在すればそれを求める問題に効率よく帰着されること, さらに, ２つの素数の積の合成数の場合を考える事が多いため, こう定義される事が多い.）また, 有限体上の離散対数問題とは, 有限体のx
乗法群 F×q の二つの要素 t, u が与えられた時, u = t なる整数 x が存在すれば, それを求める問題である. ここで, 整数 x は t の位数を法として一意に定まり, logt uなどと表され, t を底とした u の離散対数と呼ばれる. 有限素体上の場合に, 従来
は指数と呼ばれていたものである. 1976 年に, Diffie と Hellman により公開鍵暗号の概念が提案され, その実現例として, 有限体上の離散対数問題の困難さに基づく
Diffie-Hellman 鍵交換方式が提案された. 続く翌年の 1977 年には, Rivest, Shamirと Adleman により素因数分解問題の困難さに基づく公開鍵暗号である RSA 暗号が提案され, 上記２つの問題に対する高速なアルゴリズムを見つけるという研究は,直接的に, これらの問題に基づく公開鍵暗号方式の安全性の研究を意味することとなった. こういった背景や, 計算機の能力の飛躍的な向上も追い風となり, これらのアルゴリズムについては, 実用的な公開鍵暗号方式の安全性の研究と密接な関係を保ちながら活発な研究がなされてきた.
本節では, 有限体上の離散対数問題に対する, 現在までのところ漸近的に最高速なアルゴリズムである, 数体ふるい法について, 最近の結果まで含めて概説する.
本節の構成は次の通りである. まず 2.1 節で, Schirokauer による有限体上の離散対数問題に対する数体ふるい法の概説を行う. 2.2 節では, NFS の詳しい解説, 2.3
節では拡大体上の場合について簡単にふれ, 2.4 節では計算量評価について述べる.
次に, 2.5 節では, 現在までに行われている有限体上の離散対数問題に対する数値実験について述べる. 最後に, 2.6 節で安全な鍵サイズについて考察する.
以下では, p を素数, n を自然数とし, q = pn とする.

1

2.1

数体ふるい法 (NFS)

ここでは, [26] に従って, 有限体上の離散対数問題への数体ふるい法の解説を行う.
数体ふるい法 (Number Field Sieve. 以下, NFS と略す.) は, Pollard によってア
イデアが提案され [23], Lenstra 兄弟, Manasse 等によって, N = re ± s (r, s は小さな自然数) の形をした合成数に対する素因数分解アルゴリズムとして提案されたものである [18]. その後さらなる改良が加えられ, 一般の合成数に対しても有効なものとなった. 前者を特殊数体ふるい法 (SNFS), 後者を一般数体ふるい法 (GNFS)と呼ぶことが多い.
この NFS は, 1920 年代に Kraitchik によって導入された指数計算法 (Index Calculus Method) と呼ばれるアルゴリズムのクラスに属すものである. NFS 以前の指数計算法に属すアルゴリズムとしては, Pomerance による２次ふるい法 [25] が漸
近的に高速な代表的なものであった. 素因数分解アルゴリズムとしては, NFS が漸
近的に最速である. また, 計算時間は, 準指数時間アルゴリズムと呼ばれるクラスに属するものであって, 多項式時間アルゴリズムと指数時間アルゴリズムの中間的なものである. NFS を用いた合成数 N の素因数分解の計算量は, 次で与えられる：

LN [1/3, (64/9)1/3 ],但し, LN [s, c] は, LN [s, c] = exp((c + o(1))(log N )s (log log N )1−s ) で定義されるもので (s, c は正の実数. s は 0 ≤ s ≤ 1 を満たし, o(1) は N が十分大きいとき 0 に収束するものである.), L 表示などと呼ばれる. (上記のものは GNFS の計算量であって, SNFS の場合は, LN [1/3, (32/9)1/3 ] で与えられる.)
素因数分解と離散対数問題それぞれへの NFS の概略を述べると, 以下のようになる：今, N を分解したい大きな合成数とする. 何らかの方法で代数体とその整環
O (必ずしも極大とは限らない) を選び, 環準同型写像 φ : O → Z/N Z が存在するとする. このとき smoothness と呼ばれる (後で定義する) 性質を持つ O の要素を“ふるい” にかけて十分たくさん集め, 何らかの方法で代数体 K = Q(α)(α の Q 上の最小多項式を f とする. 但し, ある整数 m があって, f (m) ≡ 0 (mod N ) とする. ) を選び, その整環 O = Z[α] から Z/N Z への環準同型写像 φ : O 3 a − bα 7→
a − bm mod N ∈ Z/N Z が構成できる. この時, smoothness とよばれる性質 (整数であれば, その素因子が小さい. また, 代数的整数であれば, そのノルムの素因子が小さい. ) を持つ O の要素である a − bα, a − bm たちをたくさん集め, それらを用いて O の要素 δ 2 , γ 2 (δ, γ ∈ O) で, φ(δ 2 ) ≡ φ(γ 2 ) mod N なるものを構成する. 集められた smoothness な O の要素たちの間の乗法的な性質をうまく使い,
Gaußの消去法などの行列演算を用いて, このような平方数が構成出来る. この時,
φ(δ) 6≡ ±φ(γ) mod N であれば, GCD(φ(δ) − φ(γ), N ) は N の非自明な約数とな2

り, 素因数分解が成功する. (素因数分解に関する NFS の詳しい解説については,
Lenstra 兄弟による [17] を参照.)
一方, Fq 上の離散対数問題の場合を考える. 素因数分解と同様に, 何らかの方法で代数体の整環 O と環準同型写像 φ : O → Fq が与えられているとき, smoothness という性質を持つ O の要素をたくさん集め, それらを用いて O の要素 δ l , γ l (δ, γ ∈ O)
で, ある整数 x が存在して φ(δ l ) = utx · φ(γ l ) なるものを構成する. 但し, l は q − 1の素因子とする. この時, x ≡ − logt u (mod l) となり, x mod l が求まる. 一般的には, x mod lν (lν | (q − 1)) を求めることに離散対数問題を解く事は帰着される.
このように見ると, 素因数分解の場合と離散対数問題の場合の NFS の適用方法は,
本質的にはほとんど同じで, 違いは, 整環 O の中で “平方数” を構成し, それを“開平” する必要があるか, “l 乗の要素” を構成する必要があるか, であると言えよう. また, 有限素体 Fp 上の離散対数問題を NFS を使って解く計算量は, サイズがp と同じ合成数の素因数分解と同じで Lp [1/3, (64/9)1/3 ] で与えられる. 一般の有限体の場合は, q(= pn ) を十分大きくとるとき, n が p のサイズと比較して小さい場
合 (n < (log p)1/2 ) は, 素体の場合と同じで Lq [1/3, (64/9)1/3 ] で与えられるが, 何の条件もない場合は, Lq [1/2, c1 ] (c1 は定数) となるものしか知られていない [28].

2.2

有限体上の離散対数問題への NFS有限体上の離散対数問題への NFS は, Gordon [8] によって最初提案され, Schirokauer [26] によって改良された. ここでは, Schirokauer のアルゴリズムの解説を行う. まず, いくつか用語を準備する. 正の実数 B に対して, 有理整数 a が B-smoothであるとは, a の素因子が全て B 以下であるときに言う. 同様に, 代数体 K, K の整数環 OK の要素 γ が B-smooth であるとは, そのノルムの値 NK/Q (γ) が B-smoothであるときに言う.
Fq 上の離散対数問題を考えるとき, その答えは一般には mod (q − 1) で一意に求まるが, q − 1 の全ての素因子 l について, mod lνl (q−1) (νl は l 進付値) で答えが求められれば, 中国人剰余定理を用いて mod (q − 1) での答えを求めることが出来る. 以
下では, 簡単のために l は奇素数で νl (q − 1) = 1 の場合, つまり, mod l で求めればよい場合を考える. この節での解説は簡単のため n = 1 とし (Fq = Fp の場合. n > 1の場合は 2.3 節で簡単に触れる.), 離散対数問題のパラメータ t, u ∈ Fp = Z/pZ は共にアルゴリズムの中で定める smoothness bound に関して smooth な要素だとしておく. より一般の場合は, 原論文 [26, 27] を参照.

Step 1. 多項式の選択
NFS を行うためには, 代数体 K = Q(α) を選ぶ, すなわち K を生成する多項式を選ぶ必要がある. 一般的に良く知られている方法は以下である：
3

自然数 d (どの程度の大きさのものを選べば良いかなどについては, 2.4 節で述べる.) を取り, m = [p1/d ] とおき,

p=

d
X

ai mi

i=0

Pd
と p を m で展開する. これにより, d 次の多項式 f (X) = i=0 ai X i ∈ Z[X] を得る. この多項式 f は, Q 上既約であることが示せる [2]. この f の根 α ∈ C を用いて, K = Q(α), 整環 O = Z[α] と取る. このとき, 一般に, O は K の整数環
OK とは一致しない. また, φ : Z[α] 3 g(α) 7→ g(m) mod p ∈ Z/pZ = Fp (但し,g(X) ∈ Z[X]) で定義される φ は, 環準同型写像となる.
この多項式 f は以下の条件を満足している：(i) f の各係数は p1/d 程度の大きさである.
(ii) f mod p の根は高々 p1/d 程度の大きさである.
さらに, ここでは(iii) f は monic である.
(iv) l は f の判別式を割らない.
という条件も加えておく. 条件 (i), (ii) は, NFS の計算量評価に影響を与えるが,(iii), (iv) は必要なものではなく [26, 27], 説明を簡単にするためのものである.
Step 2. ふるい (Sieve)
Smoothness bound と呼ばれる正の実数 B, ふるい (sieve) にかける代数的整数の探索範囲を決めるパラメータとなる正の実数 C を取る. (選び方などは, 2.4 節で述べる)|a|, |b| ≤ C である互いに素な有理整数の組 (a, b) ∈ Z × Z で, a − bm, a − bα がB-smooth なものをたくさん集める. このような (a, b) の組の全体を S とする.
ここで, |a − bm|, |N (a − bα)| の大きさは|a − bm| ≤ C(1 + p1/d ), |N (a − bα)| = |bd f (a/b)| ≤ (1 + d)C d p1/d

(1)と評価出来る. これら, ふるいにかける代数的整数のサイズが小さいことが, 他の指数計算法に属すアルゴリズムと比較して NFS が高速である主な理由である. 具
体的なふるいの方法については, [17] などを参照.

Step 3. 指数ベクトルの計算
ここでは, Step 2 で集めた smooth な代数的整数たちの間の乗法的な関係式を見つけるための準備をする. B 以下の素数の個数を π(B), B 以下の素数 q1 , . . . , qπ(B)の全体を BQ で表す. 同様に, B 以下のノルムを持つ OK の 1 次の素イデアル,4

及び [OK : O] の素因子の上にある OK の素イデアルの個数を Π(B), これらを
q1 , . . . , qΠ(B) で表し, その全体を BK とする. BQ ∪ BK の要素は, 因子基底とも呼ばれる. さらに, 素イデアル q ⊂ OK に対して, νq で q 進付値を表すものとする.
このとき, 各 (a, b) ∈ S について, Zπ(B)+Π(B)+d の要素となるベクトル Va,b を次で計算する：
最初の π(B) 番目までは

νq1 (a − bm), . . . , νqπ(B) (a − bm)
これに続く Π(B) 個は

νq1 (a − bα), . . . , νqΠ(B) (a − bα)で与えられるものとする. ここで, イデアル (a − bα)OK を割る素イデアルは BKの要素しか出てこないことに注意しておく ([6] の Lemma 10.5.1). 各 q ∈ BK について, q が 1 次の素イデアルの場合の νq (a − bα) の値は, N (q) = q 0 とすると,
νq0 (N (a − bα)) で与えられる. [OK : O] の素因子を割る OK の素イデアルの場合の計算については [6] の 10.5 章に詳しい解説がある.
最後に, 残りの d 個の成分の計算については, Schirokauer によって提案された指標 λ を用いる [26].
Γ = {γ ∈ OK | N (γ) 6≡ 0 mod l}
なる OK の部分集合を考える. ` が l を割る OK の素イデアルの全体を動くとして, ² を #(OK /`)× たちの最小公倍数とする. 今, l は f の判別式の約数ではなく,
即ち, K で不分岐であるので, 任意の γ ∈ Γ に対して

γ ² ≡ 1 mod lが言える. このとき, λ : Γ → lOK /l2 OK を λ(γ) = (γ ² − 1) + l2 OK で定める.
lOK /l2 OK の基底を {bj l + l2 OK }1≤j≤d とすれば
²

γ −1≡

d
X

λj (γ)bj l mod l2

j=1と書けるので, λ を d 個の成分で表せる. 各 λj : Γ → Z/lZ と λ は, 任意の γ, γ 0 ∈ Γ
に対して, 定義より明らかに λ(γγ 0 ) = λ(γ) + λ(γ 0 ), λj (γγ 0 ) = λj (γ) + λj (γ 0 ) なる準同型性を持つ. (この指標 λ は, 本質的に Fermat 商と呼ばれるものであり, l 進対数関数の近似を与えている.)5この指標を用いて, 残る d 個の成分はλ1 (a − bα), . . . , λd (a − bα)と定める.
ここで, 上で定めたベクトル Va,b の以降での役割について簡単に見ておく. まず,a − bm = ±Πq∈BQ q νq (a−bm) ,(2)(a − bα)OK = Πq∈BK qνq (a−bα)(3)が成り立っている事に注意しておく. 2 節の冒頭でも簡単に述べたが, このような関係式が Step 2 で十分たくさん集められており, これらを利用して OK の要素のl 乗を構成することになる. すなわち, Ok の二つの要素 δ, γ, 整数 x, ea,b で

utx ·

Y

(a − bm)ea,b = δ l ,(4)(a,b)∈SY(a − bα)ea,b = γ l(5)(a,b)∈S

を満たすものが発見できたとする.
このとき,φ(δ)l = utx · φ(γ)l(6)

が成り立ち, x ≡ − logt u mod l が求まる.
具体的には, Step 4 で説明する Gaußの消去法などを用いた行列の計算で求められるのであるが, (5) の左辺のような代数的整数が, 正確に, ある OK の要素の l 乗であるということを見るには Va,b の最初の π(b) + Π(B) 個の成分だけでは情報が十分でない. 一般的には, イデアルとしての l 乗しか構成出来ない. 仮にそれが単項イデアルであったとしても, 単数倍は無視できず不確定さが残る. この問題は,Schirokauer によって導入された上述の指標 λ を用いれば解決できる.
実際, 次が成り立つ：
定理 1 (Schirokauer [26]). 代数体 K, その整数環 OK , 素数 l は K で不分岐とする. λ, Γ などは上述のものとすると, γ ∈ Γ が(i) 任意の素イデアル p ⊂ OK について νp (γ) ≡ 0 mod l,(ii) λ(γ) = 0(全ての λj (γ) = 0)を満たすとする. このとき, 素数 l が代数体 K の類数と互いに素であり, かつ OKの単数で l2 を法として 1 と合同なものは全て OK の要素の l 乗となるか, 又はLeopoldt 予想が正しいと仮定すると, γ は OK のある要素の l 乗である.

6有限体上の離散対数問題を考える場合, 一般に, l は十分大きな素数であると考えてよいので, K の類数と l は互いに素だと期待され, 単数に関する条件も heuristicには満たしていると期待されるので [26], この定理を用いれば, 最初の π(b) + Π(B)
個の成分を使ってイデアルとして l 乗のものを構成し, かつ残りの d 個の成分が全部 0 になるような関係式を求めれば (上述の集合 S, x, ea,b ∈ Z/lZ を求める事), 要
素としての l 乗が構成出来る.
ここで注意として, 一般に, 上述の δ, γ は Z[α] の要素とならない場合も考えられる. しかしながら, f 0 (α)OK ⊂ Z[α] が成り立つので, (4), (5) の両辺に f 0 (α)l を乗じてφ(f 0 (α)δ)l = utx · φ(f 0 (α)γ)lを得る.

Step 4. 連立方程式の解法
ここでは, Step 3 で求めた各 (a, b) ∈ S に対するベクトル Va,b を使って, 実際に代数的整数の l 乗を構成し, logt u を求める. まず, 離散対数問題のパラメータ t, uに対しても Zπ(B)+Π(B)+d のベクトルを定義しておく. Vt は, 最初の π(B) 個の成分が νq1 (t), . . . , νqπ(B) (t) で, 残りは全て 0 となるものとする. Vu も同様で, 最初のπ(B) 個の成分が νq1 (u), . . . , νqπ(B) (u) で, 残りは全て 0 となるものとする. 今, Aを, 最初の 1 列が Vt , 他の列は Va,b として得られる (π(B) + Π(B) + d) × (#S + 1)型の行列とする. A = (ai,j ) とする. 但し, S は #S + 1 ≥ π(B) + Π(B) + d を満たすとする. このとき次の連立方程式を考える：
AX ≡ −Vu mod l(7)

この線形方程式が解けるためには, Z/lZ 上の行列 A mod l = (ai,j mod l) のランクが π(B) + Π(B) + d となればよく, ランクがこれより小さければ S の要素をさらに増やすか, Step 2 で定めたパラメータ C を大きく取り直すなどする必要がある.
この解を (x, . . . , ea,b , . . .) とすれば, Step 3 で考察した関係式 (4), (5) が得られることが簡単に分かる.
ここで, 連立方程式の解法に用いるアルゴリズムであるが, 一般によく知られているものは Gaußの消去法と呼ばれるものである. これは, 行列のサイズの 3 乗のオーダの計算量である事が知られているが, 現在の NFS の実装サイズでは大きすぎて実装には向いていないと考えられている. 行列が疎であるような場合は, conjugate
gradient method や Lanczos 法と呼ばれるアルゴリズムが実用的であることが知られている. また, Wiedemann による coordinate recurrence method は理論的には
高速で, 行列のサイズの 2 + o(1) 乗のオーダの計算量である [22, 30].

7

2.3

Fpn (n > 1) 上の離散対数問題への NFS

この節では, 素体上でない場合の離散対数問題への NFS について簡単に説明する. 詳しくは [27] を参照. まずは, Fq = Fpn の構成から. r を, r ≡ 1 mod n となる素数の中で, n と (r − 1)/e (e は p mod r の位数) が互いに素となる最小のものとする. ζr を 1 の原始 r 乗根とし, Q(ζr ) の部分体で Q 上 n 次のものを F とする. p は F で惰性するので
OF /pOF ' Fqが成立する. t1 を TF/Q (ζr ) (ζr のトレース), t2 , . . . , tn を t1 の共役元とする. このPn
とき, t1 , . . . , tn は OF の整数基底となる [3]. Fq は { j=1 aj tj | 0 ≤ aj < p} と同一視することにする. 一般 Riemann 予想 (ERH) を仮定すれば, 上の素数 r はr ≤ (log q)c3 (c3 は定数) を満たすものが取れる [4].
この数体 F を用いて, 素体と同様に NFS を適用することが出来る. 多項式の選択も m = [p1/d ] とおいて p を m で展開する方法で行い, F (α) が F の d 次拡大体だとする. Smooth な要素も, a − bm, a − bα (a, b ∈ OF ) たちを集めることになる.

2.4

NFS の漸近的な計算量評価

ここでは, 前節で見た Schirokauer のアルゴリズムの計算量評価を与える. アル
ゴリズムの中で出てきていたパラメータ d, B, C なども最適な値を求める. Step
2 で集められる smooth な要素の大きさの評価は (1) から |(a − bm)N (a − bα)| ≤C(p1/d + 1)(1 + d)C d p2/d ≤ 2dC d+1 p2/d で与えられる. この最右辺の値を x とする.
次に, Step 4 での行列のサイズについて, #S + 1 は π(B) + Π(B) + d 以上である
必要があり, π(B) + Π(B) + d は (d + 1)B + d で上から押さえられるので, もし拡
大次数 d が d = B o(1) とおけるならば N = #S は, N = B 1+o(1) とおける. これは行列のサイズも与えている.
ψ(x, B) で, x 以下の B-smooth な自然数の個数を表すことにする. すると,
smooth な組 (a, b) を N 個集めるためには (|(a − bm)N (a − bα)| の値が, 一様に x 以下の自然数を動くと仮定して) xN/ψ(x, B) 回 smoothness テストを繰り返せば良いと期待される. これから C の値を最適化することが出来るが, それには次の定理が有効である.
定理 2 ([17]). 任意の y ≥ 2 で定義された関数 g(y) = y 1+o(1) (y が十分大きいとき
o(1) は 0 に近づく) に対して, x が十分大きいとき√
xg(y)≥ Lx [1/2, 2]
ψ(x, y)8

√が成立する. さらに, この式で等号が成立するための必要十分条件は, y = Lx [1/2, 1/ 2]のときである.
この定理を用いると, N = B 1+o(1) であれば, C 2 ≥ xN/ψ(x, B) は必要であるから√
C 2 ≥ Lx [1/2, 2].
(8)
これから d, B, C の値を最適化すると [27]C = Lp [1/3, (8/9)1/3 ], d = ((3 + o(1)) log p 1/3) , B = Lp [1/3, (8/9)1/3 ].
log log p(9)

従って, smoothness テストにかかる計算量は C 2 = Lp [1/3, (64/9)1/3 ], 行列の計
算は B 2+o(1) = Lp [1/3, (64/9)1/3 ] となり, 最終的な計算量は Lp [1/3, (64/9)1/3 ] で与
えられる.

2.5

有限素体上の離散対数問題の数値実験

ここでは, 有限素体上の離散対数問題の数値実験について述べる. 有限素体上の離散対数問題の数値実験は, 素因数分解の数値実験ほど注目されておらず数も多くはないが, いくつかの数値実験が報告されている. 主なものは, 1998 年に Weber 等
は [29], 129 桁の特殊な形の素数740 · 7149 − 737
3
位数の有限素体上の離散対数問題を, 本稿で説明した Schirokauer のアルゴリズムを実装して解いたものである. p が特殊な形なので SNFS を用いている. これは, この p を標数とする有限素体上の Diffie-Hellman 鍵交換方式を解くという McCurleyによるチャレンジ問題 [20] の解でもある. 同じ年に, Joux 等 は, 90 桁 [11], 1999
年には 100 桁 [12], 2001 年には 110 桁と 120 桁 [14] のサイズの有限素体上の離散対数問題に対する離散対数問題に対する数値実験を行い成功している. さらに, 2005
年にも彼等 [16] は, 130 桁のサイズの有限素体上の離散対数問題を解いている. 同様に GNFS の数値実験である. 実装には [15] の改良などを用いている. 130 桁は,2006 年 12 月現在でのチャンピオンレコードである.
形が特殊ではない素数を標数とする有限素体上の離散対数問題の年代ごとの桁数の記録を, 以下の表１に, 素因数分解と並べてまとめておく. 但し, 離散対数問題の方には, GNFS ではなく Gaussian Integer Method と呼ばれる手法を使ったものも含まれており（以下の表では, * を記している）, 素因数分解の方には MPQS（複数多項式２次ふるい）と呼ばれるものの記録も含まれる（以下の表では, + を記している） [13]. ：
p=

9

年

1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
1900
2001
2002
2003
2004
2005

DLP

IFP
116+

58*
120+
129+
65
85*

130

90
100

155

120
158
174
130

200

表１

2.6

公開鍵暗号への安全な鍵サイズ

ここでは, 有限素体上の離散対数問題の困難性に安全性の根拠をおく公開鍵暗号の安全性を考える場合の鍵サイズについて考察する. すでに述べたように, 有限素体上の離散対数問題を解く場合に, 漸近的に最も高速なアルゴリズムは NFS であり, ここでは, NFS を用いた攻撃に対する安全性についてのみ考えることにする.
素因数分解アルゴリズムに対する NFS と有限素体上の離散対数問題に対する NFS
は, そのサイズ（素因数分解の場合は合成数全体のサイズ, 有限体上の離散対数問
題の場合は有限体のサイズ）の準指数時間アルゴリズムとしてオーダは同じである. 現在までの有限素体上の離散対数問題の数値実験例が素因数分解のそれと比べてあまり多くないため, 単純な比較は難しいが, 少なくとも素因数分解問題が困難になるサイズを取っておくことは必要である. 漸近的な計算量評価に関しては, 上
述のように素因数分解も離散対数問題の場合もオーダは同じであり, さらなる数値
実験によって具体的な差が出ることは期待出来なくはないが, 実用的な観点からの改良 [15] などを考慮しても, 計算量的にはほぼ同じであると考えてよいと思われる. 公開鍵暗号に関する安全な鍵サイズの予測に関しては, [1] 及び [19] 等が代表
的である.

10

3

有限体上の楕円曲線上の離散対数問題

本節では, 有限体上の楕円曲線の有理点のなす有限アーベル群上の離散対数問題の困難性について述べる. 有限体 Fq 上定義された楕円曲線 E とは

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6という形の非特異３次曲線の事である. 但し, 各 ai ∈ Fq である.
このとき, よく知られているように E の Fq 有理点の全体のなす集合 E(Fq ) には, 無限遠点を単位元とする群構造を定義する事が出来, 有限アーベル群となる. 群
演算は, 点を表す成分の有理関数で表すことが出来, 効率的に計算できる.
たとえば, 有限体 Fq の標数が奇素数で, 5 以上の場合, 定義方程式は

y 2 = x3 + a4 x + a6で与えられ, その上の 2 つの点 P = (x1 , y1 ), Q = (x2 , y2 )（P 6= −Q = (x2 , −y2 )）に対してその “和”P + Q = (x3 , y3 ) は次で計算できる：

x3 = λ 2 − x1 − x2 ,y3 = λ(x1 − x2 ) − y2
但し, λ = (y2 − y1 )/(x2 − x1 )（P 6= Q の場合）, = (3x21 + a4 )/(2y1 )（P = Q の場合）
楕円曲線上の離散対数問題（ECDLP）とは, 有限体 Fq 上の楕円曲線 E とその上の２つの Fq 有理点 P, Q が与えられたとき, Q = mP なる自然数 m が存在すれば, それを求める問題である. 有限体上の離散対数問題と同様に, 点 P の位数を lとすれば, m は mod l で一意に定まる.
ECDLP への解法アルゴリズム研究は, 1990 年代に入って盛んになり, 特殊な曲線に対しては準指数時間となるものや（確率的）多項式時間で動くアルゴリズムも提案されている. 提案されている. 典型的な例は 超特異と呼ばれる曲線に対するア
ルゴリズムでこれは, 定義体の拡大体の乗法群に効率よく埋め込む写像が Weil 対や Tate 対と呼ばれる関数を用いて定義出来る事を用いている. 一般には, ランダ
ムな曲線を選んだ場合は, その埋め込む際の拡大次数が入力サイズに対して指数的となるため, 有効でないことが知られている. また, 有限素体上定義され定義体を
同じ位数を持つ楕円曲線に対しては楕円曲線上の Fermat 商, もしくは “対数微分商” を効率よく計算する事により離散対数問題を（確率的）多項式時間で解くアルゴリズムが存在することが知られている. 素体ではない有限体（単に拡大体と呼ぶことにする）上定義された ECDLP で, その拡大体の素体からの拡大次数が合成数11の場合に有効となる Weil descent なる手法も提案されているが, いずれも効果的に適用できるのは特殊な曲線に限られる. 他にも, ECDLP に対して, 有限体上の曲線を代数体上の曲線に “持ち上げ” て, 指数計算法が直接適用出来るかどうかの研究などもあるが, 現在のところ直接的に適用することは難しいと考えられている. [9].
一方, 最近, Huang と Raskind によって, “Signature Calculas” [10] と呼ばれる, 有限体上の離散対数問題や ECDLP を統一的に扱おうという非常に興味深い研究も現れてきているが, 現段階では, 実用的ではなく, 純粋に理論的なものである. 代数曲線を用いた公開鍵暗号全般に関するサーベイとして [7] を挙げておく.
一般的な曲線を選んだ場合は, Pollard による Rho 法と呼ばれるものが最も有効である. ここでは, 一般的な ECDLP に対して, その計算量的困難さを, Rho 法を用いた場合に述べる.
本節の構成は次の通りである. まず 3.1 節で, Pollard の Rho 法やいくつかの
ECDLP へのアルゴリズムについて説明する. 最後に 3.2 節では, 現在までに行われている ECDLP の数値実験について述べる. 最後に, 安全な鍵サイズについて簡
単に考察する.

3.1

Pollard の Rho 法

ここでは, 簡単に Pollard の Rho 法について解説する. Rho 法は, ECDLP に限らず, 一般の有限アベール群上の離散対数問題に対して適用できるアルゴリズムである.
以下, 一般的な状況で述べる. G を位数 l の有限巡回群とし, 問題を g, h ∈ G が与えられたとき, h = g m なる m を求める問題としておく. 群 G における演算は乗法的に記すことにする.
まず, G を, ３つの部分集合にランダムに分割しておく: それぞれ, S1 , S2 , S3 とおく. 次に, x0 = h とおく. このとき, G 自身の上への写像 f を次で定め G 内の要
素の列 {xk } を xk+1 = f (xk ) で定義する：
 gx x ∈ S1
f (x) =
hx x ∈ S2
 x2 x ∈ S
3
このとき, xk = xj と衝突が起きれば xk = g bk m+ck などと書けるので bk m + ck ≡bj m + cj (mod l) となり, m ≡ (ck − cj )/(bk − bj ) (mod l) が得られる.
√f が理想的にランダム写像とすると, この衝突が起きるのに必要な計算量は O( l)である事が知られている. Rho 法は, 並列処理も可能であるので n 台のマシーンで√行った場合は n 倍高速となる.

12また, 最近, Miller と Venkatessan によって Rho 法の詳しい計算量評価も与えられている [21]3.2

楕円離散対数問題の数値実験

ECDLP の数値実験については, カナダの Ceticom 社による 1997 年に始まった
ECC challenge が有名であるので, ここでは 2006 年 12 月現在の ECC challenge のチャンピオンレコードについて簡単に述べる.
問題は大きく２つに分類されている（Koblitz 曲線と呼ばれるものも含まれているので, それも含めると３つ）, 定義体の標数が 2 の場合は奇素数の場合である. それぞれの問題（曲線と言っても良いが）ECC2-**, ECC2K-** や ECCp-** などと記される. 但し, ** にはビットサイズが入る.
2006 年 12 月現在の ECC challenge のチャンピオンレコードはどちらも 109 ビッ
トで, つまり, ECC2-109, ECCp-109 である.
ECCp-109 は, 2002 年 11 月に解かれたもので, 約 10000 人のメンバーが参加し,549 日かけて解いた.
ECC2-109 は, 2004 年 4 月に解かれたもので, 並列化された Rho 法を用いている. 2002 年の開始以来, 2000 人近いメンバーが参加し 17ヶ月かかっている.
以下の表２に, 現在までの ECC challenge の結果を抜き出しておく. 詳しくはCeticom の web ページを参照されたい. [5]
年

ECC2

1997
1998
1999
2000
2001
2002
2003
2004

79
97

ECC2K

ECCp

95

79
97

108
109
109
表２

3.3

公開鍵暗号への安全な鍵サイズ

ECDLP については, 一般的な楕円曲線を用いる限りは, Rho 法が最も有効で,サ√
π2k
イズはほぼ半分となるが, いわゆる総当り攻撃しかない. 計算量は 2 （ECDLP
13

のビット長が k ）に比例すると評価されるので, ECDLP の定義に現れる群位数 lのサイズが 160 ビット程度あれば, 現時点では, 十分安全であると考えられる. ちなみに, Lenstra 等による見積もり [19] では解法アルゴリズムの進歩がある場合には, 160 ビットのサイズの ECDLP が安全なのは, 2010 年頃までで, ない場合には2020 年頃までとなっている.

参考文献[1] R. Brent, “Recent Progress and prospects for integer factorisations algorithms,” Proc. of COCOON, LNCS1858, pp.3–22, Springer-Verlag, 2000.
[2] J. Brillhart, M. Filaseta and A. Odlyzko, “On an irreducibility theorem on A.
Cohn,” Can. J. Math., vol.33, no.5, pp.1055–1059, 1981.
[3] E. Bach and J. Shallit, “Factoring with cyclotimic polynomials,” Math. Comp.,
vol.52, no.185, pp.201–219, 1989.
[4] J.H. Buchmann and V. Shoup, “Constructing nonresidues in finite fields andthe extended Riemann hypothesis,” Math. Comp., vol.65, pp.1311–1326, 1996.
[5] http://www.certicom.com[6] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138,
Springer-Verlag, 1995.
[7] S. Galbraith and A. Menezes, “Algebraic Curves and Cryptography,” Finite
Fields and Their Applications, 11, pp.533-544, 2006.
[8] D. Gordon, “Discrete logarithms using the number field sieve,” SIAM J. Discrete Math., vol.6, pp.124–138, 1993.
[9] M.-D. A. Huang, K.L. Kueh and K.-S. Tan, “Lifting elliptic curves and solving the elliptic discrete logarithm problem,” Proc. of ANTS2000, LNCS1838,
Springer-Verlag, 2000.
[10] M-D. A. Huang and W. Raskind, “Signature Calculus and Discrete Logarithm Problems,” Proc. of ANTS2006, LNCS4076, pp.558–572, SpringerVerlag, 2006.

14

[11] A. Joux and R. Lercier, “Discrete logarithms indigits,”May 1998,
NMBRTHRY Maling List,
http://www.medics.polytechnique.fr/˜lercier.

GF (p) –Available90at[12] A. Joux and R. Lercier, “Discrete logarithms in GF (p) – 100 digits,” Nov.
1999, Available at http://www.medics.polytechnique.fr/˜lercier.
[13] R. Lercier, “State-of-the art in implementing algorithms for the (ordinary)
discrete logarithm problem,” slide from the talk at ECC99, Available at
http://www.cacr.math.uwaterloo.ca/conferences/1999/ecc99/slides.html[14] A. Joux and R. Lercier, “Discrete logarithms in GF (p) – 120
digits,” Apr. 17 2001, NMBRTHRY Maling List, Available at
http://www.medics.polytechnique.fr/˜lercier.
[15] A. Joux and R. Lercier, “Improvement to the general number field sieve for thediscrete logarithms in prime finite fields,” Math. Comp. 72, 242, pp.953–967,
2003[16] A. Joux and R. Lercier, “Discrete logarithms in GF (p) – 130
digits,” June 18 2005, NMBRTHRY Maling List, Available at
http://www.medics.polytechnique.fr/˜lercier.
[17] A.K. Lenstra and H.W. Lenstra, Jr., The Development of the Number Field
Sieve, LNM 1554, Springer-Verlag, 1993.
[18] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard, “The Number Field Sieve,” Proc. of STOC90, pp.564–572, 1990.
[19] A.K. Lenstra and E. Verheul, “Selecting cryptographic key sizes,” Proc.
PKC2000, LNCS1751, pp.446–465, Springer-Verlag, 2000.
[20] K. McCurley, “The discrete logarithm problem,” in Cryptology and Computational Number Theory, Proc. of Sympos. Appl. Math., vol.42, AMS, pp.49–74,
1990.
[21] S.D. Miller and R. Venkatessan, “Spectral Analysis of Pollard Rho Collision,”
Proc. of ANTS2006, LNCS4076, pp.573–581, 2006.
[22] A.M. Odlyzko, “Discrete logarithms: the past and the future,” Des. Codes
Crypt., vol.19, pp.129–145, 2000.
15

[23] J. Pollard, Factoring with cubic integers, pp.4–10, in [17].
[24] J. Pollard, The lattice sieve, pp.43–49, in [17].
[25] C. Pomernace, “The Quadratic Sieve Factoring Algorithm,” Proc. of Eurocrypt’84, LNCS 209, Springer-Verlag, pp.169–182, 1984.
[26] O. Schirokauer, “Discrete logarithms and local units,” Theory and applicationsof numbers without large prime factors (R.C. Vaughan, ed.), Philos. Trans.
Roy. Soc. London Ser. A, vol.345, Royal Society, London, pp.409–424, 1993.
[27] O. Schirokauer, “Using number fields to compute logarithms in finite fields,”
Math. Comp., vol.69, pp.1267–1283, 2000.
[28] O. Schirokauer, D. Weber and T. Denny, “Discrete logarithms – the effectiveness of the index calculus method,” Proc. of ANTS-II, LNCS 1122, SpringerVerlag, pp.337–361, 1996.
[29] D. Weber and T. Denny, “The solution of McCurley’s discrete log challenge,”
Proc. of Crypto’98, LNCS 1462, Springer-Verlag, pp.458–471, 1998.
[30] D.H. Wiedemann, “Solving sparse linear equations over finite fields,” IEEE
Trans. Inform. Theory, vol.32, pp.54–62, 1986.

16