Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
ハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法、プログラム、および記録媒体
説明

ハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法、プログラム、および記録媒体

【課題】圧縮手段が第2原像発見困難性と一方向性とを有しているならば、第2原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供する。
【解決手段】本発明のハッシュ値生成装置は、入力された任意長のデータXをデータYに変換する前処理部と、データYにパディングを行いデータ長がm−nビットの倍数のデータZを出力するデータ長調整部と、圧縮関数を用いてデータZを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データYが次の2つの条件を満足するように、データXをデータYに変換する。(条件1)データZを、C個のm−nビットのブロックz[1],…,z[C]に分割した場合に、すべてのブロックz[1],…,z[C]がデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含む。(条件2)データXとデータYとは一対一に対応する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、通信路上または記録媒体上のデータに対してそのハッシュ値を生成するハッシュ値生成装置とハッシュ値生成方法、データとハッシュ値の組に対してその暗号学的安全性を検証する検証装置と検証方法、およびそれらのプログラムと記録媒体に関する。
【背景技術】
【0002】
任意長のデータから、固定長(以下、nビットとする)の値を決定する関数
H:{0,1}→{0,1}
をハッシュ関数という。ただし、“{0,1}”は、0または1が任意の長さ並んだビット列を、“{0,1}”は、0または1がn個並んだビット列を示している。なお、ハッシュ関数では、マークル・ダンガード(Merkle-Damgard)構成と呼ばれる反復法を用いたものが主流である(非特許文献1、2)。マークル・ダンガード構成のハッシュ関数Hは、入力されたデータXにパディングを施した上で、mビット(ただし、mはnより大きい整数)のデータをnビットのデータに圧縮する圧縮関数hを繰り返し利用し、任意長の入力データに対するnビットのハッシュ値を得る。代表的な圧縮関数には、m=672、n=160の
sha1:{0,1}160+512→{0,1}160
や、m=768、n=256の
sha256:{0,1}256+512→{0,1}256
などがある。
【0003】
ハッシュ関数Hが暗号学的に安全であるためには、衝突発見困難性、第2原像発見困難性、一方向性の3つの条件を満たすことが必要とされている。衝突発見困難性とは、
H(X)=H(X’) かつ X≠X’
となる(X,X’)の組を見つけることが難しいことである。ハッシュ関数Hの出力は2通りあるので、nは衝突発見困難性の程度を示すパラメータであり、nを大きくすれば衝突発見困難性が高くなる。なお、衝突発見困難性は、出力長nの半分の難しさであることが知られている。第2原像発見困難性とは、任意に与えられたXに対し、
H(X)=H(X’) かつ X≠X’
となるようなX’を見つけることが難しいことである。一方向性とは、任意に与えられたVに対し、V=H(X’)となるようなX’を見つけることが難しいことである。ただし、「Vが任意に与えられる」とは、Xを任意に選び、
V←H(X)
と計算してVの任意の値を決定することを指す。また、“←”は、右辺の計算結果を左辺の変数の値とすること(ここでは、Vの値をH(X)とすること、もしくはH(X)を変数Vに代入すること)を示している。また、マークル・ダンガード構成のハッシュ関数Hが暗号学的に安全であるためには、圧縮関数hも、衝突発見困難性、第2原像発見困難性、一方向性が必要である。
【0004】
第2原像発見困難性、一方向性について、さらに表現を変えて説明する。例えば、圧縮関数hの第2原像発見困難性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータWを選ぶ。次にデータの長さがm−|W|のデータXが任意に選ばれ、データXの値が攻撃者に知らされる。このとき、
h(X‖W)=h(X’) かつ X‖W≠X’
となるような長さmのデータX’を攻撃者がみつけることが困難だという性質が、圧縮関数hの第2原像発見困難性である。ただし、“‖”はビット列の結合を意味し、mは圧縮関数hに入力されるビット列の長さである。また、例えば、圧縮関数hの一方向性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータWを選ぶ。次にデータの長さがm−|W|のデータXが任意に選ばれ、h(X‖W)の値が攻撃者に知らされる。このとき、
h(X‖W)=h(X’) かつ X‖W≠X’
となるような長さmのデータX’を攻撃者がみつけることが困難だという性質が、圧縮関数hの一方向性である。
【0005】
図1は従来のハッシュ値生成装置の機能構成例を示す図、図2は従来のハッシュ値生成装置の処理フローの例を示す図である。ハッシュ値生成装置900は、マークル・ダンガード構成のハッシュ関数を用いて、ハッシュ値を生成する。ハッシュ値生成装置900は、データ長調整部980とデータ圧縮部990とを備える。データ長調整部980は、データY分割手段981とデータZ生成手段982とを有し、入力された任意の長さのデータYにパディングを行い、データ長がm−nビットの倍数のデータZを出力する。データ圧縮部990は、データZ分割手段991と圧縮手段992とを有し、入力されたデータZを圧縮して、データ長がnビットのハッシュ値を求める。
【0006】
具体的には、例えば、データY分割手段981は、任意長のデータYが入力されると、データYを、
Y→y[1]‖y[2]‖・・・‖y[B]
のように、B−1個のm−nビットのブロックy[1],…,y[B−1]と、1個のm−nビット以下のブロックy[B]に分割する(S981)。ここで、“→”は、左辺を右辺のように変換(分割)することを示している。また、Bは分割されたブロックの数であり、
【数1】

