WO2013175599A1

WO2013175599A1 - ハッシュ値演算装置、ハッシュ値演算方法及びハッシュ値演算プログラム

Info

Publication number: WO2013175599A1
Application number: PCT/JP2012/063259
Authority: WO
Inventors: 祐介内藤
Original assignee: 三菱電機株式会社
Priority date: 2012-05-24
Filing date: 2012-05-24
Publication date: 2013-11-28

Abstract

　十分な安全性を持ちつつ、効率的な関数を構成することを目的とする。ｒ'ビットのＩＶ１とｍ［１］とを入力としてＡ［１］によりｒ'ビットのｓ［１］が計算され、ｓ［１］とｃ'ビットＩＶ２とを入力として置換関数Ｐによりｔ［１］が計算される。ｔ［１］をｘ［１］として、ｘ［１］がｒ''ビットのｚ［１］とｃ''ビットのｙ［１］とに分割され、ｚ［１］とｙ［１］とを入力として置換関数Ｐによりｘ［２］が計算される。ｋ＝２からｉ'まで、ｘ［ｋ］のうちのｃ''ビットのｙ［ｋ］とｙ［ｋ－１］とを入力としてＢ［ｋ］によりｚ'［ｋ］が計算され、ｘ［ｋ］の残りのｒ''ビットのｚ［ｋ］とｙ［ｋ］とを入力として置換関数Ｐによりｘ［ｋ＋１］が計算される。ｚ［１］と全てのｋについてのｚ［ｋ］とｚ'［ｋ］とが結合されハッシュ値となる。

Description

ハッシュ値演算装置、ハッシュ値演算方法及びハッシュ値演算プログラム

　この発明は、例えば、安全性の高いハッシュ値を計算する技術に関する。

　ハッシュ関数は、任意長の値を入力として、固定長のハッシュ値を出力する関数である。

　非特許文献１－５には、擬似ランダムオラクルの性質を満たす置換関数を用いたハッシュ関数についての記載がある。非特許文献１－４のハッシュ関数は、ハッシュ長を自由に変えることができる。非特許文献５のハッシュ関数は、ハッシュ長を自由に変えることができない。
　ここで、非特許文献１－５におけるハッシュ関数が擬似ランダムオラクルの性質を満たすためには、用いる置換関数が理想化された置換関数である必要がある。

Ｇｕｉｄｏ　Ｂｅｒｔｏｎｉ，　Ｊｏａｎ　Ｄａｅｍｅｎ，　Ｍｉｃｈａｅｌ　Ｐｅｅｔｅｒｓ　ａｎｄ　Ｇｉｌｌｅｓ　Ｖａｎ　Ａｓｓｃｈｅ，　Ｏｎ　ｔｈｅ　Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　Ｓｐｏｎｇｅ　Ｃｏｎｓｔｒｕｃｔｉｏｎ，　ＥＵＲＯＣＲＹＴ　２００８，　ＬＮＣＳ　４９６５，　ｐｐ１８１－１９７Ｇ．　Ｂｅｒｔｏｎｉ，　Ｊ．　Ｄａｅｍｅｎ，　Ｍ．　Ｐｅｅｔｅｒｓ　ａｎｄ　Ｇ．　Ｖａｎ　Ａｓｓｃｈｅ，　Ｓｐｏｎｇｅ　Ｆｕｎｃｔｉｏｎｓ，　Ｅｃｒｙｐｔ　Ｈａｓｈ　Ｗｏｒｋｓｈｏｐ　２００７Ｇｕｉｄｏ　Ｂｅｒｔｏｎｉ，　Ｊｏａｎ　Ｄａｅｍｅｎ，　Ｍｉｃｈａｅｌ　Ｐｅｅｔｅｒｓ　ａｎｄ　Ｇｉｌｌｅｓ　Ｖａｎ　Ａｓｓｃｈｅ，　Ｔｈｅ　Ｋｅｃｃａｋ　ＳＨＡ－３　ｓｕｂｍｉｓｓｉｏｎ，　Ｓｕｂｍｉｓｓｉｏｎ　ｔｏ　ＮＩＳＴ　（Ｒｏｕｎｄ　３），　２０１１．Ｅｌｅｎａ　Ａｎｄｒｅｅｖａ，　Ｂａｒｔ　Ｍｅｎｎｉｎｋ　ａｎｄ　Ｂａｒｔ　Ｐｒｅｎｅｅｌ，　"Ｔｈｅ　Ｐａｒａｚｏａ　Ｆａｍｉｌｙ：　Ｇｅｎｅｒａｌｉｚｉｎｇ　ｔｈｅ　Ｓｐｏｎｇｅ　Ｈａｓｈ　Ｆｕｎｃｔｉｏｎｓ"，　Ｅｐｒｉｎｔ　ｒｅｐｏｒｔ：　０２８／２０１０．Ｈｏｎｇｊｕｎ　Ｗｕ　－　Ｔｈｅ　Ｈａｓｈ　Ｆｕｎｃｔｉｏｎ　ＪＨ，　Ｓｕｂｍｉｓｓｉｏｎ　ｔｏ　ＮＩＳＴ　（ｒｏｕｎｄ　３），　２０１１Ｖｉｃｔｏｒ　Ｓｈｏｕｐ．　Ａ　Ｐｒｏｐｏｓａｌ　ｆｏｒ　ａｎ　ＩＳＯ　Ｓｔａｎｄａｒｄ　ｆｏｒ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｅｎｃｒｙｐｔｉｏｎ　（ｖｅｒｓｉｏｎ　２．１）．　２００１．

