プロジェクト報告書 Project Report

提出日 (Date) 2018/1/19

FUN-ECM プロジェクト
FUN-ECM project
A グループ (A) Search Group (A)1015014 中島俊平 Shunpei Nakajima
1 背景

2 課題の設定と到達目標

暗号化技術は，情報の保護やコンピュータセキュリプログラムの性能を確認するために，ECMNET とティにおいて欠かせない技術である．ファイルの暗号化

STUDIO KAMADA に記載されている合成数などを用の他に，HTTPS や，無線 LAN における通信など多くいて計算を行った．ECMNET や STUDIO KAMADAの場面で暗号化技術が利用されている．しかし，暗号化に記載されている合成数の素因数分解が成功した場技術は常に進化する攻撃方法により解読の脅威に晒され合，当プロジェクトの名前が ECMNET や STUDIOている．様々な攻撃方法から安全な暗号アルゴリズムをKAMADA に記載される．合成数の素因数分解を行う

作成するためには，作成する側が暗号解読の方法を知るプログラムの性能を向上させるために，既存のプログラ必要がある．暗号の安全性評価には暗号解読の技術が利ムを改善し，単位時間ごとの計算速度を向上させる必要用されていて，暗号の強度は暗号解読に必要な情報量とがある．そのため，この目的を達成するために以下のこ計算量によって評価される．今回のプロジェクトでは，とを実施した．

その暗号解読アルゴリズムの１つである，楕円曲線法を学ぶ．
現在，有名な公開鍵暗号の１つに RSA 暗号がある．

RSA 暗号は，桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号である．RSA 暗号を解読する時は合成数の元となる 2 つの素因数を見つけ出す必要がある．楕円曲線法では，与えられた曲線の点が無限遠点になることによって，因数が発見される．
この性質を利用して RSA 暗号を解読する．

• 既存のプログラムのバグの修正• プログラムの無駄な処理の除去• 論文の読解• アルゴリズムの検討・理解• Stage2 においての新たなアルゴリズムの実装• プログラム内で扱う曲線の変更• プログラムの性能検証のための合成数の決定
前年度のプロジェクトでは前期で ECM についての学

楕円曲線法には Stage1 と Stage2 があり，Stage1 で習を行い，後期でアルゴリズムの提案・実装を行ってい素因数分解できなかった場合，Stage2 で素因数分解を試た．しかし，このような日程でプロジェクトを進行してみる．前年度までのプロジェクト活動によって Stage1

いくと以下のような問題が発生した．のプログラムは完成していた．一方 Stage2 については高速化されていないという問題点があった．そこで今年
度では，Stage2 をより高速化させることを課題とした．
また，ECMNET や STUDIO KAMADA という暗号解読した素因数の大きさを競うサイトがあり，Stage2 を実装することで ECMNET や STUDIO KAMADA でのランクインをすることを目標として掲げた．

• 実際にプログラムを実装する期間が少ない• 完成したプログラムを試行する期間が少ない• 巨大な合成数の分解を行いにくい

本プロジェクトでは，5 月上旬まで全員で楕円曲線法についての基礎学習を行った．5 月中旬以降，既存のプログラムを改善するためにグループ全員でアルゴリズムの理解と実装をするのは効率が悪いと判断し，プログラム班，理論班の 2 つのグループに班分けをした．以下にそれぞれの班の課題を述べる．
理論班
楕円曲線法について理解を深め，前期では，計算

Algorithm 1 Euclidean Algorithm
Require: a, b ∈ N, a, b ̸= 0, a ≥ bEnsure: gcd (a, b)
while b ̸= 0 doq ← a/br ← a mod ba←bb←r
end while

速度の向上のためのアルゴリズム，Stage2 での新たなアルゴリズム (Baby-step Giant-step) の検討，在すれば無数に存在する．この方程式を一次不定方理解に取り組んだ．後期では，モンゴメリー曲線を程式という．一次不定方程式の解を求めるには，拡用いた計算，ρ 法，高速フーリエ変換，素数ペアリ

張 Euclid の互除法が有効である．拡張 Euclid のングの検討，理解に取り組んだ．逐次，理解したア互除法は，自然数 a，b に関する一次不定方程式ルゴリズムをプログラム班に説明した．

ax + by = gcd(a，b) を満たす無数の整数 x，y を効プログラム班率よく求めることができるというものである．

前期では，既存のプログラムの内容を理解し，プロ有限体 Fp において除算 a ÷ b を計算する場合，グラムの動作内容の理解に取り組んだ．理論班から

