(57)【要約】【課題】  高速なIDベース暗号方法における楕円曲線のテートペアリング演算装置を提供する。【解決手段】  標数3の楕円曲線上で定義されるテートペアリングを計算する際に、1/3乗演算を行う必要を無くし、さらに2回のループを1回にまとめることによりGF(q)上の乗算回数の削減を行う。これらテートペアリングの計算速度に大きく影響する演算の削除および削減により、より高速なテートペアリングの計算を行う。【選択図】図3
2006178125.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線テートペアリング演算装置であって、
演算対象となる楕円曲線および演算対象データを入力する入力部と、
楕円曲線の情報を保持する楕円曲線情報保持部と、
演算対象データを保持する演算対象データ保持部と、
テートペアリング演算を行うペアリング演算部と、
演算結果を保持する演算結果保持部と、
演算結果を出力する出力部と、を備える楕円曲線テートペアリング演算装置。
【請求項２】
請求項1記載の楕円曲線テートペアリング演算装置において、
mを6と互いに素な正整数、q=3m、かつ、b=±1としたとき、
前記ペアリング演算部は、標数3のm次拡大体GF(q)上の楕円曲線
y2=x3-x+b上で定義されるテートペアリングを計算する
ことを特徴とする楕円曲線テートペアリング演算装置。
【請求項３】
請求項2記載の楕円曲線テートペアリング演算装置において、
前記ペアリング演算部は、前記テートペアリングを計算する際に、標数3の6m次拡大体GF(q6)の元である中間データfの値を更新する
ことを特徴とする楕円曲線テートペアリング演算装置。
【請求項４】
請求項3記載の楕円曲線テートペアリング演算装置において、
前記中間データfの値の更新に必要な値を計算する際に、GF(q)上の1/3乗演算を行わない
ことを特徴とする請求項3記載の楕円曲線テートペアリング演算装置。
【請求項５】
請求項3記載の楕円曲線テートペアリング演算装置において、
前記テートペアリングを計算する際の繰り返し演算において、前記中間データfの更新をGF(q6)の元g1 、g2から求められるg=g1・g2を用いてf←f9・gを計算することにより行う
ことを特徴とする楕円曲線テートペアリング演算装置。
【請求項６】
請求項3記載の楕円曲線テートペアリング演算装置において、
テートペアリングを計算する際に前記中間データfの最終的な値に対して、fのq3-1乗を計算することで最終的なテートペアリングの値を求める
ことを特徴とする楕円曲線テートペアリング演算装置。
【請求項７】
mを6と互いに素な正整数、q=3m、かつ、b=±1としたとき、
標数3のm次拡大体GF(q)上の楕円曲線
y2=x3-x+b上で定義されるテートペアリングを計算する
ことを特徴とする楕円曲線テートペアリング演算方法。
【請求項８】
請求項7記載の楕円曲線テートペアリング演算方法において、
前記テートペアリングを計算する際に、標数3の6m次拡大体GF(q6)の元である中間データfの値を更新する
ことを特徴とする楕円曲線テートペアリング演算方法。
【請求項９】
請求項8記載の楕円曲線テートペアリング演算方法において、
前記中間データfの値の更新に必要な値を計算する際に、GF(q)上の1/3乗演算を行わない
ことを特徴とする楕円曲線テートペアリング演算方法。
【請求項１０】
請求項8記載の楕円曲線テートペアリング演算装置において、
前記テートペアリングを計算する際の繰り返し演算において、前記中間データfの更新をGF(q6)の元g1 、g2から求められるg=g1・g2を用いてf←f9・gを計算することにより行う
ことを特徴とする楕円曲線テートペアリング演算方法。
【請求項１１】
請求項8記載の楕円曲線テートペアリング演算装置において、
テートペアリングを計算する際に前記中間データfの最終的な値に対して、fのq3-1乗を計算することで最終的なテートペアリングの値を求める
ことを特徴とする楕円曲線テートペアリング演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術としての暗号技術に関するものであり、特に、任意の文字列を公開鍵として用いることが可能な、IDベース暗号を実現する上で必要となるテートペアリングを、高速に計算する上で必要となる楕円曲線テートペアリング高速演算装置に関するものである。
【背景技術】
【０００２】
任意の文字列を公開鍵として用いることのできるIDベース公開鍵暗号として、以下のようなペアリングと呼ばれる双線形写像の性質を応用した方法が提案されている（たとえば、非特許文献1参照）。
【０００３】
位数がqの2つの群G1,G2とした時G1×G1からG2への写像eで以下の性質を満たすものをペアリングと呼ぶ。
1. 任意のP,Q∈ G1に対してeはe(aP,bQ)=e(P,Q)abを満たす。
2. 任意のP,Q∈ G1×G1に対してe(P,Q)≠G2の単位元を満たす。
任意のP,Q∈ G1×G1に対して、e(P,Q)を計算する効率的なアルゴリズムが知られている。
【０００４】
次にIDベース公開鍵暗号方法について説明する。
【０００５】
(1)公開パラメータおよびマスター鍵生成
入力:セキュリティパラメータl
出力:公開パラメータparam、マスター鍵s
ステップ1:セキュリティパラメータlを用いて素数q、位数がqの2つの群G1、G2、ペアリングe:G1×G1を→G2を生成しG1の生成元Pを選択する。
ステップ2:ランダムにZq*の元sを選択し、Ppub=sPとおく。
ステップ3:ハッシュ関数H1:{0,1}* →G1*を選択する。
ステップ4:ある整数nに対して、ハッシュ関数 H2:G2→{0,1}n を選択する。
ステップ5:公開パラメータをparam=<q,G1,G2,e,n,P,Ppub,H1,H2>、マスター鍵をsとする。
【０００６】
(2)秘密鍵生成
入力:公開パラメータparam、マスター鍵s、公開鍵として用いる任意の文字列ID
出力:IDに対応する秘密鍵dID
ステップ1:QID=H1(ID)を計算する。
ステップ2:dID=sQIDを計算する。
ステップ3:秘密鍵としてdIDとする。
【０００７】
(3)暗号化
入力:暗号化対象データM、公開パラメータをparam、公開鍵ID
出力:暗号化データC=(C1,C2)
ステップ1:QID =H1(ID)∈ G1*を計算する。
ステップ2:ランダムにr∈ Zq*を選択する。
ステップ3:C1=rPを計算する。
ステップ4:gID=e(QID,Ppub)を計算する。
ステップ5:h= H2(gIDr)を計算する。
ステップ6:C2=M XOR hを計算する。
ステップ7:暗号化デーをC=(C1,C2)とする。
【０００８】
(4)復号
入力:暗号化データC=(C1,C2)、公開パラメータparam、秘密鍵dID
出力:復号データM
ステップ1:g=e(dID,C1)を計算する。
ステップ2:h=H2(g)を計算する。
ステップ3:M=C2 XOR hを計算する。
ステップ4:復号データMを出力する。
【０００９】
上述のように、ペアリングを用いたIDベース公開鍵暗号方法では、暗号化および復号処理においてペアリングの計算が必要となる。
【００１０】
非特許文献1ではIDベース公開鍵暗号を構成する際に用いることができるペアリングの例として楕円曲線上で定義されるテートペアリングが示されている。
【００１１】
次に楕円曲線上のテートペアリングについて説明する。
【００１２】
有限体GF(p)上の楕円曲線をE(GF(p))、lねじれ群E[l](GF(p))をE(GF(p))の点の内、l倍が楕円曲線上の単位元となる点集合とする。楕円曲線をE(Fp)をFpのk次拡大体Fq上の楕円曲線とみなしたものをE(GF(pk)、そのlねじれ群をE[l](GF(pk))とする。ただしlおよびkは以下の3つの条件を満たすものとする。
1. lはE(GF(p))の位数#E(GF(p))を割り切る。
2. lはpk-1を割り切る。
3. lはα=1,2,...,k-1に対してpα-1を割り切らない。
【００１３】
このとき、テートペアリングeはE[l](GF(p))[l]×E[l](GF(pk))からGF(pk)＊への写像で、E[l](GF(p))の点P、単位元O、E[l](GF(pk))の点Qに対して(fP)=l(P)-l(O)を満たす有理関数fPを用いてe(P,Q)=(fP(Q))(q-1)/mを用いて計算される。ただしq=pkとする。
【００１４】
有限体GF(q)上の楕円曲線y2=x3-x+b上のテートペアリングの具体的な計算方法が非特許文献2に示されている。ただしmは6と互いに素な正整数、q=3m、b=±1であるとする。またσ、ρ∈ GF(q6)はそれぞれσ2+1=0、ρ3-ρ+bを満たし、φ(x,y)=(ρ-x、σy)であるとする。
【００１５】
以上の前提で非特許文献2に示されている計算方法を説明する。
入力: 楕円曲線y2=x3-x+b、P=(α,β)∈ GF[l](q)、
Q=(x,y)∈ GF[l](q)
出力: テートペアリングe(P,φ(Q))=(fP(φ(Q)))q'-1
ステップ1: f←1
ステップ2: iが1からmまで、以下の処理を繰り返す。
ステップ2.1: α←α3、β←β3
ステップ2.2: μ←α+x+b
ステップ2.3: λ←-σβy-μ2 
ステップ2.4: g←λ-μρ-ρ2 
ステップ2.5: f←f・g
ステップ2.6: x←x1/3、y←y1/3 
ステップ2.7: i←i+1
ステップ3: q'=q3としてe(P,φ(Q))=fq'-1を計算する。
ステップ4: e(P,Q)を出力する。
【００１６】
非特許文献2に示されている計算方法のソフトウェア実装結果および標数3の拡大体GF(q)の実装方法が非特許文献3に記載されている。
【００１７】
非特許文献3によるとGF(q)の実装は、正規基底を用いる方法と多項式基底を用いる方法の2種類が記載されている。正規基底は3乗および1/3乗演算が巡回シフトを用いて高速に実現できる反面、乗算が複雑になるという問題がある。多項式基底は正規基底に比べて3乗および1/3乗演算の速度で劣るものが、ソフトウェア実装に適し、その他の演算では正規基底を用いた場合より高速である。
【００１８】
また、非特許文献3に記載されている非特許文献2に示されているテートペアリングの実装結果では、多項式基底を用いた実装が正規基底を用いた実装より2.5倍程度高速であるという結果が記載されている。さらに、多項式基底を用いた場合、1/3乗演算は3乗演算の約12倍演算時間がかかることも記載されている。
【００１９】
多項式基底を用いてGF(q)を実現した場合、高速計算が可能となるよう1/3乗演算を用いない非特許文献2に示されている計算方法が非特許文献4に示されている。
【００２０】
以下、非特許文献2に示されている計算方法と同じ前提で非特許文献4に示されている計算方法を説明する。
入力: 楕円曲線y2=x3-x+b、P=(α,Β)∈ GF[l](q)、Q=(x,y)∈ GF[l](q)
出力: テートペアリングe(P,φ(Q))=(fP(φ(Q)))q'-1
ステップ1: f←1
ステップ2: x←x3、y←y3、d←mb
ステップ3: iが1からmまで、以下の処理を繰り返す。
ステップ3.1: α←α9、β←β9
ステップ3.2: μ←α+x+b
ステップ3.3: λ←σβy-μ2 
ステップ3.4: g←λ-μρ-ρ2 
ステップ3.5: f←f3・g
ステップ3.6: y←-y、d←d-b 
ステップ3.7: i←i+1
ステップ4:q'=q3としてe(P,Q)=fq'-1を計算する。
ステップ5: e(P,Q)を出力する。
【００２１】
非特許文献2に示されている計算方法と比較してGF(q)上の2回の1/3乗演算が削減される代わりにGF(q)上の3乗演算が8回増えている。しかしながら多項式基底を用いてGF(q)を実装した場合、非特許文献3で示されているように1/3乗演算の計算時間は3乗演算の約12倍となるためテートペアリングの計算時間を短縮できる。
【００２２】
非特許文献2に示されている繰り返し計算（ステップ2）の2回分の計算を1回にまとめることで繰り返し計算回数を(m-1)/2回に削減し、1回あたりg1,g2 を計算し、fの更新をf←f・g1・g2 により行うことでGF(q)上の乗算回数を削減する計算方法が非特許文献5に示されている。
【００２３】
以下、非特許文献2に示されている計算方法と同じ前提で非特許文献5に示されている計算方法を説明する。
入力: 楕円曲線y2=x3-x+b、P=(α,β)∈ GF[l](q)、Q=(x,y)∈ GF[l](q)
出力: テートペアリングe(P,φ(Q))=(fP(φ(Q)))q'-1
ステップ1: f←1
ステップ2: iが1から(m-1)/2まで、以下の処理を繰り返す。
ステップ2.1: α←α3、β←β3
ステップ2.2: μ←α+x+b、λ←-σβy-μ2 
ステップ2.3: g1←λ-μρ-ρ2
ステップ2.4: x←x1/3 、y←y1/3 
ステップ2.5: α←α3、β←β3
ステップ2.6: μ←α+x+b、λ←-σβy-μ2 
ステップ2.7: g1←λ-μρ-ρ2
ステップ2.8: g←g1・g2、f←f・g
ステップ2.9: x←x1/3 、y←y1/3
ステップ2.10: i←i+1
ステップ3: α←α3、β←β3
ステップ4: μ←α+x+b、λ←-σβy-μ2 
ステップ5: g←λ-μρ-ρ2、f←f・g
ステップ6: q'=q3としてe(P,φ(Q))=fq'-1を計算する。
ステップ7: e(P,φ(Q))を出力する。
【００２４】
上記従来例は非特許文献2に示されている計算方法の繰る返し計算(ステップ2)で必要であったGF(q)上の1/3乗算を行う必要が無くなり、非特許文献2に示されている計算方法の繰り返し計算(ステップ2)2回あたり40回必要であったGF(q)上の乗算が、非特許文献5に示されている計算方法では1回あたり28回に削減されるためテートペアリングの高速計算が可能になる。
【００２５】
【非特許文献１】D.Boneh, M.Franklin著 「Identity-Based Encryption from the Weil PairingS」Springer-Verlag,2001年, Proceedings Asiacrypt 2001, Lecture Notes in Computer Science 2248,p-514-532
【非特許文献２】I. Duursma and H. Lee著  「Tate pairing implementation for hyperelliptic curves y2=xp-x+d」Springer-Verlag,2003年 Asiacrypt 2003, Lecture Notes in Computer Science, vol. 2894, pp. 111-123, 2003.
【非特許文献３】R. Granger, D. Page, M. Stam著  「Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three」2004年  http://eprint.iacr.org/2004/157.pdf Cryptology ePrint Archive 2004/157
【非特許文献４】S. Kwon著  「Efficient Tate Pairing Computation for Supersingular Elliptic Curves over Binary Fields」2004年  http://eprint.iacr.org/2004/303.pdf Cryptology ePrint Archive 2004/303
【非特許文献５】R.Granger, D. Page, M. Stam著  「On Small Characteristic Tori in Pairing-Based Cryptography」2004年  http://eprint.iacr.org/2004/132.pdf Cryptology ePrint Archive 2004/032
【発明の開示】
【発明が解決しようとする課題】
【００２６】
楕円曲線上で定義されるテートペアリングを用いたIDベース公開鍵暗号方法では、ペアリング演算を行う演算装置が必須である。暗号化および復号の際のペアリング演算は負荷が大きいため、これを高速に行う必要がある。
【００２７】
非特許文献2で示されている計算方法では多項式基底を用いてGF(q)を実装した場合、演算速度的に不利な1/3乗演算が2回必要であるという問題がある。非特許文献4で示されている計算方法では1/3乗根演算を行う必要が無いが、非特許文献5で示されている計算方法に比べてGF(q)上の乗算回数が多いという問題がある。非特許文献5で示されている計算方法は非特許文献2および非特許文献4で示されている計算方法のループ2回に相当するループ1回あたりのGF(q)上の乗算回数が28回で非特許文献2および非特許文献4で示されている計算方法に比べて12回少ないという利点があるが、GF(q)を多項式基底を用いて実現した場合、演算速度的に不利な1/3乗演算が繰り返し計算1回あたり4回必要であるという問題がある。
【課題を解決するための手段】
【００２８】
本発明は上述の問題点を踏まえて行われたもので、楕円曲線上で定義されるテートペアリングの計算を行う際に、非特許文献5で示されている計算方法に対して非特許文献3で示されている改良方法を適用することにより1/3乗演算の必要がなく、また2回分の繰り返し計算を1回分の繰り返し計算にまとめることによりGF(q)上の乗算回数の削減を行う。
【００２９】
より具体的には、本発明は、mを6と互いに素な正整数、q=3m、かつ、b=±1としたとき、標数3のm次拡大体GF(q)上の楕円曲線
y2=x3-x+b上で定義されるテートペアリングを計算することを特徴とする。
【００３０】
さらに、上記テートペアリングを計算する際に、標数3の6m次拡大体GF(q6)の元である中間データfの値を更新してもよい。
【００３１】
さらに、上記中間データfの値の更新に必要な値を計算する際に、GF(q)上の1/3乗演算を行わなくてもよい。
【００３２】
さらに、上記テートペアリングを計算する際の繰り返し演算において、上記中間データfの更新をGF(q6)の元g1 、g2から求められるg=g1・g2を用いてf←f9・gを計算することにより行ってもよい。
【００３３】
さらに、テートペアリングを計算する際に上記中間データfの最終的な値に対して、fのq3-1乗を計算することで最終的なテートペアリングの値を求めてもよい。
【００３４】
以上の改良を行うことにより多項式基底を用いてGF(q)を実装した場合速度的に不利な1/3乗演算を行う必要が無くなり、さらにGF(q)上の乗算回数を削減できるためより高速にテートペアリングを計算することが可能となる。
【００３５】
これらの改良により高速な暗号装置を提供することが可能となる。
【発明の効果】
【００３６】
本発明により、高速なIDベース公開鍵暗号方法を可能にする楕円曲線IDベース公開鍵暗号装置を提供できる。
【発明を実施するための最良の形態】
【００３７】
以下、本発明を適用した実施形態について、図1を用いて説明する。
【００３８】
図1は本実施形態を実現する楕円曲線テートペアリング演算装置(以下演算装置)101の機能構成図である。演算装置101は、制御演算部102およびデータ保持部103から構成される。制御演算部102は、楕円曲線のパラメータ、定義体情報、演算対象データを入力し、演算結果としてTate ペアリングe(P,φ(Q))を出力する入出力部104、演算装置101全体を制御する制御部105、ペアリング演算を行うペアリング演算部106から構成される。
【００３９】
データ保持部103は入出力部104により入力された演算対象データである楕円曲線のlねじれ群E[l](GF(q))の点P、Qを保持する演算対象データ保持部107、使用する楕円曲線に関する情報を保持する楕円曲線情報保持部108、ペアリング演算部106で用いられる中間データを保持する中間データ保持部109、制御演算部102で計算された演算結果を保持する演算結果保持部110から構成される。
【００４０】
次に各々の動作は制御部105により制御されているものとして動作の流れを説明する。入出力部104により入力された演算対象データは演算対象データ保持部107に保持される。入出力部104により入力された楕円曲線パラメータ、定義体情報は楕円曲線情報保持部108に保持される。次にペアリング演算部106において演算対象データ保持部107、楕円曲線情報保持部108で保持されている情報を用いてペアリングを計算する。ペアリング演算における中間演算結果は必要に応じて中間データ保持部109において保持される。テートペアリングの計算は図2に示すフローチャートに従って行われるものとする。最後に楕円曲線テートペアリング演算装置101は入出力部104により演算結果を出力する。
【００４１】
上記の演算装置は、CPUとメモリと、ハードディスク装置やその他の外部記憶装置と、キーボードなどの入力装置と、ディスプレイなどの出力装置と、外部記憶装置や入出力装置とのインターフェースを備えた、一般的な構成を有する情報処理装置上に構築することができる。
【００４２】
演算部102の各処理部104〜106は、CPUがメモリにロードされたプログラム(コード、モジュールともいう)を実行することで、情報処理装置上に具現化されるプロセスとして実現される。また、メモリや外部記憶装置がデータ保持部103の各保持部107〜110として使用される。
【００４３】
上述した各プログラムは、予め外部記憶装置に記憶され、必要に応じてメモリ上にロードされ、CPUにより実行される。上記プログラムは、可搬性の記憶媒体、例えばCD-ROMを扱う外部記憶装置を解して、必要に応じて、可搬性の記憶媒体からメモリにロードされても良いし、一旦、外部記憶装置を介して、可搬性の記憶媒体から外部記憶装置から外部記憶装置にインストールされた後、必要に応じて、外部記憶装置からメモリにロードされても良いし、さらには、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置が読み取り可能な媒体の一種である伝送信号により、一旦外部記憶装置にダウンロードされてからメモリにロードされても良いし、あるいは、直接、ネットワーク経由でメモリにロードされても良い。
【００４４】
次に図2〜3を用いて本実施形態の動作を詳細に説明する。
【００４５】
図2は図1において行われている処理を説明するフローチャートである。
<ステップ201>
mを6と互いに素な正整数、q=3m、b=±1、GF(q)上の楕円曲線E:y2=x3-x+b、 写像φ:φ(x,y)=(ρ-x,σy)、lねじれ群E[l](GF(q))を入力する。ただし、b=±1、 σ、ρはGF(3)上の方程式σ2+1=0、ρ3-ρ-b=0を満たし、lは以下の条件を満たすものとする。
1. lはE(GF(q))の位数#E(Fp)を割り切る。
2. lはq6-1を割り切る。
3. lはc=1、2、...、5に対してqc-1を割り切らない。
<ステップ202>
演算対象データとしてlねじれ群E[l](GF(q))の点P=(α,β)、Q=(x,y)を入力する。
<ステップ203>
テートペアリングe(P,φ(Q))を計算する。
<ステップ204>
演算結果e(P,φ(Q))を出力する。
【００４６】
上記ステップ203を、図3に示すペアリング演算部106の動作説明フローチャートを用いて詳細に説明を行う。
<ステップ301>
f←1、x←x3、y←y3、d=(m-1)b、i←1
<ステップ302>
x'←x3、y'←y3
<ステップ303>
α←α27、β←β27
<ステップ304>
μ←α+x'+d、λ←-σβy'-μ2 
<ステップ305>
g1←λ-μρ-ρ2
<ステップ306>
α←α3、β←β3
<ステップ307>
μ←α+x+d、λ←-σβy-μ2 
<ステップ308>
g2←λ-μρ-ρ2
<ステップ309>
g←g1・g2、f←f9・g
<ステップ310>
d←d-2b
<ステップ311>
i←i+1, i=(m+1)/2であればステップ312に進み、異なればステップ303に戻る。
<ステップ312>
α←α3、β←β3
<ステップ313>
μ←α+x+b、λ←σβy-μ2 
<ステップ314>
g←λ-μρ-ρ2 
<ステップ315>
f←f3・g
<ステップ316>
q'=q3としてe(P,φ(Q))=fq'-1を計算する。
<ステップ317>
e(P,φ(Q))を出力する。
【００４７】
以上述べたように、本実施形態では1/3乗演算を行う必要がなく、繰り返し計算2回分を1回分にまとめる(ステップ303〜311)ことによりGF(q)上の乗算回数の削減が可能となる。
【００４８】
次に本実施形態を用いたIDベース公開鍵暗号を構成する際必要となる公開パラメータおよびマスター鍵生成装置について、図4を用いて説明する。
【００４９】
鍵生成装置401は、制御演算部402およびデータ保持部403から構成される。制御演算部402は、セキュリティパラメータを入力し、生成された公開パラメータおよびマスター鍵を出力する入出力部404、公開パラメータおよびマスター鍵生成装置401全体を制御する制御部405、楕円曲線の生成、lねじれ群およびその点Pを選択する楕円曲線生成部407、乱数を生成する乱数生成部408、マスター鍵を生成するマスター鍵生成部409、楕円曲線上の点の整数倍を計算する楕円曲線スカラー倍演算部410、ハッシュ関数を生成するハッシュ関数選択部411から構成される。
【００５０】
データ保持部403は入出力部により入力された楕円曲線のパラメータ、ベースポイント及びその位数、定義体情報を保持する楕円曲線情報保持部408、制御演算部で生成されたマスター鍵を保持するマスター鍵保持部414、制御演算部で生成された公開パラメータを保持する公開パラメータ保持部415から構成される。
【００５１】
次に各々の動作は制御部405により制御されているものとして動作の流れを説明する。入出力部404により入力された情報は入力情報保持部412に保持される。次にパラメータ生成部406において入力情報保持部412、ハッシュ情報保持部413で保持されている情報を用いて公開パラメータおよびマスター鍵生成処理を行い公開パラメータおよびマスター鍵を生成する。公開パラメータおよびマスター鍵生成処理は図5に示すフローチャートに従って行われるものとする。次にマスター鍵sをマスター鍵保持部414において保持する。
【００５２】
次に公開パラメータparams=<m,E[l](GF(q)),GF(q6),P,Ppub,H1,H2>を公開パラメータ保持部415において保持する。最後に公開パラメータおよびマスター鍵生成装置401は入出力部404により公開パラメータparamsおよびマスター鍵sを出力する。
【００５３】
図4のパラメータ生成部506で行われる公開パラメータおよびマスター鍵生成処理のフローチャートを図6に示す。以下、処理の流れを説明する。
<ステップ501>
mを6と互いに素な正整数、b=±1、を選択しGF(q)上の楕円曲線E:y2=x3-x+bとする。さらにlねじれ群E[l](GF(q))およびその元Pを選択する。
<ステップ502>
ランダムにマスター鍵s∈ Zl*を生成する。
<ステップ503>
Ppub=sPを計算する。
<ステップ504>
ハッシュ関数H1:{0,1}*→E[l](GF(q))を選択する。
<ステップ505>
整数nに対してハッシュ関数H2:GF(q6)→{0,1}nを選択する。
<ステップ506>
マスター鍵sを出力する。
<ステップ507>
公開パラメータparams=<m,E[l](GF(q)),GF(q6),P,Ppub,H1,H2>を出力する。
【００５４】
次に本実施形態を用いたIDベース公開鍵暗号を構成する際必要となる秘密鍵生成装置について図6を用いて説明する。
【００５５】
秘密鍵生成装置601は、制御演算部602およびデータ保持部603から構成される。制御演算部602は、公開パラメータparamsおよびマスター鍵s、任意の文字列である公開鍵IDを入力し、IDに対応する秘密鍵を出力する入出力部604、秘密鍵生成装置601全体を制御する制御部605、秘密鍵生成処理を行う秘密鍵生成部606、また秘密鍵生成部は公開パラメータで指定されているハッシュ関数H1を用いてハッシュ値を生成するハッシュ値生成部607、楕円曲線上の点の整数倍を計算する楕円曲線スカラー倍演算部608から構成される。
【００５６】
データ保持部603は入出力部604により入力された公開鍵IDを保持する公開鍵情報保持部609、同様に入出力部により入力された公開パラメータparamsを保持する公開パラメータ保持部610、秘密鍵生成に用いるマスター鍵sを保持するマスター鍵保持部611、秘密鍵生成部606で生成された秘密鍵を保持する秘密鍵保持部612から構成される。
【００５７】
次に各々の動作は制御部605により制御されているものとして動作の流れを説明する。入出力部604により入力された公開鍵は公開鍵保持部609に保持される。入出力部604により入力された公開パラメータparamsは公開パラメータ保持部610に保持される。入出力部604により入力されたマスター鍵sはマスター鍵情報保持部611に保持される。次に秘密鍵生成部606において公開鍵保持部609、公開パラメータ保持部610、マスター鍵保持部611で保持されている情報を用いて秘密鍵生成処理を行い秘密鍵を生成する。秘密鍵生成処理は図7に示すフローチャートに従って行われるものとする。最後に秘密鍵生成部606で作成された秘密鍵を秘密鍵保持部612に保持するとともに入出力部604より出力する。
【００５８】
図6の秘密鍵生成部606で行われる秘密鍵生成処理のフローチャートを図7に示す。以下公開鍵ID、マスター鍵sとして説明を行う。
<ステップ701>
QID=H1(ID)を計算する。
<ステップ702>
dID=sQIDを計算する。
<ステップ703>
dIDを秘密鍵として出力する。
【００５９】
次に本実施形態を用いた暗号化装置について、図8を用いて説明する。
【００６０】
暗号化装置801は、制御演算部802およびデータ保持部803から構成される。制御演算部802は、公開鍵、公開パラメータ、暗号化対象データを入力し、暗号化データを出力する入出力部804、暗号化装置801全体を制御する制御部805、暗号化を行う暗号化部806、また暗号化部はハッシュ値生成部807、乱数を生成する乱数生成部808、楕円曲線上の点のスカラー倍を行う楕円曲線スカラー倍演算部809、楕円曲線上のTateペアリングを計算するペアリング演算部810、および排他的論理和を行う排他的論理和演算部811から構成される。
【００６１】
データ保持部803は入出力部804により入力された公開鍵を保持する公開鍵保持部812、入出力部804により入力された公開パラメータを保持する公開パラメータ保持部813、入出力部804により入力された暗号化対象データを保持する暗号化対象データ保持部814、暗号化部806において生成された暗号化データを保持する暗号化データ保持部814から構成される。
【００６２】
次に各々の動作は制御部805により制御されているものとして動作の流れを説明する。入出力部804により入力された公開鍵は公開鍵保持部812に保持される。入出力部804により入力された公開パラメータは公開パラメータ保持部813に保持される。入出力部804により入力された暗号化対象データは暗号化対象データ保持部814に保持される。次に暗号化部において公開鍵保持部812、公開パラメータ保持部813、暗号化対象データ保持部814で保持されている情報を用いて暗号化処理を行い暗号化データを生成する。暗号化処理は図9に示すフローチャートに従って行われるものとする。最後に暗号化部806において暗号化された暗号化データを暗号化データ保持部815に保持するとともに入出力部804より出力する。
【００６３】
図8の暗号化部806で行われる暗号化処理のフローチャートを図9に示す。以下公開鍵ID、暗号化対象データMとして説明を行う。
<ステップ901>
QID=H1(ID)を計算する。
<ステップ902>
ランダムにrを選択する。
<ステップ903>
C1=rPを計算する。
<ステップ904>
gID=e(QID,φ(Ppub))を計算する。
<ステップ905>
h=H2(gIDr)を計算する。
<ステップ906>
C2=M XOR hを計算する。
<ステップ907>
暗号化データC=(C1,C2)を出力する。
【００６４】
次に本実施形態を用いた復号装置について、図10を用いて説明する。
【００６５】
復号装置1001は、制御演算部1002およびデータ保持部1003から構成される。制御演算部1002は、秘密鍵、公開パラメータ、復号対象データを入力し、復号データを出力する入出力部1004、復号装置1001全体を制御する制御部1005、復号を行う復号部1006、また復号部はハッシュ値生成部1007、楕円曲線上の点のスカラー倍を行う楕円曲線スカラー倍演算部1008、楕円曲線上のテートペアリングを計算するペアリング演算部1009、および排他的論理和を行う排他的論理和演算部1010から構成される。
【００６６】
データ保持部1003は入出力部1004により入力された秘密鍵を保持する秘密鍵保持部1011、入出力部1004により入力された公開パラメータを保持する公開パラメータ保持部1012、入出力部1004により入力された復号対象データを保持する復号対象データ保持部1013、復号部1006において復号された復号データを保持する復号データ保持部1014から構成される。
【００６７】
次に各々の動作は制御部1005により制御されているものとして動作の流れを説明する。入出力手段1004により入力された秘密鍵は秘密鍵保持部1011に保持される。入出力手段1004により入力された公開パラメータは公開パラメータ保持部1012に保持される。入出力手段1004により入力された復号対象データは復号対象データ保持部1013に保持される。次に復号部において秘密鍵保持部1011、公開パラメータ保持部1012、暗号化データ保持部1013で保持されている情報を用いて復号処理を行い復号結果を生成する。復号処理は図11に示すフローチャートに従って行われるものとする。最後に復号部1006において復号された復号データを復号データ保持部1014に保持するとともに入出力部1004より出力する。
【００６８】
図10の復号部1006で行われる復号処理のフローチャートを図11に示す。以下秘密鍵dID、復号対象データC=(C1,C2)として説明を行う。
<ステップ1101>
g=e(dID,φ(C1))を計算する。
<ステップ1102>
h=H2(g)を計算する。
<ステップ1103>
M=C2 XOR hを計算する。
<ステップ1104>
Mを出力する。
【図面の簡単な説明】
【００６９】
【図１】実施形態のシステム機能構成図である。
【図２】実施形態における動作説明フローチャートである。
【図３】実施形態における楕円曲線上のペアリング演算動作説明フローチャートである。
【図４】実施形態における公開パラメータおよびマスター鍵生成装置の構成図である。
【図５】実施形態における公開パラメータおよびマスター鍵生成装置の動作説明フローチャートである。
【図６】実施形態における秘密鍵生成装置の構成図である。
【図７】実施形態における秘密鍵生成装置の動作説明フローチャートである。
【図８】実施形態における暗号化装置の構成図である。
【図９】実施形態における暗号化装置の動作説明フローチャートである。
【図１０】実施形態における復号装置の構成図である。
【図１１】実施形態における復号装置の動作説明フローチャートである。
【符号の説明】
【００７０】
101:楕円曲線テートペアリング演算装置、102:制御演算部、103:データ保持部、104:入出力部、105:制御部、106:ペアリング演算部、107:演算対象データ保持部、108:楕円曲線情報保持部、109:中間データ保持部、110:演算結果保持部、401:公開パラメータおよびマスター鍵生成装置、402:制御演算部、403:データ保持部、404:入出力部、405:制御部、406:パラメータ生成部、407:楕円曲線生成部、408:乱数生成部、409:マスター鍵生成部、410:楕円曲線スカラー倍演算部、411:ハッシュ関数選択部、412:入力情報保持部、413:ハッシュ情報保持部、414:マスター鍵保持部、415:公開パラメータ保持部、601:秘密鍵生成装置、602:制御演算部、603:データ保持部、604:入出力部、605:制御部、606:秘密鍵生成部、607:ハッシュ演算部、608:楕円曲線スカラー倍演算部、609:公開鍵保持部、610:公開パラメータ保持部、611:マスター鍵保持部、613:秘密鍵保持部、801:暗号化装置、802:制御演算部、803:データ保持部、804:入出力部、805:制御部、806:暗号化部、807:ハッシュ値生成部、808:乱数生成部、809:楕円曲線スカラー倍演算部、810:ペアリング演算部、811:排他的論理和演算部、812:公開鍵保持部、813:公開パラメータ保持部、814:暗号化対象データ保持部、815:暗号化データ保持部、1001:復号装置、1002:制御演算部、1003:データ保持部、1004:入出力部、1005:制御部、1006:復号部、1007:ハッシュ値生成部、1008:楕円曲線スカラー倍演算部、1009:ペアリング演算部、1010:排他的論理和演算部、1011:秘密鍵保持部、1012:公開パラメータ保持部、1013:復号対象データ保持部、1014:復号データ保持部
【図１】
2006178125.tif 000003
【図２】
2006178125.tif 000004
【図３】
2006178125.tif 000005
【図４】
2006178125.tif 000006
【図５】
2006178125.tif 000007
【図６】
2006178125.tif 000008
【図７】
2006178125.tif 000009
【図８】
2006178125.tif 000010
【図９】
2006178125.tif 000011
【図１０】
2006178125.tif 000012
【図１１】
2006178125.tif 000013