　非特許文献１－４に記載されたハッシュ関数は、用いる置換関数が理想化された置換関数であり、その入出力長がｂビット、１メッセージサイズがｒビットの場合、擬似ランダムオラクルの性質を満たし、安全性レベルがＯ（２^{（ｂ－ｒ）／２}）である。
　しかし、このハッシュ関数は、長いハッシュ値を必要とする場合、計算効率が悪い。

　非特許文献５に記載されたハッシュ関数は、用いる置換関数が理想化された置換関数であり、その入出力長がｂビット、１メッセージサイズがｂ／２ビットの場合、擬似ランダムオラクルの性質を満たし、安全性のレベルがＯ（２^ｂ／６）である。
　しかし、長いハッシュ値を必要とする場合の計算方法は提案されていない。但し、このハッシュ関数と非特許文献６の方式とを組み合わせると、長いハッシュ値を得ることができるようになる。しかし、この場合、効率が悪くなってしまう。
　また、このハッシュ関数は、１メッセージサイズがｂ／２ビットと固定されており、非特許文献１－４に記載されたハッシュ関数より安全性が低い。

　この発明は、例えば、非特許文献１－４の方式と同等の安全性とすることが可能な関数であって、非特許文献１－４の方式より効率的な関数を構成することを目的とする。

　この発明に係るハッシュ値演算装置は、
　ｒ’ビット長（ｒ’は１以上の整数）の値ｍ［１］を入力する既定長値入力部と、
　ｒ’ビット長の固定値ＩＶ１と前記値ｍ［１］とを入力として関数Ａ［１］を計算してｒ’ビット長の値ｓ［１］を求め、求めた値ｓ［１］とｃ’ビット長（ｃ’は１以上の整数）の固定値ＩＶ２とを入力として置換関数を計算して（ｒ’＋ｃ’）ビット長の値ｔ［１］を求める先頭関数計算部と、
　値ｔ［１］を値ｘ［１］として、値ｘ［１］からｒ’’ビット長（ｒ’’は１以上の整数）の値ｚ［１］と、値ｘ［１］から値ｚ［１］を除いたｃ’’ビット長（ｃ’’は１以上の整数であり、ｒ’＋ｃ’＝ｒ’’＋ｃ’’）の値ｙ［１］とを切り出して、値ｚ［１］と値ｙ［１］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［２］を求めるとともに、ｋ＝２からｉ’（ｉ’は１以上の整数）まで順に、値ｘ［ｋ］からｒ’’ビット長の値ｚ［ｋ］を切り出し、値ｘ［ｋ］から値ｚ［ｋ］を除いたｃ’’ビット長の値ｙ［ｋ］と値ｙ［ｋ－１］とを入力として関数Ｂ［ｋ］を計算してｃ’’ビット長の値ｚ’［ｋ］を求め、値ｚ［ｋ］と値ｙ［ｋ］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［ｋ＋１］を求める出力関数計算部と、
　値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを結合してハッシュ値Ｚを計算するハッシュ値計算部と
を備えることを特徴とする。