p と b は互いに素なので，拡張 Euclid の互除法によ提示されたアルゴリズム (Baby-step Giant-step)

り不定方程式 px + by = 1 の解 (x0 , y0 ) を求めるこをもとに，既存のプログラムを基に実装を行った．とができる．このとき px0 + by0 = 1 となるので，後期では，モンゴメリー曲線，素数ペアリングの実有限体 Fp 上では by = 1，つまり b− 1 = y0 が成立

装を行った．

する．よって a ÷ b = a × b−1 = a × y0 と変形することで，除算を乗算に置き換えて計算できる．

3 課題解決のプロセスとその結果
3.1 基礎学習
まず，ECM の理解のために基礎学習を行い，以下のことを理解した．

楕円曲線の定義方程式a, b ∈ Fp に対して y 2 = x3 + ax + b で定義される曲線を有限体 Fp 上の楕円曲線という．
楕円曲線の加算と逆元(加 算) 楕 円 曲 線 上 の あ る 2 点 P, Q を 通 る 直
有限体
素数 p に対し，0 から p − 1 までの整数の集合

Fp = {0，1，…，p − 1} を有限体と言う．Fp では四則演算が可能であり，楕円曲線法ではこの範囲で考える．

Euclid の互除法
自然数 a，b(a ≥ b) に対して以下の操作を繰り返し行い，余りが 0 になるまで行うことによって a，bの最大公約数を求めるものである．
以後，a, b の最大公約数を gcd (a, b) と表記することとする.
拡張 Euclid の互除法
与えられた整数 a，b，c に対し，未知数 x，y に関する一次方程式 ax + by = c の整数解は，1 組存線 を と す る と, 楕 円 曲 線 と 直 線 ℓの 3 つ 目 の 交
点 R (= P × Q) の x 軸に関する対称点を R とす る ．こ れ で 得 ら れ た 点 R を R′ の 逆 元 と 呼 び，R = −R′ が成り立つ．また，R を P と Q を加算した点と定義し，R = P + Q が成り立つ．
無限遠点
楕円曲線上の点 P とその逆元 − P をとり，P +(−P ) を考える．そうすると，２点を通る直線と楕円曲線には P と − P の他には交点が存在しない．このような状態のときに，存在しない点を仮想的に考え，それを無限遠点と呼び，P + (−P ) = O が成り立つ．
楕円曲線の２倍算
楕円曲線上の点 P の接線を ℓとし，楕円曲線と直線 ℓの P 以外の交点を R′ とし，R′ の逆元を R とす算しておける)

る．この R は R = P + P = 2P であり，楕円曲線ここで逆元の関係にある点の x 座標は等しい. つまの 2 倍算と定義する．

り (av) × Q の x 座標を Gx ，−u × Q の x 座標を楕円曲線の scalar 倍算

Hx とすると楕円曲線の加算・２倍算を利用して，点 P と自然

Gx ≡ Hx

数 d に対して，点 P を d 回足す演算を定義できる

G x − Hx ≡ 0．この演算を楕円曲線の scalar 倍算という．

(mod p)(mod p)← Gx − Hx が p の倍数が成り立つ．

以上のことを基礎学習として学んだ．その後，理論班とこ れ ま で の 説 明 を ま と め る と ， G x − Hx ≡ 0プログラム班に分かれて活動を行った．以下にそれぞれ(mod p) となる s が存在するならば，(av) × P =の班の活動内容を示す．

−u × P となる s が存在する. すなわち，s × P = O

3.2 理論班となる s が存在するため，Stage2 が成功，素因数分理論班では主に以下の理論を検討し，プログラム班が解が完了となる.

実装できるよう準備を整えた．

ここで，全ての s について Gxk − Hxk を計算しす
べてを掛け合わせた数を d をすると，Gx − Hx ≡ 0• Baby-step Giant-step(mod p) となる s が存在すれば，d ≡ 0 (mod p)• 素数ペアリングとなる．したがって d と合成数 N の最大公約数• Montgomery 曲線を用いた ECMを求めることで素因数 p が判明する．Baby-step• Pollard’s ρ 法

Giant-step の手順は，以下のようになる．

• Brent のアルゴリズム

Step1 B1 < s < B2 を満たすすべての素数 s
このうち，特に速度向上に貢献した Baby-step Giant-について計算する.

step について説明する．

