(57)【要約】【課題】差分攻撃耐性を有し、メモリ容量に制限のある装置に実装可能なハッシュ生成方法を提供する。【解決手段】メッセージをメッセージブロックに分割し、各メッセージブロックに対してブロック暗号の処理を実行してハッシュ値を算出するハッシュ値生成装置であって、初期値を格納する記憶部と、鍵定数Ｋを算出する関数ｆk、及び、出力データを算出する関数ｆRを実行し、出力データを記憶部に格納し、出力データを連結してハッシュ値を算出する演算部と、を備え、関数ｆRは、ｍビット幅のビット列の巡回シフトと、二つのビット列を加算する算術加算とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する非線形関数γと、２ｍビット幅のビット列の巡回シフトと、二つのビット列の排他的論理和とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する線形関数θと、の合成関数である関数ＦRを含む。【選択図】図９
2013076854.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを所定のデータ長のメッセージブロックに分割し、前記分割された各メッセージブロックに対してブロック暗号の処理を実行することによって算出された出力データを連結して、所定のデータ長のハッシュ値を算出するハッシュ値生成装置であって、
前記メッセージの入力を受け付け、前記ハッシュ値を出力する入出力部と、
前記ハッシュ値の算出処理に用いられる初期値を格納する記憶領域を提供する記憶部と、
前記初期値から暗号化に用いられる鍵定数Ｋを算出する関数ｆk、並びに、前記算出された鍵定数Ｋ及び前記メッセージブロックを入力することによって前記出力データを算出する関数ｆRを実行し、前記関数ｆk及び関数ｆRによって前記各メッセージブロックが変換された前記出力データを前記記憶部に格納し、前記出力データを連結して前記ハッシュ値を算出する演算部と、を備え、
前記関数ｆRは、
ｍビット幅（ｍは、ｍ＞１となる整数）のビット列の巡回演算を実行する巡回シフトと、二つのビット列を加算する算術加算とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する非線形関数γと、
２ｍビット幅のビット列の巡回演算を実行する巡回シフトと、二つのビット列の排他的論理和とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する線形関数θと、の合成関数である関数ＦRを含むことを特徴とするハッシュ値生成装置。
【請求項２】
前記演算部は前記非線形関数γを実行することによって、
前記入力データを２ｍビットのサブデータに分割し、
前記分割された各サブデータを関数Ｆkに入力することによって前記各サブデータを変換し、
前記変換された各サブデータを連結して４ｍビットの出力データを算出し、
前記演算部は前記関数Ｆkを実行することによって、
２ｍビットの入力データをｍビットのサブデータｓ0、ｓ1に分割し、
前記サブデータｓ1に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ0との算術加算を実行してデータｓ'0を算出し、
前記データｓ'0に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ1との算術加算を実行してデータｓ'1を算出し、
前記データｓ'0及び前記データｓ'1を連結することによって、前記サブデータを変換することを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項３】
前記ハッシュ値生成装置は、
前記関数ｆk及び前記関数ｆRを用いた処理を一つの処理単位とするラウンド処理を複数回実行し、
前記演算部は、前記ラウンド処理において、前回のラウンド処理において算出された前記鍵定数を前記関数ｆkに入力することによって新たな前記鍵定数を算出し、前記新たな鍵定数と、前回のラウンド処理において算出された前記出力データとを前記関数ｆRに入力することによって新たな前記出力データを算出し、
前記前記演算部は前記関数ｆRを実行することによって、
前回のラウンド（ｒ−１）のラウンド処理において算出された出力データｘ(r-1)を、ビット数が同一である五つのデータｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)、ｘ4(r-1)に分割し、
前記データｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)を、それぞれ、前記新たな出力データｘrを構成するデータｘ1r、ｘ2r、ｘ3r、ｘ4rとして出力し、
前記新たな鍵定数Ｋrからビット列Ｓを生成し、
前記ビット列Ｓと前記データｘ3(r-1)との排他的論理和ｐを前記関数ＦRに入力することによってデータｑを算出し、
前記データｑと前記データｘ4(r-1)との排他的論理和を前記出力データｘrを構成するデータｘ0rとして出力し、
前記データｘ0r、ｘ1r、ｘ2r、ｘ3r、ｘ4rを連結して、前記新たな出力データｘrを算出し、
前記記憶部に前記出力データｘrを格納することを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項４】
前記記憶部は、前記鍵定数の算出時に用いられるラウンド定数及び鍵ラウンド値を格納し、
前記演算部は、さらに、前回のラウンド（ｒ−１）のラウンド処理において算出された前記ラウンド定数Ｃ(r-1)からラウンドｒにおける前記ラウンド定数Ｃrを算出する関数ｆcを実行し、
前記演算部は前記関数ｆkを実行することによって、
前回のラウンド（ｒ−１）において算出された鍵ラウンド値ｋ(r-1)を、ビット数が同一である五つのデータｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、ｋ4(r-1)に分割し、
前記データｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)を、それぞれ、前記新たな鍵ラウンド値ｋrを構成するデータｋ1r、ｋ2r、ｋ3r、ｋ4rとして出力し、
前記ラウンド定数Ｃrと前記データｋ3(r-1)との排他的論理和ａを前記関数ＦRに入力することによってデータｂを算出し、
前記データｂと前記データｋ4(r-1)との排他的論理和を前記新たな鍵ラウンド値ｋrを構成するデータｋ0rとして出力し、
前記データｋ0r、ｋ1r、ｋ2r、ｋ3r、ｋ4rを連結して、前記新たな鍵ラウンド値ｋrを算出し、
前記記憶部に前記鍵ラウンド値ｋrを格納し、
前記鍵ラウンド値ｋrを構成するｋ1rを前記新たな鍵定数Ｋrとして、前記関数ｆRに対して出力することを特徴とする請求項３に記載のハッシュ値生成装置。
【請求項５】
メッセージを所定のデータ長のメッセージブロックに分割し、前記各メッセージブロックに対してブロック暗号の処理を実行することによって算出された出力データを連結して、所定のデータ長のハッシュ値を算出する装置に実行させるためのハッシュ値生成プログラムであって、
前記装置は、前記ハッシュ値生成プログラムを実行するプロセッサと、前記プロセッサに接続される記憶媒体とを備え、
前記ハッシュ値生成プログラムは
前記メッセージの入力を受け付ける手順と、
前記ハッシュ値の算出処理に用いる初期値が格納される前記記憶媒体から前記初期値を読み出し、当該初期値から暗号化に用いられる鍵定数Ｋを生成する関数ｆkを実行させる手順と、
前記生成された鍵定数Ｋ及び前記メッセージブロックを入力として前記出力データを算出する関数ｆRを実行させる手順と、
前記算出された出力データを前記記憶媒体に格納する手順と、
前記記憶媒体に格納される前記出力データを連結して前記ハッシュ値を算出する手順と、を前記プロセッサに実行させ、
前記関数ｆRは、
ｍビット幅（ｍは、ｍ＞１となる整数）のビット列の巡回演算を実行する巡回シフトと、二つのビット列を加算する算術加算とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する非線形関数γと、
２ｍビット幅のビット列の巡回演算を実行する巡回シフトと、二つのビット列の排他的論理和とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する線形関数θと、の合成関数である関数ＦRを含むことを特徴とするハッシュ値生成プログラム。
【請求項６】
前記関数ＦRに含まれる非線形関数γを実行させる手順では、
前記入力データを２ｍビットのサブデータに分割する手順と、
前記分割された各サブデータを関数Ｆkに入力することによって前記各サブデータを変換する手順と、
前記変換された各サブデータを連結して４ｍビットの出力データを算出する手順と、
を含み、
前記関数Ｆkを実行させる手順では、
２ｍビットの入力データをｍビットのサブデータｓ0、ｓ1に分割する手順と、
前記サブデータｓ1に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ0との算術加算を実行してデータｓ'0を算出する手順と、
前記データｓ'0に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ1との算術加算を実行してデータｓ'1を算出する手順と、
前記データｓ'0及び前記データｓ'1を連結することによって、前記サブデータを変換する手順と、
を含むことを特徴とする請求項５に記載のハッシュ値生成プログラム。
【請求項７】
前記関数ｆk及び前記関数ｆRを用いた処理を一つの処理単位とするラウンド処理を複数回実行させる手順を含み、
前記ラウンド処理は、
前回のラウンド処理において算出された前記鍵定数を前記関数ｆkに新たな鍵定数を算出する手順と、
前記新たな鍵定数と、前回のラウンド処理において算出された前記出力データとを前記関数ｆRに入力することによって新たな前記出力データを算出する手順と、を含み、
前記関数ｆRを実行させる手順では、
前回のラウンド（ｒ−１）のラウンド処理において算出された出力データｘ(r-1)を、ビット数が同一である五つのデータｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)、ｘ4(r-1)に分割する手順と、
前記データｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)を、それぞれ、前記新たな出力データｘrを構成するデータｘ1r、ｘ2r、ｘ3r、ｘ4rとして出力する手順と、
前記新たな鍵定数Ｋrからビット列Ｓを生成する手順と、
前記ビット列Ｓと前記データｘ3(r-1)との排他的論理和ｐを前記関数ＦRに入力することによってデータｑを算出する手順と、
前記データｑと前記データｘ4(r-1)との排他的論理和を前記出力データｘrを構成するデータｘ0rとして出力する手順と、
前記データｘ0r、ｘ1r、ｘ2r、ｘ3r、ｘ4rを連結して、前記新たな出力データｘrを算出する手順と、
前記記憶媒体に前記出力データｘrを格納する手順と、を含むことを特徴とする請求項６に記載のハッシュ値生成プログラム。
【請求項８】
前記記憶媒体は、前記鍵定数の算出時に用いられるラウンド定数及び鍵ラウンド値を格納し、
前記ハッシュ値生成プログラムは、前回のラウンド（ｒ−１）のラウンド処理においてにおいて算出された前記ラウンド定数Ｃ(r-1)からラウンドｒにおける前記ラウンド定数Ｃrを算出する関数ｆcを前記プロセッサに実行させる手順を含み、
前記関数ｆkを実行させる手順では、
前回のラウンド（ｒ−１）において算出された鍵ラウンド値ｋ(r-1)を、ビット数が同一である五つのデータｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、ｋ4(r-1)に分割する手順と、
前記データｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)を、それぞれ、前記新たな鍵ラウンド値ｋrを構成するデータｋ1r、ｋ2r、ｋ3r、ｋ4rとして出力する手順と、
前記ラウンド定数Ｃrと前記データｋ3(r-1)との排他的論理和ａを前記関数ＦRに入力することによってデータｂを算出する手順と、
前記データｂと前記データｋ4(r-1)との排他的論理和を前記新たな鍵ラウンド値ｋrを構成するデータｋ0rとして出力する手順と、
前記データｋ0r、ｋ1r、ｋ2r、ｋ3r、ｋ4rを連結して、前記新たな鍵ラウンド値ｋrを算出する手順と、
前記記憶媒体に前記鍵ラウンド値ｋrを格納する手順と、
前記鍵ラウンド値ｋrを構成するｋ1rを前記新たな鍵定数Ｋrとして、前記関数ｆRに対して出力する手順と、を含むことを特徴とする請求項７に記載のハッシュ値生成プログラム。
【請求項９】
メッセージを所定のデータ長のメッセージブロックに分割し、前記各メッセージブロックに対してブロック暗号の処理を実行することによって算出された出力データを連結して、所定のデータ長のハッシュ値を算出する装置が実行するハッシュ値生成方法であって、
前記装置は、プロセッサと、前記プロセッサに接続される記憶媒体とを備え、
前記方法は、
前記プロセッサが、前記メッセージの入力を受け付けるステップと、
前記プロセッサが、前記ハッシュ値の算出処理に用いる初期値が格納される前記記憶媒体から前記初期値を読み出し、当該初期値から暗号化に用いられる鍵定数Ｋを算出する関数ｆkを実行するステップと、
前記プロセッサが、前記生成された鍵定数Ｋ及び前記各メッセージブロックを入力することによって前記出力データを算出する関数ｆRを実行するステップと、
前記プロセッサが、前記出力データを前記記憶媒体に格納するステップと、
前記プロセッサが、前記記憶媒体に格納される前記出力データを連結して前記ハッシュ値を算出するステップと、を含み、
前記関数ｆRは、
ｍビット幅（ｍは、ｍ＞１となる整数）のビット列の巡回演算を実行する巡回シフトと、二つのビット列を加算する算術加算とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する非線形関数γと、
２ｍビット幅のビット列の巡回演算を実行する巡回シフトと、二つのビット列の排他的論理和とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する線形関数θと、の合成関数である関数ＦRを含むことを特徴とするハッシュ値生成方法。
【請求項１０】
前記プロセッサが前記関数ＦRに含まれる前記非線形関数γを実行する処理は、
前記入力データを２ｍビットのサブデータに分割するステップと、
前記分割された各サブデータを関数Ｆkに入力することによって前記各サブデータを変換するステップと、
前記変換された各サブデータを連結して４ｍビットの出力データを算出するステップと、
を含み、
前記プロセッサが前記関数Ｆkを実行する処理は、
２ｍビットの入力データをｍビットのサブデータｓ0、ｓ1に分割するステップと、
前記サブデータｓ1に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ0との算術加算を実行してデータｓ'0を算出するステップと、
前記データｓ'0に対して所定のビットの巡回シフトを実行して算出された値と、前記サブデータｓ1との算術加算を実行してデータｓ'1を算出するステップと、
前記データｓ'0及び前記データｓ'1を連結することによって、前記サブデータを変換するステップと、を含むことを特徴とする請求項９に記載のハッシュ値生成方法。
【請求項１１】
前記ブロック暗号の処理では、前記プロセッサが、前記関数ｆk及び前記関数ｆRを用いた処理を一つの処理単位とするラウンド処理を複数回実行し、
前記ラウンド処理は、
前記プロセッサが、前回のラウンド処理において算出された前記鍵定数を前記関数ｆkに入力することによって新たな前記鍵定数を算出するステップと、
前記新たな鍵定数と、前回のラウンド処理において算出された前記出力データとを前記関数ｆRに入力することによって新たな前記出力データを算出するステップと、を含み、
前記プロセッサが前記関数ｆRを実行する処理は、
前回のラウンド（ｒ−１）において算出された出力データｘ(r-1)を、ビット数が同一である五つのデータｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)、ｘ4(r-1)に分割するステップと、
前記データｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)を、それぞれ、前記新たな出力データｘrを構成するデータｘ1r、ｘ2r、ｘ3r、ｘ4rとして出力するステップと、
前記算出された鍵定数Ｋrからビット列Ｓを生成するステップと、
前記ビット列Ｓと前記データｘ3(r-1)との排他的論理和ｐを前記関数ＦRに入力して、データｑを算出するステップと、
前記データｑと前記データｘ4(r-1)との排他的論理和を前記出力データｘrを構成するデータｘ0rとして出力するステップと、
前記データｘ0r、ｘ1r、ｘ2r、ｘ3r、ｘ4rを連結して、前記新たな出力データｘrを算出するステップと、
前記記憶領域に前記出力データｘrを格納するステップと、を含むことを特徴とする請求項１０に記載のハッシュ値生成方法。
【請求項１２】
前記記憶媒体は、前記鍵定数の算出時に用いられるラウンド定数及び鍵ラウンド値を格納し、
前記方法は、前回のラウンド（ｒ−１）において算出された前記ラウンド定数Ｃ(r-1)からラウンドｒにおける前記ラウンド定数Ｃrを算出する関数ｆcを実行するステップを含み、
前記プロセッサが前記関数ｆkを実行する処理は、
前回のラウンド（ｒ−１）において算出された鍵ラウンド値ｋ(r-1)を、ビット数が同一である五つのデータｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、ｋ4(r-1)に分割するステップと、
前記データｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)を、それぞれ、前記新たな鍵ラウンド値ｋrを構成するデータｋ1r、ｋ2r、ｋ3r、ｋ4rとして出力するステップと、
前記ラウンド定数Ｃrと前記データｋ3(r-1)との排他的論理和ａを前記関数ＦRに入力することによってデータｂを算出するステップと、
前記データｂと前記データｋ4(r-1)との排他的論理和を前記新たな鍵ラウンド値ｋrを構成するデータｋ0rとして出力するステップと、
前記データｋ0r、ｋ1r、ｋ2r、ｋ3r、ｋ4rを連結して、前記新たな鍵ラウンド値ｋrを算出するステップと、
前記記憶媒体に前記鍵ラウンド値ｋrを格納するステップと、
前記鍵ラウンド値ｋrを構成するｋ1rを前記新たな鍵定数Ｋrとして、前記関数ｆRに対して出力するステップと、を含むことを特徴とする請求項１１に記載のハッシュ値生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長のメッセージを入力として、特定の長さのハッシュ値を生成する関数である。
【０００３】
一般的に、ハッシュ関数は、固定長のメッセージブロックを入力するブロック暗号及び固定長の置換から構成される。ハッシュ関数は、入力されたメッセージに対してブロック暗号及び置換を繰り返し行うことによってメッセージを攪拌して、最終的なハッシュ値を出力する。ハッシュ関数の代表例としてはＳＨＡ−１、又は、ＳＨＡ−２５６等のＳＨＡ−２ハッシュ族、ＳＨＡ−３コンペティションの候補アルゴリズムなどがある（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】NIST FIPS 180-2, "Secure Hash Standard", 2002 August 1, pp. 9-23, http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載のＳＨＡ−１は、ハッシュ関数が持つべき安全性である衝突耐性に問題があることが知られており、ＳＨＡ−２ハッシュ族についても、ＳＨＡ−１と類似した構造であることから、ハッシュ関数が持つべき安全性に問題を生ずる可能性がある。そこで、本発明は、安全性の評価が可能なハッシュ関数を提供することを目的とする。従来技術は、算術加算による非線形変換処理と巡回シフト変換による線型変換処理との組み合わせ処理を一回実行しているため、安全性を確保するのが困難である。
【０００６】
また、ハッシュ関数では、非線形変換が利用されており、その一つにＳ−ｂｏｘ型によるものがある。従来のＳ−ｂｏｘ型の非線形変換は、８ビットのＳ−ｂｏｘでは、表参照によって実装され、また、４ビットのＳ−ｂｏｘでは、論理演算の合成として実装される。しかし、８ビットのＳ−ｂｏｘの場合、表を格納するためのＲＯＭ使用量が増大し、また、４ビットのＳ−ｂｏｘでは演算数が１５〜２０程度と多くコードサイズが増大し、ＲＯＭ使用量が増大する。したがって、従来の非線形変換を実現するためのプログラムは、マイコン等のＲＯＭサイズが小さいローエンド環境における実装することが困難であるという課題がある。
【０００７】
一方、他の非線形変換の構成方法として、ＳＨＡ−３候補ハッシュ関数Ｓｋｅｉｎが採用しているＡＲＸ（算術加算、巡回シフト、排他的論理和）型によるものがある。この非線形置換に基づいてワード長を変えることによって、容易に非線形変換を設計することができる。しかし、前述した非線形置換では、差分攻撃に対する強度が小さいという課題がある。
【０００８】
また、従来のハッシュ関数では、実装環境であるＰＣ及びサーバ等に用いられるＣＰＵのレジスタ幅に合わせた処理単位で内部の処理が実行される。例えば、ＣＰＵのレジスタ幅が３２（又は６４）ビットであれば、ハッシュ関数は、入力データを３２（又は６４）ビットのワード単位に区切って処理実行しており、これらのワードを８ビット、１６ビット単位のような、より小さい長さのワードに分割することは一般的には行われない。これは、小さい長さのワードに分割すると、処理速度が悪くなる等の困難性が生じるためである。
【０００９】
これは、一般的に３２ビットＣＰＵは、３２ビット命令（３２ビット単位で処理を行う命令）をサポートしているが、３２より小さいビット幅（１６ビット又は８ビット）の命令はサポートしないという点による。
【００１０】
本発明では、ハッシュ値の安全性を確保し、かつ、ＲＯＭ使用量を抑えたハッシュ関数を実現することを目的とする。
【課題を解決するための手段】
【００１１】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、メッセージを所定のデータ長のメッセージブロックに分割し、前記分割された各メッセージブロックに対してブロック暗号の処理を実行することによって算出された出力データを連結して、所定のデータ長のハッシュ値を算出するハッシュ値生成装置であって、前記メッセージの入力を受け付け、前記ハッシュ値を出力する入出力部と、前記ハッシュ値の算出処理に用いられる初期値を格納する記憶領域を提供する記憶部と、前記初期値から暗号化に用いられる鍵定数Ｋを算出する関数ｆk、並びに、前記算出された鍵定数Ｋ及び前記メッセージブロックを入力することによって前記出力データを算出する関数ｆRを実行し、前記関数ｆk及び関数ｆRによって前記各メッセージブロックが変換された前記出力データを前記記憶部に格納し、前記出力データを連結して前記ハッシュ値を算出する演算部と、を備え、前記関数ｆRは、ｍビット幅のビット列の巡回演算を実行する巡回シフトと、二つのビット列を加算する算術加算とを含み、４ｍビット（ｍは、ｍ＞１となる整数）の入力データに対して４ｍビットの出力データを算出する非線形関数γと、２ｍビット幅のビット列の巡回演算を実行する巡回シフトと、二つのビット列の排他的論理和とを含み、４ｍビットの入力データに対して４ｍビットの出力データを算出する線形関数θと、の合成関数である関数ＦRを含むことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、算術加算、巡回シフト、及び排他的論理和を用いてハッシュ値を算出するため差分攻撃に対する耐性が向上する。また、Ｓ−ｂｏｘを用いることなくハッシュ値を生成できるためメモリ容量に制限のある機器に適用することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態におけるハッシュ値生成装置の論理構成の一例を示すブロック図である。
【図２】本発明の実施形態におけるハッシュ値生成装置のハードウェア構成を示すブロック図である。
【図３】本発明の実施形態におけるハッシュ値の算出方法の一例を示す説明図である。
【図４】本発明の実施形態におけるハッシュ値生成装置が実行するハッシュ値の生成処理を説明するフローチャートである。
【図５】本発明の実施形態におけるブロック暗号ｆEにおける処理の概要を示す説明図である。
【図６】本発明の実施形態における関数ｆcの概要を示す説明図である。
【図７】本発明の実施形態における鍵ラウンド値変換関数ｆKを示す説明図である。
【図８】本発明の実施形態における平文ラウンド値変換関数ｆRを示す説明図である。
【図９】本発明の実施形態における関数ＦRを示す説明図である。
【図１０】本発明の実施形態における関数ＦRの処理の流れを説明するフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面を用いて本発明の実施形態について説明する。
【００１５】
図１は、本発明の実施形態におけるハッシュ値生成装置１００の論理構成の一例を示すブロック図である。
【００１６】
ハッシュ値生成装置１００は、所定のメッセージからハッシュ値を生成する。本実施形態では、ハッシュ値生成装置１００は、１６０ビットのハッシュ値を生成するものとする。なお、本発明は、生成するハッシュ値のビット数に限定されない。
【００１７】
ハッシュ値生成装置１００は、記憶部１１０、制御部１２０、入力部１３０及び出力部１４０を備える。
【００１８】
制御部１２０は、記憶部１１０に格納される情報を用いて、ハッシュ値生成装置１００に入力されたメッセージからハッシュ値を生成する。制御部１２０は、全体制御部１２１、メッセージブロック化部１２２、ラウンド定数生成部１２３、ラウンド鍵生成部１２４及び撹拌部１２５を備える。
【００１９】
全体制御部１２１は、ハッシュ値生成装置１００における処理の全体を制御する。本実施形態の全体制御部１２１は、処理対象であるメッセージをブロック化したメッセージブロックを管理し、また、ラウンド毎のラウンド定数生成部１２３、ラウンド鍵生成部１２４及び撹拌部１２５における処理を管理する。
【００２０】
また、全体制御部１２１は、全てのラウンドを経て撹拌部１２５において算出された平文ラウンド値を出力することによって算出値を算出する。さらに、全体制御部１２１は、全てのメッセージブロック及び全てのラウンドを経て撹拌部１２５において算出された平文ラウンド値を出力することによって、ハッシュ値を算出する。
【００２１】
メッセージブロック化部１２２は、ハッシュ値の算出対象となるメッセージを所定のビット長のブロックに分割し、パディングを行う。なお、ビット上は予め設定されているものとする。以下、所定のビット長のブロックをメッセージブロックとも記載する。
【００２２】
ここで、本実施形態では、ハッシュ値の算出対象となるメッセージを８０ビット毎のブロックに分割するようにしているが、このような態様に限定されるわけではない。
【００２３】
また、本実施形態におけるパディングは、以下のような処理が考えられる。
【００２４】
メッセージブロック化部１２２は、メッセージの最後に「１」を連結し、次に、ｖビットの「０」を連結する。ただし、ｖは、ｖ＋Ｌ（ここで、Ｌはメッセージのビット長を示す値）が８０で割り切れる最小の非負整数とする。次に、メッセージブロック化部１２２は、最後の３２ビットにＬを格納する。
【００２５】
なお、本実施形態においては、ハッシュ値を算出するメッセージをＭで表し、パディングによってブロック化されたメッセージブロックをＭ'で表す。また、メッセージＭは、ｋ＋１個（ｋは１以上の整数）のメッセージブロックに分割されるものとし、各メッセージブロックをＭ'i（ｉは、０≦ｉ≦ｋを満たす整数）で表す。
【００２６】
ラウンド定数生成部１２３は、各ラウンドにおけるラウンド定数及び定数ラウンド値を算出する。ラウンド鍵生成部１２４は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する。撹拌部１２５は、各ラウンドにおける平文ラウンド値を算出する。
【００２７】
記憶部１１０は、ハッシュ値を生成するために必要な情報及び数値を格納する。具体的には、記憶部１１０は、初期値記憶領域１１１、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３、平文ラウンド値記憶領域１１４、算出値記憶領域１１５及びハッシュ値記憶領域１１６を備える。
【００２８】
初期値記憶領域１１１は、ハッシュ値の生成時に用いられる初期値を特定するための情報を格納する。本実施形態の初期値記憶領域１１１には、定数ラウンド値の初期値及び算出値の初期値が格納される。
【００２９】
例えば、下式（１）に示すような定数ｃ(-1)がラウンド定数の初期値として格納され、下式（２）に示すような定数Ｈ-1が算出値の初期値として格納される。
【数１】
2013076854.tif 000003
【数２】
2013076854.tif 000004
ここで、Ｈ-1.0、Ｈ-1.1、Ｈ-1.2、Ｈ-1.3及びＨ-1.4は下式（３）〜（７）に示すような定数とする。
【数３】
2013076854.tif 000005
【数４】
2013076854.tif 000006
【数５】
2013076854.tif 000007
【数６】
2013076854.tif 000008
【数７】
2013076854.tif 000009
【００３０】
なお、ラウンド定数及び算出値の初期値として格納される定数は前述したものに限定されず、例えば、図示していない疑似乱数生成器等を用いて生成された乱数が、定数ラウンド値及び算出値の初期値として格納されてもよい。
【００３１】
定数ラウンド値記憶領域１１２は、各メッセージブロックにおけるラウンド毎のラウンド定数を特定する情報を格納する。なお、本実施形態においては、ラウンド定数は、ラウンド定数生成部１２３によって生成される。
【００３２】
鍵ラウンド値記憶領域１１３は、各メッセージブロックにおけるラウンド毎の鍵ラウンド値を特定する情報が格納される。なお、本実施形態においては、鍵ラウンド値は、ラウンド鍵生成部１２４によって生成される。
【００３３】
平文ラウンド値記憶領域１１４は、各メッセージブロックにおけるラウンド毎の平文ラウンド値を特定する情報を格納する。なお、本実施形態において、平文ラウンド値は、撹拌部１２５によって生成される。
【００３４】
算出値記憶領域１１５は、各メッセージブロックにおいて全てのラウンドの処理を経て算出された算出値を特定する情報を格納する。なお、本実施形態においては、算出値は、全体制御部１２１によって生成される。
【００３５】
ハッシュ値記憶領域１１６は、全てのメッセージブロックに対するハッシュ値を特定する情報が格納される。なお、本実施形態においては、ハッシュ値は、全体制御部１２１によって生成される。
【００３６】
なお、図示していないが、所定の演算に用いられる各種関数は、記憶部１１０に格納される。
【００３７】
入力部１３０は、メッセージ等の情報の入力を受け付ける。出力部１４０は、算出されたハッシュ値を出力する。
【００３８】
ハッシュ値生成装置１００は、図２に示すようなハードウェア構成によって実現される。図２は、本発明の実施形態におけるハッシュ値生成装置１００のハードウェア構成を示すブロック図である。
【００３９】
ハッシュ値生成装置１００は、プロセッサ２０１、メモリ２０２、外部記憶装置２０３、通信装置２０５、入力装置２０６、出力装置２０７及び読書装置２０８を備える計算機によって実現できる。
【００４０】
プロセッサ２０１は、メモリ２０２に格納されるプログラムを実行する。プロセッサ２０１がメモリ２０２に格納されるプログラムを実行することによって、ハッシュ値生成装置１００が備える機能が実現される。
【００４１】
メモリ２０２は、プロセッサ２０１が実行するプログラム及びプログラムの実行に必要な情報を格納する。
【００４２】
外部記憶装置２０３は、各種情報を格納する記憶媒体であり、例えば、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）及びＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等が考えられる。
【００４３】
読書装置２０８は、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）又はＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等の可搬性を有する記憶媒体２１０から情報を読み出し、又は情報を書き込む。制御部１２０を実現するためのプログラムが記録された記憶媒体２１０を、汎用的な計算機にインストールすることによって、ハッシュ値生成装置１００を実現することができる。
【００４４】
通信装置２０５は、通信ネットワークに接続するための装置であり、例えば、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）等が考えられる。
【００４５】
入力装置２０６は、ハッシュ値生成装置１００に情報を入力するための装置であり、例えば、キーボード及びマウスなどが含まれる。出力装置２０７は、ハッシュ値生成装置１００における処理結果等を出力するための装置であり、ディスプレイなどが含まれる。
【００４６】
本実施形態における記憶部１１０は、メモリ２０２及び外部記憶装置２０３の記憶領域を用いることによって実現できる。また、制御部１２０は、図１に示すような複数のプログラムモジュールから構成されるプログラムとして実現可能である。当該プログラムは、外部記憶装置２０３に格納されいる場合には、プロセッサ２０１が、メモリ２０２にロードして実行することによって制御部１２０が有する機能を実現できる。
【００４７】
また、入力部１３０は、入力装置２０６を用いることによって実現可能であり、出力部１４０は、出力装置２０７を用いることによって実現可能である。
【００４８】
制御部１２０を実現するめのプログラムは、予め、外部記憶装置２０３に格納されていなくてもよく、読書装置２０８を介して記憶媒体２１０から取得されてもよいし、又は、通信装置２０５を介して通信ネットワークから取得されてもよい。また、取得されたプログラムは、メモリ２０２及び外部記憶装置２０３のどちらに格納されてもよい。
【００４９】
なお、ハッシュ値生成装置１００を実現するためのハードウェア構成は図２に示すものに限定されず、１チップマイコンなどを用いても実現することができる。また、本実施形態では、全体制御部１２１、メッセージブロック化部１２２、ラウンド定数生成部１２３、ラウンド鍵生成部１２４及び撹拌部１２５をプログラムによって実現しているが、本発明はこれに限定されず、同一の機能を有する専用のハードウェア及び回路を用いてもよい。
【００５０】
ここで、ハッシュ値の算出方法の概要について説明する。
【００５１】
図３は、本発明の実施形態におけるハッシュ値の算出方法の一例を示す説明図である。
【００５２】
まず、ハッシュ値生成装置１００は、入力部１３０を介して、処理対象であるメッセージＭの入力を受け付けると、全体制御部１２１が、メッセージブロック化部１２２にメッセージＭを入力する。
【００５３】
メッセージブロック化部１２２は、メッセージＭに対してパディングを行い、８０ビット毎のメッセージブロックＭiに分割する。本実施形態では、メッセージＭは、ｋ＋１個のメッセージブロック（Ｍ'0，…，Ｍ'k）に分割される。
【００５４】
次に、全体制御部１２１は、初期値記憶領域１１１に格納される算出値の初期値Ｈ-1と、ブロック化されたメッセージブロックＭ'0とをブロック暗号ｆEに入力し、平文ラウンド値ｈ0、ｈ1を算出する。全体制御部１２１は、平文ラウンド値ｈ0、ｈ1を算出値として出力する。
【００５５】
ここで、ブロック暗号ｆEを用いた処理は、後述するように、ラウンド定数生成部１２３、ラウンド鍵生成部１２４及び撹拌部１２５によって実行される。
【００５６】
全体制御部１２１は、出力された算出値と、次のメッセージブロックＭ'1とをブロック暗号ｆEに入力し、次の平文ラウンド値を算出する。なお、算出された算出値は、算出値記憶領域１１５に格納される。
【００５７】
全体制御部１２１は、前述した処理を繰り返し実行することによって、平文ラウンド値を更新する。
【００５８】
全体制御部１２１は、更新された平文ラウンド値と、最後のメッセージブロックＭ'kと、をブロック暗号ｆEに入力し、ハッシュ値Ｈkを算出する。算出されたハッシュ値Ｈkは、ハッシュ値記憶領域１１６に格納される。
【００５９】
なお、本発明におけるハッシュ値の算出処理（方法）は、図３に示した算出処理（方法）に限定されるわけではなく、ブロック暗号ｆEを利用すれば、どのようなものであってもよい。
【００６０】
図４は、本発明の実施形態におけるハッシュ値生成装置１００が実行するハッシュ値の生成処理を説明するフローチャートである。
【００６１】
まず、ハッシュ値生成装置１００は、入力部１３０を介して処理対象となるメッセージＭを取得すると処理を開始する（ステップＳ１１０）。
【００６２】
ハッシュ値生成装置１００は、取得したメッセージＭを所定のデータ長のメッセージブロックに分割する（ステップＳ１１２）。具体的には、メッセージブロック化部１２２が、メッセージＭを所定のデータ長に分割して、分割されたメッセージに対してパディングを行って、ｋ＋１個のメッセージブロックＭ'iを生成する。本実施形態では、メッセージブロック化部１２２は、メッセージＭを５１２ビットのデータ長のメッセージブロックＭ'iに分割するものとする。
【００６３】
ハッシュ値生成装置１００は、記憶部１１０を初期化する（ステップＳ１１４）。具体的には、全体制御部１２１が、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３、平文ラウンド値記憶領域１１４、算出値記憶領域１１５及びハッシュ値記憶領域１１６に格納される情報をリセットする。すなわち、全てのビット値が「０」に設定される。
【００６４】
ハッシュ値生成装置１００は、メッセージブロックＭ'iのカウンタであるメッセージカウンタｉの値を初期化する（ステップＳ１１６）。具体的には、全体制御部１２１が、メッセージカウンタｉの値に「０」を設定する。なお、メッセージカウンタｉは、記憶部１１０に格納されるものとする。
【００６５】
ハッシュ値生成装置１００は、全てのメッセージブロックＭ'iに対して処理が完了したか否かを判定する（ステップＳ１１８）。具体的には、全体制御部１２１が、ｉ＝ｋを満たすか否かを判定する。
【００６６】
ｉ＝ｋを満たさないと判定された場合、すなわち、ステップＳ１１８の判定結果がＮｏである場合、ハッシュ値生成装置１００は、ステップＳ１２０の処理に進む。一方、ｉ＝ｋを満たすと判定された場合、すなわち、ステップＳ１１８の判定結果がＹｅｓである場合、ハッシュ値生成装置１００は、ステップＳ１３２の処理に進む。
【００６７】
全てのメッセージブロックＭ'iに対して処理が完了していないと判定された場合、ハッシュ値生成装置１００は、ラウンドのカウンタであるラウンドカウンタｒを初期化する（ステップＳ１２０）。具体的には、全体制御部１２１が、ラウンドカウンタｒの値に「０」を設定する。
【００６８】
ハッシュ値生成装置１００は、全てのラウンドの処理が完了したか否かを判定する（ステップＳ１２２）。具体的には、全体制御部１２１が、ラウンドカウンタｒの値が、予め設定されたラウンド数Ｒに対して、ｒ＝Ｒ＋１を満たすか否かを判定する。
【００６９】
ｒ＝Ｒ＋１を満たすと判定された場合、すなわち、ステップＳ１２２の判定結果がＹＥＳの場合、ハッシュ値生成装置１００は、ステップＳ１２８の処理に進む。一方、ｒ＝Ｒ＋１を満たさないと判定された場合、すなわち、ステップＳ１２２の判定結果がＮＯの場合、ハッシュ値生成装置１００は、ステップＳ１２４の処理に進む。
【００７０】
全てのラウンドの処理が完了していないと判定された場合、ハッシュ値生成装置１００は、メッセージブロックＭ'iに対する所定のラウンドの処理を実行する（ステップＳ１２４）。具体的には、ラウンド定数生成部１２３、ラウンド鍵生成部１２４及び撹拌部１２５が、ブロック暗号ｆEを用いて、ラウンド定数、鍵ラウンド値及び平文ラウンド値を算出し、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３及び平文ラウンド値記憶領域１１４に格納される情報を更新する。
【００７１】
次に、ハッシュ値生成装置１００は、ラウンドカウンタｒを更新し（ステップＳ１２６）、ステップＳ１２２に戻り、次のラウンドの処理を実行する。具体的には、全体制御部１２１が、現在のラウンドカウンタｒの値に「１」をインクリメントしたものを新たなラウンドカウンタｒの値とする。
【００７２】
本実施形態では、ハッシュ値生成装置１００は、一つのメッセージブロックＭ'iに対して、ラウンドにおける処理を繰り返し実行する。
【００７３】
ステップＳ１２２において、全てのラウンドの処理が完了したと判定された場合、ハッシュ値生成装置１００は、算出値記憶領域１１５を更新する（ステップＳ１２８）。具体的には、全体制御部１２１が、平文ラウンド値記憶領域１１４に格納される平文ラウンド値に基づいて算出値を算出し、算出値記憶領域１１５に格納される情報を更新する。
【００７４】
ハッシュ値生成装置１００は、メッセージカウンタｉを更新して（ステップＳ１３０）、ステップＳ１１８に戻り、同様の処理を実行する。具体的には、全体制御部１２１が、メッセージカウンタｉの値に「１」をインクリメントしたものを新たなメッセージカウンタｉの値とする。
【００７５】
ステップＳ１１８において、全てのメッセージブロックＭ'iに対して処理が完了したと判定された場合、ハッシュ値生成装置１００は、ハッシュ値を算出して処理を終了する（ステップＳ１３２）。具体的には、全体制御部１２１が、ラウンドカウンタｒに初期値「０」を設定し、また、平文ラウンド値記憶領域１１４に格納される平文ラウンド値に基づいてハッシュ値を算出し、ハッシュ値記憶領域１１６に格納される情報を更新する。
【００７６】
図５は、本発明の実施形態におけるブロック暗号ｆEにおける処理の概要を示す説明図である。
【００７７】
ブロック暗号ｆEは、複数のラウンドを含み、各ラウンドでは鍵スケジューリング処理及び攪拌処理が実行される。ｒ＝ｉにおける鍵スケジューリング処理では、ラウンド定数Ｃ(i)及び算出値を鍵ラウンド値変換関数ｆkに入力してラウンド鍵Ｋ(i)が算出される。また、ｒ＝ｉにおける攪拌処理では、ラウンド鍵Ｋ(i)、メッセージブロックＭ'i及び算出値を平文ラウンド値変換関数ｆRに入力して平文ラウンド値が算出される。以下では、ｒ＝ｉにおける平文ラウンド値をｘ(i)と表す。
【００７８】
ここでは、ラウンドｒ＝０、１の場合を例に、処理の流れについて説明する。
【００７９】
まず、ラウンド定数生成部１２３は、初期値記憶領域１１１に格納される定数ラウンド値の初期値ｃ(-1)を取得し、取得した定数ラウンド値ｃ(-1)を線形変換関数ｆcに入力することによって、定数ラウンド値ｃ(0)を算出する。ここで、線形変換関数ｆcは、図６に示すような変換を行う関数である。
【００８０】
さらに、ラウンド定数生成部１２３は、算出された定数ラウンド値ｃ(0)の下位１６ビットを、ｒ＝０におけるラウンド定数Ｃ(0)として算出する。ラウンド定数生成部１２３は、算出された定数ラウンド値ｃ(0)を定数ラウンド値記憶領域１１２に格納し、ラウンド定数Ｃ(0)をラウンド鍵生成部１２４に出力する。
【００８１】
次に、ラウンド鍵生成部１２４は、ブロック暗号ｆEに入力されたメッセージブロックがＭ'0であるため、初期値記憶領域１１１に格納される算出値の初期値ｈ0、ｈ1を取得する。なお、メッセージブロックがＭ'0以外の場合には、算出値記憶領域１１５に格納される算出値が取得される。なお、算出値記憶領域１１５には、一つ前のラウンドにおいて算出された算出値が格納される。
【００８２】
ラウンド鍵生成部１２４は、ラウンド定数Ｃ(0)、及び算出値の初期値ｈ0を鍵ラウンド値変換関数ｆKに入力して鍵ラウンド値ｋ(0)を算出する。
【００８３】
ここで、鍵ラウンド値変換関数ｆKについて説明する。
【００８４】
図７は、本発明の実施形態における鍵ラウンド値変換関数ｆKを示す説明図である。
【００８５】
鍵ラウンド値変換関数ｆkは、第ｒ−１ラウンドの鍵ラウンド値ｋ(r-1)を５分割（ここでは、１６ビットに分割）した分割データｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、ｋ4(r-1)を、それぞれ、ｋ0(r)、ｋ1(r)、ｋ2(r)、ｋ3(r)、ｋ4(r)に変換する。さらに、鍵ラウンド値変換関数ｆkは、ｋ0(r)、ｋ1(r)、ｋ2(r)、ｋ3(r)、ｋ4(r)を連結することによって、第ｒラウンドの鍵ラウンド値ｋ(r)を算出する。ただし、ｒ＝０の場合、鍵ラウンド値ｋ(r-1)は、初期値記憶領域１１１に格納される算出値の初期値とする。
【００８６】
具体的には、鍵ラウンド値変換関数ｆkでは、まず、ラウンド鍵生成部１２４が、鍵ラウンド値記憶領域１１３に格納される第ｒ−１ラウンドの鍵ラウンド値ｋ(r-1)を５つに分割し、ｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、ｋ4(r-1)を出力する。
【００８７】
次に、ラウンド鍵生成部１２４は、分割データｋ0(r-1)、ｋ1(r-1)、ｋ2(r-1)、ｋ3(r-1)、をそれぞれｋ1(r)、ｋ2(r)、ｋ3(r)、ｋ4(r)として出力する。
【００８８】
次に、ラウンド鍵生成部１２４は、ラウンド定数生成部１２３によって生成されたラウンド定数Ｃ(r)と第ｒ−１ラウンドのラウンド鍵の内のｋ3(r-1)との排他的論理和の値ａHを関数Ｆkに入力して、出力値ｂHを算出する。なお、出力値ｂHは下式（８）に示すように表される。
【数８】
2013076854.tif 000010
【００８９】
ラウンド鍵生成部１２４は、出力値ｂHとｋ4(r-1)との排他的論理和を算出し、算出された値をｋ0(r)として出力する。
【００９０】
ラウンド鍵生成部１２４は、以上のようにして算出されたｋ0(r)、ｋ1(r)、ｋ2(r)、ｋ3(r)、ｋ4(r)を連結して第ｒラウンドの鍵ラウンド値ｋ(r)として鍵ラウンド値記憶領域１１３に格納する。このとき、鍵ラウンド値記憶領域１１３に格納される第ｒ−１ラウンドの鍵ラウンド値ｋ(r-1)は上書きされる。
【００９１】
また、ラウンド鍵生成部１２４は、第ｒラウンドの鍵ラウンド値ｋ(r)の内のｋ1(r)を、第ｒラウンドのラウンド鍵Ｋ(r)として、撹拌部１２５に出力する。
【００９２】
次に、ラウンド鍵生成部１２４が使用する関数ＦKについて説明する。ここでは、関数ＦKへの入力値をＸ、関数ＦKからの出力値をＹとする。また、本実施形態において、Ｘ及びＹは１６ビットのデータである。
【００９３】
関数ＦKは、非線形な変換を行う関数であり、関数ＦKでは、Ｘを８ビット毎のサブデータ（ｓ0，ｓ1）に分割して、分割された各サブデータを下式（９）及び下式（１０）に示すように非線形変換が行われる。ここで、変換後のサブデータをｓ'0、ｓ'1とする。また、ｑ1及びｑ2は自然数とする。関数ＦKは、最後に、算出されたサブデータｓ'0、ｓ'1を連結して、出力値Ｙを出力する。
【数９】
2013076854.tif 000011
【数１０】
2013076854.tif 000012
ここで、「＞＞＞ｑ1」はｑ1ビットの右巡回シフトを示し、プラス記号は算術加算を示す。
【００９４】
以上が鍵ラウンド値変換関数ｆKの説明である。図５の説明に戻る。
【００９５】
ラウンド鍵生成部１２４は、前述したような処理によって算出された鍵ラウンド値ｋ(0)の内のｋ0(0)を、ラウンドｒ＝０のラウンド鍵Ｋ(0)として算出する。また、ラウンド鍵生成部１２４は、鍵ラウンド値ｋ(0)を鍵ラウンド値記憶領域１１３に格納し、ラウンド鍵Ｋ(0)を撹拌部１２５に出力する。
【００９６】
撹拌部１２５は、ブロック暗号ｆEに入力されたメッセージブロックＭ'iと初期値ｈ1とを平文ラウンド値変換関数ｆRに入力するによって、ｒ＝０における平文ラウンド値ｘ(0)を算出し、平文ラウンド値記憶領域１１４に格納する。
【００９７】
以上が、第０ラウンドの処理である。
【００９８】
ここで、平文ラウンド値変換関数ｆRについて説明する。
【００９９】
図８は、本発明の実施形態における平文ラウンド値変換関数ｆRを示す説明図である。
【０１００】
平文ラウンド値変換関数ｆRは、第ｒ−１ラウンドの平文ラウンド値ｘ(r-1)を５分割（ここでは、各々３２ビット）した分割データであるｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)、ｘ4(r-1)を、それぞれ、ｘ0(r)、ｘ1(r)、ｘ2(r)、ｘ3(r)、ｘ4(r)に変換する。さらに、平文ラウンド値変換関数ｆRは、変換された値を連結することによって、第ｒラウンドの平文ラウンド値ｘ(r)を生成する。ただし、ｒ＝０の場合、メッセージブロックＭ'iと算出値ｈ1とを連結した値が平文ラウンド値ｘ(r-1)となる。
【０１０１】
具体的には、平文ラウンド値変換関数ｆRでは、まず、撹拌部１２５が、平文ラウンド値記憶領域１１４に格納される第ｒ−１ラウンドの平文ラウンド値を５つに分割し、ｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)、ｘ4(r-1)を出力する。
【０１０２】
次に、撹拌部１２５は、ｘ0(r-1)、ｘ1(r-1)、ｘ2(r-1)、ｘ3(r-1)をそれぞれ第ｒラウンドの平文ラウンド値の内のｘ1(r)、ｘ2(r)、ｘ3(r)、ｘ4(r)として出力する。
【０１０３】
次に、撹拌部１２５は、ラウンド鍵生成部１２４によって生成されたラウンド鍵Ｋ(r)を用いてＳを生成し、当該Ｓと第ｒ−１ラウンドの平文ラウンド値の内のｘ3(r-1)との排他的論理和の値ｐを、関数ＦRに入力して出力値ｑを算出する。Ｓは、３２ビットのデータであり、上位１６ビットがラウンド鍵Ｋ(r)の値、下位１６ビットがすべて０の値を有する。なお、値ｑは下式（１１）に示すように表される。
【数１１】
2013076854.tif 000013
【０１０４】
撹拌部１２５は、値ｑと、第ｒ−１ラウンドの平文ラウンド値の内のｘ4(r-1)との排他的論理和を算出し、算出された値を第ｒラウンドの平文ラウンド鍵のｘ0(r)とする。
【０１０５】
そして、撹拌部１２５は、以上のようにして算出されたｘ0(r)、ｘ1(r)、ｘ2(r)、ｘ3(r)、ｘ4(r)を連結して第ｒラウンドの平文ラウンド値ｘ(r)として平文ラウンド値記憶領域１１４に格納する。このとき、平文ラウンド値記憶領域１１４に格納される第ｒ−１ラウンドの平文ラウンド値ｘ(r-1)は上書きされる。
【０１０６】
なお、関数ＦRの詳細については図９及び図１０を用いて後述する。以上が、平文ラウンド値変換関数ｆRの説明である。次に、ｒ＝１の場合の処理の流れについて説明する。
【０１０７】
ｒ＝１において、ラウンド定数生成部１２３は、定数ラウンド値記憶領域１１２に格納される定数ラウンド値ｃ(0)と鍵ラウンド値記憶領域１１３に格納される鍵ラウンド値ｋ(0)とを線形変換関数ｆcに入力することによって、ラウンドｒ＝１における定数ラウンド値ｃ(1)を算出する。ラウンド定数生成部１２３は、ラウンド定数ｃ(1)の下位１６ビットを、ｒ＝１におけるラウンド定数Ｃ(1)として算出する。
【０１０８】
ラウンド定数生成部１２３は、算出された定数ラウンド値ｃ(1)を定数ラウンド値記憶領域１１２に格納し、ラウンド定数Ｃ(1)をラウンド鍵生成部１２４に出力する。このとき、定数ラウンド値記憶領域１１２に格納される定数ラウンド値ｃ(0)は上書きされる。
【０１０９】
次に、ラウンド鍵生成部１２４は、鍵ラウンド値記憶領域１１３に格納される鍵ラウンド値ｋ(0)を鍵ラウンド値変換関数ｆKに入力することによって、ｒ＝１における鍵ラウンド値ｋ(1)を算出する。また、ラウンド鍵生成部１２４は、鍵ラウンド値ｋ(1)の内のｋ0(1)を、ｒ＝１のラウンド鍵Ｋ(1)として算出する。
【０１１０】
ラウンド鍵生成部１２４は、算出された鍵ラウンド値ｋ(1)を鍵ラウンド値記憶領域１１３に格納し、ラウンド鍵Ｋ(1)を撹拌部１２５に出力する。このとき、鍵ラウンド値記憶領域１１３に格納される鍵ラウンド値ｋ(0)は上書きされる。
【０１１１】
次に、撹拌部１２５は、平文ラウンド値記憶領域１１４に格納される平文ラウンド値ｘ(0)を平文ラウンド値変換関数ｆRに入力することによって、ｒ＝１における平文ラウンド値ｘ(1)を算出する。また、撹拌部１２５は、算出された平文ラウンド値ｘ(1)を平文ラウンド値記憶領域１１４に格納する。このとき、平文ラウンド値記憶領域１１４に格納される平文ラウンド値ｘ(0)は上書きされる。
【０１１２】
以上が、第１ラウンドの処理である。第２ラウンド以下の処理は、同一の処理であるため説明を省略する。ブロック暗号ｆEでは、ｒ＝ｋまで処理が繰り返し実行される。
【０１１３】
次に、関数ＦRについて説明する。
【０１１４】
図９は、本発明の実施形態における関数ＦRを示す説明図である。
【０１１５】
関数ＦRは、下式（１２）に示すように、非線形変換γRをＴ回、線形変換θRをＮ回行う合成関数である。
【数１２】
2013076854.tif 000014
【０１１６】
ここで、関数ＦRへの入力をＸ、関数ＦRからの出力をＹとして説明する。本実施形態においては、Ｘ及びＹは、３２ビットのデータである。なお、図７に示す例では、入力Ｘは排他的論理和ｐに対応し、出力Ｙは出力ｑに対応する。
【０１１７】
まず、非線形変換γRでは、値Ｘを１６ビットのサブデータ（ｓ0，ｓ1）に分割して、分割された各サブデータを、下式（１３）に示すように関数ＦKを用いて非線形変換を行う。ここで、変換後のサブデータをｓ'0，ｓ'1とする。
【数１３】
2013076854.tif 000015
【０１１８】
次に、線形変換θRでは、下式（１４）及び下式（１５）に示すように、非線形変換γRによって変換されたサブデータ（ｓ'0，ｓ'1）の入替えを行う。なお、式（１４）及び式（１５）は一例であって、他の入替え方式を採用してもよい。ここで、変換後のサブデータを（ｙ0，ｙ1）とする。ここで、ｑ3及びｑ4は自然数とする。
【数１４】
2013076854.tif 000016
【数１５】
2013076854.tif 000017
【０１１９】
そして、算出されたサブデータ（ｙ0，ｙ1）を連結したものを、関数ＦRの出力Ｙとする。
【０１２０】
なお、関数ＦRにおける非線形変換γRと、線形変換θRとの適用回数については、それぞれ適宜変更可能である。
【０１２１】
図１０は、本発明の実施形態における関数ＦRの処理の流れを説明するフローチャートである。
【０１２２】
ハッシュ値生成装置１００は、３２ビットの入力値Ｘを受け付けると（ステップＳ２１０）、当該入力値Ｘを２つのビットデータに分割する（ステップＳ２１２）。具体的には、撹拌部１２５が、入力値Ｘの上位１６ビットのビットデータｓ0と、下位１６ビットのビットデータｓ1とに分割する。以下では、上位１６ビットのビットデータを上位ビットデータｓ0と記載し、下位１６ビットのビットデータを下位ビットデータｓ1と記載する。
【０１２３】
ハッシュ値生成装置１００は、それぞれのビットデータを関数ＦKに入力して、ビットデータを変換する（ステップＳ２１４）。関数ＦKを用いた変換処理では、図７及び図９において説明したような処理が実行される。
【０１２４】
ハッシュ値生成装置１００は、上位ビットデータｓ'0に巡回シフトを適用したビットデータと、下位ビットデータｓ'1との排他的論理和の値ｙ1を算出する（ステップＳ２１６）。また、ハッシュ値生成装置１００は、値ｙ1に巡回シフトを適用したビットデータと、上位ビットデータｓ'0との排他的論理和の値ｙ0を算出する（ステップＳ２１８）。
【０１２５】
ハッシュ値生成装置１００は、ビットデータｙ0及びｙ1を連結して出力Ｙを算出する（ステップＳ２２０）。
【０１２６】
以上のように、本発明では、１６０ビットにおけるブロック暗号を用いている。本発明によれば、算術加算による非線形変換処理と巡回シフト変換による線型変換処理との組み合わせ処理を複数回実行しているため、理論的安全性を確保する共に、Ｓｂｏｘを用いないためハッシュ値を生成するプログラムのコードを小さくすることができる。また、本発明では、入力データを１６ビット又は８ビットに分割して、ハッシュ値を算出できるため、汎用のＰＣ及びサーバ以外の組み込み機器等に適用することができる。
【符号の説明】
【０１２７】
１００  ハッシュ値生成装置
１１０  記憶部
１１１  初期値記憶領域
１１２  定数ラウンド値記憶領域
１１３  鍵ラウンド値記憶領域
１１４  平文ラウンド値記憶領域
１１５  算出値記憶領域
１１６  ハッシュ値記憶領域
１２０  制御部
１２１  全体制御部
１２２  メッセージブロック化部
１２３  ラウンド定数生成部
１２４  ラウンド鍵生成部
１２５  撹拌部
１３０  入力部
１４０  出力部
２０１  プロセッサ
２０２  メモリ
２０３  外部記憶装置
２０５  通信装置
２０６  入力装置
２０７  出力装置
２０８  読書装置
２１０  記憶媒体
【図１】
2013076854.tif 000018
【図２】
2013076854.tif 000019
【図３】
2013076854.tif 000020
【図４】
2013076854.tif 000021
【図５】
2013076854.tif 000022
【図６】
2013076854.tif 000023
【図７】
2013076854.tif 000024
【図８】
2013076854.tif 000025
【図９】
2013076854.tif 000026
【図１０】
2013076854.tif 000027