Sutherlandの位数計算法の楕円曲線に対する適用

神奈川大学理学部情報科学科 2014 年度学士論文要旨
指導教員：松尾和人
Sutherland の位数計算法の楕円曲線に対する適用
磯田遼
1
はじめに
ウェブの閲覧やメールなど情報通信が発達した現在で
は，ウェブサイトの認証に用いる ID やパスワード，メー
ルなどの重要な情報がネットワーク上で受け渡しが行わ
れている．データに何の手も加えないままネットワーク
上で通信を行うと，第三者により通信の改ざんや盗聴な
どをされる恐れがある．これらの脅威に対応するために，
暗号技術が用いられる．暗号技術は通信内容を秘匿化し，
第三者にその内容を改ざん，盗聴などをさせないように
する方法であり，古代から様々な形で利用されてきた手
法である．暗号技術に，長らく秘密鍵暗号方式が利用さ
れてきたが，1970 年代に Diﬃe と Hellman により，公開
鍵暗号方式が提案された．この公開鍵暗号方式は，現在
の様々な通信に利用されている．公開鍵暗号方式の一方
式である楕円曲線暗号は，1980 年代に Miller と Koblitz
により独自に提案された公開鍵暗号方式のひとつである．
既に知られている暗号方式に RSA 暗号があるが，楕円曲
線暗号は RSA 暗号に比べて安全性が高く，鍵の長さを短
くできる利点がある．楕円曲線暗号では，代数曲線の 1 つ
である楕円曲線が使用される．楕円曲線暗号は，楕円曲
線上の離散対数問題の困難性がそのまま安全性の根拠と
なっている．近年では SSL や携帯電話のセキュリティな
どにこの暗号方式が利用されている．本研究では楕円曲
線暗号に使用する楕円曲線の位数計算を行う．楕円曲線
の位数計算とは，楕円曲線上の有理点の個数を求める計
算である．楕円曲線は，同じ有限体上でも曲線が異なれ
ば位数が異なる．位数が合成数となる場合，楕円曲線暗
号が簡単に解けてしまう可能性がある．そのため，この位
数計算を行うことにより，素数位数の安全な楕円曲線を
作成することが必要である．位数計算法はこれまでに様々
な方法が提案されているが，本研究では Sutherland[1] の
提案した超楕円曲線に対する位数計算を楕円曲線へ適用
する．この位数計算法の楕円曲線に対する実装は知られ
ていない．そこでこれを実装し，その効果を確認する．
2
楕円曲線暗号
本節では，楕円曲線と楕円曲線暗号について説明する．
2.1 楕円曲線
素数 p > 5 として，有限体 Fp 上の楕円曲線 E を以下
のように定義する．
E : Y 2 = X 3 + aX + b, a, b ∈ Fp , 4a3 + 27b2 ̸= 0
楕円曲線上の有理点は，y 2 = x3 + ax + b を満たす組
(x, y) である．x, y は共に Fp の要素である．また，(x, y)
で表現できない無限遠点 1 点を含む．有理点には加算が
定義される．楕円曲線の位数とは，曲線上の有理点の個
数である．また，曲線上の有理点を 1 つ選んだ時，その
点が作る巡回群の位数を元位数と呼ぶ．
2.2
楕円曲線上の離散対数問題
楕円曲線上の 2 点 P, Q に対し Q = dP としたとき，
d を求める問題を楕円曲線上の離散対数問題という．楕
円曲線暗号は，整数 d を秘密鍵とし点 Q を公開鍵とし
て使用する．楕円曲線暗号が注目されている理由は，こ
れまでの公開鍵暗号方式で利用されている離散対数問題
に比べて楕円曲線上の離散対数問題を解くことが難しい
からである．離散対数問題を効率的に解く方法である指
数計算法は，楕円曲線上の離散対数問題には適用できな
い．そのため，楕円曲線上の離散対数問題を解くのは難
しい．ほとんどの楕円曲線では指数関数時間の解読法し
か見つかっておらず，これが楕円曲線暗号の安全性の根
拠となっている．
2.3 安全な楕円曲線
楕円曲線暗号を解かれないようにするには，安全な楕
円曲線を使用する必要がある．位数が小さな楕円曲線の場
合，離散対数問題を解くのに時間がほとんどかからない．
位数が大きい場合でもそれが合成数の場合では，PohligHellman 法によって解かれてしまうが，素数位数の楕円
曲線には Pohlig-Hellman 法を適用できない．暗号で利
用するためには大きな素数位数の楕円曲線を設定する必
要があり，これを満足する楕円曲線を発見するため位数
計算を行う．素数 p は 160bit 以上に設定すれば安全性が
保たれることが知られている．
3
Sutherland の位数計算法
楕円曲線の位数計算とは，楕円曲線上の有理点の個数
を求める計算である．Sutherland の提案した位数計算法
では，楕円曲線の位数計算を行うために必要な λ(G) を
計算する．λ(G) は，楕円曲線上の任意の有理点の元位数
の最小公倍数である．λ(G) が求まれば，群の性質によ
り容易に位数 #E(Fp ) を計算出来る．この位数計算法は
#E(Fp ) の計算時間が λ(G) の計算時間に依存している．
ここで，λ(G) を計算する際に使用するパラメータを示
す．E(Fp ) を楕円曲線上の群，B を任意の整数，c を任
i i
意の自然数，l を B 以下の素数 lj の集合，q = {ljj |ljj ≤
∏
i +1
B, ljj > B}，e = qj ，N = 1 とする．Algorithm1
にしたがって，λ(G) の計算法の概略を示す．|β|,|δ|,|γ| は
各々の元位数を示す．計算して求めた N が λ(G) となる．
Step6, Step11 の |δ|,|γ| は l, q を用いて計算する．求めた
λ(G) から E(Fp ) の位数を求める．Step4 で |δ| が B 2 より
も大きい場合は，位数の計算が出来ないとして f alse を返
す．Step6, Step11 では，|δ|,|γ| が e の約数とならないと
きに f alse となる．この位数計算法では直接位数が素数と
なる楕円曲線は計算ができない．位数が素数となる楕円曲
神奈川大学理学部情報科学科 2014 年度学士論文要旨
線の場合，現実的な計算時間では計算できない．そこで，
求めた合成数の位数を利用して素数位数となる楕円曲線
を探す．#E(Fp ) = p + 1 − t と置いたとき，#Et (Fp ) =
p+1+t となる曲線 Et を簡単に求めることができる．この
ことから，#Et (Fp ) が素数となるような E を求めれば素
数位数の楕円曲線を発見することができる．Sutherland
の位数計算法の計算量を示す．Step4 の計算量は Baby
step Giant step 法を用いて O(B log B)，Step6, Step11 は
Sutherland[1] の提案した LinearOrder アルゴリズムを用
いて O(B)，それ以外の Step は O(1) となる．全体の計
算量は，O(B log B)+O(B)+O(B)=O(B log B) となる．
指導教員：松尾和人
B が 15bit 程度，p が 70bit のとき B が 14bit 程度となっ
1
1
1
た．B が p に対して p 3 , p 4 , p 5 となり，p が大きくなる
につれ B は小さくなっていくことが分かる．B が小さい
と λ(G) を求められる確率が低くなるが，曲線 1 本あた
りの計算時間は短くなるので計算効率は良くなる．
Algorithm 1 GroupExponent
Input: E(Fp ), B, e, l, q, c
Output: λ(G) or f alse
1: Choos α ∈ E(Fp ) randomly
2: γ = N × α
3: β = e × γ
4: N ′ = |β| if N ′ ≤ B 2 , or return f alse
5: δ = N ′ × γ
6: N ′′ = |δ| if N ′′ |e, or return f alse
7: N = N × N ′ × N ′′
8: for t = 1 to c do
9:
Choos α ∈ E(Fp ) randomly
10:
γ =N ×α
11:
N ′ = |γ| if N ′ |e, or goto Step1
12:
N = N × N′
13: return N
4
位数計算法の実装
Sutherland の位数計算法を実装した．本研究では実装
に Magma[4] を使用した．Magma は楕円曲線や超楕円
曲線なども扱うことができ有理点の加算や乱数などがあ
らかじめ定義されているので，本研究ではそれを利用し
た．本研究では λ(G) の計算だけでなく，位数 #E(Fp )
の計算も実装した．
5
図 1: λ(G) が得られた曲線 1 本あたりの平均計算時間
以下に素数 p を決め，最適な B で λ(G) の計算を行っ
たときの結果を示す．
表 1: 最適な B での計算結果
実験
実装した位数計算プログラムを使用して実際に λ(G)
の計算を行う．初めに楕円曲線の位数を計算する際に使
用するパラメータ B を決定する．この位数計算法の計
算量は B に依存している．B を大きく設定すると λ(G)
はほとんどの場合で求めることが出来るが，同時に計算
時間も膨大なものとなる．B を小さく設定すると計算時
間は速くなるが，λ(G) がほとんど求められない．そこ
で，λ(G) が効率よく求められるような最適な B を探す．
Magma 上で素数 p の bit を決め Fp 上で楕円曲線を定
義し位数計算を行う．実験は，Corei7-3820 3.60GHz で
行った．素数 p を一定の bit で固定し，B の bit を変化
させて実際に λ(G) の計算を行う．各 B に対して複数回
計算を行い，その結果と計算時間から最も計算効率が良
くなる B を求める．図 1 は，全体の計算時間を λ(G) が
求められた曲線の本数で割った値である．これにより，
λ(G) が求められた曲線 1 本あたりの平均計算時間が分
かる．縦は曲線 1 本あたりの平均計算時間，横は B を示
す．曲線 1 本あたりの平均計算時間が最も小さくなるの
は，p が 30bit のとき B が 9bit 程度，p が 60bit のとき
曲線 1 本あたりの
平均計算時間 [s]
p の bit 数
最適な B の bit 数
確率
30
60
70
9
15
14
0.214 0.002546
0.0754 0.344825
0.0126 0.252797
λ(G) が得られた曲
線 1 本あたりの平均
計算時間 [s]
0.011897196
4.573275862
20.06325397
λ(G) が求められる確率はそれほど高くはないが曲線 1
本あたりの平均計算時間はそれほどかからないので，複
数回計算を行えば λ(G) を求めることが出来る．
6
まとめ
Sutherland の提案した位数計算法を楕円曲線へ適用し
た．現状では素数位数の安全な楕円曲線を発見できてい
ない．160bit 以上の素数 p に対して最適な B を求め，安
全な楕円曲線を発見することが今後の課題である．
参考文献
[1] A. V. Sutherland, A generic approach to searching for
Jacobians, Math. Comp. Vol.78, 485-507, 2009.
[2] A. V. Sutherland, Order Computations in Generic
Groups, Thesis, MIT, 2007.
[3] 辻井, 笠原, 有田, 境, 只木, 趙, 松尾, 暗号理論と楕円曲線,
森北出版, 2011.
[4] The Magma computational algebra system,
http://magma.maths.usyd.edu.au/magma/

Download Report