プロジェクト報告書 Project Report

提出日（Date) 2020/1/22

FUN-ECM プロジェクト
FUN-ECM Project
A グループ(A) Search Group (A)1017217 下地健介 Kensuke Shimoji
1

背景

まずメンバー全員で楕円曲線法について基礎学

情報化が進んだ現代では,暗号化の技術が重要習を行い，その後前項で述べた本プロジェクトのである. 暗号化の技術の一つに RSA 暗号がある．

2 つの目標に沿って活動を行うために，次の 2 つ

本プロジェクトでは RSA 暗号技術の安全性を検の班に分かれた．

証し,その RSA 暗号解読方法の一つである楕円曲・PARI/GP によって素因数分解プログラムを作線法(ECM : Elliptic Curve Method)について学ぶ.

成するプログラム班

RSA 暗号とは約 40 年前に考案された公開鍵暗・Web サイトを作成する Web 班号であり, 現在でも広く利用されている. RSA 暗前期は楕円曲線法について学び理解を深めた. 後号は 2 つの素数を掛け合わせて作られた長大桁合期ではこの 2 班体制に分かれてそれぞれ活動を行成数の素因数分解が困難であることを根拠に安全った.

性が保障されている暗号である．楕円曲線法は，また，作成したプログラムの性能確認のために，与えられた曲線の点の演算結果より合成数の因数

STUDIO KAMADA[1]という Web サイトで公開である素数を見つけることができる方法である．

されているチャレンジ合成数を対象に素因数分解

これを利用し, 長大桁数合成数を素因数分解するを行った．これに成功すると，STUDIO KAMADAことで RSA 暗号を解読することができるが，ただ上に本プロジェクトの名前が記載される．

行うだけでは非常に長い時間と大きな計算量を要する．

以下に各班の課題を述べる．
プログラム班

前年度までのプロジェクト活動で，楕円曲線法

前年度までに C 言語によって作成された素因数によって素因数分解を行うプログラム funecm が分解プログラム funecm と同様の動作をするプ完成していた．そこで，今年度のプロジェクト活ログラムを，計算機代数アプリケーションであ動では funecm を高速化すること，または別のプる PARI/GP でプログラムを作成することで高ログラムを作成することによって，前年度までに速化を図ろうとし，PARI/GP の学習，及び C と作成されたプログラム以上の速度で素因数分解をPARI/GP の速度比較を課題とした．

行うことを目標とした．また, 去年度に作成されWeb 班

た Web サイトには正しくページが表示されない,Web サイトを更新するにあたり，従来の Web サ

特定のページから特定のページに飛ぶことが出来イトの問題点を探した. その後， HTML, CSSないなど様々な問題点があった．そのため, Web サの学習を行い実際に新しい Web サイトの作成

イトを新しく作成し，また高校生向けに理解しやを行った. その中で, どのような説明が高校生

すい楕円曲線法の説明を載せることを目標とした.に理解してもらえるかを課題として作成した.

2

課題の設定と到達目標

3

課題解決のプロセスとその結果

プロジェクト報告書 Project Report
3.1基礎学習

まず楕円曲線法を理解するため基礎学習を行っ提出日（Date) 2020/1/22
れていくが , それよりも効率の良い Baby-step

Giant-step がある. そして Baby-step Giant-step のた．有限体，Euclid の互除法，拡張 Euclid の互除高速化として素数テーブルの利用がある.

法, 楕円曲線の定義，楕円曲線上での加算・逆元・

Baby-step Giant-step とは, B1 < s < B2 を満たすスカラー倍算，無限遠点, 2 倍算などについてメン

全ての素数 s1, s2, s3, …, sk に対して, s を変形してバー全員で学んだ．その後，メンバーの希望をも計算を行うことで高速化を図る手法である.とに班分けを行い課題解決に向けて活動を開始しStage2 は sP = O の際に成功する.この式を変形すた．

ることである確率で素因数分解を行うことができ

3.2

プログラム班る. Baby-step Giant-step の改良として素数テーブ

今年度では, PARI/GP を利用して ECM でのルを用いた. Baby-step Giant-step では x 座標の差素因数分解を行うプログラムを作成することで高を掛け合わせるが, この差が素数でなければ掛け速化, およびプログラム上でどのようにしてる必要はない. そのため, 素数かどうかを判断すECM を行っているのかを把握しやすくすることることが高速化につながる. PARI/GP の関数としを図った. 高速化に関しては, 通常の ECM より効ては isprime 関数があるが時間を要する. そのた率の良い方法を実装することでさらなる高速化をめ, 素数テーブルを実装した. 素数テーブルとは図った.

あらかじめメモリ上に小さい順に素数が用意されECM は Stage1, Stage2 の２つに大きく分けらたものである. メモリ上には連番で配置されておれる.

