1. No category

神奈川大学理学部情報科学科 2013 年度学士論文要旨
指導教員：松尾和人
楕円曲線暗号の Android 端末への実装
2010
はじめに
1
従来、公開鍵暗号では RSA 暗号が代表的な例として
あげられた。しかし、近年では RSA 暗号と同等以上の
田中 裕紀
ある。
2.3 実装
楕円曲線暗号の実行時間の多くは楕円曲線のなす群に
安全性を持ち、かつ高速に実行できる楕円曲線暗号が注
おけるスカラー倍算に費やされる [2]。
目されている。楕円曲線暗号とは、楕円曲線上の離散対
スカラー倍算は楕円加算及び楕円 2 倍算から構成され
数問題を解くことが困難ということを安全性の根拠にし
る。また、これらの楕円加算・楕円 2 倍算は素体および
ている暗号方式である。さらに、有限体上の離散対数問
拡大体上の体演算から構成されている。
題を利用する暗号方式の多くは楕円曲線上においても定
そこで本稿ではこれらの演算を作成し、スカラー倍算
義ができるため、ほかの暗号方式に対しても応用できる
をアプリケーションとして Android 端末へ組み込むこ
といった一面を持つ。
とを目標とする。また、実装するにあたり、アプリケー
また、技術の発展に伴い、Android をプラットフォー
ションを以下の端末に組み込む。 ムとするスマートフォンやタブレットなどの携帯端末が
3 有限体の演算
普及し、また、そのなかでも、優れた性能を持つ端末も
楕円曲線暗号では素体 F p が主に使用される。しかし、
多く存在している。さらに、Android 向けのアプリケー
近年、最適拡大体を用いた高速演算可能な暗号方式が提
ションが数多く公開されている。これは Android が第三
案された [3]。最適拡大体とは、素体 F p を既約多項式
者によるアプリケーションの開発・搭載が可能という特
f ( x ) = x m − ω によって拡大した体である。これらの体
徴によるものだと考えられる。アプリケーションの多く
による演算を使用することで楕円曲線暗号の高速計算を
はセキュリティの強化が必要であるため、暗号の実装が
実現させる。
3.1 パラメータの選定
重要となる。Android では暗号ライブラリが利用可能で
あるが端末の機種に依存してしまう。そこで、機種によ
初めに、素体 F p における p の値を設定する。鍵を
らずに動作するアプリケーションで利用するために機種
32bit とするので p は 32bit 以下のメルセンヌ素数であ
る p = 231 − 1 とする。メルセンヌ素数を用いることで
演算の高速計算が可能になることが知られている [6]。
に依存しない Java による実装が必要である。
本稿では公開鍵暗号として最も安全な楕円曲線暗号の
Android 端末への Java 実装を行い、アプリケーションに
よる楕円曲線暗号の利用を可能とさせる。楕円曲線暗号の
既約多項式 f ( x ) は x7 − 3 に設定する。これは拡大次
数 m が素数以外であると、攻撃される可能性があるため
実行時間の多くは楕円曲線上でのスカラー倍算に費やさ
m は素数にする必要があるからである。m = 5 の場合、
れる。そこで、楕円曲線上でのスカラー倍算を Android
鍵が 155bit となり十分な安全性が保てず、m = 11 とす
にアプリケーションとして組み込むことを目標とする。
ると鍵は 341bit になるが大きすぎるため高速計算には適
楕円曲線暗号とその実装
2
楕円曲線暗号とは楕円曲線上の離散対数問題が解くこ
していないからである。
3.2 素体上の演算
とが困難ということを安全性の根拠にした暗号方式であ
はじめに素体 F p 上での加算 c = a + b、減算 c = a − b、
る。有限体上の離散対数問題を安全性の根拠にしている
加法逆元 c = − a、乗算 c = ab、逆元 c = a−1 を作成した。
暗号方式の多くは楕円曲線上においても定義することが
3.2.1 加減算・加法逆元
素体 F p での加減算・加法逆元は
{
a+b
( a + b < p)
加算 c =
a + b − p ( a + b ≥ p)
{
a−b
( a − b ≥ 0)
減算 c =
a − b + p ( a − b < 0)
{
a
( a = 0)
加法逆元 c =
p − a ( a ̸ = 0)
できる。 2.1 楕円曲線
p を奇素数とし q を p のべきとしたとき、F を位数 q
の有限体とする。このとき、下式で定義される曲線 E を
Fq 上の楕円曲線という [1]。
E : y2 = x3 + ax + b ( a ∈ F p , b ∈ Fq , 4a3 + 27b2 ̸= 0)
2.2
楕円曲線暗号
楕円曲線暗号とは楕円曲線上の離散対数問題を解くこ
とが困難であることを安全性の根拠にした暗号方式で
として実装した。
神奈川大学理学部情報科学科 2013 年度学士論文要旨
3.2.2 逆元
素体 F p での逆元は c = a−1 は 2 進 GCD アルゴリズ
ム [4, Algorithm 10.49] を実装した。
3.2.3 乗算
素体 F p での乗算は c = ab
(mod p) は p をメルセン
ヌ素数としているため高速で計算できる [6] の方法で実
装した。
3.3 拡大体上の演算
次に拡大体における加算 h = a + b、減算 h = a − b、
加法逆元 h = − a、乗算 h = ab、逆元 h = a−1 を作成し
た。拡大体の演算は素体上の多項式の演算と既約多項式
f による剰余で構成される。
3.3.1 加減算・加法逆元
拡大体 Fq における加減算は下式で計算することがで
きる。
a = a6 z6 + a5 z5 + a4 z4 + a3 z3 + a2 z2 + a1 z + a0
b = b6 z6 + b5 z5 + b4 z4 + b3 z3 + b2 z2 + b1 z + b0
加減算 h = a ± b = Σ0≤i≤6 ( ai ± bi )zi
加法逆元 h = − a = Σ0≤i≤6 (− ai )zi
3.3.2 乗算
拡大体 Fq における乗算 h = ab を計算方法としてクラ
シカル乗算と Karatsuba 乗算の 2 通りがある。この 2 つ
の計算方法の優劣は端末の機種に依存してしまうため、
両方を作成し計算速度の比較を行った。比較結果から本
稿ではクラシカル乗算を用いる。
3.3.3 逆元
拡大体 Fq における逆元 h = a−1 は拡大体 Fq 上では a の
pi べき乗を高速で計算できることを利用して [4, pp.231235]、h = aq−2 として実装した。
4
楕円曲線上の演算
本稿では Affine 座標を用いた演算によって楕円曲線上
の演算を作成した。また、計算はすべて有限体での計算
となるので 3.2、3.3 によって作成した演算を使用する。
4.1 座標系の選定
楕円曲線上の演算には Affine 座標を用いた演算と Projective 座標を用いた演算の 2 つがある [4, pp. 280-281]。
拡大体における乗算と逆元の計算時間の比を測定した結
果、逆元はおよそ乗算の 5 倍となった。この結果よりそ
れぞれの計算量を比較すると表 1 となった。表 1 におい
て M は拡大体上の乗算 1 回の時間を表す。この結果よ
り本稿では Affine 座標を用いた演算方法で加算・2 倍算
を実装した。
表 1: 計算量の比較
加算 2 倍算
Affine
8M
9M
Projective 14M
12M
指導教員：松尾和人
4.2
スカラー倍算
楕円曲線上のスカラー倍算は
[k] P = P + P +・
・
・+ P( P を k 回加算する)
と表すことができる。[k ] P は k 回 P を足すことで結果を
得られるが、この方法では計算時間が多くかかってしま
うため高速計算には適していない。そこで、符号付きス
ライドウィンドウ法 [5, pp.71-73] を用いて作成した。
k = Σid=−01 k i 2 j , k i を満たす {(bi , ei )}id=−01 を求め、{(bi , ei )}id=−01
を用いて点 P のスカラー倍算を計算した。
4.3 計算時間の測定
位数が素数の楕円曲線を用いて計算時間の測定を行っ
た。測定方法は加算・2 倍算・スカラー倍算を各 10 回ず
つ測定しその平均値を求めた。
表 2: 測定結果
計算時間 (ms)
スカラー倍算 [k ] P
74.1
加算 P + Q
0.28
2 倍算 [2]P
0.31
スカラー倍算においても約 0.1s で計算することができ
た。これは暗号化をするときの時間と同等であるので約
0.1s で暗号化することが可能である。
5 まとめ
本稿では、Android 端末に Java によるスカラー倍
算の実装を行った。参考文献 [2] の最適拡大体を利用す
ることで楕円曲線暗号の高速計算に取り組んだ。
安全性を十分に保つため拡大体の拡大次数を 7 とし、
素体・拡大体の演算を作成した。拡大体の演算の結果よ
り Affine 座標を用いた演算により楕円曲線上の加算・2
倍算を作成した。スカラー倍算はスライドウィンドウ法
を用いることで高速計算を可能とした。
結果として、約 0.1s でスカラー倍算計算を可能にした。
また、鍵長を 217bit としているため安全性も十分に保っ
ている。
参考文献
[1] 伊豆哲也,“楕円曲線暗号入門”, 立教大学理学部数学科講
「計算機緒論 2」講義補助資料, 2006.8.
[2] 青木和麻呂,“楕円曲線暗号はどこまで速くなるか？”, 仙
台数論小研究集会，2000.
[3] D.V.Bailey and C.Paar, “Optimal Extension Fields for
Fast Arithmetic in Public-Key Algorithms”, Advances
in Cryptology - CRYPTO’98, LNCS 1462, pp.472-485.
Springer-Verlag, 1998.
[4] Henri Chohen, Gerhard Frey, Roberto Avanzi,
Christophe Doche, Tanja Lange, Kim Ngyuyen,
Frederik Vercauteren, “HANDBOOK OF ELLIPTIC AND HYPERELLEIPTIC CURVE CRYPTOGRAPHY”, Chapman & Hall/CRC, 2006.
[5] イアン・F・ブラケ, ガディエル・セロッシ, ナイジェル・P・
スマート, “楕円曲線暗号” , Pearson Education Japan,
pp.71-73, 2001.12.
[6] Masaki Gonda, Kazuto Matsuo, Kazumaro Aoki, Jinhui Chao, Shigeo Tsujii, “Improvements of Addition Algorithm on Genus Hyperelliptic Curves and
Their Implementation”, IEICE TRANS.E88-A, pp.9294 ,2005.