　この発明に係るハッシュ値演算装置は、用いる置換関数が理想化された置換関数であれば、擬似ランダムオラクルの性質を満たし、かつ、非特許文献１－４の方式と同等の安全性とすることが可能な関数であって、非特許文献１－４の方式より効率的な関数を構成することができる。

実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図。図１に示すハッシュ値演算装置１０の動作を示すフローチャート。図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図（１）。図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図（２）。

　実施の形態１．
　まず、ハッシュ関数の安全性の概念について説明する。

　ランダムオラクルの性質を満たすハッシュ関数は、理想化されたハッシュ関数である。
　ランダムオラクルの性質を満たすハッシュ関数Ｈとは、以下の１，２が与えられたハッシュ関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリスト。
２．（順方向の値を出力するオラクル）：入力値ｘに対し、リストから入力値ｘに対する出力値ｚを検索して、値ｚを出力するオラクル。つまり、Ｈ（ｘ）＝ｚとなる値ｚを出力するオラクルである。

　ランダムオラクルの性質を満たすハッシュ関数は、「（１）衝突困難性」、「（２）第２原像計算困難性」、「（３）原像計算困難性」の３つの性質を満たす。
　（１）～（３）の各性質の定義は以下の通りである。以下の定義において、「Ｈ」は、ハッシュ関数を示す。「Ｍ」「Ｍ’（≠Ｍ）」は、ハッシュ関数Ｈの入力値を示す。「Ｈ（ｘ）」は、ｘを入力したハッシュ関数Ｈの出力（ハッシュ値）を示す。

（１）衝突困難性を満たすハッシュ関数とは、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」となる２つの入力値Ｍ、Ｍ’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質である。
（２）第２原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Ｍが与えられたとき、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」を満たす入力値Ｍ’を見つけることが困難なハッシュ関数である。つまり、第２原像計算困難性とは、第１の入力値とハッシュ値が同じである第２の入力値を求めることが難しいという性質である。
（３）原像計算困難性を満たすハッシュ関数とは、ランダムな値ｚが与えられたとき、「ｚ＝Ｈ（Ｍ）」を満たすＭを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質である。

　（１）～（３）各性質には、（１）衝突困難性を満たすハッシュ関数は（２）第２原像計算困難性を満たし、（２）第２原像計算困難性を満たすハッシュ関数は（３）原像計算困難性を満たすという関係がある。
　また、（３）原像計算困難性が破られたハッシュ関数（原像計算困難性を満たさないハッシュ関数）は、（１）衝突困難性、及び、（２）第２原像計算困難性を満たさないという関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき（１）～（３）の性質を満たさない関数であり、安全性が低いため一般的に使い物にならない。

　標準的な公開鍵暗号、電子署名アルゴリズムであるＲＳＡ－ＯＡＥＰ（ＲＳＡ－Ｏｐｔｉｍａｌ　Ａｓｙｍｍｅｔｒｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　Ｐａｄｄｉｎｇ）、ＲＳＡ－ＫＥＭ（ＲＳＡ－Ｋｅｙ　Ｅｎｃａｐｓｕｌａｔｉｏｎ　Ｍｅｃｈａｎｉｓｍ）、ＲＳＡ－ＰＳＳ（ＲＳＡ－Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｓｉｇｎａｔｕｒｅ　Ｓｃｈｅｍｅ）などは、用いられるハッシュ関数がランダムオラクルの性質を満たすと仮定したときに安全なものである。
　しかし、ランダムオラクルの性質を満たすハッシュ関数を実現することは困難であることが知られている。そのため、これらの公開鍵暗号、電子署名アルゴリズムを実現する際は、ランダムオラクルの性質を満たすハッシュ関数に代え、ＳＨＡ－２５６（Ｓｅｃｕｒｅ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ－２５６）などのハッシュ関数を用いて運用されている。

