TOP > 国内特許検索 > 楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置 > 明細書

明細書 :楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4193176号 (P4193176)
公開番号 特開2005-148141 (P2005-148141A)
登録日 平成20年10月3日(2008.10.3)
発行日 平成20年12月10日(2008.12.10)
公開日 平成17年6月9日(2005.6.9)
発明の名称または考案の名称 楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置
国際特許分類 G09C   1/00        (2006.01)
FI G09C 1/00 650A
G09C 1/00 620Z
請求項の数または発明の数 8
全頁数 28
出願番号 特願2003-381344 (P2003-381344)
出願日 平成15年11月11日(2003.11.11)
審査請求日 平成17年8月8日(2005.8.8)
特許権者または実用新案権者 【識別番号】593165487
【氏名又は名称】学校法人金沢工業大学
発明者または考案者 【氏名】林 彬
個別代理人の代理人 【識別番号】100105924、【弁理士】、【氏名又は名称】森下 賢樹
審査官 【審査官】青木 重徳
参考文献・文献 特開平11-102158(JP,A)
特開2002-229446(JP,A)
V. Paliouras and T. Stouraitis,“NOVEL HIGH-RADIX RESIDUE NUMBER SYSTEM MULTIPLIERS AND ADDERS”,Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on,1999年 7月,Vol.1,p.451-454,URL,http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=777911
青木和麻呂,“楕円曲線暗号はどこまで速くなるか?-ソフトウェア実行の到達点”,仙台数論小研究集会2000(第4回),2001年 1月31日,p.1-15,URL,http://www.math.is.tohoku.ac.jp/~taya/sendaiNT/2000/aoki_m.pdf
安達大亮,蒲生真之,平田富夫,“直接計算による楕円曲線上のスカラ倍計算の効率化”,コンピュータセキュリティシンポジウム2003論文集,日本,社団法人情報処理学会,2003年10月29日,Vol.2003,No.15,p.151-156
Mathieu Ciet, Marc Joye, Kristin Lauter and Peter L. Montgomery,“Trading Inversions for Multiplications in Elliptic Curve Cryptography”,Cryptology ePrint Archive,2003年12月16日,p.1-19,URL,http://eprint.iacr.org/2003/257
林彬,“楕円曲線暗号の高速化の一手法”,2004年暗号と情報セキュリティシンポジウム(SCIS2004)予稿集CD-ROM,日本,2004年 1月27日,2B2計算手法・数理応用,2B2-1
調査した分野 G09C 1/00
特許請求の範囲 【請求項1】
楕円曲線上の任意の点Pの整数倍演算kPを行う楕円曲線整数倍演算装置であって、
整数kについて複数の基数sによるs進展開を求めるs進展開部と、
前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、
選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする楕円曲線整数倍演算装置。
【請求項2】
前記h進法演算部における前記h進法の演算に必要な前記点Pの(h-1)倍以下の整数倍点をあらかじめ計算する予備計算部と、
前記予備計算部により計算された前記(h-1)倍以下の整数倍点を記憶する記憶部とをさらに含み、
前記h進法演算部は、前記記憶部に記憶された前記(h-1)倍以下の整数倍点を加算の際に利用することを特徴とする請求項1に記載の楕円曲線整数倍演算装置。
【請求項3】
前記コスト評価部は、前記s進展開における非零桁の個数を用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項1または2に記載の楕円曲線整数倍演算装置。
【請求項4】
前記コスト評価部は、前記s進展開における非零桁の個数をs進桁数で除算した相対重みを用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項1または2に記載の楕円曲線整数倍演算装置。
【請求項5】
前記コスト評価部は、前記s進法における逆元算と乗算の計算コストの比の見積もり値を用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項3または4に記載の楕円曲線整数倍演算装置。
【請求項6】
楕円曲線上の基点Gとその位数nの入力を受け付ける入力部と、
0<d<nを満たす乱数dを生成する乱数生成部と、
前記基点Gのd倍点Qを算出する整数倍演算部と、
前記乱数dを秘密鍵、前記d倍点Qを公開鍵として生成する鍵生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、
整数kについて複数の基数sによるs進展開を求めるs進展開部と、
前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、
選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする鍵生成装置。
【請求項7】
楕円曲線上の基点Gとその位数n、公開鍵Q、および平文Mの入力を受け付ける入力部と、
0<r<nを満たす乱数rを生成する乱数生成部と、
前記基点Gのr倍点rGと、前記公開鍵Qのr倍点rQを算出する整数倍演算部と、
前記整数倍演算部による算出結果を用いて、第1暗号C1=rGと第2暗号C2=rQ+Mを計算し、暗号文(C1、C2)を生成する暗号文生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、
整数kについて複数の基数sによるs進展開を求めるs進展開部と、
前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、
選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする暗号化装置。
【請求項8】
楕円曲線上の基点Gとその位数n、公開鍵Q、および平文Mに対して、0<r<nを満たす乱数rを定めて、前記基点Gのr倍点rGと前記公開鍵Qのr倍点rQを算出し、その算出結果を用いて、第1暗号C1=rGと第2暗号C2=rQ+Mを計算することで生成された暗号文(C1、C2)と、秘密鍵dの入力を受け付ける入力部と、
前記第1暗号C1のd倍点dC1を算出する整数倍演算部と、
前記整数倍演算部による算出結果を用いて、前記第2暗号C2から前記第1暗号C1のd倍点dC1を減算することにより、復号された平文Mを生成する平文生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、
整数kについて複数の基数sによるs進展開を求めるs進展開部と、
前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、
選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする復号装置。
発明の詳細な説明 【技術分野】
【0001】
この発明は楕円曲線暗号技術に関し、特に楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置に関する。
【背景技術】
【0002】
公開鍵暗号の一方式として、楕円曲線暗号(あるいは楕円暗号)がある。楕円曲線暗号は1985年頃、KoblitzとMillerがほぼ同時期に独立に提案し、RSA暗号に代わる次世代の公開鍵暗号と目されている有望な暗号である。この楕円曲線暗号は同じ安全性規準で比較すると、RSA暗号に比して鍵の大きさは数分の一でよい、という特徴がある。しかしそれでも秘密鍵暗号に比べて計算に時間がかかり低速である、という問題点は解決されていない。そこで高速化の方法が種々の方面から検討されている。
【0003】
楕円曲線暗号は有限体上で定義された楕円曲線上の点の間に適当な加法を定義すると、これら点たちが群をなすことを利用する。楕円曲線の上に基準となる1点Pを定め、これをk倍した点をQ=kPとすると、Qを与えられても、これからkを求めることは計算量的に難しい。これを楕円曲線上の離散対数問題の困難性という。楕円曲線暗号はこの性質を利用する暗号であり、楕円曲線暗号を利用するには、点のk倍算が必要になる。従来のk倍算の方法は、2倍算と加算の組合せ(いわゆる“double-and-add”)による2進法である。この方法ではlogk回の2倍算と平均(1/2)logk回の加算が必要となる。これの改良法としてm進法がある。ただしmは2のべき2である。さらに加法と減法を併用する符号付き法、移動窓法などがある(たとえば、非特許文献1参照)。