り, 配列としてアクセスすることで n 番目の素数Stage1 では, 合成数 N の因数 p を見つけることが取得できる.

について考えている. 合成数 N の桁数から, 因数きるため, 高速化につながる. 素数テーブルはあの大きさを予想して, パラメータ B1, B2 を決める.

らかじめ別のプログラムで作成し用いる. この手

本プロジェクトでは B1, B2 の値を ECMNET[2]か

法は多くのメモリを消費し, 素数テーブルを読みら引用した. ある楕円曲線上の射影座標で与えら込む時間が必要となるが,れた点 P =(Xp : Yp : Zp)に対してある手順によって部分が大幅に高速化される.

確率的に因数を見つけることができる. このまた, 作成したプログラムを用いて funecm と実Stage1 では P に対するスカラー倍は B1 の階乗よ

行時間を比較した. PARI/GP の実行環境は Coreりも 1 から B1 までの数すべての最小公倍数を入れi3-7100U 及び Xeon E5-2640 を用いた. 昨年度のた方が効率が良くなる. そのため, 1 から B1 まで

実 行 環 境 は Xeon E5-2640 を 用 い た . Core i3-の数すべての最小公倍数を求めるプログラムを作

7100U のスペックとしては, CPU2 コアである.

成した.

Xeon E5-2640 のスペックは, CPU12 コアである.

これにより, 一瞬で素数判定がでその後の素数判定のStage2 では, B1 から B2 までの素数 s の中に, 位

この時, B1 = 3000000, B2 = 300000000, 分解する数があるかを調べる. これは, Stage1 のみを利用

合成数は STUDIO KAMADA に載っている桁数していると, 素因数を見つけやすくするためには159 桁の合成数とした. そして, 200 回の合計試行

B1 を大きくし, 非常に大きい数 l に対して,スカラ時間から平均を取り, 昨年度のプログラムは一番ー倍 lP を計算する必要がある. そしてスカラー倍速い実行時間を平均として比較した. 比較した結の計算は, 非常に計算量が大きくなるため, Stage2果, Stage1 での実行時間は funecm と比べて約 1.14を利用する. 本来の Stage2 では B1 から B2 までの倍速くなった. また, Stage 1, Stage 2 合わせた速素数を Stage1 が終わった後の点のスカラー倍に入度比較も行った. PARI/GP の実行環境は Core i3-プロジェクト報告書 Project Report

提出日（Date) 2020/1/22

7100U 及び Xeon E5-2640 を用いた. 昨年度の実挙がった意見では, 高校生は楕円曲線法を調べる

行環境は Xeon E5-2640 を用いた.

ことがない, というものであった. そのため, 公

この時, B1 = 4572523, B2 = 457252300, 分解す

開鍵暗号方式や共通鍵暗号方式などの暗号の説明る合成数は STUDIO KAMADA に載っている合を丁寧にしてから, 楕円曲線法について説明する成数とした. そして, 100 回の合計試行時間から平こととなった. また, 数式をできるだけ使わず,均を取った. 括弧内には用いた CPU を示す. ここ

図を多く入れることを重視すべきだと考えた.

で, Core とは Core i3-7100U を指し, Xeon とはWeb 班のメンバーは HTML と CSS をほとんどXeon E5-2640 を指すこととする. Core i3 を用い触ったことがなかった. そのため, HTML と CSS

た PARI/GP のプログ ラムと , Xeon を 用 い たの参考書を用いて, 2 週間ほど学習した. 参考書は,funecm に着目する. Stage 1 では Core を用いた

HTML などのタグの説明とソースコード, 実行結

PARI/GP のプログラムの方が約 1.32 倍速くなっ果が並んで表示されており, その工程をすべて行た. Stage 2 では Core を用いた PARI/GP のプログ

うと一つの Web サイトが作成できる仕組みとなラムの方が遅くなったものの, 全体としては Coreっ て い た . は じ め に 大 ま か な Web サ イ ト をの PARI/GP のプログラムが約 1.15 倍速くなった.

HTML で作成した. その後, CSS を実際に使って次に, Xeon を用いた PARI/GP のプログラムと,コーディングした. 実際に Web サイトが作成する

同じく Xeon を用いた funecm に着目する. Stage 2ことができる点が魅力的であった. このことによでは PARI/GP のプログラムの方が約 1.14 倍速くって, 理解しやすく, 楽しみながら学習を進めるなった. しかし, 全体として比較すると funecm のことができた. また, よく分からないところやう方が約 1.4 倍速いという結果となった.

まくコンパイルできなかった時には, メンバー同士で作成したソースコードを見ながら学習を行っ3.3

Web 班

た. 学習はメンバーが揃って行っていたので助け