　ランダムオラクルの性質を満たさないハッシュ関数を用いて、上述した公開鍵暗号、電子署名アルゴリズムを実現した場合、その安全性が保証されるとは限らない。しかし、その安全性を保証するための概念として、擬似ランダムオラクルという概念が存在する。
　ここで、ハッシュ関数で用いる内部関数をＰ、Ｐを用いて構成したハッシュ関数をＨ［Ｐ］とする。Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすとは、どんな識別者でも、Ｈ［Ｐ］とランダムオラクルの性質を満たすハッシュ関数とを識別できないようなＰをシミュレートするシミュレータＳが存在することである。

　Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすならば、Ｈ［Ｐ］は（１）衝突困難性、（２）第２原像計算困難性、（３）原像計算困難性の性質を満たす。そして、ランダムオラクルの性質を満たすハッシュ関数を用いた場合に安全な暗号アルゴリズムは、Ｈ［Ｐ］を用いた場合にも安全であることが保証される。

　置換関数（Ｐ，Ｐｉｎｖ）は、順方向計算関数Ｐ、逆方向計算関数Ｐｉｎｖの組である。順方向計算関数Ｐと逆方向計算関数Ｐｉｎｖとは、所定のｄビットの値を入力とし、ｄビットの値を出力する。
　理想化された置換関数とは、全ての置換関数の集合からランダムに１つ置換関数を選択した場合における置換関数のことである。

　理想化された置換関数を実現することは困難であることが知られている。そのため、非特許文献１－５に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する際は、理想化された置換関数の代わりに、加算、シフト、掛け算、テーブル参照などを用いて実現した置換関数を用いることが考えられる。
　この場合、理想化された置換関数を用いていないため、得られたハッシュ関数は、擬似ランダムオラクルの性質を満たすハッシュ関数とはならない。しかし、理想化された置換関数を用いた場合に疑似ランダムオラクルの性質を満たすことが証明されているため、ある程度の安全性があるものと認められる。

　以下の説明では、非特許文献１－５に記載されたハッシュ関数と同様に、置換関数を用いたハッシュ関数について説明する。以下で説明するハッシュ関数は、非特許文献１－５に記載されたハッシュ関数と同様に、用いる置換関数が理想化された置換関数の場合、擬似ランダムオラクルの性質を満たす。
　しかし、以下で説明するハッシュ関数では、非特許文献１－４に記載されたハッシュ関数と同等の安全性を満たし、非特許文献１－４に記載されたハッシュ関数より長いハッシュ値を高速に計算可能である。

　図１は、実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
　図２は、図１に示すハッシュ値演算装置１０の動作を示すフローチャートである。
　図３，４は、図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。なお、図４は図３の処理の続きを示す。

　図１に示すハッシュ値演算装置１０の機能と動作について、図２－４を用いて説明する。
　図１に示すハッシュ値演算装置１０は、任意長値入力部１１、パディング部１２、分割部１３、既定長値入力部１４、関数計算部１５、ハッシュ値計算部１６を備える。関数計算部１５は、先頭関数計算部１５１、後続関数計算部１５２、出力関数計算部１５３を備える。

　なお、関数計算部１５は、図３，４に示す関数Ａ［１］，．．．，Ａ［ｉ］と、関数Ｂ［２］，．．．，Ｂ［ｉ’］と、関数Ｐとを用いる。
　関数Ａ［１］は、２つのｒ’ビット長（ｒ’は１以上の整数）の値を入力とし、ｒ’ビット長の値を出力する関数である。関数Ａ［１］は、例えば、ｘ，ｙをｒ’ビット長の値とすると、ｘ＋ｙを計算してｒ’＋１ビット目以降は切り捨てて出力する関数や、ｘとｙとの排他的論理和を計算して出力する関数である。
　関数Ａ［２］，．．．，Ａ［ｉ］は、２つのｒビット長（ｒは１以上の整数）の値を入力とし、ｒビット長の値を出力する関数である。関数Ａ［２］，．．．，Ａ［ｉ］は、例えば、ｘ，ｙをｒビット長の値とすると、ｘ＋ｙを計算してｒ＋１ビット目以降は切り捨てて出力する関数や、ｘとｙとの排他的論理和を計算して出力する関数である。
　関数Ｂ［２］，．．．，Ｂ［ｉ’］は、２つのｃ’’ビット長（ｃ’’は１以上の整数）の値を入力とし、２つのｃ’’ビット長の値を出力する関数である。関数Ｂ［２］，．．．，Ｂ［ｉ’］は、例えば、ｘ，ｙをｃ’’ビット長の値とすると、ｘ＋ｙを計算してｃ’’＋１ビット目以降は切り捨てて出力する関数や、ｘとｙとの排他的論理和を計算して出力する関数である。
　関数Ｐは、上述した置換関数における順方向計算関数であり、ｄビット長の値を入力とし、ｄビット長の値を出力する。なお、以下の説明において、ｃ，ｃ’，ｒ’’は１以上の整数であり、ｄ＝ｒ＋ｃ＝ｒ’＋ｃ’＝ｒ’’＋ｃ’’である。

