説明

楕円曲線ペアリング演算方法、暗号化方法、復号化方法、プログラム、楕円曲線ペアリング演算装置、暗号化装置および復号化装置

【課題】効率的な楕円曲線ペアリング演算を行うことを目的とする。
【解決手段】Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現したTwisted Edward型楕円曲線上の素数位数の点P(Z1=1)と、affine座標を用いて表現したQとのペアリング演算を行うことを特徴とする。また、このペアリング演算を用いたIDベース暗号による暗号化方法、および、このIDベース暗号を復号する復号化方法も提供する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、楕円曲線ペアリング演算方法、暗号化方法、復号化方法、プログラム、楕円曲線ペアリング演算装置、暗号化装置および復号化装置に関するものである。
【背景技術】
【0002】
任意の文字列を公開鍵として用いることのできるID(Identification)ベース方式による暗号、デジタル署名がある。これらは、ペアリングと呼ばれる双線形写像の性質を応用して実現される。
【0003】
ペアリングとは、位数がnの3つの群をG,G,Gとした時、G×GからGへの写像eで以下の性質を満たすもののことである。ここで、「×」は直積を意味する。
1.任意のP∈Gおよび任意のQ∈Gに対してeはe(aP,bQ)=e(P,Q)abを満たす。
2.任意のP∈Gおよび任意のQ∈Gに対してe(P,Q)はGの単位元と異なる。
【0004】
具体的なペアリングとしてはReduced Tateペアリングが知られている。
qを2で割ることのできない素数のべきとし、E(F)をF上で定義される楕円曲線とし、その単位元をOとする。E(F)の位数を#E(F)、nを#E(F)を割り切る素数、E(F)[n]をE(F)の位数nの部分群、kをk>1を満たし、nがq−1を割り切る最小の整数とする。またfをP∈E(F)[n]に対して計算される多項式とする。
この時Reduced Tateペアリングは以下のように定義することができる。
【0005】
【数1】