後期から, 楕円曲線法をより一般に知ってもら合い, 情報共有しながらスムーズに進めることがうために新しく Web サイトを作成することとなできた. Web サイトのレイアウトを決定する前に,った. はじめに, 去年度の Web サイトを参考にし,広報班のメンバーで様々な Web サイトを閲覧し,どのような Web サイトを作成するかをメンバーどのようなサイトが見やすいかを挙げた. そのよと話し合った. 去年度の Web サイトは, 老若男女

うなサイトはシンプルなデザインで, ページごと幅広い年代の方々が親しみやすく, 操作しやすいに色が統一されていた. また, 画面上部にヘッダWeb サイトを目指していた. また, 去年度の Webーや画面下部にフッターがあった. その後, 閲覧サイトの問題点は 2 つあった. 1 つ目は, デザインした Web サイトを参考にしながら, Web サイトのの問題である. Web サイトのページが中心からずレイアウトを作成した. 採用したレイアウトは,れている, タブレット端末でサイトを閲覧した際画面上部にヘッダーがあり, シンプルなデザイン

正しく表示されないなどがあった. 2 つ目は, 掲載なものである. このとき, ワイヤーフレームを作されている楕円曲線法の説明文が長くなり, 分か成し, 実際にページの移動や見出しの位置などをりづらくなっていた. それらの問題点を踏まえて確認した. ワイヤーフレームを作成する際には,今年の Web サイトは対象者である高校生が見やAdobe の XD というソフトを用いた. Adobe XD は,すく, 理解しやすい Web サイトを目指した.

ユーザ操作性をデザイン, プロトタイプ化し, ユ

次に, 高校生が理解しやすいような Web サイトーザの立場になってそのレイアウトを確認するこにはどのようなものが必要であるかを話し合った.とができるものである. FUN-ECM の Web サイト

プロジェクト報告書 Project Report

提出日（Date) 2020/1/22にはすでにロゴがあった. 去年のロゴは十分良い

HOME と暗号を, 谷山が楕円曲線法(ECM)とそものであったが, 今回の Web サイトはシンプルなの他である. 活動内容と Link は 2 人で作成した.

ものを目指していたので, 去年のロゴの良い点を担当するページを作り, 時々プレビューを確認し取り入れながら新しく制作した. 新しいロゴには,ながら進めていった. メンバーと話し合った結果,去年と引き続き代表的な楕円曲線と, 新たに有限HOME 以外のすべてのページで文字の大きさを体の記号を追加した. また, 全体の色を黒にした.

調整できる HTML として書くことに決めた. また,

このロゴは Web サイトの画面最上部に使用した.

画像の大きさがページによって異なることが分かった. また, 楕円曲線法と暗号の仕組みの図はす
べて Adobe Illustrator を用いて作った. 楕円曲線のグラフは Python で作成した.

図 1 作成したロゴ

最終成果発表会の一週間前に, 全体の微調整と最終確認を行うことが出来た.

ロゴを制作したのは Web 班の富樫である. AdobeIllustrator を用いて制作した. 今年の Web サイト
作成は Ameba Ownd という Web サイト無料作成

4

今後の課題
以下が来年度以降の課題として挙げられる．

サービスを用いた. Ameba Ownd を用いた理由と・Stage1 での素因数発見確率を調べることしては 3 つ挙げられる. 1 つ目は, 複数人で 1 つの・PARI/GP のさらなる高速化とサーバー上でのものを編集することができることである. 後でフ実装

ァイルをまとめる必要がなく, 他のメンバーが制・実際に高校生に Web サイトを見てもらいフィー作した部分を見ることができるため, 間違っていドバックをすることるところをお互いに直しながら作成することができる. 2 つ目は, 操作が簡単なことである. Ameba

参考文献

Ownd では用意されているデザインの中から 1 つ[1]STUDIO KAMADA．http://stdkmd.com/ ，(最選び, 編集していく. 画像, 地図やテキストなど

終アクセス 2019 年 7 月 22 日)を簡単に入れることができる. さらに, 細かいコ[2]ECMNET.

ーディングやメンバーがそれぞれコーディングすhttps://members.loria.fr/PZimmermann/ecmnet/

るわけではないので, ページのずれが起きない.

(最終アクセス 2019 年 7 月 22 日)

また, スマートフォンやタブレットにも対応しているため, 去年の問題点が解決する. 3 つ目は,HTML と CSS でのコーディングが可能であることである. Ameba Ownd ではテキストをそのまま打ち込めるが, 色や大きさなどを細かく指定するとき, 線を引いたり囲んだりしたいときに,HTML と CSS を用いることができる. Ameba
Ownd 内での HTML と CSS は通常のタグを使用することができる. 以上の点を踏まえて, Ameba
Ownd を利用することにした.
次に, 主に担当するカテゴリを決めた. 下地が