ハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法、プログラム、および記録媒体
【課題】圧縮手段が第２原像発見困難性と一方向性とを有しているならば、第２原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供する。
【解決手段】本発明のハッシュ値生成装置は、入力された任意長のデータＸをデータＹに変換する前処理部と、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、圧縮関数を用いてデータＺを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。（条件１）データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含む。（条件２）データＸとデータＹとは一対一に対応する。
【解決手段】本発明のハッシュ値生成装置は、入力された任意長のデータＸをデータＹに変換する前処理部と、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、圧縮関数を用いてデータＺを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。（条件１）データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含む。（条件２）データＸとデータＹとは一対一に対応する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対してそのハッシュ値を生成するハッシュ値生成装置とハッシュ値生成方法、データとハッシュ値の組に対してその暗号学的安全性を検証する検証装置と検証方法、およびそれらのプログラムと記録媒体に関する。
【背景技術】
【０００２】
任意長のデータから、固定長（以下、ｎビットとする）の値を決定する関数
Ｈ：｛０，１｝＊→｛０，１｝ｎ
をハッシュ関数という。ただし、“｛０，１｝＊”は、０または１が任意の長さ並んだビット列を、“｛０，１｝ｎ”は、０または１がｎ個並んだビット列を示している。なお、ハッシュ関数では、マークル・ダンガード（Merkle-Damgard）構成と呼ばれる反復法を用いたものが主流である（非特許文献１、２）。マークル・ダンガード構成のハッシュ関数Ｈは、入力されたデータＸにパディングを施した上で、ｍビット（ただし、ｍはｎより大きい整数）のデータをｎビットのデータに圧縮する圧縮関数ｈを繰り返し利用し、任意長の入力データに対するｎビットのハッシュ値を得る。代表的な圧縮関数には、ｍ＝６７２、ｎ＝１６０の
ｓｈａ１：｛０，１｝１６０＋５１２→｛０，１｝１６０
や、ｍ＝７６８、ｎ＝２５６の
ｓｈａ２５６：｛０，１｝２５６＋５１２→｛０，１｝２５６
などがある。
【０００３】
ハッシュ関数Ｈが暗号学的に安全であるためには、衝突発見困難性、第２原像発見困難性、一方向性の３つの条件を満たすことが必要とされている。衝突発見困難性とは、
Ｈ（Ｘ）＝Ｈ（Ｘ’） かつ Ｘ≠Ｘ’
となる（Ｘ，Ｘ’）の組を見つけることが難しいことである。ハッシュ関数Ｈの出力は２ｎ通りあるので、ｎは衝突発見困難性の程度を示すパラメータであり、ｎを大きくすれば衝突発見困難性が高くなる。なお、衝突発見困難性は、出力長ｎの半分の難しさであることが知られている。第２原像発見困難性とは、任意に与えられたＸに対し、
Ｈ（Ｘ）＝Ｈ（Ｘ’） かつ Ｘ≠Ｘ’
となるようなＸ’を見つけることが難しいことである。一方向性とは、任意に与えられたＶに対し、Ｖ＝Ｈ（Ｘ’）となるようなＸ’を見つけることが難しいことである。ただし、「Ｖが任意に与えられる」とは、Ｘを任意に選び、
Ｖ←Ｈ（Ｘ）
と計算してＶの任意の値を決定することを指す。また、“←”は、右辺の計算結果を左辺の変数の値とすること（ここでは、Ｖの値をＨ（Ｘ）とすること、もしくはＨ（Ｘ）を変数Ｖに代入すること）を示している。また、マークル・ダンガード構成のハッシュ関数Ｈが暗号学的に安全であるためには、圧縮関数ｈも、衝突発見困難性、第２原像発見困難性、一方向性が必要である。
【０００４】
第２原像発見困難性、一方向性について、さらに表現を変えて説明する。例えば、圧縮関数ｈの第２原像発見困難性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータＷを選ぶ。次にデータの長さがｍ−｜Ｗ｜のデータＸが任意に選ばれ、データＸの値が攻撃者に知らされる。このとき、
ｈ（Ｘ‖Ｗ）＝ｈ（Ｘ’） かつ Ｘ‖Ｗ≠Ｘ’
となるような長さｍのデータＸ’を攻撃者がみつけることが困難だという性質が、圧縮関数ｈの第２原像発見困難性である。ただし、“‖”はビット列の結合を意味し、ｍは圧縮関数ｈに入力されるビット列の長さである。また、例えば、圧縮関数ｈの一方向性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータＷを選ぶ。次にデータの長さがｍ−｜Ｗ｜のデータＸが任意に選ばれ、ｈ（Ｘ‖Ｗ）の値が攻撃者に知らされる。このとき、
ｈ（Ｘ‖Ｗ）＝ｈ（Ｘ’） かつ Ｘ‖Ｗ≠Ｘ’
となるような長さｍのデータＸ’を攻撃者がみつけることが困難だという性質が、圧縮関数ｈの一方向性である。
【０００５】
図１は従来のハッシュ値生成装置の機能構成例を示す図、図２は従来のハッシュ値生成装置の処理フローの例を示す図である。ハッシュ値生成装置９００は、マークル・ダンガード構成のハッシュ関数を用いて、ハッシュ値を生成する。ハッシュ値生成装置９００は、データ長調整部９８０とデータ圧縮部９９０とを備える。データ長調整部９８０は、データＹ分割手段９８１とデータＺ生成手段９８２とを有し、入力された任意の長さのデータＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力する。データ圧縮部９９０は、データＺ分割手段９９１と圧縮手段９９２とを有し、入力されたデータＺを圧縮して、データ長がｎビットのハッシュ値を求める。
【０００６】
具体的には、例えば、データＹ分割手段９８１は、任意長のデータＹが入力されると、データＹを、
Ｙ→ｙ［１］‖ｙ［２］‖・・・‖ｙ［Ｂ］
のように、Ｂ−１個のｍ−ｎビットのブロックｙ［１］，…，ｙ［Ｂ−１］と、１個のｍ−ｎビット以下のブロックｙ［Ｂ］に分割する（Ｓ９８１）。ここで、“→”は、左辺を右辺のように変換（分割）することを示している。また、Ｂは分割されたブロックの数であり、
【数１】
である。
【０００７】
データＺ生成手段９８２は、｜ｙ［Ｂ］｜≦ｍ−ｎ−σ−１かを確認する（Ｓ９８３）。つまり、ブロックｙ［Ｂ］のデータ長がｍ−ｎ−σ−１以下かを確認する。ステップＳ９８３がＹｅｓの場合、データＺ生成手段９８２は、データＺを、
Ｚ←Ｙ‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞
のように生成する（Ｓ９８４）。ステップＳ９８３がＮｏの場合、データＺ生成手段９８２は、データＺを、
Ｚ←Ｙ‖１０ｍ−ｎ−１−｜ｙ［Ｂ］｜‖０ｍ−ｎ−σ‖＜｜Ｙ｜＞
のように生成する（Ｓ９８５）。ただし、“０ｍ”は“０”がｍ個並んだビット列、＜｜Ｙ｜＞はデータＹのデータ長｜Ｙ｜をσビットで表現したビット列である。例えば、σは６４である。このようにデータＺを生成するので、データＺは、データ長がｍ−ｎの倍数となる。
【０００８】
データＺ分割手段９９１は、データＺを、
Ｚ→ｚ［１］‖ｚ［２］‖・・・‖ｚ［Ｃ］
のように、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割する（Ｓ９９１）。また、Ｃは分割されたブロックの数であり、Ｃ＝｜Ｚ｜／（ｍ−ｎ）である。
【０００９】
圧縮手段９９２は、ｎビットの変数ｖ［０］に、ｎビットの初期値ｖ０を設定する（Ｓ９９３）。また、変数ｃに１を代入する（Ｓ９９４）。そして、圧縮手段９９２は、
ｖ［ｃ］←ｈ（ｚ（ｃ）‖ｖ［ｃ−１］）
のように圧縮関数ｈを用いた演算を行う（Ｓ９９５）。ｃがＣと一致するかを確認し（Ｓ９９６）、Ｎｏの場合にはｃの値を１増やし、ステップＳ９９５に戻る（Ｓ９９７）。ステップＳ９９６がＹｅｓの場合には、変数ｖ［Ｃ］の値をハッシュ値として出力する（Ｓ９９８）。
【非特許文献１】Ralph C. Merkle, “One Way Hash Functions and DES,” CRYPTO 1989, LNCS vol.435, pp.428-446, Springer, Heidelberg(1990).
【非特許文献２】Ivan Damgard, “A Design Principle for Hash Functions,” CRYPTO 1989, LNCS vol.435, pp.416-427, Springer, Heidelberg (1990).
【発明の開示】
【発明が解決しようとする課題】
【００１０】
マークル・ダンガード構成のハッシュ値生成装置（ハッシュ関数）では、圧縮手段（圧縮関数）が衝突発見困難性を有していれば、ハッシュ値生成装置も衝突発見困難性が保証されることが知られている。しかし、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかった。
【００１１】
これは、圧縮関数に入力されるブロックの中に、ハッシュ値生成装置への入力データを含まないブロックが存在する可能性があることが原因であった。本発明は、圧縮手段が第２原像発見困難性と一方向性とを有しているならば、第２原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のハッシュ値生成装置は、ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成する。本発明のハッシュ値生成装置は、入力された任意長のデータＸをデータＹに変換する前処理部と、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、圧縮関数を用いてデータＺを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。
【００１３】
（条件１）データＸのデータ長がμビット以上のときに、データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含む。
（条件２）データＸとデータＹとは一対一に対応する。
【００１４】
なお、本発明のハッシュ値生成装置の前処理部は、より具体的には、データＸ分割手段とデータＹ生成手段とを備えればよい。そして、データＸ分割手段は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）。データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとする。このとき、データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにする。また、データＹ生成手段は、ｘ［Ａ’］のデータ長を、データ長調整部の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるように調整する。例えば、データ長調整部がデータＹのデータ長にかかわらずデータＹに付加するビット数をσ＋１ビットとすると、データＹ生成手段は、ｘ［Ａ’］のデータ長をｍ−ｎ−σ−１以下となるようにすれば、データＺのデータ長が、Ａ’×（ｍ−ｎ）となる。ただし、この具体例に限定する必要はなく、データ長調整部とデータ圧縮部の処理を考慮して、Ａ’＝Ｂ＝Ｃとなるようにブロックｘ’［１］，…，ｘ’［Ａ’］に変換する方法であれば別の方法でもよい。
【００１５】
データＹ生成手段は以下のような処理を行えばよい。例えば、データＹ生成手段は、μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、データＸにビット“０”を付加した結果を、データＹとする。｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとする。｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、ｘ［１］‖１をデータＹとする。｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、ブロックｘ”をブロックｘ［Ａ＋１］とし、ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとする。ただし、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、σはデータ長調整部内部がデータＹのデータ長にかかわらず付加するビット数より１少ない数（データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビット）とする。なお、この例のデータＹ生成手段は、最後の２つのブロックを変更することで、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含むようにしている。しかし、最後の２つに限定する必要はなく、３つ以上のブロックを変更してもよい。
【発明の効果】
【００１６】
本発明のハッシュ値生成装置によれば、データＸのデータ長がμビット以上のときに、データＺを分割することで得られるＣ個のブロックｚ［１］，…，ｚ［Ｃ］のすべてが、データＸ内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることになる。このことによって、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することが保証できる。また、データＸとデータＹとは一対一に対応しているので、衝突発見困難性は維持することができる。また、本発明のハッシュ値生成装置は、従来のマークル・ダンガード構成のハッシュ値生成装置に前処理部を付加するだけで、第２原像発見困難性と一方向性を保証できるようになる。つまり、すでに広く普及しているマークル・ダンガード構成のハッシュ値生成装置をそのまま利用できるという利点がある。
【発明を実施するための最良の形態】
【００１７】
以下に、本発明の実施例を説明する。なお、同じ機能を有する構成部やステップには同じ番号を付し、重複説明を省略する。
【００１８】
分析
まず、なぜ従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかったかを説明する。
【００１９】
図２に示したように、従来のマークル・ダンガード構成のハッシュ値生成装置９００では、データ長調整部９８０は、データＺのデータ長がｍ−ｎビットの倍数となるようにビット列をデータＹに付加する。ただし、データ長調整部９８０は、データＹのデータ長にかかわらず少なくともσ＋１ビットを付加する。したがって、データＺのデータ長は、データＹのデータ長よりもσ＋１ビット以上長くなる。この結果、ブロックｙ［Ｂ］のデータ長がｍ−ｎ−σ−１よりも長いときには、データＺを分割したときのブロックの数の方が、データＹを分割したときのブロックの数よりも多くなる（つまり、Ｃ＝Ｂ＋１となる。）。そして、最後のブロックｚ［Ｃ］には、データＹの中のビット列がまったく含まれていない。また、ブロックｙ［Ｂ］のデータ長が短いときには、最後のブロックｚ［Ｃ］には、データＹの中のビット列が少ししか含まれていない。
【００２０】
したがって、データ圧縮部９９０の圧縮手段９９２での圧縮関数ｈを用いた繰り返し演算の中で、最後の演算では、入力されるデータ（ブロックｚ［Ｃ］）にデータＹの中のビット列が十分含まれていない可能性がある。このことが、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかったことの原因である。
【実施例１】
【００２１】
上記の分析から、本発明では、データＸのデータ長がμビット以上のときに、圧縮関数に入力されるすべてのブロックが、ハッシュ値生成装置への入力データをμビット以上含むようにする。図３は、実施例１のハッシュ値生成装置の機能構成例を示す図である。図４は、実施例１のハッシュ値生成装置の処理フローを示す図である。
【００２２】
ハッシュ値生成装置１００は、ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成する。ハッシュ値生成装置１００は、前処理部１１０、データ長調整部９８０、データ圧縮部９９０を備える。前処理部１１０は、あらかじめ定めた条件を満足するように入力された任意長のデータＸをデータＹに変換する（Ｓ１１０）。データ長調整部９８０は、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力する（Ｓ９８０）。データ圧縮部９９０は、圧縮関数を用いてデータＺを圧縮してハッシュ値を求める（Ｓ９９０）。データ長調整部９８０とデータ圧縮部９９０は、従来のハッシュ値生成装置９００と同じである。なお、従来のハッシュ値生成装置９００の説明では、入力データ（ハッシュ値を求める対象となるデータ）をデータＹとしたが、ハッシュ値生成装置１００の説明では、入力データ（ハッシュ値を求める対象となるデータ）はデータＸであることに注意されたい。
【００２３】
前処理部１１０は、データＸ分割手段１２０とデータＹ生成手段１３０とを備え、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。
（条件１）データＸのデータ長がμビット以上のときに、データ長調整部９８０が生成するデータＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含む。
（条件２）データＸとデータＹとは一対一に対応する。
ただし、μはあらかじめ定めた整数であって、セキュリティーレベルを決めるパラメータである。μ＝ｎにすれば、第２原像発見困難性と一方向性の程度が、出力長ｎの難しさとなる。また、μ＝ｎ／２にすれば、第２原像発見困難性と一方向性の程度が、出力長ｎの半分の難しさ（衝突発見困難性と同じ程度）となる。したがって、μの値は、ｎ／２〜ｎの範囲で決めることが適当である。
【００２４】
前処理部１１０が、このようにデータＹを生成するので、データＺを分割することで得られるＣ個のブロックｚ［１］，…，ｚ［Ｃ］のすべてが、データＸ内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることになる。このことによって、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することが保証できる。また、データＸとデータＹとは一対一に対応しているので、衝突発見困難性は維持することができる。
【００２５】
さらに、本発明は、入力データ（ハッシュ値を求める対象となるデータ）に対して前処理部１１０があらかじめ定めた条件を満足するように変換を行い、変換後のデータを従来のハッシュ値生成装置９００に入力する。そして、前処理部１１０を付加したことのみによって、広く普及している従来のハッシュ値生成装置９００を利用しながら、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することを保証できる。また、衝突発見困難性は維持する。従って、広く普及している技術を有効に利用できる。
【００２６】
前処理部１１０は、より具体的には、以下のように処理を行えばよい。データＸ分割手段１２０は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）。データＹ生成手段１３０は、ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとする。このとき、データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにする。また、データＹ生成手段は、ｘ［Ａ’］のデータ長を、データ長調整部９８０の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるように調整する。例えば、データ長調整部９８０がデータＹのデータ長にかかわらずデータＹに付加するビット数をσ＋１ビットとすると、データＹ生成手段１３０が、ｘ［Ａ’］のデータ長をｍ−ｎ−σ−１以下となるようにしておけば、データＺのデータ長が、Ａ’×（ｍ−ｎ）となる。ただし、このような処理を行うためには、ｍはｎ＋σ＋μ＋２以上でなければならない。μ＝ｎ、σ＝６４とすると、広く普及している圧縮関数ｓｈａ１もｓｈａ２５６もこの条件を満たす。なお、上述の具体例に限定する必要はなく、データ長調整部９８０とデータ圧縮部９９０の処理を考慮して、Ａ’＝Ｂ＝Ｃとなるようにブロックｘ’［１］，…，ｘ’［Ａ’］に変換する方法であれば別の方法でも同じ効果を得ることができる。
【００２７】
図５に、前処理部１１０の処理フローの具体例を示す。この処理フローは、図２に示したデータ長調整部９８０とデータ圧縮部９９０と組み合わせることを前提としたものである。データＸ分割手段１２０は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）（Ｓ１２０）。
【００２８】
データＹ生成手段１３０は、μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２かを確認する（Ｓ１３１）。データＹ生成手段１３０は、ステップＳ１３１がＹｅｓならば、データＸにビット“０”を付加した結果を、データＹとする（Ｓ１３２）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じであり、ｘ’［Ａ−１］はｘ［Ａ−１］‖０である。
【００２９】
データＹ生成手段１３０は、ステップＳ１３１がＮｏならば、データＹ生成手段１３０は、｜ｘ［Ａ］｜≦μ―１かを確認する（Ｓ１３３）。データＹ生成手段１３０は、ステップＳ１３３がＹｅｓならば、Ａ≧２かを確認する（Ｓ１３４）。データＹ生成手段１３０は、ステップＳ１３４がＹｅｓならば、ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割する（Ｓ１３５）。ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とする（Ｓ１３６）。そして、ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとする（Ｓ１３７）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−２］はｘ［１］，…，ｘ［Ａ−２］と同じである。データＹ生成手段１３０は、ステップＳ１３４がＮｏならば、ｘ［１］‖１をデータＹとする（Ｓ１３８）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じであり、ｘ’［Ａ−１］はｘ［Ａ−１］‖１である。
【００３０】
データＹ生成手段１３０は、ステップＳ１３３がＮｏ（つまり、｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１）ならば、ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割する（Ｓ１３９）。ブロックｘ”をブロックｘ［Ａ＋１］とする（Ｓ１４０）。ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとする（Ｓ１４１）。この場合、Ａ’＝Ａ＋１であり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じである。ただし、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、σはデータＹのデータ長｜Ｙ｜を表現したビット数であり、データ長調整部９８０がデータＹのデータ長にかかわらず付加するビット数より１少ない数である。なお、この例のデータＹ生成手段１３０は、最後の２つのブロックを変更することで、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含むようにしている。しかし、最後の２つに限定する必要はなく、３つ以上のブロックを変更してもよい。
【００３１】
図６は、前処理部１１０を付加した場合のデータ圧縮部９９０（圧縮手段９９２）の処理を示す図である。上述のように、前処理部１１０の処理は、ブロックｘ［Ａ］のデータ長によって異なる。したがって、データ圧縮部９９０の処理も、ブロックｘ［Ａ］のデータ長によって異なる。μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ［Ａ−１］，ｘ［Ａ］‖０‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。｜ｘ［Ａ］｜≦μ―１かつＡ≧２の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ’［Ａ−１］‖１０μ−１，ｘ’［Ａ］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。｜ｘ［Ａ］｜≦μ―１かつＡ＝１の場合、圧縮関数ｈへの入力は、ｘ［１］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞のみとなる。この場合は、データＸがμビット以上含まれていない。しかし、入力されたデータＸ自体がμビットより短いので、本発明の解決すべき課題の対象外である。｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ［Ａ−１］，ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１，ｘ’［Ａ＋１］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。したがって、入力されたデータＸのデータ長がμビット以上であれば、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることが分かる。
【実施例２】
【００３２】
図７に本発明の検証装置の機能構成例を示す。また、図８に本発明の検証装置の処理フロー例を示す。検証装置５００は、実施例１で示したハッシュ値生成装置１００と比較部５１０と記録部５９０を備える。検証装置５００は、データＸとハッシュ値τが入力、検証結果が出力である。
【００３３】
検証装置５００内のハッシュ値生成装置１００は、データＸからハッシュ値τ’を生成する（Ｓ１００）。比較部５１０は、ハッシュ値τとハッシュ値τ’とを比較する。そして、τ＝τ’ならば、データ内容の整合性が検証されたとする。τ≠τ’ならば、データの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。
このような構成なので、検証装置５００でも、ハッシュ値生成装置１００と同じ効果を得ることができる。
【００３４】
図９に、コンピュータの機能構成例を示す。なお、本発明のハッシュ値生成装置および検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００３５】
本発明のハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法は、例えば携帯電話、パソコン、ルータ、サーバなどに組み込み、送受信されるデータや蓄積されたデータに対するハッシュ値を生成することまたは検証することに利用できる。
【図面の簡単な説明】
【００３６】
【図１】従来のハッシュ値生成装置の機能構成例を示す図。
【図２】従来のハッシュ値生成装置の処理フローの例を示す図。
【図３】実施例１のハッシュ値生成装置の機能構成例を示す図。
【図４】実施例１のハッシュ値生成装置の処理フローを示す図。
【図５】前処理部１１０の処理フローの具体例を示す図。
【図６】前処理部１１０を付加した場合のデータ圧縮部９９０の処理を示す図。
【図７】本発明の検証装置の機能構成例を示す図。
【図８】本発明の検証装置の処理フロー例を示す図。
【図９】コンピュータの機能構成例を示す図。
【符号の説明】
【００３７】
１００、９００ ハッシュ値生成装置 １１０ 前処理部
１２０ データＸ分割手段 １３０ データＹ生成手段
５００ 検証装置 ５１０ 比較部
５９０ 記録部 ９８０ データ長調整部
９８１ データＹ分割手段 ９８２ データＺ生成手段
９９０ データ圧縮部 ９９１ データＺ分割手段
９９２ 圧縮手段
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対してそのハッシュ値を生成するハッシュ値生成装置とハッシュ値生成方法、データとハッシュ値の組に対してその暗号学的安全性を検証する検証装置と検証方法、およびそれらのプログラムと記録媒体に関する。
【背景技術】
【０００２】
任意長のデータから、固定長（以下、ｎビットとする）の値を決定する関数
Ｈ：｛０，１｝＊→｛０，１｝ｎ
をハッシュ関数という。ただし、“｛０，１｝＊”は、０または１が任意の長さ並んだビット列を、“｛０，１｝ｎ”は、０または１がｎ個並んだビット列を示している。なお、ハッシュ関数では、マークル・ダンガード（Merkle-Damgard）構成と呼ばれる反復法を用いたものが主流である（非特許文献１、２）。マークル・ダンガード構成のハッシュ関数Ｈは、入力されたデータＸにパディングを施した上で、ｍビット（ただし、ｍはｎより大きい整数）のデータをｎビットのデータに圧縮する圧縮関数ｈを繰り返し利用し、任意長の入力データに対するｎビットのハッシュ値を得る。代表的な圧縮関数には、ｍ＝６７２、ｎ＝１６０の
ｓｈａ１：｛０，１｝１６０＋５１２→｛０，１｝１６０
や、ｍ＝７６８、ｎ＝２５６の
ｓｈａ２５６：｛０，１｝２５６＋５１２→｛０，１｝２５６
などがある。
【０００３】
ハッシュ関数Ｈが暗号学的に安全であるためには、衝突発見困難性、第２原像発見困難性、一方向性の３つの条件を満たすことが必要とされている。衝突発見困難性とは、
Ｈ（Ｘ）＝Ｈ（Ｘ’） かつ Ｘ≠Ｘ’
となる（Ｘ，Ｘ’）の組を見つけることが難しいことである。ハッシュ関数Ｈの出力は２ｎ通りあるので、ｎは衝突発見困難性の程度を示すパラメータであり、ｎを大きくすれば衝突発見困難性が高くなる。なお、衝突発見困難性は、出力長ｎの半分の難しさであることが知られている。第２原像発見困難性とは、任意に与えられたＸに対し、
Ｈ（Ｘ）＝Ｈ（Ｘ’） かつ Ｘ≠Ｘ’
となるようなＸ’を見つけることが難しいことである。一方向性とは、任意に与えられたＶに対し、Ｖ＝Ｈ（Ｘ’）となるようなＸ’を見つけることが難しいことである。ただし、「Ｖが任意に与えられる」とは、Ｘを任意に選び、
Ｖ←Ｈ（Ｘ）
と計算してＶの任意の値を決定することを指す。また、“←”は、右辺の計算結果を左辺の変数の値とすること（ここでは、Ｖの値をＨ（Ｘ）とすること、もしくはＨ（Ｘ）を変数Ｖに代入すること）を示している。また、マークル・ダンガード構成のハッシュ関数Ｈが暗号学的に安全であるためには、圧縮関数ｈも、衝突発見困難性、第２原像発見困難性、一方向性が必要である。
【０００４】
第２原像発見困難性、一方向性について、さらに表現を変えて説明する。例えば、圧縮関数ｈの第２原像発見困難性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータＷを選ぶ。次にデータの長さがｍ−｜Ｗ｜のデータＸが任意に選ばれ、データＸの値が攻撃者に知らされる。このとき、
ｈ（Ｘ‖Ｗ）＝ｈ（Ｘ’） かつ Ｘ‖Ｗ≠Ｘ’
となるような長さｍのデータＸ’を攻撃者がみつけることが困難だという性質が、圧縮関数ｈの第２原像発見困難性である。ただし、“‖”はビット列の結合を意味し、ｍは圧縮関数ｈに入力されるビット列の長さである。また、例えば、圧縮関数ｈの一方向性とは、具体的には次のような性質を意味する。まず、攻撃者が決まった長さのデータＷを選ぶ。次にデータの長さがｍ−｜Ｗ｜のデータＸが任意に選ばれ、ｈ（Ｘ‖Ｗ）の値が攻撃者に知らされる。このとき、
ｈ（Ｘ‖Ｗ）＝ｈ（Ｘ’） かつ Ｘ‖Ｗ≠Ｘ’
となるような長さｍのデータＸ’を攻撃者がみつけることが困難だという性質が、圧縮関数ｈの一方向性である。
【０００５】
図１は従来のハッシュ値生成装置の機能構成例を示す図、図２は従来のハッシュ値生成装置の処理フローの例を示す図である。ハッシュ値生成装置９００は、マークル・ダンガード構成のハッシュ関数を用いて、ハッシュ値を生成する。ハッシュ値生成装置９００は、データ長調整部９８０とデータ圧縮部９９０とを備える。データ長調整部９８０は、データＹ分割手段９８１とデータＺ生成手段９８２とを有し、入力された任意の長さのデータＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力する。データ圧縮部９９０は、データＺ分割手段９９１と圧縮手段９９２とを有し、入力されたデータＺを圧縮して、データ長がｎビットのハッシュ値を求める。
【０００６】
具体的には、例えば、データＹ分割手段９８１は、任意長のデータＹが入力されると、データＹを、
Ｙ→ｙ［１］‖ｙ［２］‖・・・‖ｙ［Ｂ］
のように、Ｂ−１個のｍ−ｎビットのブロックｙ［１］，…，ｙ［Ｂ−１］と、１個のｍ−ｎビット以下のブロックｙ［Ｂ］に分割する（Ｓ９８１）。ここで、“→”は、左辺を右辺のように変換（分割）することを示している。また、Ｂは分割されたブロックの数であり、
【数１】
である。
【０００７】
データＺ生成手段９８２は、｜ｙ［Ｂ］｜≦ｍ−ｎ−σ−１かを確認する（Ｓ９８３）。つまり、ブロックｙ［Ｂ］のデータ長がｍ−ｎ−σ−１以下かを確認する。ステップＳ９８３がＹｅｓの場合、データＺ生成手段９８２は、データＺを、
Ｚ←Ｙ‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞
のように生成する（Ｓ９８４）。ステップＳ９８３がＮｏの場合、データＺ生成手段９８２は、データＺを、
Ｚ←Ｙ‖１０ｍ−ｎ−１−｜ｙ［Ｂ］｜‖０ｍ−ｎ−σ‖＜｜Ｙ｜＞
のように生成する（Ｓ９８５）。ただし、“０ｍ”は“０”がｍ個並んだビット列、＜｜Ｙ｜＞はデータＹのデータ長｜Ｙ｜をσビットで表現したビット列である。例えば、σは６４である。このようにデータＺを生成するので、データＺは、データ長がｍ−ｎの倍数となる。
【０００８】
データＺ分割手段９９１は、データＺを、
Ｚ→ｚ［１］‖ｚ［２］‖・・・‖ｚ［Ｃ］
のように、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割する（Ｓ９９１）。また、Ｃは分割されたブロックの数であり、Ｃ＝｜Ｚ｜／（ｍ−ｎ）である。
【０００９】
圧縮手段９９２は、ｎビットの変数ｖ［０］に、ｎビットの初期値ｖ０を設定する（Ｓ９９３）。また、変数ｃに１を代入する（Ｓ９９４）。そして、圧縮手段９９２は、
ｖ［ｃ］←ｈ（ｚ（ｃ）‖ｖ［ｃ−１］）
のように圧縮関数ｈを用いた演算を行う（Ｓ９９５）。ｃがＣと一致するかを確認し（Ｓ９９６）、Ｎｏの場合にはｃの値を１増やし、ステップＳ９９５に戻る（Ｓ９９７）。ステップＳ９９６がＹｅｓの場合には、変数ｖ［Ｃ］の値をハッシュ値として出力する（Ｓ９９８）。
【非特許文献１】Ralph C. Merkle, “One Way Hash Functions and DES,” CRYPTO 1989, LNCS vol.435, pp.428-446, Springer, Heidelberg(1990).
【非特許文献２】Ivan Damgard, “A Design Principle for Hash Functions,” CRYPTO 1989, LNCS vol.435, pp.416-427, Springer, Heidelberg (1990).
【発明の開示】
【発明が解決しようとする課題】
【００１０】
マークル・ダンガード構成のハッシュ値生成装置（ハッシュ関数）では、圧縮手段（圧縮関数）が衝突発見困難性を有していれば、ハッシュ値生成装置も衝突発見困難性が保証されることが知られている。しかし、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかった。
【００１１】
これは、圧縮関数に入力されるブロックの中に、ハッシュ値生成装置への入力データを含まないブロックが存在する可能性があることが原因であった。本発明は、圧縮手段が第２原像発見困難性と一方向性とを有しているならば、第２原像発見困難性と一方向性とが保証できるハッシュ値生成装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のハッシュ値生成装置は、ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成する。本発明のハッシュ値生成装置は、入力された任意長のデータＸをデータＹに変換する前処理部と、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、圧縮関数を用いてデータＺを圧縮してハッシュ値を求めるデータ圧縮部とを備える。前処理部は、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。
【００１３】
（条件１）データＸのデータ長がμビット以上のときに、データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含む。
（条件２）データＸとデータＹとは一対一に対応する。
【００１４】
なお、本発明のハッシュ値生成装置の前処理部は、より具体的には、データＸ分割手段とデータＹ生成手段とを備えればよい。そして、データＸ分割手段は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）。データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとする。このとき、データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにする。また、データＹ生成手段は、ｘ［Ａ’］のデータ長を、データ長調整部の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるように調整する。例えば、データ長調整部がデータＹのデータ長にかかわらずデータＹに付加するビット数をσ＋１ビットとすると、データＹ生成手段は、ｘ［Ａ’］のデータ長をｍ−ｎ−σ−１以下となるようにすれば、データＺのデータ長が、Ａ’×（ｍ−ｎ）となる。ただし、この具体例に限定する必要はなく、データ長調整部とデータ圧縮部の処理を考慮して、Ａ’＝Ｂ＝Ｃとなるようにブロックｘ’［１］，…，ｘ’［Ａ’］に変換する方法であれば別の方法でもよい。
【００１５】
データＹ生成手段は以下のような処理を行えばよい。例えば、データＹ生成手段は、μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、データＸにビット“０”を付加した結果を、データＹとする。｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとする。｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、ｘ［１］‖１をデータＹとする。｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、ブロックｘ”をブロックｘ［Ａ＋１］とし、ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとする。ただし、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、σはデータ長調整部内部がデータＹのデータ長にかかわらず付加するビット数より１少ない数（データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビット）とする。なお、この例のデータＹ生成手段は、最後の２つのブロックを変更することで、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含むようにしている。しかし、最後の２つに限定する必要はなく、３つ以上のブロックを変更してもよい。
【発明の効果】
【００１６】
本発明のハッシュ値生成装置によれば、データＸのデータ長がμビット以上のときに、データＺを分割することで得られるＣ個のブロックｚ［１］，…，ｚ［Ｃ］のすべてが、データＸ内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることになる。このことによって、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することが保証できる。また、データＸとデータＹとは一対一に対応しているので、衝突発見困難性は維持することができる。また、本発明のハッシュ値生成装置は、従来のマークル・ダンガード構成のハッシュ値生成装置に前処理部を付加するだけで、第２原像発見困難性と一方向性を保証できるようになる。つまり、すでに広く普及しているマークル・ダンガード構成のハッシュ値生成装置をそのまま利用できるという利点がある。
【発明を実施するための最良の形態】
【００１７】
以下に、本発明の実施例を説明する。なお、同じ機能を有する構成部やステップには同じ番号を付し、重複説明を省略する。
【００１８】
分析
まず、なぜ従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかったかを説明する。
【００１９】
図２に示したように、従来のマークル・ダンガード構成のハッシュ値生成装置９００では、データ長調整部９８０は、データＺのデータ長がｍ−ｎビットの倍数となるようにビット列をデータＹに付加する。ただし、データ長調整部９８０は、データＹのデータ長にかかわらず少なくともσ＋１ビットを付加する。したがって、データＺのデータ長は、データＹのデータ長よりもσ＋１ビット以上長くなる。この結果、ブロックｙ［Ｂ］のデータ長がｍ−ｎ−σ−１よりも長いときには、データＺを分割したときのブロックの数の方が、データＹを分割したときのブロックの数よりも多くなる（つまり、Ｃ＝Ｂ＋１となる。）。そして、最後のブロックｚ［Ｃ］には、データＹの中のビット列がまったく含まれていない。また、ブロックｙ［Ｂ］のデータ長が短いときには、最後のブロックｚ［Ｃ］には、データＹの中のビット列が少ししか含まれていない。
【００２０】
したがって、データ圧縮部９９０の圧縮手段９９２での圧縮関数ｈを用いた繰り返し演算の中で、最後の演算では、入力されるデータ（ブロックｚ［Ｃ］）にデータＹの中のビット列が十分含まれていない可能性がある。このことが、従来のマークル・ダンガード構成のハッシュ値生成装置では、圧縮手段が第２原像発見困難性と一方向性とを有していたとしても、ハッシュ値生成装置の第２原像発見困難性と一方向性とを保証できなかったことの原因である。
【実施例１】
【００２１】
上記の分析から、本発明では、データＸのデータ長がμビット以上のときに、圧縮関数に入力されるすべてのブロックが、ハッシュ値生成装置への入力データをμビット以上含むようにする。図３は、実施例１のハッシュ値生成装置の機能構成例を示す図である。図４は、実施例１のハッシュ値生成装置の処理フローを示す図である。
【００２２】
ハッシュ値生成装置１００は、ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成する。ハッシュ値生成装置１００は、前処理部１１０、データ長調整部９８０、データ圧縮部９９０を備える。前処理部１１０は、あらかじめ定めた条件を満足するように入力された任意長のデータＸをデータＹに変換する（Ｓ１１０）。データ長調整部９８０は、データＹにパディングを行いデータ長がｍ−ｎビットの倍数のデータＺを出力する（Ｓ９８０）。データ圧縮部９９０は、圧縮関数を用いてデータＺを圧縮してハッシュ値を求める（Ｓ９９０）。データ長調整部９８０とデータ圧縮部９９０は、従来のハッシュ値生成装置９００と同じである。なお、従来のハッシュ値生成装置９００の説明では、入力データ（ハッシュ値を求める対象となるデータ）をデータＹとしたが、ハッシュ値生成装置１００の説明では、入力データ（ハッシュ値を求める対象となるデータ）はデータＸであることに注意されたい。
【００２３】
前処理部１１０は、データＸ分割手段１２０とデータＹ生成手段１３０とを備え、データＹが次の２つの条件を満足するように、データＸをデータＹに変換する。
（条件１）データＸのデータ長がμビット以上のときに、データ長調整部９８０が生成するデータＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含む。
（条件２）データＸとデータＹとは一対一に対応する。
ただし、μはあらかじめ定めた整数であって、セキュリティーレベルを決めるパラメータである。μ＝ｎにすれば、第２原像発見困難性と一方向性の程度が、出力長ｎの難しさとなる。また、μ＝ｎ／２にすれば、第２原像発見困難性と一方向性の程度が、出力長ｎの半分の難しさ（衝突発見困難性と同じ程度）となる。したがって、μの値は、ｎ／２〜ｎの範囲で決めることが適当である。
【００２４】
前処理部１１０が、このようにデータＹを生成するので、データＺを分割することで得られるＣ個のブロックｚ［１］，…，ｚ［Ｃ］のすべてが、データＸ内のμビット以上を含んでいる。したがって、圧縮関数を用いるときに、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることになる。このことによって、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することが保証できる。また、データＸとデータＹとは一対一に対応しているので、衝突発見困難性は維持することができる。
【００２５】
さらに、本発明は、入力データ（ハッシュ値を求める対象となるデータ）に対して前処理部１１０があらかじめ定めた条件を満足するように変換を行い、変換後のデータを従来のハッシュ値生成装置９００に入力する。そして、前処理部１１０を付加したことのみによって、広く普及している従来のハッシュ値生成装置９００を利用しながら、圧縮関数が第２原像発見困難性と一方向性を有するならば、ハッシュ関数も第２原像発見困難性と一方向性を有することを保証できる。また、衝突発見困難性は維持する。従って、広く普及している技術を有効に利用できる。
【００２６】
前処理部１１０は、より具体的には、以下のように処理を行えばよい。データＸ分割手段１２０は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）。データＹ生成手段１３０は、ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとする。このとき、データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにする。また、データＹ生成手段は、ｘ［Ａ’］のデータ長を、データ長調整部９８０の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるように調整する。例えば、データ長調整部９８０がデータＹのデータ長にかかわらずデータＹに付加するビット数をσ＋１ビットとすると、データＹ生成手段１３０が、ｘ［Ａ’］のデータ長をｍ−ｎ−σ−１以下となるようにしておけば、データＺのデータ長が、Ａ’×（ｍ−ｎ）となる。ただし、このような処理を行うためには、ｍはｎ＋σ＋μ＋２以上でなければならない。μ＝ｎ、σ＝６４とすると、広く普及している圧縮関数ｓｈａ１もｓｈａ２５６もこの条件を満たす。なお、上述の具体例に限定する必要はなく、データ長調整部９８０とデータ圧縮部９９０の処理を考慮して、Ａ’＝Ｂ＝Ｃとなるようにブロックｘ’［１］，…，ｘ’［Ａ’］に変換する方法であれば別の方法でも同じ効果を得ることができる。
【００２７】
図５に、前処理部１１０の処理フローの具体例を示す。この処理フローは、図２に示したデータ長調整部９８０とデータ圧縮部９９０と組み合わせることを前提としたものである。データＸ分割手段１２０は、データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）（Ｓ１２０）。
【００２８】
データＹ生成手段１３０は、μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２かを確認する（Ｓ１３１）。データＹ生成手段１３０は、ステップＳ１３１がＹｅｓならば、データＸにビット“０”を付加した結果を、データＹとする（Ｓ１３２）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じであり、ｘ’［Ａ−１］はｘ［Ａ−１］‖０である。
【００２９】
データＹ生成手段１３０は、ステップＳ１３１がＮｏならば、データＹ生成手段１３０は、｜ｘ［Ａ］｜≦μ―１かを確認する（Ｓ１３３）。データＹ生成手段１３０は、ステップＳ１３３がＹｅｓならば、Ａ≧２かを確認する（Ｓ１３４）。データＹ生成手段１３０は、ステップＳ１３４がＹｅｓならば、ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割する（Ｓ１３５）。ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とする（Ｓ１３６）。そして、ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとする（Ｓ１３７）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−２］はｘ［１］，…，ｘ［Ａ−２］と同じである。データＹ生成手段１３０は、ステップＳ１３４がＮｏならば、ｘ［１］‖１をデータＹとする（Ｓ１３８）。この場合、Ａ’＝Ａであり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じであり、ｘ’［Ａ−１］はｘ［Ａ−１］‖１である。
【００３０】
データＹ生成手段１３０は、ステップＳ１３３がＮｏ（つまり、｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１）ならば、ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割する（Ｓ１３９）。ブロックｘ”をブロックｘ［Ａ＋１］とする（Ｓ１４０）。ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとする（Ｓ１４１）。この場合、Ａ’＝Ａ＋１であり、ｘ’［１］，…，ｘ’［Ａ−１］はｘ［１］，…，ｘ［Ａ−１］と同じである。ただし、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、σはデータＹのデータ長｜Ｙ｜を表現したビット数であり、データ長調整部９８０がデータＹのデータ長にかかわらず付加するビット数より１少ない数である。なお、この例のデータＹ生成手段１３０は、最後の２つのブロックを変更することで、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット以上を含むようにしている。しかし、最後の２つに限定する必要はなく、３つ以上のブロックを変更してもよい。
【００３１】
図６は、前処理部１１０を付加した場合のデータ圧縮部９９０（圧縮手段９９２）の処理を示す図である。上述のように、前処理部１１０の処理は、ブロックｘ［Ａ］のデータ長によって異なる。したがって、データ圧縮部９９０の処理も、ブロックｘ［Ａ］のデータ長によって異なる。μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ［Ａ−１］，ｘ［Ａ］‖０‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。｜ｘ［Ａ］｜≦μ―１かつＡ≧２の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ’［Ａ−１］‖１０μ−１，ｘ’［Ａ］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。｜ｘ［Ａ］｜≦μ―１かつＡ＝１の場合、圧縮関数ｈへの入力は、ｘ［１］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞のみとなる。この場合は、データＸがμビット以上含まれていない。しかし、入力されたデータＸ自体がμビットより短いので、本発明の解決すべき課題の対象外である。｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１の場合、圧縮関数ｈへの入力は、ｘ［１］，…，ｘ［Ａ−１］，ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１，ｘ’［Ａ＋１］‖１‖１０ｍ−ｎ−σ−１−｜ｙ［Ｂ］｜‖＜｜Ｙ｜＞となる。よって、すべての入力にデータＸがμビット以上含まれている。したがって、入力されたデータＸのデータ長がμビット以上であれば、常に圧縮関数への入力の中にμビット以上のデータＸ内のビット列が含まれることが分かる。
【実施例２】
【００３２】
図７に本発明の検証装置の機能構成例を示す。また、図８に本発明の検証装置の処理フロー例を示す。検証装置５００は、実施例１で示したハッシュ値生成装置１００と比較部５１０と記録部５９０を備える。検証装置５００は、データＸとハッシュ値τが入力、検証結果が出力である。
【００３３】
検証装置５００内のハッシュ値生成装置１００は、データＸからハッシュ値τ’を生成する（Ｓ１００）。比較部５１０は、ハッシュ値τとハッシュ値τ’とを比較する。そして、τ＝τ’ならば、データ内容の整合性が検証されたとする。τ≠τ’ならば、データの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。
このような構成なので、検証装置５００でも、ハッシュ値生成装置１００と同じ効果を得ることができる。
【００３４】
図９に、コンピュータの機能構成例を示す。なお、本発明のハッシュ値生成装置および検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００３５】
本発明のハッシュ値生成装置、検証装置、ハッシュ値生成方法、検証方法は、例えば携帯電話、パソコン、ルータ、サーバなどに組み込み、送受信されるデータや蓄積されたデータに対するハッシュ値を生成することまたは検証することに利用できる。
【図面の簡単な説明】
【００３６】
【図１】従来のハッシュ値生成装置の機能構成例を示す図。
【図２】従来のハッシュ値生成装置の処理フローの例を示す図。
【図３】実施例１のハッシュ値生成装置の機能構成例を示す図。
【図４】実施例１のハッシュ値生成装置の処理フローを示す図。
【図５】前処理部１１０の処理フローの具体例を示す図。
【図６】前処理部１１０を付加した場合のデータ圧縮部９９０の処理を示す図。
【図７】本発明の検証装置の機能構成例を示す図。
【図８】本発明の検証装置の処理フロー例を示す図。
【図９】コンピュータの機能構成例を示す図。
【符号の説明】
【００３７】
１００、９００ ハッシュ値生成装置 １１０ 前処理部
１２０ データＸ分割手段 １３０ データＹ生成手段
５００ 検証装置 ５１０ 比較部
５９０ 記録部 ９８０ データ長調整部
９８１ データＹ分割手段 ９８２ データＺ生成手段
９９０ データ圧縮部 ９９１ データＺ分割手段
９９２ 圧縮手段
【特許請求の範囲】
【請求項１】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、かつ、
データＸとデータＹとは一対一に対応するように
データＸをデータＹに変換する
ことを特徴とするハッシュ値生成装置。
【請求項２】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）データＸ分割手段と、
前記ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとするデータＹ生成手段と
を有し、
前記データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにし、かつ
前記データＹ生成手段は、ｘ［Ａ’］のデータ長を、前記データ長調整部の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるようにする
ことを特徴とするハッシュ値生成装置。
【請求項３】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割するデータＸ分割手段と、
μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、
データＸにビット“０”を付加した結果を、データＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、
ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、
ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、
ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、
ｘ［１］‖１をデータＹとし、
｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、
ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、
ブロックｘ”をブロックｘ［Ａ＋１］とし、
ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとするデータＹ生成手段と
を有す
（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、前記データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビットとする）
ことを特徴とするハッシュ値生成装置。
【請求項４】
データＸとハッシュ値τとを入力とし、データＸの検証を行う検証装置であって、
データＸに対するハッシュ値τ’を出力する請求項１から３のいずれかに記載のハッシュ生成装置と、
前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータＸの検証結果を出力する比較部と
を備える検証装置。
【請求項５】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、かつ、
データＸとデータＹとは一対一に対応するように
データＸをデータＹに変換する
ことを特徴とするハッシュ値生成方法。
【請求項６】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）データＸ分割サブステップと、
前記ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとするデータＹ生成サブステップと
を有し、
前記データＹ生成サブステップは、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにし、かつ
前記データＹ生成手段は、ｘ［Ａ’］のデータ長を、前記データ長調整ステップの処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるようにする
ことを特徴とするハッシュ値生成方法。
【請求項７】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割するデータＸ分割サブステップと、
μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、
データＸにビット“０”を付加した結果を、データＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、
ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、
ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、
ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、
ｘ［１］‖１をデータＹとし、
｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、
ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、
ブロックｘ”をブロックｘ［Ａ＋１］とし、
ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとするデータＹ生成サブステップと
を有す
（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、前記データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビットとする）
ことを特徴とするハッシュ値生成方法。
【請求項８】
データＸとハッシュ値τとを入力とし、データＸの検証を行う検証方法であって、
データＸに対するハッシュ値τ’を出力する請求項５から７のいずれかに記載のハッシュ生成方法の各ステップと、
比較部で、前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータＸの検証結果を出力する比較ステップと
を有する検証方法。
【請求項９】
請求項１から３のいずれかに記載のハッシュ値生成装置、または４記載の検証装置として、コンピュータを動作させるプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、かつ、
データＸとデータＹとは一対一に対応するように
データＸをデータＹに変換する
ことを特徴とするハッシュ値生成装置。
【請求項２】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）データＸ分割手段と、
前記ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとするデータＹ生成手段と
を有し、
前記データＹ生成手段は、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにし、かつ
前記データＹ生成手段は、ｘ［Ａ’］のデータ長を、前記データ長調整部の処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるようにする
ことを特徴とするハッシュ値生成装置。
【請求項３】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成装置であって、
前記データＸをデータＹに変換する前処理部と、
データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整部と、
前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮部と
を備え、
前記前処理部は、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割するデータＸ分割手段と、
μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、
データＸにビット“０”を付加した結果を、データＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、
ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、
ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、
ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、
ｘ［１］‖１をデータＹとし、
｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、
ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、
ブロックｘ”をブロックｘ［Ａ＋１］とし、
ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとするデータＹ生成手段と
を有す
（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、前記データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビットとする）
ことを特徴とするハッシュ値生成装置。
【請求項４】
データＸとハッシュ値τとを入力とし、データＸの検証を行う検証装置であって、
データＸに対するハッシュ値τ’を出力する請求項１から３のいずれかに記載のハッシュ生成装置と、
前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータＸの検証結果を出力する比較部と
を備える検証装置。
【請求項５】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＺを、Ｃ個のｍ−ｎビットのブロックｚ［１］，…，ｚ［Ｃ］に分割した場合に（ただし、ＣはデータＺをｍ−ｎビットずつに分割した場合の分割の数）、すべてのブロックｚ［１］，…，ｚ［Ｃ］がデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、かつ、
データＸとデータＹとは一対一に対応するように
データＸをデータＹに変換する
ことを特徴とするハッシュ値生成方法。
【請求項６】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割する（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数）データＸ分割サブステップと、
前記ブロックｘ［１］，…，ｘ［Ａ］を、全てのブロックがデータＸ内のμビット（ただし、μはあらかじめ定めた整数）以上を含むように、Ａ’−１個のｍ−ｎビットのブロックｘ’［１］，…，ｘ’［Ａ’−１］と１個のｍ−ｎビット以下のブロックｘ’［Ａ’］とに変換し（ただし、Ａ’はＡ以上の整数）、ｘ’［１］‖ｘ’［２］‖…‖ｘ’［Ａ’］（ただし、“‖”はビット列の結合を意味する記号）を含むビット列をデータＹとするデータＹ生成サブステップと
を有し、
前記データＹ生成サブステップは、ブロックｘ［１］，…，ｘ［Ａ］の組合せとブロックｘ’［１］，…，ｘ’［Ａ’］の組合せとが一対一に対応するようにし、かつ
前記データＹ生成手段は、ｘ［Ａ’］のデータ長を、前記データ長調整ステップの処理によって生成されるデータＺのデータ長が、Ａ’×（ｍ−ｎ）となるようにする
ことを特徴とするハッシュ値生成方法。
【請求項７】
ｍビットのデータをｎビットに圧縮する圧縮関数を用いて、データＸに対するｎビットのハッシュ値を生成するハッシュ値生成方法であって、
前処理部で、前記データＸをデータＹに変換する前処理ステップと、
データ長調整部で、データＹにパディングを行い、データ長がｍ−ｎビットの倍数のデータＺを出力するデータ長調整ステップと、
データ圧縮部で、前記圧縮関数を用いてデータＺを圧縮して、ハッシュ値を求めるデータ圧縮ステップと
を有し、
前記前処理ステップは、
データＸを、Ａ−１個のｍ−ｎビットのブロックｘ［１］，…，ｘ［Ａ−１］と、１個のｍ−ｎビット以下のブロックｘ［Ａ］に分割するデータＸ分割サブステップと、
μ≦｜ｘ［Ａ］｜≦ｍ−ｎ−σ―２ならば、
データＸにビット“０”を付加した結果を、データＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ≧２ならば、
ブロックｘ［Ａ−１］をｍ−ｎ−μビットのブロックｘ’[Ａ−１]とμビットのブロックｘ”に分割し、
ｘ”‖ｘ［Ａ］をブロックｘ’［Ａ］とし、
ｘ［１］‖…‖ｘ［Ａ−２］‖ｘ’［Ａ−１］‖１０μ-１‖ｘ’［Ａ］‖１をデータＹとし、
｜ｘ［Ａ］｜≦μ―１、かつ、Ａ＝１ならば、
ｘ［１］‖１をデータＹとし、
｜ｘ［Ａ］｜≧ｍ−ｎ−σ―１ならば、
ブロックｘ［Ａ］を｜ｘ［Ａ］｜−μビットのブロックｘ’[Ａ]とμビットのブロックｘ”に分割し、
ブロックｘ”をブロックｘ［Ａ＋１］とし、
ｘ［１］‖…‖ｘ［Ａ−１］‖ｘ’［Ａ］‖１０ｍ−ｎ−｜ｘ’［Ａ］｜−１‖ｘ’［Ａ＋１］‖１をデータＹとするデータＹ生成サブステップと
を有す
（ただし、ＡはデータＸをｍ−ｎビットずつに分割した場合の分割の数、μはあらかじめ定めた整数、“｜ｘ［Ａ］｜”はｘ［Ａ］のデータ長を示す記号、“‖”はビット列の結合を意味する記号、“０μ-１”は“０”がμ-１個並んだビット列、前記データ長調整部がデータＹのデータ長にかかわらず付加するビット数をσ＋１ビットとする）
ことを特徴とするハッシュ値生成方法。
【請求項８】
データＸとハッシュ値τとを入力とし、データＸの検証を行う検証方法であって、
データＸに対するハッシュ値τ’を出力する請求項５から７のいずれかに記載のハッシュ生成方法の各ステップと、
比較部で、前記ハッシュ値τと前記ハッシュ値τ’とを比較してデータＸの検証結果を出力する比較ステップと
を有する検証方法。
【請求項９】
請求項１から３のいずれかに記載のハッシュ値生成装置、または４記載の検証装置として、コンピュータを動作させるプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−１２８１５４（Ｐ２０１０−１２８１５４Ａ）
【公開日】平成２２年６月１０日（２０１０．６．１０）
【国際特許分類】
【出願番号】特願２００８−３０２３８０（Ｐ２００８−３０２３８０）
【出願日】平成２０年１１月２７日（２００８．１１．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年６月１０日（２０１０．６．１０）
【国際特許分類】
【出願日】平成２０年１１月２７日（２００８．１１．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]