【0006】
ここで、FおよびFの定義は以下の通りである。
:位数qの有限体
:位数qの有限体Fqから0を除いたもので乗法に関して群構造を持つもの。
【0007】
次に、非特許文献4に基づき、Reduced Tateペアリングを計算するアルゴリズムを示す。以下、Reduced Tateペアリングをペアリングと呼ぶ。
【0008】
入力:楕円曲線上の点P∈E(F)、Q∈E(Fq1)/nE(Fq1)、点P、Qの位数である素数n
出力:f=e(P,Q)∈Fq1/nFq1
(ここで、q1=q
【0009】
処理手順:
(1)計算機が、nを2進数展開して、n=n+n×2+・・・+nt−1×2t−1 (nt−1=1)とする。
(2)計算機が、R←Pとおく。
(3)計算機が、f←1とおく。
(4)計算機が、i←t−2とおく。
(5)i≧0を満たす間、計算機は、以下の処理(5−1)〜(5−3)を繰り返す。
(5−1)計算機が、f←f--R,R(Q),R←2Rを計算する(2倍算処理)。
(5−2)計算機が、n=1であればf←fgR,P(Q),Q←Q+Pを計算する(加算処理)。
(5−3)計算機が、i←i−1を計算する。
【0010】
(6)計算機が、f←f(q1−1)/n(q1=q)を計算する。
【0011】
(7)計算機が、計算結果としてfを出力する
【0012】
このようなペアリングの具体的な計算方法は、ペアリングが定義される楕円曲線に依存して決まる。また、上記アルゴリズムにおけるループ処理では楕円曲線上の加算および2倍算処理が行われる。
ここでは楕円曲線として加算・2倍算処理に適した楕円曲線として知られているTwisted Edward型楕円曲線を用いる(例えば、非特許文献2参照)。
【0013】
まず、非特許文献2に基づきTwisted Edward型楕円曲線について説明する。
Twisted Edward型楕円曲線とは標数が2以外の有限体をFとした場合、ax+y=1+dx (a,dはF上の定数でad(a−d)≠0を満たす)で表される曲線であり、この曲線上の点は、曲線の方程式を満たすx,y∈Fの組(x,y)で表すことができる。以下(x、y)の組で表される座標をAffine座標と呼ぶ。
【0014】
Twisted Edward型楕円曲線上の2点P,Qに対して加算P+Qが、1点Pに対して2倍算2Pが定義でき具体的な計算方法が知られている。
Twisted Edward型楕円曲線上の2点P=(x,y)、Q=(x,y)に対して加算は以下の式(1)で計算することができる。
【0015】
【数2】

【0016】
さらに、点P=(x,y)に対して2倍算は上記加算式においてP=Qとすることで計算できる。以下に示す式(2)は2倍算に特化した形で前記した加算式(式(1))を記載したものである。
【0017】
【数3】

【0018】
また、点P=(x,y)に対して−Pを(−x,y)で定義する。
Twisted Edward型楕円曲線上の点全体からなる集合は、加算に対して(0,1)を単位元とする加法群の構造を持つ。またTwisted Edward型楕円曲線上の点Pおよび、正整数Lに対してPのL回加算LPを求める演算をスカラ倍と呼ぶ。
また、Twisted Edward型楕円曲線上の点Pに対してPをn回加算するスカラ倍の演算結果nPが単位元である(0,1)となる場合、正整数nを点Pの位数と呼ぶ。
【0019】
非特許文献3において、F上で係数aは2乗根を持ち係数dは持たない場合、係数dを用いない加算方法が開示されている。以下、非特許文献3に基づき上記加算方法を説明する。
【0020】
楕円曲線上の2点をP=(x,y)、Q=(x,y)、P≠Q、PおよびQは素数位数とした場合、加算P+Qは以下の式(3)で計算することができる。
【0021】
【数4】

【0022】
非特許文献2に開示されている加算および2倍算では有限体F上の乗算に比べて10倍以上演算コストの大きい逆元計算が用いられる。この問題に対して逆元計算を用いないことでより高速な加算および2倍算の計算方法が非特許文献3に開示されている。
【0023】
具体的には、点(x,y)をx=X/Z、y=Y/Z、xy=T/Z、Z≠0を満たすX,Y,Z,T∈Fを用いて変換した拡張射影座標(X:Y:T:Z)を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う。
なお、拡張射影座標(X:Y:T:Z)に含まれるT座標を省略した座標(X:Y:Z)を射影座標と呼ぶことにする。
【0024】
次に、非特許文献3に基づき逆元計算の必要の無い加算アルゴリズムを示す。なお、以降のアルゴリズムの説明においてm,s,Dは、それぞれ定義体F上の乗算、2乗算、定数倍算の演算コストを示す。
入力情報:(X:Y:T:Z),(X:Y:T:Z
出力情報:(X:Y:T:Z)=(X:Y:T:Z)+(X:Y:T:Z
処理手順:
(1)計算機が、A←X、B←Y、C←Z、D←T、E←D+CをF上でそれぞれ計算する(4m)。
(2)計算機が、F←(X−Y)(X+Y)+B−A、G←B+aA、H←D−CをF上でそれぞれ計算する(1m,1D)。
(3)計算機が、X←EFをF上で計算する(1m)。
(4)計算機が、Y←GHをF上で計算する(1m)。
(5)計算機が、T←EHをF上で計算する(1m)。
(6)計算機が、Z←FGをF上で計算する(1m)。
(7)計算機が、(X:Y:T:Z)を演算結果として出力する。
この加算アルゴリズムの総演算コストは9m+1D、Zが1であれば1回の乗算を削減できるため総演算コストは8m+1Dとなる。
【0025】
次に、非特許文献3に基づき逆元計算の必要の無い2倍算アルゴリズムを示す。
入力情報:(X:Y:T:Z
出力情報:(X:Y:T:Z)=2(X:Y:T:Z
処理手順:
(1)計算機が、A←X、B←Y、C←2Z、D←aAをF上でそれぞれ計算する(3s,1D)。
(2)計算機が、E←(X+Y−A−B、G←D+B、F←G−C、H←D−BをF上でそれぞれ計算する(1s)。
(3)計算機が、X←EFをF上で計算する(1m)。
(4)計算機が、Y←GHをF上で計算する(1m)。
(5)計算機が、T←EHをF上で計算する(1m)。
(6)計算機が、Z←FGをF上で計算する(1m)。
(7)計算機が、(X:Y:T:Z)を演算結果として出力する。
この2倍算アルゴリズムの総演算コストは4m+4s+1Dとなる。
【0026】
また、点(x,y)をx=Z/X、y=Z/Y、XYZ≠0を満たすX,Y,Z∈Fを用いて変換したInverted Twisted Edward座標(X:Y:Z)を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う方法が非特許文献2に開示されている。
【0027】
次に、非特許文献2に基づき逆元計算の必要の無い加算アルゴリズムを示す。
入力情報:(X:Y:Z),(X:Y:Z
出力情報:(X:Y:Z)=(X:Y:Z)+(X:Y:Z
処理手順:
(1)計算機が、A←Z、B←dA、C←X、D←Y、E←CDをF上でそれぞれ計算する(4m,1s,1D)。
(2)計算機が、H←C−aD、I←(X+Y)(X+Y)−C−DをF上でそれぞれ計算する(1m,1D)。
(3)計算機が、X←(E+B)HをF上で計算する(1m)。
(4)計算機が、Y←(E−B)IをF上で計算する(1m)。
(5)計算機が、Z←AHIをF上で計算する(2m)。
(6)計算機が、(X:Y:Z)を演算結果として出力する。
この加算アルゴリズムの総演算コストは9m+1s+2D、Zが1であれば1回の乗算を削減できるため総演算コストは8m+1s+2Dとなる。
【0028】
次に、非特許文献2に基づき逆元計算の必要の無い2倍算アルゴリズムを示す。
入力情報:(X:Y:Z
出力情報:(X:Y:Z)=2(X:Y:Z
処理手順:
(1)計算機が、A←X、B←Y、U←aBをF上でそれぞれ計算する(2s,1D)。
(2)計算機が、C←A+U、D←A−U、E←(X+Y−A−BをF上でそれぞれ計算する(1s)。
(3)計算機が、X←CDをF上で計算する(1m)。
(4:計算機が、Y←E(C−2dZ)をF上で計算する(1m,1s,1D)。
(5)計算機が、Z←DEをF上で計算する(1m)。
(6)計算機が、(X:Y:Z)を演算結果として出力する。
この2倍算アルゴリズムの総演算コストは3m+4s+2Dとなる。
【0029】
次に、非特許文献4に基づきTwisted Edward型楕円曲線を用いた、ペアリングの計算方法を説明する。
【0030】
2以外の素数のべきqに対して、素数nがq−1を割り切り、かつ最小のkが偶数であるとする。この時、楕円曲線の定義体をF、位数nの部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(F)をax+y=1+dx(ad(a−d)≠0かつF上で係数aは2乗根を持ち係数dは持たない)、その位数nの部分群をGとする。
【0031】
のk次拡大体Fq1(q1=q、kは偶数)はFのk/2次拡大体Fq2(q2=qk/2)の2次拡大体と見なすことができ、α=δ∈Fq2(q2=qk/2)を満たす基底{1,α}を用いることで任意の元をx+yα(x,y∈Fq2(q2=qk/2))で表現することができる。
さらに、Qを、E(F)をFq1(q1=q)上の楕円曲線と見なしたE(Fq1)(q1=q)上の位数nの元で射影座標を用いてQ=(Xα:Y:Z)(X,Y,Z∈Fq2:q2=qk/2)と表現できるものとする。この時、Qの属する位数nの部分群をGとし、Fq1(q1=q)の位数nの乗法に関する部分群をGとする。
【0032】
次に、ペアリングを計算するアルゴリズムを非特許文献4に基づき示す。
入力:点P=(X:Y:T:Z)∈G,Q=(Xα:Y:Z)∈G(X,Y,Z∈Fq2:q2=qk/2
出力:f=e(P,Q)∈G
【0033】
処理手順:
(1)計算機が、点Pの位数である3以上の素数nを2進数展開して、n=n+n×2+・・・+nt−1×2t−1 (nt−1=1)とする。
(2)計算機が、η←(Z+Y)/(Xδ)とおく。
(3)計算機が、y←Y/Zとおく。
(4)計算機が、R←Pとおく。
(5)計算機が、f←1とおく。
(6)計算機が、i←t−2とおく。
(7)i≧0を満たす間、計算機は、以下の処理(7−1)〜(7−3)を繰返す。
(7−1)計算機が、f←fR,R(Q),R←2Rを計算する(2倍算処理)。なお、(7−1)の計算方法は後記する。
(7−2)計算機が、n=1であればf←fgR,P(Q),R←R+Pを計算する(加算処理)。なお、(7−2)の計算方法は後記する。
(7−3)計算機が、i←i−1を計算する。
(8)計算機が、f←f(q1−1)/n(q1=q)を計算する。
(9)fを計算結果とする。
【0034】
次に、(7−1)における2倍算処理について詳しく説明する。
入力情報:R=(X:Y:T:Z
出力情報:R=(X:Y:T:Z)=2(X:Y:T:Z)、f
処理手順:(7−1)、(7−2)の処理における、m,s,Dは、それぞれ定義体F上の乗算、2乗算、定数倍算の演算コスト、M,Dは、それぞれFのk次拡大体Fq1(q1=q)上の乗算、2乗算の演算コストを示す。ただし、定義体F上の2倍算については、より演算コストの小さい加算もしくは1ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
(1)計算機が、A←X、B←Y、C←Z、D←(X+Y、E←(Y+ZをF上でそれぞれ計算する(5s)。
(2)計算機が、F←D−(A+B)、G←E−(B+C)、H←aAをF上でそれぞれ計算する(1D)。
(3)計算機が、I←H+B、J←C−I、K←J+CをF上でそれぞれ計算する。
(4)計算機が、cZZ←2Y(T−X)をF上で計算する(1m)。
(5)計算機が、cXY←2J+GをF上で計算する。
(6)計算機が、cXZ←2(aX−B)をF上で計算する(1m,1D)。
(7)計算機が、gR,R(Q)←cZZηα+cXY+cXZをFq2(q2=qk/2)上で計算する(km)。
【0035】
(8)計算機が、f←fR,R(Q)を計算する(1M、1S)。
(9)計算機が、X←FKをF上で計算する(1m)。
(10)計算機が、Y←I(B−H)をF上で計算する(1m)。
(11)計算機が、T←F(B−H)をF上で計算する(1m)。
(12)計算機が、Z←IKをF上で計算する(1m)。
(13)計算機が、R=(X:Y:T:Z)、fを演算結果とする。
この2倍算アルゴリズムの総演算コストは1M+1S+(k+6)m+5s+2Dとなる。
【0036】
次に、(7−2)における加算ステップについて説明する。
入力情報:R=(X:Y:T:Z),P=(X:Y:T:Z)、f
出力情報:R=(X:Y:T:Z)=(X:Y:T:Z)+(X:Y:T:Z)、f
【0037】
処理手順:
(1)計算機が、A←X、B←Y、C←Z、D←T、E←D+CをF上でそれぞれ計算する(4m)。
(2)計算機が、F←(X−Y)(X+Y)+B−A、G←B+aA、H←D−C、I←TをF上でそれぞれ計算する(2m,1D)。
(3)計算機が、cZZ←(T−X)(T+X)−I+AをF上で計算する(1m)。
(4)計算機が、cXY←X−X+FをF上で計算する(2m)。
(5)計算機が、cXZ←(Y−T)(Y+T)−B+I−HをF上で計算する(1m)。
【0038】
(7)計算機が、gR,P(Q)←cZZηα+cXY+cXZをFq2(q2=qk/2)上で計算する(km)。
【0039】
(8)計算機が、f←fgR,P(Q)を計算する(1M)。
(6)計算機が、X←EFをF上で計算する(1m)。
(7)計算機が、Y←GHをF上で計算する(1m)。
(8)計算機が、T←EHをF上で計算する(1m)。
(9)計算機が、Z←FGをF上で計算する(1m)。
(10)計算機が、R←(X:Y:T:Z)、fを演算結果として出力する。
この加算アルゴリズムの総演算コストは1M+(k+14)m+1D、Z=1の場合、乗算を2回削減できて1M+(k+12)m+1Dとなる。
【0040】
次に、非特許文献1に開示されているIDベース公開鍵暗号方式について説明する。
IDベース公開鍵暗号方式を実現するシステムは、公開鍵の認証を行う認証局の代わりに、鍵生成センタを備える。鍵生成センタは、システムで共通に用いる公開パラメータを定め、各利用者が公開鍵として選択する任意のID(例えば、電子メールアドレス)に対して、鍵生成センタが外部にもれないよう厳重に保管するマスタ鍵を用いて公開鍵毎に秘密鍵を生成し、利用者に配布する。そして、鍵生成センタは、利用者が選択するID(公開鍵)と生成した秘密鍵とを対応づけて管理する。公開鍵の選定方法については、システム内でルール化しておく。
【0041】
IDベース公開鍵暗号方式は以下の4種類の処理より構成される。(1)、(2)は鍵生成センタでの処理であり、(3)は送信側端末の処理、(4)は受信側端末の処理である。
(1)公開パラメータおよびマスタ鍵生成処理:鍵生成センタに設置されている鍵発行装置が、システムで共通に用いる群やペアリングを含む公開パラメータの生成およびマスタ鍵の生成を行う。公開パラメータは、鍵生成センタによって外部に公開される。なお、システム全体の安全を確保するため、マスタ鍵は、システムの利用者を含む外部に漏洩しないよう、鍵生成センタによって厳重に保管される。
(2)秘密鍵生成処理:鍵発行装置が、利用者のメールアドレスなど、利用者と対応付けることのできる文字列(ID:公開鍵)毎に、マスタ鍵を用いて秘密鍵を生成する。この文字列が公開鍵となる。
(3)暗号化:送信側端末が鍵発行装置から公開パラメータや、送付先の公開鍵を取得し、取得した公開パラメータおよび送付先の公開鍵を用いて暗号化対象データの暗号化を行い、暗号化されたデータ(暗号化データ)を受信側端末へ送信する。
(4)復号:受信側端末が、鍵発行装置から公開パラメータおよび受信者の秘密鍵を取得し、公開パラメータおよび受信者の秘密鍵を用いて、送信側端末から送信された暗号化データを復号する。
【0042】
次に上記(1)から(4)の各処理における、入力、出力、および処理について説明する。
以下、{0,1}は全てのバイナリ系列を表し、{0,1}は全てのNビットバイナリ系列を表し、XORは排他的論理和を表す。
【0043】
(1)公開パラメータおよびマスタ鍵生成処理
入力情報:セキュリティパラメータである正整数L
出力情報:公開パラメータparams、マスタ鍵s
処理手順:
(1−1)鍵発行装置が、Lビットの素数nを生成する。
(1−2)鍵発行装置が、位数nの群G、G、Gを選択する。
(1−3)鍵発行装置が、ペアリングe:G×G→Gを選択する。
(1−4)鍵発行装置が、Gの生成元Pを選択する。
(1−5)鍵発行装置が、0<s<nを満たす整数sをランダムに選択しマスタ鍵とする。
(1−6)鍵発行装置が、楕円曲線スカラ倍演算を用いて、Ppub←sPを計算する。
(1−7)鍵発行装置が、ハッシュ関数H:{0,1}→Gを選択する。
(1−8)鍵発行装置が、ある整数Nに対して、ハッシュ関数H:G→{0,1}を選択する。
(1−9)鍵発行装置が、公開パラメータをparams=<n,G,G,G,e,N,P,Ppub,H,H>とする。
【0044】
(2)秘密鍵生成処理:
入力情報:公開パラメータparams、マスタ鍵s、公開鍵として用いる任意の文字列ID
出力情報:IDに対応する秘密鍵dID
処理手順:
(2−1)鍵発行装置が、任意のバイナリ列からなる集合に含まれる、与えられたID(ID∈{0,1})に対して、公開パラメータparamsに含まれているハッシュ関数Hを用いて、QID←H(ID)を計算する。
(2−2)鍵発行装置が、マスタ鍵sを用いてdID←sQIDを計算し、秘密鍵とする。
【0045】
(3)暗号化:
入力:暗号化対象データW、公開パラメータparams、公開鍵ID
出力:暗号化データC=(C,C
処理手順:
(3−1)送信側端末が、公開パラメータparamsに含まれているハッシュ関数Hを用いて、ハッシュ値QID←H(ID)を計算する。
(3−2)送信側端末が、0<r<nを満たす整数rをランダムに選択する。
(3−3)送信側端末が、楕円曲線スカラ倍演算を用いて、C←rPを計算する。
(3−4)送信側端末が、公開パラメータparamsに含まれているペアリングeを用いて、ペアリング演算を行い、g←e(Ppub,QID)を計算する。
(3−5)送信側端末が、公開パラメータparamsに含まれているハッシュ関数Hを用いて、ハッシュ値h←H(g)を計算する。
(3−6)送信側端末が、C←W XOR hを計算する。
(3−7)送信側端末が、C←(C,C)を暗号化データとする。
【0046】
(4)復号:
入力情報:暗号化データC=(C,C)、公開パラメータparams、秘密鍵dID
出力情報:復号データM
処理手順:
(4−1)受信側端末が、公開パラメータparamsに含まれているペアリングeを用いて、ペアリング演算を行い、g←e(C,dID)を計算する。
(4−2)受信側端末が、公開パラメータparamsに含まれているハッシュ関数Hを用いて、h←H(g)を計算する。
(4−3)受信側端末が、W←C XOR hを計算し復号データとする。
【先行技術文献】
【非特許文献】
【0047】
【非特許文献1】D. Boneh and M. Franklin. Identity based encryption from the Weil pairing SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003. Extended abstract in proc. of Crypto '2001, LNCS Vol. 2139, Springer-Verlag, pp. 213-229, 2001.
【非特許文献2】Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters,”Twisted Edwards curves.” In AFRICACRYPT 2008, volume 5023 of LNCS,p389-p405. Springer, 2008.
【非特許文献3】Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson,”Twisted Edwards Curves Revisited.” In ASIACRYPT 2008, volume 5350 of LNCS, p326-p343 Springer, 2008.
【非特許文献4】Christophe Arene, Tanja Lange, Michael Naehrig and Christophe Ritzenthaler, “Faster Computation of the Tate Pairing” Cryptology ePrint Archive: Report 2009/155, http://eprint.iacr.org/2009/155
【発明の概要】
【発明が解決しようとする課題】
【0048】
前記したIDベース暗号では、楕円曲線上のペアリング演算処理が必須である。しかし、ペアリング演算は暗号化および復号化処理において負荷が重いため処理性能に大きな影響を及ぼす事が知られている。
具体的には、ペアリング演算の処理性能は楕円曲線の定義体上の乗算および、2乗算、定数倍算の回数に依存する事が知られている。
また、ペアリング演算の際、Inverted Twisted Edward座標の適用可能性および係数a=−1に特化した計算方法については、非特許文献4において開示されていない。
【0049】
このような背景に鑑みて本発明がなされたのであり、本発明は、効率的なペアリング演算を行うことを目的とする。
【課題を解決するための手段】
【0050】
前記課題を解決するため、本発明は、Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現したTwisted Edward型楕円曲線上の素数位数の点である第1の点(Z=1)と、affine座標を用いて表現した第2の点とのペアリング演算を行うことを特徴とする。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【0051】
本発明によれば効率的な楕円曲線ペアリング演算を行うことができる。
【図面の簡単な説明】
【0052】
【図1】本実施形態に係る楕円曲線ペアリング演算装置の構成例を示す図である。
【図2】本実施形態に係る楕円曲線ペアリング演算部の構成例を示す図である。
【図3】本実施形態にかかる楕円曲線ペアリング演算処理の全体処理を説明するためのフローチャートである。
【図4】ステップS104における2倍算処理の手順を示すフローチャートである。
【図5】ステップS106において係数aが−1と異なる場合の加算処理の手順を示すフローチャートである。
【図6】ステップS106において係数aが−1の場合の加算処理の手順を示すフローチャートである。
【図7】本実施形態に係るIDベース暗号システムの構成例を示す図である。
【図8】本実施形態に係る鍵発行装置の構成例を示す図である。
【図9】本実施形態に係る鍵生成処理の手順を示すフローチャートである。
【図10】本実施形態に係る公開パラメータおよびマスタ鍵生成処理の手順を示すフローチャートである。
【図11】本実施形態に係る秘密鍵生成処理の手順を示すフローチャートである。
【図12】本実施形態に係る暗号化装置の構成例を示す図である。
【図13】本実施形態に係る暗号化処理の手順を示すフローチャートである。
【図14】本実施形態に係る復号化装置の構成例を示す図である。
【図15】本実施形態に係る復号化処理の手順を示すフローチャートである。
【図16】情報処理装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【0053】
次に、本発明を実施するための形態(「実施形態」という)について、適宜図面を参照しながら詳細に説明する。なお、本実施形態では、拡張Inverted twisted Edward座標を用いることで、楕円曲線スカラ倍演算における演算コストを低減することを目的とする。
【0054】
《楕円曲線ペアリング演算》
[楕円曲線ペアリング演算装置]
図1は、本実施形態に係る楕円曲線ペアリング演算装置の構成例を示す図である。
楕円曲線ペアリング演算装置1は、制御演算部110と、記憶部120を有している。
制御演算部110は、入出力部111と、制御部112と、楕円曲線ペアリング演算部113とを有する。入出力部111は、入力情報としての演算対象データおよび出力情報としての演算結果の入出力を行う機能を有する。制御部112は、楕円曲線ペアリング演算装置1全体を制御する機能を有する。楕円曲線ペアリング演算部113は、実際に楕円曲線上のペアリング演算を計算する機能を有する。
【0055】
記憶部120には、中間データ121、データ122などが格納されている。中間データ121は、必要に応じて処理中に生成されるデータである。データ122は、楕円曲線のパラメータなどのデータである。
【0056】
図2は、本実施形態に係る楕円曲線ペアリング演算部の構成例を示す図である。
楕円曲線ペアリング演算部113は、入出力部114と、楕円曲線加算演算部115と、楕円曲線2倍算演算部116と、基本演算部117とを有する。
楕円曲線加算演算部115は、楕円曲線上の2点の加算演算などを行う機能を有する。楕円曲線2倍算演算部116は、楕円曲線上の点の2倍算演算などを行う機能を有する。基本演算部117は、楕円曲線加算演算部115および楕円曲線2倍算演算部116から必要に応じて呼び出され楕円曲線の定義体上の演算や剰余計算(mod)を用いた四則演算などを行う機能を有する。
【0057】
なお、楕円曲線ペアリング演算装置1は、図16に示すような、バス67で接続されたCPU(Central Processing Unit)61と、RAM(Random Access Memory)などのメモリ62と、HDD(Hard Disk Drive)やその他の外部記憶装置65と、キーボードなどの入力装置63と、ディスプレイなどの出力装置64と、外部記憶装置65や、入力装置63や、出力装置64と、バス67とを中継するインタフェース66とを備えた、一般的な構成を有する情報処理装置6上に構築することができる。
楕円曲線ペアリング演算装置1の制御演算部110および各部111〜117は、CPU61が、メモリ62にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置6上に具現化される。また、メモリ62や、外部記憶装置65が図1の記憶部120として使用される。
【0058】
また、前記したプログラムは、予め外部記憶装置65に記憶され、必要に応じてメモリ62上にロードされ、CPU61により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROM(Compact Disk-Read Only Memory)などに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ62にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDDなどの外部記憶装置65にインストールされた後、必要に応じて、この外部記憶装置65からメモリ62にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置6が伝送信号により、一旦、外部記憶装置65にダウンロードされてからメモリ62にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ62にロードされてもよい。
【0059】
[楕円曲線ペアリング演算処理]
次に、図2を参照しつつ、図3〜図6に沿って楕円曲線ペアリング演算処理の手順を説明する。
2以外の素数のべきqに対して、素数nがq−1を割り切りかつ最小のkが偶数であるとする。この時、楕円曲線の定義体をF、位数nの部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(F)をax+y=1+dx(ad(a−d)≠0かつF上で係数aは2乗根を持ち係数dは持たない)、その位数(素数位数)nの部分群をGとする。
【0060】
のk次拡大体Fq1(q1=q:kは偶数)はFのk/2次拡大体Fq2(q2=qk/2)上の2次拡大体と見なすことができ、α=δ∈Fq2(q2=qk/2)を満たす基底{1,α}を用いることで、任意の元はx+yα(x,y∈Fq2:q2=qk/2)で表現することができる。
次にQを、(F)をFq1(q1=q)上の楕円曲線の点と見なし、E(Fq1)(q1=q)上の位数nの元でAffine座標を用いてQ=(xα,y)(x、y∈Fq2:q2=qk/2)と表現できるものとする。この時、Qの属する位数nの部分群をGとし、Fq1(q1=q)の乗法に関する位数nの部分群をGとする。
【0061】
以上の前提で、本実施形態に係る楕円曲線ペアリング演算の全体概要を説明すると、入出力部111により入力を受け付けた3つの群G、G、G、拡張Inverted twisted Edward座標を用いて表現したGの点(第1の点)P=(X:Y:T:Z)∈G、Affine座標を用いて表現したGの点(第2の点)Q=(xα,y)(x,y∈Fq2:q2=qk/2)、点PおよびQの位数n(n≧3)の各入力情報は、記憶部120に保持される。
【0062】
ここで、拡張Inverted twisted Edward座標とは、楕円曲線上の点(x,y)をx=Z/X、y=Z/Y、XYZ≠0を満たすX,Y,Zを用いて変換したInverted Twisted Edward座標(X:Y:Z)に対して、xy=T/Zを満たす座標Tを加えて(X:Y:T:Z)とした座標である。
そして、制御演算部110が、記憶部120で保持されている各入力情報を用いて、図3〜図6に示すペアリング演算処理を行い、演算結果(第1の元)f=e(P,Q)∈Gを求め、出力する。
【0063】
(全体処理)
図3は、本実施形態に係る楕円曲線ペアリング演算処理の全体処理を説明するためのフローチャートである。
ステップS101において、基本演算部117が、Pの位数である素数nを2進数展開して、n=n+n×2+・・・+nt−1×2t−1 (nt−1=1)とする。
ステップS102において、基本演算部117が、η←(1+y)/(xδ)とおく。
ステップS103において、基本演算部117が、f←1(単位元)、i←t−2、R(第3の点)←Pとおく。
ステップS104において、楕円曲線2倍算演算部116が、f←fR,R(Q)、R←2Rを、を計算する(2倍算処理)。ステップS104の計算方法は図4を参照して後記する。gR,R(Q)については、図4のステップS206において後記する。
【0064】
ステップS105において、基本演算部117が、n=1であるか否かを判定し、n=1であれば(S105→Yes)、ステップS106の処理に進み、n=1でなければ(S105→No)、ステップS107の処理に進む。
ステップS106において、楕円曲線加算演算部115が、f←fgR,P(Q)、R←R+Pを計算する(加算処理)。ステップS106の計算方法は、係数aが−1以外の場合は図5を参照して後記し、係数aが−1の場合は図6を参照して後記する。gR,P(Q)については、図5のステップS306、図6のステップS406で後記する。
ステップS107において、基本演算部117が、i←i−1を計算する。
ステップS108において、基本演算部117が、i≧0であるか否かを判定し、i≧0であれば(S108→Yes)、ステップS104の処理に戻り、i≧0でなければ(S108→No)、ステップS109の処理に進む。
ステップS109において、基本演算部117が、fのべき乗f←f(q1−1)/n(q1=q)を計算しfを演算結果とする。
【0065】
(2倍算処理)
次に、図2を参照しつつ、図4に沿って図3のステップS104における2倍算処理について説明する。なお、これ以降、各処理の最後に記述してあるm,s,Dは、それぞれ定義体F上の乗算、2乗算、定数倍算の演算コスト、M,Sは、それぞれFのk次拡大体Fq1(q1=q)上の乗算、2乗算の演算コストを示す。ただし、定義体F上の2倍算については、より演算コストの小さい加算もしくは1ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
【0066】
図4は、図3のステップS104における2倍算処理の手順を示すフローチャートである。
なお、図4において、入力時におけるRの座標は(X:Y:T:Z)であるとする。
ステップS201において、楕円曲線2倍算演算部116が、A←X、B←Y、C←T、D←aB、E←aYをF上でそれぞれ計算する(1m,3s,2D)。ここでa=−1である場合、D←aBおよびE←aYはF上でBの符号を反転することにより定数倍算を用いないで計算できるため、演算コストを2D削減することができる。
【0067】
ステップS202において、楕円曲線2倍算演算部116が、F←A+D、G←A−D、H←(X+Y−A−B、I←(X+T−A−C、J←(2C−F)をF上でそれぞれ計算する(2s)。
ステップS203において、楕円曲線2倍算演算部116が、cZZ←2X(Y−Z)をF上で計算する(1m)。
ステップS204において、楕円曲線2倍算演算部116が、cXY←2(F−C)−IをF上で計算する。
ステップS205において、楕円曲線2倍算演算部116が、cXZ←2(A−E)をF上で計算する。
【0068】
ステップS206において、楕円曲線2倍算演算部116が、gR,R(Q)←cZZηα+cXY+cXZをFのk/2次拡大体Fq2(q2=qk/2)上で計算する(km)。
【0069】
ステップS207において、楕円曲線2倍算演算部116が、f←fR,R(Q)をFのk次拡大体Fq1(q1=q)上で計算する(1M,1S)。
ステップS208において、楕円曲線2倍算演算部116が、X←FGをF上で計算する(1m)。
ステップS209において、楕円曲線2倍算演算部116が、Y←HJをF上で計算する(1m)。
ステップS210において、楕円曲線2倍算演算部116が、T←FJをF上で計算する(1m)。
ステップS211において、楕円曲線2倍算演算部116が、Z←GHをF上で計算する(1m)。
ステップS212において、楕円曲線2倍算演算部116が、2倍算の演算結果を拡張Inverted twisted Edward座標を用いてR←(X:Y:T:Z)とおき、fとともに、演算結果として出力する。
この2倍算の総演算コストは、1M+1S+(k+6)m+5s+2Dとなる。
またa=−1である場合、1M+1S+(k+6)m+5sとなる。
【0070】
ここで、図4の処理について詳細に説明する。
まず、非特許文献2に基づくInverted twisted Edward座標(X:Y:Z)を用いた(X:Y:Z)=2(X:Y:Z)を計算する2倍算は以下の式(4)〜(6)で計算できる。
【0071】
=(X+aY)(X−aY)・・・(4)
=2X(X+aY−2dZ)・・・(5)
=2X(X−aY)・・・(6)
【0072】
次に、この非特許文献2に記載の2倍算計算方法を本実施形態による、すなわち拡張Inverted twisted Edward座標を用いるペアリング演算手段に適するよう変形する。
つまり、上記のInverted twisted Edward座標(X:Y:Z)に加えて1/(x)=Z/Tを満たすT座標を求める必要がある。
ここで、Tは以下の条件(式(7))を満たす。
【0073】
【数5】

【0074】
さらに、変形して、式(8)を得る。
【0075】
【数6】

【0076】
以上より、Tは、式(9)とおける。
【0077】
=(X+aY)(X+aY−2dZ)・・・(9)
【0078】
次に楕円曲線ax+y=1+dxをx=Z/X、y=Z/Yを用いて変換すると、式(10)を得る。
【0079】
(X+aY)Z=X+dZ・・・(10)
【0080】
で両辺を割ることによって、式(11)とおける。
【0081】
【数7】

【0082】
=Tを用いることで式(12)を得る。
【0083】
2dZ=2(X+aY−T)・・・(12)
【0084】
式(12)を式(5)に代入することによりYが求まる。
【0085】
=2X(2T−X−aY)・・・(13)
【0086】
式(12)を式(9)に代入することによりTが求まる。
【0087】
=(X+aY)(2T−X−aY)・・・(14)
【0088】
次に非特許文献4に基づくと、gR,R(Q)は式(15)で表すことができる。
【0089】
R,R(Q)=c0ZZηα+c0XY+c0XZ・・・(15)
【0090】
射影座標を用いてR=(X:Y:Z)とした場合、式(15)の係数c0ZZ、c0XY、c0XZは以下の式(16)〜(18)で求められる。
【0091】
0ZZ=X(Z−Y)・・・(16)
0XY=dX−Z・・・(17)
0XZ=Z(Z−aX)・・・(18)
【0092】
Rの各座標はすべてFの元であるため、Fの元をgR,R(Q)全体に乗算したとしても、あるいはFの元でgR,R(Q)全体を割った結果を、新たにgR,R(Q)とおきなおして計算したとしても、乗算または除算に用いたFの元は最後に行うfのべき乗の過程で単位元となるためペアリングの演算結果には影響しない。また、Rの各座標は全てFの元であるため、これらの座標でgR,P(Q)全体に乗算する、または座標gR,R(Q)全体をすることで、gR,R(Q)の係数を、拡張射影座標を用いる表現からAffine座標を用いる表現に変換し、その後Affine座標を用いる表現から拡張Inverted twisted Edward座標を用いる表現へと変換することでgR,R(Q)を得る。
【0093】
R,R(Q)全体をZで割ることによって式(16)より式(19)を得る。
【0094】
【数8】

【0095】
=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)に変換することによって式(20)を得る。
【0096】
ZZ=x(1−y)・・・(20)
【0097】
さらに、x=Z/X、y=Z/Y、x=Z/Tを満たす拡張Inverted twisted Edward座標(X:Y:T:Z)を用いて変換することで式(21)を得る。
【0098】
【数9】

【0099】
式(17)をZで割ることによって式(22)を得る。
【0100】
【数10】

【0101】
=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)変換することによって式(23)を得る。
【0102】
XY=dx−1・・・(23)
【0103】
さらに、x=Z/X、y=Z/Y、x=Z/Tを満たす拡張Inverted twisted Edward座標(X:Y:T:Z)を用いて変換することで式(24)を得る。
【0104】
【数11】

【0105】
同様に式(18)をZで割ることによって式(25)を得る。
【0106】
【数12】

【0107】
=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)変換することによって式(26)を得る。
【0108】
XY=y−ax・・・(26)
【0109】
さらに、x=Z/X、y=Z/Y、x=Z/Tを満たす拡張Inverted twisted Edward座標(X:Y:T:Z)を用いて変換することで式(27)を得る。
【0110】
【数13】

【0111】
R,R(Q)全体に2Xを掛けることでcZZ←2XZZを計算し、式(28)を得る。
【0112】
ZZ=2X(Y−Z)・・・(28)
【0113】
R,R(Q)全体に2Xを掛けることでcXY←2XXYを計算し式(29)を得る。
【0114】
XY=2dZ−2X・・・(29)
【0115】
=Tを用いて変形することで式(30)を得る。
【0116】
XY=2dZ−2X=Z(2dZ−2X)・・・(30)
【0117】
さらに、式(12)を用いることで式(31)を得る。
【0118】
XY=Z(2(X+aY−T)2X)・・・(31)
【0119】
R,R(Q)全体に2Xを掛けることでCの係数cXZ←2XXZを計算し式(32)を得る。
【0120】
XZ=2X−2aY・・・(32)
【0121】
最後にgR,R(Q)全体をZで割ることによって、Cの係数cZZ←cZZ/Z、cXY←cXY/Z、cXZ←cXZ/Zを計算することで式(33)〜(35)を得る。
【0122】
ZZ=2X(Y−Z)・・・(33)
XY=2(X+aY−T)−2X・・・(34)
XZ=2(X−aY)・・・(35)
【0123】
以上をアルゴリズムの形でまとめると、図4で示す手順となる。
【0124】
(加算処理)
次に、図2を参照しつつ、図5および図6に沿って図3のステップS106における処理を説明する。
図5は、図3のステップS106において係数aが−1以外の場合の加算処理の手順を示すフローチャートである。
なお、図5において、入力時のPの座標は(X:Y:T:Z)、Rの座標は(X:Y:T:Z)であるとする。
ステップS301において、楕円曲線加算演算部115が、A←X、B←Y、C←T、D←TをF上でそれぞれ計算する(4m)。
ここでZ=1である場合、C←TはC←Tとなり、乗算の必要がなくなるため、演算コストを1m削減することができる。
ステップS302において、楕円曲線加算演算部115が、E←(X+Y)(X−Y)+B−A、F←C+D、G←C−D、H←A+aB、I←TをF上でそれぞれ計算する(2m,1D)。
ステップS303において、楕円曲線加算演算部115が、cZZ←Y−YをF上で計算する(2m)。
ここでZ=1である場合、cZZ←Y−Yとなり、1回分の乗算の必要がなくなるため、演算コストを1m削減することができる。
【0125】
ステップS304において、楕円曲線加算演算部115が、cXY←(Y−T)(Y+T)−B+I+EをF上で計算する(1m)。
ステップS305において、楕円曲線加算演算部115が、cXZ←D−C+(X+X)をF上で計算する(2m)。
ここでZ=1である場合、cXZ←D−C+(X+X)となり、1回分の乗算の必要がなくなるため、演算コストを1m削減することができる。
【0126】
ステップS306において、gR,P(Q)←cZZηα+cXY+cXZをFのk/2次拡大体Fq2(q2=qk/2)上で計算する(km)。
【0127】
ステップS307において、f←fgR,P(Q)をFのk次拡大体Fq1(q1=q)上で計算する(1M)。
【0128】
ステップS308において、楕円曲線加算演算部115が、i=0であるか否かを判定し、i=0であれば(S308→Yes)、ステップS314の処理に進み、そうでなければ(S308→No)、ステップS309に進む。
ステップS309において、楕円曲線加算演算部115が、X←HGをF上で計算する(1m)。
ステップS310において、楕円曲線加算演算部115が、Y←EFをF上で計算する(1m)。
ステップS311において、楕円曲線加算演算部115が、T←HEをF上で計算する(1m)。
ステップS312において、楕円曲線加算演算部115が、Z←FGをF上で計算する(1m)
【0129】
ステップS313において、楕円曲線加算演算部115が、演算結果をInverted twisted Edward座標を用いてR←(X:Y:T:Z)としfとともに出力し、加算処理を終了する。
ステップS314では、楕円曲線加算演算部115が、演算結果をfとして出力し、加算処理を終了する。
図5に示す加算アルゴリズムの総演算コストは1M+(k+15)m+1D、Z=1の場合、1M+(k+12)m+1Dとなる。なお、通常はZ=1が用いられる。
【0130】
ここで、図5の処理の詳細について説明する。
非特許文献3に基づく加算公式によるとTwisted Edward型楕円曲線上の2点P=(x,y)、Q=(x,y)に対して係数dを用いない加算P+Q=(x,y)は以下の式(36)で計算することができる。
【0131】
この式(36)より、図5に示す加算アルゴリズムを導く。
【0132】
【数14】

【0133】
2点P=(x,y)、Q=(x,y)と拡張Inverted twisted Edward座標を用いて表現したP=(X:Y:T:Z)、Q=(X:Y:T:Z)は以下の関係を満たす。
【0134】
= Z/X、y=Z/Y、x= Z/T、x= Z/X、y=Z/Y、x= Z/T
【0135】
これらの関係式を、式(36)に代入することによって、加算公式(式(36))を変形し、式(37)を得る。
【0136】
【数15】

【0137】
次に、以下の式(38)より式(39)が導かれる。
【0138】
【数16】

【0139】
=Z・・・(39)
【0140】
この式(39)を式(37)に代入して、変形すると、以下の式(40)を得る。
【0141】
【数17】

【0142】
最終的にP+Qは以下の式(41)を計算することで求められる。
【0143】
【数18】

【0144】
式(39)より、x=Z/X、y=Z/Y、x=Z/Tを満たすX、Y、T、Zをそれぞれ求めると、以下の式(42)〜(45)を得る。
【0145】
=(X+aY)(Z−T)・・・(42)
=(Y−X)(Z+T)・・・(43)
=(X+aY)(Y−X)・・・(44)
=(Z+T)(Z−T)・・・(45)
【0146】
式(42)〜(45)を用いることでP+R=(X:Y:T:Z)+(X:Y:T:Z)=(X:Y:T:Z)を計算することができる。
実際にx=Z/X、y=Z/Y、x=Z/Tを満たしていることは以下の式(46)〜(48)で確認できる。
【0147】
【数19】

【0148】
次に非特許文献4に基づくと、gR,P(Q)は式(49)で表すことができる。
【0149】
R,P(Q)=c0ZZηα+c0XY+c0XZ・・・(49)
【0150】
拡張射影座標を用いてP=(X:Y:T:Z)、R=(X:Y:T:Z)とした場合、式(47)の係数c0ZZ、c0XY、c0XZは以下の式(50)〜(52)で求められる。
【0151】
0ZZ=X(Y−Y)・・・(50)
0XY=Z(X−X+X−X)・・・(51)
0XZ=X−X+Y(X−X)・・・(52)
【0152】
PおよびRの各座標は全てFの元であるため、Fの元をgR,P(Q)全体に乗算したとしても、あるいはFの元でgR,P(Q)全体を割った結果を、新たにgR,P(Q)とおきなおして計算したとしても、乗算または除算に用いたFの元は最後に行うfのべき乗の過程で単位元となるためペアリングの演算結果には影響しない。また、PおよびRの各座標は全てFの元であるため、これらの座標でgR,P(Q)全体に乗算する、または座標gR,P(Q)全体をすることで、gR,P(Q)の係数を、拡張射影座標を用いる表現からAffine座標を用いる表現に変換し、その後Affine座標を用いる表現から拡張Inverted twisted Edward座標を用いる表現へと変換することで図5に示すgR,P(Q)を得る。
【0153】
R,P(Q)全体をZで割ることによって式(50)より式(53)を得る。
【0154】
【数20】

【0155】
=X/Z、y=Y/Z、x=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)および(x,y)に変換することによって式(54)を得る。
【0156】
ZZ=x(y−y)・・・(54)
【0157】
=Z/X、y=Z/Y、x=Z/T、x=Z/X、y=Z/Y、x=Z/Tを満たすInverted twisted Edward座標(X:Y:T:Z)および(X:Y:T:Z)を用いて変換することで式(55)を得る。
【0158】
【数21】

【0159】
R,P(Q)全体をZで割ることによって式(51)より式(56)を得る。
【0160】
【数22】

【0161】
=X/Z、y=Y/Z、x=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)および(x,y)に変換することで式(57)を得る。
【0162】
XY=x−x+x−x・・・(57)
【0163】
=Z/X、y=Z/Y、x=Z/T、x=Z/X、y=Z/Y、x=Z/Tを満たすInverted twisted Edward座標(X:Y:T:Z)および(X:Y:T:Z)を用いて変換することで式(58)を得る。
【0164】
【数23】

【0165】
R,P(Q)全体をZで割ることによって式(52)より式(59)を得る。
【0166】
【数24】

【0167】
=X/Z、y=Y/Z、x=X/Z、y=Y/Zを用いて射影座標をAffine座標(x,y)および(x,y)に変換することで式(60)を得る。
【0168】
XZ=x−x+y(x−x)・・・(60)
【0169】
=Z/X、y=Z/Y、x=Z/T、x=Z/X、y=Z/Y、x=Z/Tを満たすInverted twisted Edward座標(X:Y:T:Z)および(X:Y:T:Z)を用いて変換することで式(61)が得られる。
【0170】
【数25】

【0171】
R,P(Q)全体にXを掛けることによって式(55)より式(62)を得る。
【0172】
ZZ←XZZ=Z(Y−Y)・・・(62)
【0173】
R,P(Q)全体にXを掛けることによって式(58)より式(63)を得る。
【0174】
XY←XXY=Y−X+Z(X−X)・・・(63)
【0175】
さらに、X=T、X=Tを用いて変形することで式(64)を得る。
【0176】
XY=Z(Y−Y+X−X)・・・(64)
【0177】
R,P(Q)全体にXを掛けることによって式(59)より式(65)を得る。
【0178】
XZ←XXZ=X−X+Z(X−X)・・・(65)
【0179】
さらに、T=X、T=Xを用いて変形することで式(66)を得る。
【0180】
XZ=Z(T−T+X−X)・・・(66)
【0181】
R,P(Q)全体をZで割、cZZ←cZZ/(Z)、cXY←cXY/(Z)、cXZ←cXZ/(Z)を計算することにより式(67)〜(69)を得る。
【0182】
ZZ=Y−Y・・・(67)
XY=Y−Y+X−X・・・(68)
XZ=T−T+X−X・・・(69)
【0183】
上記の内容をアルゴリズムの形でまとめると、図5に示す処理手順となる。
【0184】
図6は、図3のステップS106において係数aが−1の場合の加算処理の手順を示すフローチャートである。
なお、図6において、入力時におけるPの座標は(X:Y:T:Z)、Rの座標は(X:Y:T:Z)であるとする。
ステップS401において、楕円曲線加算演算部115が、A←(X−Y)(X+Y)、B←(X+Y)(X−Y)、C←2T、D←2TをF上でそれぞれ計算する(4m)。
ここでZ=1である場合、C←2TはC←2Tとなり、乗算の必要がなくなるため、演算コストを1m削減することができる。
ステップS402において、楕円曲線加算演算部115が、E←A+B、F←C+D,G←C−D,H←B−AをF上でそれぞれ計算する。
ステップS403において、楕円曲線加算演算部115が、cZZ←2(Y−Y)をF上で計算する(2m)。
ここでZ=1である場合、cZZ←2(Y−Y)となり、1回分の乗算の必要がなくなるため、演算コストを1m削減することができる。
【0185】
ステップS404において、楕円曲線加算演算部115が、cXY←2(Y−Y)+HをF上で計算する(2m)。
ステップS405において、楕円曲線加算演算部115が、cXZ←D−C+2(X−X)をF上で計算する(2m)。
ここでZ=1である場合、cXZ←D−C+2(X−X)となり、1回分の乗算の必要がなくなるため、演算コストを1m削減することができる。
ステップS406において、楕円曲線加算演算部115が、gR,P(Q)←cZZηα+cXY+cXZをFのk/2次拡大体Fq2(q2=qk/2)上で計算する(km)。
ステップS407において、楕円曲線加算演算部115が、f←fgR,P(Q)をFのk次拡大体Fq1(q1=q)上で計算する(1M)。
【0186】
ステップS408において、楕円曲線加算演算部115が、i=0であるか否かを判定し、i=0であれば(S408→Yes)、ステップS414の処理に進み、そうでなければ(S408→No)、ステップS409に進む。
ステップS409において、楕円曲線加算演算部115が、X←EGをF上で計算する(1m)。
ステップS410において、楕円曲線加算演算部115が、Y←HFをF上で計算する(1m)。
ステップS411において、楕円曲線加算演算部115が、T←EHをF上で計算する(1m)。
ステップS412において、楕円曲線加算演算部115が、Z←FGをF上で計算する(1m)。
ステップS413において、楕円曲線加算演算部115が、演算結果をInverted twisted Edward座標を用いたR←(X:Y:T:Z)としてfとともに出力し、加算処理を終了する。
ステップS414では、楕円曲線加算演算部115が、演算結果をfとして出力し、加算処理を終了する。
図6に示す加算アルゴリズムの演算コストは1M+(k+14)m(Z=1以外)、1M+(k+11)m(Z=1)となる。この処理における演算コストは、非特許文献4において該当するコストより、1m+1D減っている。非特許文献4に記載の技術にa=−1を適用した場合と比べても1m減っている。
【0187】
ここで、図6に示す処理について詳細に説明する。
ここでは、図5に示す加算方法を変形することにより、図6に示す加算アルゴリズムを導く。
図5における加算方法(式(42)〜(45))に対して、a=−1を代入することにより以下の式(70)〜(73)が得られる。
【0188】
=(X+aY)(Z−T)・・・(42)
=(Y−X)(Z+T)・・・(43)
=(X+aY)(Y−X)・・・(44)
=(Z+T)(Z−T)・・・(45)
【0189】
=(X−Y)(Z−T)・・・(70)
=(Y−X)(Z+T)・・・(71)
=(X−Y)(Y−X)・・・(72)
=(Z+T)(Z−T)・・・(73)
【0190】
式(70)〜(73)を用いることによりP+R=(X:Y:T:Z)+(X:Y:T:Z)=(X:Y:T:Z)を計算することができ、(X:Y:T:Z)の代わりに(X:Y:T:Z)=(4X:4Y:4T:4Z)を用いてもx=Z/X、y=Z/Y、x=Z/Tを満たすことから、以下の式(74)〜(77)を用いることによりP+Q=(X:Y:T:Z)+(X:Y:T:Z)=(X:Y:T:Z)を計算できる。
【0191】
=(2X−2Y)(2Z−2T)・・・(74)
=(2Y−2X)(2Z+2T)・・・(75)
=(2X−2Y)(2Y−2X)・・・(76)
=(2Z+2T)(2Z−2T)・・・(77)
【0192】
ここで、X、Y、Z座標を求める際に必要となる式は以下の条件(式(78),(79))を満たす。
【0193】
(2X−2Y)=(X−Y)(X+Y)+(X+Y)(X−Y)・・・(78)
(2Y−2X)=(X+Y)(X−Y)−(X−Y)(X+Y)・・・(79)
【0194】
次にgR,P(Q)について説明する。
図5におけるgR,P(Q)の式(67)から(69)で表される係数を2倍し、cZZ←2cZZ、cXY←2cXY、cXZ←2cXZを計算することにより式(80)〜(82)を得る。
【0195】
ZZ=Y−Y・・・(67)
XY=Y−Y+X−X・・・(68)
XZ=T−T+X−X・・・(69)
【0196】
ZZ=2(Y−Y)・・・(80)
XY=2(Y−Y)+2X−2X・・・(81)
XZ=2T−2T+2(X−X)・・・(82)
【0197】
上記の内容をアルゴリズムの形でまとめると、図6に示す処理手順となる。
【0198】
ここで、a=−1の場合の加算処理において、1m分、乗算コストが削減できる理由を、削減に影響する箇所のみを取り出して説明する。
【0199】
aが−1以外の場合、加算は以下の方法で求まる。まず、前記した式(42)〜(45)をみてみる。
【0200】
=(X+aY)(Z−T)・・・(42)
=(Y−X)(Z+T)・・・(43)
=(X+aY)(Y−X)・・・(44)
=(Z+T)(Z−T)・・・(45)
【0201】
上記の式の内、乗算の削減に影響するのはE=Y−X、H=X+aYであり、これら2つの式を求める部分で以下の方法が適用できる。
【0202】
A←X、B←Y、E←(X+Y)(X−Y)+B−A、H←A+aB
【0203】
この場合の計算コストは3m+1D、a=−1であればH←A−Bとなり1Dの削減が可能となり計算コストは3mとなる。
【0204】
次にa=−1の場合、aが−1以外の場合の加算結果(X:Y:T:Z)を求める代わりに(4X:4Y:4T:4Z)を加算結果とするようにアルゴリズムを修正する。
具体的には(42)〜(43)式にa=−1を代入し全体を4倍した以下の式(74)〜(77)で求めることができる。
【0205】
=(2X−2Y)(2Z−2T)・・・(74)
=(2Y−2X)(2Z+2T)・・・(75)
=(2X−2Y)(2Y−2X)・・・(76)
=(2Z+2T)(2Z−2T)・・・(77)
【0206】
aが−1以外の場合のEに相当するE=2Y−2X、Hに相当するH=2X−Yは以下の方法で求めることができる。
【0207】
A←(X−Y)(X+Y)、B←(X+Y)(X−Y)、E←A+B、H←B−A
【0208】
この場合の計算コストは2mとなりaが−1以外の場合に比べて1m+1Dの計算コストを削減できる。
【0209】
ここで、本実施形態の効果について説明する。非特許文献4に開示されている拡張射影座標を用いて表現した点P=(X:Y:T:Z)(Z≠1)を用いてReduced Tateペアリングを計算したときにおいて、m,s,Dを、それぞれ定義体F上の乗算、2乗算、定数倍算の演算コストとし、M,Sを、それぞれFのk次拡大体Fq1(q1=q)上の乗算、2乗算の演算コストとした場合、ループ処理で計算される加算処理の演算コストは1M+(k+14)m+1D、2倍算処理の演算コストは1M+1S+(k+6)m+5s+2Dとなる。
【0210】
本実施形態における拡張Inverted Twisted Edward座標を用いて表現した点P=(X:Y:T:Z)(Z≠1)を用いてReduced Tateペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは1M+(k+15)m+1D、2倍算処理の演算コストは1M+1S+(k+6)m+5s+2Dとなる。
【0211】
非特許文献4に開示されている拡張射影座標を用いて表現した点P=(X:Y:T:Z)(Z=1)を用いてReduced Tateペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは1M+(k+12)m+1D、2倍算処理の演算コストは1M+1S+(k+6)m+5s+2Dとなる。
本実施形態における拡張Inverted Twisted Edward座標を用いて表現した点P=(X:Y:T:Z)(Z=1)を用いてReduced Tateペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは1M+(k+12)m+1D、2倍算処理の演算コストは1M+1S+(k+6)m+5s+2Dとなり、非特許文献4に開示されている計算方法と同等の演算コストとなる。
加算ステップにおけるPのZ座標を1にすることは実用上問題が無いため、Z=1とすることにより非特許文献4に開示されている計算方法と同等の演算速度を実現できる。
【0212】
さらに、楕円曲線の係数aを−1とすることにより本実施形態における加算ステップの演算コストは1M+(k+11)m、2倍算処理の演算コストは1M+1S+(k+6)m+5sとなり、非特許文献4に開示されている計算方法に比べて、加算処理において1m+D、2倍算ステップにおいて2Dの演算コストを削減できる。
【0213】
すなわち、本実施形態によれば、非特許文献4に記載の技術に比べてペアリング演算時の演算コストを削減できるためスカラ倍演算コストをより高速化することができる。これにより高速なIDベース暗号など楕円曲線上で定義されるペアリングの性質を用い、任意の文字列を公開鍵として用いることのできる署名方式や公開鍵暗号の実現が可能となる。
【0214】
《IDベース暗号システム》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用したIDベース暗号システムについて図7〜図15を参照して説明する。
【0215】
図7は、本実施形態に係る楕円曲線ペアリング演算方法を利用したIDベース暗号システムの構成例を示す図である。
図7に示すように、本実施形態のIDベース暗号システム2は、鍵生成センタに設置されている鍵発行装置3と、暗号化装置4と、復号化装置5とを備える。鍵発行装置3、暗号化装置4および復号化装置5のそれぞれは、ネットワーク201により接続されている。以下、暗号化装置4の利用者を利用者A、復号化装置5の利用者を利用者Bとする。両者を区別する必要がない場合は、利用者と呼ぶ。
【0216】
これらの各装置を用いた本実施形態での暗号化および復号化処理の概略について説明する。本実施形態では、公開鍵として、所定のルールによって定められた利用者と対応付けられるID、例えば電子メールアドレスなどを用いるものとする。
まず、鍵発行装置3において、IDベース暗号システム2全体で用いる公開パラメータおよびマスタ鍵を生成し、生成した公開パラメータを公開する。
暗号化したメッセージを送信する場合、暗号化装置4において、鍵発行装置3から取得した送信相手の公開鍵(利用者BのID)および公開パラメータを用いて暗号化対象データを暗号化することによって暗号化データを生成し、生成した暗号化データを送出する。復号化装置5では、予め、鍵発行装置3に自身の公開鍵に対応する秘密鍵の発行を依頼し、その秘密鍵および公開パラメータを用いて、暗号化装置4から受け取った暗号化データを復号する。
【0217】
《鍵生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用した鍵生成方法について図8から図11を参照して説明する。
【0218】
[鍵発行装置]
図8は、本実施形態に係る鍵発行装置の構成例を示す図である。
鍵発行装置3は、制御演算部310および記憶部320を有している。
制御演算部310は、入出力部311、制御部312、群選択部313、乱数生成部314、楕円曲線スカラ倍演算部315、ハッシュ関数選択部316、ハッシュ関数演算部317を有している。入出力部311は、公開パラメータおよびマスタ鍵生成処理または秘密鍵生成処理のいずれの処理を実行するかの処理選択情報や、公開パラメータおよびマスタ鍵生成処理時のセキュリティパラメータや、秘密鍵生成処理時の利用者の公開鍵などを入力情報として受け付けるとともに、生成された公開パラメータまたは秘密鍵を出力情報として出力する機能を有している。制御部312は、鍵発行装置3を制御する機能を有している。群選択部313は、群を選択する機能を有する。乱数生成部314は、乱数を生成する機能を有する。楕円曲線スカラ倍演算部315は、楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算(mod)、比較などを行う機能を有する。ハッシュ関数選択部316は、ハッシュ関数を選択する機能を有する。ハッシュ関数演算部317は、ハッシュ関数選択部316で選択されたハッシュ関数を用いてハッシュ値を生成する機能を有する。
【0219】
記憶部320には、中間データ321、セキュリティパラメータ322、公開パラメータ323、マスタ鍵324、公開鍵325、秘密鍵326などが格納されている。中間データ321は、制御演算部310における演算時の中間データである。セキュリティパラメータ322は、入出力部311により入力を受け付けたセキュリティパラメータのデータである。公開パラメータ323は、制御演算部310で生成された公開パラメータのデータである。マスタ鍵324は、制御演算部310で生成されたマスタ鍵のデータである。公開鍵325は、入出力部311により入力を受け付けた公開鍵のデータである。秘密鍵326は、制御演算部310で生成された秘密鍵のデータである。
【0220】
なお、鍵発行装置3は、図16に示すような、バス67で接続されたCPU61と、RAMなどのメモリ62と、HDDやその他の外部記憶装置65と、キーボードなどの入力装置63と、ディスプレイなどの出力装置64と、外部記憶装置65や、入力装置63や、出力装置64と、バス67とを中継するインタフェース66とを備えた、一般的な構成を有する情報処理装置6上に構築することができる。
鍵発行装置3の制御演算部310および各部311〜320は、CPU61が、メモリ62にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置6上に具現化されるプロセスとして実現される。また、メモリ62や、外部記憶装置65が図8の記憶部320として使用される。
【0221】
また、前記したプログラムは、予め外部記憶装置65に記憶され、必要に応じてメモリ62上にロードされ、CPU61により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ62にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDDなどの外部記憶装置65にインストールされた後、必要に応じて、この外部記憶装置65からメモリ62にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置6が伝送信号により、一旦外部記憶装置65にダウンロードされてからメモリ62にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ62にロードされてもよい。
【0222】
[鍵生成処理]
図9は、本実施形態に係る鍵生成処理の手順を示すフローチャートである。鍵の生成はIDベース暗号システム2全体で用いる公開パラメータおよびマスタ鍵を生成する公開パラメータおよびマスタ鍵生成処理と利用者の秘密鍵を生成する秘密鍵生成処理と、から構成される。
【0223】
図8を参照しつつ、鍵生成処理の概略を記述すると、入出力部311により、鍵発行装置3が、入力情報として、公開パラメータおよびマスタ鍵生成処理を行うか、または秘密鍵生成処理を行うかの処理選択情報と、公開パラメータおよびマスタ鍵生成処理であればセキュリティパラメータ322である正整数L、秘密鍵生成処理であれば、公開鍵である任意の文字列を入力情報として受け付けると、制御演算部310は受け付けた入力情報を記憶部320に格納する。
そして、制御演算部310が、記憶部320に保持されている入力情報を参照し、選択された処理が公開パラメータおよびマスタ鍵生成処理であれば図10の処理に従って公開パラメータ323およびマスタ鍵324を生成する。そして、制御演算部310は公開パラメータ323およびマスタ鍵324を記憶部320に格納とするとともに公開パラメータのみ入出力部311より出力情報として出力し動作を終了する。制御演算部310は、秘密鍵生成処理であれば図11の処理に従って秘密鍵326を生成し、制御演算部310は生成した秘密鍵326を記憶部320に格納とするとともに入出力部311より出力情報として出力し動作を終了する。
まず、図8を参照しつつ、図9に沿って、鍵発行装置3における全体処理を説明する。
【0224】
ステップS501において、制御演算部310による制御の元、入出力部311が処理の選択を受け付ける。公開パラメータおよびマスタ鍵生成処理が選択された場合、制御演算部310はセキュリティパラメータ322である正整数Lの入力を受け付けるとともにLを必要に応じて記憶部320に格納後、ステップS502に進む。秘密鍵生成処理が選択された場合、制御演算部310は利用者の公開鍵である任意の文字列IDの入力を受け付けるとともに、このIDを必要に応じて記憶部320に格納後、ステップS503に進む。
ステップS502において、制御演算部310は公開パラメータおよびマスタ鍵生成処理を行った後、処理を終了する。ステップS502の処理については、図10を用いて後述する。
ステップS503において、制御演算部310は秘密鍵生成処理を行った後、処理を終了する。ステップS503の処理については、図11を用いて後述する。
なお、以降の処理において、{0,1}はすべてのバイナリ系列を表し、{0,1}はすべてのNビットバイナリ系列を表し、XORは排他的論理和を表す。
【0225】
以下、図8を参照しつつ、図10に沿って、ステップS502における公開パラメータおよびマスタ鍵生成処理を説明する。
ステップS601において、群選択部313が、Lビットの素数nを選択し、nがq−1を割り切りかつ最小の整数kが偶数となる、偶数kおよび 2以外の素数のべきqを選択し、楕円曲線の定義体をF、位数nの部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(F):ax+y=1+dx(ad(a−d)≠0かつF上で係数aは2乗根を持ち係数dは持たない)を選択し、位数nの部分群をGとすることによって群Gを選択する。
【0226】
ステップS602において、群選択部313が、位数のnの群GをE(Fq1)/nE(Fq1)(q1=q)とすることによって群Gを選択する。
ステップS603において、群選択部313が、GをFq1(q1=q)の位数nの乗法に関する部分群Gとし、ペアリングe:G×G→Gを選択する。
【0227】
ステップS604において、群選択部313が、Gの生成元Pを選択する。
ステップS605において、乱数生成部314が、0<s<nを満たす整数sをランダムに生成し、マスタ鍵324とするとともに記憶部320に格納する。
ステップS606において、楕円曲線スカラ倍演算部315が、Ppub←sPを計算し、計算結果をZ=1の拡張Inverted twisted Edward座標(X:Y:T:1)を用いて表現する。この処理は、特許文献1〜3に記載の技術や、特願2009−119256に記載の技術などを用いて計算される。
【0228】
ステップS607において、ハッシュ関数選択部316が、ハッシュ関数H:{0,1}→Gを選択する。なおGの元は、(αx,y)(x,y∈Fq2)(q2=qk/2)で表現されているものとする。
【0229】
ステップS608において、ハッシュ関数選択部316が、予め設定されている整数Nに対して、ハッシュ関数H:G→{0,1}を選択する。
ステップS609において、公開パラメータparams=<n,G,G,G,e,N,P,Ppub,H,H>を出力するとともに記憶部320に格納する。
【0230】
以下、図8を参照しつつ、図11に沿って、ステップS503における秘密鍵生成処理を説明する。なお、この処理では公開パラメータおよびマスタ鍵生成処理S502において生成され、記憶部320に格納されている公開パラメータ323(params)およびマスタ鍵324(s)を用いるものとする。
【0231】
ステップS701において、ハッシュ関数演算部317が、公開パラメータ323(params)に含まれているハッシュ関数Hを使用して、ハッシュ値QID←H(ID)を計算する。
ステップS702において、楕円曲線スカラ倍演算部315が、マスタ鍵sを用いてdID←sQIDを計算し、計算結果である(αx,y)を利用者の秘密鍵326とする。この処理は、特許文献1〜3に記載の技術や、特願2009−119256に記載の技術などを用いて計算される。
【0232】
《暗号化》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用した暗号化処理について図12および図13を参照して説明する。
【0233】
[暗号化装置]
図12は、本実施形態に係る暗号化装置の構成例を示す図である。
暗号化装置4は、制御演算部410および記憶部420を有している。
制御演算部410は、入出力部411、制御部412、乱数生成部413、楕円曲線ペアリング演算部414、ハッシュ関数演算部415を有している。入出力部411は、公開パラメータ422、利用者Bの公開鍵、暗号化対象データ424を入力情報として受け付けるとともに、生成した暗号化データ425を出力情報として出力する機能を有している。制御部412は、暗号化装置4を制御する機能を有している。乱数生成部413は、乱数を生成する機能を有する。楕円曲線ペアリング演算部414は、ペアリングを計算する機能に加えて楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算(mod)、比較などを行う機能を有し、図1の楕円曲線ペアリング演算部113に相当するものである。ハッシュ関数演算部415は、ハッシュ関数を用いてハッシュ値を生成する機能を有する。
【0234】
記憶部420には、中間データ421、公開パラメータ422、利用者B公開鍵423、暗号化対象データ424、暗号化データ425などが格納されている。中間データ421は、制御演算部410における演算時の中間データである。公開パラメータ422は、鍵発行装置3で生成された公開パラメータのデータである。利用者B公開鍵423は、入出力部411により入力を受け付けた暗号化データ425の受信する利用者Bの公開鍵である。暗号化対象データ424は、入出力部411により入力を受け付けた暗号化の対象データである。暗号化データ425は、制御演算部410で暗号化対象データ424を暗号化することにより生成されるデータである。
【0235】
なお、暗号化装置4は、図16に示すような、バス67で接続されたCPU61と、RAMなどのメモリ62と、HDDやその他の外部記憶装置65と、キーボードなどの入力装置63と、ディスプレイなどの出力装置64と、外部記憶装置65や、入力装置63や、出力装置64と、バス67を中継するインタフェース66とを備えた、一般的な構成を有する情報処理装置6上に構築することができる。
暗号化装置4の制御演算部410および各部411〜415は、CPU61が、メモリ62にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置6上に具現化されるプロセスとして実現される。また、メモリ62や、外部記憶装置65が図12の記憶部420として使用される。
【0236】
また、前記したプログラムは、予め外部記憶装置65に記憶され、必要に応じてメモリ62上にロードされ、CPU61により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ62にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDDなどの外部記憶装置65にインストールされた後、必要に応じて、この外部記憶装置65からメモリ62にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置6が読み取り可能な媒体の一種である伝送信号により、一旦外部記憶装置65にダウンロードされてからメモリ62にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ62にロードされてもよい。
【0237】
[暗号化処理]
図13は、本実施形態に係る暗号化処理の手順を示すフローチャートである。
図12を参照しつつ、暗号化処理の概略を記述すると、入出力部411により、暗号化装置4が、入力情報として、公開パラメータ422(params)、暗号データの受信者である利用者Bの公開鍵423(ID)を鍵発行装置3から取得し、暗号化対象データ424を入力情報として受け付けると、制御演算部410は受け付けた各入力情報を記憶部420に格納する。
そして、制御演算部410が、記憶部420に保持されている入力情報を用いて、図13の処理に従って暗号化処理を行う。
制御演算部410は、生成された暗号化データを、記憶部420に保持するとともに、入出力部411より出力情報として出力し、動作を終了する。
【0238】
以下、図12を参照しつつ、図13に沿って暗号化処理を説明する。
ステップS801において、ハッシュ関数演算部415が、公開パラメータ422に含まれているハッシュ関数Hを用いて、ハッシュ値QID←H(ID)を計算する。
ステップS802において、乱数生成部413が、公開パラメータ422に含まれている値nを用いて、0<r<nを満たす整数rをランダムに生成する。
ステップS803において、楕円曲線ペアリング演算部414が、公開パラメータ422に含まれているPと、ステップS802で生成した整数rを用いて、C←rPを計算し、計算結果をZ=1の拡張Inverted twisted Edward座標(X:Y:T:1)を用いて表現する。この処理は、スカラ倍演算処理であり、特許文献1〜3に記載の技術や、特願2009−119256に記載の技術を用いて行われるものである。
ステップS804において、楕円曲線ペアリング演算部414が、公開パラメータ422に含まれているeと、Ppubと、ステップS801で生成したQIDを用いて、g←e(Ppub,QID)を計算する。この処理は、図1〜図6を参照して説明した処理を用いる。
ステップS805において、楕円曲線ペアリング演算部414が、gr←gを計算する。
ステップS806において、ハッシュ関数演算部415が、公開パラメータ422に含まれているハッシュ関数Hを用いて、ハッシュ値h←H(gr)を計算する。
ステップS807において、楕円曲線ペアリング演算部414が、C←W XOR hを計算する。ここで、Wは暗号化対象データ424である。
ステップS808において、制御演算部410が、算出した(C,C)を暗号化データ425として出力するとともに、記憶部420に格納する。
【0239】
《復号化処理》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用した復号化処理について図14および図15を参照して説明する。
【0240】
[復号化装置]
図14は、本実施形態に係る復号化装置の構成例を示す図である。
復号化装置5は、制御演算部510および記憶部520を有している。
制御演算部510は、入出力部511、制御部512、楕円曲線ペアリング演算部513、ハッシュ関数演算部514を有している。入出力部511は、公開パラメータ522、利用者Bの秘密鍵523、暗号化データ524を入力情報として受け付けるとともに、復号データ525を出力情報として出力する機能を有している。制御部512は、復号化装置5を制御する機能を有している。楕円曲線ペアリング演算部513は、ペアリングを計算する機能に加えて楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算(mod)、比較などを行う機能を有し、図1の楕円曲線ペアリング演算部113に相当するものである。ハッシュ関数演算部514は、ハッシュ関数を用いてハッシュ値を生成する機能を有する。
【0241】
記憶部520には、中間データ521、公開パラメータ522、利用者B秘密鍵523、暗号化データ524、復号データ525などが格納されている。中間データ521は、制御演算部510における演算時の中間データである。公開パラメータ522は、鍵発行装置3で生成された公開パラメータのデータである。利用者B秘密鍵523は、鍵発行装置3から受け付けた暗号化データの復号者である利用者B秘密鍵のデータである。暗号化データ524は、暗号化装置4から送られた復号の対象データである。復号データ525は、制御演算部510で暗号化データ524を復号することにより生成されるデータである。
【0242】
なお、復号化装置5は、図16に示すような、バス67で接続されたCPU61と、RAMなどのメモリ62と、HDDやその他の外部記憶装置65と、キーボードなどの入力装置63と、ディスプレイなどの出力装置64と、外部記憶装置65や、入力装置63や、出力装置64と、バス67を中継するインタフェース66とを備えた、一般的な構成を有する情報処理装置6上に構築することができる。
復号化装置5の制御演算部510および各部511〜514は、CPU61が、メモリ62にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置6上に具現化される。また、メモリ62や、外部記憶装置65が図14の記憶部520として使用される。
【0243】
また、前記したプログラムは、予め外部記憶装置65に記憶され、必要に応じてメモリ62上にロードされ、CPU61により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ62にロードされてもよいし、一旦、CD−ROMなどの可搬性の記憶媒体からHDDなどの外部記憶装置65にインストールされた後、必要に応じて、この外部記憶装置65からメモリ62にロードされてもよいし、さらには、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置6が伝送信号により、一旦外部記憶装置65にダウンロードされてからメモリ62にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ62にロードされてもよい。
【0244】
[復号化処理]
図15は、本実施形態に係る復号化処理の手順を示すフローチャートである。
図14を参照しつつ、図15に沿って復号化処理の概略を記述すると、入出力部511により、復号化装置5が、公開パラメータ522(params)、復号者である利用者Bの秘密鍵523(dID)を鍵発行装置3から取得し、暗号化データ524(C=(C,C))を暗号化装置4から受け付けると、制御演算部510は受け付けた各入力情報を記憶部520に格納する。
そして、制御演算部510が、記憶部520に保持されている各入力情報を用いて、図15の処理に従って復号化処理を行う。
制御演算部510は、復号化処理によって生成した復号データ525を、記憶部520に保持するとともに、入出力部511より出力情報として出力し、動作を終了する。
【0245】
以下、図14を参照しつつ、図15に沿って、復号化処理を説明する。
ステップS901において、楕円曲線ペアリング演算部513が、公開パラメータ522に含まれるeと、秘密鍵523(dID)と、暗号化データ524に含まれるdIDを用いて、g←e(C,dID)を計算する。この処理は、図1〜図6を参照して説明した処理を使用することによって行なわれる。
ステップS902において、ハッシュ関数演算部514が、公開パラメータ522に含まれるハッシュ関数Hを用いて、ハッシュ値h←H(g)を計算する。
ステップS903において、楕円曲線ペアリング演算部513が、W←C XOR hを計算しWを復号データ525とし、生成した復号データ525を出力するとともに、記憶部520に格納する。
【0246】
[ハードウェア構成]
図16は、情報処理装置のハードウェア構成例を示す図である。
この情報処理装置6は、楕円曲線ペアリング演算装置1(図1)、鍵発行装置3(図8)、暗号化装置4(図12)、復号化装置5(図14)に相当する装置である。
情報処理装置6では、CPU61およびメモリ62がバス67を介して互いに接続されている。また、キーボードや、マウスに相当する入力装置63、ディスプレイに相当する出力装置64、HDDや、CD−ROMなどに相当し、プログラムや、データが格納されている外部記憶装置65がインタフェース66を介してバス67に接続している。
【0247】
《まとめ》
本実施形態では、楕円曲線ax+y=1+dx(ad(a−d)≠0,定義体上で係数aは2乗根を持ち係数dは持たない)上の点(x,y)に対してx=Z/X、y=Z/Y、XYZ≠0を満たすX、Y、Z∈Fを用いて(X:Y:Z)と変換したInverted Twisted Edward座標に加えて、x=Z/X、y=Z/Y、xy=Z/T、XYTZ≠0を満たすX、Y、T、Z∈Fを用いて(X:Y:T:Z)と変換した拡張Inverted Twisted Edward座標を導入する。
つまり、拡張Inverted Twisted Edward座標をペアリング計算の際にループ処理で行われる2倍算処理における2倍算および2倍算に付随する多項式の計算、加算処理における加算および加算に付随する多項式計算に用いている。
このとき、加算においてa=−1の場合、a倍は符号の反転のみで行えるためa=−1の楕円曲線を採用するだけで2倍算ステップ1回あたり2回の定数倍算、加算処理1回あたり1回の定数倍算を削減できるが、加算処理においてそれに特化したアルゴリズムを用いることにより、さらに、加算処理1回あたり乗算を1回削減することができる。
【符号の説明】
【0248】
1 楕円曲線ペアリング演算装置
2 IDベース暗号システム
3 鍵発行装置
4 暗号化装置
5 復号化装置
6 情報処理装置
110 制御演算部(楕円曲線ペアリング演算装置)
111 入出力部(楕円曲線ペアリング演算装置)
112 制御部(楕円曲線ペアリング演算装置)
113 楕円曲線ペアリング演算部(楕円曲線ペアリング演算装置)
114 入出力部
115 楕円曲線加算演算部
116 楕円曲線2倍算演算部
117 基本演算部
120 記憶部(楕円曲線ペアリング演算装置)
310 制御演算部(鍵発行装置)
311 入出力部(鍵発行装置)
312 制御部(鍵発行装置)
313 群選択部(鍵発行装置)
314 乱数生成部(鍵発行装置)
315 楕円曲線ペアリング演算部(鍵発行装置)
316 ハッシュ関数選択部(鍵発行装置)
317 ハッシュ関数演算部(鍵発行装置)
320 記憶部(鍵発行装置)
410 制御演算部(暗号化装置)
411 入出力部(暗号化装置)
412 制御部(暗号化装置)
413 乱数生成部(暗号化装置)
414 楕円曲線ペアリング演算部(暗号化装置)
415 ハッシュ関数演算部(暗号化装置)
420 記憶部(暗号化装置)
510 制御演算部(復号化装置)
511 入出力部(復号化装置)
512 制御部(復号化装置)
413 楕円曲線ペアリング演算部(復号化装置)
514 ハッシュ関数演算部(復号化装置)
520 記憶部(復号化装置)

【特許請求の範囲】
【請求項1】
Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現したTwisted Edward型楕円曲線上の素数位数の点である第1の点と、affine座標を用いて表現した第1の点と同じ位数を持ち異なる前記Twisted Edward型楕円曲線上の第2の点と、前記第1の点および第2の点と同じ位数を持ち、前記Twisted Edward型楕円曲線上の群とは異なる群に属する第1の元を算出する楕円曲線ペアリング演算装置による楕円曲線ペアリング演算方法であって、
前記第1の点の座標を拡張Inverted twisted Edward座標を用いてP=(X1:Y1:T1:Z1)と表現したとき、Z1の値が1である場合の処理として、
前記楕円曲線ペアリング演算装置が、
入出力部を介して、前記第1の点、前記第2の点、前記第1の点の位数であり、かつ前記第2の点の位数である素数を入力し、
前記入力した素数を2進数展開し、
前記第1の元の初期値を単位元とし、
前記第1の点と同じ群に含まれ、拡張Inverted twisted Edward座標で表される第3の点の初期値を前記第1の点とし、前記展開した2進数の係数ごとに、(a)および(b)の処理を行うことで第1の元の値を更新し、前記(a)および(b)の処理で更新された第1の元に対してべき乗計算を行った結果を第1の元と置き直すことで、第1の元を得ることを特徴とする楕円曲線ペアリング演算方法。
(a)前記楕円曲線ペアリング演算装置が、前記第3の点を2倍した値で置換することによって、前記第3の点を更新し、
前記2倍算に付随して計算される多項式に対して前記第2の点を代入した値と、前記第1の元の2乗と、を乗算することで得られた値を前記第1の元とすることで前記第1の元を更新し、
(b)前記楕円曲線ペアリング演算装置が、前記第1の点と、前記第3の点の加算処理を行い、
前記加算処理で算出された値を前記第3の点とすることで前記第3の点を更新し、
前記加算に付随して計算される多項式に対して前記第2の点を代入した値と、前記第1の元と乗算することで得られた値を前記第1の元とすることで前記第1の元を更新する。
【請求項2】
前記Twisted Edward型楕円曲線におけるx2の項の係数が−1である
ことを特徴とする請求項1に記載の楕円曲線ペアリング演算方法。
【請求項3】
Twisted Edward型楕円曲線上のペアリング演算(f=e(P,Q))を行う楕円ペアリング演算装置による楕円曲線ペアリング演算方法であって、
前記楕円ペアリング演算装置が、
入力部を介して、
位数qの有限体Fq(qは2以外の素数のべきqで、E(Fq)の位数である#E(Fq)を割り切る位数であるとともに3以上の素数である値nがqk−1を割り切る最小のkが偶数となる数)を定義体として持ち、かつ前記値nの部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(Fq):ax2+y2=1+dx22(ad(a−d)≠0かつFq上で係数aは2乗根を持ち係数dは持たない)の値nを位数とする部分群G1の情報、前記Twisted Edward型楕円曲線E(Fq)上の点(x1,y1)において、x1=Z1/X1、y1=Z1/Y1、x11=Z1/T1、X1111≠0を満たすとともにZ1=1を満たすX1,Y1,T1,Z1∈Fqで表現される拡張Inverted twisted Edward座標を用いて表現したG1の元P=(X1:Y1:T1:Z1)の情報、前記値nがqk−1を割り切る最小の偶数kを拡大次数として持ち、かつα2=δ∈Fq2(q2=qk/2)を満たす基底{1,α}を用いてFqのk/2次拡大体Fq2(q2=qk/2)上の2次拡大体と見なすことのできるFqのk次拡大体Fq1(q1=qk)の値nを位数とする乗法に関する部分群G3の情報、E(Fq)をFq1(q1=qk)上の楕円曲線と見なしたE(Fq1)(q1=qk)の値nを位数とする部分群G2の情報、およびAffine座標を用いてQ=(x0α,y0)(x0,y0∈Fq2)(q2=qk/2)と表現できるG2の元Qの情報を入力し、
前記楕円ペアリング演算装置が、
(a1)前記値nを2進数展開して、n=n0+n1×2+・・・+nt-1×2t-1 (nt-1=1)とし、
(a2)η←(1+y0)/(x0δ)とおき、
(a3)f←1、i←t−2、R←Pとおき、
(a4)f←f2R,R(Q)、R←2Rを計算し、
(a5)ni=1であるか否かを判定し、ni=1であれば(a6)の処理に進み、ni=1でなければ(a7)の処理に進み、
(a6)f←fgR,P(Q)、R←R+Pを計算し、
(a7)i←i−1を計算し、
(a8)i≧0であるか否かを判定し、i≧0であれば、前記(a4)の処理に戻り、i≧0でなければ(a9)の処理に進み、
(a9)f←f(q1-1)/n(q1=qk)を計算し、当該fを演算結果とする
ことを特徴とする楕円曲線ペアリング演算方法。
【請求項4】
前記(a4)の処理において、入力時におけるRの座標を拡張Inverted twisted Edward座標を用いて(X2:Y2:T2:Z2)とした場合、
前記楕円曲線ペアリング演算装置が、
(b1)A←X22、B←Y22、C←T22、D←aB、E←aY22をFq上でそれぞれ計算し、
(b2)F←A+D、G←A−D、H←(X2+Y22−A−B、I←(X2+T22−A−C、J←(2C−F)をFq上でそれぞれ計算し、
(b3)cZZ←2X2(Y2−Z2)をFq上で計算し、
(b4)cXY←2(F−C)−IをFq上で計算し、
(b5)cXZ←2(A−E)をFq上で計算し、
(b6)gR,R(Q)←cZZηα+cXY0+cXZをFqのk/2次拡大体Fq2(q2=qk/2)上で計算し、
(b7)f←f2R,R(Q)をFqのk次拡大体Fq1(q1=qk)上で計算し、
(b8)X3←FGをFq上で計算し、
(b9)Y3←HJをFq上で計算し、
(b10)T3←FHをFq上で計算し、
(b11)Z3←GHをFq上で計算し、
(b12)R←(X3:Y3:T3:Z3)とおき、fとともに、演算結果とする
ことを特徴とする請求項3に記載の楕円曲線ペアリング演算方法。
【請求項5】
前記Twisted Edward型楕円曲線における係数aの値が−1と異なる場合、かつ前記(a6)の処理において、入力時のPの座標を(X1:Y1:T1:Z1=1)、Rの座標を(X2:Y2:T2:Z2)であるとした場合の処理として、
前記楕円曲線ペアリング演算装置が、
(c1)A←X12、B←Y12、C←T21、D←T12をFq上でそれぞれ計算し、
(c2)E←(X1+Y1)(X2−Y2)+B−A、F←C+D、G←C−D、H←A+aB、I←T12をFq上でそれぞれ計算し、
(c3)cZZ←Y21−Y12をFq上で計算し、
(c4)cXY←(Y1−T1)(Y2+T2)−B+I+EをFq上で計算し、
(c5)cXZ←D−C+(X12+X21)をFq上で計算し、
(c6)gR,P(Q)←cZZηα+cXY0+cXZをFqのk/2次拡大体Fq2(q2=qk/2)上で計算し、
(c7)f←fgR,P(Q)をFqのk次拡大体Fq1(q1=qk)上で計算し、
(c8)i=0であるか否かを判定し、i=0であれば(c14)の処理に進み、i=0でなければ(c9)の処理に進み、
(c9)X3←HGをFq上で計算し、
(c10)Y3←EFをFq上で計算し、
(c11)T3←HEをFq上で計算し、
(c12)Z3←FGをFq上で計算し、
(c13)演算結果をQ←(X3:Y3:T3:Z3)およびfとする
(c14)演算結果をfとする
ことを特徴とする請求項3に記載の楕円曲線ペアリング演算方法。
【請求項6】
前記Twisted Edward型楕円曲線における係数aの値が−1の場合、かつ前記(a6)の処理において、入力時のPの座標を(X1:Y1:T1:Z1=1)、Rの座標を(X2:Y2:T2:Z2)とした場合の処理として、
前記楕円曲線ペアリング演算装置が、
(d1)A←(X1−Y1)(X2+Y2)、B←(X1+Y1)(X2−Y2)、C←2T21、D←2T12をFq上でそれぞれ計算し、
(d2)E←A+B、F←C+D,G←C−D,H←B−AをFq上でそれぞれ計算し、
(d3)cZZ←2(Y21−Y12)をFq上で計算し、
(d4)cXY←2(Y12−Y21)+HをFq上で計算し、
(d5)cXZ←D−C+2(X12−X21)をFq上で計算し、
(d6)gR,P(Q)←cZZηα+cXY0+cXZをFqのk/2次拡大体Fq2(q2=qk/2)上で計算し、
(d7)f←fgR,P(Q)をFqのk次拡大体Fq1(q1=qk)上で計算し、
(d8)i=0であるか否かを判定し、i=0であれば(d14)の処理に進み、i=0でなければ(d9)の処理に進み、
(d9)X3←EGをFq上で計算し、
(d10)Y3←HFをFq上で計算し、
(d11)T3←EHをFq上で計算し、
(d12)Z3←FGをFq上で計算し、
(d13)演算結果をQ←(X3:Y3:T3:Z3)およびfとする
(d14)演算結果をfとする
ことを特徴とする請求項3に記載の楕円曲線ペアリング演算方法。
【請求項7】
請求項1から請求項6のいずれか一項に記載の楕円曲線ペアリング演算方法をコンピュータに実行させることを特徴とするプログラム。
【請求項8】
IDベース暗号を利用した暗号化を行う暗号化装置による暗号化方法であって、
前記暗号化装置が、
鍵発行装置から、公開パラメータおよび暗号化データの受信者の公開鍵を取得し、
外部装置から暗号化対象データを取得し、
前記公開パラメータと、前記公開鍵を基に、請求項1または請求項2に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化対象データを暗号化する
ことを特徴とする暗号化方法。
【請求項9】
IDベース暗号を利用した暗号化を行う暗号化装置による暗号化方法であって、
前記暗号化装置が、
鍵発行装置から、公開パラメータparams、および暗号化データの受信者の公開鍵IDを取得し、
外部装置から暗号化対象データWを取得し、
前記公開パラメータparamsは、すべてのバイナリ系列から部分群G2への写像であるハッシュ関数H1、Fq上で定義される楕円曲線E(Fq)の位数である#E(Fq)を割り切る位数であるとともに3以上の素数である値n、Twisted Edward型楕円曲線上の任意の点P、前記Pをs(sは0<s<nを満たすランダムな整数)倍した点Ppub、e:G1×G2→G3を満たすeを含んでおり、
(f1)QID←H1(ID)を計算し、
(f2)0<r<nを満たす整数rをランダムに生成し、
(f3)C1←rPを計算し、計算結果をZ=1の拡張Inverted twisted Edward座標(X:Y:T:1)を用いて表現し、
(f4)請求項3から請求項6のいずれか一項に記載の楕円曲線ペアリング演算方法を行って、g←e(Ppub,QID)を計算し、
(f5)gr←grを計算し、
(f6)h←H2(gr)を計算し、
(f7)C2←W XOR hを計算し、
(f7)C←(C1,C2)を暗号化データとする
ことを特徴とする暗号化方法。
ここで、G1は位数qの有限体Fq(qは2以外の素数のべきqで、#E(Fq)を割り切る位数であるとともに3以上の素数である値nがqk−1を割り切る最小のkが偶数となる数)を定義体として持ち、かつ前記値nを位数とする部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(Fq):ax2+y2=1+dx22(ad(a−d)≠0かつFq上で係数aは2乗根を持ち係数dは持たない)の値nを位数とする部分群であり、G2はE(Fq)をFq1(q1=qk)上の楕円曲線と見なしたE(Fq1)(q1=qk)の値nを位数とする部分群であり、G3はF*q1(q1=qk)の値nを位数とする乗法に関する部分群である。
【請求項10】
請求項8または請求項9に記載の暗号化方法をコンピュータに実行させることを特徴とするプログラム。
【請求項11】
請求項8に記載の暗号化方法によって生成された暗号化データを復号する復号化装置による復号化方法であって、
前記復号化装置が、
鍵発行装置から、公開パラメータおよび復号者の秘密鍵を取得し、
前記公開パラメータと、前記公開鍵を基に、請求項1または請求項2に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化データを復号する
ことを特徴とする復号化方法。
【請求項12】
請求項9に記載の暗号化方法によって生成された暗号化データを復号する復号化装置による復号化方法であって、
前記復号化装置が、
鍵発行装置から、公開パラメータparams、復号者である利用者Bの秘密鍵dIDを取得し、
前記暗号化装置から暗号化データC=(C1,C2)を取得し、
前記公開パラメータparamsは、部分群G3からすべてのNビットバイナリ系列への写像であるハッシュ関数H2、e:G1×G2→G3を満たすeを含んでおり、
前記楕円曲線ペアリング演算部は、
(g1)請求項3から請求項6のいずれか一項に記載の楕円曲線ペアリング演算方法を行ってg←e(C1,dID)を計算し、
ハッシュ関数演算部は、
(g2)h←H2(g)を計算し、
前記楕円曲線ペアリング演算部は、
(g3)W←C2 XOR hを計算し、Wを復号データとする
ことを特徴とする復号化方法。
ここで、G1は位数qの有限体Fq(qは2以外の素数のべきqで、#E(Fq)を割り切る位数であるとともに3以上の素数である値nがqk−1を割り切る最小のkが偶数となる数)を定義体として持ち、かつ前記値nを位数とするの部分群を最大位数の部分群として持つTwisted Edward型楕円曲線E(Fq):ax2+y2=1+dx22(ad(a−d)≠0かつFq上で係数aは2乗根を持ち係数dは持たない)の値nを位数とする部分群であり、G2はE(Fq)をFq1(q1=qk)上の楕円曲線と見なしたE(Fq1)(q1=qk)の値nの部分群であり、G3はF*q1(q1=qk)の値nを位数とする乗法に関する部分群である。
【請求項13】
請求項11または請求項12に記載の復号化方法をコンピュータに実行させることを特徴とするプログラム。
【請求項14】
Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現したTwisted Edward型楕円曲線上の素数位数の点である第1の点と、affine座標を用いて表現した第1の点と同じ位数を持ち異なる前記Twisted Edward型楕円曲線上の第2の点と、前記第1の点および第2の点と同じ位数を持ち、前記Twisted Edward型楕円曲線上の群とは異なる群に属する第1の元を算出する楕円曲線ペアリング演算装置であって、
前記第1の点の座標を拡張Inverted twisted Edward座標を用いてP=(X1:Y1:T1:Z1)と表現したとき、Z1の値が1である場合の処理として、
入出力部を介して、前記第1の点、前記第2の点、前記第1の点の位数であり、かつ前記第2の点の位数である素数を入力し、前記入力した素数を2進数展開し、前記第1の元の初期値を単位元とし、前記第1の点と同じ群に含まれ、拡張Inverted twisted Edward座標で表される第3の点の初期値を前記第1の点とする基本演算部と、
前記展開した2進数の係数ごとに、(a)および(b)の処理を行うことで第1の元の値を更新し、前記(a)および(b)の処理で更新された第1の元に対してべき乗計算を行った結果を第1の元と置き直すことで、第1の元を得る楕円曲線ペアリング演算部と、
を有することを特徴とする楕円曲線ペアリング演算装置。
(a)前記楕円曲線ペアリング演算装置が、前記第3の点を2倍した値で置換することによって、前記第3の点を更新し、
前記2倍算に付随して計算される多項式に対して前記第2の点を代入した値と、前記第1の元の2乗と、を乗算することで得られた値を前記第1の元とすることで前記第1の元を更新し、
(b)前記楕円曲線ペアリング演算装置が、前記第1の点と、前記第3の点の加算処理を行い、
前記加算処理で算出された値を前記第3の点とすることで前記第3の点を更新し、
前記加算に付随して計算される多項式に対して前記第2の点を代入した値と、前記第1の元と乗算することで得られた値を前記第1の元とすることで前記第1の元を更新する。
【請求項15】
前記Twisted Edward型楕円曲線におけるx2の項の係数が−1である
ことを特徴とする請求項14に記載の楕円曲線ペアリング演算装置。
【請求項16】
IDベース暗号を利用した暗号化を行う暗号化装置であって、
鍵発行装置から、公開パラメータおよび暗号化データの受信者の公開鍵を取得し、外部装置から暗号化対象データを取得する入出力部と、
前記公開パラメータと、前記公開鍵を基に、請求項1または請求項2に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化対象データを暗号化する制御演算部と、
を有することを特徴とする暗号化装置。
【請求項17】
請求項16に記載の暗号化装置によって生成された暗号化データを復号する復号化装置であって、
鍵発行装置から、公開パラメータおよび復号者の秘密鍵を取得する入出力部と、
前記公開パラメータと、前記公開鍵を基に、請求項1または請求項2に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化データを復号する制御演算部と、
を有することを特徴とする復号化装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate


【公開番号】特開2011−237475(P2011−237475A)
【公開日】平成23年11月24日(2011.11.24)
【国際特許分類】
【出願番号】特願2010−106367(P2010−106367)
【出願日】平成22年5月6日(2010.5.6)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】