【非特許文献1】イアン・F・ブラケ,ガディエル・セロッシ,ナイジェル・P・スマート著,鈴木治郎訳,「楕円曲線暗号」,初版,株式会社ピアソン・エデュケーション,2001年12月20日
【発明の開示】
【発明が解決しようとする課題】
【0004】
楕円曲線暗号は公開鍵暗号の現在の主流であるRSA暗号よりも鍵の大きさが小さくてもよいという利点があるが、暗号化と復号処理が遅いという欠点をもつ。一般に、公開鍵暗号では巨大数を使うので、有限体における演算にどうしても計算時間がかかり、処理が遅くなる。計算量の問題は、暗号システムを実用化する上で避けることができない深刻な課題であり、楕円曲線暗号の実用性をより一層高めるために、さらなる計算速度の向上が求められている。
【0005】
本発明はこうした状況に鑑みてなされたものであり、その目的は、楕円曲線暗号の高速化を実現することのできる楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置を提供することにある。
【課題を解決するための手段】
【0006】
本発明のある態様は楕円曲線整数倍演算装置に関する。この装置は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、整数kについて複数の基数sによるs進展開を求めるs進展開部と、前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含む。
【0007】
本発明の別の態様は鍵生成装置に関する。この装置は、楕円曲線上の基点Gとその位数nの入力を受け付ける入力部と、0<d<nを満たす乱数dを生成する乱数生成部と、前記基点Gのd倍点Qを算出する整数倍演算部と、前記乱数dを秘密鍵、前記d倍点Qを公開鍵として生成する鍵生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【0008】
本発明のさらに別の態様は暗号化装置に関する。この装置は、楕円曲線上の基点Gとその位数n、公開鍵Q、および平文Mの入力を受け付ける入力部と、0<r<nを満たす乱数rを生成する乱数生成部と、前記基点Gのr倍点rGと、前記公開鍵Qのr倍点rQを算出する整数倍演算部と、前記整数倍演算部による算出結果を用いて、第1暗号C1=rGと第2暗号C2=rQ+Mを計算し、暗号文(C1、C2)を生成する暗号文生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【0009】
本発明のさらに別の態様は復号装置に関する。この装置は、秘密鍵d、および楕円曲線による第1暗号C1と第2暗号C2を含む暗号文(C1、C2)の入力を受け付ける入力部と、前記第1暗号C1のd倍点dC1を算出する整数倍演算部と、前記整数倍演算部による算出結果を用いて、前記第2暗号C2から前記第1暗号C1のd倍点dC1を減算することにより、復号された平文Mを生成する平文生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【0010】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【0011】
本発明によれば、楕円曲線上の任意の点の整数倍演算を高速化することができる。
【発明を実施するための最良の形態】
【0012】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【0013】
[前提技術]
[1] 概要
本発明は、有限体上の楕円曲線の点群における演算の高速化に関するものである。本発明の実施の形態の基礎技術は、点の加算と2倍算を組み合わせた従来の2進法に対して、加算と3倍算を組み合わせた3進法、さらには、その一般化として加算とh倍算を組み合わせたh進法(h>2)を導入し、少なくとも2つのs進法(s≧2)を選択的に併用するものであり、計算量の削減を図り、それによって楕円曲線暗号の高速化を図る。
【0014】
[2] 楕円曲線
以下、N.コブリッツ著,林彬訳,「暗号の代数理論」(シュプリンガー・フェアラーク東京,1999年10月)の第6章の記載を適宜用いて説明する。
[2.1] 楕円曲線の方程式
体F上の楕円曲線Eは、次の形の方程式で与えられる曲線である。
+aXY+aY=X+a+aX+a, a∈F (1)
E(F)は、この方程式を満たす点(x,y)∈Fと、Oと表記する「無限遠点」の集合を表す。もしKがFの拡大体であるなら、E(K)は式(1)を満たす(x,y)∈KとOの集合を表す。曲線(1)が楕円曲線であるためには、滑らかでなければならない。これは両方の偏導関数がともに0になるようなE(F)の点がないことを意味する(FはFの代数的閉包を表す)。言い換えれば、2つの方程式
Y=3X+2aX+a, 2Y+aX+a=0 (2)
は、どの(x,y)∈E(F)によっても、同時に満たされることがない。
【0015】
集合E(F)は単位元がOであるアーベル群をなす。Fの任意の拡大体Kに対し、集合E(K)は単位元がOであるアーベル群をなす。
【0016】
楕円曲線暗号のために使われる楕円曲線は、有限体F(GF(q)と書かれることもある)の上で定義されるものである。そして楕円曲線の方程式は、Fの標数pの違いによって異なるので、以下、p=2,p=3,p>3のそれぞれの場合について別々に扱うことにする。
【0017】
[2.2] 標数p=2の場合
1.非超特異の場合
これは式(1)の左辺がY+aXYの場合で、一般性を失うことなくa=1としてよく、楕円曲線Eの方程式を次のように与えることができる。
+XY=X+a+a, a,a∈F. (3)
2.超特異の場合
これは楕円曲線Eの方程式を次のように与えることができる場合である。
+aY=X+aX+a, a,a,a∈F. (4)
【0018】
[2.3] 標数3の場合
標数3の体F上の楕円曲線Eの方程式を次のように与える。
=X+a+aX+a, a,a,a∈F. (5)
【0019】
[2.4] 標数p≠2,3の場合
体F上の楕円曲線Eは、Fの標数が2でも3でもないなら、一般性を失うことなく次の形の方程式によって与えられる。
=X+aX+b, a,b∈F,charF≠2,3. (6)
ただし、X+aX+bの判別式-(4a+27b)≠0である。
【0020】
[2.5] 加法則
集合E(F)は単位元がOであるアーベル群をなすことは前に述べた。この群における演算は次の加法則で与えられる。ここでは幾何的イメージが湧きやすいように、実数体R上の楕円曲線として話を進める。
【0021】
定義
Eを式(6)で与えられる実数体上の楕円曲線とし、PとQをE上の2点とする。Pの負および和P+Qを、次の規則に従って定義する。
1)もしPが無限遠点Oなら、-PをOと定義する。任意の点Qに対し、O+QをQと定義する。すなわち、Oは点の群の加法単位元(「零元」)としての役割を果たす。以下では、PもQも無限遠点でないと仮定する。
2)負-Pは、x座標がPと同じで、y座標が逆符号の点である。すなわち、-(x,y)=(x,-y)である。(x,y)が曲線上にあれば、(x,-y)も曲線上にあることは、式(6)から明らかである。もしQ=-Pなら、P+Qを無限遠点Oと定義する。
3)もしPとQが異なるx座標をもてば、直線l=PQ(2点P、Qを結ぶ直線)は、曲線とちょうどもう一つの点Rで交わる(もし直線lが曲線にPで接するなら、R=P、あるいはQで接するなら、R=Qととるが、そうでないとする)。このとき、P+Qを-R、すなわち第3の交点の(x軸に関する)鏡像と定義する。
4)最後の可能性はP=Qである。このとき直線lをPにおける曲線への接線とし、Rを直線lと曲線のただ一つの他の交点として、2P=-Rと定義する。(もし接線がPで「2重の接線」をもつなら、換言すれば、もしPが変曲点なら、RをPにとる。)
【0022】
上の規則の組は、次のように簡潔に要約できる。
直線が曲線と交わる3点の和は零である。
【0023】
もし直線が無限遠点Oを通るなら、この関係はP+P+O=Oの形をもつ(ここでPとPは対称な点である)、すなわち、P=-Pである。そうでないなら、P+Q+R=Oの形をもつ。ただし、P、QとRは規則3)あるいは4)の3点である。
【0024】
(x,y)、(x,y)、(x,y)でそれぞれP、Q、P+Qの座標を表す。xとyをx,y,x,yで表したい。上のP+Qの定義の規則3)と4)の場合、直線lの方程式をy=λx+νとする。
P≠Qの場合(加算公式)
=λ-(x+x
=λ(x-x)-y
λ=(y-y)/(x-x) (7)
P=Qの場合(2倍点公式)
λがPにおける導関数dy/dxの値である以外、P≠Qの場合と同様である。Pの2倍点の座標の式は次のとおりである。
=λ-2x
=λ(x-x)-y
λ=(3x+a)/(2y) (8)
【0025】
記法nPによって、もしnが正なら、Pをそれ自身n回加えることを、またもしnが負なら、-Pをそれ自身|n|回加えることを表す。
【0026】
[2.6] 加算の計算量
P+Q=(x,y)の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれM、Iで表す。なお平方算のコストをSで表すが、多くの場合平方算と乗算のコストはほぼ同等と考えることができるので、ここではS≒Mとした式も示す。
【0027】
P≠Qの場合
1.λ=(y-y)/(x-x)の計算:
(x-x-1の計算に逆元算のコストI。
これにy-yをかける計算に乗算のコストM。
2.x=λ-(x+x)の計算:
λの計算に平方算のコストS≒M。
3.y=λ(x-x)-yの計算:
λをx-xにかける計算に乗算のコストM。
以上の合計コストt=1I+2M+S≒1I+3M。なおtの添え字AはAddition(加算)のつもりである。
【0028】
P=Qの場合
1.λ=(3x+a)/(2y)の計算:
(2y-1の計算に逆元算のコストI。
の計算に平方算のコストS≒M。
これに(2y-1をかける計算に乗算のコストM。
2.x=λ-2xの計算:
λの計算に平方算のコストS≒M。
3.y=λ(x-x)-yの計算:
λをx-xにかける計算に乗算のコストM。
以上の合計コストt=1I+2M+2S≒1I+4M。なおtの添え字DはDoubling(2倍算)のつもりである。
【0029】
まとめ
以上をまとめると、FにおけるP+Qの計算コストは次のとおりである。ただしFの標数はp>3であり、また計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量t=1I+2M+S≒.1I+3M
2倍算の場合、計算量t=1I+2M+2S=t+1S≒t+1M
【0030】
[3] 3倍点公式
我々の方法は点の3倍算を使う。よって3倍点3P=(x,y)の座標をP=(x,y)の座標で表したい。
[3.1] 3倍点公式の導出
まず2倍点P=2P=2(x,y)=(x,y)を求める。
=λ-2x
=λ(x-x)-y
λ=(3x+a)/(2y) (9)
【0031】
次に3倍点を3P=P+Pとして求める。Pの3倍点3P=(x,y)の座標は次で与えられる。式(7)においてx,y,x,y,x,y,λをそれぞれx,y,x,y,x,y,μで置き換える。その上でさらに、xの式の右辺のxに式(9)の第1式を代入する。
=μ-(x+x
=μ-λ+x
=μ(x-x)-y
μ=(y-y)/(x-x) (10)
={λ(x-x)-y-y}/(λ-2x-x
={λ(x-λ+2x)-2y}/(λ-3x
=-λ-2y/(λ-3x) (11)
【0032】
3倍点公式:まとめ
=μ-λ+x
=μ(x-x)-y
λ=(3x+a)/(2y),μ=-λ-2y/(λ-3x) (12)
【0033】
[3.2] 2進法と3進法の適用例
[例:100P の計算]
100=1100100(2)=10201(3)
2進法の場合
1)2P+P=3P
0)2(3P)=6P
0)2(6P)=12P
1)2(12P)+P=25P
0)2(25P)=50P
0)2(50P)=100P
3進法の場合
0)3P
2)3(3P)+2P=11P
0)3(11P)=33P
1)3(33P)+P=100P
【0034】
[3.3] 3倍算の計算量
点Pの3倍算すなわち3Pを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれM、Iで表わす。なお平方算のコストをSで表すが、ここではS≒Mとする式も示す。
1.λ=(3x+a)/(2y)の計算:
(2y-1の計算に逆元算のコストI。
の計算に平方算のコストS≒M。
これに(2y-1をかける計算に乗算のコストM。
2.λの計算に平方算のコストS≒M。
3.μ=-λ-2y/(λ-3x)の計算:
(λ-3x-1の計算に逆元算のコストI。
これに2yをかける計算に乗算のコストMがかかる。
4.μの計算:
平方算のコストS≒M。
5.yの計算:
μをx-xにかける計算に乗算のコストM。
以上の合計コストt=2I+3M+3S≒2I+6M=2t。ここでtの添え字TはTripling(3倍算)のつもりである。なお2Pを求めてからPを加算して3Pを求めると、計算量はt’=t+t=2t+1S=t+1Mであることに注意する。したがって、3倍算公式の使用で計算量をMだけ節約できる。
【0035】
[4] k倍算の計算量:標数p>3の場合
2倍算公式を使うときと、3倍算公式を使うときの計算量を比較する。
【0036】
[4.1] 2進法とその計算量:標数p>3の場合
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
1.kを2進展開する。k=kl-1l-2…k0(2)。ただしl(エル)はkのビット数でkl-1=1である。
2.Q=Pとしてj=l-2,…,0に対して次を行う。
(2a)Q←2Q
(2b)k=1ならQ←Q+P
【0037】
2進法の計算量:
1.の2進展開のコストは無視する。
2.の(2a)は2倍算であるからその計算量はt=t+1Sである。
2.の(2b)は一般の加算であるからその計算量はt=1I+2M+1Sである。
【0038】
ところで2倍算はl-1回、加算はw-1回行うから、2進法によるkPの計算量tは次のとおりである。ただしwはkの2進展開におけるハミング重み(すなわち非零桁の個数)である。
=(l-1)t+(w-1)t
=(l-1)(t+1S)+(w-1)t
=(l+w-2)t+(l-1)S
=(l+w-2)I+(2l+2w-4)M+(2l+w-3)S
≒(l+w-2)I+(4l+3w-7)M (13)
lはkのビット数だけで決まるがwはw=1からw=lまであり得る。ゆえに
(l-1)(t+S)≦t≦(l-1)(2t+S) (14)
+S≦t/(l-1)≦2t+S (15)
である。また平均としてw=l/2とし、l≫1とすれば
=(l/2)(3t+2S) (16)
さらにt=1I+2M+S、S≒Mとすれば
=(l/2)(3I+11M) (17)
ここで典型的にI=3Mならt=10lM、I=11Mならt=22lMとなる。
【0039】
[4.2] 3進法とその計算量:標数p>3の場合
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
0.P=2Pを予め計算し記憶する。
1.kを3進展開する。k=hi-1i-2…h0(3)。ただしiはkの3進桁数でhi-1>0である。
2.hi-1=1ならQ←P、hi-1=2ならQ←Pとしてj=i-2,…,0に対して次を行う。
(2a)Q←3Q
(2b)h=1ならQ←Q+P
(2c)h=2ならQ←Q+P
【0040】
3進法の計算量:
0.P=2Pの予備計算のコストは無視する。
1.の3進展開のコストは無視する。
2.の(2a)は3倍算であるからその計算量はt=2I+3M+3S≒2tである。
2.の(2b)、(2c)は一般の加算であるからその計算量はt=1I+2M+1Sである。
【0041】
ところで3倍算はi-1回、加算はw-1回行うから、3進法によるkPの計算量tは次のとおりである。ただしwはkの3進展開におけるハミング重み(すなわち非零桁の個数)である。
=(i-1)t+(w-1)t
=(i-1)(2I+3M+3S)+(w-1)(1I+2M+1S)
=(2i+w-3)I+(3i+2w-5)M+(3i+w-4)S
≒(2i+w-3)(1I+3M)≒(2i+w-3)t (18)
iはkの3進桁数だけで決まるがwはw=1からw=iまであり得る。ゆえにt≒(2i+w-3)tの近似を使えば、
2(i-1)t≦t≦3(i-1)t (19)
2t≦t3/(i-1)≦3t (20)
である。また平均としてw=2i/3とし、i≫1とすれば
=(8i/3)t (21)
さらにt=1I+2M+S、S≒Mとすれば
=(8i/3)(1I+3M) (22)
ここで典型的にI=3Mならt=16iM,I=11Mならt=(112i/3)Mとなる。
【0042】
[5] 2進法と3進法の選択による高速化
これまでに2進法と3進法によるk倍算の計算量tとtを見積もった。両者のどちらが小さいかはkを展開したときの重みw、wすなわち非零桁数に依存する。したがってkが与えられるとき、まずこれを2進法と3進法とで展開し、tとtの大小関係によって2進法と3進法のいずれかを選択することで高速化を図ることができると考えられる。
【0043】
[5.1] 2進法と3進法の計算量の比較
平均値の比較
平均値tとtの比t=t/tは式(22)、(17)により次のとおりである。
=t/t=16i(1I+3M)/{3l(3I+11M)}
=16i(d+3)/{3l(3d+11)} (23)
ただしd=I/Mは逆元算と乗算の計算時間の比である。そこでt<1となるd=I/Mの条件を求めよう。c=l/i=log3=1.585を使うと
d=I/M<(33c-48)/(16-9c)=2.480 (24)
である。すなわちI<2.480Mのとき、t<tとなる。
【0044】
一般の場合の比較
とtの比t=t/tは式(13)、(18)により次のとおりである。ただしw’=w/l、w’=w/iは相対重みである。
t=t/t
=(2i+w-3)(d+3)/{(l+w-2)d+4l+3w-7}
={(2+w’-3c/l)(d+3)/c}/{(1+w’-2/l)d+4+3w’-7/l} (25)
通常lは十分大きいから上の式で1/lの項を省略すると
t={(2+w’)(d+3)/c}/{(1+w’)d+4+3w’} (26)
式(26)でt<1となるw’、w’、dに関する条件を求めれば、t<tとなる数kを求めることができる。ただしdは予め決まっている数である。式(26)の近似を用いれば、
’<cw’-{(2-c)d+6-4c}/(d+3) (27)
となる。
【0045】
ここでは典型的なdの値に対して、上の条件を求める。
d=3の場合:
t<1となるためには
’<cw’+(7/6)c-2=1.585w’-0.1509 (28)
でなければならない。ただし0<w’,w’≦1を考慮すると、t<1となる条件は
条件Ter
0.0952<w’<0.7261 (29)
かつ式(28)が成り立つ。 (30)
【0046】
d=11の場合:
t<1となるためには
’<cw’+(15/14)c-2=1.585w’-0.3018 (31)
でなければならない。0<w’,w’≦1を考慮すると、t<1となる条件は
条件Ter
0.190<w’<0.8213 (32)
かつ式(31)が成り立つ。 (33)
【0047】
[5.2] 提案法-選択的2進・3進法
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
1.kを2進および3進展開する。それぞれにおける桁数lとi、重みwとw、また相対重みw’とw’を求める。
2.(2a)条件Terが成立するなら3進法による計算を行う。
(2b)条件Terが成立しないなら2進法による計算を行う。
【0048】
[5.3] 2進法と3進法の計算量の例
[例1:100Pの計算]
100=1100100(2)=10201(3)
2進法の場合
2倍算Dと加算Aの列はDADDDADDとなるから、
=2t+6t=2(1,2,1)+6(1,2,2)=(8,16,14)となる。ただし、コストを(I,M,S)で表記している。
3進法の場合
3倍算Tと加算Aの列はTTATTAとなるから、
=2t+4t=2(1,2,1)+4(2,3,3)=(10,16,14)となる。
この例では3進法のほうが逆元算2回だけ多い。
【0049】
[例2:90Pの計算]
90=1011010(2)=10100(3)
2進法の場合
2倍算Dと加算Aの列はDDADADDADとなるから、
=3t+6t=3(1,2,1)+6(1,2,2)=(9,18,15)となる。
3進法の場合
3倍算Tと加算Aの列はTTATTとなるから、
=2t+4t=(1,2,1)+3(2,3,3)=(7,11,10)となる。
この例では平方算を乗算とみなすと、3進法のほうが逆元算2回と乗算が12回だけ少ない。計算量の削減率をδ=(t-t)/tで表すと、d=I/M=3のときδ=30%、d=I/M=11のときδ=25%となる。
【0050】
[6] 楕円曲線:標数3の場合
標数3の体F上の楕円曲線Eの方程式を次のように与える。
=X+a+aX+a, a,a,a∈F. (34)
【0051】
[6.1] 加法公式:標数3の場合
前と同じく(x,y)、(x,y)、(x,y)でそれぞれP、Q、P+Qの座標を表す。xとyをx,y,x,yで表したい。
P≠Qの場合(加算公式)
=λ-a-(x+x
=λ(x-x)-y
λ=(y-y)/(x-x) (35)
【0052】
P=Qの場合(2倍点公式)
λがPにおける導関数dy/dxの値である以外、P≠Qの場合と同様である。Pの2倍点の座標の式は次のとおりである。
=λ-a-2x=λ-a+x
=λ(x-x)-y
λ=(3x+2a+a)/(2y)=(a-a)/y (36)
なお2倍点の座標であることを明示するために、この場合の(x,y)を(x,y)と表すこともある。
【0053】
3倍点公式
P=(x,y)、2P=(x,y)、3P=(x,y)として、3倍点3P=(x,y)=(x,y)+(x,y)を求める。3Pの座標は次で与えられる。
=μ-λ+x
=μ(x-x)-y
λ=(a-a)/y, μ=-λ+y/(λ-a) (37)
【0054】
[6.2] 加算の計算量:標数3の場合
P+Q=(x,y)の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれS、M、Iで表す。
P≠Qの場合
1.λ=(y-y)/(x-x)の計算:
(x-x-1の計算に逆元算のコストI。
これにy-yをかける計算に乗算のコストM。
2.x=λ-a-(x+x)の計算:
λの計算に平方算のコストS.
3.y=λ(x-x)-yの計算:
λをx-xにかける計算に乗算のコストM。
以上の合計コストt=1I+2M+1S。なおtの添え字AはAddition(加算)のつもりである。
【0055】
P=Qの場合
1.λ=(a-a)/yの計算:
-1の計算に逆元算のコストI。
-aの計算に乗算のコストM。
これにy-1 をかける計算に乗算のコストM。
2.x=λ-a+xの計算:
λの計算に平方算のコストS。
3.y=λ(x-x)-yの計算:
λをx-xにかける計算に乗算のコストM。
以上の合計コストt=1I+3M+1S。なおtの添え字DはDoubling(2倍算)のつもりである。
【0056】
まとめ
以上をまとめると、標数3の有限体FにおけるP+Qの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量t=1I+2M+1S
2倍算の場合、計算量t=1I+3M+1S=t+1M
M≒Sの場合には、標数>3の場合と同じ計算量となることに注意する。
【0057】
[6.3] 3倍算の計算量
点Pの3倍算すなわち3Pを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれM、Iで表わす。なお平方算のコストをSで表すが、ここではS≒Mとする。
1.λ=(a-a)/yの計算:
前出の通りコストは1I+2M。
2.μ=-λ+y1/(λ-a)の計算:
λの計算に平方算のコストS。
(λ-a-1の計算に逆元算のコストI。
これにy=1をかける計算に乗算のコストM。
3.xの計算:
μの計算に平方算のコストS。
4.yの計算:
μをx-xにかける計算に乗算のコストM。
以上の合計コストt=2I+4M+2S=2t。M≒Sの場合には、標数>3の場合と同じ計算量となることに注意する。なお2Pを求めてからPを加算して3Pを求めると、計算量はt’=t+t=2t+M=t+Mであり、この関係は標数>3の場合と同じであることに注意する。
【0058】
[7] k倍算の計算量:標数3の場合
2倍算公式を使うときと、3倍算公式を使うときの計算量を比較する。
【0059】
[7.1] 2進法とその計算量:標数3の場合
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
1.kを2進展開する。k=kl-1l-2…k0(2)。ただしlはkのビット数でkl-1=1である。
2.Q=0としてj=l-1,…,0に対して次を行う。
(2a)Q←2Q
(2b)k=1ならQ←Q+P
【0060】
2進法の計算量:
1.の2進展開のコストは無視する。
2.の(2a)は2倍算であるからその計算量はt=t+1Sである。
2.の(2b)は一般の加算であるからその計算量はt=1I+2M+1Sである。
【0061】
ところで2倍算はl-1回、加算はw-1回行うから、2進法によるkPの計算量tは次のとおりである。
=(l-1)t+(w-1)t
=(l-1)(t+1M)+(w-1)t
=(l+w-2)t+(l-1)S
=(l+w-2)I+(3l+2w-5)M+(l+w-2)S
≒(l+w-2)I+(4l+3w-7)M (38)
lはkのビット数だけで決まるがwはw=1からw=lまであり得る。ゆえに
(l-1)(t+M)≦t≦(l-1)(2t+M) (39)
+M≦t/(l-1)≦2t+M (40)
である。また平均としてw=l/2とし、l≫1とすれば
=(l/2)(3t+2M) (41)
さらにt=1I+2M+S、S≒Mとすれば
=(l/2)(3I+11M) (42)
ここで典型的にI=3Mならt=10lM、I=11Mならt=22lMとなる。
【0062】
[7.2] 3進法とその計算量:標数3の場合
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
0.P=2Pを予め計算し記憶する。
1.kを3進展開する。k=hi-1i-2…h0(3)。ただしiはkの3進桁数でhi-1>0である。
2.Q=0としてj=i-1,…,0に対して次を行う。
(2a)Q←3Q
(2b)i=1ならQ←Q+P
(2c)i=2ならQ←Q+P
【0063】
3進法の計算量:
0.のP=2Pの予備計算のコストは無視する。
1.の3進展開のコストは無視する。
2.の(2a)は3倍算であるからその計算量はt=2I+4M+2S=2tである。
2.の(2b)、(2c)は一般の加算であるからその計算量はt=1I+2M+1Sである。
【0064】
ところで3倍算はi-1回、加算はw-1回行うから、3進法によるkPの計算量tは次のとおりである。
=(i-1)t+(w-1)t
=(i-1)2t+(w-1)t=(2i+w-3)t
=(2i+ w-3)(1I+2M+1S) (43)
iはkの3進桁数だけで決まるがwはw=1からw=iまであり得る。
2(i-1)t≦t≦3(i-1)t (44)
2tA≦t/(i-1)≦3t (45)
である。また平均としてw=2i/3とし、i≫1とすれば
=(8i/3)t (46)
さらにt=1I+2M+S、S≒Mとすれば
=(8i/3)(1I+3M) (47)
ここで典型的にI=3Mならt=16iM、I=11Mならt=(112i/3)Mとなる。
【0065】
[7.3] 2進法と3進法の選択による高速化
これまでに2進法と3進法によるk倍算の計算量tとtを見積もった。両者のどちらが小さいかはkを展開したときの重みw、wすなわち非零桁数に依存する。したがってkが与えられるとき、まずこれを2進法と3進法とで展開し、tとtの大小関係によって2進法と3進法のいずれかを選択することで高速化を図ることができると考えられる。
【0066】
[7.4] 2進法と3進法の計算量の比較
平均値の比較(結果は標数3の場合と同じ)
平均値tとtの比t=t/tは式(42)、(47)により次のとおりである。
=t/t=16i(1I+3M)/{3l(3I+11M)}
=16i(d+3)/{3l(3d+11)} (48)
ゆえにt<1となるd=I/Mの条件を求め、c=l/i=log3=1.585を使うと
d=I/M<(33c-48)/(16-9c)=2.480 (49)
である。すなわちI<2.480Mのとき、t<tとなる。
【0067】
一般の場合の比較(結果は標数3の場合と同じ)
とtの比t=t/tは式(38)、(43)により次のとおりである。ただしw’=w/l、w’=w/iは相対重みである。
t=t/t
=(2i+w-3)(d+3)/{(l+w-2)d+4l+3w-7}
={(2+w’-3c/l)(d+3)/c}/{(1+w’-2/l)d+4+3w’-7/l} (50)
通常lは十分大きいから上の式で1/lの項を省略すると
t={(2+w’)(d+3)/c}/{(1+w’)d+4+3w’} (51)
式(51)でt<1となるw’、w’、dに関する条件を求めれば、t<tとなる数kを求めることができる。ただしdは予め決まっている数である。式(51)の近似を用いれば、
’<cw’-{(2-c)d+6-4c}/(d+3) (52)
となる。
【0068】
ここでは典型的なdの値に対して、上の条件を求める。
d=3の場合:
t<1となるためには
’<cw’+(7/6)c-2=1.585w’-0.1509 (53)
でなければならない。ただし0<w’,w’≦1を考慮すると、t<1となる条件は
条件Ter
0.0952<w’<0.7261 (54)
かつ式(53)が成り立つ。 (55)
【0069】
d=11の場合:
t<1となるためには
’<cw’+(15/14)c-2=1.585w’-0.3018 (56)
でなければならない。0<w’,w’≦1を考慮すると、t<1となる条件は
0.190<w’<0.8213 (57)
かつ式(56)が成り立つ。 (58)
【0070】
[7.5] 提案法-選択的2進・3進法
入力:点Pと整数k
出力:点Q=kP
アルゴリズム:
1.kを2進および3進展開する。それぞれにおける桁数lとi、重みwとw、また相対重みw’とw’を求める。
2.(2a)条件Terが成立するなら3進法による計算を行う。
(2b)条件Terが成立しないなら2進法による計算を行う。
【0071】
[8] 楕円曲線:標数2で非超特異の場合
標数2の体F上の非超特異な楕円曲線Eの方程式を次のように与える。
+XY=X+a+a, a,a∈F. (59)
【0072】
[8.1] 非超特異の場合:加法公式
前と同じく(x,y)、(x,y)、(x,y)でそれぞれP、Q、P+Qの座標を表す。xとyをx,y,x,yで表したい。
P≠Qの場合(加算公式)
=λ+λ+x+x+a
=λ(x+x)+x+y
λ=(y+y)/(x+x) (60)
【0073】
P=Qの場合(2倍点公式)
λがPにおける導関数dy/dxの値である以外、P≠Qの場合と同様である。Pの2倍点の座標の式は次のとおりである。
=x+a/x
=x+λx+x
λ=x+y/x (61)
なお2倍点の座標であることを明示するために、この場合の(x,y)を(x,y)と表すこともある。
【0074】
3倍点公式
P=(x,y)、2P=(x,y)、3P=(x,y)として、3倍点3P=(x,y)=(x,y)+(x,y)を求める。3Pの座標は次で与えられる。
=μ+μ+x+x+a/x+a
=μ(x+x)+x+y
λ=x+y/x, μ=λ+(x+a)/(x+x+a) (62)
【0075】
[8.2] 非超特異の場合:加算の計算量
P+Q=(x,y)の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれS、M、Iで表す。
P≠Qの場合
1.λ=(y+y)/(x+x)の計算:
(x+x-1の計算に逆元算のコストI。
これにy+yをかける計算に乗算のコストM。
2.x=λ+λ+x+x+aの計算:
λの計算に平方算のコストS。
3.y=λ(x+x)+x+yの計算:
λをx+xにかける計算に乗算のコストM。
以上の合計コストt=1I+2M+1S。なおtの添え字AはAddition(加算)のつもりである。
【0076】
P=Qの場合
1.λ=x+y/xの計算:
-1の計算に逆元算のコストI。
/xの計算に乗算のコストM。
2.x=x+a/xの計算:
の計算に平方算のコストS。
(x-1の計算に平方算のコストS。
これにaをかける計算に乗算のコストM。
3.y=x+λx+xの計算:
λをxにかける計算に乗算のコストM。
以上の合計コストt=1I+3M+1S=t+M。なおtの添え字DはDoubling(2倍算)のつもりである。
【0077】
まとめ
以上をまとめると、標数2の有限体F上で定義された非超特異な楕円曲線におけるP+Qの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量t=1I+2M+1S
2倍算の場合、計算量t=1I+3M+1S=t+1M
【0078】
[8.3] 3倍算の計算量:非超特異の場合
点Pの3倍算すなわち3Pを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれM、Iで表わす。なお平方算のコストをSで表すが、ここではS≒Mとする。
1.λの計算:
前出の通りコストは1I+1M。
2.μの計算:
コストは計1I+2M+2S。
3.xの計算:
μの計算に平方算のコストS。
4.yの計算:
μをx+xにかける計算に乗算のコストM。
以上の合計コストt=2I+4M+3S=2t+1S。なお2Pを求めてからPを加算して3Pを求めると、計算量はt’=t+t=2t+1M+1S=t+Mであることに注意する。
【0079】
[9] 楕円曲線:標数2で超特異の場合
標数2の体F上の超特異な楕円曲線Eの方程式を次のように与える。
+aY=X+aX+a, a,a,a∈F. (63)
【0080】
[9.1] 超特異の場合:加法公式
前と同じく(x,y)、(x,y)、(x,y)でそれぞれP、Q、P+Qの座標を表す。xとyをx,y,x,yで表したい。
P≠Qの場合(加算公式)
=λ+x+x
=λ(x+x)+y+a
λ=(y+y)/(x+x) (64)
【0081】
P=Qの場合(2倍点公式)
λがPにおける導関数dy/dxの値である以外、P≠Qの場合と同様である。Pの2倍点の座標の式は次のとおりである。
=(x+a)/a=λ
=λ(x+x)+y+a
λ=(x+a)/a (65)
なお2倍点の座標であることを明示するために、この場合の(x,y)を(x,y)と表すこともある。
【0082】
3倍点公式
P=(x,y)、2P=(x,y)、3P=(x,y)として、3倍点3P=(x,y)=(x,y)+(x,y)を求める。3Pの座標は次で与えられる。
=μ+λ+x
=μ(x+x)+y+a
λ=(x+a)/a, μ=λ+a/(x+λ) (66)
【0083】
[9.2] 超特異の場合:加算の計算量
P+Q=(x,y)の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれS、M、Iで表す。
P≠Qの場合
1.λ=(y+y)/(x+x)の計算:
(x+x-1の計算に逆元算のコストI。
これにy+yをかける計算に乗算のコストM。
2.x=λ+x+xの計算:
λの計算に平方算のコストS。
3.y=λ(x+x)+y+aの計算:
λをx+xにかける計算に乗算のコストM。
以上の合計コストt=1I+2M+1S。なおtの添え字AはAddition(加算)のつもりである。
【0084】
P=Qの場合
1.λ=(x+a)/aの計算:
の計算に平方算のコストS。
+aにa-1をかける計算に乗算のコストM。
2.x=λの計算:
λの計算に平方算のコストS。
3.y=λ(x+x)+y+aの計算:
λ(x+x)の計算に乗算の乗算のコストM。
以上の合計コスト合計t=2M+2S。
【0085】
まとめ
以上をまとめると、標数2の有限体F上で定義された超特異な楕円曲線におけるP+Qの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量t=1I+2M+1S
2倍算の場合、計算量t=2M+2S
【0086】
[9.3] 3倍算の計算量:超特異の場合
点Pの3倍算すなわち3Pを求める計算のコストを考える。
1.λ=(x+a)/aの計算:
前出の通りコストは1M+1S。
2.μ=λ+a/(x+λ)の計算:
λの計算に平方算のコストS。
(x+λ-1の計算に逆元算のコストI。
これにaをかける計算に乗算のコストM。
3.x=μ+λ+xの計算:
μの計算に平方算のコストS。
4.y=μ(x+x)+y+aの計算:
μをx+xにかける計算に乗算のコストM。
以上の合計コストt=1I+3M+3S。なお2Pを求めてからPを加算して3Pを求めると、計算量はt’=t+t=1I+4M+3S=t+Mであることに注意する。
【0087】
[具体例]
実施の形態1
図1は、実施の形態1に係る楕円曲線整数倍演算装置100の構成図である。これらの構成は、ハードウエア的には、任意のコンピュータのCPU、メモリ、その他のLSIで実現でき、ソフトウエア的にはメモリにロードされた暗号処理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。後述する鍵生成装置200、暗号化装置300、および復号装置400の構成についても同様である。
【0088】
入出力部10は、楕円曲線を規定する標数や関数の係数などのパラメータ、楕円曲線上の点Pの座標、および整数倍算の倍数を与える整数kの入力を受け付ける。入力された楕円曲線を規定するパラメータは楕円曲線パラメータ18として、点Pの座標と整数kは入力データ12として主記憶装置や外部記憶装置などの記憶部に保持される。記憶部には、入力データ12以外に、楕円曲線情報15、中間データであるs進展開データ14と予備計算データ24、および最終データであるk倍算結果データ26が記憶される。
【0089】
楕円曲線情報15には、楕円曲線パラメータ18以外に、コスト評価式データ16、加算公式データ20、s倍点公式データ22が含まれる。コスト評価式データ16、加算公式データ20、およびs倍点公式データ22は、楕円曲線の標数pによって、p=2で非超特異の場合、p=2で超特異の場合、p=3の場合、p>3の場合に分けて、あらかじめ用意された数式データであり、楕円曲線パラメータ18として、具体的に楕円曲線の係数が与えられることで、計算が可能である。
【0090】
s進展開部28は、入力データ12の整数kについて複数の基数sによるs進展開を求め、各基数s毎にs進展開データ14として記憶する。
【0091】
コスト評価部30は、s進展開データ14を参照して、s進展開の桁数、s進展開の非零桁の個数を取得し、非零桁の個数を桁数で除算することにより、各s進展開の相対重みを算出する。さらに、コスト評価部30は、s進法の計算量を相対重みの関数で表したコスト評価式データ16を参照し、各s進展開の相対重みに基づいてs進法によりk倍算を行った場合の計算コストを求める。
【0092】
選択部32は、コスト評価部30によって求められた各s進法の計算コストの内、もっとも小さい計算コストを選択し、その場合の基数hを出力して、予備計算部34とh進法演算部35に与える。
【0093】
コスト評価部30および選択部32によってなされるコスト評価と最適なh進法の選択は、楕円曲線の標数p>3の場合は前提技術の[4]、[5]、標数p=3の場合は前提技術の[7]、標数p=2の場合は前提技術の[8]、[9]の記載に基づくものである。ただし、前提技術では、一例として、複数の基数sとして、s=2、3を用いた場合を説明しているが、基数sとして、s=2、3以外を用いてもよく、また、3つ以上の基数sを用いてもよい。
【0094】
予備計算部34は、入力データ12に含まれる点Pについて(h-1)倍以下の整数倍点をあらかじめ計算し、予備計算データ24として記憶する。h=3であれば、2Pを求めて記憶する。h=4であれば、2P、3Pを求めて記憶する。ただし、h=2であれば、予備計算は不要である。
【0095】
h進法演算部35は、記憶されている複数の基数sについてのs進展開データ14の中から、選択部32により選択された基数hについてのh進展開データを取得する。また、h進法演算部35は、楕円曲線パラメータ18と、楕円曲線上で点の加算を求めるための加算公式データ20を読み出す。さらに、h進法演算部35は、記憶されている複数の基数sについてのs倍点公式データ22の中から、選択部32により選択された基数hについてのh倍点公式データを取得する。
【0096】
h進法演算部35は、h進展開データ、楕円曲線パラメータ18、加算公式データ20、h倍点公式データに基づき、入力データ12の点Pのk倍算をh進法により計算し、得られたk倍点kPをk倍算結果データ26として記憶する。
【0097】
h進法演算部35によってなされるh進法は、点Pのh倍算と、あらかじめ計算した点Pの(h-1)倍以下の整数倍点の加算を組み合わせて、点Pのk倍算を計算するものである。点Pのh倍算は、h倍算演算部36によってなされ、点Pの(h-1)倍以下の整数倍点の加算は、予備計算データ24を用いて加算演算部38によってなされる。加算演算部38による加算結果はh倍算演算部36の入力として与えられて、さらにh倍算される。h倍算演算部36および加算演算部38によってなされるh進法演算は、2進法の場合は、前提技術[4.1]、[7.1]に記載のアルゴリズム、3進法の場合は、前提技術[4.2]、[7.2]に記載のアルゴリズムに基づくものであり、後にフローチャートを用いて詳細な動作を説明する。
【0098】
最終的にk倍算結果データ26として得られた点Pのk倍点Q=kPは入出力部10より出力される。
【0099】
図2は、以上の構成の楕円曲線整数倍演算装置100による整数倍演算手順を説明するフローチャートである。ここでは、一例として、2進法または3進法を選択して整数倍演算を行う場合を説明する。
【0100】
入出力部10は楕円曲線上の点Pと整数kの入力を受け付ける(S10)。s進展開部28は、整数kの2進展開と3進展開を算出する(S12)。
【0101】
コスト評価部30は、整数kの2進展開における非零桁の個数wを2進展開の桁数lで除算した相対重みw’と、整数kの3進展開における非零桁の個数wを3進展開の桁数iで除算した相対重みw’を算出する(S14)。
【0102】
選択部32は、前提技術の[5.1]で説明した2進展開の相対重みw’と3進展開の相対重みw’に関する条件Terが成立するかどうかを調べる(S16)。条件Terが成立するなら(S16のY)、予備計算部34およびh進法演算部35は、3進法により点Pのk倍点kPを算出する(S18)。条件Terが成立しないなら(S16のN)、h進法演算部35は、2進法により点Pのk倍点kPを算出する(S20)。入出力部10は、こうして得られたk倍点Q=kPを出力する(S22)。
【0103】
図3は、ステップS18の3進法によるk倍算の詳細な手順を説明するフローチャートである。
【0104】
予備計算部34は、点Pの2倍点P=2Pをあらかじめ計算して記憶する(S30)。h進法演算部35は、整数kの3進展開k=hi-1i-2…h0(3)を取得する(S32)。ここで、iはkの3進桁数であり、最上位桁hi-1は0ではない。Qの初期値として、hi-1=1ならば、QにPを代入し、hi-1=2ならば、QにPを代入する(S34)。
【0105】
次に、h進法演算部35は、添え字jをi-2に設定する(S36)。h倍算演算部36は、3倍算公式により現在のQに対して3倍点3Qを求め、3QをQに代入する(S38)。加算演算部38は、h=1ならば、現在のQにPを加算した値Q+Pを求め、その加算値をQに代入し、h=2ならば、現在のQにPを加算した値Q+P求め、その加算値をQに代入する(S40)。なお、ここでh=0のときは、加算演算部38による加算は行わない。
【0106】
h進法演算部35は、添え字jにj-1を代入する、すなわち添え字jを1だけデクリメントする(S42)。j<0であれば(S44のY)、そのときのQがPのk倍点であり、k倍算の手順を終了してリターンする。j<0でなければ(S44のN)、ステップS38に戻り、h倍算演算部36による3倍算演算と、加算演算部38による加算が繰り返される。
【0107】
図4は、ステップS20の2進法によるk倍算の詳細な手順を説明するフローチャートである。
【0108】
h進法演算部35は、整数kの2進展開k=kl-1l-2…k0(2)を取得する(S50)。ここで、lはkの2進桁数であり、最上位桁hl-1は1である。Qの初期値として、QにPを代入する(S52)。
【0109】
次に、h進法演算部35は、添え字jをl-2に設定する(S54)。h倍算演算部36は、2倍算公式により現在のQに対して2倍点2Qを求め、2QをQに代入する(S56)。加算演算部38は、h=1ならば、現在のQにPを加算した値Q+Pを求め、その加算値をQに代入する(S58)。なお、ここでh=0のときは、加算演算部38による加算は行わない。
【0110】
h進法演算部35は、添え字jにj-1を代入する、すなわち添え字jを1だけデクリメントする(S60)。j<0であれば(S62のY)、そのときのQがPのk倍点であり、k倍算の手順を終了してリターンする。j<0でなければ(S62のN)、ステップS56に戻り、h倍算演算部36による2倍算演算と、加算演算部38による加算が繰り返される。
【0111】
以上述べたように、実施の形態の楕円曲線整数倍演算装置100によれば、楕円曲線上で任意の点Pのk倍点Qを求める際、複数の基数sについて整数kのs進展開を求め、s進法の計算コストを評価し、計算コストの最も小さいh進法によりk倍演算を行う。これにより、単に2進法だけを用いる整数倍算に比べて、計算時間を短縮することができる。
【0112】
一般に、h>3として、h倍算の計算量は、(h-1)倍算と加算の組み合わせの計算量よりも多くなることはないといえる。なぜなら、h倍点公式は、hP=(h-1)P+Pの関係から式を整理して得られるため、式変形の結果、計算量が少なくなることがあり、また、最悪のケースでも、h倍算を(h-1)倍算と加算の組み合わせに置き換えて計算できるからである。したがって、2倍算だけでなく、h倍算を利用することで、計算量をさらに少なくすることができる。もっとも、h進展開したときに、非零桁の個数が多いと、h倍算が利用できる回数が減るため、いつでもh進法が2進法よりも計算量が少ないとは限らない。そこで、実施の形態では、いくつかの基数sによるs進展開を求めて、非零桁の個数により計算量を評価し、複数のs進法の中から計算量の少ないものを選ぶことにより、最適なh進法を選択し、高速化を図っている。
【0113】
実施の形態2
図5は、実施の形態2に係る鍵生成装置200の構成図である。鍵生成装置200は、実施の形態1の楕円曲線整数倍演算装置100を利用して秘密鍵と公開鍵のペアを生成するものである。
【0114】
鍵生成装置200は、楕円曲線データ42の入力を受け付け、生成された鍵データ44を出力する入出力部40と、乱数を生成する乱数生成部46と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部48と、鍵データ44を生成する鍵生成部50を含む。楕円曲線整数倍演算部48として、実施の形態1の楕円曲線整数倍演算装置100を用いる。
【0115】
図6は、鍵生成装置200による鍵生成手順を説明するフローチャートである。図6も参照しながら、図5の各構成の動作を説明する。
【0116】
入出力部40は、楕円曲線パラメータ、楕円曲線上の基点Gおよびその位数nの入力を受け付ける(S200)。これらのデータは楕円曲線データ42として記憶部に記憶される。乱数生成部46は、楕円曲線データ42に含まれる位数nを参照して、0<d<nを満たす乱数dを生成し、楕円曲線整数倍演算部48に与える(S210)。
【0117】
楕円曲線整数倍演算部48は、楕円曲線データ42に含まれる基点Gの座標を読み出し、基点Gのd倍点Q=dGを算出する(S220)。楕円曲線整数倍演算部48は、d倍点の算出に当たり、実施の形態1で述べたように、計算量が最も少ないh進法を選択して、h進法によるd倍演算を行う。
【0118】
鍵生成部50は、乱数生成部46が生成した乱数dを秘密鍵、楕円曲線整数倍演算部48が算出したd倍点Qを公開鍵とした鍵データ(d,Q)を生成して、鍵データ44として記憶部に保持する(S230)。入出力部40は、生成された鍵データ44を出力する。
【0119】
本実施の形態の鍵生成装置200によれば、楕円曲線暗号により秘密鍵と公開鍵のペアを生成する際、計算量の最も少ないh進法を利用することにより、鍵生成を高速化できる。
【0120】
実施の形態3
図7は、実施の形態3に係る暗号化装置300の構成図である。暗号化装置300は、実施の形態1の楕円曲線整数倍演算装置100を利用して平文を暗号化するものである。
【0121】
暗号化装置300は、楕円曲線データ62、公開鍵データ64および平文データ66の入力を受け付け、生成された暗号文データ68を出力する入出力部60と、乱数を生成する乱数生成部70と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部72と、平文データ66を暗号化して暗号文データ68を生成する暗号文生成部74とを含む。楕円曲線整数倍演算部72として、実施の形態1の楕円曲線整数倍演算装置100を用いる。
【0122】
図8は、暗号化装置300による暗号化手順を説明するフローチャートである。図8も参照しながら、図7の各構成の動作を説明する。
【0123】
入出力部60は、楕円曲線パラメータ、楕円曲線上の基点Gおよびその位数nの入力を受け付ける(S300)。これらのデータは楕円曲線データ42として記憶部に記憶される。入出力部60は、さらに公開鍵Qと平文Mの入力を受け付ける(S310)。これらのデータはそれぞれ公開鍵データ64と平文データ66として記憶される。乱数生成部70は、楕円曲線データ42に含まれる位数nを参照して、0<r<nを満たす乱数rを生成し、楕円曲線整数倍演算部72に与える(S320)。
【0124】
楕円曲線整数倍演算部72は、楕円曲線データ62に含まれる基点Gの座標を読み出して、基点Gのr倍点rGを算出し、さらに、公開鍵データ64に含まれる公開鍵Qを読み出して、公開鍵Qのr倍点rQを算出する(S330)。楕円曲線整数倍演算部48は、r倍点の算出に当たり、実施の形態1で述べたように、計算量が最も少ないh進法を選択して、h進法によるr倍演算を行う。楕円曲線整数倍演算部72は、算出した2つのr倍点rG、rQを暗号文生成部74に与える。
【0125】
暗号文生成部74は、平文データ66に含まれる平文Mを読み出し、第1暗号C1=rGと第2暗号C2=rQ+Mを算出し、暗号文(C1、C2)を生成する(S340)。生成された暗号文(C1、C2)は、暗号文データ68として記憶され、入出力部60により出力される。
【0126】
本実施の形態の暗号化装置300によれば、楕円曲線暗号により平文を暗号化する際、計算量の最も少ないh進法を利用することにより、暗号化処理の高速化を図ることができる。
【0127】
実施の形態4
図9は、実施の形態4に係る復号装置400の構成図である。復号装置400は、実施の形態1の楕円曲線整数倍演算装置100を利用して暗号文を復号するものである。
【0128】
復号装置400は、楕円曲線データ82、秘密鍵データ84および暗号文データ86の入力を受け付け、生成された平文データ88を出力する入出力部80と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部90と、暗号文データ86を復号して平文データ88を生成する平文生成部92とを含む。楕円曲線整数倍演算部90として、実施の形態1の楕円曲線整数倍演算装置100を用いる。
【0129】
図10は、復号装置400による復号手順を説明するフローチャートである。図10も参照しながら、図9の各構成の動作を説明する。
【0130】
入出力部80は、楕円曲線パラメータの入力を受け付け、楕円曲線データ82として記憶部に記憶する。入出力部60は、さらに秘密鍵dと暗号文(C1、C2)の入力を受け付ける(S400)。これらのデータはそれぞれ秘密鍵データ84と暗号文データ86として記憶される。
【0131】
楕円曲線整数倍演算部90は、秘密鍵データ84に含まれる秘密鍵dと、暗号文データ86に含まれる第1暗号C1を読み出し、楕円曲線データ82に基づいて、第1暗号C1のd倍点dC1を算出する(S410)。楕円曲線整数倍演算部90は、d倍点の算出に当たり、実施の形態1で述べたように、計算量が最も少ないh進法を選択して、h進法によるd倍演算を行う。楕円曲線整数倍演算部90は、算出したd倍点dC1を平文生成部92に与える。
【0132】
平文生成部92は、暗号文データ86に含まれる第2暗号C2を読み出し、M=C2-dC1の計算により平文Mを生成する(S420)。生成された平文Mは、平文データ88として記憶され、入出力部80により出力される。ここで、第2暗号C2は、暗号化装置300によりrQ+Mの演算で暗号化されたものであり、第1暗号C1は、暗号化装置300により基点Gのr倍点rGとして暗号化されたものであり、公開鍵Qは、鍵生成装置200により基点Gのd倍点dGとして生成されたものであることに注意すると、C2-dC1=rQ+M-d(rG)=r(dG)+M-d(rG)=Mとなることから、平文Mの解読が保証されている。
【0133】
本実施の形態の復号装置400によれば、楕円曲線暗号により暗号文を復号する際、計算量の最も少ないh進法を利用することにより、復号処理の高速化を図ることができる。
【0134】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【0135】
上記の説明では、計算コストに基づき2進法と3進法を選択的に利用する方法を一例として説明したが、2進法、3進法以外を用いてもよく、3つ以上のs進法の中から計算量の少ないh進法を選択してもよい。
【0136】
上記の説明では、実施の形態1の楕円曲線整数倍演算装置100の利用例として、鍵生成、暗号化および復号を説明したが、これ以外に、デジタル署名の生成と署名の検証に用いてもよい。また、一例として楕円曲線を利用したElGamal暗号を説明したが、楕円曲線を利用した暗号方式は特にこれに限定されない。
【0137】
上記の説明では、演算にはアフィン座標系を用いたが、他の座標系、たとえば射影座標系を用いてもよい。特に、逆元算の計算コストが乗算に比べて高いとき、射影座標で演算することが効率的である。
【図面の簡単な説明】
【0138】
【図1】実施の形態1に係る楕円曲線整数倍演算装置の構成図である。
【図2】図1の楕円曲線整数倍演算装置による整数倍演算手順を説明するフローチャートである。
【図3】図2の3進法による整数倍算の詳細な手順を説明するフローチャートである。
【図4】図2の2進法による整数倍算の詳細な手順を説明するフローチャートである。
【図5】実施の形態2に係る鍵生成装置の構成図である。
【図6】図5の鍵生成装置による鍵生成手順を説明するフローチャートである。
【図7】実施の形態3に係る暗号化装置の構成図である。
【図8】図7の暗号化装置による暗号化手順を説明するフローチャートである。
【図9】実施の形態4に係る復号装置の構成図である。
【図10】図9の復号装置による復号手順を説明するフローチャートである。
【符号の説明】
【0139】
28 s進展開部、 30 コスト評価部、 32 選択部、 34 予備計算部、 35 h進法演算部、 36 h倍算演算部、 38 加算演算部、 46、70 乱数生成部、 48、72、90 楕円曲線整数倍演算部、 50 鍵生成部、 74 暗号文生成部、 92 平文生成部、 100 楕円曲線整数倍演算装置、 200 鍵生成装置、 300 暗号化装置、 400 復号装置。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9