【2017最終】Project No.11

FUN-ECMプロジェクト 白勢政明・由良文孝

FUN-ECMプロジェクト
中島俊平

福永慧

小澤貴也

落合航平

金子真澄

水上敬介

FUN-ECM Project
外山拓

Nakajima Shunpei

Fukunaga Kei

Ozawa Takaya

Ochiai Kouhei

Kaneko Masumi

Mizukami Keisuke

Toyama Taku

1. 概要

1.1 プロジェクト名について About project name
FUN-ECM FUN 、 こだて未来大学を、ECM Elliptic Curve Method(楕円曲線法)を意味しており、それらを繋げた が本プロジェクト名 由来である。
Why this project name is FUN-ECM is that FUN means Future University Hakodate and ECM
means Elliptic Curve Method that is a best algorithm for prime factorization.

1.2 背景 Background
約40年前に RSA暗号※1が登場し、安全な電子商取引が可能となった。RSA暗号 安全性 公開鍵 素因数分解 困難さ等価であると考えられるため, RSA暗号 普及以降、素因数分解実験 重要なテーマとなっている。本プロジェクトが素因数分解法 中でECMを対象とする理由 、最良法 １つであることや並列実装 しやすさ、近年普及している楕円曲線暗号（ECC）※２が関連しているためである。
※1 素因数分解が困難であれ あるほど安全である公開鍵暗号 一つ。
※2 楕円曲線上 離散対数問題 困難性を安全性 根拠とした公開鍵暗号一つ。ECMと楕円曲線暗号 アルゴリズム 類似している。
RSA encryption ※１ was developed at 40 years ago, and secure e-commerce has become possible. Prime factorization experiments have become an important
theme since the spread of RSA. Because the security of RSA cryptosystem is considered to be equivalent difficulty in prime factorization of public key”. We
have three reasons that prime factorization among ECM is selected. First, it is one of the best methods. Second, it is easy to implement in parallel. Third,elliptic curve cryptography (ECC) ※２ have become widespread relate in recent years.
※1 RSA is one of public key cryptographies. RSA is based on the hardness of prime factorizations.
※2 ECC is one of public key cryptographies. ECC is based on the hardness of elliptic curve discrete logarithm problems. Algorithm for ECM is similar to oneof ECC.

1.3 目的 The purpose
・ECMを利用した素因数分解 プログラム 作成
・素因数分解チャレンジECMNETにランクイン（※1）
・STUDIO ＫＡＭＡＤＡ（※2）にランクイン
・活動や結果を発信・報告するサイトを作成

・Making of program for prime factorization using ECM.
・Ranking in ECMNET, which is a factorization challenge
・ Ranking in STUDIO KAMADA.
・Making a website to report activities and results※１：ＥＣＭＮＥＴ 目的 、主にECMにより大きな合成数 因数を見つけることでCunningham projectに貢献すること。（詳細 QRコードを参照）
The purpose of ECMNET is to find large factors by ECM, mainly by contributing to the Cunningham project.

URL： https://members.loria.fr/PZimmermann/records/ecmnet.html※２：STUDIO KAMADA 目的 、ニアレプディジット(ゾロ目素因数分解表を作成する。（詳細 QRコードを参照）

ＥＣＭＮＥＴ自然数)関連 数

The purpose of STUDIO KAMADA is to create a prime factorization table of numbers related to near
replicates (natural number of Repdigit).

URL：http://stdkmd.com/nrr/#summary
STUDIO ＫＡＭＡＤＡ

1.4 今期活動成果
STUDIO KAMADAに載っているまだ素因数が見つかっていなかった合成数２つ 素因数分解に成功した。
詳細 、QRコードを参照。

2. 活動内容
2.1 年間スケジュール

前期活動内容5月
ログラム班
プログラム班

6月

7月

8月

後期活動内容9月

BSGSを実装
中間発表
報告書準備

基礎学習

理論班理論班夏季休業

BSGS理解10月

11月

Montgomery
曲線 実装

最終発表
準備計測
素数ペアリング
実装
FFT 理解

最終発表
準備

12月
最最終
終報報
告告【2017最終】Project No.11

FUN-ECMプロジェクト 白勢政明・由良文孝

FUN-ECMプロジェクト
中島俊平

福永慧

小澤貴也

落合航平

金子真澄

水上敬介

FUN-ECM Project
外山拓

Nakajima Shunpei

Fukunaga Kei

Ozawa Takaya

Ochiai Kouhei

Kaneko Masumi

Mizukami Keisuke

Toyama Taku

2.2 後期活動内容詳細
プログラム

計算時間を短縮させるために、様々なアルゴリズム実装を行った。他にも、シェルスクリプトやドキュメント作成した。

・ 素数テーブル
ECMで やや小さ目な素数 テーブル(例え ４3億以下 素数 テーブル)が必要となる。去年まで プログラムで 素数を求めるにC言語 ライブラリを使用していたが、それで 素数を求める に時間がかかってしまうため、予めテキストファイルに素数を用意して、素数が必要になった際 そ ファイルを読み込み、計算に用いる。

・新たなアルゴリズム

実装

