リカバリ署名システム、署名生成装置、署名検証装置、それらの方法、及びプログラム
【課題】公開鍵の取得や管理の煩雑さを軽減し、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名技術を提供する。
【解決手段】署名生成装置10が、整数yを選択し、R=e(P1,P2)y、h=H1(rec|R|id)、v=H2(h|R|id)、r=h|(v(+)rec)、u=H3(r|Mclr|id)、t=u mod p、σ=y・P1−t・Sidを算出し、署名情報(r,σ)を送信する。また、署名検証装置20が、署名情報(r’,σ’)を受信し、u’=H3(r’|Mclr|id)、t=u’ mod p、R’=e(σ’,P2)・e(Pid,mp)t’を算出し、r’からビット列h’,x’を抽出し、v’=H2(h’|R’|id)、rec’=v’(+)x’、h’’=H1(rec’|R’|id)を算出し、h’=h’’であるか否かを判定する。
【解決手段】署名生成装置10が、整数yを選択し、R=e(P1,P2)y、h=H1(rec|R|id)、v=H2(h|R|id)、r=h|(v(+)rec)、u=H3(r|Mclr|id)、t=u mod p、σ=y・P1−t・Sidを算出し、署名情報(r,σ)を送信する。また、署名検証装置20が、署名情報(r’,σ’)を受信し、u’=H3(r’|Mclr|id)、t=u’ mod p、R’=e(σ’,P2)・e(Pid,mp)t’を算出し、r’からビット列h’,x’を抽出し、v’=H2(h’|R’|id)、rec’=v’(+)x’、h’’=H1(rec’|R’|id)を算出し、h’=h’’であるか否かを判定する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、情報セキュリティ技術の応用技術に関し、特に、署名からメッセージが復元できるメッセージ復元署名に関する。
【背景技術】
【0002】
メッセージ復元署名の従来技術として非特許文献1に示すものがある。この方式は、ランダムオラクルモデルで安全性が証明される方式である。以下にこの方式の概要を示す。
【0003】
この方式では、
メッセージM∈{0,1}k2
関数F1:{0,1}k2→{0,1}k1
関数F2:{0,1}k1→{0,1}k2
関数F:{0,1}k1+k2→{0,1}k
E:有限体Fq上で定義された楕円曲線
p:楕円曲線E上の点Rに対してp・R=O(Oは無限遠点)を満たす素数
G1:楕円曲線E上の位数pの部分集合の点
w∈Z/pZ
秘密鍵:x∈Z/pZ
公開鍵:(Fq,E,G1,Y)(Y=−x・G1(∈E))
とする。なお、{0,1}δは、2進δ桁のビットデータを示し、{0,1}δ→{0,1}εは、2進δ桁のビットデータから2進ε桁のビットデータへの写像である関数を示す。
【0004】
<署名生成>
署名生成は以下のように行う。ただし、Rxは点R∈Eのx座標を示し、(+)は排他的論理和演算子を示す。
【0005】
M’=F1(M)|(F2(F1(M))(+)M) …(1)
Rx=(w・G1)x
r=Rx(+)M’ …(2)
c=F(r)
z=w+c・x mod p
署名Sign=(r,z)
【0006】
<署名検証>
署名検証は以下のように行う。ただし、[M’]k1はM’の先頭k1ビットを示し、[M’]k2はM’の残りのk2ビットを示す。
【0007】
M’=r(+)(z・G1+F(r)・Y)x
M=[M’]k2(+)F2([M’]k1)
[M’]k1=F1(M)であれば検証合格
【非特許文献1】Masayuki Abe, Tatsuaki Okamoto, "A Signature Scheme with Message Recovery as Secure as Discrete Logarithm," ASIACRYPT 1999, pp.378-389
【発明の開示】
【発明が解決しようとする課題】
【0008】
しかし、非特許文献1の方式では、署名検証を行う署名検証装置が、署名生成を行った署名生成装置の公開鍵を取得する必要がある。従来の構成の場合、公開鍵は署名生成装置ごとに異なるため、その取得や管理が煩雑であった。
【0009】
また、非特許文献1の方式では、式(1)の(F2(F1(M))や式(2)のRxのビット長が固定長であり、メッセージMのビット長も固定長としなければならない。特に、式(2)のRxは楕円曲線E上の点R∈Eのx座標であり、そのビット長は楕円曲線Eに依存する。しかしながら、メッセージMのビット長に応じ、Rxのビット長がM’(式(1)の演算結果)のビット長と等しくなるように楕円曲線Eを変更し、なおかつ、変更されたすべての楕円曲線Eにおいて安全性を確保することは容易ではない。
【0010】
このため、従来は、メッセージMの長さが固定長より短い場合であっても、それに併せて署名Signの一部分rのビット長を短くすることができず、非効率であった。また、メッセージMのビット長が固定長よりも長い場合には、式(1)にメッセージMの一部分しか代入することができず、メッセージMの全てのビットを対象としたメッセージ復元署名を構成できない。
【0011】
本発明はこのような点に鑑みてなされたものであり、公開鍵の取得や管理の煩雑さを軽減し、なおかつ、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名技術を提供することを目的とする。
【課題を解決するための手段】
【0012】
本発明の署名生成装置は、有限体Fq上の楕円曲線をEとし、楕円曲線E上の有理点からなる有限集合の要素数#Eを割り切る素数をpとし、楕円曲線E上のp等分点からなる有限集合をE[p]とし、有限体Fqを基礎体とする拡大体からなる有限集合をμpとし、有限集合E[p]の2つの元を有限集合μpの1つの元に写す非退化双線形ペアリング関数をe:E[p]×E[p]→μpとし、e(P1,P2)≠1を満たす有限集合E[p]の元をP1,P2∈E[p]とし、署名生成装置の識別子をidとし、識別子idに対応する有限集合E[p]の元をPidとし、整数であるマスター秘密鍵をmsとし、Pidの楕円曲線E上でのms倍点ms・Pidを署名生成装置の秘密鍵Sidとした場合における、当該秘密鍵Sidを格納する第1記憶部と、秘匿される署名対象のビット列である復元署名対象情報recを格納する第2記憶部と、任意の整数yを選択する任意数選択部と、双線形関数値R=e(P1,P2)y∈μpを算出する第1双線形関数演算部と、復元署名対象情報recのビット列と双線形関数値Rのビット列とを含むビット結合値αに対し、第1ハッシュ関数H1を作用させたハッシュ値h=H1(α)を算出する第1ハッシュ演算部と、ハッシュ値hのビット列と双線形関数値Rのビット列とを含むビット結合値βに対し、任意のビット長のビット列を復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を作用させたハッシュ値v=H2(β)を算出する第2ハッシュ演算部と、ハッシュ値vと復元署名対象情報recとの排他的論理和値xを算出する第1排他的論理和演算部と、ハッシュ値hのビット列を第1ビット位置に配置し、排他的論理和値xのビット列を第2ビット位置に配置したビット結合値rを算出するビット結合部と、ビット結合値rのビット列を含むビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する第3ハッシュ演算部と、予め定められた規則に従ってハッシュ値uに対して定まる整数をtとした場合における、元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sidを算出する楕円曲線演算部と、ビット結合値rと楕円曲線演算値σとからなる署名情報(r,σ)を送信する送信部と、を有する。
【0013】
以上のように本発明では、第2ハッシュ演算部が、任意のビット長のビット列を復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を用い、ビット結合値βを復元署名対象情報recとビット長が等しいハッシュ値vに変換する。ハッシュ関数の出力ビット長を変化させることは、楕円曲線Eを変更することに比べて大変容易である。そのため、本発明の署名生成装置では、復元署名対象情報recのあらゆるビット長に柔軟に対応した署名生成が可能となる。
【0014】
また、本発明の署名検証装置は、元P2と、元P2の楕円曲線E上でのms倍点ms・P2であるマスター公開鍵mpと、を格納する第3記憶部と、ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなる署名情報(r’,σ’)を受信する受信部と、第1パート情報r’と第2パート情報σ’を格納する第4記憶部と、署名生成装置の識別子idに対応する有限集合E[p]の元Pidを格納する第5記憶部と、第1パート情報r’のビット列を含むビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する第4ハッシュ演算部と、予め定められた規則に従ってハッシュ値u’に対して定まる整数をt’とした場合における、双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’∈μpを算出する第2双線形関数演算部と、第1パート情報r’の第1ビット位置のビット列h’と、第1パート情報r’の第2ビット位置のビット列x’とを抽出するビット分割部と、ハッシュ値h’のビット列と双線形関数値R’のビット列とを含むビット結合値β’に対し、第2ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する第5ハッシュ演算部と、ハッシュ値v’とビット列x’との排他的倫理和値を、署名対象情報の復元値rec’として算出する第2排他的論理和演算部と、署名対象情報の復元値rec’のビット列と双線形関数値R’のビット列とを含むビット結合値α’に対し、第1ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する第6ハッシュ演算部と、ビット列h’とハッシュ値h’’とが等しいか否かを判定する比較部と、を有する。
【0015】
この署名検証装置により、上述の署名生成装置が生成した署名を検証できる。また、本発明の署名検証装置は、複数の署名生成装置に共通するマスター公開鍵mpと、実際に署名生成を行った署名生成装置の識別子idとがあれば、署名検証と署名対象情報の復元とができる。そのため、実際に署名生成を行った署名生成装置ごとに異なる公開鍵を用いる従来構成に比べ、署名検証と署名対象情報の復元を行うために必要な鍵の取得や管理の煩雑さを軽減できる。
【発明の効果】
【0016】
本発明では、公開鍵の取得や管理の煩雑さを軽減し、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名を実現できる。
【発明を実施するための最良の形態】
【0017】
以下、図面を参照して本発明の実施形態を説明する。
〔記号・用語の定義〕
まず、各実施形態で使用する記号・用語を定義する。
【0018】
Z:整数集合。
k:k∈Z(Zの元)であるセキュリティパラメータ。
E:位数qの有限体Fq上で定義された楕円曲線。アフィン(affine)座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6 …(3)
(ただし、a1,a2,a3,a4,a6∈Fq)を満たす点(x,y)の集合に無限遠点と呼ばれる特別な点Oを付加したもので定義される。楕円曲線E上の任意の2点に対して楕円加算と呼ばれる二項演算+及び楕円曲線E上の任意の1点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、この楕円加算に関して群をなすこと及び楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている(例えば、参考文献1“イアン・F・ブラケ、ガディエル・セロッシ、ナイジェル・P・スマート=著、「楕円曲線暗号」、出版=ピアソン・エデュケーション、ISBN4-89471-431-0”等参照)。
【0019】
#E:楕円曲線E上の有理点からなる有限集合の要素数。有限体Fq上で定義された楕円曲線Eの有理点の個数#Eは有限である。
p:#Eを割り切る大きい素数。
E[p]:楕円曲線Eのp等分点からなる有限集合。楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A=Oを満たす点Aの有限集合として定義される。E[p]はEの部分群である。
μp:有限体Fqを基礎体とする拡大体である有限集合。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。
e:非退化双線形ペアリング(pairing)関数(以下「ペアリング関数」と呼ぶ)であり、以下の式で定義される。
E[p]×E[p]=μp …(4)
【0020】
ペアリング関数eは次の性質を持つ。
[性質1]E[p]上の任意の点A1に対して、e(A1,A1)=1が成り立つ。
[性質2]E[p]上の任意の2点A1、A2に対して、e(A1,A2)=e(A2,A1)−1が成り立つ。
[性質3]E[p]上の任意の3点A1,A2,A3に対して、e(A1+A2,A3)=e(A1,A3)e(A2,A3)であり、e(A1,A2+A3)=e(A1,A2)e(A1,A3)が成り立つ。
[性質4]E[p]上の任意の点A1に対して、e(A1,O)=1が成り立つ。
[性質5]E[p]上のある点A1がE[p]上のすべての点A2に対して、e(A1,A2)=1を満たすなら、A1=Oが成り立つ。
【0021】
なお、ペアリング関数eの具体例としては、WeilペアリングやTateペアリングなどを挙げることができる(例えば、参考文献2「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp. 61-81」等参照)。また、ペアリング関数が効率的に計算可能な非超特異楕円曲線(non-supersingular curve)の生成方法については、参考文献3「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献4「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献5「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」などに開示されている。また、ペアリング関数をコンピュータ上で計算するためのアルゴリズムとしては、周知のMiller のアルゴリズム(参考文献6「V. S. Miller, “Short Programs for functions on Curves,” [online],1986,[2008年6月13日検索],インターネット<http://crypto.stanford.edu/miller/miller.pdf>」などが存在する。
【0022】
P1,P2:e(P1,P2)≠1を満たす有限集合E[p]の元。
<P1>:P1を生成元とする巡回群。
<P2>:P2を生成元とする巡回群。
IDencode:任意のビット列を<P1>に移す衝突困難な関数{0,1}*→<P1>。IDencodeの例は以下の通りである。
【0023】
《IDencodeの例1》関数H:{0,1}*→Fqを衝突困難な関数とする。このような関数は、例えばSHA−1などのハッシュ関数の出力を一定の方法で有限体Fqの元に対応させることで得られる。cを自然数で、#E=c・pとなるものとする。cは通常cofactorと呼ばれる。以上の準備の下で、以下のアルゴリズムを実行する関数をIDencodeとする。
【0024】
処理1.ran←0
処理2.入力isに対してx1=H(is|ran)を計算する。
処理3.y1∈Fqに関して、(x1,y1)∈Eとなる条件から導かれる2次方程式を解く。解y1が存在するならば、処理5に進む。
処理4.ran←ran+1として処理2に戻る。
処理5.点(x1,y1)∈Eをc倍してその結果を出力する。#E=c・pであり、楕円曲線E上の任意の点をc・p倍すると無限遠点Oとなるため、点(x1,y1)∈Eをc倍した点はE[p]の元となる。
【0025】
《IDencodeの例2》<P1>の元をD個選択し、それらをそれぞれ0以上D−1以下の整数dに対応付け、選択された<P1>の各元をSPd∈<P1>とする。また、入力された任意のビット列に対してDビットのハッシュ値を出力とするハッシュ関数H0を用意する。入力された任意のビット列にハッシュ関数H0を作用させて得られたDビットのビット列の上位からdビット目をhd∈{0,1}とする。そして、入力された任意のビット列に対してΣd=0D−1hd・SPdを出力する関数をIDencodeとする。
【0026】
Mrec:署名対象となるメッセージの復元部分である任意のビット長のリカバリーメッセージMrec∈{0,1}*。なお、メッセージの復元部分とは、メッセージのうち一旦秘匿され、署名検証装置で復元される情報を意味する。つまり、リカバリーメッセージMrecは、秘匿される署名対象のビット列である。
【0027】
Mclr:署名対象となるメッセージの非復元部分である任意のビット長のクリアーメッセージMclr∈{0,1}*。なお、メッセージの非復元部分とは、メッセージのうち秘匿されることなく署名検証装置に開示される情報を意味する。つまり、クリアーメッセージMclrは秘匿されない署名対象のビット列である。
【0028】
encode:任意のビット長のビット列を入力ビット長に応じたビット長のビット列に変換する関数{0,1}*→{0,1}*。ただし、encodeの出力ビット長をL(Lは1以上の整数)とする。encodeの例は後述する。
【0029】
decode:encodeの逆関数。
rec:署名検証装置によって復元されるビット列である復元署名対象情報rec=encode(Mrec)。
rounddown{*}: *の小数点以下を切り捨てる関数。
length(*): *のビット長を求める関数。その出力ビット長は一定である。
delete{δ,ε}:εのビットを先頭からδビットだけ削除する関数。
【0030】
H1:任意のビット長のビット列をNビットのビット列に変換するハッシュ関数{0,1}*→{0,1}N。ただし、Nは1以上の整数。なお、ハッシュ関数の具体例としては、SHA−1やそれを利用した一方向性関数を例示できる。
H2:出力長可変のハッシュ関数H2:{0,1}*×N→{0,1}*である。任意のL∈Nについて、任意のω∈{0,1}*に対する出力値H2(ω,L)は長さLのビット列となる。なお、以下では、H2(ω,L)をH2(ω)と表記する。
H3:ハッシュ関数。
【0031】
b|c:ビット列bとビット列cとのビット結合値。
b(+)c:bとcとの排他的論理和。
Z/pZ:pを法とする剰余類。各実施形態では、その代表元をZ/pZと表現する。また、代表元の一例は、0以上p−1以下の整数である。
(Z/pZ)\{0}:Z/pZから0を除いた集合。各実施形態では、1以上p−1以下の整数を(Z/pZ)\{0}とする。
ms:IDベース暗号のマスター秘密鍵ms∈Z/pZ。なお、IDベース暗号については、例えば、参考文献7「D. Boneh and M. Franklin, "Identify-based encryption from the Weil pairing", Advances in Cryptology 0 CRYTPO '01, volume 2139 of LNCS, pages 213-229. Springer, 2001.」などに開示されている。
【0032】
mp:IDベース暗号のマスター公開鍵mp=ms・P2∈<P2>。
id:署名生成装置の識別子id∈{0,1}*。
Pid:idに対応する楕円曲線E上の点Pid=IDencode(id)∈<P1>。
Sid:署名生成装置の秘密鍵Sid=ms・Pid∈<P1>。
【0033】
〔第1実施形態〕
本発明の第1実施形態を説明する。
【0034】
<構成>
図1は、第1実施形態のリカバリ署名システム1を説明するためのシステム構成図である。また、図2は、第1実施形態の署名生成装置10の詳細構成を説明するためのブロック図である。図3は、第1実施形態におけるハッシュ演算部10iの詳細構成の一例を説明するためのブロック図である。図4は、第1実施形態の署名検証装置20の詳細構成を説明するためのブロック図である。図5は、第1実施形態の管理装置30の詳細構成を説明するためのブロック図である。
【0035】
図1に示すように、本形態のリカバリ署名システム1は、署名を生成する署名生成装置10と、署名を検証する署名検証装置20と、リカバリ署名システム1を管理する第三者機関の装置である管理装置30とを有し、それらはネットワーク40を通じて通信可能に接続されている。なお、説明の簡略化のため、図1では署名生成装置10及び署名検証装置20を1つずつ記述しているが、署名生成装置10や署名検証装置20が2以上存在してもよい。同様に、管理装置30が2以上存在してもよい。
【0036】
図2に示すように、本形態の署名生成装置10は、メモリ10a(「第1記憶部」「第2記憶部」「第6記憶部」)と、一時メモリ10bと、制御部10cと、入力部10dと、符号化部10eと、任意数選択部10fと、双線形関数演算部10g(「第1双線形関数演算部」)と、ハッシュ演算部10h(「第1ハッシュ演算部」)と、ハッシュ演算部10i(「第2ハッシュ演算部」)と、排他的論理和演算部10j(「第1排他的論理和演算部」)と、ビット結合部10kと、ハッシュ演算部10m(「第3ハッシュ演算部」)と、剰余演算部10nと、判定部10p,10rと、楕円曲線演算部10qと、通信部10s(「送信部」)とを有する。また、図3に示す例では、ハッシュ演算部10iは、ハッシュ回数演算部10iaと、部分ハッシュ演算部10ibと、ビット結合部10icと、ビット削除部10idとを有する。なお、本形態の署名生成装置10は、CPU(Central Processing Unit)やRAM(Random Access Memory)などからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。ここで、メモリ10aや一時メモリ10bは、例えば、RAM、レジスタ、補助記憶装置、或いはこれらを結合した記憶領域である。また、制御部10cと、符号化部10eと、任意数選択部10fと、双線形関数演算部10gと、ハッシュ演算部10h,10i,10mと、排他的論理和演算部10jと、ビット結合部10kと、剰余演算部10nと、判定部10p,10rと、楕円曲線演算部10qとは、例えば、CPUが所定のプログラムを実行して構築される処理手段である。また、入力部10dは、キーボード、マウス、入力ポートなどの入力インタフェースである。また、通信部10sは、所定のプログラムを実行するCPUの制御のみと駆動するLANカード、モデム等の通信手段である。また、署名生成装置10は、制御部10cの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ10bに読み書きされる。
【0037】
また、図4に示すように、本形態の署名検証装置20は、メモリ20a(「第3記憶部」「第4記憶部」「第5記憶部」「第7記憶部」)と、一時メモリ20bと、制御部20cと、通信部20d(「受信部」)と、ハッシュ演算部20e(「第4ハッシュ演算部」)と、剰余演算部20fと、識別子符号化部20gと、双線形関数演算部20h(「第2双線形関数演算部」)と、判定部20iと、ビット分割部20jと、ハッシュ演算部20k(「第5ハッシュ演算部」)と、排他的論理和演算部20m(「第2排他的論理和演算部」)と、ハッシュ演算部20n(「第6ハッシュ演算部」)と、比較部20pと、復号部20qと、出力部20rと、入力部20sとを有する。なお、本形態の署名検証装置20は、CPUやRAMからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。ここで、メモリ20aや一時メモリ20bは、例えば、RAM、レジスタ、補助記憶装置、或いはこれらを結合した記憶領域である。また、制御部20cと、ハッシュ演算部20eと、剰余演算部20fと、識別子符号化部20gと、双線形関数演算部20hと、判定部20iと、ビット分割部20jと、ハッシュ演算部20kと、排他的論理和演算部20mと、ハッシュ演算部20nと、比較部20pと、復号部20qとは、例えば、CPUが所定のプログラムを実行して構築される処理手段である。また、通信部20dは、所定のプログラムを実行するCPUの制御のみと駆動するLANカード、モデム等の通信手段である。また、出力部20rは、ディスプレイ、出力ポートなどの出力インタフェースであり、入力部20sは、キーボード、マウス、入力ポートなどの入力インタフェースである。また、署名検証装置20は、制御部20cの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ20bに読み書きされる。
【0038】
また、図5に示すように、管理装置30は、メモリ30aと、一時メモリ30bと、制御部30cと、マスター秘密鍵生成部30dと、マスター公開鍵生成部30eと、識別子符号化部30fと、秘密鍵生成部30gと、通信部30hとを有する。本形態の管理装置30は、CPUやRAMからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。
【0039】
<処理>
次に本形態の処理について説明する。
[前処理]
まず、前処理として、第三者機関が、セキュリティパラメータk∈Zに対してkビット安全性が担保されるように、楕円曲線Eと、#Eを割り切る大きい素数pと、ペアリング関数eと、元P1,P2と、関数IDencodeと、関数encodeと、関数decodeと、ハッシュ関数H1,H2,H3とを設定する。
【0040】
設定された楕円曲線Eとペアリング関数eと関数encodeとハッシュ関数H1,H2,H3は、例えば、署名生成装置10を構成するためのプログラムに記述され、素数pと元P1,P2とは、例えば、署名生成装置10のメモリ10aに格納され、これらは署名生成装置10が利用可能な状態にされる。また、設定された楕円曲線Eとペアリング関数eと関数IDencodeと関数decodeとハッシュ関数H1,H2,H3は、例えば、署名検証装置20を構成するためのプログラムに記述され、素数pと元P2とは、例えば、署名検証装置20のメモリ20aに格納され、これらは署名検証装置20が利用可能な状態にされる。さらに、設定された楕円曲線Eと関数encodeと関数IDencodeとは、例えば、管理装置30を構成するためのプログラムに記述され、素数pと元P1,P2とは、例えば、管理装置30のメモリ30aに格納され、これらは管理装置30が利用可能な状態にされる。
【0041】
また、管理装置30のマスター秘密鍵生成部30dが、マスター秘密鍵ms∈UZ/pZを一様ランダムに選択し、それをメモリ30aに安全に格納する。次に、マスター公開鍵生成部30eが、メモリ30aからマスター秘密鍵msと元P2とを読み込み、楕円曲線E上の点である元P2を楕円曲線E上でmsし、その演算結果mp=ms・P2∈<P2>をマスター公開鍵mpとしてメモリ30aに格納する。このように生成されたマスター公開鍵mpは、署名検証装置20にも配信され、署名検証装置20のメモリ20aに格納される。
【0042】
[秘密鍵生成処理]
次に、管理装置30が署名生成装置10の秘密鍵を生成する秘密鍵生成処理を説明する。秘密鍵生成処理は、前処理において実行されてもよいし、署名生成装置10が署名生成を行うたびに実行されてもよいし、所定の契機で定期的又は不定期的に実行されてもよい。
【0043】
秘密鍵生成処理では、まず、署名生成装置10の入力部10dに署名生成装置10の識別子idが入力される。識別子idの例は、署名生成装置10のメールアドレス、URL、電話番号、位置情報、時刻情報、ユーザ名などである。入力された識別子idはメモリ10aに格納される。また、識別子idは、秘密鍵発行要求情報とともに通信部10qからネットワーク40経由で管理装置30に送信される。これらの情報は管理装置30の通信部30hで受信され、識別子idはメモリ30aに格納される。次に、識別子idは識別子符号化部30fに読み込まれ、識別子符号化部30fは識別子idを関数IDencodeに入力し、楕円曲線E上の点Pid=IDencode(id)を算出する。これは有限集合E[p]の元である。楕円曲線E上の点Pidはメモリ30aに格納され、さらに秘密鍵生成部30gに読み込まれる。秘密鍵生成部30gは、楕円曲線E上の点Pidを楕円曲線E上でms倍した署名生成装置10の秘密鍵Sid=ms・Pidを生成し、秘密鍵Sidをメモリ30aに格納する。生成された秘密鍵Sidは通信部30hに送られ、専用回線や公知の公開鍵暗号や共通鍵暗号などを用い、署名生成装置10に安全に送信される。秘密鍵Sidは署名生成装置10の通信部10qで受信され、メモリ10aに安全に格納される。
【0044】
[署名生成処理]
次に、署名生成装置10の署名生成処理を説明する。この処理の前提として、署名生成装置10のメモリ10aに元P1,P2と素数pと署名生成装置10の秘密鍵Sidと識別子idとが格納されているものとする。
【0045】
図6は、第1実施形態の署名生成処理を説明するためのフローチャートである。以下、この図に従って本形態の署名生成処理を説明する。
【0046】
まず、入力部10dに、署名対象となるリカバリーメッセージMrec及びクリアーメッセージMclrが入力され、これらがメモリ10aに格納される(ステップS1)。次に、符号化部10eが、メモリ10aからリカバリーメッセージMrecを読み込み、関数encodeを用いて符号化し、Lビットの復元署名対象情報rec=encode(Mrec)を生成する。以下に関数encodeの具体例を示す。
【0047】
[関数encodeの具体例の説明]
関数encodeは、任意の入力ビット列に対し、セキュリティパラメータkに対応した安全性が得られるビット長の復元署名対象情報recを出力する可逆な関数(逆関数が存在する関数)である。セキュリティパラメータkに対応した安全性が得られるビット長が72ビット以上であった場合の関数encodeの一例は以下の通りである。
【0048】
《length(Mrec)が72ビット未満の場合》
encode(Mrec)=length(Mrec)|Mrec|0…0 …(4)
(ただし、Mrec|0…0のビット長は72ビットである。)
【0049】
《length(Mrec)が72ビット以上の場合》
encode(Mrec)=0xff|Mrec …(5)
(ただし、0xffは、付加ビットが追加されていないことを示すヘッダ情報である。また、0xffのビット長BLは関数lengthの出力ビット長BLと等しい。)
この場合、関数decodeの演算は以下のようになる。
【0050】
《recの先頭BLビットが0xffである場合》
recから先頭BLビットを除いたビット列を出力する。
【0051】
《recの先頭BLビットが0xffでない場合》
recの先頭BLビットが0xffでない場合には、recから先頭BLビットに示されるビット長だけ、recの先頭BLビットより下位のビット列を抽出して出力する( [関数encodeの具体例の説明]終わり)。
【0052】
生成された復元署名対象情報recは、メモリ10aに格納される(ステップS2)。次に、任意数選択部10fが乱数y∈(Z/pZ)\{0}を選択し、それをメモリ10aに格納する(ステップS3)。なお、乱数の選択は、例えば、SHA-1等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて行う。
【0053】
次に、双線形関数演算部10gが、メモリ10aから元P1,P2と乱数yとを読み込み、ペアリング関数eを用いて双線形関数値R=e(P1,P2)y∈μpを算出し、双線形関数値Rをメモリ10aに格納する(ステップS4)。なお、e(P1,P2)y∈μpは有限体Fqを基礎体とする標数qのm(m≧2)次の拡大体Fqm上の演算である。拡大体Fqmの元は、有限体Fqの元を係数とするαについてのm−1次多項式で表現できる。なお、αは有限体Fqの元を係数とする既約多項式の根である。また、この既約多項式のうち最小次数のものをfとし、拡大体Fqmの元を表現する2つの多項式をA(α),B(α)とすると、拡大体Fqm上の乗算は、C(α)=A(α)・B(α) mod f(α)と表現でき、多項式演算A(α)・B(α)とf(α)による除算とによって計算できる。なお、多項式演算A(α)・B(α)における各次数の係数間の演算は有限体Fq上の演算である。また、拡大体Fqm上のべき乗は、このような拡大体Fqm上の乗算をべき乗回繰り返すことを意味する。例えば、e(P1,P2)3∈μpは、e(P1,P2)・e(P1,P2)・e(P1,P2)∈μpを意味する。
【0054】
次に、ハッシュ演算部10hが、メモリ10aから復元署名対象情報recと双線形関数値Rと識別子idとを読み込み、それらの各ビット列のビット結合値α=rec|R|idに対し、ハッシュ関数H1を作用させたNビットのハッシュ値h=H1(α)を算出する(ステップS5)。生成されたハッシュ値hはメモリ10aに格納される。次に、ハッシュ演算部10iが、メモリ10aからハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列とを読み込み、それらの各ビット列のビット結合値β=h|R|idに対し、ハッシュ関数H2を作用させたLビットのハッシュ値v=H2(β)を算出する(ステップS6)。生成されたハッシュ値vはメモリ10aに格納される。以下にステップS6の詳細を例示する。
【0055】
[ステップS6の詳細処理の例]
図7は、ステップS6の詳細処理を例示するためのフローチャートである。
まず、ハッシュ演算回数算出部10ia(図3)が、記憶部10aから復元署名対象情報recを読み込み、
emax=rounddown{L/length(H)}, L=length(rec) …(6)
の演算を行ってemax
を一時メモリ10bに格納する(ステップS6a)。なお、HはSHA−1等の公知のハッシュ関数を意味し、length(H)はハッシュ関数Hの出力ビットのビット長を意味する。なお、Lが定数である場合にはemaxを事前計算しておくことも可能であり、その場合にはステップS6aの処理は不要となる。
【0056】
次に、制御部10cは変数eに0を代入し、変数eを一時メモリ10bに格納する(ステップS6b)。次に、部分ハッシュ演算部10ibが、一時メモリ10bから変数eを読み込み、記憶部10aからハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列とを読み込み、それらの各ビット列のビット結合値β=h|R|idに対し、ハッシュ値
H(e,β) …(7)
を算出して一時メモリ10bに格納する(ステップS6c)。
【0057】
次に、制御部10cが、一時メモリ10bからemaxと変数eとを読み込み、
e=emax …(8)
を満たすか否かを判断する(ステップS6d)。ここで、式(8)を満たさないのであれば、制御部10cはe+1を新たなeとし、新たなeを一時メモリ10bに格納した後(ステップS6e)、処理をステップS6cに戻す。一方、式(8)を満たすのであれば、制御部10cはビット結合部10icに指示を与え、ビット結合部10icは、一時メモリ10bから各ハッシュ値H(0,β),H(1,β),H(2,β),…,H(emax,β)を読み込み、それらのビット結合値
HC(β)=H(0,β)|・・・|H(emax,β) …(9)
を算出して一時メモリ10bに格納する(ステップS6f)。
【0058】
次に、ビット削除部10idが、一時メモリ10bから、ビット結合値HC(β)を読み込み、
v=H2(β)=delete{length(HC(β))- L,HC(β)} …(10)
を算出して記憶部10aに出力する(ステップS6g)。すなわち、HC(R)の先頭の数ビットを削除して全体のビット長をLとしたものをv=H2(β)とする。
【0059】
なお、ステップS6の処理方法はこれに限定されない。例えば、eを用いるのではなく、ハッシュチェインによってハッシュ値のビット長を拡張する方法でもよい。この場合、式(9)のHC(β)は、例えば、
HC(β)=H(β)|H(H(β))|H(H(H(β)))|…|H(H(H…(β)…))
であってもよい([ステップS6の詳細処理の例]の説明終わり)。
【0060】
次に、排他的論理和演算部10jが、メモリ10aからハッシュ値vと復元署名対象情報recとを読み込み、それらの排他的論理和値x=v(+)recを算出し、排他的論理和値xをメモリ10aに格納する(ステップS7)。次に、ビット結合部10kが、メモリ10aからハッシュ値hと排他的論理和値xとを読み込み、ハッシュ値hのビット列を第1ビット位置に配置し、排他的論理和値xのビット列を第2ビット位置に配置したN+Lビットのビット結合値rを算出する(ステップS8)。なお、第1ビット位置及び第2ビット位置はどのビット位置に設定されてもよいが、署名生成装置10で設定される第1ビット位置と、署名検証装置20で設定される第1ビット位置とは同一であり、かつ、署名生成装置10で設定される第2ビット位置と、署名検証装置20で設定される第2ビット位置とは同一であるものとする。また、第1ビット位置及び第2ビット位置の設定例は以下の通りである。
【0061】
[第1ビット位置及び第2ビット位置の設定例]
図9は、第1ビット位置及び第2ビット位置の設定例を説明する図である。
《例1》先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置とする(図9(a))。
《例2》先頭Lビットを第2ビット位置とし、残りNビットを第1ビット位置とする(図9(b))。
《例3》L個の奇数ビットを第2ビット位置とし、残りのNビットを第1ビット位置とする(図9(c))。
【0062】
なお、これらは一例であり、その他の設定も可能である([第1ビット位置及び第2ビット位置の設定例]の説明終わり)。
【0063】
次に、ハッシュ演算部10mが、メモリ10aからビット結合値rとクリアーメッセージMclrと識別子idとを読み込み、それらのビット結合値γ=r|Mclr|idに対し、ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する(ステップS9)。生成されたハッシュ値uはメモリ10aに格納される。次に、剰余演算部10nがメモリ10aからハッシュ値uと素数pとを読み込み、剰余演算t=u mod pを行い、その演算結果をメモリ10aに格納する(ステップS10)。次に、判定部10pがメモリ10aから演算結果tを読み込み、t=0であるか否かを判定する(ステップS11)。ここで、t=0であれば、処理がステップS3に戻され、乱数yを取り直して処理がやり直される。一方、t=0でなければ、楕円曲線演算部10qがメモリ10aから演算結果tと元P1と乱数yと秘密鍵Sidとを読み込み、元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sid∈E[p]を算出する(ステップS12)。算出された楕円曲線演算値σはメモリ10aに格納される。次に、判定部10rが、メモリ10aから楕円曲線演算値σを読み込み、それが無限遠点Oを示すか否かを判定する(ステップS13)。ここで、楕円曲線演算値σ=Oであれば、処理がステップS3に戻され、乱数yを取り直して処理がやり直される。一方、楕円曲線演算値σ=Oでなければ、制御部10cがメモリ10aから乱数yを削除する(ステップS14)。そして、クリアーメッセージMclrとビット結合値rと楕円曲線演算値σとが送信部10sに送られ、送信部10sは、クリアーメッセージMclrと署名情報(r,σ)とをネットワーク40経由で署名検証装置20に送信する(ステップS15)。
【0064】
[署名検証処理]
次に、署名検証装置20の署名検証処理を説明する。この処理の前提として、署名検証装置20のメモリ20aにマスター公開鍵mpと元P2と素数pとが格納されているものとする。
【0065】
図8は、第1実施形態の署名検証処理を説明するためのフローチャートである。以下、この図に従って本形態の署名検証処理を説明する。
【0066】
まず、署名検証装置20の通信部20dが、クリアーメッセージMclrと署名情報(r’,σ’)とを受信する(ステップS21)。なお、この署名情報が正当なものであれば署名情報(r’,σ’)=(r,σ)であるが、この時点ではそれが不明であるため、通信部20dが受信する署名情報を(r’,σ’)と表現する。受信された署名情報(r’,σ’)は、ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなり、これらはメモリ20aに格納される。次に、入力部20sに署名生成装置10の識別子idが入力され、メモリ20aに格納される(ステップS22)。なお、識別子idがすでにメモリ20aに格納されているのであれば、ステップS22は省略可能である。次に、ハッシュ演算部20eが、メモリ20aから第1パート情報r’とクリアーメッセージMclrと識別子idとを読み込み、これらのビット列のビット結合からなるビット列γ’=r’|Mclr|idに対し、ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する(ステップS23)。算出されたハッシュ値u’はメモリ20aに格納される。次に、剰余演算部20fが、メモリ20aからハッシュ値u’と素数pとを読み込み、剰余演算t’=u’ mod pを行い、その演算結果をメモリ20aに格納する(ステップS24)。次に、識別子符号化部20gが、メモリ20aから識別子idを読み込み、識別子idを関数IDencodeに入力し、楕円曲線E上の点Pid=IDencode(id)を算出する(ステップS25)。これは署名生成装置10の識別子idに対応する有限集合E[p]の元Pidである。生成された楕円曲線E上の点Pidはメモリ20aに格納される。次に、双線形関数演算部20hが、メモリ20aから、第2パート情報σ’と元P2と楕円曲線E上の点Pidとマスター公開鍵mpと演算結果t’を読み込み、ペアリング関数eを用いて双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’を算出する(ステップS26)。生成された双線形関数値R’はメモリ20aに格納される。次に、判定部20iが、メモリ20aから双線形関数値R’を読み込み、R’=1であるか否かを判定する(ステップS27)。ここで、R’=1であれば、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、R’=1でなければ、次に、ビット分割部20jが、メモリ20aから第1パート情報r’を読み込み、1パート情報r’の第1ビット位置のビット列h’と、第1パート情報r’の第2ビット位置のビット列x’とを抽出し(ステップS28)、それらをメモリ20aに格納する。なお、前述のように、第1ビット位置及び第2ビット位置は、署名生成装置10のビット結合部10kに設定されたものと同一とする。例えば、署名生成装置10のビット結合部10kで先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置としていたのであれば、ビット分割部20jも先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置として処理を行う。次に、ハッシュ演算部20kが、メモリ20aからハッシュ値h’と双線形関数値R’と識別子idとを読み込み、それらのビット列のビット結合値β’=h’|R’|idに対し、ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する(ステップS29)。算出されたハッシュ値v’はメモリ20aに格納される。次に、排他的論理和演算部20mが、メモリ20aからハッシュ値v’とビット列x’とを読み込み、それらの排他的倫理和値を、署名対象情報の復元値rec’として算出し(ステップS30)、算出された復元値rec’をメモリ20aに格納する。次に、ハッシュ演算部20nが、メモリ20aから署名対象情報の復元値rec’と双線形関数値R’と識別子idとを読み込み、それらのビット列のビット結合値α’=rec’|R’|idに対し、ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する(ステップS31)。算出されたハッシュ値h’’は、メモリ20aに格納される。次に、比較部20pがメモリ20aから、ビット列h’とハッシュ値h’’とを読み込み、これらが等しいか否かを判定する(ステップS32)。ここで、これらが等しくなければ、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、これらが等しければ、次に、復号部20qがメモリ20aから復元値rec’を読み込み、それをdecode関数に入力し、復号値Mrec’=decode(rec’)を算出し、それをメモリ20aに格納する(ステップS34)。ここで、復号値Mrec’が所定のフォーマットに従ったものでなければ、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、復号値Mrec’が所定のフォーマットに従ったものであれば、検証が成功ものとして、復号値Mrec’が出力部20rに送られ、そこから出力される(ステップS35)。
【0067】
<本形態の特徴>
本形態の署名生成装置10は、ステップS6で、ハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列のビット結合値β=h|R|idに対し、ハッシュ関数H2を作用させたLビットのハッシュ値v=H2(β)を求め、このハッシュ値vとLビットの復元署名対象情報recとの排他的論理和値x=v(+)recを行い、復元署名対象情報recを最終的な署名情報に関連付けている。ここで、排他的論理和値x=v(+)recを行うためには、ハッシュ値vと復元署名対象情報recとのビット長を同一にする必要があるが、前述のように、任意のビット長の入力に対し、復元署名対象情報recと同じビット長のハッシュ値vを出力するハッシュ関数H2を設定することは容易である。よって、本形態では、様々なビット長の復元署名対象情報rec及びリカバリーメッセージMrecに柔軟に対応可能な署名情報を生成できる。
【0068】
また、署名検証装置20がステップS21で受信した署名情報(r’,σ’)が正当であり、(r’,σ’)=(r,σ)であった場合、ステップS23で算出されるハッシュ値u’は、
u’=H3(γ’)
=H3(r’|Mclr|id)
=H3(r|Mclr|id)
=u
となり、ステップS24で算出される剰余演算結果t’=tとなる。そして、ステップS26で算出される双線形関数値R’は、
R’=e(σ’,P2)・e(Pid,mp)t’
=e(σ,P2)・e(Pid,mp)t
=e(y・P1−t・Sid,P2)・e(Pid,mp)t …(11)
となる。そして、mp=ms・P2であることと、ペアリング関数の[性質3]より、式(11)は、
R’=e(y・P1−t・ms・Pid,P2)・e(Pid,ms・P2)t
=e(y・P1−t・ms・Pid,P2)・e(ms・t・Pid,P2)
=e(y・P1−t・ms・Pid+ms・t・Pid,P2)
=e(y・P1,P2)
=e(P1,P2)y
=R
となる。
【0069】
ここで、本形態ではy≠0であるため、R’≠1とはならない(ステップS27)。また、r’=rである場合にはh’=h,x’=xとなるため(ステップS28)、β’=βとなり、v’=vとなり(ステップS29)、rec’=recとなる(ステップS30)。よってh’’=h’=hとなり(ステップS31,S32)、rec’=recからリカバリーメッセージMrec’=Mrecが復号され、検証が成功する(ステップS33〜S35)。
【0070】
また、この署名検証処理を行うために署名検証装置20がクリアーメッセージMclr及び署名情報(r’,σ’)以外に取得すべき情報は、すべての装置に共有される楕円曲線E、ペアリング関数e、関数IDencode、関数decode、ハッシュ関数H1,H2,H3、マスター公開鍵mpなどの共用パラメータと、実際に署名生成を行った署名生成装置10の識別子idである。これらのうち、署名生成装置10に独自の情報は識別子idのみであり、さらに、この識別子idはメールアドレス等の容易に入手可能な情報である。よって、従来のように公開鍵証明書等を必要とするRSA等の公開鍵を用いる方式に比べ、署名検証に必要な鍵の取得や管理の煩雑さが軽減できる。また、GPS装置で検出される特定の位置情報や、時計から出力される時刻情報などを識別子idとして用いた場合には、署名検証装置20が所定の位置に達したり、所定の時間に達したりした場合にのみ、署名検証やリカバリーメッセージMrecの復元を可能とするといったシステムも構築可能である。
【0071】
〔第2実施形態〕
次に、本発明の第2実施形態を説明する。第2実施形態は第1実施形態の変形例であり、クリアーメッセージMclrを用いず、クリアーメッセージMclrをヌル値とした形態である。以下では、第1実施形態との相違点を中心に説明し、第1実施形態と共通する事項については説明を省略する。
【0072】
<構成>
図10は、第2実施形態の署名生成装置110の詳細構成を説明するためのブロック図である。図11は、第2実施形態の署名検証装置120の詳細構成を説明するためのブロック図である。
【0073】
本形態のリカバリ署名システムは、第1実施形態のリカバリ署名システム1を構成する署名生成装置10を署名生成装置110に置換し、署名検証装置20を署名検証装置120に置換した構成である。また、署名生成装置10と署名生成装置110との相違点は、ハッシュ演算部10mがハッシュ演算部110m(「第3ハッシュ演算部」)に置換された点である。また、署名検証装置20と署名検証装置120との相違点は、ハッシュ演算部20eがハッシュ演算部120e(「第4ハッシュ演算部」)に置換された点である。
【0074】
<処理>
次に本形態の処理について説明する。
[前処理及び秘密鍵生成処理]
第1実施形態と同じであるため説明を省略する。
【0075】
[署名生成処理]
次に、署名生成装置110の署名生成処理を説明する。図12は、第2実施形態の署名生成処理を説明するためのフローチャートである。以下、第1実施形態との相違点を中心に説明する。
【0076】
まず、入力部10dに、署名対象となるリカバリーメッセージMrecが入力され、これがメモリ10aに格納される(ステップS101)。本形態ではクリアーメッセージMclrは入力されない。その後、第1実施形態と同じ、ステップS2〜S8の処理が実行される。次に、ハッシュ演算部10mが、メモリ10aからビット結合値rと識別子idとを読み込み、それらのビット結合値γ=r|idに対し、ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する(ステップS109)。生成されたハッシュ値uはメモリ10aに格納される。その後、第1実施形態と同じ、ステップS10〜S14の処理が実行された後、ビット結合値rと楕円曲線演算値σとが送信部10sに送られ、送信部10sは、署名情報(r,σ)とをネットワーク40経由で署名検証装置120に送信する(ステップS115)。
【0077】
[署名検証処理]
次に、署名検証装置120の署名検証処理を説明する。図13は、第2実施形態の署名検証処理を説明するためのフローチャートである。以下、第1実施形態との相違点を中心に説明する。
【0078】
まず、署名検証装置20の通信部20dが、署名情報(r’,σ’)を受信する(ステップS121)。本形態ではクリアーメッセージMclrは受信されない。次に、入力部20sに署名生成装置10の識別子idが入力され、メモリ20aに格納される(ステップS22)。なお、識別子idがすでにメモリ20aに格納されているのであれば、ステップS22は省略可能である。次に、ハッシュ演算部20eが、メモリ20aから第1パート情報r’と識別子idとを読み込み、これらのビット列のビット結合からなるビット列γ’=r’|idに対し、ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する(ステップS123)。算出されたハッシュ値u’はメモリ20aに格納される。その後、第1実施形態のステップS24〜S36の処理によって署名検証とリカバリーメッセージの復元とが行われる。
【0079】
〔変形例等〕
なお、本発明は上述の各実施形態に限定されるものではない。例えば、第1実施形態では、復元署名対象情報recと双線形関数値Rと識別子idとの各ビット列のビット結合値rec|R|idをαとし、署名対象情報の復元値rec’と双線形関数値R’と識別子idとの各ビット列のビット結合値rec’|R’|idをα’とした。しかし、復元署名対象情報recと双線形関数値Rとの各ビット列を含むビット結合値をαとし、前記署名対象情報の復元値rec’と前記双線形関数値R’との各ビット列を含むビット結合値をα’とし、ビット結合値αを構成するビット列とビット結合値をα’を構成するビット列とが等しい場合にα=α’となるのであれば、αやα’が識別子idを含まなくてもよく、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0080】
また、同様に第1実施形態では、β=h|R|idとし、β’=h’|R’|idとしたが、ハッシュ値hと双線形関数値Rとの各ビット列を含むビット結合値をβとし、ハッシュ値h’と双線形関数値R’との各ビット列を含むビット結合値をβ’とし、ビット結合値βを構成するビット列とビット結合値β’を構成するビット列とが等しい場合にβ=β’となるのであれば、βやβ’が識別子idを含まなくてもよく、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0081】
また、同様に第1実施形態では、γ=r|Mclr|idとし、γ’=r’|Mclr|idとしたが、ビット結合値rのビット列を含むビット列をγとし、署名情報の第1パート情報r’のビット列を含むビット列をγ’とし、ビット結合値γを構成するビット列とビット結合値γ’を構成するビット列とが等しい場合にγ=γ’となるのであれば、γやγ’が識別子idを含まなくてもよく、Mclrを含まなくてもよくてもよく(例えば、第2実施形態)、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0082】
また、署名検証装置20,120の判定部20iが、メモリ20aから第2パート情報σ’や剰余演算結果t’を読み込み、σ’が無限遠点Oであるか否かや、剰余演算結果t’が0であるか否かを判定し、σ’=Oであったり、t’=0であったりした場合に署名情報を拒絶する構成であってもよい。特に、t’=0であった場合に署名情報を拒絶する構成とした場合、ランダムオラクルモデルを前提としない実環境での安全性が向上する。すなわち、攻撃者が0=u mod p、u=H3(r|Mclr|id)を満たす整数rを発見できたとする。ここで、署名検証装置20,120がt’=0となることを許した場合には、攻撃者は、公開情報であるP1のみを用い、何れかの署名生成装置に成りすまして楕円曲線演算値σ=y・P1−t・Sid=y・P1を生成し、署名検証に合格する署名情報(r,σ)を生成できてしまう。署名検証装置20,120がt’=0となる署名情報を排除することで、このような攻撃を防止できる。
【0083】
また、第1,2実施形態では、(Z/pZ)\{0}の範囲から乱数yを選択することとした。しかし、0を含むZ/pZから乱数yを選び、署名検証時にステップS27の判定を行わない構成でもよい。さらには、演算効率は落ちるが、一般的な整数から乱数yを選ぶ構成であってもよい。また、ステップS11やステップS13の判定を行わない構成であってもよい。
【0084】
また、第1,2実施形態では、rec=encode(Mrec)としたが、rec=Mrecとし、ステップS2,S33,S34を実行しない構成であってもよい。また、第1,2実施形態では、剰余演算t=u mod pやt’=u’ mod pによってtやt’を算出することとしたが、t=u及びt’=u’とし、ステップS10,S24を実行しない構成であってもよい。
【0085】
また、ステップS4,S12においてP1の代わりに<P1>に属するその他の元(例えば、Pid)を用いてもよい。
【0086】
また、本形態ではリカバリーメッセージのビット長がどのような値であっても署名を生成できるため、リカバリーメッセージをヌル値とすることもできる。この場合には、クリアーメッセージのみが署名対象となる。このように、本形態の構成では、署名対象の自由度が向上する。
【0087】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0088】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0089】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0090】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0091】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0092】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0093】
本発明は、電子署名を用いる様々な用途に適用可能である。
【図面の簡単な説明】
【0094】
【図1】図1は、第1実施形態のリカバリ署名システムを説明するためのシステム構成図である。
【図2】図2は、第1実施形態の署名生成装置の詳細構成を説明するためのブロック図である。
【図3】図3は、第1実施形態におけるハッシュ演算部10iの詳細構成の一例を説明するためのブロック図である。
【図4】図4は、第1実施形態の署名検証装置の詳細構成を説明するためのブロック図である。
【図5】図5は、第1実施形態の管理装置の詳細構成を説明するためのブロック図である。
【図6】図6は、第1実施形態の署名生成処理を説明するためのフローチャートである。
【図7】図7は、ステップS6の詳細処理を例示するためのフローチャートである。
【図8】図8は、第1実施形態の署名検証処理を説明するためのフローチャートである。
【図9】図9は、第1ビット位置及び第2ビット位置の設定例を説明する図である。
【図10】図10は、第2実施形態の署名生成装置の詳細構成を説明するためのブロック図である。
【図11】図11は、第2実施形態の署名検証装置の詳細構成を説明するためのブロック図である。
【図12】図12は、第2実施形態の署名生成処理を説明するためのフローチャートである。
【図13】図13は、第2実施形態の署名検証処理を説明するためのフローチャートである。
【符号の説明】
【0095】
1 リカバリ署名システム
10,110 署名生成装置
20,120 署名検証装置
30 管理装置
【技術分野】
【0001】
本発明は、情報セキュリティ技術の応用技術に関し、特に、署名からメッセージが復元できるメッセージ復元署名に関する。
【背景技術】
【0002】
メッセージ復元署名の従来技術として非特許文献1に示すものがある。この方式は、ランダムオラクルモデルで安全性が証明される方式である。以下にこの方式の概要を示す。
【0003】
この方式では、
メッセージM∈{0,1}k2
関数F1:{0,1}k2→{0,1}k1
関数F2:{0,1}k1→{0,1}k2
関数F:{0,1}k1+k2→{0,1}k
E:有限体Fq上で定義された楕円曲線
p:楕円曲線E上の点Rに対してp・R=O(Oは無限遠点)を満たす素数
G1:楕円曲線E上の位数pの部分集合の点
w∈Z/pZ
秘密鍵:x∈Z/pZ
公開鍵:(Fq,E,G1,Y)(Y=−x・G1(∈E))
とする。なお、{0,1}δは、2進δ桁のビットデータを示し、{0,1}δ→{0,1}εは、2進δ桁のビットデータから2進ε桁のビットデータへの写像である関数を示す。
【0004】
<署名生成>
署名生成は以下のように行う。ただし、Rxは点R∈Eのx座標を示し、(+)は排他的論理和演算子を示す。
【0005】
M’=F1(M)|(F2(F1(M))(+)M) …(1)
Rx=(w・G1)x
r=Rx(+)M’ …(2)
c=F(r)
z=w+c・x mod p
署名Sign=(r,z)
【0006】
<署名検証>
署名検証は以下のように行う。ただし、[M’]k1はM’の先頭k1ビットを示し、[M’]k2はM’の残りのk2ビットを示す。
【0007】
M’=r(+)(z・G1+F(r)・Y)x
M=[M’]k2(+)F2([M’]k1)
[M’]k1=F1(M)であれば検証合格
【非特許文献1】Masayuki Abe, Tatsuaki Okamoto, "A Signature Scheme with Message Recovery as Secure as Discrete Logarithm," ASIACRYPT 1999, pp.378-389
【発明の開示】
【発明が解決しようとする課題】
【0008】
しかし、非特許文献1の方式では、署名検証を行う署名検証装置が、署名生成を行った署名生成装置の公開鍵を取得する必要がある。従来の構成の場合、公開鍵は署名生成装置ごとに異なるため、その取得や管理が煩雑であった。
【0009】
また、非特許文献1の方式では、式(1)の(F2(F1(M))や式(2)のRxのビット長が固定長であり、メッセージMのビット長も固定長としなければならない。特に、式(2)のRxは楕円曲線E上の点R∈Eのx座標であり、そのビット長は楕円曲線Eに依存する。しかしながら、メッセージMのビット長に応じ、Rxのビット長がM’(式(1)の演算結果)のビット長と等しくなるように楕円曲線Eを変更し、なおかつ、変更されたすべての楕円曲線Eにおいて安全性を確保することは容易ではない。
【0010】
このため、従来は、メッセージMの長さが固定長より短い場合であっても、それに併せて署名Signの一部分rのビット長を短くすることができず、非効率であった。また、メッセージMのビット長が固定長よりも長い場合には、式(1)にメッセージMの一部分しか代入することができず、メッセージMの全てのビットを対象としたメッセージ復元署名を構成できない。
【0011】
本発明はこのような点に鑑みてなされたものであり、公開鍵の取得や管理の煩雑さを軽減し、なおかつ、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名技術を提供することを目的とする。
【課題を解決するための手段】
【0012】
本発明の署名生成装置は、有限体Fq上の楕円曲線をEとし、楕円曲線E上の有理点からなる有限集合の要素数#Eを割り切る素数をpとし、楕円曲線E上のp等分点からなる有限集合をE[p]とし、有限体Fqを基礎体とする拡大体からなる有限集合をμpとし、有限集合E[p]の2つの元を有限集合μpの1つの元に写す非退化双線形ペアリング関数をe:E[p]×E[p]→μpとし、e(P1,P2)≠1を満たす有限集合E[p]の元をP1,P2∈E[p]とし、署名生成装置の識別子をidとし、識別子idに対応する有限集合E[p]の元をPidとし、整数であるマスター秘密鍵をmsとし、Pidの楕円曲線E上でのms倍点ms・Pidを署名生成装置の秘密鍵Sidとした場合における、当該秘密鍵Sidを格納する第1記憶部と、秘匿される署名対象のビット列である復元署名対象情報recを格納する第2記憶部と、任意の整数yを選択する任意数選択部と、双線形関数値R=e(P1,P2)y∈μpを算出する第1双線形関数演算部と、復元署名対象情報recのビット列と双線形関数値Rのビット列とを含むビット結合値αに対し、第1ハッシュ関数H1を作用させたハッシュ値h=H1(α)を算出する第1ハッシュ演算部と、ハッシュ値hのビット列と双線形関数値Rのビット列とを含むビット結合値βに対し、任意のビット長のビット列を復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を作用させたハッシュ値v=H2(β)を算出する第2ハッシュ演算部と、ハッシュ値vと復元署名対象情報recとの排他的論理和値xを算出する第1排他的論理和演算部と、ハッシュ値hのビット列を第1ビット位置に配置し、排他的論理和値xのビット列を第2ビット位置に配置したビット結合値rを算出するビット結合部と、ビット結合値rのビット列を含むビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する第3ハッシュ演算部と、予め定められた規則に従ってハッシュ値uに対して定まる整数をtとした場合における、元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sidを算出する楕円曲線演算部と、ビット結合値rと楕円曲線演算値σとからなる署名情報(r,σ)を送信する送信部と、を有する。
【0013】
以上のように本発明では、第2ハッシュ演算部が、任意のビット長のビット列を復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を用い、ビット結合値βを復元署名対象情報recとビット長が等しいハッシュ値vに変換する。ハッシュ関数の出力ビット長を変化させることは、楕円曲線Eを変更することに比べて大変容易である。そのため、本発明の署名生成装置では、復元署名対象情報recのあらゆるビット長に柔軟に対応した署名生成が可能となる。
【0014】
また、本発明の署名検証装置は、元P2と、元P2の楕円曲線E上でのms倍点ms・P2であるマスター公開鍵mpと、を格納する第3記憶部と、ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなる署名情報(r’,σ’)を受信する受信部と、第1パート情報r’と第2パート情報σ’を格納する第4記憶部と、署名生成装置の識別子idに対応する有限集合E[p]の元Pidを格納する第5記憶部と、第1パート情報r’のビット列を含むビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する第4ハッシュ演算部と、予め定められた規則に従ってハッシュ値u’に対して定まる整数をt’とした場合における、双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’∈μpを算出する第2双線形関数演算部と、第1パート情報r’の第1ビット位置のビット列h’と、第1パート情報r’の第2ビット位置のビット列x’とを抽出するビット分割部と、ハッシュ値h’のビット列と双線形関数値R’のビット列とを含むビット結合値β’に対し、第2ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する第5ハッシュ演算部と、ハッシュ値v’とビット列x’との排他的倫理和値を、署名対象情報の復元値rec’として算出する第2排他的論理和演算部と、署名対象情報の復元値rec’のビット列と双線形関数値R’のビット列とを含むビット結合値α’に対し、第1ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する第6ハッシュ演算部と、ビット列h’とハッシュ値h’’とが等しいか否かを判定する比較部と、を有する。
【0015】
この署名検証装置により、上述の署名生成装置が生成した署名を検証できる。また、本発明の署名検証装置は、複数の署名生成装置に共通するマスター公開鍵mpと、実際に署名生成を行った署名生成装置の識別子idとがあれば、署名検証と署名対象情報の復元とができる。そのため、実際に署名生成を行った署名生成装置ごとに異なる公開鍵を用いる従来構成に比べ、署名検証と署名対象情報の復元を行うために必要な鍵の取得や管理の煩雑さを軽減できる。
【発明の効果】
【0016】
本発明では、公開鍵の取得や管理の煩雑さを軽減し、様々なビット長のメッセージに柔軟に対応可能なメッセージ復元署名を実現できる。
【発明を実施するための最良の形態】
【0017】
以下、図面を参照して本発明の実施形態を説明する。
〔記号・用語の定義〕
まず、各実施形態で使用する記号・用語を定義する。
【0018】
Z:整数集合。
k:k∈Z(Zの元)であるセキュリティパラメータ。
E:位数qの有限体Fq上で定義された楕円曲線。アフィン(affine)座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6 …(3)
(ただし、a1,a2,a3,a4,a6∈Fq)を満たす点(x,y)の集合に無限遠点と呼ばれる特別な点Oを付加したもので定義される。楕円曲線E上の任意の2点に対して楕円加算と呼ばれる二項演算+及び楕円曲線E上の任意の1点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、この楕円加算に関して群をなすこと及び楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている(例えば、参考文献1“イアン・F・ブラケ、ガディエル・セロッシ、ナイジェル・P・スマート=著、「楕円曲線暗号」、出版=ピアソン・エデュケーション、ISBN4-89471-431-0”等参照)。
【0019】
#E:楕円曲線E上の有理点からなる有限集合の要素数。有限体Fq上で定義された楕円曲線Eの有理点の個数#Eは有限である。
p:#Eを割り切る大きい素数。
E[p]:楕円曲線Eのp等分点からなる有限集合。楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A=Oを満たす点Aの有限集合として定義される。E[p]はEの部分群である。
μp:有限体Fqを基礎体とする拡大体である有限集合。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。
e:非退化双線形ペアリング(pairing)関数(以下「ペアリング関数」と呼ぶ)であり、以下の式で定義される。
E[p]×E[p]=μp …(4)
【0020】
ペアリング関数eは次の性質を持つ。
[性質1]E[p]上の任意の点A1に対して、e(A1,A1)=1が成り立つ。
[性質2]E[p]上の任意の2点A1、A2に対して、e(A1,A2)=e(A2,A1)−1が成り立つ。
[性質3]E[p]上の任意の3点A1,A2,A3に対して、e(A1+A2,A3)=e(A1,A3)e(A2,A3)であり、e(A1,A2+A3)=e(A1,A2)e(A1,A3)が成り立つ。
[性質4]E[p]上の任意の点A1に対して、e(A1,O)=1が成り立つ。
[性質5]E[p]上のある点A1がE[p]上のすべての点A2に対して、e(A1,A2)=1を満たすなら、A1=Oが成り立つ。
【0021】
なお、ペアリング関数eの具体例としては、WeilペアリングやTateペアリングなどを挙げることができる(例えば、参考文献2「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp. 61-81」等参照)。また、ペアリング関数が効率的に計算可能な非超特異楕円曲線(non-supersingular curve)の生成方法については、参考文献3「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献4「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献5「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」などに開示されている。また、ペアリング関数をコンピュータ上で計算するためのアルゴリズムとしては、周知のMiller のアルゴリズム(参考文献6「V. S. Miller, “Short Programs for functions on Curves,” [online],1986,[2008年6月13日検索],インターネット<http://crypto.stanford.edu/miller/miller.pdf>」などが存在する。
【0022】
P1,P2:e(P1,P2)≠1を満たす有限集合E[p]の元。
<P1>:P1を生成元とする巡回群。
<P2>:P2を生成元とする巡回群。
IDencode:任意のビット列を<P1>に移す衝突困難な関数{0,1}*→<P1>。IDencodeの例は以下の通りである。
【0023】
《IDencodeの例1》関数H:{0,1}*→Fqを衝突困難な関数とする。このような関数は、例えばSHA−1などのハッシュ関数の出力を一定の方法で有限体Fqの元に対応させることで得られる。cを自然数で、#E=c・pとなるものとする。cは通常cofactorと呼ばれる。以上の準備の下で、以下のアルゴリズムを実行する関数をIDencodeとする。
【0024】
処理1.ran←0
処理2.入力isに対してx1=H(is|ran)を計算する。
処理3.y1∈Fqに関して、(x1,y1)∈Eとなる条件から導かれる2次方程式を解く。解y1が存在するならば、処理5に進む。
処理4.ran←ran+1として処理2に戻る。
処理5.点(x1,y1)∈Eをc倍してその結果を出力する。#E=c・pであり、楕円曲線E上の任意の点をc・p倍すると無限遠点Oとなるため、点(x1,y1)∈Eをc倍した点はE[p]の元となる。
【0025】
《IDencodeの例2》<P1>の元をD個選択し、それらをそれぞれ0以上D−1以下の整数dに対応付け、選択された<P1>の各元をSPd∈<P1>とする。また、入力された任意のビット列に対してDビットのハッシュ値を出力とするハッシュ関数H0を用意する。入力された任意のビット列にハッシュ関数H0を作用させて得られたDビットのビット列の上位からdビット目をhd∈{0,1}とする。そして、入力された任意のビット列に対してΣd=0D−1hd・SPdを出力する関数をIDencodeとする。
【0026】
Mrec:署名対象となるメッセージの復元部分である任意のビット長のリカバリーメッセージMrec∈{0,1}*。なお、メッセージの復元部分とは、メッセージのうち一旦秘匿され、署名検証装置で復元される情報を意味する。つまり、リカバリーメッセージMrecは、秘匿される署名対象のビット列である。
【0027】
Mclr:署名対象となるメッセージの非復元部分である任意のビット長のクリアーメッセージMclr∈{0,1}*。なお、メッセージの非復元部分とは、メッセージのうち秘匿されることなく署名検証装置に開示される情報を意味する。つまり、クリアーメッセージMclrは秘匿されない署名対象のビット列である。
【0028】
encode:任意のビット長のビット列を入力ビット長に応じたビット長のビット列に変換する関数{0,1}*→{0,1}*。ただし、encodeの出力ビット長をL(Lは1以上の整数)とする。encodeの例は後述する。
【0029】
decode:encodeの逆関数。
rec:署名検証装置によって復元されるビット列である復元署名対象情報rec=encode(Mrec)。
rounddown{*}: *の小数点以下を切り捨てる関数。
length(*): *のビット長を求める関数。その出力ビット長は一定である。
delete{δ,ε}:εのビットを先頭からδビットだけ削除する関数。
【0030】
H1:任意のビット長のビット列をNビットのビット列に変換するハッシュ関数{0,1}*→{0,1}N。ただし、Nは1以上の整数。なお、ハッシュ関数の具体例としては、SHA−1やそれを利用した一方向性関数を例示できる。
H2:出力長可変のハッシュ関数H2:{0,1}*×N→{0,1}*である。任意のL∈Nについて、任意のω∈{0,1}*に対する出力値H2(ω,L)は長さLのビット列となる。なお、以下では、H2(ω,L)をH2(ω)と表記する。
H3:ハッシュ関数。
【0031】
b|c:ビット列bとビット列cとのビット結合値。
b(+)c:bとcとの排他的論理和。
Z/pZ:pを法とする剰余類。各実施形態では、その代表元をZ/pZと表現する。また、代表元の一例は、0以上p−1以下の整数である。
(Z/pZ)\{0}:Z/pZから0を除いた集合。各実施形態では、1以上p−1以下の整数を(Z/pZ)\{0}とする。
ms:IDベース暗号のマスター秘密鍵ms∈Z/pZ。なお、IDベース暗号については、例えば、参考文献7「D. Boneh and M. Franklin, "Identify-based encryption from the Weil pairing", Advances in Cryptology 0 CRYTPO '01, volume 2139 of LNCS, pages 213-229. Springer, 2001.」などに開示されている。
【0032】
mp:IDベース暗号のマスター公開鍵mp=ms・P2∈<P2>。
id:署名生成装置の識別子id∈{0,1}*。
Pid:idに対応する楕円曲線E上の点Pid=IDencode(id)∈<P1>。
Sid:署名生成装置の秘密鍵Sid=ms・Pid∈<P1>。
【0033】
〔第1実施形態〕
本発明の第1実施形態を説明する。
【0034】
<構成>
図1は、第1実施形態のリカバリ署名システム1を説明するためのシステム構成図である。また、図2は、第1実施形態の署名生成装置10の詳細構成を説明するためのブロック図である。図3は、第1実施形態におけるハッシュ演算部10iの詳細構成の一例を説明するためのブロック図である。図4は、第1実施形態の署名検証装置20の詳細構成を説明するためのブロック図である。図5は、第1実施形態の管理装置30の詳細構成を説明するためのブロック図である。
【0035】
図1に示すように、本形態のリカバリ署名システム1は、署名を生成する署名生成装置10と、署名を検証する署名検証装置20と、リカバリ署名システム1を管理する第三者機関の装置である管理装置30とを有し、それらはネットワーク40を通じて通信可能に接続されている。なお、説明の簡略化のため、図1では署名生成装置10及び署名検証装置20を1つずつ記述しているが、署名生成装置10や署名検証装置20が2以上存在してもよい。同様に、管理装置30が2以上存在してもよい。
【0036】
図2に示すように、本形態の署名生成装置10は、メモリ10a(「第1記憶部」「第2記憶部」「第6記憶部」)と、一時メモリ10bと、制御部10cと、入力部10dと、符号化部10eと、任意数選択部10fと、双線形関数演算部10g(「第1双線形関数演算部」)と、ハッシュ演算部10h(「第1ハッシュ演算部」)と、ハッシュ演算部10i(「第2ハッシュ演算部」)と、排他的論理和演算部10j(「第1排他的論理和演算部」)と、ビット結合部10kと、ハッシュ演算部10m(「第3ハッシュ演算部」)と、剰余演算部10nと、判定部10p,10rと、楕円曲線演算部10qと、通信部10s(「送信部」)とを有する。また、図3に示す例では、ハッシュ演算部10iは、ハッシュ回数演算部10iaと、部分ハッシュ演算部10ibと、ビット結合部10icと、ビット削除部10idとを有する。なお、本形態の署名生成装置10は、CPU(Central Processing Unit)やRAM(Random Access Memory)などからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。ここで、メモリ10aや一時メモリ10bは、例えば、RAM、レジスタ、補助記憶装置、或いはこれらを結合した記憶領域である。また、制御部10cと、符号化部10eと、任意数選択部10fと、双線形関数演算部10gと、ハッシュ演算部10h,10i,10mと、排他的論理和演算部10jと、ビット結合部10kと、剰余演算部10nと、判定部10p,10rと、楕円曲線演算部10qとは、例えば、CPUが所定のプログラムを実行して構築される処理手段である。また、入力部10dは、キーボード、マウス、入力ポートなどの入力インタフェースである。また、通信部10sは、所定のプログラムを実行するCPUの制御のみと駆動するLANカード、モデム等の通信手段である。また、署名生成装置10は、制御部10cの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ10bに読み書きされる。
【0037】
また、図4に示すように、本形態の署名検証装置20は、メモリ20a(「第3記憶部」「第4記憶部」「第5記憶部」「第7記憶部」)と、一時メモリ20bと、制御部20cと、通信部20d(「受信部」)と、ハッシュ演算部20e(「第4ハッシュ演算部」)と、剰余演算部20fと、識別子符号化部20gと、双線形関数演算部20h(「第2双線形関数演算部」)と、判定部20iと、ビット分割部20jと、ハッシュ演算部20k(「第5ハッシュ演算部」)と、排他的論理和演算部20m(「第2排他的論理和演算部」)と、ハッシュ演算部20n(「第6ハッシュ演算部」)と、比較部20pと、復号部20qと、出力部20rと、入力部20sとを有する。なお、本形態の署名検証装置20は、CPUやRAMからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。ここで、メモリ20aや一時メモリ20bは、例えば、RAM、レジスタ、補助記憶装置、或いはこれらを結合した記憶領域である。また、制御部20cと、ハッシュ演算部20eと、剰余演算部20fと、識別子符号化部20gと、双線形関数演算部20hと、判定部20iと、ビット分割部20jと、ハッシュ演算部20kと、排他的論理和演算部20mと、ハッシュ演算部20nと、比較部20pと、復号部20qとは、例えば、CPUが所定のプログラムを実行して構築される処理手段である。また、通信部20dは、所定のプログラムを実行するCPUの制御のみと駆動するLANカード、モデム等の通信手段である。また、出力部20rは、ディスプレイ、出力ポートなどの出力インタフェースであり、入力部20sは、キーボード、マウス、入力ポートなどの入力インタフェースである。また、署名検証装置20は、制御部20cの制御のもと各処理を実行する。さらに、特に明示しない限り、演算過程の各データは逐一一時メモリ20bに読み書きされる。
【0038】
また、図5に示すように、管理装置30は、メモリ30aと、一時メモリ30bと、制御部30cと、マスター秘密鍵生成部30dと、マスター公開鍵生成部30eと、識別子符号化部30fと、秘密鍵生成部30gと、通信部30hとを有する。本形態の管理装置30は、CPUやRAMからなる通信手段を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。
【0039】
<処理>
次に本形態の処理について説明する。
[前処理]
まず、前処理として、第三者機関が、セキュリティパラメータk∈Zに対してkビット安全性が担保されるように、楕円曲線Eと、#Eを割り切る大きい素数pと、ペアリング関数eと、元P1,P2と、関数IDencodeと、関数encodeと、関数decodeと、ハッシュ関数H1,H2,H3とを設定する。
【0040】
設定された楕円曲線Eとペアリング関数eと関数encodeとハッシュ関数H1,H2,H3は、例えば、署名生成装置10を構成するためのプログラムに記述され、素数pと元P1,P2とは、例えば、署名生成装置10のメモリ10aに格納され、これらは署名生成装置10が利用可能な状態にされる。また、設定された楕円曲線Eとペアリング関数eと関数IDencodeと関数decodeとハッシュ関数H1,H2,H3は、例えば、署名検証装置20を構成するためのプログラムに記述され、素数pと元P2とは、例えば、署名検証装置20のメモリ20aに格納され、これらは署名検証装置20が利用可能な状態にされる。さらに、設定された楕円曲線Eと関数encodeと関数IDencodeとは、例えば、管理装置30を構成するためのプログラムに記述され、素数pと元P1,P2とは、例えば、管理装置30のメモリ30aに格納され、これらは管理装置30が利用可能な状態にされる。
【0041】
また、管理装置30のマスター秘密鍵生成部30dが、マスター秘密鍵ms∈UZ/pZを一様ランダムに選択し、それをメモリ30aに安全に格納する。次に、マスター公開鍵生成部30eが、メモリ30aからマスター秘密鍵msと元P2とを読み込み、楕円曲線E上の点である元P2を楕円曲線E上でmsし、その演算結果mp=ms・P2∈<P2>をマスター公開鍵mpとしてメモリ30aに格納する。このように生成されたマスター公開鍵mpは、署名検証装置20にも配信され、署名検証装置20のメモリ20aに格納される。
【0042】
[秘密鍵生成処理]
次に、管理装置30が署名生成装置10の秘密鍵を生成する秘密鍵生成処理を説明する。秘密鍵生成処理は、前処理において実行されてもよいし、署名生成装置10が署名生成を行うたびに実行されてもよいし、所定の契機で定期的又は不定期的に実行されてもよい。
【0043】
秘密鍵生成処理では、まず、署名生成装置10の入力部10dに署名生成装置10の識別子idが入力される。識別子idの例は、署名生成装置10のメールアドレス、URL、電話番号、位置情報、時刻情報、ユーザ名などである。入力された識別子idはメモリ10aに格納される。また、識別子idは、秘密鍵発行要求情報とともに通信部10qからネットワーク40経由で管理装置30に送信される。これらの情報は管理装置30の通信部30hで受信され、識別子idはメモリ30aに格納される。次に、識別子idは識別子符号化部30fに読み込まれ、識別子符号化部30fは識別子idを関数IDencodeに入力し、楕円曲線E上の点Pid=IDencode(id)を算出する。これは有限集合E[p]の元である。楕円曲線E上の点Pidはメモリ30aに格納され、さらに秘密鍵生成部30gに読み込まれる。秘密鍵生成部30gは、楕円曲線E上の点Pidを楕円曲線E上でms倍した署名生成装置10の秘密鍵Sid=ms・Pidを生成し、秘密鍵Sidをメモリ30aに格納する。生成された秘密鍵Sidは通信部30hに送られ、専用回線や公知の公開鍵暗号や共通鍵暗号などを用い、署名生成装置10に安全に送信される。秘密鍵Sidは署名生成装置10の通信部10qで受信され、メモリ10aに安全に格納される。
【0044】
[署名生成処理]
次に、署名生成装置10の署名生成処理を説明する。この処理の前提として、署名生成装置10のメモリ10aに元P1,P2と素数pと署名生成装置10の秘密鍵Sidと識別子idとが格納されているものとする。
【0045】
図6は、第1実施形態の署名生成処理を説明するためのフローチャートである。以下、この図に従って本形態の署名生成処理を説明する。
【0046】
まず、入力部10dに、署名対象となるリカバリーメッセージMrec及びクリアーメッセージMclrが入力され、これらがメモリ10aに格納される(ステップS1)。次に、符号化部10eが、メモリ10aからリカバリーメッセージMrecを読み込み、関数encodeを用いて符号化し、Lビットの復元署名対象情報rec=encode(Mrec)を生成する。以下に関数encodeの具体例を示す。
【0047】
[関数encodeの具体例の説明]
関数encodeは、任意の入力ビット列に対し、セキュリティパラメータkに対応した安全性が得られるビット長の復元署名対象情報recを出力する可逆な関数(逆関数が存在する関数)である。セキュリティパラメータkに対応した安全性が得られるビット長が72ビット以上であった場合の関数encodeの一例は以下の通りである。
【0048】
《length(Mrec)が72ビット未満の場合》
encode(Mrec)=length(Mrec)|Mrec|0…0 …(4)
(ただし、Mrec|0…0のビット長は72ビットである。)
【0049】
《length(Mrec)が72ビット以上の場合》
encode(Mrec)=0xff|Mrec …(5)
(ただし、0xffは、付加ビットが追加されていないことを示すヘッダ情報である。また、0xffのビット長BLは関数lengthの出力ビット長BLと等しい。)
この場合、関数decodeの演算は以下のようになる。
【0050】
《recの先頭BLビットが0xffである場合》
recから先頭BLビットを除いたビット列を出力する。
【0051】
《recの先頭BLビットが0xffでない場合》
recの先頭BLビットが0xffでない場合には、recから先頭BLビットに示されるビット長だけ、recの先頭BLビットより下位のビット列を抽出して出力する( [関数encodeの具体例の説明]終わり)。
【0052】
生成された復元署名対象情報recは、メモリ10aに格納される(ステップS2)。次に、任意数選択部10fが乱数y∈(Z/pZ)\{0}を選択し、それをメモリ10aに格納する(ステップS3)。なお、乱数の選択は、例えば、SHA-1等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて行う。
【0053】
次に、双線形関数演算部10gが、メモリ10aから元P1,P2と乱数yとを読み込み、ペアリング関数eを用いて双線形関数値R=e(P1,P2)y∈μpを算出し、双線形関数値Rをメモリ10aに格納する(ステップS4)。なお、e(P1,P2)y∈μpは有限体Fqを基礎体とする標数qのm(m≧2)次の拡大体Fqm上の演算である。拡大体Fqmの元は、有限体Fqの元を係数とするαについてのm−1次多項式で表現できる。なお、αは有限体Fqの元を係数とする既約多項式の根である。また、この既約多項式のうち最小次数のものをfとし、拡大体Fqmの元を表現する2つの多項式をA(α),B(α)とすると、拡大体Fqm上の乗算は、C(α)=A(α)・B(α) mod f(α)と表現でき、多項式演算A(α)・B(α)とf(α)による除算とによって計算できる。なお、多項式演算A(α)・B(α)における各次数の係数間の演算は有限体Fq上の演算である。また、拡大体Fqm上のべき乗は、このような拡大体Fqm上の乗算をべき乗回繰り返すことを意味する。例えば、e(P1,P2)3∈μpは、e(P1,P2)・e(P1,P2)・e(P1,P2)∈μpを意味する。
【0054】
次に、ハッシュ演算部10hが、メモリ10aから復元署名対象情報recと双線形関数値Rと識別子idとを読み込み、それらの各ビット列のビット結合値α=rec|R|idに対し、ハッシュ関数H1を作用させたNビットのハッシュ値h=H1(α)を算出する(ステップS5)。生成されたハッシュ値hはメモリ10aに格納される。次に、ハッシュ演算部10iが、メモリ10aからハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列とを読み込み、それらの各ビット列のビット結合値β=h|R|idに対し、ハッシュ関数H2を作用させたLビットのハッシュ値v=H2(β)を算出する(ステップS6)。生成されたハッシュ値vはメモリ10aに格納される。以下にステップS6の詳細を例示する。
【0055】
[ステップS6の詳細処理の例]
図7は、ステップS6の詳細処理を例示するためのフローチャートである。
まず、ハッシュ演算回数算出部10ia(図3)が、記憶部10aから復元署名対象情報recを読み込み、
emax=rounddown{L/length(H)}, L=length(rec) …(6)
の演算を行ってemax
を一時メモリ10bに格納する(ステップS6a)。なお、HはSHA−1等の公知のハッシュ関数を意味し、length(H)はハッシュ関数Hの出力ビットのビット長を意味する。なお、Lが定数である場合にはemaxを事前計算しておくことも可能であり、その場合にはステップS6aの処理は不要となる。
【0056】
次に、制御部10cは変数eに0を代入し、変数eを一時メモリ10bに格納する(ステップS6b)。次に、部分ハッシュ演算部10ibが、一時メモリ10bから変数eを読み込み、記憶部10aからハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列とを読み込み、それらの各ビット列のビット結合値β=h|R|idに対し、ハッシュ値
H(e,β) …(7)
を算出して一時メモリ10bに格納する(ステップS6c)。
【0057】
次に、制御部10cが、一時メモリ10bからemaxと変数eとを読み込み、
e=emax …(8)
を満たすか否かを判断する(ステップS6d)。ここで、式(8)を満たさないのであれば、制御部10cはe+1を新たなeとし、新たなeを一時メモリ10bに格納した後(ステップS6e)、処理をステップS6cに戻す。一方、式(8)を満たすのであれば、制御部10cはビット結合部10icに指示を与え、ビット結合部10icは、一時メモリ10bから各ハッシュ値H(0,β),H(1,β),H(2,β),…,H(emax,β)を読み込み、それらのビット結合値
HC(β)=H(0,β)|・・・|H(emax,β) …(9)
を算出して一時メモリ10bに格納する(ステップS6f)。
【0058】
次に、ビット削除部10idが、一時メモリ10bから、ビット結合値HC(β)を読み込み、
v=H2(β)=delete{length(HC(β))- L,HC(β)} …(10)
を算出して記憶部10aに出力する(ステップS6g)。すなわち、HC(R)の先頭の数ビットを削除して全体のビット長をLとしたものをv=H2(β)とする。
【0059】
なお、ステップS6の処理方法はこれに限定されない。例えば、eを用いるのではなく、ハッシュチェインによってハッシュ値のビット長を拡張する方法でもよい。この場合、式(9)のHC(β)は、例えば、
HC(β)=H(β)|H(H(β))|H(H(H(β)))|…|H(H(H…(β)…))
であってもよい([ステップS6の詳細処理の例]の説明終わり)。
【0060】
次に、排他的論理和演算部10jが、メモリ10aからハッシュ値vと復元署名対象情報recとを読み込み、それらの排他的論理和値x=v(+)recを算出し、排他的論理和値xをメモリ10aに格納する(ステップS7)。次に、ビット結合部10kが、メモリ10aからハッシュ値hと排他的論理和値xとを読み込み、ハッシュ値hのビット列を第1ビット位置に配置し、排他的論理和値xのビット列を第2ビット位置に配置したN+Lビットのビット結合値rを算出する(ステップS8)。なお、第1ビット位置及び第2ビット位置はどのビット位置に設定されてもよいが、署名生成装置10で設定される第1ビット位置と、署名検証装置20で設定される第1ビット位置とは同一であり、かつ、署名生成装置10で設定される第2ビット位置と、署名検証装置20で設定される第2ビット位置とは同一であるものとする。また、第1ビット位置及び第2ビット位置の設定例は以下の通りである。
【0061】
[第1ビット位置及び第2ビット位置の設定例]
図9は、第1ビット位置及び第2ビット位置の設定例を説明する図である。
《例1》先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置とする(図9(a))。
《例2》先頭Lビットを第2ビット位置とし、残りNビットを第1ビット位置とする(図9(b))。
《例3》L個の奇数ビットを第2ビット位置とし、残りのNビットを第1ビット位置とする(図9(c))。
【0062】
なお、これらは一例であり、その他の設定も可能である([第1ビット位置及び第2ビット位置の設定例]の説明終わり)。
【0063】
次に、ハッシュ演算部10mが、メモリ10aからビット結合値rとクリアーメッセージMclrと識別子idとを読み込み、それらのビット結合値γ=r|Mclr|idに対し、ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する(ステップS9)。生成されたハッシュ値uはメモリ10aに格納される。次に、剰余演算部10nがメモリ10aからハッシュ値uと素数pとを読み込み、剰余演算t=u mod pを行い、その演算結果をメモリ10aに格納する(ステップS10)。次に、判定部10pがメモリ10aから演算結果tを読み込み、t=0であるか否かを判定する(ステップS11)。ここで、t=0であれば、処理がステップS3に戻され、乱数yを取り直して処理がやり直される。一方、t=0でなければ、楕円曲線演算部10qがメモリ10aから演算結果tと元P1と乱数yと秘密鍵Sidとを読み込み、元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sid∈E[p]を算出する(ステップS12)。算出された楕円曲線演算値σはメモリ10aに格納される。次に、判定部10rが、メモリ10aから楕円曲線演算値σを読み込み、それが無限遠点Oを示すか否かを判定する(ステップS13)。ここで、楕円曲線演算値σ=Oであれば、処理がステップS3に戻され、乱数yを取り直して処理がやり直される。一方、楕円曲線演算値σ=Oでなければ、制御部10cがメモリ10aから乱数yを削除する(ステップS14)。そして、クリアーメッセージMclrとビット結合値rと楕円曲線演算値σとが送信部10sに送られ、送信部10sは、クリアーメッセージMclrと署名情報(r,σ)とをネットワーク40経由で署名検証装置20に送信する(ステップS15)。
【0064】
[署名検証処理]
次に、署名検証装置20の署名検証処理を説明する。この処理の前提として、署名検証装置20のメモリ20aにマスター公開鍵mpと元P2と素数pとが格納されているものとする。
【0065】
図8は、第1実施形態の署名検証処理を説明するためのフローチャートである。以下、この図に従って本形態の署名検証処理を説明する。
【0066】
まず、署名検証装置20の通信部20dが、クリアーメッセージMclrと署名情報(r’,σ’)とを受信する(ステップS21)。なお、この署名情報が正当なものであれば署名情報(r’,σ’)=(r,σ)であるが、この時点ではそれが不明であるため、通信部20dが受信する署名情報を(r’,σ’)と表現する。受信された署名情報(r’,σ’)は、ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなり、これらはメモリ20aに格納される。次に、入力部20sに署名生成装置10の識別子idが入力され、メモリ20aに格納される(ステップS22)。なお、識別子idがすでにメモリ20aに格納されているのであれば、ステップS22は省略可能である。次に、ハッシュ演算部20eが、メモリ20aから第1パート情報r’とクリアーメッセージMclrと識別子idとを読み込み、これらのビット列のビット結合からなるビット列γ’=r’|Mclr|idに対し、ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する(ステップS23)。算出されたハッシュ値u’はメモリ20aに格納される。次に、剰余演算部20fが、メモリ20aからハッシュ値u’と素数pとを読み込み、剰余演算t’=u’ mod pを行い、その演算結果をメモリ20aに格納する(ステップS24)。次に、識別子符号化部20gが、メモリ20aから識別子idを読み込み、識別子idを関数IDencodeに入力し、楕円曲線E上の点Pid=IDencode(id)を算出する(ステップS25)。これは署名生成装置10の識別子idに対応する有限集合E[p]の元Pidである。生成された楕円曲線E上の点Pidはメモリ20aに格納される。次に、双線形関数演算部20hが、メモリ20aから、第2パート情報σ’と元P2と楕円曲線E上の点Pidとマスター公開鍵mpと演算結果t’を読み込み、ペアリング関数eを用いて双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’を算出する(ステップS26)。生成された双線形関数値R’はメモリ20aに格納される。次に、判定部20iが、メモリ20aから双線形関数値R’を読み込み、R’=1であるか否かを判定する(ステップS27)。ここで、R’=1であれば、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、R’=1でなければ、次に、ビット分割部20jが、メモリ20aから第1パート情報r’を読み込み、1パート情報r’の第1ビット位置のビット列h’と、第1パート情報r’の第2ビット位置のビット列x’とを抽出し(ステップS28)、それらをメモリ20aに格納する。なお、前述のように、第1ビット位置及び第2ビット位置は、署名生成装置10のビット結合部10kに設定されたものと同一とする。例えば、署名生成装置10のビット結合部10kで先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置としていたのであれば、ビット分割部20jも先頭Nビットを第1ビット位置とし、残りLビットを第2ビット位置として処理を行う。次に、ハッシュ演算部20kが、メモリ20aからハッシュ値h’と双線形関数値R’と識別子idとを読み込み、それらのビット列のビット結合値β’=h’|R’|idに対し、ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する(ステップS29)。算出されたハッシュ値v’はメモリ20aに格納される。次に、排他的論理和演算部20mが、メモリ20aからハッシュ値v’とビット列x’とを読み込み、それらの排他的倫理和値を、署名対象情報の復元値rec’として算出し(ステップS30)、算出された復元値rec’をメモリ20aに格納する。次に、ハッシュ演算部20nが、メモリ20aから署名対象情報の復元値rec’と双線形関数値R’と識別子idとを読み込み、それらのビット列のビット結合値α’=rec’|R’|idに対し、ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する(ステップS31)。算出されたハッシュ値h’’は、メモリ20aに格納される。次に、比較部20pがメモリ20aから、ビット列h’とハッシュ値h’’とを読み込み、これらが等しいか否かを判定する(ステップS32)。ここで、これらが等しくなければ、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、これらが等しければ、次に、復号部20qがメモリ20aから復元値rec’を読み込み、それをdecode関数に入力し、復号値Mrec’=decode(rec’)を算出し、それをメモリ20aに格納する(ステップS34)。ここで、復号値Mrec’が所定のフォーマットに従ったものでなければ、制御部20cは署名を拒絶し(ステップS36)、処理を終了する。一方、復号値Mrec’が所定のフォーマットに従ったものであれば、検証が成功ものとして、復号値Mrec’が出力部20rに送られ、そこから出力される(ステップS35)。
【0067】
<本形態の特徴>
本形態の署名生成装置10は、ステップS6で、ハッシュ値hのビット列と双線形関数値Rのビット列と識別子idのビット列のビット結合値β=h|R|idに対し、ハッシュ関数H2を作用させたLビットのハッシュ値v=H2(β)を求め、このハッシュ値vとLビットの復元署名対象情報recとの排他的論理和値x=v(+)recを行い、復元署名対象情報recを最終的な署名情報に関連付けている。ここで、排他的論理和値x=v(+)recを行うためには、ハッシュ値vと復元署名対象情報recとのビット長を同一にする必要があるが、前述のように、任意のビット長の入力に対し、復元署名対象情報recと同じビット長のハッシュ値vを出力するハッシュ関数H2を設定することは容易である。よって、本形態では、様々なビット長の復元署名対象情報rec及びリカバリーメッセージMrecに柔軟に対応可能な署名情報を生成できる。
【0068】
また、署名検証装置20がステップS21で受信した署名情報(r’,σ’)が正当であり、(r’,σ’)=(r,σ)であった場合、ステップS23で算出されるハッシュ値u’は、
u’=H3(γ’)
=H3(r’|Mclr|id)
=H3(r|Mclr|id)
=u
となり、ステップS24で算出される剰余演算結果t’=tとなる。そして、ステップS26で算出される双線形関数値R’は、
R’=e(σ’,P2)・e(Pid,mp)t’
=e(σ,P2)・e(Pid,mp)t
=e(y・P1−t・Sid,P2)・e(Pid,mp)t …(11)
となる。そして、mp=ms・P2であることと、ペアリング関数の[性質3]より、式(11)は、
R’=e(y・P1−t・ms・Pid,P2)・e(Pid,ms・P2)t
=e(y・P1−t・ms・Pid,P2)・e(ms・t・Pid,P2)
=e(y・P1−t・ms・Pid+ms・t・Pid,P2)
=e(y・P1,P2)
=e(P1,P2)y
=R
となる。
【0069】
ここで、本形態ではy≠0であるため、R’≠1とはならない(ステップS27)。また、r’=rである場合にはh’=h,x’=xとなるため(ステップS28)、β’=βとなり、v’=vとなり(ステップS29)、rec’=recとなる(ステップS30)。よってh’’=h’=hとなり(ステップS31,S32)、rec’=recからリカバリーメッセージMrec’=Mrecが復号され、検証が成功する(ステップS33〜S35)。
【0070】
また、この署名検証処理を行うために署名検証装置20がクリアーメッセージMclr及び署名情報(r’,σ’)以外に取得すべき情報は、すべての装置に共有される楕円曲線E、ペアリング関数e、関数IDencode、関数decode、ハッシュ関数H1,H2,H3、マスター公開鍵mpなどの共用パラメータと、実際に署名生成を行った署名生成装置10の識別子idである。これらのうち、署名生成装置10に独自の情報は識別子idのみであり、さらに、この識別子idはメールアドレス等の容易に入手可能な情報である。よって、従来のように公開鍵証明書等を必要とするRSA等の公開鍵を用いる方式に比べ、署名検証に必要な鍵の取得や管理の煩雑さが軽減できる。また、GPS装置で検出される特定の位置情報や、時計から出力される時刻情報などを識別子idとして用いた場合には、署名検証装置20が所定の位置に達したり、所定の時間に達したりした場合にのみ、署名検証やリカバリーメッセージMrecの復元を可能とするといったシステムも構築可能である。
【0071】
〔第2実施形態〕
次に、本発明の第2実施形態を説明する。第2実施形態は第1実施形態の変形例であり、クリアーメッセージMclrを用いず、クリアーメッセージMclrをヌル値とした形態である。以下では、第1実施形態との相違点を中心に説明し、第1実施形態と共通する事項については説明を省略する。
【0072】
<構成>
図10は、第2実施形態の署名生成装置110の詳細構成を説明するためのブロック図である。図11は、第2実施形態の署名検証装置120の詳細構成を説明するためのブロック図である。
【0073】
本形態のリカバリ署名システムは、第1実施形態のリカバリ署名システム1を構成する署名生成装置10を署名生成装置110に置換し、署名検証装置20を署名検証装置120に置換した構成である。また、署名生成装置10と署名生成装置110との相違点は、ハッシュ演算部10mがハッシュ演算部110m(「第3ハッシュ演算部」)に置換された点である。また、署名検証装置20と署名検証装置120との相違点は、ハッシュ演算部20eがハッシュ演算部120e(「第4ハッシュ演算部」)に置換された点である。
【0074】
<処理>
次に本形態の処理について説明する。
[前処理及び秘密鍵生成処理]
第1実施形態と同じであるため説明を省略する。
【0075】
[署名生成処理]
次に、署名生成装置110の署名生成処理を説明する。図12は、第2実施形態の署名生成処理を説明するためのフローチャートである。以下、第1実施形態との相違点を中心に説明する。
【0076】
まず、入力部10dに、署名対象となるリカバリーメッセージMrecが入力され、これがメモリ10aに格納される(ステップS101)。本形態ではクリアーメッセージMclrは入力されない。その後、第1実施形態と同じ、ステップS2〜S8の処理が実行される。次に、ハッシュ演算部10mが、メモリ10aからビット結合値rと識別子idとを読み込み、それらのビット結合値γ=r|idに対し、ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する(ステップS109)。生成されたハッシュ値uはメモリ10aに格納される。その後、第1実施形態と同じ、ステップS10〜S14の処理が実行された後、ビット結合値rと楕円曲線演算値σとが送信部10sに送られ、送信部10sは、署名情報(r,σ)とをネットワーク40経由で署名検証装置120に送信する(ステップS115)。
【0077】
[署名検証処理]
次に、署名検証装置120の署名検証処理を説明する。図13は、第2実施形態の署名検証処理を説明するためのフローチャートである。以下、第1実施形態との相違点を中心に説明する。
【0078】
まず、署名検証装置20の通信部20dが、署名情報(r’,σ’)を受信する(ステップS121)。本形態ではクリアーメッセージMclrは受信されない。次に、入力部20sに署名生成装置10の識別子idが入力され、メモリ20aに格納される(ステップS22)。なお、識別子idがすでにメモリ20aに格納されているのであれば、ステップS22は省略可能である。次に、ハッシュ演算部20eが、メモリ20aから第1パート情報r’と識別子idとを読み込み、これらのビット列のビット結合からなるビット列γ’=r’|idに対し、ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する(ステップS123)。算出されたハッシュ値u’はメモリ20aに格納される。その後、第1実施形態のステップS24〜S36の処理によって署名検証とリカバリーメッセージの復元とが行われる。
【0079】
〔変形例等〕
なお、本発明は上述の各実施形態に限定されるものではない。例えば、第1実施形態では、復元署名対象情報recと双線形関数値Rと識別子idとの各ビット列のビット結合値rec|R|idをαとし、署名対象情報の復元値rec’と双線形関数値R’と識別子idとの各ビット列のビット結合値rec’|R’|idをα’とした。しかし、復元署名対象情報recと双線形関数値Rとの各ビット列を含むビット結合値をαとし、前記署名対象情報の復元値rec’と前記双線形関数値R’との各ビット列を含むビット結合値をα’とし、ビット結合値αを構成するビット列とビット結合値をα’を構成するビット列とが等しい場合にα=α’となるのであれば、αやα’が識別子idを含まなくてもよく、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0080】
また、同様に第1実施形態では、β=h|R|idとし、β’=h’|R’|idとしたが、ハッシュ値hと双線形関数値Rとの各ビット列を含むビット結合値をβとし、ハッシュ値h’と双線形関数値R’との各ビット列を含むビット結合値をβ’とし、ビット結合値βを構成するビット列とビット結合値β’を構成するビット列とが等しい場合にβ=β’となるのであれば、βやβ’が識別子idを含まなくてもよく、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0081】
また、同様に第1実施形態では、γ=r|Mclr|idとし、γ’=r’|Mclr|idとしたが、ビット結合値rのビット列を含むビット列をγとし、署名情報の第1パート情報r’のビット列を含むビット列をγ’とし、ビット結合値γを構成するビット列とビット結合値γ’を構成するビット列とが等しい場合にγ=γ’となるのであれば、γやγ’が識別子idを含まなくてもよく、Mclrを含まなくてもよくてもよく(例えば、第2実施形態)、その他の情報を含んでもよく、各情報がどのような順序で結合されていてもよい。
【0082】
また、署名検証装置20,120の判定部20iが、メモリ20aから第2パート情報σ’や剰余演算結果t’を読み込み、σ’が無限遠点Oであるか否かや、剰余演算結果t’が0であるか否かを判定し、σ’=Oであったり、t’=0であったりした場合に署名情報を拒絶する構成であってもよい。特に、t’=0であった場合に署名情報を拒絶する構成とした場合、ランダムオラクルモデルを前提としない実環境での安全性が向上する。すなわち、攻撃者が0=u mod p、u=H3(r|Mclr|id)を満たす整数rを発見できたとする。ここで、署名検証装置20,120がt’=0となることを許した場合には、攻撃者は、公開情報であるP1のみを用い、何れかの署名生成装置に成りすまして楕円曲線演算値σ=y・P1−t・Sid=y・P1を生成し、署名検証に合格する署名情報(r,σ)を生成できてしまう。署名検証装置20,120がt’=0となる署名情報を排除することで、このような攻撃を防止できる。
【0083】
また、第1,2実施形態では、(Z/pZ)\{0}の範囲から乱数yを選択することとした。しかし、0を含むZ/pZから乱数yを選び、署名検証時にステップS27の判定を行わない構成でもよい。さらには、演算効率は落ちるが、一般的な整数から乱数yを選ぶ構成であってもよい。また、ステップS11やステップS13の判定を行わない構成であってもよい。
【0084】
また、第1,2実施形態では、rec=encode(Mrec)としたが、rec=Mrecとし、ステップS2,S33,S34を実行しない構成であってもよい。また、第1,2実施形態では、剰余演算t=u mod pやt’=u’ mod pによってtやt’を算出することとしたが、t=u及びt’=u’とし、ステップS10,S24を実行しない構成であってもよい。
【0085】
また、ステップS4,S12においてP1の代わりに<P1>に属するその他の元(例えば、Pid)を用いてもよい。
【0086】
また、本形態ではリカバリーメッセージのビット長がどのような値であっても署名を生成できるため、リカバリーメッセージをヌル値とすることもできる。この場合には、クリアーメッセージのみが署名対象となる。このように、本形態の構成では、署名対象の自由度が向上する。
【0087】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0088】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0089】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0090】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0091】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0092】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【0093】
本発明は、電子署名を用いる様々な用途に適用可能である。
【図面の簡単な説明】
【0094】
【図1】図1は、第1実施形態のリカバリ署名システムを説明するためのシステム構成図である。
【図2】図2は、第1実施形態の署名生成装置の詳細構成を説明するためのブロック図である。
【図3】図3は、第1実施形態におけるハッシュ演算部10iの詳細構成の一例を説明するためのブロック図である。
【図4】図4は、第1実施形態の署名検証装置の詳細構成を説明するためのブロック図である。
【図5】図5は、第1実施形態の管理装置の詳細構成を説明するためのブロック図である。
【図6】図6は、第1実施形態の署名生成処理を説明するためのフローチャートである。
【図7】図7は、ステップS6の詳細処理を例示するためのフローチャートである。
【図8】図8は、第1実施形態の署名検証処理を説明するためのフローチャートである。
【図9】図9は、第1ビット位置及び第2ビット位置の設定例を説明する図である。
【図10】図10は、第2実施形態の署名生成装置の詳細構成を説明するためのブロック図である。
【図11】図11は、第2実施形態の署名検証装置の詳細構成を説明するためのブロック図である。
【図12】図12は、第2実施形態の署名生成処理を説明するためのフローチャートである。
【図13】図13は、第2実施形態の署名検証処理を説明するためのフローチャートである。
【符号の説明】
【0095】
1 リカバリ署名システム
10,110 署名生成装置
20,120 署名検証装置
30 管理装置
【特許請求の範囲】
【請求項1】
署名生成装置と署名検証装置とを有するリカバリ署名システムであって、
前記署名生成装置は、
有限体上の楕円曲線をEとし、楕円曲線E上の有理点からなる有限集合の要素数#Eを割り切る素数をpとし、楕円曲線E上のp等分点からなる有限集合をE[p]とし、上記有限体を基礎体とする拡大体からなる有限集合μpとし、有限集合E[p]の2つの元を有限集合μpの1つの元に写す非退化双線形ペアリング関数をe:E[p]×E[p]→μpとし、e(P1,P2)≠1を満たす有限集合E[p]の元をP1,P2∈E[p]とし、前記署名生成装置の識別子をidとし、識別子idに対応する有限集合E[p]の元をPidとし、整数であるマスター秘密鍵をmsとし、Pidの楕円曲線E上でのms倍点ms・Pidを前記署名生成装置の秘密鍵Sidとした場合における、当該秘密鍵Sidを格納する第1記憶部と、
秘匿される署名対象のビット列である復元署名対象情報recを格納する第2記憶部と、
任意の整数yを選択する任意数選択部と、
双線形関数値R=e(P1,P2)y∈μpを算出する第1双線形関数演算部と、
前記復元署名対象情報recのビット列と前記双線形関数値Rのビット列とを含むビット結合値αに対し、第1ハッシュ関数H1を作用させたハッシュ値h=H1(α)を算出する第1ハッシュ演算部と、
前記ハッシュ値hのビット列と前記双線形関数値Rのビット列とを含むビット結合値βに対し、任意のビット長のビット列を前記復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を作用させたハッシュ値v=H2(β)を算出する第2ハッシュ演算部と、
前記ハッシュ値vと前記復元署名対象情報recとの排他的論理和値xを算出する第1排他的論理和演算部と、
前記ハッシュ値hのビット列を第1ビット位置に配置し、前記排他的論理和値xのビット列を第2ビット位置に配置したビット結合値rを算出するビット結合部と、
前記ビット結合値rのビット列を含むビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する第3ハッシュ演算部と、
予め定められた規則に従って前記ハッシュ値uに対して定まる整数をtとした場合における、前記元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sidを算出する楕円曲線演算部と、
前記ビット結合値rと前記楕円曲線演算値σとからなる署名情報(r,σ)を送信する送信部と、を有し、
前記署名検証装置は、
前記元P2と、前記元P2の楕円曲線E上でのms倍点ms・P2であるマスター公開鍵mpと、を格納する第3記憶部と、
ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなる、署名情報(r’,σ’)を受信する受信部と、
前記第1パート情報r’と前記第2パート情報σ’を格納する第4記憶部と、
前記署名生成装置の識別子idに対応する有限集合E[p]の元Pidを格納する第5記憶部と、
前記第1パート情報r’のビット列を含むビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する第4ハッシュ演算部と、
前記予め定められた規則に従って前記ハッシュ値u’に対して定まる整数をt’とした場合における、双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’∈μpを算出する第2双線形関数演算部と、
前記第1パート情報r’の前記第1ビット位置のビット列h’と、前記第1パート情報r’の前記第2ビット位置のビット列x’とを抽出するビット分割部と、
前記ハッシュ値h’のビット列と前記双線形関数値R’のビット列とを含むビット結合値β’に対し、前記第2ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する第5ハッシュ演算部と、
前記ハッシュ値v’と前記ビット列x’との排他的倫理和値を、署名対象情報の復元値rec’として算出する第2排他的論理和演算部と、
前記署名対象情報の復元値rec’のビット列と前記双線形関数値R’のビット列とを含むビット結合値α’に対し、前記第1ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する第6ハッシュ演算部と、
前記ビット列h’と前記ハッシュ値h’’とが等しいか否かを判定する比較部と、を有する、
ことを特徴とするリカバリ署名システム。
【請求項2】
請求項1のリカバリ署名システムであって、
前記署名生成装置は、秘匿されない署名対象のビット列であるクリアーメッセージMclrを格納する第6記憶部を有し、
前記署名生成装置の前記第3ハッシュ演算部は、前記ビット結合値rのビット列と前記クリアーメッセージMclrのビット列とを含むビット結合値であるビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出するように構成され、
前記署名生成装置の前記送信部は、前記署名情報(r,σ)と前記クリアーメッセージMclrとを送信するように構成され、
前記署名検証装置の前記受信部は、前記署名情報(r’,σ’)と前記クリアーメッセージMclrとを受信するように構成され、
前記署名検証装置は、前記クリアーメッセージMclrを格納する第7記憶部を有し、
前記署名検証装置の前記第4ハッシュ演算部は、前記第1パート情報r’のビット列と前記クリアーメッセージMclrのビット列とを含むビット結合値であるビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出するように構成される、
ことを特徴とするリカバリ署名システム。
【請求項3】
請求項1又は2のリカバリ署名システムであって、
前記署名生成装置は、
前記ハッシュ値uに対して定まる整数tが0であるか否かを判定する第1判定部と、
前記ハッシュ値uに対して定まる整数tが0である場合に、前記任意数選択部に新たな任意の整数yを選択させ、その新たな任意の整数yに基づき、前記第1双線形関数演算部の処理と、前記第1ハッシュ演算部の処理と、前記第2ハッシュ演算部の処理と、前記第1排他的論理和演算部の処理と、前記ビット結合部の処理と、前記第3ハッシュ演算部の処理とをやり直させる制御部と、を有し、
前記署名検証装置は、
前記ハッシュ値u’に対して定まる整数t’が0であるか否かを判定し、整数t’が0である場合に、前記署名情報(r’,σ’)が正当でないと判定する第2判定部を有する、
ことを特徴とするリカバリ署名システム。
【請求項4】
請求項1から3の何れかのリカバリ署名システムを構成する署名生成装置。
【請求項5】
請求項1から3の何れかのリカバリ署名システムを構成する署名検証装置。
【請求項6】
請求項4の署名生成装置が実行する署名生成方法。
【請求項7】
請求項5の署名検証装置が実行する署名検証方法。
【請求項8】
請求項4の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項9】
請求項5の署名検証装置としてコンピュータを機能させるためのプログラム。
【請求項1】
署名生成装置と署名検証装置とを有するリカバリ署名システムであって、
前記署名生成装置は、
有限体上の楕円曲線をEとし、楕円曲線E上の有理点からなる有限集合の要素数#Eを割り切る素数をpとし、楕円曲線E上のp等分点からなる有限集合をE[p]とし、上記有限体を基礎体とする拡大体からなる有限集合μpとし、有限集合E[p]の2つの元を有限集合μpの1つの元に写す非退化双線形ペアリング関数をe:E[p]×E[p]→μpとし、e(P1,P2)≠1を満たす有限集合E[p]の元をP1,P2∈E[p]とし、前記署名生成装置の識別子をidとし、識別子idに対応する有限集合E[p]の元をPidとし、整数であるマスター秘密鍵をmsとし、Pidの楕円曲線E上でのms倍点ms・Pidを前記署名生成装置の秘密鍵Sidとした場合における、当該秘密鍵Sidを格納する第1記憶部と、
秘匿される署名対象のビット列である復元署名対象情報recを格納する第2記憶部と、
任意の整数yを選択する任意数選択部と、
双線形関数値R=e(P1,P2)y∈μpを算出する第1双線形関数演算部と、
前記復元署名対象情報recのビット列と前記双線形関数値Rのビット列とを含むビット結合値αに対し、第1ハッシュ関数H1を作用させたハッシュ値h=H1(α)を算出する第1ハッシュ演算部と、
前記ハッシュ値hのビット列と前記双線形関数値Rのビット列とを含むビット結合値βに対し、任意のビット長のビット列を前記復元署名対象情報recとビット長が等しいビット列に変換する第2ハッシュ関数H2を作用させたハッシュ値v=H2(β)を算出する第2ハッシュ演算部と、
前記ハッシュ値vと前記復元署名対象情報recとの排他的論理和値xを算出する第1排他的論理和演算部と、
前記ハッシュ値hのビット列を第1ビット位置に配置し、前記排他的論理和値xのビット列を第2ビット位置に配置したビット結合値rを算出するビット結合部と、
前記ビット結合値rのビット列を含むビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出する第3ハッシュ演算部と、
予め定められた規則に従って前記ハッシュ値uに対して定まる整数をtとした場合における、前記元P1の楕円曲線E上でのy倍点y・P1と、Sidの楕円曲線E上でのt倍点t・Sidの楕円逆元−t・Sidとを楕円加算した楕円曲線演算値σ=y・P1−t・Sidを算出する楕円曲線演算部と、
前記ビット結合値rと前記楕円曲線演算値σとからなる署名情報(r,σ)を送信する送信部と、を有し、
前記署名検証装置は、
前記元P2と、前記元P2の楕円曲線E上でのms倍点ms・P2であるマスター公開鍵mpと、を格納する第3記憶部と、
ビット列である第1パート情報r’と、有限集合E[p]の元である第2パート情報σ’とからなる、署名情報(r’,σ’)を受信する受信部と、
前記第1パート情報r’と前記第2パート情報σ’を格納する第4記憶部と、
前記署名生成装置の識別子idに対応する有限集合E[p]の元Pidを格納する第5記憶部と、
前記第1パート情報r’のビット列を含むビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出する第4ハッシュ演算部と、
前記予め定められた規則に従って前記ハッシュ値u’に対して定まる整数をt’とした場合における、双線形関数値R’=e(σ’,P2)・e(Pid,mp)t’∈μpを算出する第2双線形関数演算部と、
前記第1パート情報r’の前記第1ビット位置のビット列h’と、前記第1パート情報r’の前記第2ビット位置のビット列x’とを抽出するビット分割部と、
前記ハッシュ値h’のビット列と前記双線形関数値R’のビット列とを含むビット結合値β’に対し、前記第2ハッシュ関数H2を作用させたハッシュ値v’=H2(β’)を算出する第5ハッシュ演算部と、
前記ハッシュ値v’と前記ビット列x’との排他的倫理和値を、署名対象情報の復元値rec’として算出する第2排他的論理和演算部と、
前記署名対象情報の復元値rec’のビット列と前記双線形関数値R’のビット列とを含むビット結合値α’に対し、前記第1ハッシュ関数H1を作用させたハッシュ値h’’=H1(α’)を算出する第6ハッシュ演算部と、
前記ビット列h’と前記ハッシュ値h’’とが等しいか否かを判定する比較部と、を有する、
ことを特徴とするリカバリ署名システム。
【請求項2】
請求項1のリカバリ署名システムであって、
前記署名生成装置は、秘匿されない署名対象のビット列であるクリアーメッセージMclrを格納する第6記憶部を有し、
前記署名生成装置の前記第3ハッシュ演算部は、前記ビット結合値rのビット列と前記クリアーメッセージMclrのビット列とを含むビット結合値であるビット列γに対し、第3ハッシュ関数H3を作用させたハッシュ値u=H3(γ)を算出するように構成され、
前記署名生成装置の前記送信部は、前記署名情報(r,σ)と前記クリアーメッセージMclrとを送信するように構成され、
前記署名検証装置の前記受信部は、前記署名情報(r’,σ’)と前記クリアーメッセージMclrとを受信するように構成され、
前記署名検証装置は、前記クリアーメッセージMclrを格納する第7記憶部を有し、
前記署名検証装置の前記第4ハッシュ演算部は、前記第1パート情報r’のビット列と前記クリアーメッセージMclrのビット列とを含むビット結合値であるビット列γ’に対し、第3ハッシュ関数H3を作用させたハッシュ値u’=H3(γ’)を算出するように構成される、
ことを特徴とするリカバリ署名システム。
【請求項3】
請求項1又は2のリカバリ署名システムであって、
前記署名生成装置は、
前記ハッシュ値uに対して定まる整数tが0であるか否かを判定する第1判定部と、
前記ハッシュ値uに対して定まる整数tが0である場合に、前記任意数選択部に新たな任意の整数yを選択させ、その新たな任意の整数yに基づき、前記第1双線形関数演算部の処理と、前記第1ハッシュ演算部の処理と、前記第2ハッシュ演算部の処理と、前記第1排他的論理和演算部の処理と、前記ビット結合部の処理と、前記第3ハッシュ演算部の処理とをやり直させる制御部と、を有し、
前記署名検証装置は、
前記ハッシュ値u’に対して定まる整数t’が0であるか否かを判定し、整数t’が0である場合に、前記署名情報(r’,σ’)が正当でないと判定する第2判定部を有する、
ことを特徴とするリカバリ署名システム。
【請求項4】
請求項1から3の何れかのリカバリ署名システムを構成する署名生成装置。
【請求項5】
請求項1から3の何れかのリカバリ署名システムを構成する署名検証装置。
【請求項6】
請求項4の署名生成装置が実行する署名生成方法。
【請求項7】
請求項5の署名検証装置が実行する署名検証方法。
【請求項8】
請求項4の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項9】
請求項5の署名検証装置としてコンピュータを機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2010−2662(P2010−2662A)
【公開日】平成22年1月7日(2010.1.7)
【国際特許分類】
【出願番号】特願2008−161298(P2008−161298)
【出願日】平成20年6月20日(2008.6.20)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成22年1月7日(2010.1.7)
【国際特許分類】
【出願日】平成20年6月20日(2008.6.20)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]