(1) 素数 s について v, u を求める
(2) (2) 式の左辺の x 座標 Gx , (2) 式の右

Baby-step Giant-step

辺の x 座標 Hx を求める

去年までのプログラムでは楕円曲線法の Stage2 の計算に，総当たり法を用いていた. この方法では，Step2 d = (Gx1 −Hx1 )(Gx2 −Hx2 ) . . . (Gxk −k 回の scalar 倍が必要となるため高速ではない. そHxk ) を計算する
Step3 d と合成数 N の最大公約数をとる．

こで今年は総当たり法に代わり Baby-step Giant-

Step4 最大公約数が 1,N 以外ならその数は求step を実装した. Baby-step Giant-step とは，B1 <めたい素因数であり，成功する.

s < B2 を満たす全ての素数 s1 , s2 , s3 , . . . , sk に対して，s を変形して計算を行うことで高速化を図る手法である.

3.3

プログラム班プログラム班では，昨年度の ECM プログラムに理論

Stage2 は s × P ≡ O のとき成功する．この式を変班から引き継いだ新たなアルゴリズムを実装した．ま形していく．まず s をた，プログラムの改善を行うなどプログラム全体の効率

s = av + u( aa)− <u<22(1)化を行った．主な活動内容を以下に示す．

• Baby-step Giant-step の実装と変形する．すると• 素数ペアリングの実装

s×Q≡O• Montgomery 曲線を用いた ECM の実装(av + u) × Q ≡ O(av) × Q = −u × Q(2)と言い換えられる．この式を満たすかを確認すればaaよい．(u × Q は − < u < であるから事前に計22• 素数テーブルの実装• VPS の導入
• ソースファイルのドキュメント作成• テスト用のスクリプトの作成

• ソースコードの階層化
このうち，素数テーブルの実装について説明する．
素数テーブルの実装

stage2.png

プログラム中の実行時間について調べたところ，

gmp nextprime 関数が時間を多く使っていることがわかった. gmp nextprime 関数は与えられた数の次の素数を返す関数である. この関数は内部で毎図 1 Stage2 の実行にかかった時間回計算を行っていたため，より効率良く素数を求めることができる素数テーブルを作成することとした．
素数テーブルとはあらかじめメモリ上に小さい順に素数を用意しておく手法である. メモリ上には配graf2.png列として素数が 2,3,5,7,11,13,... と配置されており，配列としてアクセスすることにより簡単に n 番目の素数を取得することができる．この手法により，毎回計算せず 1 回のメモリアクセスで次の素数を取得できるため，高速化につながる．

図 2 1 つの楕円曲線における実行時間

なお，この手法は多くのメモリを消費する. 前期では 43 億までの素数テーブルを作成したが，後期で246した．1 つめの合成数は 52×109+11である [1]．2は 2900 億までの素数テーブルを作成した. 43 億まつめの合成数は 76×109での素数テーブルはおよそ 1.6[GB] となり，2900

約 9 日，2 日プログラムを動かして素因数を発見

億の素数テーブルはおよそ 92[GB] となった.

した．

247−31である [2]．それぞれ具体的な実装としては素数テーブルの内容となるファイルを作成し，プログラムを実行した際にそのファイルをメモリ上に配置して利用する．素数テー4 今後の課題
今後の課題として，以下が挙げられる．

ブルを作成したことにより，最初に素数テーブルをメモリ上に読み込む時間は必要となるが，楕円曲線• Pollard’s ρ 法の実装を用いた演算の部分は大幅に高速化した．

• FFT の実装

3.4 活動結果
プログラムの計測結果
プログラム班がプログラムのテストを行った結果，
図 1,2 の結果が得られた．

• 長期間（数か月）プログラムを動作させる• 安定した実行環境の構築

参考文献

図 1,2 の結果から，昨年度のプログラムに比べて，[1] STUDIO KAMADA. http://stdkmd.com/nrr/

前期終了時のプログラムの Stage2 の計算速度は 6

c.cgi?q=57779_246,（最終アクセス 2018 年 1 月〜7 倍に向上した．また，後期終了時のプログラム

19 日）の Stage1 と Stage2 を合わせた計算速度は 80 倍向上した．

STUDIO KAMADA へのランクイン
STUDIO KAMADA に載っているまだ素因数が見つかっていなかった合成数 2 つの素因数分解に成功[2] STUDIO KAMADA. http://stdkmd.com/nrr/c.cgi?q=84441_247,（最終アクセス 2018 年 1 月19 日）