プログラム 計算 速度を向上させるために、様々なアルゴリズムを実装した。アルゴリズム
Baby-Step Giant-Step、モンゴメリー曲線、素数ペアリングを使用した。

・シェルスクリプト

作成

プログラム 実行を効率良く行うために、スクリプトを作成した。 実行された結果をテキストに出力するようにしてあり、 指定した桁数 合成数を計算できるようにした。

3. ECMについて
3.1 基礎学習目的・ スカラー倍昨年度 プログラムを理解するために、メンバー全員が、基礎知識として楕円曲線を知る必要があった。

方法『楕円曲線暗号入門（2013年度）』（著 伊豆哲也）を用いて学習した。

学習内容
・ 𝒁/𝒏𝒁

世界で加算、減算、乗算、除算について

𝑍/𝑛𝑍 = {0,1,2, … , 𝑛 − 1}まで 整数 集合を考えると、加算・減算・乗算 普通に計算した結果 mod 𝑛をとる。
除算について、𝑎, 𝑏 ∈ 𝑍/𝑛𝑍に対して、𝑎 ÷ 𝑏 解
𝑎 = 𝑏𝑐 mod 𝑛となる𝑐である。𝑛が素数 場合、𝑏 ≠ 0なら 𝑎 ÷ 𝑏 計算が可能

・ 楕円曲線

プログラムの楕円曲線𝐸定義（方程式）、方程式E：𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏で定義される。

・ 楕円曲線𝑬上2点𝑷, 𝑸

加法・𝑃 + 𝑄 定義：𝑃, 𝑄を通る直線𝑙と楕円曲線 交点を𝑅とすると、
点𝑅と𝑥軸に関して対称な点𝑅’ こと。
・2𝑃 定義：直線𝑙を点𝑃における接線とする。さらに、こ 接線と楕円曲線 交点を𝑅とすると、点𝑅と𝑥軸に関して対称な点𝑅’こと。 𝑃 座標と𝑄 座標から𝑃 + 𝑄 座標や2𝑃 座標を計算する公式が存在する(加算公式と2倍算公式)。

3.2 ECM

計算

Stage1

流れ

点𝑃と自然数𝑛から、𝑛個 𝑃 和
𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃をスカラー倍という。
・ECM 支配的な演算 スカラー倍である。
本プロジェクトにとって、スカラー倍 高速化 重要である。
高速化 方法として、バイナリ法や射影座標 手法がある。

・射影座標
点(𝑥, 𝑦)を𝑧座標を追加して(𝑥, 𝑦, 𝑧)で表す座標を射影座標と言い、射影座標を用いるとスカラー倍が高速になる。

・ Stage1 と素因数分解したい合成数𝑁に対して、適切な大きさ 𝐵1 からkを求め、mod 𝑁上でスカラーkP を計算する。そして、 kP 𝑧座標と𝑁と 最大公約数が1でなけれ 𝑁 因数である。見つからなかったらStage2へ。
見つかる理由として、𝑃を𝑁 素因数 １つとすると、𝑚が#𝐸 mod 𝑝 倍数 時、𝑚𝑃 = 𝑂 (mod 𝑝)となり、𝑚𝑝 = 𝑥: 𝑦: 𝑧 mod 𝑁 に対して、𝑧 ≡0(mod 𝑝) となる。

・ Stage2 と𝐵1 < 𝑠 < 𝐵2 を満たす、すべて 素数𝑠1 , 𝑠2 , 𝑠3 ,…,𝑠𝑘 まで
Stage1で得られた点をQとして全て スカラー倍𝑠𝑖 𝑄を求め、 𝑠𝑖 𝑄𝑧座標とNと 最大公約数をとる。Stage2を高速に行う方法に
Baby-Step Giant-Step法がある。

流れStage2

𝑃 ∈ 𝐸 mod N に対して、
𝑄 = 𝑚𝑃 = (𝑥, 𝑦, 𝑧) 𝑚𝑜𝑑 𝑁を計算する

gcd(n,z) ≠ 1
終了・𝐸時

gcd(n,z) = 1 時
Q を返して、stage2へ

流れStage1で見つかったQをもとに、
Baby-Step Giant-Step法を使用（Baby-Step
Giant-Step法について 3.3.2を参照）

未発見 時、曲線を変えてStage1へ移行

発見した時、終了

【2017最終】Project No.11

FUN-ECMプロジェクト 白勢政明・由良文孝

FUN-ECMプロジェクト
中島俊平

福永慧

小澤貴也

落合航平

金子真澄

水上敬介

FUN-ECM Project
外山拓

Nakajima Shunpei

Fukunaga Kei

Ozawa Takaya

Ochiai Kouhei

Kaneko Masumi

Mizukami Keisuke

Toyama Taku

