神奈川大学理学部情報科学科 2013 年度学士論文要旨 指導教員：松尾和人 Cheon アルゴリズムの実装に関する研究 2010 1 はじめに 情報技術の進歩やインターネットの普及により情報化 浅賀 優人 数とする。 楕円曲線上の離散対数問題は、楕円曲線離与えられた E 社会となっている今日では、電子マネーやネットショッ の有理点 G, G = αG1 ∈ E(Fp ) に対し、G = G1 + G1 + ピングなどを気軽に使えるようになり個人情報を入力す … + G1 (α個) を満足する α ∈ [0, r − 1] を求める問題で る機会が増えているたため、情報の機密性保持は重要な ある。 課題となっている。情報を守るためには暗号技術が必要 離散対数問題の困難性は楕円曲線暗号の安全性の根拠と であり、その中でも公開鍵暗号方式の一つである楕円曲 なっている。楕円曲線離散対数問題は解くことが難しい 線暗号が注目を集めている。楕円曲線暗号は楕円曲線上 問題として知られており、このような楕円曲線離散対数 の離散対数問題を用いた暗号であり、有限体上の暗号と 問題の難しさを利用した公開鍵暗号の総称を楕円曲線暗 同じ強度の暗号が小さい鍵サイズで実現可能である。そ 号と呼ぶ。 2.2 補助入力付き離散対数問題と weak Diffie-Hellman 問題 d を r − 1 を割る正整数とする。ｒを E(Fp ) の位数と の為、近年の小型化した電子機器にも適した暗号方式で ある。 楕円曲線暗号の一種にペアリング暗号がある。ペアリン グ暗号の登場により、従来実現できなかった ID ベース 暗号や ID ベース署名などが利用可能になった。ペアリ ング暗号には、weak Diffie-Hellman 問題の困難性を安全 性の根拠としているものが知られている。weak Diffie- Hellman 問題を一般化した問題に補助入力付き離散対数 問題がある。 補助入力付き離散対数問題を解くアルゴリズムに Cheon アルゴリズムがある。Cheon アルゴリズムとその改良に ついては多くの実装実験結果 [2] が知られている。Cheon アルゴリズムの効率は補助入力パラメータに依存する が、これら実験は、Cheon アルゴリズムが最も効率的に なるパラメータに対する実験であり、現実の用途ではこ のようなパラメータは利用されない。また、実際に利用さ れるプロトコルは、補助入力付き離散対数問題ではなく weak Diffie-Hellman 問題である。しかし、weak DiffieHellman 問題に対してより効率的な解法であると知られ る KKM アルゴリズム [3] は実装されていない。 する。楕円曲線 E 上の３つの元を G, G1 = αG, Gd = αd G ∈ E(Fp ) とする。 補助入力付き離散対数問題とは、上記の３つの元 G, G1 , Gd よりα ∈ Z/rZ を求める問題である。 また前節より離散対数問題を用いれば、G, G1 からα が 求められるので補助入力付き離散対数問題は、離散対数 問題が解ければ解くことができる。 weak Diffie-Hellman 問題とは、与えられてるいくつもの 点 (G, [α]G, [α2 ]G, ..., [αq ]G) から [1/α]G を求める問題 である。 また与えられた点には、G, [α]G, [αd ]G も含まれること から補助入力付き離散対数問題を用いれば α が求められ る。α が求められれば、α → 1/α → [1/α]G として weak Diffie-Hellman 問題を解くことができる。 3 Cheon アルゴリズムと KKM 法 本章では、Cheon アルゴリズム [1] と KKM 法 [3] につ そこで、Cheon アルゴリズムを実装し現実的なパラメー いて説明する。 3.1 Cheon アルゴリズムの概要 Cheon アルゴリズムは、補助入力つき離散対数問題を タ設定の下で効率を検討し、さらにその改良を検討する。 解くアルゴリズムである。 また KKM アルゴリズムを実装し、weak Diffie-Hellman ζ を巡回群（Z/rZ）∗ の生成元 とする。ζd = ζ d とする。 BsGs 法を用いて Gd = [ζdk1 ]G となる k1 を計算する。 次に、同様に BsGs 法により G1 = [ζ k1 +k2 (r−1)/d ]G と 問題に対する効率を議論する。実装と計算には、代数計 算システムの Magma を用いる。 2 準備 て述べる。 2.1 離散対数問題 E : y 2 = x3 + ax + b (a, b ∈ Fp , 4a3 + 27b2 ̸= 0) なる k2 を計算する。以上から α = ζ k1 +k2 (r−1)/d が得ら √ √ れる。計算量は O(log r（ (r − 1)/d + d）) である。 3.2 KKM 法の概要 Cheon アルゴリズムの BsGs 法を利用してる部分を改 √ 良する。c を小さな正整数とする。c 行、c r 列 のテーブ √ ルを利用し、テーブルから、β k2 ∈ Z/rZ, b = c r となる を有限体 Fp 上の楕円曲線とする。また r を E(Fp ) の位 ようなものを c 個見つける。そのｃ個を足せば解答が導 本章では本論文の研究対象である離散対数問題と補助 入力付き離散対数問題,weak Diffie-Hellman 問題につい 神奈川大学理学部情報科学科 2013 年度学士論文要旨 指導教員：松尾和人 け、c 個の足し算だけで結果が得られるようになる。計 √ √ 算量は O(（ (r − 1)/d + d）) である。 3.3 KKM 法の改良 KKM 法では、小さな正整数 ｃ を 4 に設定しており 設定方法を定義していない。さらにテーブルを作成する 際、1 度目の BsGs 法と 2 度目の BsGs 法の部分で同じ c の値を用いている。 本論文では、最適な c の値の設定を行う。 √ √ 1 度目 BsGs 法の部分では (c − 1) r/d + c c r の値が最 小になるようなｃをｃとする。 √ √ 2 度目 BsGs 法の部分では (c − 1) d + c c r の値が最小 になるようなｃをｃとする。 4 実装と実験 離散対数問題に対する BsGs 法と補助入力付き離散対 数問題に対する Cheon アルゴリズム、KKM 法、weak Diffie-Hellman 問題に対する KKM アルゴリズムの実装 を行った。 実験は補助入力付き離散対数問題に対して、BsGs 法、 Cheon アルゴリズム、KKM 法を用いた時のそれぞれの 速度を比較する実験を行った。 5 考察 補助入力付き離散対数問題を解く実験では、問題のパ ラメータによって計算速度に違いが見て取れた。 暗号に使用する場合は、その暗号が解けないよう（解け 使用マシンスペック：Linux processor :Intel(R) Core(TM) ずらい）ように工夫して問題を選択する必要がある。 具体的にはグラフでみるところの BsGs の直線と Cheon i7-3820 CPU @ 3.60GHz, MemTotal:65888208 kB 4.1 補助入力付き離散対数問題 実験方法 アルゴリズムの近似直線の交点以下のパラメータに設定 補助入力付き離散対数問題を設定し、問題に対して 3 すると Cheon アルゴリズムや KKM 法によって解ける 種類の解法を試しそれぞれ計算時間を計測する。 難易度が下がってしまう。 1 つ目は BsGs 法、2 つ目は Cheon アルゴリズム、3 つ 目は KKM 法で解く。 計算結果は、Cheon アルゴリズムと KKM 法で思ったよ ランダム素数 p を 40bit から 72bit まで 8bit ずつまで上 げ楕円曲線を作成し、d の値を素数の 1/8∼7/8 の bit 数 となるように設定し、それを 20 回づつ解いた。 4.1.1 結果 実行結果ををグラフに示す。 グラフは、横軸が d の bit 数を縦軸は計算時間 (秒) の底 2 の対数のグラフである。 り差が出なかった。 c を固定した KKM 法の実験では c を適切な値に設定し た KKM 法の方が速くなっているので c は適切な値を取 るべきである。 実験の中で計算速度が想定と一部逆転してしまってい るが、これは実験の試行回数の少なさが原因と計算機 Magma のテーブル参照の時間が遅い事が考えられる。 また、実験後 BsGs 法を一部改良することができたので、 そこを改良する事でより良い結果が出せと考えられる。 weak Diffie-Hellman problem に対する KKM アルゴリ ズムでは、後半部分を無視して計算できるため計算効率 はとても高いと判断できる。 参考文献 [1] Cheon J. H. , Security Analysis of strong Diffie-Hellman Problem , EUROCRYPT 2006, 1-11, 2006 [2] TetsuyaIzu MasahikoTakenaka MasayaYasuda,Experimental Analysis of Cheon’s Algorithm against Pairing-friendly Curves, IPSJ Jounal Vol.52 No.9 2652-2661, 2011-09-15 [3] Shunji Kozaki, Taketeru Kutsuma, Kazuto Matsuo ,“Remarks on Cheon’s Algorithms for Pairing-Related Problems, Pairing-based cryptography - Pairing 2007
© Copyright 2024 ExpyDoc