　（Ｓ１：任意長値入力ステップ）
　任意長値入力部１１は、入力装置により、任意ビット長の値Ｍを入力する。

　（Ｓ２：パディングステップ）
　パディング部１２は、処理装置により、（Ｓ１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、ｒ’＋（ｉ－１）ｒビット長の値Ｍ＊を生成する。なお、ｉは１以上の整数である。但し、パディング部１２は、最後のｒビットが全て０にならないように、値Ｍ＊を生成する。
　パディング部１２は、例えば、値Ｍの後に１を付加し、その後に０を必要なビット数付加してｒ’＋（ｉ－１）ｒビット長の値Ｍ＊とする。つまり、Ｍ＊＝Ｍ｜｜１｜｜０，．．．，０とする。この方法により、最後のｒビットが全て０となる場合には、最後のｒビットのうちの少なくとも１ビットを１にすればよい。

　（Ｓ３：分割ステップ）
　分割部１３は、処理装置により、（Ｓ２）で生成されたｒ’＋（ｉ－１）ｒビット長の値Ｍ＊を先頭からｒ’ビット切り出して値ｍ［１］とする。さらに、分割部１３は、処理装置により、残りの（ｉ－１）ｒビット長の値を先頭から順にｒビット毎にｉ－１個に分割して、先頭から順に値ｍ［２］，．．．，ｍ［ｉ－１］とする。

　（Ｓ４：既定長値入力ステップ）
　既定長値入力部１４は、入力装置により、分割部１３が生成したｒ’ビット長の値ｍ［１］と、ｒビット長のｉ－１個の値ｍ［２］，．．．，値ｍ［ｉ］とを入力する。

　（Ｓ５：関数計算ステップ）
　関数計算ステップは、（Ｓ５１）から（Ｓ５３）までの３つのステップを備える。
　（Ｓ５１：先頭関数計算ステップ）
　先頭関数計算部１５１は、処理装置により、ｒ’ビット長の固定値ＩＶ１とｒ’ビット長の値ｍ［１］とを入力として関数Ａ［１］を計算してｒ’ビット長の値ｓ［１］を求める。そして、先頭関数計算部１５１は、処理装置により、求めた値ｓ［１］とｃ’ビット長の固定値ＩＶ２とを入力として置換関数Ｐを計算して（ｒ’＋ｃ’）ビット長の値ｔ［１］を求める。

　（Ｓ５２：後続関数計算ステップ）
　後続関数計算部１５２は、ｊ＝２からｉまで順に、以下の処理を実行する。
　後続関数計算部１５２は、処理装置により、値ｔ［ｊ－１］を先頭のｒビット長の値ｕ［ｊ］と、残りのｃビット長の値ｖ［ｊ］とに分割する。次に、後続関数計算部１５２は、処理装置により、ｒビット長の値ｕ［ｊ］とｒビット長の値ｍ［ｊ］とを入力として関数Ａ［ｊ］を計算してｒビット長の値ｓ［ｊ］を求める。そして、後続関数計算部１５２は、処理装置により、ｒビット長の値ｓ［ｊ］とｃビット長の値ｖ［ｊ］とを入力として置換関数Ｐを計算して（ｒ＋ｃ）ビット長の値ｔ［ｊ］を求める。

　（Ｓ５３：出力関数計算ステップ）
　出力関数計算部１５３は、値ｔ［ｉ］を値ｘ［１］とする。
　出力関数計算部１５３は、処理装置により、値ｘ［１］を先頭のｒ’’ビット長の値ｚ［１］と、残りのｃ’’ビット長の値ｙ［１］とに分割する。次に、出力関数計算部１５３は、処理装置により、値ｚ［１］と値ｙ［１］とを入力として置換関数Ｐを計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［２］を求める。
　続いて、出力関数計算部１５３は、ｋ＝２からｉ’（ｉ’は１以上の整数）まで順に、以下の処理を実行する。
　出力関数計算部１５３は、処理装置により、値ｘ［ｋ］を先頭のｒ’’ビット長の値ｚ［ｋ］と、残りのｃ’’ビット長の値ｙ［ｋ］とに分割する。次に、出力関数計算部１５３は、処理装置により、ｃ’’ビット長の値ｙ［ｋ］とｃ’’ビット長の値ｙ［ｋ－１］とを入力として関数Ｂ［ｋ］を計算してｃ’’ビット長の値ｚ’［ｋ］を求める。そして、出力関数計算部１５３は、処理装置により、値ｚ［ｋ］と値ｙ［ｋ］とを入力として置換関数Ｐ計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［ｋ＋１］を求める。

