ハッシュ値演算装置及びハッシュ値演算方法及びハッシュ値演算プログラム
【課題】ハッシュ関数に入力するメッセージのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることを目的とする。
【解決手段】演算部１０４は、ｎ個の演算器Ｃ１，・・・，Ｃｎを有する。演算部１０４は、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力としてビット列Ｍｉの入力を受け付け、ビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、演算器Ｃ１，・・・，Ｃｎを用いて演算する。ビット列Ｍｉは演算器Ｃｉごとに予め定められたビット長をもつ。パディング部１０２は、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、ビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加してメッセージＭ´を生成する。ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じて設定される。
【解決手段】演算部１０４は、ｎ個の演算器Ｃ１，・・・，Ｃｎを有する。演算部１０４は、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力としてビット列Ｍｉの入力を受け付け、ビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、演算器Ｃ１，・・・，Ｃｎを用いて演算する。ビット列Ｍｉは演算器Ｃｉごとに予め定められたビット長をもつ。パディング部１０２は、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、ビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加してメッセージＭ´を生成する。ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じて設定される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値演算装置及びハッシュ値演算方法及びハッシュ値演算プログラムに関するものである。本発明は、特に、ハッシュ関数の入力値を加工する方式（ハッシュ関数パディング方式）に関するものである。
【背景技術】
【０００２】
ハッシュ関数は入力長が任意で、出力長が固定の関数である。ハッシュ関数Ｈには衝突困難性が要求される。衝突困難性とは、Ｈ（Ｍ）＝Ｈ（Ｍ´）となる異なる２つの値Ｍ、Ｍ´を求めることは難しいという性質である。
【０００３】
ハッシュ関数の入力長は任意であるが、ハッシュ関数の中ではある長さの倍数に変換してから用いられる。通常の変換方式は入力値の後ろに“１”と“０・・・０”（“０”のビット列）と６４ビットの入力長の符号語が付加されるパディング処理が一般的である（例えば、非特許文献１参照）。
【０００４】
ハッシュ関数は小さな部品を組み合わせて構成される。この部品とはブロック暗号や圧縮関数と呼ばれる、入力長、出力長が固定された関数である。
【０００５】
ハッシュ関数の構成法にｓｔｒｅｎｇｔｈ・Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ（ｓＭＤ）構造がある。ここで、圧縮関数の入力長をａビット、出力長をｂビットとおく。ｂビットの固定値をＩＶ（Ｉｎｉｔｉａｌｉｚａｔｉｏｎ・Ｖｅｃｔｏｒ）とおく。ＭＤ構造への入力をＭとおく。中身の処理では、まずＭから、ビット長がａ−ｂビットの倍数となるＭ´を、Ｍの後ろに“１”と“０・・・０”（“０”のビット列）とＭのビット長を表す６４ビットの符号語を付加することにより生成する。即ち、
Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜｜Ｍ｜＞
とする。なお、“｜｜”はビット（列）の連結を表記したものである。“｜Ｍ｜”はＭのビット長を表記したものである。“＜｜Ｍ｜＞”はＭのビット長を表す固定長（ここでは６４ビット）の符号語を表記したものである。Ｍに付加する“０・・・０”は、０を付加する個数が最小となるようにする。次にＭ´をａ−ｂビットごとに分割する。即ち、
Ｍ´＝（ｍ［１］，ｍ［２］，・・・，ｍ［ｎ］）
とする。ｃ［１］＝ＩＶとおき、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｍ［ｉ］）をｉ＝１，・・・，ｎ（ｎはｎ＞１となる整数）について計算する。なお、ｈ（ｃ［ｉ］，ｍ［ｉ］）はｃ［ｉ］を入力、ｍ［ｉ］を出力とする圧縮関数を表記したものである。最後にｃ［ｎ＋１］をハッシュ関数の出力値とする。
【０００６】
ハッシュ関数の入力値の後ろに“１”を付加せず、“０・・・０”（“０”のビット列）と６４ビットの入力長の符号語のみを付加するパディング方式もある（例えば、非特許文献２参照）。
【非特許文献１】Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， “Ｓｅｃｕｒｅ Ｈａｓｈ Ｓｔａｎｄａｒｄ （ＳＨＳ），” Ｆｅｄｅｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄｓ Ｐｕｂｌｉｃａｔｉｏｎ １８０−２， Ａｕｇｕｓｔ １， ２００２
【非特許文献２】Ｄｏｎ Ｂ． Ｊｏｈｎｓｏｎ， Ｅｎｔｒｕｓｔ ＣｙｇｎａＣｏｍ， “Ｉｍｐｒｏｖｉｎｇ Ｈａｓｈ Ｆｕｎｃｔｉｏｎ Ｐａｄｄｉｎｇ，” Ｆｉｒｓｔ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｓｈ Ｗｏｒｋｓｈｏｐ， Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎｏｖｅｍｂｅｒ １， ２００５
【発明の開示】
【発明が解決しようとする課題】
【０００７】
非特許文献２の方式では、一般的なパディング方式（Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｍ＞）よりもパディングされたデータの長さが短くなるものの、１ビットしか短くできないため、ハッシュ関数の計算量が依然多いという課題があった。
【０００８】
本発明は、例えば、ハッシュ関数に入力するメッセージのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一の態様に係るハッシュ値演算装置は、
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
メッセージＭを入力する入力部と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とする。
【発明の効果】
【００１０】
本発明の一の態様によれば、ｎ個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉへの入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置において、パディング部が、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成することにより、メッセージＭのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の実施の形態について、図を用いて説明する。
【００１２】
実施の形態１．
図１は、本実施の形態に係るハッシュ値演算装置１００の構成を示すブロック図である。
【００１３】
図１において、ハッシュ値演算装置１００は、入力部１０１、パディング部１０２、分割部１０３、演算部１０４、出力部１０５を備える。
【００１４】
演算部１０４は、ｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有する。演算部１０４は、それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力としてビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値Ｈ（Ｍ´）を、上記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する。ビット列Ｍｉは演算器Ｃｉごとに予め定められたビット長をもつ。以下では、ビット列Ｍｉのビット長をｍｉ（ｍｉはｍｉ＞０となる整数）と表記する。
【００１５】
入力部１０１は、ハッシュ関数の入力値であるメッセージＭを入力する。メッセージＭは任意のビット長をもつ。以下では、メッセージＭのビット長をｍ（ｍはｍ＞１となる整数）と表記する。
【００１６】
パディング部１０２は、入力部１０１により入力されたメッセージＭに対し、所定のパディングを行って上記メッセージＭ´を生成する。具体的には、パディング部１０２は、ｎを表すビット列Ｓと所定のビットパターンＴとを組み合わせて（さらに、他のビットあるいはビット列と組み合わせてもよい）ビット列Ｐを生成する。そして、パディング部１０２は、生成したビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加して上記メッセージＭ´を生成する。ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じてパディング部１０２により設定される。以下では、ビット列Ｐのビット長をｐ（ｐはｐ＞０となる整数）と表記する。なお、ｐは可変であるが、メッセージＭ´のビット長はΣｍｉであるから、常にｐ＝Σｍｉ−ｍが成り立つ。
【００１７】
本実施の形態では、パディング部１０２は、ビットパターンＴとして、“１０・・・０”（開始ビットが“１”、それ以外がオール“０”）を生成するものとする。なお、パディング部１０２は、これ以外にも、“０・・・０”（オール“０”）、“１・・・１”（オール“１”）、“０１・・・１”（開始ビットが“０”、それ以外がオール“１”）といった任意のパターンを用いることができるが、ハッシュ関数の衝突困難性を高めるため、“１０”又は“０１”で始まるものを用いることが望ましい。どのようなパターンを用いるかは予め定義されており、パディング部１０２は、その定義に従ってビットパターンＴを生成する。予め複数のパターンが定義されている場合には、パディング部１０２が、それらのパターンのうち、外部から指定されたものを用いるようにしてもよいし、用途等に応じていずれかのパターンを選択し、選択したものを用いるようにしてもよい。
【００１８】
本実施の形態では、パディング部１０２は、ビット列ＰをメッセージＭの後（所定の位置の一例）に連結してメッセージＭ´を生成するものとする。なお、パディング部１０２は、ビット列ＰをメッセージＭの先頭に追加して（即ち、ビット列Ｐの後にメッセージＭを連結して）メッセージＭ´を生成してもよいし、ビット列ＰをメッセージＭの所定の位置に挿入してメッセージＭ´を生成してもよい。どの位置にビット列Ｐを追加するかは予め定義されており、パディング部１０２は、その定義に従ってビット列ＰをメッセージＭに追加する。予め複数の位置が定義されている場合には、パディング部１０２が、外部から指定された位置にビット列Ｐを追加するようにしてもよいし、用途等に応じていずれかの位置を選択し、選択した位置にビット列Ｐを追加するようにしてもよい。
【００１９】
分割部１０３は、パディング部１０２により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成する。そして、分割部１０３は、生成したビット列Ｍ１，・・・，Ｍｎを演算部１０４へ入力して演算部１０４にメッセージＭ´のハッシュ値Ｈ（Ｍ´）を演算させる。
【００２０】
出力部１０５は、演算部１０４により演算されたメッセージＭ´のハッシュ値Ｈ（Ｍ´）を出力する。
【００２１】
図２は、演算部１０４の構成の一例を示すブロック図である。
【００２２】
図２において、演算部１０４が備えるｎ個の演算器Ｃ１，・・・，Ｃｎは、それぞれ圧縮関数ｈの演算を行う回路（ハードウェアで実装される場合）、関数（ソフトウェアで実装される場合）等である（ハードウェアとソフトウェアとの組み合わせで実装されてもよい）。なお、演算器Ｃ１，・・・，Ｃｎの個数ｎは、入力部１０１により入力されるメッセージＭのビット長ｍに応じて決まるものである。単純な例として、ビット列Ｍ１，・・・，Ｍｎが、いずれも同じビット長をもつとすると、そのビット長でｍを割ったときの商がｎとなる。なお、このときの余りがパディング部１０２により生成されるビット列Ｐのビット長ｐとなる。以上より、演算部１０４は、実際には所定数の演算器を備えておき、その中から、メッセージＭのビット長ｍに応じてｎ個の演算器Ｃ１，・・・，Ｃｎを選択して用いることが望ましい。
【００２３】
それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対して圧縮関数ｈの演算を行ってビット列Ｂｉを生成する。ｉ＜ｎの場合、演算器Ｃｉは、生成したビット列Ｂｉを他の演算器Ｃｊ（ｊはｉ＜ｊ≦ｎとなる整数）へビット列Ａｊの一部として入力する。図１に示したように、本実施の形態では、演算部１０４のｎ個の演算器Ｃ１，・・・，Ｃｎは、順番に直列に接続されているものとする。そして、それぞれの演算器Ｃｉは、ｉ＜ｎの場合（即ち、演算器Ｃ１，・・・，Ｃｎ−１は）、生成したビット列Ｂｉを他の演算器Ｃｊである演算器Ｃｉ＋１へビット列Ａｉ＋１の一部として入力するものとする。演算器Ｃｎは、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【００２４】
例えば、演算器Ｃ１は、所定の固定値であるＩＶとパディング部１０２により生成されたビット列Ｍ１とからなるビット列Ａ１が入力されると、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算器Ｃ２は、演算器Ｃ１から出力されたビット列Ｂ１とパディング部１０２により生成されたビット列Ｍ２とからなるビット列Ａ２が入力されると、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成する。演算器Ｃ３以降については、演算器Ｃ２と同様である。この例では、出力部１０５は、演算器Ｃｎにより生成されたビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力することになる。
【００２５】
他の実施の形態については後述するが、演算部１０４の構成としては、ハッシュ関数の演算が可能なものであれば、図２に示したもの以外にも様々な構成を採用することができる。また、例えば、ビット列Ｍ１，・・・，Ｍｎが、いずれも同じビット長をもち、さらに、ビット列Ａ１，・・・，Ａｎが、いずれも同じビット長をもつように構成してもよいし、同様に、ビット列Ｂ１，・・・，Ｂｎが、いずれも同じビット長をもつように構成してもよい。この場合、実装が容易になるという効果を奏する。
【００２６】
図３は、ハッシュ値演算装置１００のハードウェア構成の一例を示す図である。
【００２７】
図３において、ハッシュ値演算装置１００は、コンピュータであり、ＬＣＤ９０１（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ９０６といったハードウェアデバイスを備えている。これらのハードウェアデバイスはケーブルや信号線で接続されている。ＬＣＤ９０１の代わりに、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）、あるいは、その他の表示装置が用いられてもよい。マウス９０３の代わりに、タッチパネル、タッチパッド、トラックボール、ペンタブレット、あるいは、その他のポインティングデバイスが用いられてもよい。
【００２８】
ハッシュ値演算装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）を備えている。ＣＰＵ９１１は、処理装置の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、ＬＣＤ９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ９０６、ＨＤＤ９２０（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）と接続され、これらのハードウェアデバイスを制御する。ＨＤＤ９２０の代わりに、フラッシュメモリ、光ディスク装置、メモリカードリーダライタ又はその他の記憶媒体が用いられてもよい。
【００２９】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、ＨＤＤ９２０は、不揮発性メモリの一例である。これらは、記憶装置の一例である。通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５は、入力装置の一例である。また、通信ボード９１５、ＬＣＤ９０１、プリンタ９０６は、出力装置の一例である。
【００３０】
通信ボード９１５は、ＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）等に接続されている。通信ボード９１５は、ＬＡＮに限らず、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ・Ｐｒｏｔｏｃｏｌ・Ｖｉｒｔｕａｌ・Ｐｒｉｖａｔｅ・Ｎｅｔｗｏｒｋ）、広域ＬＡＮ、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ・Ｔｒａｎｓｆｅｒ・Ｍｏｄｅ）ネットワークといったＷＡＮ（Ｗｉｄｅ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）、あるいは、インターネットに接続されていても構わない。ＬＡＮ、ＷＡＮ、インターネットは、ネットワークの一例である。
【００３１】
ＨＤＤ９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」として説明する機能を実行するプログラムが含まれている。プログラムは、ＣＰＵ９１１により読み出され実行される。ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（識別子）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として含まれている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶される。ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理（動作）に用いられる。抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３２】
本実施の形態の説明において用いるブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示す。データや信号は、ＲＡＭ９１４等のメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、ＨＤＤ９２０の磁気ディスク、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）、あるいは、その他の記録媒体に記録される。また、データや信号は、バス９１２、信号線、ケーブル、あるいは、その他の伝送媒体により伝送される。
【００３３】
本実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。即ち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアのみ、あるいは、素子、デバイス、基板、配線といったハードウェアのみで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアとハードウェアとの組み合わせ、あるいは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、フレキシブルディスク、コンパクトディスク、磁気ディスク、光ディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」としてコンピュータを機能させるものである。あるいは、プログラムは、本実施の形態の説明で述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００３４】
図４は、ハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を示すフローチャートである。
【００３５】
ステップＳ１０１（入力処理）において、入力部１０１は、ｍビットのメッセージＭを記憶装置や入力装置から入力する（例えば、ＲＡＭ９１４やＨＤＤ９２０から読み込んだり、通信ボード９１５によりネットワークから受信したり、キーボード９０２やマウス９０３を介してユーザから入力を受け付けたりする）。
【００３６】
ステップＳ１０２（パディング処理）において、パディング部１０２は、ｎを表すビット列Ｓのビット長をｑ（ｑはｑ＞ｌｏｇ２ｎとなる整数であり、例えば５５とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑを満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列Ｓを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ＝１｜｜０・・・０｜｜＜ｎ＞
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑであり、ｔ＝Σｍｉ−ｍ−ｑであるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００３７】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞
とする。
【００３８】
従来技術では、メッセージＭにパディングがなされたメッセージＭ´は、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜｜Ｍ｜＞であった。＜｜Ｍ｜＞を一般的な６４ビットの符号語であるとすると、従来技術では、最大２６４−１ビットのメッセージＭの入力を受け付けられることになる。一方、本実施の形態では、上記のように、メッセージＭにパディングがなされたメッセージＭ´は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞となる。ｎ個の演算器Ｃ１，・・・，Ｃｎに入力されるビット列Ｍ１，・・・，Ｍｎのビット長がいずれも一般的な５１２ビットに定められているとすると、＜ｎ＞が５５ビットの符号語であれば、ハッシュ値演算装置１００は、最大２６４−１ビットのメッセージＭの入力を受け付けられることになる。このように、本実施の形態によれば、メッセージＭのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることが可能となる。
【００３９】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数への入力値Ｍに対して、後述するハッシュ値導出関数に使われる圧縮関数の数を示す値ｎを求め、ハッシュ値導出関数の入力条件を満たしかつｎを含む値Ｍ´を出力するパディング関数の処理を実行する。パディング関数の処理では、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｎを表す例えば５５ビットの符号語を、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００４０】
ステップＳ１０３（分割処理）において、分割部１０３は、ステップＳ１０２で生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成する。そして、分割部１０３は、生成したビット列Ｍ１，・・・，Ｍｎを演算部１０４へ入力する。
【００４１】
ステップＳ１０４（演算処理）において、演算部１０４は、ステップＳ１０３におけるビット列Ｍ１，・・・，Ｍｎの入力を受け付ける。演算部１０４は、ビット列Ｍ１と予め定められた固定値であるＩＶとをビット列Ａ１として演算器Ｃ１へ入力する。演算器Ｃ１は、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算部１０４は、ビット列Ｍ２と演算器Ｃ１から出力されたビット列Ｂ１とをビット列Ａ２として演算器Ｃ２へ入力する。演算器Ｃ１と同様に、演算器Ｃ２は、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成し、出力する。これ以降、同様の演算手順が演算器Ｃｎ−１まで実行される。その後、演算部１０４は、ビット列Ｍｎと演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とをビット列Ａｎとして演算器Ｃｎへ入力する。演算器Ｃｎは、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、メッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力する。
【００４２】
上記のように、ステップＳ１０３及びＳ１０４では、分割部１０３及び演算部１０４が、前述したパディング関数の出力値Ｍ´を入力し、そのハッシュ値Ｈ（Ｍ´）を求めるハッシュ値導出関数の処理を実行し、その出力値Ｈ（Ｍ´）をハッシュ関数の出力値として出力する。
【００４３】
なお、図４ではパディング関数とハッシュ値導出関数を分けて記述しているが、これらは同時に行う場合が一般的である。即ち、２つの関数が１つになっており、ハッシュ値導出関数内でパディング値が計算に必要になった場合にパディング関数を呼び出して、パディング処理を行うという形態が実施可能である。例えば、上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞）をＭＤ構造（図２参照）に適用した場合、ハッシュ関数の入力値Ｍ＝（ｍ［１］，・・・，ｍ［ｘ］）に対して、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｍ［ｉ］）をｉ＝１，・・・，ｘ−１について計算する。ｉ＝ｎのときにパディング関数を呼び出しｍ´［ｘ］＝ｍ［ｘ］｜｜１｜｜０・・・０｜｜＜ｎ＞とし、ｃ［ｘ＋１］＝ｈ（ｃ［ｘ］，ｍ´［ｘ］）を計算し、ｃ［ｘ＋１］をハッシュ値として出力する。
【００４４】
ステップＳ１０５（出力処理）において、出力部１０５は、ステップＳ１０４で演算されたメッセージＭ´のハッシュ値Ｈ（Ｍ´）を記憶装置や出力装置へ出力する（例えば、ＲＡＭ９１４やＨＤＤ９２０に書き出したり、通信ボード９１５によりネットワークに送信したり、ＬＣＤ９０１で画面表示したり、プリンタ９０６で印刷したりする）。
【００４５】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００４６】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００４７】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００４８】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の３パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００４９】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００５０】
２．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠Ｂｂの場合（ここで、ＢａはＨ（Ｍａ）の中で用いる圧縮関数ｈの数、ＢｂはＨ（Ｍｂ）の中で用いる圧縮関数ｈの数とする）
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００５１】
３．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂの場合
Ｍａ、Ｍｂのパディング後の値をＭａ´、Ｍｂ´とする。即ち、Ｍａ´＝Ｍａ｜｜１０・・・０｜｜＜Ｂａ＞、Ｍｂ´＝Ｍｂ｜｜１０・・・０｜｜＜Ｂｂ＞となる。ここで、｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂなので、０をパディングする数が異なる。Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる最後の圧縮関数ｈの入力が異なりかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００５２】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００５３】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、任意の値Ｍを入力として受けたとき、その値のハッシュ関数の計算に必要な圧縮関数ｈの個数の情報を含む値ｎを生成し、Ｍにある方法を用いてｎを含む値に変換することを特徴とする。
【００５４】
また、上記ハッシュ関数演算装置は、さらに、Ｍ、ｎともに２進表現で用いることを特徴とする。
【００５５】
また、上記ハッシュ関数演算装置は、さらに、パディングされた値Ｍ´がＭ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞となることを特徴とする。
【００５６】
また、上記ハッシュ関数演算装置は、圧縮関数の入力長をａ（ａはａ＞１となる整数）、出力長をｂ（ｂはａ＞ｂ＞１となる整数）としたときに、パディングされた値Ｍ´の長さがａ−ｂの倍数となり、ｎの長さが固定長となることを特徴とする。
【００５７】
また、上記ハッシュ関数演算装置は、パディングにより加工された値Ｍ´で“０”をパディングする個数が最小となることを特徴とする。
【００５８】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００５９】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【００６０】
ステップＳ１０１（入力処理）については、実施の形態１と同様であるため、説明を省略する。
【００６１】
ステップＳ１０２（パディング処理）において、ｎ≦２ｑ（ｑはｑ＞０となる整数であり、例えば３２とする）の場合、パディング部１０２は、ｎを表すビット列Ｓのビット長をｑビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓと値が“０”（又は“１”）であるビットＤ０とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列ＳとビットＤ０とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ０＝１｜｜０・・・０｜｜＜ｎ＞｜｜０
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑ＋１であり、ｔ＝Σｍｉ−ｍ−ｑ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００６２】
一方、ステップＳ１０２（パディング処理）において、ｎ＞２ｑの場合、パディング部１０２は、ｎを表すビット列Ｓのビット長をｒ（ｒはｒ＞ｑとなる整数であり、例えば５５とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｒ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｒビットのビット列Ｓと値がビットＤ０と異なる（ビットＤ０が“０”であれば“１”）であるビットＤ１とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、ｎ≦２ｑの場合と同様に、パディング部１０２は、ビット列ＳとビットＤ１とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成することになる。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ１＝１｜｜０・・・０｜｜＜ｎ＞｜｜１
となる。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｒビット）の符号語を表記したものである。ｐ＝ｔ＋ｒ＋１であり、ｔ＝Σｍｉ−ｍ−ｒ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００６３】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０（ｎ≦２ｑの場合）
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１（ｎ＞２ｑの場合）
とする。なお、前述したように、ｎ≦２ｑの場合、“＜ｎ＞”のビット長はｑであり、ｎ＞２ｑの場合、“＜ｎ＞”のビット長はｒ＞ｑを満たすｒである。
【００６４】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数の入力値Ｍに対して、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｎを表す例えば３２ビット又は５５ビットの符号語と“０”又は“１”を（ｎ≦２３２ならばｎを表す符号語は３２ビット、最後のビットは“０”となり、ｎ＞２３２ならばｎを表す符号語は５５ビット、最後のビットは“１”となる）、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。Ｍ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜０またはＭ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜１。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００６５】
ステップＳ１０３（分割処理）以降については、実施の形態１と同様であるため、説明を省略する。
【００６６】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００６７】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０、又は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００６８】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００６９】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の５パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００７０】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００７１】
２．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ≦２ｑかつＢｂ＞２ｑの場合（ここで、ＢａはＨ（Ｍａ）の中で用いる圧縮関数ｈの数、ＢｂはＨ（Ｍｂ）の中で用いる圧縮関数ｈの数とする）
最後のチェックビットが異なるので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７２】
３．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ≦２ｑかつＢｂ≦２ｑの場合
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７３】
４．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ＞２ｑかつＢｂ＞２ｑの場合
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７４】
５．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂの場合
Ｍａ、Ｍｂのパディング後の値をＭａ´、Ｍｂ´とする。即ち、Ｍａ´＝Ｍａ｜｜１０・・・０｜｜＜Ｂａ＞｜｜ｄ、Ｍｂ´＝Ｍｂ｜｜１０・・・０｜｜＜Ｂｂ＞｜｜ｄとなる（ｄはＢａ、Ｂｂの長さによって異なってくる）。ここで、｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂなので、０をパディングする数が異なる。Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる最後の圧縮関数ｈの入力が異なりかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７５】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００７６】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、実施の形態１と異なり、ｑをある整数としたときに、ｎが２ｑ以下ならば、＜ｎ＞の長さをｑビットとし、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０とし、ｎが２ｑより上ならば＜ｎ＞の長さをｑビットより長いｒビットとし、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１とすることを特徴とする。
【００７７】
また、上記ハッシュ関数演算装置は、“０”をパディングする個数が最小となることを特徴とする。
【００７８】
実施の形態３．
本実施の形態について、主に実施の形態１及び２との差異を説明する。
【００７９】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１及び２のものと同様である。
【００８０】
本実施の形態では、パディング部１０２は、ｎではなくｍを表すビット列Ｓと所定のビットパターンＴと所定のビットＤ０又はＤ１とを組み合わせてビット列Ｐを生成する。そして、パディング部１０２は、生成したビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加してメッセージＭ´を生成する。実施の形態１及び２と同様に、ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じてパディング部１０２により設定される。
【００８１】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【００８２】
ステップＳ１０１（入力処理）については、実施の形態１及び２と同様であるため、説明を省略する。
【００８３】
ステップＳ１０２（パディング処理）において、ｍ≦２ｑ（ｑはｑ＞０となる整数であり、例えば３２とする）の場合、パディング部１０２は、ｍを表すビット列Ｓのビット長をｑビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓと値が“０”（又は“１”）であるビットＤ０とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列ＳとビットＤ０とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ０＝１｜｜０・・・０｜｜＜ｍ＞｜｜０
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｍ＞”はｍを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑ＋１であり、ｔ＝Σｍｉ−ｍ−ｑ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００８４】
一方、ステップＳ１０２（パディング処理）において、ｍ＞２ｑの場合、パディング部１０２は、ｍを表すビット列Ｓのビット長をｒ（ｒはｒ＞ｑとなる整数であり、例えば６３とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｒ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｒビットのビット列Ｓと値がビットＤ０と異なる（ビットＤ０が“０”であれば“１”）であるビットＤ１とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、ｍ≦２ｑの場合と同様に、パディング部１０２は、ビット列ＳとビットＤ１とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成することになる。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ１＝１｜｜０・・・０｜｜＜ｍ＞｜｜１
となる。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｍ＞”はｍを表す固定長（ここではｒビット）の符号語を表記したものである。ｐ＝ｔ＋ｒ＋１であり、ｔ＝Σｍｉ−ｍ−ｒ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００８５】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜０（ｍ≦２ｑの場合）
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜１（ｍ＞２ｑの場合）
とする。なお、前述したように、ｍ≦２ｑの場合、“＜ｍ＞”のビット長はｑであり、ｍ＞２ｑの場合、“＜ｍ＞”のビット長はｒ＞ｑを満たすｒである。
【００８６】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数の入力値Ｍに対して、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｍを表す例えば３２ビット又は６３ビットの符号語と“０”又は“１”を（ｍ≦２３２ならばｍを表す符号語は３２ビット、最後のビットは“０”となり、ｍ＞２３２ならばｍを表す符号語は６３ビット、最後のビットは“１”となる）、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。Ｍ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜０またはＭ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜１。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００８７】
ステップＳ１０３（分割処理）以降については、実施の形態１及び２と同様であるため、説明を省略する。
【００８８】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００８９】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜０、又は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜１）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００９０】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００９１】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の４パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００９２】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００９３】
２．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜≦２ｑかつ｜Ｍａ｜＞２ｑの場合
最後のチェックビットが異なるので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９４】
３．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜≦２ｑかつ｜Ｍａ｜≦２ｑの場合
Ｍａ´＝Ｍａ｜｜１｜｜０・・・０｜｜＜｜Ｍａ｜＞｜｜０、Ｍｂ´＝Ｍｂ｜｜１｜｜０・・・０｜｜＜｜Ｍｂ｜＞｜｜０とする。＜｜Ｍａ｜＞と＜｜Ｍｂ｜＞のビット数は同じなので、ｓＭＤの証明と同様に、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９５】
４．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜＞２ｑかつ｜Ｍａ｜＞２ｑの場合
Ｍａ´＝Ｍａ｜｜１｜｜０・・・０｜｜＜｜Ｍａ｜＞｜｜１、Ｍｂ´＝Ｍｂ｜｜１｜｜０・・・０｜｜＜｜Ｍｂ｜＞｜｜１とする。＜｜Ｍａ｜＞と＜｜Ｍｂ｜＞のビット数は同じなので、ｓＭＤの証明と同様に、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９６】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００９７】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、実施の形態１及び２と異なり、任意の値Ｍを入力として受けたとき、Ｍのビット長がある値ｑに対して、２ｑ以下ならば、Ｍをｑビットの、Ｍのビット長情報が入った符号語＜Ｍ＞を含む値に変換し、２ｑより大きいならばｑビットより長いｒビットの、Ｍのビット長情報が入った符号語＜Ｍ＞を含む値に変換することを特徴とする。
【００９８】
また、上記ハッシュ関数演算装置は、任意の値Ｍを入力として受けたとき、Ｍのビット長が２ｑ以下ならば、ｑビットの、Ｍのビット長情報が入った符号語＜Ｍ＞に対して、ＭをＭ｜｜１｜｜０・・・０｜｜＜Ｍ＞｜｜０に変換し、２ｑより大きいならばｑビットより長いｒビットの、Ｍのビット長情報が入った符号語＜Ｍ＞に対して、ＭをＭ｜｜１｜｜０・・・０｜｜＜Ｍ＞｜｜１に変換することを特徴とする。
【００９９】
また、上記ハッシュ関数演算装置は、“０”をパディングする個数が最小となることを特徴とする。
【０１００】
実施の形態４．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１０１】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１０２】
図５は、演算部１０４の構成の一例を示すブロック図である。
【０１０３】
図５において、演算器Ｃ１，・・・，Ｃｎ−１については、実施の形態１から３までと同様である。本実施の形態では、演算器Ｃｎは、演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とパディング部１０２により生成されたビット列Ｍｎとに加えて、所定の固定値であるビット列Ｖｎの入力を受け付ける。演算器Ｃｎは、ビット列Ｂｎ−１とビット列Ｍｎとビット列Ｖｎとからなるビット列Ａｎが入力されると、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【０１０４】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１０５】
実施の形態５．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１０６】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１０７】
図６は、演算部１０４の構成の一例を示すブロック図である。
【０１０８】
図６において、演算器Ｃ１，・・・，Ｃｎ−１については、実施の形態１から３までと同様である。本実施の形態では、演算器Ｃｎは、演算器Ｃｎ−１から出力されたビット列Ｂｎ−１に対して１対１写像の置換πを行ってから、当該置換πの結果とパディング部１０２により生成されたビット列Ｍｎとを圧縮関数ｈに入力する。そして、演算器Ｃｎは、ビット列Ｂｎ−１の置換πの結果とビット列Ｍｎとからなるデータに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【０１０９】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１１０】
実施の形態６．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１１１】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１１２】
図７は、演算部１０４の構成の一例を示すブロック図である。
【０１１３】
図７において、演算部１０４が備えるｎ個の演算器Ｃ１，・・・，Ｃｎは、それぞれ圧縮関数の一例としてブロック暗号Ｅの演算を行う回路（ハードウェアで実装される場合）、関数（ソフトウェアで実装される場合）等である（ハードウェアとソフトウェアとの組み合わせで実装されてもよい）。
【０１１４】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１１５】
実施の形態７．
本実施の形態について、主に実施の形態６との差異を説明する。
【０１１６】
図８は、演算部１０４の構成の一例を示すブロック図である。
【０１１７】
図８において、それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対してブロック暗号Ｅの演算を行った後、当該演算の結果とビット列Ａｉのうちビット列Ｍｉ以外のデータとの排他的論理和（ＸＯＲ）を演算する。そして、演算器Ｃｉは、当該ＸＯＲの演算結果をビット列Ｂｉとして出力する。
【０１１８】
例えば、演算器Ｃ１は、所定の固定値であるＩＶとパディング部１０２により生成されたビット列Ｍ１とからなるビット列Ａ１が入力されると、ビット列Ａ１に対してブロック暗号Ｅの演算を行った後、当該演算の結果とＩＶとのＸＯＲを演算し、その結果をビット列Ｂ１として出力する。演算器Ｃ２は、演算器Ｃ１から出力されたビット列Ｂ１とパディング部１０２により生成されたビット列Ｍ２とからなるビット列Ａ２が入力されると、ビット列Ａ２に対してブロック暗号Ｅの演算を行った後、当該演算の結果とビット列Ｂ１とのＸＯＲを演算し、その結果をビット列Ｂ２として生成する。演算器Ｃ３以降については、演算器Ｃ２と同様である。
【０１１９】
上記のような構成によっても、実施の形態６と同様の効果が得られる。
【０１２０】
実施の形態８．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１２１】
図９は、本実施の形態に係るハッシュ値演算装置１００の構成を示すブロック図である。
【０１２２】
図９において、演算部１０４のｎ個の演算器Ｃ１，・・・，Ｃｎは、並列に接続されている。
【０１２３】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【０１２４】
ステップＳ１０３（分割処理）までについては、実施の形態１から３までと同様であるため、説明を省略する。
【０１２５】
ステップＳ１０４（演算処理）において、演算部１０４は、ステップＳ１０３におけるビット列Ｍ１，・・・，Ｍｎの入力を受け付ける。演算部１０４は、ビット列Ｍ１と予め定められた固定値であるＩＶ（図９には示していないが、図２等と同様である）とをビット列Ａ１として演算器Ｃ１へ入力する。演算器Ｃ１は、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算部１０４は、ビット列Ｍ２と予め定められた固定値であるＩＶ（演算器Ｃ１へ入力されるものとは異なる値でもよい）とをビット列Ａ２として演算器Ｃ２へ入力する。演算器Ｃ１と同様に、演算器Ｃ２は、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成し、出力する。演算部１０４は、ビット列Ｍ３と演算器Ｃ１から出力されたビット列Ｂ１とをビット列Ａ３として演算器Ｃ３へ入力する。演算器Ｃ１と同様に、演算器Ｃ３は、ビット列Ａ３に対して圧縮関数ｈの演算を行ってビット列Ｂ３を生成し、出力する。演算部１０４は、ビット列Ｍ４と演算器Ｃ２から出力されたビット列Ｂ２とをビット列Ａ４として演算器Ｃ４へ入力する。演算器Ｃ２と同様に、演算器Ｃ４は、ビット列Ａ４に対して圧縮関数ｈの演算を行ってビット列Ｂ４を生成し、出力する。これ以降、同様の演算手順が演算器Ｃｎ−１まで実行される。その後、演算部１０４は、ビット列Ｍｎと演算器Ｃｎ−２から出力されたビット列Ｂｎ−２と演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とをビット列Ａｎとして演算器Ｃｎへ入力する。演算器Ｃｎは、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、メッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力する。
【０１２６】
ステップＳ１０５（出力処理）については、実施の形態１から３までと同様であるため、説明を省略する。
【０１２７】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１２８】
以上、本発明の実施の形態について説明したが、これらのうち、２つ以上の実施の形態を組み合わせて実施しても構わない。あるいは、これらのうち、１つの実施の形態を部分的に実施しても構わない。あるいは、これらのうち、２つ以上の実施の形態を部分的に組み合わせて実施しても構わない。
【図面の簡単な説明】
【０１２９】
【図１】実施の形態１に係るハッシュ値演算装置の構成を示すブロック図である。
【図２】実施の形態１に係る演算部の構成の一例を示すブロック図である。
【図３】実施の形態１に係るハッシュ値演算装置のハードウェア構成の一例を示す図である。
【図４】実施の形態１に係るハッシュ値演算装置の動作を示すフローチャートである。
【図５】実施の形態４に係る演算部の構成の一例を示すブロック図である。
【図６】実施の形態５に係る演算部の構成の一例を示すブロック図である。
【図７】実施の形態６に係る演算部の構成の一例を示すブロック図である。
【図８】実施の形態７に係る演算部の構成の一例を示すブロック図である。
【図９】実施の形態８に係るハッシュ値演算装置の構成を示すブロック図である。
【符号の説明】
【０１３０】
１００ ハッシュ値演算装置、１０１ 入力部、１０２ パディング部、１０３ 分割部、１０４ 演算部、１０５ 出力部、９０１ ＬＣＤ、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信ボード、９２０ ＨＤＤ、９２１ オペレーティングシステム、９２２ ウィンドウシステム、９２３ プログラム群、９２４ ファイル群。
【技術分野】
【０００１】
本発明は、ハッシュ値演算装置及びハッシュ値演算方法及びハッシュ値演算プログラムに関するものである。本発明は、特に、ハッシュ関数の入力値を加工する方式（ハッシュ関数パディング方式）に関するものである。
【背景技術】
【０００２】
ハッシュ関数は入力長が任意で、出力長が固定の関数である。ハッシュ関数Ｈには衝突困難性が要求される。衝突困難性とは、Ｈ（Ｍ）＝Ｈ（Ｍ´）となる異なる２つの値Ｍ、Ｍ´を求めることは難しいという性質である。
【０００３】
ハッシュ関数の入力長は任意であるが、ハッシュ関数の中ではある長さの倍数に変換してから用いられる。通常の変換方式は入力値の後ろに“１”と“０・・・０”（“０”のビット列）と６４ビットの入力長の符号語が付加されるパディング処理が一般的である（例えば、非特許文献１参照）。
【０００４】
ハッシュ関数は小さな部品を組み合わせて構成される。この部品とはブロック暗号や圧縮関数と呼ばれる、入力長、出力長が固定された関数である。
【０００５】
ハッシュ関数の構成法にｓｔｒｅｎｇｔｈ・Ｍｅｒｋｌｅ−Ｄａｍｇａａｒｄ（ｓＭＤ）構造がある。ここで、圧縮関数の入力長をａビット、出力長をｂビットとおく。ｂビットの固定値をＩＶ（Ｉｎｉｔｉａｌｉｚａｔｉｏｎ・Ｖｅｃｔｏｒ）とおく。ＭＤ構造への入力をＭとおく。中身の処理では、まずＭから、ビット長がａ−ｂビットの倍数となるＭ´を、Ｍの後ろに“１”と“０・・・０”（“０”のビット列）とＭのビット長を表す６４ビットの符号語を付加することにより生成する。即ち、
Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜｜Ｍ｜＞
とする。なお、“｜｜”はビット（列）の連結を表記したものである。“｜Ｍ｜”はＭのビット長を表記したものである。“＜｜Ｍ｜＞”はＭのビット長を表す固定長（ここでは６４ビット）の符号語を表記したものである。Ｍに付加する“０・・・０”は、０を付加する個数が最小となるようにする。次にＭ´をａ−ｂビットごとに分割する。即ち、
Ｍ´＝（ｍ［１］，ｍ［２］，・・・，ｍ［ｎ］）
とする。ｃ［１］＝ＩＶとおき、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｍ［ｉ］）をｉ＝１，・・・，ｎ（ｎはｎ＞１となる整数）について計算する。なお、ｈ（ｃ［ｉ］，ｍ［ｉ］）はｃ［ｉ］を入力、ｍ［ｉ］を出力とする圧縮関数を表記したものである。最後にｃ［ｎ＋１］をハッシュ関数の出力値とする。
【０００６】
ハッシュ関数の入力値の後ろに“１”を付加せず、“０・・・０”（“０”のビット列）と６４ビットの入力長の符号語のみを付加するパディング方式もある（例えば、非特許文献２参照）。
【非特許文献１】Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， “Ｓｅｃｕｒｅ Ｈａｓｈ Ｓｔａｎｄａｒｄ （ＳＨＳ），” Ｆｅｄｅｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄｓ Ｐｕｂｌｉｃａｔｉｏｎ １８０−２， Ａｕｇｕｓｔ １， ２００２
【非特許文献２】Ｄｏｎ Ｂ． Ｊｏｈｎｓｏｎ， Ｅｎｔｒｕｓｔ ＣｙｇｎａＣｏｍ， “Ｉｍｐｒｏｖｉｎｇ Ｈａｓｈ Ｆｕｎｃｔｉｏｎ Ｐａｄｄｉｎｇ，” Ｆｉｒｓｔ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｓｈ Ｗｏｒｋｓｈｏｐ， Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎｏｖｅｍｂｅｒ １， ２００５
【発明の開示】
【発明が解決しようとする課題】
【０００７】
非特許文献２の方式では、一般的なパディング方式（Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｍ＞）よりもパディングされたデータの長さが短くなるものの、１ビットしか短くできないため、ハッシュ関数の計算量が依然多いという課題があった。
【０００８】
本発明は、例えば、ハッシュ関数に入力するメッセージのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一の態様に係るハッシュ値演算装置は、
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
メッセージＭを入力する入力部と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とする。
【発明の効果】
【００１０】
本発明の一の態様によれば、ｎ個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉへの入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置において、パディング部が、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成することにより、メッセージＭのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の実施の形態について、図を用いて説明する。
【００１２】
実施の形態１．
図１は、本実施の形態に係るハッシュ値演算装置１００の構成を示すブロック図である。
【００１３】
図１において、ハッシュ値演算装置１００は、入力部１０１、パディング部１０２、分割部１０３、演算部１０４、出力部１０５を備える。
【００１４】
演算部１０４は、ｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有する。演算部１０４は、それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力としてビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値Ｈ（Ｍ´）を、上記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する。ビット列Ｍｉは演算器Ｃｉごとに予め定められたビット長をもつ。以下では、ビット列Ｍｉのビット長をｍｉ（ｍｉはｍｉ＞０となる整数）と表記する。
【００１５】
入力部１０１は、ハッシュ関数の入力値であるメッセージＭを入力する。メッセージＭは任意のビット長をもつ。以下では、メッセージＭのビット長をｍ（ｍはｍ＞１となる整数）と表記する。
【００１６】
パディング部１０２は、入力部１０１により入力されたメッセージＭに対し、所定のパディングを行って上記メッセージＭ´を生成する。具体的には、パディング部１０２は、ｎを表すビット列Ｓと所定のビットパターンＴとを組み合わせて（さらに、他のビットあるいはビット列と組み合わせてもよい）ビット列Ｐを生成する。そして、パディング部１０２は、生成したビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加して上記メッセージＭ´を生成する。ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じてパディング部１０２により設定される。以下では、ビット列Ｐのビット長をｐ（ｐはｐ＞０となる整数）と表記する。なお、ｐは可変であるが、メッセージＭ´のビット長はΣｍｉであるから、常にｐ＝Σｍｉ−ｍが成り立つ。
【００１７】
本実施の形態では、パディング部１０２は、ビットパターンＴとして、“１０・・・０”（開始ビットが“１”、それ以外がオール“０”）を生成するものとする。なお、パディング部１０２は、これ以外にも、“０・・・０”（オール“０”）、“１・・・１”（オール“１”）、“０１・・・１”（開始ビットが“０”、それ以外がオール“１”）といった任意のパターンを用いることができるが、ハッシュ関数の衝突困難性を高めるため、“１０”又は“０１”で始まるものを用いることが望ましい。どのようなパターンを用いるかは予め定義されており、パディング部１０２は、その定義に従ってビットパターンＴを生成する。予め複数のパターンが定義されている場合には、パディング部１０２が、それらのパターンのうち、外部から指定されたものを用いるようにしてもよいし、用途等に応じていずれかのパターンを選択し、選択したものを用いるようにしてもよい。
【００１８】
本実施の形態では、パディング部１０２は、ビット列ＰをメッセージＭの後（所定の位置の一例）に連結してメッセージＭ´を生成するものとする。なお、パディング部１０２は、ビット列ＰをメッセージＭの先頭に追加して（即ち、ビット列Ｐの後にメッセージＭを連結して）メッセージＭ´を生成してもよいし、ビット列ＰをメッセージＭの所定の位置に挿入してメッセージＭ´を生成してもよい。どの位置にビット列Ｐを追加するかは予め定義されており、パディング部１０２は、その定義に従ってビット列ＰをメッセージＭに追加する。予め複数の位置が定義されている場合には、パディング部１０２が、外部から指定された位置にビット列Ｐを追加するようにしてもよいし、用途等に応じていずれかの位置を選択し、選択した位置にビット列Ｐを追加するようにしてもよい。
【００１９】
分割部１０３は、パディング部１０２により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成する。そして、分割部１０３は、生成したビット列Ｍ１，・・・，Ｍｎを演算部１０４へ入力して演算部１０４にメッセージＭ´のハッシュ値Ｈ（Ｍ´）を演算させる。
【００２０】
出力部１０５は、演算部１０４により演算されたメッセージＭ´のハッシュ値Ｈ（Ｍ´）を出力する。
【００２１】
図２は、演算部１０４の構成の一例を示すブロック図である。
【００２２】
図２において、演算部１０４が備えるｎ個の演算器Ｃ１，・・・，Ｃｎは、それぞれ圧縮関数ｈの演算を行う回路（ハードウェアで実装される場合）、関数（ソフトウェアで実装される場合）等である（ハードウェアとソフトウェアとの組み合わせで実装されてもよい）。なお、演算器Ｃ１，・・・，Ｃｎの個数ｎは、入力部１０１により入力されるメッセージＭのビット長ｍに応じて決まるものである。単純な例として、ビット列Ｍ１，・・・，Ｍｎが、いずれも同じビット長をもつとすると、そのビット長でｍを割ったときの商がｎとなる。なお、このときの余りがパディング部１０２により生成されるビット列Ｐのビット長ｐとなる。以上より、演算部１０４は、実際には所定数の演算器を備えておき、その中から、メッセージＭのビット長ｍに応じてｎ個の演算器Ｃ１，・・・，Ｃｎを選択して用いることが望ましい。
【００２３】
それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対して圧縮関数ｈの演算を行ってビット列Ｂｉを生成する。ｉ＜ｎの場合、演算器Ｃｉは、生成したビット列Ｂｉを他の演算器Ｃｊ（ｊはｉ＜ｊ≦ｎとなる整数）へビット列Ａｊの一部として入力する。図１に示したように、本実施の形態では、演算部１０４のｎ個の演算器Ｃ１，・・・，Ｃｎは、順番に直列に接続されているものとする。そして、それぞれの演算器Ｃｉは、ｉ＜ｎの場合（即ち、演算器Ｃ１，・・・，Ｃｎ−１は）、生成したビット列Ｂｉを他の演算器Ｃｊである演算器Ｃｉ＋１へビット列Ａｉ＋１の一部として入力するものとする。演算器Ｃｎは、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【００２４】
例えば、演算器Ｃ１は、所定の固定値であるＩＶとパディング部１０２により生成されたビット列Ｍ１とからなるビット列Ａ１が入力されると、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算器Ｃ２は、演算器Ｃ１から出力されたビット列Ｂ１とパディング部１０２により生成されたビット列Ｍ２とからなるビット列Ａ２が入力されると、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成する。演算器Ｃ３以降については、演算器Ｃ２と同様である。この例では、出力部１０５は、演算器Ｃｎにより生成されたビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力することになる。
【００２５】
他の実施の形態については後述するが、演算部１０４の構成としては、ハッシュ関数の演算が可能なものであれば、図２に示したもの以外にも様々な構成を採用することができる。また、例えば、ビット列Ｍ１，・・・，Ｍｎが、いずれも同じビット長をもち、さらに、ビット列Ａ１，・・・，Ａｎが、いずれも同じビット長をもつように構成してもよいし、同様に、ビット列Ｂ１，・・・，Ｂｎが、いずれも同じビット長をもつように構成してもよい。この場合、実装が容易になるという効果を奏する。
【００２６】
図３は、ハッシュ値演算装置１００のハードウェア構成の一例を示す図である。
【００２７】
図３において、ハッシュ値演算装置１００は、コンピュータであり、ＬＣＤ９０１（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ９０６といったハードウェアデバイスを備えている。これらのハードウェアデバイスはケーブルや信号線で接続されている。ＬＣＤ９０１の代わりに、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）、あるいは、その他の表示装置が用いられてもよい。マウス９０３の代わりに、タッチパネル、タッチパッド、トラックボール、ペンタブレット、あるいは、その他のポインティングデバイスが用いられてもよい。
【００２８】
ハッシュ値演算装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）を備えている。ＣＰＵ９１１は、処理装置の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、ＬＣＤ９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ９０６、ＨＤＤ９２０（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）と接続され、これらのハードウェアデバイスを制御する。ＨＤＤ９２０の代わりに、フラッシュメモリ、光ディスク装置、メモリカードリーダライタ又はその他の記憶媒体が用いられてもよい。
【００２９】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、ＨＤＤ９２０は、不揮発性メモリの一例である。これらは、記憶装置の一例である。通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５は、入力装置の一例である。また、通信ボード９１５、ＬＣＤ９０１、プリンタ９０６は、出力装置の一例である。
【００３０】
通信ボード９１５は、ＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）等に接続されている。通信ボード９１５は、ＬＡＮに限らず、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ・Ｐｒｏｔｏｃｏｌ・Ｖｉｒｔｕａｌ・Ｐｒｉｖａｔｅ・Ｎｅｔｗｏｒｋ）、広域ＬＡＮ、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ・Ｔｒａｎｓｆｅｒ・Ｍｏｄｅ）ネットワークといったＷＡＮ（Ｗｉｄｅ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）、あるいは、インターネットに接続されていても構わない。ＬＡＮ、ＷＡＮ、インターネットは、ネットワークの一例である。
【００３１】
ＨＤＤ９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」として説明する機能を実行するプログラムが含まれている。プログラムは、ＣＰＵ９１１により読み出され実行される。ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（識別子）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として含まれている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶される。ＲＡＭ９１４やＨＤＤ９２０等の記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理（動作）に用いられる。抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３２】
本実施の形態の説明において用いるブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示す。データや信号は、ＲＡＭ９１４等のメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、ＨＤＤ９２０の磁気ディスク、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）、あるいは、その他の記録媒体に記録される。また、データや信号は、バス９１２、信号線、ケーブル、あるいは、その他の伝送媒体により伝送される。
【００３３】
本実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。即ち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアのみ、あるいは、素子、デバイス、基板、配線といったハードウェアのみで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアとハードウェアとの組み合わせ、あるいは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、フレキシブルディスク、コンパクトディスク、磁気ディスク、光ディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」としてコンピュータを機能させるものである。あるいは、プログラムは、本実施の形態の説明で述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００３４】
図４は、ハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を示すフローチャートである。
【００３５】
ステップＳ１０１（入力処理）において、入力部１０１は、ｍビットのメッセージＭを記憶装置や入力装置から入力する（例えば、ＲＡＭ９１４やＨＤＤ９２０から読み込んだり、通信ボード９１５によりネットワークから受信したり、キーボード９０２やマウス９０３を介してユーザから入力を受け付けたりする）。
【００３６】
ステップＳ１０２（パディング処理）において、パディング部１０２は、ｎを表すビット列Ｓのビット長をｑ（ｑはｑ＞ｌｏｇ２ｎとなる整数であり、例えば５５とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑを満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列Ｓを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ＝１｜｜０・・・０｜｜＜ｎ＞
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑであり、ｔ＝Σｍｉ−ｍ−ｑであるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００３７】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞
とする。
【００３８】
従来技術では、メッセージＭにパディングがなされたメッセージＭ´は、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜｜Ｍ｜＞であった。＜｜Ｍ｜＞を一般的な６４ビットの符号語であるとすると、従来技術では、最大２６４−１ビットのメッセージＭの入力を受け付けられることになる。一方、本実施の形態では、上記のように、メッセージＭにパディングがなされたメッセージＭ´は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞となる。ｎ個の演算器Ｃ１，・・・，Ｃｎに入力されるビット列Ｍ１，・・・，Ｍｎのビット長がいずれも一般的な５１２ビットに定められているとすると、＜ｎ＞が５５ビットの符号語であれば、ハッシュ値演算装置１００は、最大２６４−１ビットのメッセージＭの入力を受け付けられることになる。このように、本実施の形態によれば、メッセージＭのパディング後の長さを短くして、ハッシュ関数の計算量を少なくすることが可能となる。
【００３９】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数への入力値Ｍに対して、後述するハッシュ値導出関数に使われる圧縮関数の数を示す値ｎを求め、ハッシュ値導出関数の入力条件を満たしかつｎを含む値Ｍ´を出力するパディング関数の処理を実行する。パディング関数の処理では、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｎを表す例えば５５ビットの符号語を、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００４０】
ステップＳ１０３（分割処理）において、分割部１０３は、ステップＳ１０２で生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成する。そして、分割部１０３は、生成したビット列Ｍ１，・・・，Ｍｎを演算部１０４へ入力する。
【００４１】
ステップＳ１０４（演算処理）において、演算部１０４は、ステップＳ１０３におけるビット列Ｍ１，・・・，Ｍｎの入力を受け付ける。演算部１０４は、ビット列Ｍ１と予め定められた固定値であるＩＶとをビット列Ａ１として演算器Ｃ１へ入力する。演算器Ｃ１は、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算部１０４は、ビット列Ｍ２と演算器Ｃ１から出力されたビット列Ｂ１とをビット列Ａ２として演算器Ｃ２へ入力する。演算器Ｃ１と同様に、演算器Ｃ２は、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成し、出力する。これ以降、同様の演算手順が演算器Ｃｎ−１まで実行される。その後、演算部１０４は、ビット列Ｍｎと演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とをビット列Ａｎとして演算器Ｃｎへ入力する。演算器Ｃｎは、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、メッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力する。
【００４２】
上記のように、ステップＳ１０３及びＳ１０４では、分割部１０３及び演算部１０４が、前述したパディング関数の出力値Ｍ´を入力し、そのハッシュ値Ｈ（Ｍ´）を求めるハッシュ値導出関数の処理を実行し、その出力値Ｈ（Ｍ´）をハッシュ関数の出力値として出力する。
【００４３】
なお、図４ではパディング関数とハッシュ値導出関数を分けて記述しているが、これらは同時に行う場合が一般的である。即ち、２つの関数が１つになっており、ハッシュ値導出関数内でパディング値が計算に必要になった場合にパディング関数を呼び出して、パディング処理を行うという形態が実施可能である。例えば、上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞）をＭＤ構造（図２参照）に適用した場合、ハッシュ関数の入力値Ｍ＝（ｍ［１］，・・・，ｍ［ｘ］）に対して、ｃ［ｉ＋１］＝ｈ（ｃ［ｉ］，ｍ［ｉ］）をｉ＝１，・・・，ｘ−１について計算する。ｉ＝ｎのときにパディング関数を呼び出しｍ´［ｘ］＝ｍ［ｘ］｜｜１｜｜０・・・０｜｜＜ｎ＞とし、ｃ［ｘ＋１］＝ｈ（ｃ［ｘ］，ｍ´［ｘ］）を計算し、ｃ［ｘ＋１］をハッシュ値として出力する。
【００４４】
ステップＳ１０５（出力処理）において、出力部１０５は、ステップＳ１０４で演算されたメッセージＭ´のハッシュ値Ｈ（Ｍ´）を記憶装置や出力装置へ出力する（例えば、ＲＡＭ９１４やＨＤＤ９２０に書き出したり、通信ボード９１５によりネットワークに送信したり、ＬＣＤ９０１で画面表示したり、プリンタ９０６で印刷したりする）。
【００４５】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００４６】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００４７】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００４８】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の３パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００４９】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００５０】
２．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠Ｂｂの場合（ここで、ＢａはＨ（Ｍａ）の中で用いる圧縮関数ｈの数、ＢｂはＨ（Ｍｂ）の中で用いる圧縮関数ｈの数とする）
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００５１】
３．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂの場合
Ｍａ、Ｍｂのパディング後の値をＭａ´、Ｍｂ´とする。即ち、Ｍａ´＝Ｍａ｜｜１０・・・０｜｜＜Ｂａ＞、Ｍｂ´＝Ｍｂ｜｜１０・・・０｜｜＜Ｂｂ＞となる。ここで、｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂなので、０をパディングする数が異なる。Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる最後の圧縮関数ｈの入力が異なりかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００５２】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００５３】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、任意の値Ｍを入力として受けたとき、その値のハッシュ関数の計算に必要な圧縮関数ｈの個数の情報を含む値ｎを生成し、Ｍにある方法を用いてｎを含む値に変換することを特徴とする。
【００５４】
また、上記ハッシュ関数演算装置は、さらに、Ｍ、ｎともに２進表現で用いることを特徴とする。
【００５５】
また、上記ハッシュ関数演算装置は、さらに、パディングされた値Ｍ´がＭ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞となることを特徴とする。
【００５６】
また、上記ハッシュ関数演算装置は、圧縮関数の入力長をａ（ａはａ＞１となる整数）、出力長をｂ（ｂはａ＞ｂ＞１となる整数）としたときに、パディングされた値Ｍ´の長さがａ−ｂの倍数となり、ｎの長さが固定長となることを特徴とする。
【００５７】
また、上記ハッシュ関数演算装置は、パディングにより加工された値Ｍ´で“０”をパディングする個数が最小となることを特徴とする。
【００５８】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００５９】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【００６０】
ステップＳ１０１（入力処理）については、実施の形態１と同様であるため、説明を省略する。
【００６１】
ステップＳ１０２（パディング処理）において、ｎ≦２ｑ（ｑはｑ＞０となる整数であり、例えば３２とする）の場合、パディング部１０２は、ｎを表すビット列Ｓのビット長をｑビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓと値が“０”（又は“１”）であるビットＤ０とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列ＳとビットＤ０とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ０＝１｜｜０・・・０｜｜＜ｎ＞｜｜０
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑ＋１であり、ｔ＝Σｍｉ−ｍ−ｑ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００６２】
一方、ステップＳ１０２（パディング処理）において、ｎ＞２ｑの場合、パディング部１０２は、ｎを表すビット列Ｓのビット長をｒ（ｒはｒ＞ｑとなる整数であり、例えば５５とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｒ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｒビットのビット列Ｓと値がビットＤ０と異なる（ビットＤ０が“０”であれば“１”）であるビットＤ１とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、ｎ≦２ｑの場合と同様に、パディング部１０２は、ビット列ＳとビットＤ１とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成することになる。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ１＝１｜｜０・・・０｜｜＜ｎ＞｜｜１
となる。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｎ＞”はｎを表す固定長（ここではｒビット）の符号語を表記したものである。ｐ＝ｔ＋ｒ＋１であり、ｔ＝Σｍｉ−ｍ−ｒ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００６３】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０（ｎ≦２ｑの場合）
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１（ｎ＞２ｑの場合）
とする。なお、前述したように、ｎ≦２ｑの場合、“＜ｎ＞”のビット長はｑであり、ｎ＞２ｑの場合、“＜ｎ＞”のビット長はｒ＞ｑを満たすｒである。
【００６４】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数の入力値Ｍに対して、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｎを表す例えば３２ビット又は５５ビットの符号語と“０”又は“１”を（ｎ≦２３２ならばｎを表す符号語は３２ビット、最後のビットは“０”となり、ｎ＞２３２ならばｎを表す符号語は５５ビット、最後のビットは“１”となる）、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。Ｍ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜０またはＭ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜１。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００６５】
ステップＳ１０３（分割処理）以降については、実施の形態１と同様であるため、説明を省略する。
【００６６】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００６７】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０、又は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００６８】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００６９】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の５パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００７０】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００７１】
２．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ≦２ｑかつＢｂ＞２ｑの場合（ここで、ＢａはＨ（Ｍａ）の中で用いる圧縮関数ｈの数、ＢｂはＨ（Ｍｂ）の中で用いる圧縮関数ｈの数とする）
最後のチェックビットが異なるので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７２】
３．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ≦２ｑかつＢｂ≦２ｑの場合
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７３】
４．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ≠ＢｂかつＢａ＞２ｑかつＢｂ＞２ｑの場合
Ｂａ≠Ｂｂなので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７４】
５．｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂの場合
Ｍａ、Ｍｂのパディング後の値をＭａ´、Ｍｂ´とする。即ち、Ｍａ´＝Ｍａ｜｜１０・・・０｜｜＜Ｂａ＞｜｜ｄ、Ｍｂ´＝Ｍｂ｜｜１０・・・０｜｜＜Ｂｂ＞｜｜ｄとなる（ｄはＢａ、Ｂｂの長さによって異なってくる）。ここで、｜Ｍａ｜≠｜Ｍｂ｜かつＢａ＝Ｂｂなので、０をパディングする数が異なる。Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる最後の圧縮関数ｈの入力が異なりかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００７５】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００７６】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、実施の形態１と異なり、ｑをある整数としたときに、ｎが２ｑ以下ならば、＜ｎ＞の長さをｑビットとし、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜０とし、ｎが２ｑより上ならば＜ｎ＞の長さをｑビットより長いｒビットとし、Ｍ´＝Ｍ｜｜１｜｜０・・・０｜｜＜ｎ＞｜｜１とすることを特徴とする。
【００７７】
また、上記ハッシュ関数演算装置は、“０”をパディングする個数が最小となることを特徴とする。
【００７８】
実施の形態３．
本実施の形態について、主に実施の形態１及び２との差異を説明する。
【００７９】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１及び２のものと同様である。
【００８０】
本実施の形態では、パディング部１０２は、ｎではなくｍを表すビット列Ｓと所定のビットパターンＴと所定のビットＤ０又はＤ１とを組み合わせてビット列Ｐを生成する。そして、パディング部１０２は、生成したビット列Ｐを、入力部１０１により入力されたメッセージＭの所定の位置に付加してメッセージＭ´を生成する。実施の形態１及び２と同様に、ビット列Ｓは予め定められたビット長をもつが、ビット列Ｐ全体のビット長はメッセージＭのビット長に応じてパディング部１０２により設定される。
【００８１】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【００８２】
ステップＳ１０１（入力処理）については、実施の形態１及び２と同様であるため、説明を省略する。
【００８３】
ステップＳ１０２（パディング処理）において、ｍ≦２ｑ（ｑはｑ＞０となる整数であり、例えば３２とする）の場合、パディング部１０２は、ｍを表すビット列Ｓのビット長をｑビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｑ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｑビットのビット列Ｓと値が“０”（又は“１”）であるビットＤ０とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、パディング部１０２は、ビット列ＳとビットＤ０とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成するものとする。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ０＝１｜｜０・・・０｜｜＜ｍ＞｜｜０
とする。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｍ＞”はｍを表す固定長（ここではｑビット）の符号語を表記したものである。ｐ＝ｔ＋ｑ＋１であり、ｔ＝Σｍｉ−ｍ−ｑ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００８４】
一方、ステップＳ１０２（パディング処理）において、ｍ＞２ｑの場合、パディング部１０２は、ｍを表すビット列Ｓのビット長をｒ（ｒはｒ＞ｑとなる整数であり、例えば６３とする）ビットに設定する。また、パディング部１０２は、ビットパターンＴとして“１０・・・０”を生成する。このとき、パディング部１０２は、ビットパターンＴのビット長を、ｔ＝Σｍｉ−ｍ−ｒ−１を満たすｔビットに設定する。そして、パディング部１０２は、ｒビットのビット列Ｓと値がビットＤ０と異なる（ビットＤ０が“０”であれば“１”）であるビットＤ１とをｔビットの“１０・・・０”と所定の順番で連結してｐビットのビット列Ｐを生成する。ここでは、ｍ≦２ｑの場合と同様に、パディング部１０２は、ビット列ＳとビットＤ１とを“１０・・・０”の後（所定の順番の一例）に連結してビット列Ｐを生成することになる。即ち、
Ｐ＝Ｔ｜｜Ｓ｜｜Ｄ１＝１｜｜０・・・０｜｜＜ｍ＞｜｜１
となる。なお、前述したように、“｜｜”はビット（列）の連結を表記したものである。“＜ｍ＞”はｍを表す固定長（ここではｒビット）の符号語を表記したものである。ｐ＝ｔ＋ｒ＋１であり、ｔ＝Σｍｉ−ｍ−ｒ−１であるから、前述したように、ｐ＝Σｍｉ−ｍが成り立つ。
【００８５】
パディング部１０２は、上記のように生成したビット列Ｐを、ステップＳ１０１で入力されたメッセージＭの後に連結してΣｍｉビットのメッセージＭ´を生成する。即ち、
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜０（ｍ≦２ｑの場合）
Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜１（ｍ＞２ｑの場合）
とする。なお、前述したように、ｍ≦２ｑの場合、“＜ｍ＞”のビット長はｑであり、ｍ＞２ｑの場合、“＜ｍ＞”のビット長はｒ＞ｑを満たすｒである。
【００８６】
上記のように、ステップＳ１０２では、パディング部１０２が、ハッシュ関数の入力値Ｍに対して、Ｍをハッシュ関数の演算に使える長さに加工するために、Ｍの後に“１”と“０・・・０”（“０”のビット列）とｍを表す例えば３２ビット又は６３ビットの符号語と“０”又は“１”を（ｍ≦２３２ならばｍを表す符号語は３２ビット、最後のビットは“０”となり、ｍ＞２３２ならばｍを表す符号語は６３ビット、最後のビットは“１”となる）、“０・・・０”のビット長が最小となるように付加し（即ち、パディングし）、Ｍ´を作る。Ｍ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜０またはＭ’＝Ｍ｜｜１｜｜０・・・０｜｜＜Ｂ＞｜｜１。前述したように、パディングされる“０”と“１”はそれぞれ反転させてもよい。
【００８７】
ステップＳ１０３（分割処理）以降については、実施の形態１及び２と同様であるため、説明を省略する。
【００８８】
以下では、本実施の形態でも、ハッシュ関数が従来技術と同様の衝突困難性をもつことについての証明を行う。
【００８９】
ハッシュ関数Ｈとしては、ＭＤ構造と上記のパディング方式（Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜０、又は、Ｍ´＝Ｍ｜｜Ｐ＝Ｍ｜｜１｜｜０・・・０｜｜＜ｍ＞｜｜１）を用いることにする。なお、他の構造に対しても同様に衝突困難性の証明を行うことができる。
【００９０】
以下、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たすことを証明する。
【００９１】
証明：
上記の対偶を取ることにより証明を行う。即ち、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことを示すことにより、証明を行う。そのため、まずハッシュ関数Ｈの衝突困難性が破れたと仮定する。即ち、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）となるＭａ、Ｍｂが見つかったと仮定する。このとき、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の中で起きている事象は以下の４パターンに分けることができ、全てのパターンで圧縮関数ｈの衝突困難性が破れていることを示す。
【００９２】
１．｜Ｍａ｜＝｜Ｍｂ｜の場合
｜Ｍａ｜＝｜Ｍｂ｜なので、Ｈ（Ｍａ）とＨ（Ｍｂ）の中で用いる圧縮関数ｈの数は同じである。Ｍａ≠ＭｂかつＨ（Ｍａ）＝Ｈ（Ｍｂ）なので、出力部分の圧縮関数ｈからＩＶ側にバックワードサーチを行っていくとＨ（Ｍａ）、Ｈ（Ｍｂ）の圧縮関数ｈで入力が異なりかつ出力が等しいものが存在する。即ち、圧縮関数ｈの衝突困難性が破れている。
【００９３】
２．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜≦２ｑかつ｜Ｍａ｜＞２ｑの場合
最後のチェックビットが異なるので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９４】
３．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜≦２ｑかつ｜Ｍａ｜≦２ｑの場合
Ｍａ´＝Ｍａ｜｜１｜｜０・・・０｜｜＜｜Ｍａ｜＞｜｜０、Ｍｂ´＝Ｍｂ｜｜１｜｜０・・・０｜｜＜｜Ｍｂ｜＞｜｜０とする。＜｜Ｍａ｜＞と＜｜Ｍｂ｜＞のビット数は同じなので、ｓＭＤの証明と同様に、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９５】
４．｜Ｍａ｜≠｜Ｍｂ｜かつ｜Ｍａ｜＞２ｑかつ｜Ｍａ｜＞２ｑの場合
Ｍａ´＝Ｍａ｜｜１｜｜０・・・０｜｜＜｜Ｍａ｜＞｜｜１、Ｍｂ´＝Ｍｂ｜｜１｜｜０・・・０｜｜＜｜Ｍｂ｜＞｜｜１とする。＜｜Ｍａ｜＞と＜｜Ｍｂ｜＞のビット数は同じなので、ｓＭＤの証明と同様に、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの入力は必ず異なる。また、Ｈ（Ｍａ）＝Ｈ（Ｍｂ）なので、Ｈ（Ｍａ）、Ｈ（Ｍｂ）の最後の圧縮関数ｈの衝突困難性が破れている。
【００９６】
以上全パターンで圧縮関数ｈの衝突困難性が破れているので、ハッシュ関数Ｈが衝突困難性を満たさないならば圧縮関数ｈが衝突困難性を満たさないことが示せた。よって、この対偶により、圧縮関数ｈが衝突困難性を満たすならばハッシュ関数Ｈは衝突困難性を満たす。
【００９７】
以上のように、本実施の形態に係るハッシュ関数演算装置（ハッシュ値演算装置１００）は、実施の形態１及び２と異なり、任意の値Ｍを入力として受けたとき、Ｍのビット長がある値ｑに対して、２ｑ以下ならば、Ｍをｑビットの、Ｍのビット長情報が入った符号語＜Ｍ＞を含む値に変換し、２ｑより大きいならばｑビットより長いｒビットの、Ｍのビット長情報が入った符号語＜Ｍ＞を含む値に変換することを特徴とする。
【００９８】
また、上記ハッシュ関数演算装置は、任意の値Ｍを入力として受けたとき、Ｍのビット長が２ｑ以下ならば、ｑビットの、Ｍのビット長情報が入った符号語＜Ｍ＞に対して、ＭをＭ｜｜１｜｜０・・・０｜｜＜Ｍ＞｜｜０に変換し、２ｑより大きいならばｑビットより長いｒビットの、Ｍのビット長情報が入った符号語＜Ｍ＞に対して、ＭをＭ｜｜１｜｜０・・・０｜｜＜Ｍ＞｜｜１に変換することを特徴とする。
【００９９】
また、上記ハッシュ関数演算装置は、“０”をパディングする個数が最小となることを特徴とする。
【０１００】
実施の形態４．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１０１】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１０２】
図５は、演算部１０４の構成の一例を示すブロック図である。
【０１０３】
図５において、演算器Ｃ１，・・・，Ｃｎ−１については、実施の形態１から３までと同様である。本実施の形態では、演算器Ｃｎは、演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とパディング部１０２により生成されたビット列Ｍｎとに加えて、所定の固定値であるビット列Ｖｎの入力を受け付ける。演算器Ｃｎは、ビット列Ｂｎ−１とビット列Ｍｎとビット列Ｖｎとからなるビット列Ａｎが入力されると、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【０１０４】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１０５】
実施の形態５．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１０６】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１０７】
図６は、演算部１０４の構成の一例を示すブロック図である。
【０１０８】
図６において、演算器Ｃ１，・・・，Ｃｎ−１については、実施の形態１から３までと同様である。本実施の形態では、演算器Ｃｎは、演算器Ｃｎ−１から出力されたビット列Ｂｎ−１に対して１対１写像の置換πを行ってから、当該置換πの結果とパディング部１０２により生成されたビット列Ｍｎとを圧縮関数ｈに入力する。そして、演算器Ｃｎは、ビット列Ｂｎ−１の置換πの結果とビット列Ｍｎとからなるデータに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、生成したビット列ＢｎをメッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力部１０５に返す。
【０１０９】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１１０】
実施の形態６．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１１１】
本実施の形態に係るハッシュ値演算装置１００の構成は、図１に示した実施の形態１から３までのものと同様である。
【０１１２】
図７は、演算部１０４の構成の一例を示すブロック図である。
【０１１３】
図７において、演算部１０４が備えるｎ個の演算器Ｃ１，・・・，Ｃｎは、それぞれ圧縮関数の一例としてブロック暗号Ｅの演算を行う回路（ハードウェアで実装される場合）、関数（ソフトウェアで実装される場合）等である（ハードウェアとソフトウェアとの組み合わせで実装されてもよい）。
【０１１４】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１１５】
実施の形態７．
本実施の形態について、主に実施の形態６との差異を説明する。
【０１１６】
図８は、演算部１０４の構成の一例を示すブロック図である。
【０１１７】
図８において、それぞれの演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対してブロック暗号Ｅの演算を行った後、当該演算の結果とビット列Ａｉのうちビット列Ｍｉ以外のデータとの排他的論理和（ＸＯＲ）を演算する。そして、演算器Ｃｉは、当該ＸＯＲの演算結果をビット列Ｂｉとして出力する。
【０１１８】
例えば、演算器Ｃ１は、所定の固定値であるＩＶとパディング部１０２により生成されたビット列Ｍ１とからなるビット列Ａ１が入力されると、ビット列Ａ１に対してブロック暗号Ｅの演算を行った後、当該演算の結果とＩＶとのＸＯＲを演算し、その結果をビット列Ｂ１として出力する。演算器Ｃ２は、演算器Ｃ１から出力されたビット列Ｂ１とパディング部１０２により生成されたビット列Ｍ２とからなるビット列Ａ２が入力されると、ビット列Ａ２に対してブロック暗号Ｅの演算を行った後、当該演算の結果とビット列Ｂ１とのＸＯＲを演算し、その結果をビット列Ｂ２として生成する。演算器Ｃ３以降については、演算器Ｃ２と同様である。
【０１１９】
上記のような構成によっても、実施の形態６と同様の効果が得られる。
【０１２０】
実施の形態８．
本実施の形態について、主に実施の形態１から３までとの差異を説明する。
【０１２１】
図９は、本実施の形態に係るハッシュ値演算装置１００の構成を示すブロック図である。
【０１２２】
図９において、演算部１０４のｎ個の演算器Ｃ１，・・・，Ｃｎは、並列に接続されている。
【０１２３】
図４を用いて、本実施の形態に係るハッシュ値演算装置１００の動作（本実施の形態に係るハッシュ値演算方法、本実施の形態に係るハッシュ値演算プログラムの処理手順）を説明する。
【０１２４】
ステップＳ１０３（分割処理）までについては、実施の形態１から３までと同様であるため、説明を省略する。
【０１２５】
ステップＳ１０４（演算処理）において、演算部１０４は、ステップＳ１０３におけるビット列Ｍ１，・・・，Ｍｎの入力を受け付ける。演算部１０４は、ビット列Ｍ１と予め定められた固定値であるＩＶ（図９には示していないが、図２等と同様である）とをビット列Ａ１として演算器Ｃ１へ入力する。演算器Ｃ１は、ビット列Ａ１に対して圧縮関数ｈの演算を行ってビット列Ｂ１を生成し、出力する。演算部１０４は、ビット列Ｍ２と予め定められた固定値であるＩＶ（演算器Ｃ１へ入力されるものとは異なる値でもよい）とをビット列Ａ２として演算器Ｃ２へ入力する。演算器Ｃ１と同様に、演算器Ｃ２は、ビット列Ａ２に対して圧縮関数ｈの演算を行ってビット列Ｂ２を生成し、出力する。演算部１０４は、ビット列Ｍ３と演算器Ｃ１から出力されたビット列Ｂ１とをビット列Ａ３として演算器Ｃ３へ入力する。演算器Ｃ１と同様に、演算器Ｃ３は、ビット列Ａ３に対して圧縮関数ｈの演算を行ってビット列Ｂ３を生成し、出力する。演算部１０４は、ビット列Ｍ４と演算器Ｃ２から出力されたビット列Ｂ２とをビット列Ａ４として演算器Ｃ４へ入力する。演算器Ｃ２と同様に、演算器Ｃ４は、ビット列Ａ４に対して圧縮関数ｈの演算を行ってビット列Ｂ４を生成し、出力する。これ以降、同様の演算手順が演算器Ｃｎ−１まで実行される。その後、演算部１０４は、ビット列Ｍｎと演算器Ｃｎ−２から出力されたビット列Ｂｎ−２と演算器Ｃｎ−１から出力されたビット列Ｂｎ−１とをビット列Ａｎとして演算器Ｃｎへ入力する。演算器Ｃｎは、ビット列Ａｎに対して圧縮関数ｈの演算を行ってビット列Ｂｎを生成し、メッセージＭ´のハッシュ値Ｈ（Ｍ´）として出力する。
【０１２６】
ステップＳ１０５（出力処理）については、実施の形態１から３までと同様であるため、説明を省略する。
【０１２７】
上記のような構成によっても、実施の形態１から３までと同様の効果が得られる。
【０１２８】
以上、本発明の実施の形態について説明したが、これらのうち、２つ以上の実施の形態を組み合わせて実施しても構わない。あるいは、これらのうち、１つの実施の形態を部分的に実施しても構わない。あるいは、これらのうち、２つ以上の実施の形態を部分的に組み合わせて実施しても構わない。
【図面の簡単な説明】
【０１２９】
【図１】実施の形態１に係るハッシュ値演算装置の構成を示すブロック図である。
【図２】実施の形態１に係る演算部の構成の一例を示すブロック図である。
【図３】実施の形態１に係るハッシュ値演算装置のハードウェア構成の一例を示す図である。
【図４】実施の形態１に係るハッシュ値演算装置の動作を示すフローチャートである。
【図５】実施の形態４に係る演算部の構成の一例を示すブロック図である。
【図６】実施の形態５に係る演算部の構成の一例を示すブロック図である。
【図７】実施の形態６に係る演算部の構成の一例を示すブロック図である。
【図８】実施の形態７に係る演算部の構成の一例を示すブロック図である。
【図９】実施の形態８に係るハッシュ値演算装置の構成を示すブロック図である。
【符号の説明】
【０１３０】
１００ ハッシュ値演算装置、１０１ 入力部、１０２ パディング部、１０３ 分割部、１０４ 演算部、１０５ 出力部、９０１ ＬＣＤ、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信ボード、９２０ ＨＤＤ、９２１ オペレーティングシステム、９２２ ウィンドウシステム、９２３ プログラム群、９２４ ファイル群。
【特許請求の範囲】
【請求項１】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
メッセージＭを入力する入力部と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とするハッシュ値演算装置。
【請求項２】
前記パディング部は、ｎ≦２ｑ（ｑはｑ＞０となる整数）の場合、ｎを表すｑビットのビット列と値が０又は１であるビットＤ０とを前記所定のビットパターンと所定の順番で連結して前記ビット列Ｐを生成し、ｎ＞２ｑの場合、ｎを表すｒ（ｒはｒ＞ｑとなる整数）ビットのビット列と値が前記ビットＤ０と異なるビットＤ１とを前記所定のビットパターンと前記所定の順番で連結して前記ビット列Ｐを生成することを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項３】
前記パディング部は、ｎを表すｑ（ｑはｑ＞ｌｏｇ２ｎとなる整数）ビットのビット列を前記所定のビットパターンと所定の順番で連結して前記ビット列Ｐを生成することを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項４】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予めビット長が固定されたビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
ｍ（ｍはｍ＞１となる整数）ビットのビット列であるメッセージＭを入力する入力部と、
ｍ≦２ｑ（ｑはｑ＞０となる整数）の場合、ｍを表すｑビットのビット列と値が０又は１であるビットＤ０とを所定のビットパターンと所定の順番で連結してビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成し、ｍ＞２ｑの場合、ｍを表すｒ（ｒはｒ＞ｑとなる整数）ビットのビット列と値が前記ビットＤ０と異なるビットＤ１とを前記所定のビットパターンと前記所定の順番で連結してビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの前記所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とするハッシュ値演算装置。
【請求項５】
前記演算部の演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対して少なくとも圧縮関数の演算を行ってビット列Ｂｉを生成し、ｉ＜ｎの場合、生成したビット列Ｂｉを他の演算器Ｃｊ（ｊはｉ＜ｊ≦ｎとなる整数）へビット列Ａｊの一部として入力し、
前記出力部は、前記演算部の演算器Ｃｎにより生成されたビット列Ｂｎを前記メッセージＭ´のハッシュ値として出力することを特徴とする請求項１から４までのいずれかに記載のハッシュ値演算装置。
【請求項６】
前記演算部のｎ個の演算器Ｃ１，・・・，Ｃｎは、順番に直列に接続されており、
前記演算部の演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ｉ＜ｎの場合、生成したビット列Ｂｉを他の演算器Ｃｊである演算器Ｃｉ＋１へビット列Ａｉ＋１の一部として入力することを特徴とする請求項５に記載のハッシュ値演算装置。
【請求項７】
ビット列Ｍ１，・・・，Ｍｎは、いずれも同じビット長をもつことを特徴とする請求項１から６までのいずれかに記載のハッシュ値演算装置。
【請求項８】
前記所定のビットパターンは、１０又は０１で始まることを特徴とする請求項１から７までのいずれかに記載のハッシュ値演算装置。
【請求項９】
前記演算部のｎ個の演算器Ｃ１，・・・，Ｃｎは、圧縮関数の演算としてブロック暗号の演算を行うことを特徴とする請求項１から８までのいずれかに記載のハッシュ値演算装置。
【請求項１０】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置を利用するハッシュ値演算方法であって、
前記ハッシュ値演算装置の入力部が、メッセージＭを入力し、
前記ハッシュ値演算装置のパディング部が、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成し、
前記ハッシュ値演算装置の分割部が、前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させ、
前記ハッシュ値演算装置の出力部が、前記演算部により演算されたメッセージＭ´のハッシュ値を出力することを特徴とするハッシュ値演算方法。
【請求項１１】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算手順Ｃ１，・・・，Ｃｎを有し、演算手順Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算手順Ｃ１，・・・，Ｃｎを用いて演算する演算処理をＣＰＵ（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）により実行するハッシュ値演算プログラムであって、
メッセージＭを入力する入力処理と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力処理により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´をＣＰＵにより生成するパディング処理と、
前記パディング処理により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算処理へ入力して前記演算処理に前記メッセージＭ´のハッシュ値を演算させる分割処理と、
前記演算処理により演算されたメッセージＭ´のハッシュ値を出力する出力処理とをコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項１】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
メッセージＭを入力する入力部と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とするハッシュ値演算装置。
【請求項２】
前記パディング部は、ｎ≦２ｑ（ｑはｑ＞０となる整数）の場合、ｎを表すｑビットのビット列と値が０又は１であるビットＤ０とを前記所定のビットパターンと所定の順番で連結して前記ビット列Ｐを生成し、ｎ＞２ｑの場合、ｎを表すｒ（ｒはｒ＞ｑとなる整数）ビットのビット列と値が前記ビットＤ０と異なるビットＤ１とを前記所定のビットパターンと前記所定の順番で連結して前記ビット列Ｐを生成することを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項３】
前記パディング部は、ｎを表すｑ（ｑはｑ＞ｌｏｇ２ｎとなる整数）ビットのビット列を前記所定のビットパターンと所定の順番で連結して前記ビット列Ｐを生成することを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項４】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予めビット長が固定されたビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置であって、
ｍ（ｍはｍ＞１となる整数）ビットのビット列であるメッセージＭを入力する入力部と、
ｍ≦２ｑ（ｑはｑ＞０となる整数）の場合、ｍを表すｑビットのビット列と値が０又は１であるビットＤ０とを所定のビットパターンと所定の順番で連結してビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成し、ｍ＞２ｑの場合、ｍを表すｒ（ｒはｒ＞ｑとなる整数）ビットのビット列と値が前記ビットＤ０と異なるビットＤ１とを前記所定のビットパターンと前記所定の順番で連結してビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの前記所定の位置に付加して前記メッセージＭ´を生成するパディング部と、
前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させる分割部と、
前記演算部により演算されたメッセージＭ´のハッシュ値を出力する出力部とを備えることを特徴とするハッシュ値演算装置。
【請求項５】
前記演算部の演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ビット列Ｍｉを含むビット列Ａｉの入力を受け付け、入力されたビット列Ａｉに対して少なくとも圧縮関数の演算を行ってビット列Ｂｉを生成し、ｉ＜ｎの場合、生成したビット列Ｂｉを他の演算器Ｃｊ（ｊはｉ＜ｊ≦ｎとなる整数）へビット列Ａｊの一部として入力し、
前記出力部は、前記演算部の演算器Ｃｎにより生成されたビット列Ｂｎを前記メッセージＭ´のハッシュ値として出力することを特徴とする請求項１から４までのいずれかに記載のハッシュ値演算装置。
【請求項６】
前記演算部のｎ個の演算器Ｃ１，・・・，Ｃｎは、順番に直列に接続されており、
前記演算部の演算器Ｃｉ（ｉ＝１，・・・，ｎ）は、ｉ＜ｎの場合、生成したビット列Ｂｉを他の演算器Ｃｊである演算器Ｃｉ＋１へビット列Ａｉ＋１の一部として入力することを特徴とする請求項５に記載のハッシュ値演算装置。
【請求項７】
ビット列Ｍ１，・・・，Ｍｎは、いずれも同じビット長をもつことを特徴とする請求項１から６までのいずれかに記載のハッシュ値演算装置。
【請求項８】
前記所定のビットパターンは、１０又は０１で始まることを特徴とする請求項１から７までのいずれかに記載のハッシュ値演算装置。
【請求項９】
前記演算部のｎ個の演算器Ｃ１，・・・，Ｃｎは、圧縮関数の演算としてブロック暗号の演算を行うことを特徴とする請求項１から８までのいずれかに記載のハッシュ値演算装置。
【請求項１０】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算器Ｃ１，・・・，Ｃｎを有し、演算器Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算器Ｃ１，・・・，Ｃｎを用いて演算する演算部を具備するハッシュ値演算装置を利用するハッシュ値演算方法であって、
前記ハッシュ値演算装置の入力部が、メッセージＭを入力し、
前記ハッシュ値演算装置のパディング部が、ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力部により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´を生成し、
前記ハッシュ値演算装置の分割部が、前記パディング部により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算部へ入力して前記演算部に前記メッセージＭ´のハッシュ値を演算させ、
前記ハッシュ値演算装置の出力部が、前記演算部により演算されたメッセージＭ´のハッシュ値を出力することを特徴とするハッシュ値演算方法。
【請求項１１】
少なくとも圧縮関数の演算を行うｎ（ｎはｎ＞１となる整数）個の演算手順Ｃ１，・・・，Ｃｎを有し、演算手順Ｃｉ（ｉ＝１，・・・，ｎ）への入力として予め定められたビット長をもつビット列Ｍｉそれぞれの入力を受け付け、入力されたビット列Ｍ１，・・・，ＭｎからなるメッセージＭ´のハッシュ値を、前記ｎ個の演算手順Ｃ１，・・・，Ｃｎを用いて演算する演算処理をＣＰＵ（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）により実行するハッシュ値演算プログラムであって、
メッセージＭを入力する入力処理と、
ｎを表すビット列と所定のビットパターンとを組み合わせてビット列Ｐを生成し、生成したビット列Ｐを、前記入力処理により入力されたメッセージＭの所定の位置に付加して前記メッセージＭ´をＣＰＵにより生成するパディング処理と、
前記パディング処理により生成されたメッセージＭ´をｎ分割してビット列Ｍ１，・・・，Ｍｎを生成し、生成したビット列Ｍ１，・・・，Ｍｎを前記演算処理へ入力して前記演算処理に前記メッセージＭ´のハッシュ値を演算させる分割処理と、
前記演算処理により演算されたメッセージＭ´のハッシュ値を出力する出力処理とをコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−１５２４６８（Ｐ２０１０−１５２４６８Ａ）
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願番号】特願２００８−３２７３１８（Ｐ２００８−３２７３１８）
【出願日】平成２０年１２月２４日（２００８．１２．２４）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願日】平成２０年１２月２４日（２００８．１２．２４）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]