ハッシュ値生成装置は、入力された任意長のデータ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とは一対一に対応する。任意長のデータから、固定長(以下、nビットとする)の値を決定する関数H:{0,1}*→{0,1}nをハッシュ関数という。“{0,1}*”は、0または1が任意の長さ並んだビット列を、“{0,1}n”は、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などがある。3つの条件を満たすことが必要とされている。X≠X’となる(X,X’)の組を見つけることが難しいことである。ハッシュ関数Hの出力は2n通りあるので、nは衝突発見困難性の程度を示すパラメータであり、nを大きくすれば衝突発見困難性が高くなる。衝突発見困難性は、出力長nの半分の難しさであることが知られている。X≠X’となるようなX’を見つけることが難しいことである。向性とは、任意に与えられたVに対し、V=H(X’)となるようなX’を見つけることが難しいことである。「Vが任意に与えられる」とは、Xを任意に選び、V←H(X)と計算してVの任意の値を決定することを指す。“←”は、右辺の計算結果を左辺の変数の値とすること(ここでは、Vの値をH(X)とすること、もしくはH(X)を変数Vに代入すること)を示している。ついて、さらに表現を変えて説明する。圧縮関数hの第2原像発見困難性とは、具体的には次のような性質を意味する。攻撃者が決まった長さのデータWを選ぶ。次にデータの長さがm−|W|のデータXが任意に選ばれ、データXの値が攻撃者に知らされる。X‖W≠X’となるような長さmのデータX’を攻撃者がみつけることが困難だという性質が、圧縮関数hの第2原像発見困難性である。“‖”はビット列の結合を意味し、mは圧縮関数hに入力されるビット列の長さである。圧縮関数hの一方向性とは、具体的には次のような性質を意味する。攻撃者が決まった長さのデータWを選ぶ。次にデータの長さがm−|W|のデータXが任意に選ばれ、h(X‖W)の値が攻撃者に知らされる。X‖W≠X’となるような長さmのデータX’を攻撃者がみつけることが困難だという性質が、圧縮関数hの一方向性である。図1は従来のハッシュ値生成装置の機能構成例を示す図、図2は従来のハッシュ値生成装置の処理フローの例を示す図である。ハッシュ値生成装置900は、マークル・ダンガード構成のハッシュ関数を用いて、ハッシュ値を生成する。ハッシュ値生成装置900は、データ長調整部980とデータ圧縮部990とを備える。データ長調整部980は、データY分割手段981とデータZ生成手段982とを有し、入力された任意の長さのデータYにパディングを行い、データ長がm−nビットの倍数のデータZを出力する。データ圧縮部990は、データZ分割手段991と圧縮手段992とを有し、入力されたデータZを圧縮して、データ長がnビットのハッシュ値を求める。具体的には、例えば、データ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)。ここで、“→”は、左辺を右辺のように変換(分割)することを示している。【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)。“0m”は“0”がm個並んだビット列、<|Y|>はデータYのデータ長|Y|をσビットで表現したビット列である。このようにデータ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)である。圧縮手段992は、nビットの変数v[0]に、nビットの初期値v0を設定する(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)。【0010】マークル・ダンガード構成のハッシュ値生成装置(ハッシュ関数)では、圧縮手段(圧縮関数)が衝突発見困難性を有していれば、ハッシュ値生成装置も衝突発見困難性が保証されることが知られている。従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第2原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第2原像発見困難性と一方向性とを保証できなかった。【0011】これは、圧縮関数に入力されるブロックの中に、ハッシュ値生成装置への入力データを含まないブロックが存在する可能性があることが原因であった。本発明は、圧縮手段が第2原像発見困難性と一方向性とを有しているならば、第2原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供することを目的とする。本発明のハッシュ値生成装置は、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つ以上のブロックを変更してもよい。本発明のハッシュ値生成装置によれば、データXのデータ長がμビット以上のときに、データZを分割することで得られるC個のブロックz[1],...,z[C]のすべてが、データX内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータX内のビット列が含まれることになる。このことによって、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することが保証できる。データXとデータYとは一対一に対応しているので、衝突発見困難性は維持することができる。本発明のハッシュ値生成装置は、従来のマークル・ダンガード構成のハッシュ値生成装置に前処理部を付加するだけで、第2原像発見困難性と一方向性を保証できるようになる。広く普及しているマークル・ダンガード構成のハッシュ値生成装置をそのまま利用できるという利点がある。以下に、本発明の実施例を説明する。同じ機能を有する構成部やステップには同じ番号を付し、重複説明を省略する。分析まず、なぜ従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第2原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第2原像発見困難性と一方向性とを保証できなかったかを説明する。図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原像発見困難性と一方向性とを保証できなかったことの原因である。上記の分析から、本発明では、データ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であることに注意されたい。前処理部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の範囲で決めることが適当である。前処理部110が、このようにデータYを生成するので、データZを分割することで得られるC個のブロックz[1],...,z[C]のすべてが、データX内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータX内のビット列が含まれることになる。このことによって、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することが保証できる。データXとデータYとは一対一に対応しているので、衝突発見困難性は維持することができる。【0025】さらに、本発明は、入力データ(ハッシュ値を求める対象となるデータ)に対して前処理部110があらかじめ定めた条件を満足するように変換を行い、変換後のデータを従来のハッシュ値生成装置900に入力する。前処理部110を付加したことのみによって、広く普及している従来のハッシュ値生成装置900を利用しながら、圧縮関数が第2原像発見困難性と一方向性を有するならば、ハッシュ関数も第2原像発見困難性と一方向性を有することを保証できる。衝突発見困難性は維持する。従って、広く普及している技術を有効に利用できる。前処理部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’]に変換する方法であれば別の方法でも同じ効果を得ることができる。図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つ以上のブロックを変更してもよい。図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内のビット列が含まれることが分かる。図7に本発明の検証装置の機能構成例を示す。図8に本発明の検証装置の処理フロー例を示す。検証装置500は、実施例1で示したハッシュ値生成装置100と比較部510と記録部590を備える。検証装置500は、データXとハッシュ値τが入力、検証結果が出力である。検証装置500内のハッシュ値生成装置100は、データXからハッシュ値τ’を生成する(S100)。比較部510は、ハッシュ値τとハッシュ値τ’とを比較する。τ=τ’ならば、データ内容の整合性が検証されたとする。τ≠τ’ならば、データの改ざんがあると判断する。検証結果を出力する(S510)。記録部590を備えず、その他の構成部でこれらの情報を記録してもよい。このような構成なので、検証装置500でも、ハッシュ値生成装置100と同じ効果を得ることができる。図9に、コンピュータの機能構成例を示す。本発明のハッシュ値生成装置および検証装置は、コンピュータ2000の記録部2020に、本発明の各構成部としてコンピュータ2000を動作させるプログラムを読み込ませ、処理部2010、入力部2030、出力部2040などを動作させることで実現できる。コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。携帯電話、パソコン、ルータ、サーバなどに組み込み、送受信されるデータや蓄積されたデータに対するハッシュ値を生成することまたは検証することに利用できる。【図1】従来のハッシュ値生成装置の機能構成例を示す図。【図2】従来のハッシュ値生成装置の処理フローの例を示す図。【図3】実施例1のハッシュ値生成装置の機能構成例を示す図。【図4】実施例1のハッシュ値生成装置の処理フローを示す図。【図5】前処理部110の処理フローの具体例を示す図。【図6】前処理部110を付加した場合のデータ圧縮部990の処理を示す図。【図7】本発明の検証装置の機能構成例を示す図。【図8】本発明の検証装置の処理フロー例を示す図。【図9】コンピュータの機能構成例を示す図。請求項1から3のいずれかに記載のハッシュ値生成装置、または4記載の検証装置として、コンピュータを動作させるプログラム。請求項9記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。ekouhou.net。