　（Ｓ６：ハッシュ値計算ステップ）
　ハッシュ値計算部１６は、処理装置により、Ｓ５３で計算した値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを結合関数を用いて結合してハッシュ値Ｚを計算する。

　なお、上記説明では、Ｓ５２において、値ｔ［ｊ－１］を先頭のｒビット長の値ｕ［ｊ］と、残りのｃビット長の値ｖ［ｊ］とに分割した。しかし、値ｕ［ｊ］は、値ｔ［ｊ－１］の先頭のｒビットでなくても、値ｔ［ｊ－１］から切り出されたｒビットの値であればよい。そして、値ｖ［ｊ］は、値ｔ［ｊ－１］から値ｕ［ｊ］を除いた残りのｃビットからなる値であればよい。
　同様に、上記説明では、Ｓ５３において、値ｘ［ｋ］を先頭のｒ’’ビット長の値ｚ［ｋ］と、残りのｃ’’ビット長の値ｙ［ｋ］とに分割した。しかし、値ｚ［ｋ］は、値ｘ［ｋ］の先頭のｒ’’ビットでなくても、値ｘ［ｋ］から切り出されたｒ’’ビットの値であればよい。そして、値ｙ［ｋ］は、値ｘ［ｋ］から値ｚ［ｋ］を除いた残りのｃ’’ビットからなる値であればよい。

　また、Ｓ５３における処理の繰り返し回数ｉ’は、ハッシュ値として必要なビット数によって決定される。つまり、値ｚ［ｋ］と値ｚ’［ｋ］との合計ビット数が、ハッシュ値として必要なビット数になるまでＳ５３の処理を繰り返せばよい。

　また、上記説明では、ｉが２以上の場合を想定して説明した。しかし、ｉが１である場合には、Ｓ５２は実行されず、Ｓ５３で値ｔ［１］を値ｘ［１］とする。

　以上に説明したハッシュ値演算装置１０は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、記憶装置は、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）であり、記憶装置は、例えばＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばＬＣＤ（Ｌｉｑｕｉｄ　Ｃｒｙｓｔａｌ　Ｄｉｓｐｌａｙ）等の表示装置、通信ボード、レジスタやＲＡＭ等の記憶装置である。もちろん、これらに限定されるものではない。
　なお、ハッシュ値演算装置１０を回路で構成する場合、上述した「～部」を「～回路」と読み変えてもよい。また、上述した「～部」は、「～処理」、「～装置」、「～機器」、「～手段」、「～手順」、「～機能」と読み替えてもよい。つまり、「～部」として説明するものは、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。

　以上のように、実施の形態１に係るハッシュ値演算装置１０は、後続処理（Ｓ５２）ではｒビット長のメッセージを処理するのに対して、先頭処理（Ｓ５１）ではｒ’ビット長のメッセージを処理する。そのため、先頭処理で処理可能なメッセージを長くすることが可能である。
　また、実施の形態１に係るハッシュ値演算装置１０は、出力処理（Ｓ５３）における置換関数の出力値を全て用いてハッシュ値を計算する。
　そのため、実施の形態１に係るハッシュ値演算装置１０は、高速にハッシュ値を計算することができる。

　また、ｃ’，ｃ’’をｃ／２以上にすることにより、実施の形態１に係るハッシュ値演算装置１０は、用いる置換関数が理想化されたｂビット入出力置換関数であれば、擬似ランダムオラクルの性質を満たし、かつ、安全性のレベルがＯ（２^{（ｂ－ｒ）／２}）＝Ｏ（２^ｃ／２）となるハッシュ関数を構成することができる。
　ｃ’，ｃ’’をｃ／２以上にする理由は、擬似ランダムオラクルの性質を破る攻撃法として、計算量が２^ｃ’のものや計算量が２^ｃ’’のものがあるためである。ｃ’をｃ／２以上ｃ’’をｃ／２以上とすることで、これらの攻撃法による計算量が２^ｃ／２となり、安全性のレベルがＯ（２^ｃ／２）となる。