である。
【0007】
データZ生成手段982は、|y[B]|≦m−n−σ−1かを確認する(S983)。つまり、ブロックy[B]のデータ長がm−n−σ−1以下かを確認する。ステップS983がYesの場合、データZ生成手段982は、データZを、
Z←Y‖10m−n−σ−1−|y[B]|‖<|Y|>
のように生成する(S984)。ステップS983がNoの場合、データZ生成手段982は、データZを、
Z←Y‖10m−n−1−|y[B]|‖0m−n−σ‖<|Y|>
のように生成する(S985)。ただし、“0”は“0”がm個並んだビット列、<|Y|>はデータYのデータ長|Y|をσビットで表現したビット列である。例えば、σは64である。このようにデータZを生成するので、データZは、データ長がm−nの倍数となる。
【0008】
データZ分割手段991は、データZを、
Z→z[1]‖z[2]‖・・・‖z[C]
のように、C個のm−nビットのブロックz[1],…,z[C]に分割する(S991)。また、Cは分割されたブロックの数であり、C=|Z|/(m−n)である。
【0009】
圧縮手段992は、nビットの変数v[0]に、nビットの初期値vを設定する(S993)。また、変数cに1を代入する(S994)。そして、圧縮手段992は、
v[c]←h(z(c)‖v[c−1])
のように圧縮関数hを用いた演算を行う(S995)。cがCと一致するかを確認し(S996)、Noの場合にはcの値を1増やし、ステップS995に戻る(S997)。ステップS996がYesの場合には、変数v[C]の値をハッシュ値として出力する(S998)。
【非特許文献1】Ralph C. Merkle, “One Way Hash Functions and DES,” CRYPTO 1989, LNCS vol.435, pp.428-446, Springer, Heidelberg(1990).
【非特許文献2】Ivan Damgard, “A Design Principle for Hash Functions,” CRYPTO 1989, LNCS vol.435, pp.416-427, Springer, Heidelberg (1990).
【発明の開示】
【発明が解決しようとする課題】
【0010】
マークル・ダンガード構成のハッシュ値生成装置(ハッシュ関数)では、圧縮手段(圧縮関数)が衝突発見困難性を有していれば、ハッシュ値生成装置も衝突発見困難性が保証されることが知られている。しかし、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第2原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第2原像発見困難性と一方向性とを保証できなかった。
【0011】
これは、圧縮関数に入力されるブロックの中に、ハッシュ値生成装置への入力データを含まないブロックが存在する可能性があることが原因であった。本発明は、圧縮手段が第2原像発見困難性と一方向性とを有しているならば、第2原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供することを目的とする。
【課題を解決するための手段】
【0012】
本発明のハッシュ値生成装置は、mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成する。本発明のハッシュ値生成装置は、入力された任意長のデータXをデータYに変換する前処理部と、データYにパディングを行いデータ長がm−nビットの倍数のデータZを出力するデータ長調整部と、圧縮関数を用いてデータZを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データYが次の2つの条件を満足するように、データXをデータYに変換する。
【0013】
(条件1)データXのデータ長がμビット以上のときに、データZを、C個のm−nビットのブロックz[1],…,z[C]に分割した場合に(ただし、CはデータZをm−nビットずつに分割した場合の分割の数)、すべてのブロックz[1],…,z[C]がデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含む。
(条件2)データXとデータYとは一対一に対応する。
【0014】
なお、本発明のハッシュ値生成装置の前処理部は、より具体的には、データX分割手段とデータY生成手段とを備えればよい。そして、データX分割手段は、データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割する(ただし、AはデータXをm−nビットずつに分割した場合の分割の数)。データY生成手段は、ブロックx[1],…,x[A]を、全てのブロックがデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、A’−1個のm−nビットのブロックx’[1],…,x’[A’−1]と1個のm−nビット以下のブロックx’[A’]とに変換し(ただし、A’はA以上の整数)、x’[1]‖x’[2]‖…‖x’[A’](ただし、“‖”はビット列の結合を意味する記号)を含むビット列をデータYとする。このとき、データY生成手段は、ブロックx[1],…,x[A]の組合せとブロックx’[1],…,x’[A’]の組合せとが一対一に対応するようにする。また、データY生成手段は、x[A’]のデータ長を、データ長調整部の処理によって生成されるデータZのデータ長が、A’×(m−n)となるように調整する。例えば、データ長調整部がデータYのデータ長にかかわらずデータYに付加するビット数をσ+1ビットとすると、データY生成手段は、x[A’]のデータ長をm−n−σ−1以下となるようにすれば、データZのデータ長が、A’×(m−n)となる。ただし、この具体例に限定する必要はなく、データ長調整部とデータ圧縮部の処理を考慮して、A’=B=Cとなるようにブロックx’[1],…,x’[A’]に変換する方法であれば別の方法でもよい。
【0015】
データY生成手段は以下のような処理を行えばよい。例えば、データY生成手段は、μ≦|x[A]|≦m−n−σ―2ならば、データXにビット“0”を付加した結果を、データYとする。|x[A]|≦μ―1、かつ、A≧2ならば、ブロックx[A−1]をm−n−μビットのブロックx’[A−1]とμビットのブロックx”に分割し、x”‖x[A]をブロックx’[A]とし、x[1]‖…‖x[A−2]‖x’[A−1]‖10μ-1‖x’[A]‖1をデータYとする。|x[A]|≦μ―1、かつ、A=1ならば、x[1]‖1をデータYとする。|x[A]|≧m−n−σ―1ならば、ブロックx[A]を|x[A]|−μビットのブロックx’[A]とμビットのブロックx”に分割し、ブロックx”をブロックx[A+1]とし、x[1]‖…‖x[A−1]‖x’[A]‖10m−n−|x’[A]|−1‖x’[A+1]‖1をデータYとする。ただし、“|x[A]|”はx[A]のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“0μ-1”は“0”がμ-1個並んだビット列、σはデータ長調整部内部がデータYのデータ長にかかわらず付加するビット数より1少ない数(データ長調整部がデータYのデータ長にかかわらず付加するビット数をσ+1ビット)とする。なお、この例のデータY生成手段は、最後の2つのブロックを変更することで、すべてのブロックz[1],…,z[C]がデータX内のμビット以上を含むようにしている。しかし、最後の2つに限定する必要はなく、3つ以上のブロックを変更してもよい。
【発明の効果】
【0016】
本発明のハッシュ値生成装置によれば、データXのデータ長がμビット以上のときに、データZを分割することで得られるC個のブロックz[1],…,z[C]のすべてが、データX内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータX内のビット列が含まれることになる。このことによって、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することが保証できる。また、データXとデータYとは一対一に対応しているので、衝突発見困難性は維持することができる。また、本発明のハッシュ値生成装置は、従来のマークル・ダンガード構成のハッシュ値生成装置に前処理部を付加するだけで、第2原像発見困難性と一方向性を保証できるようになる。つまり、すでに広く普及しているマークル・ダンガード構成のハッシュ値生成装置をそのまま利用できるという利点がある。
【発明を実施するための最良の形態】
【0017】
以下に、本発明の実施例を説明する。なお、同じ機能を有する構成部やステップには同じ番号を付し、重複説明を省略する。
【0018】
分析
まず、なぜ従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第2原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第2原像発見困難性と一方向性とを保証できなかったかを説明する。
【0019】
図2に示したように、従来のマークル・ダンガード構成のハッシュ値生成装置900では、データ長調整部980は、データZのデータ長がm−nビットの倍数となるようにビット列をデータYに付加する。ただし、データ長調整部980は、データYのデータ長にかかわらず少なくともσ+1ビットを付加する。したがって、データZのデータ長は、データYのデータ長よりもσ+1ビット以上長くなる。この結果、ブロックy[B]のデータ長がm−n−σ−1よりも長いときには、データZを分割したときのブロックの数の方が、データYを分割したときのブロックの数よりも多くなる(つまり、C=B+1となる。)。そして、最後のブロックz[C]には、データYの中のビット列がまったく含まれていない。また、ブロックy[B]のデータ長が短いときには、最後のブロックz[C]には、データYの中のビット列が少ししか含まれていない。
【0020】
したがって、データ圧縮部990の圧縮手段992での圧縮関数hを用いた繰り返し演算の中で、最後の演算では、入力されるデータ(ブロックz[C])にデータYの中のビット列が十分含まれていない可能性がある。このことが、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第2原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第2原像発見困難性と一方向性とを保証できなかったことの原因である。
【実施例1】
【0021】
上記の分析から、本発明では、データXのデータ長がμビット以上のときに、圧縮関数に入力されるすべてのブロックが、ハッシュ値生成装置への入力データをμビット以上含むようにする。図3は、実施例1のハッシュ値生成装置の機能構成例を示す図である。図4は、実施例1のハッシュ値生成装置の処理フローを示す図である。
【0022】
ハッシュ値生成装置100は、mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成する。ハッシュ値生成装置100は、前処理部110、データ長調整部980、データ圧縮部990を備える。前処理部110は、あらかじめ定めた条件を満足するように入力された任意長のデータXをデータYに変換する(S110)。データ長調整部980は、データYにパディングを行いデータ長がm−nビットの倍数のデータZを出力する(S980)。データ圧縮部990は、圧縮関数を用いてデータZを圧縮してハッシュ値を求める(S990)。データ長調整部980とデータ圧縮部990は、従来のハッシュ値生成装置900と同じである。なお、従来のハッシュ値生成装置900の説明では、入力データ(ハッシュ値を求める対象となるデータ)をデータYとしたが、ハッシュ値生成装置100の説明では、入力データ(ハッシュ値を求める対象となるデータ)はデータXであることに注意されたい。
【0023】
前処理部110は、データX分割手段120とデータY生成手段130とを備え、データYが次の2つの条件を満足するように、データXをデータYに変換する。
(条件1)データXのデータ長がμビット以上のときに、データ長調整部980が生成するデータZを、C個のm−nビットのブロックz[1],…,z[C]に分割した場合に(ただし、CはデータZをm−nビットずつに分割した場合の分割の数)、すべてのブロックz[1],…,z[C]がデータX内のμビット以上を含む。
(条件2)データXとデータYとは一対一に対応する。
ただし、μはあらかじめ定めた整数であって、セキュリティーレベルを決めるパラメータである。μ=nにすれば、第2原像発見困難性と一方向性の程度が、出力長nの難しさとなる。また、μ=n/2にすれば、第2原像発見困難性と一方向性の程度が、出力長nの半分の難しさ(衝突発見困難性と同じ程度)となる。したがって、μの値は、n/2〜nの範囲で決めることが適当である。
【0024】
前処理部110が、このようにデータYを生成するので、データZを分割することで得られるC個のブロックz[1],…,z[C]のすべてが、データX内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータX内のビット列が含まれることになる。このことによって、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することが保証できる。また、データXとデータYとは一対一に対応しているので、衝突発見困難性は維持することができる。
【0025】
さらに、本発明は、入力データ(ハッシュ値を求める対象となるデータ)に対して前処理部110があらかじめ定めた条件を満足するように変換を行い、変換後のデータを従来のハッシュ値生成装置900に入力する。そして、前処理部110を付加したことのみによって、広く普及している従来のハッシュ値生成装置900を利用しながら、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することを保証できる。また、衝突発見困難性は維持する。従って、広く普及している技術を有効に利用できる。
【0026】
前処理部110は、より具体的には、以下のように処理を行えばよい。データX分割手段120は、データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割する(ただし、AはデータXをm−nビットずつに分割した場合の分割の数)。データY生成手段130は、ブロックx[1],…,x[A]を、全てのブロックがデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、A’−1個のm−nビットのブロックx’[1],…,x’[A’−1]と1個のm−nビット以下のブロックx’[A’]とに変換し(ただし、A’はA以上の整数)、x’[1]‖x’[2]‖…‖x’[A’](ただし、“‖”はビット列の結合を意味する記号)を含むビット列をデータYとする。このとき、データY生成手段は、ブロックx[1],…,x[A]の組合せとブロックx’[1],…,x’[A’]の組合せとが一対一に対応するようにする。また、データY生成手段は、x[A’]のデータ長を、データ長調整部980の処理によって生成されるデータZのデータ長が、A’×(m−n)となるように調整する。例えば、データ長調整部980がデータYのデータ長にかかわらずデータYに付加するビット数をσ+1ビットとすると、データY生成手段130が、x[A’]のデータ長をm−n−σ−1以下となるようにしておけば、データZのデータ長が、A’×(m−n)となる。ただし、このような処理を行うためには、mはn+σ+μ+2以上でなければならない。μ=n、σ=64とすると、広く普及している圧縮関数sha1もsha256もこの条件を満たす。なお、上述の具体例に限定する必要はなく、データ長調整部980とデータ圧縮部990の処理を考慮して、A’=B=Cとなるようにブロックx’[1],…,x’[A’]に変換する方法であれば別の方法でも同じ効果を得ることができる。
【0027】
図5に、前処理部110の処理フローの具体例を示す。この処理フローは、図2に示したデータ長調整部980とデータ圧縮部990と組み合わせることを前提としたものである。データX分割手段120は、データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割する(ただし、AはデータXをm−nビットずつに分割した場合の分割の数)(S120)。
【0028】
データY生成手段130は、μ≦|x[A]|≦m−n−σ―2かを確認する(S131)。データY生成手段130は、ステップS131がYesならば、データXにビット“0”を付加した結果を、データYとする(S132)。この場合、A’=Aであり、x’[1],…,x’[A−1]はx[1],…,x[A−1]と同じであり、x’[A−1]はx[A−1]‖0である。
【0029】
データY生成手段130は、ステップS131がNoならば、データY生成手段130は、|x[A]|≦μ―1かを確認する(S133)。データY生成手段130は、ステップS133がYesならば、A≧2かを確認する(S134)。データY生成手段130は、ステップS134がYesならば、ブロックx[A−1]をm−n−μビットのブロックx’[A−1]とμビットのブロックx”に分割する(S135)。x”‖x[A]をブロックx’[A]とする(S136)。そして、x[1]‖…‖x[A−2]‖x’[A−1]‖10μ-1‖x’[A]‖1をデータYとする(S137)。この場合、A’=Aであり、x’[1],…,x’[A−2]はx[1],…,x[A−2]と同じである。データY生成手段130は、ステップS134がNoならば、x[1]‖1をデータYとする(S138)。この場合、A’=Aであり、x’[1],…,x’[A−1]はx[1],…,x[A−1]と同じであり、x’[A−1]はx[A−1]‖1である。
【0030】
データY生成手段130は、ステップS133がNo(つまり、|x[A]|≧m−n−σ―1)ならば、ブロックx[A]を|x[A]|−μビットのブロックx’[A]とμビットのブロックx”に分割する(S139)。ブロックx”をブロックx[A+1]とする(S140)。x[1]‖…‖x[A−1]‖x’[A]‖10m−n−|x’[A]|−1‖x’[A+1]‖1をデータYとする(S141)。この場合、A’=A+1であり、x’[1],…,x’[A−1]はx[1],…,x[A−1]と同じである。ただし、“|x[A]|”はx[A]のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“0μ-1”は“0”がμ-1個並んだビット列、σはデータYのデータ長|Y|を表現したビット数であり、データ長調整部980がデータYのデータ長にかかわらず付加するビット数より1少ない数である。なお、この例のデータY生成手段130は、最後の2つのブロックを変更することで、すべてのブロックz[1],…,z[C]がデータX内のμビット以上を含むようにしている。しかし、最後の2つに限定する必要はなく、3つ以上のブロックを変更してもよい。
【0031】
図6は、前処理部110を付加した場合のデータ圧縮部990(圧縮手段992)の処理を示す図である。上述のように、前処理部110の処理は、ブロックx[A]のデータ長によって異なる。したがって、データ圧縮部990の処理も、ブロックx[A]のデータ長によって異なる。μ≦|x[A]|≦m−n−σ―2の場合、圧縮関数hへの入力は、x[1],…,x[A−1],x[A]‖0‖10m−n−σ−1−|y[B]|‖<|Y|>となる。よって、すべての入力にデータXがμビット以上含まれている。|x[A]|≦μ―1かつA≧2の場合、圧縮関数hへの入力は、x[1],…,x’[A−1]‖10μ−1,x’[A]‖1‖10m−n−σ−1−|y[B]|‖<|Y|>となる。よって、すべての入力にデータXがμビット以上含まれている。|x[A]|≦μ―1かつA=1の場合、圧縮関数hへの入力は、x[1]‖1‖10m−n−σ−1−|y[B]|‖<|Y|>のみとなる。この場合は、データXがμビット以上含まれていない。しかし、入力されたデータX自体がμビットより短いので、本発明の解決すべき課題の対象外である。|x[A]|≧m−n−σ―1の場合、圧縮関数hへの入力は、x[1],…,x[A−1],x’[A]‖10m−n−|x’[A]|−1,x’[A+1]‖1‖10m−n−σ−1−|y[B]|‖<|Y|>となる。よって、すべての入力にデータXがμビット以上含まれている。したがって、入力されたデータXのデータ長がμビット以上であれば、常に圧縮関数への入力の中にμビット以上のデータX内のビット列が含まれることが分かる。
【実施例2】
【0032】
図7に本発明の検証装置の機能構成例を示す。また、図8に本発明の検証装置の処理フロー例を示す。検証装置500は、実施例1で示したハッシュ値生成装置100と比較部510と記録部590を備える。検証装置500は、データXとハッシュ値τが入力、検証結果が出力である。
【0033】
検証装置500内のハッシュ値生成装置100は、データXからハッシュ値τ’を生成する(S100)。比較部510は、ハッシュ値τとハッシュ値τ’とを比較する。そして、τ=τ’ならば、データ内容の整合性が検証されたとする。τ≠τ’ならば、データの改ざんがあると判断する。そして、検証結果を出力する(S510)。なお、記録部590を備えず、その他の構成部でこれらの情報を記録してもよい。
このような構成なので、検証装置500でも、ハッシュ値生成装置100と同じ効果を得ることができる。
【0034】
図9に、コンピュータの機能構成例を示す。なお、本発明のハッシュ値生成装置および検証装置は、コンピュータ2000の記録部2020に、本発明の各構成部としてコンピュータ2000を動作させるプログラムを読み込ませ、処理部2010、入力部2030、出力部2040などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【0035】
本発明のハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法は、例えば携帯電話、パソコン、ルータ、サーバなどに組み込み、送受信されるデータや蓄積されたデータに対するハッシュ値を生成することまたは検証することに利用できる。
【図面の簡単な説明】
【0036】
【図1】従来のハッシュ値生成装置の機能構成例を示す図。
【図2】従来のハッシュ値生成装置の処理フローの例を示す図。
【図3】実施例1のハッシュ値生成装置の機能構成例を示す図。
【図4】実施例1のハッシュ値生成装置の処理フローを示す図。
【図5】前処理部110の処理フローの具体例を示す図。
【図6】前処理部110を付加した場合のデータ圧縮部990の処理を示す図。
【図7】本発明の検証装置の機能構成例を示す図。
【図8】本発明の検証装置の処理フロー例を示す図。
【図9】コンピュータの機能構成例を示す図。
【符号の説明】
【0037】
100、900 ハッシュ値生成装置 110 前処理部
120 データX分割手段 130 データY生成手段
500 検証装置 510 比較部
590 記録部 980 データ長調整部
981 データY分割手段 982 データZ生成手段
990 データ圧縮部 991 データZ分割手段
992 圧縮手段