3.3 アルゴリズム
3.3.1 Montgomery曲線について
Montgomery曲線と 、𝐵𝑦 2 = 𝑥 3 + 𝐴𝑥 2 + 𝑥 という式から表される曲線である。メリットとして、𝑦座標を保存する必要がなくなるため、Weierstrass曲線と違って、𝑦座標を用いずに計算を出来るようになる。デメリットとして今まで使用した曲線と違って𝑃 − 𝑄 点を用意する必要がある。
Montgomery曲線 座標 計算ついて・２点同士 加算
点𝑃と𝑄を加算するために 以下 アルゴリズムに従って加算を行う。
点𝑃＝(𝑋𝑝: 𝑍𝑝),点𝑄＝(𝑋𝑞: 𝑍𝑞)とする。𝑃0 = 𝑋𝑝 − 𝑞: 𝑍𝑝 − 𝑞 = 𝑃 − 𝑄とする。
これらを用いて計算を行う。
Montgomery曲線

・ Montgomery ladderMontgomery ladder Montgomery曲線

スカラー倍を効率よく行うためアルゴリズムである。

3.3.2 Baby-Step Giant-Step法（以下,BSGS）について去年まで 、Stage2 部分で 効率 悪い総当り法が実装されていた。
そこで今年 、より速く計算できるBSGSを実装した。
BSGSと ？
𝐵1 < 𝑠 < 𝐵2 を満たす全て 素数を𝑠1 , 𝑠2 , 𝑠3 , …, 𝑠𝑘 ，Stage1 結果で得られた点𝑃として、𝑠を変形して計算を行うことで高速化を図る手法である。
Stage2 𝑠 ∗ 𝑄 = 𝑂 とき成功する。こ 式を変形していく。𝑠 = 210 ∗ 𝑣 + 𝑢 (−105 < 𝑢 < 105) とすると(210 ∗ 𝑣) ∗ 𝑃 = −𝑢 ∗ 𝑃 となる。
こ 式を満たせ よい で、楕円曲線 逆元 定義より、 mod 𝑝上で、右辺と左辺 𝑥座標が等しい。
(210 ∗ 𝑣) ∗ 𝑃 𝑥座標を𝐺𝑥、 − 𝑢 ∗ 𝑃 𝑥座標を𝐻𝑥とすると
𝐺𝑥 ≡ 𝐻𝑥 (mod 𝑝)となり、これ 𝐺𝑥 − 𝐻𝑥 ≡ 0 (mod 𝑝)を意味し、(𝐺𝑥 − 𝐻𝑥)が𝑝 倍数となる。ここで、全て 𝑠について(𝐺𝑥 − 𝐻𝑥)を計算し、すべてを掛け合わせた数を𝑑をすると、𝐺𝑥 − 𝐻𝑥 ≡ 0 (mod 𝑝)となる𝑠が存在すれ 、𝑑 ≡ 0(mod 𝑝)となる。
そ ため、𝑑と合成数𝑁 最大公約数を求めることで𝑝が判明する。
3.3.3 素数ペアリングについてBSGSをより高速化する手法として、素数ペアリングがある。
(210 ∗ 𝑣) ∗ 𝑃 = −𝑢 ∗ 𝑃 … ☆
☆式 計算をについて考える。
楕円曲線 逆元 定義より、−𝑢 ∗ 𝑃 と 𝑢 ∗ 𝑃 、𝑥軸に対して対称であり、𝑥座標 値が等しい。よって、 (𝐺𝑥 − 𝐻𝑥) 値 同じになる。
もし、210 ∗ 𝑣 + 𝑢, 210 ∗ 𝑣 – 𝑢 がともに素数だったとき、従来 計算手法だと、同じ計算を二重に行うことになり効率が悪い。
そこで、 210 ∗ 𝑣 + 𝑢 と 210 ∗ 𝑣 – 𝑢 がともに素数になるペアを計算し、𝑠がどちらか 時 み(𝐺𝑥 − 𝐻𝑥) を求める。
これにより、試行回数が減るため高速化することができる。
☆式 こ ようにも変形可能である。
もし、 𝑠 = 210 ∗ 𝑣 + 𝑢 素数だったが、210 ∗ 𝑣 – 𝑢 が素数でないためにペアリングできなかったときに、
𝑠 = 210 ∗ 𝑣 + 𝑢 = 210 ∗ (𝑣 – 1) + (210 + 𝑢) = 210 ∗ (𝑣 – 2) + (2 ∗ 210 + 𝑢) = 210 ∗ (𝑣 – 3) + (3 ∗ 210 + 𝑢) = …と考えることで、より深くペアを探すことができ、ペア 数が増え、試行回数がより減るため、BSGS 高速化が期待できる。
ただし、☆式 右辺が増える分、多く 事前計算が必要となるため、注意が必要になる。

4. 計測結果
1曲線で実行時間(s)

去年と今年 前期と後期に作成したそれぞれ プログラム
１つ 楕円曲線にかかる計算時間 平均を比較した。
１つ 楕円曲線にかかる計算 今年度に作成したプログラムが去年 プログラムより約８０倍速度が向上した。
今後 展望として、符号付き２進展開法を実装し、新たなアルゴリズムを実装して素因数を見つける速度を高めていきたい。
ECMNETにランクインすることを試みる。そ 為、少なくとも桁数128桁以上 合成数 素因数分解をする必要がある。
(2017/12/6 現在)

実行時間

100,000
前期

10,000

後期

1,000
去年

100
10
100202530354045505560657075808590(桁数)