　１０　ハッシュ値演算装置、１１　任意長値入力部、１２　パディング部、１３　分割部、１４　既定長値入力部、１５　関数計算部、１５１　先頭関数計算部、１５２　後続関数計算部、１５３　出力関数計算部、１６　ハッシュ値計算部。

Claims

　ｒ’ビット長（ｒ’は１以上の整数）の値ｍ［１］を入力する既定長値入力部と、
　ｒ’ビット長の固定値ＩＶ１と前記値ｍ［１］とを入力として関数Ａ［１］を計算してｒ’ビット長の値ｓ［１］を求め、求めた値ｓ［１］とｃ’ビット長（ｃ’は１以上の整数）の固定値ＩＶ２とを入力として置換関数を計算して（ｒ’＋ｃ’）ビット長の値ｔ［１］を求める先頭関数計算部と、
　値ｔ［１］を値ｘ［１］として、値ｘ［１］からｒ’’ビット長（ｒ’’は１以上の整数）の値ｚ［１］と、値ｘ［１］から値ｚ［１］を除いたｃ’’ビット長（ｃ’’は１以上の整数であり、ｒ’＋ｃ’＝ｒ’’＋ｃ’’）の値ｙ［１］とを切り出して、値ｚ［１］と値ｙ［１］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［２］を求めるとともに、ｋ＝２からｉ’（ｉ’は１以上の整数）まで順に、値ｘ［ｋ］からｒ’’ビット長の値ｚ［ｋ］を切り出し、値ｘ［ｋ］から値ｚ［ｋ］を除いたｃ’’ビット長の値ｙ［ｋ］と値ｙ［ｋ－１］とを入力として関数Ｂ［ｋ］を計算してｃ’’ビット長の値ｚ’［ｋ］を求め、値ｚ［ｋ］と値ｙ［ｋ］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［ｋ＋１］を求める出力関数計算部と、
　値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを結合してハッシュ値Ｚを計算するハッシュ値計算部と
を備えることを特徴とするハッシュ値演算装置。
　前記既定長値入力部は、さらに、（ｉ－１）個（ｉは２以上の整数）のｒビット長（ｒは１以上の整数）の値ｍ［２］，．．．，値ｍ［ｉ］を入力し、
　前記ハッシュ値演算装置は、さらに、
　ｊ＝２からｉまで順に、値ｔ［ｊ－１］からｒビット長の値ｕ［ｊ］を切り出し、値ｕ［ｊ］と値ｍ［ｊ］とを入力として関数Ａ［ｊ］を計算してｒビット長の値ｓ［ｊ］を求め、求めた値ｓ［ｊ］と値ｔ［ｊ－１］から値ｕ［ｊ］を除いたｃビット長（ｃは１以上の整数であり、ｒ＋ｃ＝ｒ’＋ｃ’＝ｒ’’＋ｃ’’）の値ｖ［ｊ］とを入力として置換関数を計算して（ｒ＋ｃ）ビット長の値ｔ［ｊ］を求める後続関数計算部
を備え、
　前記出力関数計算部は、前記値ｍ［２］，．．．，値ｍ［ｉ］が入力された場合には、値ｔ［ｉ］を値ｘ［１］とする
ことを特徴とする請求項１に記載のハッシュ値演算装置。
　前記ハッシュ値演算装置は、さらに、
　任意ビット長の値Ｍを入力する任意長値入力部と、
　前記任意長値入力部が入力した値Ｍに対して、所定の値を付加して（ｒ’＋（ｉ－１）×ｒ）ビット長の値Ｍ’を生成するパディング部と、
　前記パディング部が生成した値Ｍ’を分割して、値ｍ［１］と、値ｍ［２］，．．．，値ｍ［ｉ］を生成する分割部と
を備え、
　前記既定長値入力部は、前記分割部が生成した値ｍ［１］と、値ｍ［２］，．．．，値ｍ［ｉ］を入力する
ことを特徴とする請求項２に記載のハッシュ値演算装置。
　前記関数Ａ［１］，．．．，Ａ［ｉ］と、前記関数Ｂ［１］，．．．，［ｉ’］とは、２つの入力値の和を計算し、不要なビットを切り捨てて出力する関数、あるいは、２つの入力値の排他的論理和を計算して出力する関数のいずれかである
ことを特徴とする請求項２又は３に記載のハッシュ値演算装置。
　前記ハッシュ値計算部は、値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを順に結合してハッシュ値Ｚを計算する
ことを特徴とする請求項１から４までのいずれかに記載のハッシュ値演算装置。
　前記ｃ’及び前記ｃ’’は、ｃ／２以上の整数である
ことを特徴とする請求項２に記載のハッシュ演算装置。
　入力装置が、ｒ’ビット長（ｒ’は１以上の整数）の値ｍ［１］を入力し、
　処理装置が、ｒ’ビット長の固定値ＩＶ１と前記値ｍ［１］とを入力として関数Ａ［１］を計算してｒ’ビット長の値ｓ［１］を求め、求めた値ｓ［１］とｃ’ビット長（ｃ’は１以上の整数）の固定値ＩＶ２とを入力として置換関数を計算して（ｒ’＋ｃ’）ビット長の値ｔ［１］を求め、
　処理装置が、値ｔ［１］を値ｘ［１］として、値ｘ［１］からｒ’’ビット長（ｒ’’は１以上の整数）の値ｚ［１］と、値ｘ［１］から値ｚ［１］を除いたｃ’’ビット長（ｃ’’は１以上の整数であり、ｒ’＋ｃ’＝ｒ’’＋ｃ’’）の値ｙ［１］とを切り出して、値ｚ［１］と値ｙ［１］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［２］を求めるとともに、ｋ＝２からｉ’（ｉ’は１以上の整数）まで順に、値ｘ［ｋ］からｒ’’ビット長の値ｚ［ｋ］を切り出し、値ｘ［ｋ］から値ｚ［ｋ］を除いたｃ’’ビット長の値ｙ［ｋ］と値ｙ［ｋ－１］とを入力として関数Ｂ［ｋ］を計算してｃ’’ビット長の値ｚ’［ｋ］を求め、値ｚ［ｋ］と値ｙ［ｋ］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［ｋ＋１］を求め、
　処理装置が、値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを結合してハッシュ値Ｚを計算する
ことを特徴とするハッシュ値演算方法。
　ｒ’ビット長（ｒ’は１以上の整数）の値ｍ［１］を入力する既定長値入力処理と、
　ｒ’ビット長の固定値ＩＶ１と前記値ｍ［１］とを入力として関数Ａ［１］を計算してｒ’ビット長の値ｓ［１］を求め、求めた値ｓ［１］とｃ’ビット長（ｃ’は１以上の整数）の固定値ＩＶ２とを入力として置換関数を計算して（ｒ’＋ｃ’）ビット長の値ｔ［１］を求める先頭関数計算処理と、
　値ｔ［１］を値ｘ［１］として、値ｘ［１］からｒ’’ビット長（ｒ’’は１以上の整数）の値ｚ［１］と、値ｘ［１］から値ｚ［１］を除いたｃ’’ビット長（ｃ’’は１以上の整数であり、ｒ’＋ｃ’＝ｒ’’＋ｃ’’）の値ｙ［１］とを切り出して、値ｚ［１］と値ｙ［１］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［２］を求めるとともに、ｋ＝２からｉ’（ｉ’は１以上の整数）まで順に、値ｘ［ｋ］からｒ’’ビット長の値ｚ［ｋ］を切り出し、値ｘ［ｋ］から値ｚ［ｋ］を除いたｃ’’ビット長の値ｙ［ｋ］と値ｙ［ｋ－１］とを入力として関数Ｂ［ｋ］を計算してｃ’’ビット長の値ｚ’［ｋ］を求め、値ｚ［ｋ］と値ｙ［ｋ］とを入力として置換関数を計算して（ｒ’’＋ｃ’’）ビット長の値ｘ［ｋ＋１］を求める出力関数計算処理と、
　値ｚ［１］と、ｋ＝２からｉ’までの値ｚ［ｋ］と値ｚ’［ｋ］とを結合してハッシュ値Ｚを計算するハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。