【特許請求の範囲】
【請求項1】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データXをデータYに変換する前処理部と、
データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整部と、
前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データZを、C個のm−nビットのブロックz[1],…,z[C]に分割した場合に(ただし、CはデータZをm−nビットずつに分割した場合の分割の数)、すべてのブロックz[1],…,z[C]がデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、かつ、
データXとデータYとは一対一に対応するように
データXをデータYに変換する
ことを特徴とするハッシュ値生成装置。
【請求項2】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データXをデータYに変換する前処理部と、
データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整部と、
前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割する(ただし、AはデータXをm−nビットずつに分割した場合の分割の数)データX分割手段と、
前記ブロックx[1],…,x[A]を、全てのブロックがデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、A’−1個のm−nビットのブロックx’[1],…,x’[A’−1]と1個のm−nビット以下のブロックx’[A’]とに変換し(ただし、A’はA以上の整数)、x’[1]‖x’[2]‖…‖x’[A’](ただし、“‖”はビット列の結合を意味する記号)を含むビット列をデータYとするデータY生成手段と
を有し、
前記データY生成手段は、ブロックx[1],…,x[A]の組合せとブロックx’[1],…,x’[A’]の組合せとが一対一に対応するようにし、かつ
前記データY生成手段は、x[A’]のデータ長を、前記データ長調整部の処理によって生成されるデータZのデータ長が、A’×(m−n)となるようにする
ことを特徴とするハッシュ値生成装置。
【請求項3】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データXをデータYに変換する前処理部と、
データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整部と、
前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割するデータX分割手段と、
μ≦|x[A]|≦m−n−σ―2ならば、
データXにビット“0”を付加した結果を、データYとし、
|x[A]|≦μ―1、かつ、A≧2ならば、
ブロックx[A−1]をm−n−μビットのブロックx’[A−1]とμビットのブロックx”に分割し、
x”‖x[A]をブロックx’[A]とし、
x[1]‖…‖x[A−2]‖x’[A−1]‖10μ-1‖x’[A]‖1をデータYとし、
|x[A]|≦μ―1、かつ、A=1ならば、
x[1]‖1をデータYとし、
|x[A]|≧m−n−σ―1ならば、
ブロックx[A]を|x[A]|−μビットのブロックx’[A]とμビットのブロックx”に分割し、
ブロックx”をブロックx[A+1]とし、
x[1]‖…‖x[A−1]‖x’[A]‖10m−n−|x’[A]|−1‖x’[A+1]‖1をデータYとするデータY生成手段と
を有す
(ただし、AはデータXをm−nビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“|x[A]|”はx[A]のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“0μ-1”は“0”がμ-1個並んだビット列、前記データ長調整部がデータYのデータ長にかかわらず付加するビット数をσ+1ビットとする)
ことを特徴とするハッシュ値生成装置。
【請求項4】
データXとハッシュ値τとを入力とし、データXの検証を行う検証装置であって、
データXに対するハッシュ値τ’を出力する請求項1から3のいずれかに記載のハッシュ生成装置と、
前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータXの検証結果を出力する比較部と
を備える検証装置。
【請求項5】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データXをデータYに変換する前処理ステップと、
データ長調整部で、データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データZを、C個のm−nビットのブロックz[1],…,z[C]に分割した場合に(ただし、CはデータZをm−nビットずつに分割した場合の分割の数)、すべてのブロックz[1],…,z[C]がデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、かつ、
データXとデータYとは一対一に対応するように
データXをデータYに変換する
ことを特徴とするハッシュ値生成方法。
【請求項6】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データXをデータYに変換する前処理ステップと、
データ長調整部で、データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割する(ただし、AはデータXをm−nビットずつに分割した場合の分割の数)データX分割サブステップと、
前記ブロックx[1],…,x[A]を、全てのブロックがデータX内のμビット(ただし、μはあらかじめ定めた整数)以上を含むように、A’−1個のm−nビットのブロックx’[1],…,x’[A’−1]と1個のm−nビット以下のブロックx’[A’]とに変換し(ただし、A’はA以上の整数)、x’[1]‖x’[2]‖…‖x’[A’](ただし、“‖”はビット列の結合を意味する記号)を含むビット列をデータYとするデータY生成サブステップと
を有し、
前記データY生成サブステップは、ブロックx[1],…,x[A]の組合せとブロックx’[1],…,x’[A’]の組合せとが一対一に対応するようにし、かつ
前記データY生成手段は、x[A’]のデータ長を、前記データ長調整ステップの処理によって生成されるデータZのデータ長が、A’×(m−n)となるようにする
ことを特徴とするハッシュ値生成方法。
【請求項7】
mビットのデータをnビットに圧縮する圧縮関数を用いて、データXに対するnビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データXをデータYに変換する前処理ステップと、
データ長調整部で、データYにパディングを行い、データ長がm−nビットの倍数のデータZを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータZを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データXを、A−1個のm−nビットのブロックx[1],…,x[A−1]と、1個のm−nビット以下のブロックx[A]に分割するデータX分割サブステップと、
μ≦|x[A]|≦m−n−σ―2ならば、
データXにビット“0”を付加した結果を、データYとし、
|x[A]|≦μ―1、かつ、A≧2ならば、
ブロックx[A−1]をm−n−μビットのブロックx’[A−1]とμビットのブロックx”に分割し、
x”‖x[A]をブロックx’[A]とし、
x[1]‖…‖x[A−2]‖x’[A−1]‖10μ-1‖x’[A]‖1をデータYとし、
|x[A]|≦μ―1、かつ、A=1ならば、
x[1]‖1をデータYとし、
|x[A]|≧m−n−σ―1ならば、
ブロックx[A]を|x[A]|−μビットのブロックx’[A]とμビットのブロックx”に分割し、
ブロックx”をブロックx[A+1]とし、
x[1]‖…‖x[A−1]‖x’[A]‖10m−n−|x’[A]|−1‖x’[A+1]‖1をデータYとするデータY生成サブステップと
を有す
(ただし、AはデータXをm−nビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“|x[A]|”はx[A]のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“0μ-1”は“0”がμ-1個並んだビット列、前記データ長調整部がデータYのデータ長にかかわらず付加するビット数をσ+1ビットとする)
ことを特徴とするハッシュ値生成方法。
【請求項8】
データXとハッシュ値τとを入力とし、データXの検証を行う検証方法であって、
データXに対するハッシュ値τ’を出力する請求項5から7のいずれかに記載のハッシュ生成方法の各ステップと、
比較部で、前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータXの検証結果を出力する比較ステップと
を有する検証方法。
【請求項9】
請求項1から3のいずれかに記載のハッシュ値生成装置、または4記載の検証装置として、コンピュータを動作させるプログラム。
【請求項10】
請求項9記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。




【図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