(57)【要約】【課題】ＳＰＲ性あるいはｐＳＰＲ性を満たす圧縮関数を用いて、ｅＴＣＲ性を満たすハッシュ関数を構成する。【解決手段】並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、圧縮関数を計算する。並列処理部１３０は、メッセージ入力部１１０が入力した入力メッセージＭと、ハッシュ鍵入力部１２０が入力した並列ハッシュ鍵Ｋ１とに基づいて、並列圧縮関数演算部１５０を呼び出して、複数の圧縮ビット列ｈｉを生成する。直列処理部１６０は、並列処理部１３０が生成した複数の圧縮ビット列ｈｉと、ハッシュ鍵入力部１２０が入力した直列ハッシュ鍵Ｋ２とに基づいて、直列圧縮関数演算部１８０を呼び出して、ハッシュ値Ｈを算出する。【選択図】図５
2009169316.tif 000002
【特許請求の範囲】
【請求項１】
データを処理する処理装置と、並列圧縮関数演算部と、直列圧縮関数演算部と、メッセージ入力部と、並列処理部と、直列処理部と、ハッシュ値出力部とを有し、
上記並列圧縮関数演算部は、上記処理装置を用いて、ａ１ビット（ただし、ａ１は２以上の所定の整数。）の入力ビット列を入力し、入力した入力ビット列に基づいてｂ１ビット（ただし、ｂ１は１以上ａ１未満の所定の整数。）の並列出力ビット列を生成し、
上記直列圧縮関数演算部は、上記処理装置を用いて、ａ２ビット（ただし、ａ２は１以上の所定の整数。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、上記ｂ２ビットの直列出力ビット列を生成し、
上記メッセージ入力部は、上記処理装置を用いて、Ｌ１ビット（ただし、Ｌ１は１以上の任意の整数。）のビット列を入力して入力メッセージＭとし、
上記並列処理部は、上記処理装置を用いて、上記メッセージ入力部が入力した入力メッセージＭに基づいて、上記ａ１ビットの複数の並列ビット列ｍ”を生成し、生成した複数の並列ビット列ｍ”それぞれを上記入力ビット列として上記並列圧縮関数演算部に入力し、上記並列圧縮関数演算部が入力した複数の並列ビット列ｍ”それぞれに対して生成した複数の並列出力ビット列を取得して複数の圧縮ビット列ｈとし、
上記直列処理部は、上記処理装置を用いて、上記並列処理部が取得した複数の圧縮ビット列ｈに基づいて、上記ａ２ビットの複数の直列ビット列ｙを生成し、生成した複数の直列ビット列ｙのうち少なくともいずれかの直列ビット列ｙと、上記直列ビット列ｙと異なる他の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算部に入力し、上記直列圧縮関数演算部が入力した直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記直列ビット列ｙに基づいて生成された中間ビット列ｃとし、取得した中間ビット列ｃのうちのいずれかをハッシュ値Ｈとし、
上記ハッシュ値出力部は、上記処理装置を用いて、上記直列処理部が取得したハッシュ値Ｈを出力する
ことを特徴とするハッシュ関数演算装置。
【請求項２】
上記ハッシュ関数演算装置は、更に、データを記憶する記憶装置と、直列初期値記憶部とを有し、
上記直列初期値記憶部は、上記記憶装置を用いて、上記ｂ２ビットのビット列を直列初期ビット列ＩＶとして記憶し、
上記直列処理部は、上記処理装置を用いて、生成した複数の直列ビット列ｙのうち最初の直列ビット列ｙと、上記直列初期値記憶部が記憶した直列初期ビット列ＩＶとに基づいて、上記最初の直列ビット列ｙを上記第一ビット列とし上記直列初期ビット列ＩＶを上記第二ビット列として上記直列圧縮関数演算部に入力し、上記直列圧縮関数演算部が入力した最初の直列ビット列ｙ及び直列初期ビット列ＩＶに対して生成した直列出力ビット列を取得して上記最初の直列ビット列ｙに基づいて生成された中間ビット列ｃとし、生成した複数の直列ビット列ｙのうち最初以外の直列ビット列ｙと、上記最初以外の直列ビット列ｙより一つ前の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記最初以外の直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算部に入力し、上記直列圧縮関数演算部が入力した最初以外の直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記最初以外の直列ビット列ｙに基づいて生成された中間ビット列ｃとし、上記複数の直列ビット列ｙのうち最後の直列ビット列ｙに基づいて生成された中間ビット列ｃをハッシュ値Ｈとする
ことを特徴とする請求項１に記載のハッシュ関数演算装置。
【請求項３】
上記並列処理部は、並列詰め物生成部と、並列詰め物結合部と、並列分割部と、並列生成部とを有し、
上記並列詰め物生成部は、上記処理装置を用いて、上記メッセージ入力部が入力した入力メッセージＭに基づいて、ｎ１ビット（ただし、ｎ１は１以上の整数で、ｎ１＋Ｌ１が整数ｄ１の整数倍。Ｌ１は上記入力メッセージＭのビット数。上記整数ｄ１は１以上の所定の整数。）のビット列を生成して並列詰め物Ｐ１とし、
上記並列詰め物結合部は、上記処理装置を用いて、上記メッセージ入力部が入力した入力メッセージＭと、上記並列詰め物生成部が生成した並列詰め物Ｐ１とに基づいて、上記入力メッセージＭと上記並列詰め物Ｐ１とを結合したビット列を生成して並列結合ビット列Ｍ＊とし、
上記並列分割部は、上記処理装置を用いて、上記並列詰め物結合部が生成した並列結合ビット列Ｍ＊に基づいて、上記並列結合ビット列Ｍ＊を上記ｄ１ビットごとに分割した複数のビット列を生成して複数の並列分割ビット列ｍとし、
上記並列生成部は、上記処理装置を用いて、上記並列分割部が生成した複数の並列分割ビット列ｍそれぞれに基づいて、上記複数の並列ビット列ｍ”を生成する
ことを特徴とする請求項１または請求項２に記載のハッシュ関数演算装置。
【請求項４】
上記ハッシュ関数演算装置は、更に、並列ハッシュ鍵入力部を有し、
上記並列ハッシュ鍵入力部は、上記処理装置を用いて、上記ｄ１ビットのビット列を入力して並列ハッシュ鍵Ｋ１とし、
上記並列生成部は、上記処理装置を用いて、上記並列ハッシュ鍵入力部が入力した並列ハッシュ鍵Ｋ１と、上記並列分割部が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記複数の並列ビット列ｍ”を生成する
ことを特徴とする請求項３に記載のハッシュ関数演算装置。
【請求項５】
上記並列生成部は、上記処理装置を用いて、上記並列ハッシュ鍵入力部が入力したハッシュ鍵Ｋ１と、上記並列分割部が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記ハッシュ鍵Ｋ１と上記並列分割ビット列ｍとの排他的論理和をそれぞれ算出して複数の並列撹乱ビット列ｍ’とし、算出した複数の並列撹乱ビット列ｍ’それぞれに基づいて、上記複数の並列撹乱ビット列ｍ’と所定の並列固定ビット列とを結合したビット列をそれぞれ生成して上記複数の並列ビット列ｍ”とする
ことを特徴とする請求項４に記載のハッシュ関数演算装置。
【請求項６】
上記並列生成部は、上記処理装置を用いて、上記複数の並列撹乱ビット列ｍ’と１ビットの並列固定ビット列とを結合したビット列をそれぞれ生成して上記複数の並列ビット列ｍ”とする
ことを特徴とする請求項５に記載のハッシュ関数演算装置。
【請求項７】
上記並列生成部は、上記処理装置を用いて、上記並列ハッシュ鍵入力部が入力したハッシュ鍵Ｋ１と、上記並列分割部が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記ハッシュ鍵Ｋ１と上記並列分割ビット列ｍとの排他的論理和をそれぞれ算出して複数の並列ビット列ｍ”とする
ことを特徴とする請求項４に記載のハッシュ関数演算装置。
【請求項８】
上記並列詰め物生成部は、上記処理装置を用いて、上記ｄ１個の連続した「０」を含む並列詰め物Ｐ１を生成する
ことを特徴とする請求項３乃至請求項７のいずれかに記載のハッシュ関数演算装置。
【請求項９】
上記並列詰め物生成部は、上記処理装置を用いて、上記入力メッセージＭのビット数Ｌ１をｅ１ビット（ただし、ｅ１は１以上の所定の整数。）の二進数で表現したビット列を含む並列詰め物Ｐ１を生成する
ことを特徴とする請求項３乃至請求項８のいずれかに記載のハッシュ関数演算装置。
【請求項１０】
上記直列処理部は、直列詰め物生成部と、直列詰め物結合部と、直列分割部とを有し、
上記直列詰め物生成部は、上記処理装置を用いて、上記メッセージ入力部が入力した入力メッセージＭに基づいて、ｎ２ビット（ただし、ｎ２は１以上の整数で、ｎ２＋Ｌ２が整数ｄ２の整数倍。Ｌ２は上記複数の圧縮ビット列ｈのビット数を合計した整数。上記整数ｄ２は１以上の所定の整数。）のビット列を生成して直列詰め物Ｐ２とし、
上記直列詰め物結合部は、上記処理装置を用いて、上記並列処理部が取得した複数の圧縮ビット列ｈと、上記直列詰め物生成部が生成した直列詰め物Ｐ２とに基づいて、上記複数の圧縮ビット列ｈと上記直列詰め物Ｐ２とを結合したビット列を生成して直列結合ビット列Ｈ＊とし、
上記直列分割部は、上記処理装置を用いて、上記直列詰め物結合部が生成した直列結合ビット列Ｈ＊に基づいて、上記複数の直列ビット列ｙを生成する
ことを特徴とする請求項１乃至請求項９のいずれかに記載のハッシュ関数演算装置。
【請求項１１】
上記直列分割部は、上記処理装置を用いて、上記直列詰め物結合部が生成した直列結合ビット列Ｈ＊に基づいて、上記直列結合ビット列Ｈ＊を上記ｄ２ビットごとに分割した複数のビット列を生成して上記複数の直列ビット列ｙとする
ことを特徴とする請求項１０に記載のハッシュ関数演算装置。
【請求項１２】
上記ハッシュ関数演算装置は、更に、直列ハッシュ鍵入力部を有し、
上記直列ハッシュ鍵入力部は、上記処理装置を用いて、上記ｄ２ビットのビット列を入力して直列ハッシュ鍵Ｋ２とし、
上記直列分割部は、上記処理装置を用いて、上記直列詰め物結合部が生成した直列結合ビット列Ｈ＊に基づいて、上記直列結合ビット列Ｈ＊を上記ｄ２ビットごとに分割した複数のビット列を生成して複数の直列分割ビット列ｘとし、上記直列ハッシュ鍵入力部が入力した直列ハッシュ鍵Ｋ２と、生成した複数の直列分割ビット列ｘそれぞれとに基づいて、上記複数の直列ビット列ｙを生成する
ことを特徴とする請求項１０に記載のハッシュ関数演算装置。
【請求項１３】
上記直列分割部は、上記処理装置を用いて、上記直列ハッシュ鍵入力部が入力したハッシュ鍵Ｋ２と、生成した複数の直列分割ビット列ｘそれぞれとに基づいて、上記ハッシュ鍵Ｋ２と上記直列分割ビット列ｘとの排他的論理和をそれぞれ算出して複数の直列ビット列ｙとする
ことを特徴とする請求項１２に記載のハッシュ関数演算装置。
【請求項１４】
上記直列詰め物生成部は、上記処理装置を用いて、上記ｄ２個の連続した「０」を含む直列詰め物Ｐ２を生成する
ことを特徴とする請求項１０乃至請求項１３のいずれかに記載のハッシュ関数演算装置。
【請求項１５】
上記直列詰め物生成部は、上記処理装置を用いて、上記入力メッセージＭのビット数Ｌ１をｅ２ビット（ただし、ｅ２は１以上の所定の整数。）の二進数で表現したビット列を含む直列詰め物Ｐ２を生成する
ことを特徴とする請求項１０乃至請求項１４のいずれかに記載のハッシュ関数演算装置。
【請求項１６】
上記直列詰め物生成部は、上記処理装置を用いて、上記ｄ２個の連続した「０」を含む直列第一詰め物ビット列と、上記入力メッセージＭのビット数Ｌ１をｅ２ビット（ただし、ｅ２は１以上の所定の整数。）の二進数で表現したビット列を含む直列第二詰め物ビット列とからなる直列詰め物Ｐ２を生成し、
上記直列詰め物結合部は、上記処理装置を用いて、上記並列処理部が取得した複数の圧縮ビット列ｈと、上記直列詰め物生成部が生成した直列詰め物Ｐ２に含まれる直列第一詰め物ビット列及び直列第二詰め物ビット列とに基づいて、上記直列第一詰め物ビット列と上記複数の圧縮ビット列ｈと上記直列第二詰め物ビット列とを結合したビット列を生成して直列結合ビット列Ｈ＊とする
ことを特徴とする請求項１０乃至請求項１３のいずれかに記載のハッシュ関数演算装置。
【請求項１７】
上記直列圧縮関数演算部は、上記処理装置を用いて、ａ２ビット（ただし、ａ２＝ａ１−ｂ１。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２＝ｂ１。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とを結合したビット列を生成して第三ビット列とし、生成した第三ビット列を上記入力ビット列として上記並列圧縮関数演算部に入力し、上記並列圧縮関数演算部が入力した第三ビット列に対して出力した並列出力ビット列を取得して上記直列出力ビット列とする
ことを特徴とする請求項１乃至請求項１６のいずれかに記載のハッシュ関数演算装置。
【請求項１８】
上記並列圧縮関数演算部は、上記処理装置を用いて、ＳＰＲ（Ｓｅｃｏｎｄ  Ｐｒｅｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）性圧縮関数及びｐＳＰＲ（ｐａｒｔｉａｌ−ＳＰＲ）性圧縮関数のいずれかを演算することにより、上記入力ビット列に基づいて上記並列出力ビット列を生成する
ことを特徴とする請求項１乃至請求項１７のいずれかに記載のハッシュ関数演算装置。
【請求項１９】
請求項１乃至請求項１８のいずれかに記載のハッシュ関数演算装置と、署名関数演算部と、署名出力部とを有し、
上記ハッシュ関数演算装置は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力し、
上記署名関数演算部は、上記ハッシュ値出力部が出力したハッシュ値Ｈに基づいて、署名ｓを生成し、
上記署名出力部は、上記署名関数演算部が生成した署名ｓを、上記署名対象メッセージに対する署名として出力する
ことを特徴とする署名装置。
【請求項２０】
並列ハッシュ鍵生成部と、請求項４乃至請求項７のいずれかに記載のハッシュ関数演算装置と、署名関数演算部と、署名出力部とを有し、
上記並列ハッシュ鍵生成部は、上記ｄ１ビットのビット列ｋ１をランダムに生成し、
上記メッセージ入力部は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力し、
上記並列ハッシュ鍵入力部は、上記並列ハッシュ鍵生成部が生成したビット列ｋ１を上記並列ハッシュ鍵Ｋ１として入力し、
上記署名関数演算部は、上記ハッシュ値出力部が出力したハッシュ値Ｈに基づいて、署名ｓを生成し、
上記署名出力部は、上記並列ハッシュ鍵生成部が生成したビット列ｋ１と、上記署名関数演算部が生成した署名ｓとの組を、上記署名対象メッセージに対する署名として出力する
ことを特徴とする署名装置。
【請求項２１】
直列ハッシュ鍵生成部と、請求項１２または請求項１３に記載のハッシュ関数演算装置と、署名関数演算部と、署名出力部とを有し、
上記直列ハッシュ鍵生成部は、上記ｄ２ビットのビット列ｋ２をランダムに生成し、
上記メッセージ入力部は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力し、
上記直列ハッシュ鍵入力部は、上記直列ハッシュ鍵生成部が生成したビット列ｋ２を上記直列ハッシュ鍵Ｋ２として入力し、
上記署名関数演算部は、上記ハッシュ値出力部が出力したハッシュ値Ｈに基づいて、署名ｓを生成し、
上記署名出力部は、上記直列ハッシュ鍵生成部が生成したビット列ｋ２と、上記署名関数演算部が生成した署名ｓとの組を、上記署名対象メッセージに対する署名として出力する
ことを特徴とする署名装置。
【請求項２２】
データを処理する処理装置を有するコンピュータを、請求項１乃至請求項１７のいずれかに記載のハッシュ関数演算装置として機能させることを特徴とするプログラム。
【請求項２３】
データを処理する処理装置を有するハッシュ関数演算装置がハッシュ値を計算するハッシュ関数演算方法において、
上記処理装置が、ａ１ビット（ただし、ａ１は２以上の所定の整数。）の入力ビット列を入力し、入力した入力ビット列に基づいてｂ１ビット（ただし、ｂ１は１以上ａ１以下の所定の整数。）の並列出力ビット列を生成する並列圧縮関数演算工程と、
上記処理装置が、ａ２ビット（ただし、ａ２は１以上の所定の整数。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、上記ｂ２ビットの直列出力ビット列を生成する直列圧縮関数演算工程とを有し、
上記処理装置が、Ｌ１ビット（ただし、Ｌ１は１以上の任意の整数。）のビット列を入力して入力メッセージＭとし、
上記処理装置が、入力した入力メッセージＭに基づいて、上記ａ１ビットの複数の並列ビット列ｍ”を生成し、
上記処理装置が、生成した複数の並列ビット列ｍ”それぞれを上記入力ビット列として上記並列圧縮関数演算工程を実行し、上記並列圧縮関数演算工程で入力した複数の並列ビット列ｍ”それぞれに対して生成した複数の並列出力ビット列を取得して複数の圧縮ビット列ｈとし、
上記処理装置が、取得した複数の圧縮ビット列ｈに基づいて、上記ａ２ビットの複数の直列ビット列ｙを生成し、
上記処理装置が、生成した複数の直列ビット列ｙのうち少なくともいずれかの直列ビット列ｙと、上記直列ビット列ｙと異なる他の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算工程を実行し、上記直列圧縮関数演算工程で入力した直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記直列ビット列ｙに基づいて生成された中間ビット列ｃとし、取得した中間ビット列ｃのうち少なくともいずれかをハッシュ値Ｈとし、
上記処理装置が、取得したハッシュ値Ｈを出力する
ことを特徴とするハッシュ関数演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、電子署名などに利用されるハッシュ関数を演算するハッシュ関数演算装置に関する。
【背景技術】
【０００２】
電子署名などに利用されるハッシュ関数は、ＣＲ（Ｃｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ）性を満たすことが要求される。近年、従来使われてきたＭＤ（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  Ａｌｇｏｒｉｔｈｍ）５やＳＨＡ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）−１などのハッシュ関数は、ＣＲ性を満たさないことが判明し、ＣＲ性を満たすハッシュ関数を構成することが困難であることが認識された。
そこで、電子署名などにおいては、ＣＲ性を満たすハッシュ関数を用いる代わりに、ＴＣＲ（Ｔａｒｇｅｔ  Ｃｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ）性あるいはｅＴＣＲ（ｅｎｈａｎｃｅｄ−ＴＣＲ）性を満たす鍵付きハッシュ関数を用いることが提案されている。ここで、ｅＴＣＲ性を満たす鍵付きハッシュ関数のほうが、ＴＣＲ性を満たす鍵付きハッシュ関数よりも効率的である。
【０００３】
ハッシュ関数は、通常、圧縮関数を用いて構成される。
非特許文献１には、ｅＳＰＲ（ｅｖａｌｕａｔｅｄ−ＳＰＲ）性を満たす圧縮関数を用いて、ｅＴＣＲ性を満たす鍵付きハッシュ関数を構成する方法が開示されている。
非特許文献２、非特許文献３、非特許文献４、非特許文献５には、ＴＣＲ性を満たす圧縮関数を用いて、ＴＣＲ性を満たす鍵付きハッシュ関数を構成する方法が開示されている。
また、非特許文献３には、ＳＰＲ（Ｓｅｃｏｎｄ  Ｐｒｅ−ｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）性を満たす圧縮関数を用いて、ＴＣＲ性を満たす鍵付きハッシュ関数を構成する方法が開示されている。
【非特許文献１】Ｓ．Ｈａｌｅｖｉ、Ｈ．Ｋｒａｗｃｚｙｋ「Ｓｔｒｅｎｇｔｈｅｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ｖｉａ  Ｒａｎｄｏｍｉｚｅｄ  Ｈａｓｈｉｎｇ」ＣＲＹＰＴＯ  ２００６、４１〜５９ページ。
【非特許文献２】Ｍ．Ｂｅｌｌａｒｅ、Ｐ．Ｒｏｇａｗａｙ「Ｃｏｌｌｉｓｉｏｎ−Ｒｅｓｉｓｔａｎｔ  Ｈａｓｈｉｎｇ：  Ｔｏｗａｒｄ  Ｍａｋｉｎｇ  ＵＷＯＨＦｓ  Ｐｒａｃｔｉｃａｌ」ＣＲＹＰＴＯ’９７、４７０〜４８４ページ。
【非特許文献３】Ｖ．Ｓｈｏｕｐ「Ａ  Ｃｏｍｐｏｓｉｔｉｏｎ  Ｔｈｅｏｒｅｍ  ｆｏｒ  Ｕｎｉｖｅｒｓａｌ  Ｏｎｅ−Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ」ＥＵＲＯＣＲＹＰＴ  ２０００、４４５〜４５２ページ。
【非特許文献４】Ｗ．Ｌｅｅ、Ｄ．Ｃｈａｎｇ、Ｓ．Ｌｅｅ、Ｓ．Ｈ．Ｓｕｎｇ、Ｍ．Ｎａｎｄｉ「Ｎｅｗ  Ｐａｒａｌｌｅｌ  Ｄｏｍａｉｎ  Ｅｘｔｅｎｄｅｒｓ  ｆｏｒ  ＵＯＷＨＦ」ＡＳＩＡＣＲＹＰＴ  ２００３、２０８〜２２７ページ。
【非特許文献５】Ｎ．Ｎａｎｄｉ「Ａ  Ｓｕｆｆｉｃｉｅｎｔ  Ｃｏｎｄｉｔｉｏｎ  ｆｏｒ  Ｏｐｔｉｍａｌ  Ｄｏｍａｉｎ  Ｅｘｔｅｎｄｅｒ  ｏｆ  ＵＯＷＨＦｓ」ＳＡＣ  ２００４、３４１〜３５４ページ。
【非特許文献６】Ｍ．Ｎａｏｒ、Ｍ．Ｙｕｎｇ「Ｕｎｉｖｅｒｓａｌ  Ｏｎｅ−Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ｔｈｅｉｒ  Ｃｒｙｐｔｇｒａｐｈｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ」ＳＴＯＣ’８９、３３−４３ページ。
【非特許文献７】Ｐ．Ｓａｒｋａｒ「Ｍａｓｋｉｎｇ  Ｂａｓｅｄ  Ｄｏｍａｉｎ  Ｅｘｔｅｎｄｅｒｓ  ｆｏｒ  ＵＯＷＨＦｓ：  Ｂｏｕｎｄｓ  ａｎｄ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ」ＡＳＩＡＣＲＹＰＴ  ２００４、１８７〜２００ページ。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一般に、ｅＳＰＲ性を満たす圧縮関数を構成することは、ＳＰＲ性あるいはｐＳＰＲ（ｐａｒｔｉａｌ−ＳＰＲ）性を満たす圧縮関数を構成するよりも難しい。
【０００５】
この発明は、例えば、上記のような課題を解決するためになされたものであり、ＳＰＲ性あるいはｐＳＰＲ性を満たす圧縮関数を用いて、ｅＴＣＲ性を満たすハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【０００６】
この発明にかかるハッシュ関数演算装置は、
データを処理する処理装置と、並列圧縮関数演算部と、直列圧縮関数演算部と、メッセージ入力部と、並列処理部と、直列処理部と、ハッシュ値出力部とを有し、
上記並列圧縮関数演算部は、上記処理装置を用いて、ａ１ビット（ただし、ａ１は２以上の所定の整数。）の入力ビット列を入力し、入力した入力ビット列に基づいてｂ１ビット（ただし、ｂ１は１以上ａ１未満の所定の整数。）の並列出力ビット列を生成し、
上記直列圧縮関数演算部は、上記処理装置を用いて、ａ２ビット（ただし、ａ２は１以上の所定の整数。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、上記ｂ２ビットの直列出力ビット列を生成し、
上記メッセージ入力部は、上記処理装置を用いて、Ｌ１ビット（ただし、Ｌ１は１以上の任意の整数。）のビット列を入力して入力メッセージＭとし、
上記並列処理部は、上記処理装置を用いて、上記メッセージ入力部が入力した入力メッセージＭに基づいて、上記ａ１ビットの複数の並列ビット列ｍ”を生成し、生成した複数の並列ビット列ｍ”それぞれを上記入力ビット列として上記並列圧縮関数演算部に入力し、上記並列圧縮関数演算部が入力した複数の並列ビット列ｍ”それぞれに対して生成した複数の並列出力ビット列を取得して複数の圧縮ビット列ｈとし、
上記直列処理部は、上記処理装置を用いて、上記並列処理部が取得した複数の圧縮ビット列ｈに基づいて、上記ａ２ビットの複数の直列ビット列ｙを生成し、生成した複数の直列ビット列ｙのうち少なくともいずれかの直列ビット列ｙと、上記直列ビット列ｙと異なる他の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算部に入力し、上記直列圧縮関数演算部が入力した直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記直列ビット列ｙに基づいて生成された中間ビット列ｃとし、取得した中間ビット列ｃのうちのいずれかをハッシュ値Ｈとし、
上記ハッシュ値出力部は、上記処理装置を用いて、上記直列処理部が取得したハッシュ値Ｈを出力することを特徴とする。
【発明の効果】
【０００７】
この発明にかかるハッシュ関数演算装置によれば、並列圧縮関数演算部及び直列圧縮関数演算部が計算する圧縮関数がＳＰＲ性あるいはｐＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
実施の形態１について、図１〜図１０を用いて説明する。
【０００９】
ハッシュ関数演算装置１００は、任意のビット数のビット列（以下「入力メッセージ」と呼ぶ。）と、所定のビット数のビット列（以下「ハッシュ鍵」と呼ぶ。）とを入力し、入力した入力メッセージとハッシュ鍵とに基づいて、所定のビット数のビット列（以下「鍵付きハッシュ値」と呼ぶ。）を算出する装置である。
ハッシュ関数演算装置１００は、例えば、署名装置や署名検証装置で用いられる。この実施の形態では、ハッシュ関数演算装置１００を署名装置や署名検証装置に用いる場合について説明するが、ハッシュ関数演算装置１００は、署名装置や署名検証装置以外のシステムで利用してもよい。
【００１０】
図１は、この実施の形態における署名装置８１０の構成の一例を示す全体構成図である。
署名装置８１０は、署名対象メッセージ入力部８１１、ハッシュ鍵生成部８１２、ハッシュ関数演算装置１００、署名関数演算部８１３、署名出力部８１４を有する。
【００１１】
署名対象メッセージ入力部８１１は、署名の対象であるビット列Ｍ（以下「署名対象メッセージ」と呼ぶ。）を入力する。
ハッシュ鍵生成部８１２は、所定のビット数のハッシュ鍵Ｋをランダムに生成する。
ハッシュ関数演算装置１００は、署名対象メッセージ入力部８１１が入力した署名対象メッセージＭと、ハッシュ鍵生成部８１２が生成したハッシュ鍵Ｋとに基づいて、鍵付きハッシュ値Ｈを算出する。
署名関数演算部８１３は、ハッシュ関数演算装置１００が算出した鍵付きハッシュ値Ｈに基づいて、署名ｓを生成する。例えば、署名関数演算部８１３は、署名者の秘密鍵を用いて、鍵付きハッシュ値Ｈを暗号化し、署名ｓとする。
署名出力部８１４は、ハッシュ鍵生成部８１２が生成したハッシュ鍵Ｋと、署名関数演算部８１３が生成した署名ｓとを、署名対象メッセージＭに対する署名として出力する。
【００１２】
図２は、この実施の形態における署名検証装置８２０の構成の一例を示す全体構成図である。
署名検証装置８２０は、署名対象メッセージ入力部８２１、署名入力部８２２、ハッシュ関数演算装置１００、署名復号演算部８２３、署名比較部８２４を有する。
【００１３】
署名対象メッセージ入力部８２１は、署名装置８１０により署名を付された署名対象メッセージＭを入力する。
署名入力部８２２は、署名装置８１０が署名対象メッセージＭに対する署名として出力したハッシュ鍵Ｋ及び署名ｓを入力する。
ハッシュ関数演算装置１００は、署名対象メッセージ入力部８２１が入力した署名対象メッセージＭと署名入力部８２２が入力したハッシュ鍵Ｋとに基づいて、鍵付きハッシュ値Ｈを算出する。
署名復号演算部８２３は、署名入力部８２２が入力した署名ｓに基づいて、復号ビット列Ｈ’を生成する。例えば、署名復号演算部８２３は、署名装置８１０が用いた署名者の秘密鍵に対応する公開鍵を用いて、署名ｓを復号し、復号ビット列Ｈ’とする。
署名比較部８２４は、ハッシュ関数演算装置１００が算出した鍵付きハッシュ値Ｈと、署名復号演算部８２３が生成した復号ビット列Ｈ’とを比較して、一致するか否かを判定する。鍵付きハッシュ値Ｈと復号ビット列Ｈ’とが一致した場合、署名比較部８２４は、署名が有効であると判定する。鍵付きハッシュ値Ｈと復号ビット列Ｈ’とが一致しない場合、署名比較部８２４は、署名が有効でないと判定する。署名比較部８２４は、判定結果を出力する。
【００１４】
図３は、この実施の形態における署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００の外観の一例を示す図である。
署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００は、システムユニット９１０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置９０１、キーボード９０２（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
システムユニット９１０は、コンピュータであり、ファクシミリ機９３２、電話器９３１とケーブルで接続され、また、ローカルエリアネットワーク９４２（ＬＡＮ）、ゲートウェイ９４１を介してインターネット９４０に接続されている。
【００１５】
図４は、この実施の形態における署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００のハードウェア資源の一例を示す図である。
署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、通信装置９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、スキャナ装置９０７、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。
通信装置９１５、キーボード９０２、スキャナ装置９０７、ＦＤＤ９０４などは、入力部、入力装置の一例である。
また、通信装置９１５、表示装置９０１、プリンタ装置９０６などは、出力部、出力装置の一例である。
【００１６】
通信装置９１５は、ファクシミリ機９３２、電話器９３１、ＬＡＮ９４２等に接続されている。通信装置９１５は、ＬＡＮ９４２に限らず、インターネット９４０、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。インターネット９４０或いはＩＳＤＮ等のＷＡＮに接続されている場合、ゲートウェイ９４１は不用となる。
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【００１７】
上記プログラム群９２３には、以下に述べる実施の形態の説明において「〜部」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明する情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリになどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、以下に述べる実施の形態の説明において説明するフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００１８】
また、以下に述べる実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、以下に述べる「〜部」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００１９】
図５は、この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図である。
ハッシュ関数演算装置１００は、メッセージ入力部１１０、ハッシュ鍵入力部１２０、並列処理部１３０、並列圧縮関数演算部１５０、直列処理部１６０、直列圧縮関数演算部１８０、ハッシュ値出力部１９０を有する。
【００２０】
並列圧縮関数演算部１５０は、ＣＰＵ９１１を用いて、並列処理部１３０から呼び出されて、圧縮関数を計算する。
並列圧縮関数演算部１５０は、ＣＰＵ９１１を用いて、ａ１ビット（ただし、ａ１は２以上の所定の整数。）のビット列（以下「入力ビット列」と呼ぶ。）を入力し、入力した入力ビット列に基づいて、ｂ１ビット（ただし、ｂ１は１以上の所定の整数。）のビット列（以下「並列出力ビット列」と呼ぶ。）を生成する。並列圧縮関数演算部１５０は、ＣＰＵ９１１を用いて、所定の圧縮関数により、入力ビット列を圧縮して並列出力ビット列を生成する。並列圧縮関数演算部１５０は、ＣＰＵ９１１を用いて、生成した並列出力ビット列を出力する。
【００２１】
直列圧縮関数演算部１８０は、ＣＰＵ９１１を用いて、直列処理部１６０から呼び出されて、圧縮関数を計算する。
直列圧縮関数演算部１８０は、ＣＰＵ９１１を用いて、ａ２ビット（ただし、ａ２は１以上の所定の整数。）のビット列（以下「第一ビット列」と呼ぶ。）と、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、ｂ２ビットのビット列（以下「直列出力ビット列」と呼ぶ。）を生成する。直列圧縮関数演算部１８０は、ＣＰＵ９１１を用いて、第一ビット列と第二ビット列とを結合してａ２＋ｂ２ビットのビット列（以下「第三ビット列」と呼ぶ。）を生成し、所定の圧縮関数により、生成した第三ビット列を圧縮して直列出力ビット列を生成する。直列圧縮関数演算部１８０は、ＣＰＵ９１１を用いて、生成した直列出力ビット列を出力する。
【００２２】
ここで、並列圧縮関数演算部１５０が使用する所定の圧縮関数と、直列圧縮関数演算部１８０が使用する所定の圧縮関数は、同じであってもよいし、異なっていてもよい。二つの圧縮関数が同じである場合、直列圧縮関数演算部１８０は、並列圧縮関数演算部１５０を呼び出すことにより、直列出力ビット列を生成してもよい。すなわち、直列圧縮関数演算部１８０は、ＣＰＵ９１１を用いて、生成した第三ビット列を並列圧縮関数演算部１５０に入力し、並列圧縮関数演算部１５０が入力した第三ビット列に対して出力した並列出力ビット列を取得して、直列出力ビット列としてもよい。
【００２３】
メッセージ入力部１１０は、ＣＰＵ９１１を用いて、入力メッセージＭを入力する。メッセージ入力部１１０は、ＲＡＭ９１４を用いて、入力した入力メッセージＭを記憶する。
【００２４】
ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、ａ１＋ａ２−ｋビット（ただし、ｋは１以上ａ１未満の所定の整数。）のハッシュ鍵Ｋを入力する。ハッシュ鍵入力部１２０が入力するハッシュ鍵Ｋは、ａ１−ｋビットのビット列Ｋ１（以下「並列ハッシュ鍵」と呼ぶ。）と、ａ２ビットのビット列Ｋ２（以下「直列ハッシュ鍵」）とが結合したビット列である。ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、並列ハッシュ鍵Ｋ１と直列ハッシュ鍵Ｋ２とを入力する。ハッシュ鍵入力部１２０は、ＲＡＭ９１４を用いて、入力した並列ハッシュ鍵Ｋ１及び直列ハッシュ鍵Ｋ２を記憶する。
【００２５】
並列処理部１３０は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭと、ハッシュ鍵入力部１２０が記憶した並列ハッシュ鍵Ｋ１とを入力する。並列処理部１３０は、入力した入力メッセージＭと並列ハッシュ鍵Ｋ１とに基づいて、複数の圧縮ビット列ｈｉ（ただし、ｉは１以上ｎ以下の整数。ｎは並列処理部１３０が生成する圧縮ビット列の数。）を生成する。並列処理部１３０は、ＣＰＵ９１１を用いて、入力メッセージＭ及び並列ハッシュ鍵Ｋ１から並列圧縮関数演算部１５０に入力する入力ビット列を生成し、生成した入力ビット列を並列圧縮関数演算部１５０に入力する。並列処理部１３０は、ＣＰＵ９１１を用いて、入力した入力ビット列に対して並列圧縮関数演算部１５０が出力した並列出力ビット列を取得する。並列処理部１３０は、ＣＰＵ９１１を用いて、取得した並列出力ビット列に基づいて、ｎ個の圧縮ビット列ｈｉを生成する。並列処理部１３０は、ＲＡＭ９１４を用いて、生成したｎ個の圧縮ビット列ｈｉを記憶する。
【００２６】
直列処理部１６０は、ＣＰＵ９１１を用いて、並列処理部１３０が記憶したｎ個の圧縮ビット列ｈｉと、ハッシュ鍵入力部１２０が記憶した直列ハッシュ鍵Ｋ２とを入力する。直列処理部１６０は、ＣＰＵ９１１を用いて、入力したｎ個の圧縮ビット列ｈｉと直列ハッシュ鍵Ｋ２とに基づいて、ハッシュ値Ｈを生成する。直列処理部１６０は、ＣＰＵ９１１を用いて、圧縮ビット列ｈｉ及び直列ハッシュ鍵Ｋ２から直列圧縮関数演算部１８０に入力する第一ビット列及び第二ビット列を生成し、生成した第一ビット列及び第二ビット列を直列圧縮関数演算部１８０に入力する。直列処理部１６０は、ＣＰＵ９１１を用いて、入力した第一ビット列及び第二ビット列に対して直列圧縮関数演算部１８０が出力した直列出力ビット列を取得する。直列処理部１６０は、ＣＰＵ９１１を用いて、取得した直列出力ビット列に基づいて、ハッシュ値Ｈを生成する。直列処理部１６０は、ＲＡＭ９１４を用いて、生成したハッシュ値Ｈを記憶する。
【００２７】
ハッシュ値出力部１９０は、ＣＰＵ９１１を用いて、直列処理部１６０が記憶したハッシュ値Ｈを入力する。ハッシュ値出力部１９０は、ＣＰＵ９１１を用いて、入力したハッシュ値Ｈを出力する。
【００２８】
図６は、この実施の形態における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図である。
【００２９】
並列処理部１３０は、並列詰め物生成部１３１、並列詰め物結合部１３２、並列分割部１３４、並列生成部１３５、並列圧縮部１３６を有する。
また、ハッシュ鍵入力部１２０は、並列ハッシュ鍵入力部１２１を有する。
また、ハッシュ関数演算装置１００は、並列固定記憶部１４３を有する。
【００３０】
並列ハッシュ鍵入力部１２１は、ＣＰＵ９１１を用いて、並列ハッシュ鍵Ｋ１を入力する。並列ハッシュ鍵入力部１２１は、ＲＡＭ９１４を用いて、入力した並列ハッシュ鍵Ｋ１を記憶する。
【００３１】
並列固定記憶部１４３は、ＲＯＭ９１３を用いて、ｋビットのビット列Ｆ（以下「並列固定ビット列」と呼ぶ。）をあらかじめ記憶している。並列固定ビット列Ｆは、あらかじめ定められた所定のビット列である。並列固定ビット列Ｆは、例えば、１ビットのビット列であり、「１」もしくは「０」である。
【００３２】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１−ｋより大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１−ｋの整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。なお、ａ１は、並列圧縮関数演算部１５０が入力する入力ビット列のビット数である。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットのビット列Ｐ１（以下「並列詰め物」と呼ぶ。）を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを「０」にした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１−ｋビットが「０」であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【００３３】
並列詰め物結合部１３２は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭと、並列詰め物生成部１３１が記憶した並列詰め物Ｐ１とを入力する。並列詰め物結合部１３２は、入力した入力メッセージＭと並列詰め物Ｐ１とに基づいて、入力メッセージＭと並列詰め物Ｐ１とを結合したビット列（以下「並列結合ビット列Ｍ＊」と呼ぶ。）を生成する。例えば、並列詰め物結合部１３２は、ＣＰＵ９１１を用いて、入力メッセージＭの後に、並列詰め物Ｐ１を結合して、並列結合ビット列Ｍ＊を生成する。並列詰め物結合部１３２は、ＲＡＭ９１４を用いて、生成した並列結合ビット列Ｍ＊を記憶する。
【００３４】
並列分割部１３４は、ＣＰＵ９１１を用いて、並列詰め物結合部１３２が記憶した並列結合ビット列Ｍ＊を入力する。並列分割部１３４は、ＣＰＵ９１１を用いて、入力した並列結合ビット列Ｍ＊に基づいて、並列結合ビット列Ｍ＊をａ１−ｋビットごとに分割した複数のビット列ｍｉ（以下「並列分割ビット列」と呼ぶ。）（ただし、ｉは１以上ｎ以下の整数。ｎは並列分割ビット列ｍｉの数。）を生成する。並列分割部１３４は、ＲＡＭ９１４を用いて、生成したｎ個の並列分割ビット列ｍｉを記憶する。
【００３５】
並列生成部１３５は、ＣＰＵ９１１を用いて、並列ハッシュ鍵入力部１２１が記憶した並列ハッシュ鍵Ｋ１と、並列固定記憶部１４３が記憶した並列固定ビット列Ｆと、並列分割部１３４が記憶したｎ個の並列分割ビット列ｍｉとを入力する。並列生成部１３５は、ＣＰＵ９１１を用いて、入力した並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉとに基づいて、並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉそれぞれとの間のビットごとの排他的論理和を取り、ｎ個のビット列ｍｉ’（以下「並列撹乱ビット列」と呼ぶ。）（ただし、ｉは１以上ｎ以下の整数。）を生成する。ここで、並列ハッシュ鍵Ｋ１及びｎ個の並列分割ビット列ｍｉは、それぞれａ１−ｋビットのビット列であり、並列生成部１３５が生成するｎ個の並列撹乱ビット列ｍｉ’も同じく、ａ１−ｋビットのビット列である。
並列生成部１３５は、ＣＰＵ９１１を用いて、生成したｎ個の並列撹乱ビット列ｍｉ’と、入力した並列固定ビット列Ｆとに基づいて、ｎ個の並列撹乱ビット列ｍｉ’それぞれと並列固定ビット列Ｆとを結合したｎ個のビット列ｍｉ”（以下「並列ビット列」と呼ぶ。）（ただし、ｉは１以上ｎ以下の整数。）を生成する。例えば、並列生成部１３５は、ＣＰＵ９１１を用いて、ｎ個の並列撹乱ビット列ｍｉ’それぞれの後に、並列固定ビット列Ｆを結合して、ｎ個の並列ビット列ｍｉ”を生成する。並列生成部１３５が生成するｎ個の並列ビット列ｍｉ”のビット数は、ａ１ビットである。
並列生成部１３５は、ＲＡＭ９１４を用いて、生成したｎ個の並列ビット列ｍｉ”を記憶する。
【００３６】
並列圧縮部１３６は、ＣＰＵ９１１を用いて、並列生成部１３５が記憶したｎ個の並列ビット列ｍｉ”を入力する。並列圧縮部１３６は、ＣＰＵ９１１を用いて、入力したｎ個の並列ビット列ｍｉ”に基づいて、ｎ個の並列ビット列ｍｉ”それぞれを入力ビット列として並列圧縮関数演算部１５０に入力する。並列圧縮部１３６は、ＣＰＵ９１１を用いて、入力したｎ個の並列ビット列ｍｉ”に対して並列圧縮関数演算部１５０が出力したｎ個の並列出力ビット列を取得して、ｎ個の圧縮ビット列ｈｉ（ただし、ｉは１以上ｎ以下の整数。）とする。ここで、並列圧縮部１３６が取得するｎ個の圧縮ビット列ｈｉは、それぞれｂ１ビットのビット列である。並列圧縮部１３６は、ＲＡＭ９１４を用いて、取得したｎ個の圧縮ビット列ｈｉを記憶する。
【００３７】
図７は、この実施の形態における直列処理部１６０の内部ブロックの一例を示す詳細ブロック構成図である。
直列処理部１６０は、直列詰め物生成部１６１、直列詰め物結合部１６２、直列分割部１６３、直列圧縮部１６６を有する。
また、ハッシュ鍵入力部１２０は、直列ハッシュ鍵入力部１２２を有する。
また、ハッシュ関数演算装置１００は、直列初期値記憶部１４２を有する。
【００３８】
直列ハッシュ鍵入力部１２２は、ＣＰＵ９１１を用いて、直列ハッシュ鍵Ｋ２を入力する。直列ハッシュ鍵入力部１２２は、ＲＡＭ９１４を用いて、入力した直列ハッシュ鍵Ｋ２を記憶する。
【００３９】
直列初期値記憶部１４２は、ＲＯＭ９１３を用いて、ｂ２ビットのビット列ＩＶ（以下「直列初期値ビット列」と呼ぶ。）をあらかじめ記憶している。直列初期値ビット列ＩＶは、あらかじめ定められた所定のビット列である。
【００４０】
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭと、並列圧縮部１３６が記憶した圧縮ビット列ｈｉの数ｎとを入力する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。なお、直列詰め物生成部１６１は、入力メッセージＭのビット数Ｌ１を算出する代わりに、並列詰め物生成部１３１が算出した入力メッセージＭのビット数Ｌ１を取得してもよい。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、入力した圧縮ビット列ｈｉの数ｎに基づいて、ｎ個の圧縮ビット列ｈｉのビット数を合計した整数Ｌ２を算出する。すなわち、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、圧縮ビット列ｈｉのビット数ｂ１と圧縮ビット列ｈｉの数ｎとの積を算出して、整数Ｌ２とする。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数Ｌ２に基づいて、以下の条件を満たす整数ｎ２を算出する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、整数ｎ２がａ２＋ｅ２より大きく、かつ、整数ｎ２と整数Ｌ２との和ｎ２＋Ｌ２がａ２の整数倍となる整数ｎ２のうち、最小の整数ｎ２を算出する。なお、ａ２は、直列圧縮関数演算部１８０が入力する第一ビット列のビット数である。また、ｅ２は、１以上の所定の整数であり、例えば、６４である。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数ｎ２に基づいて、ｎ２ビットのビット列Ｐ２（以下「直列詰め物」と呼ぶ。）を生成する。例えば、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、ａ２ビットのビット列（以下「直列第一詰め物ビット列」と呼ぶ。）と、ｎ２−ａ２ビットのビット列（以下「直列第二詰め物ビット列」と呼ぶ。）とからなる直列詰め物Ｐ２を生成する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、直列第一詰め物ビット列として、すべてのビットが「０」であるビット列を生成する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、直列第二詰め物ビット列として、最初のビットを「１」、残りのビットを、入力メッセージＭのビット数Ｌ１を二進数で表現したビット列としたビット列を生成する。ここで、直列詰め物生成部１６１が整数ｎ２を算出する際の条件より、直列第二詰め物ビット列は、ｅ２ビットより長い。
なお、直列詰め物生成部１６１が生成する直列第二詰め物ビット列は、最後からｅ２ビットが入力メッセージＭのビット数Ｌ１を表わす二進数であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
直列詰め物生成部１６１は、ＲＡＭ９１４を用いて、生成した直列第一詰め物ビット列と直列第二詰め物ビット列とを記憶する。
【００４１】
直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、並列圧縮部１３６が記憶したｎ個の圧縮ビット列ｈｉと、直列詰め物生成部１６１が生成した直列第一詰め物ビット列及び直列第二詰め物ビット列とを入力する。直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、入力したｎ個の圧縮ビット列ｈｉと直列第一詰め物ビット列と直列第二詰め物ビット列とに基づいて、直列第一詰め物ビット列と、ｎ個の圧縮ビット列ｈｉと、直列第二詰め物ビット列とをすべて結合したビット列（以下「直列結合ビット列Ｈ＊」と呼ぶ。）を生成する。例えば、直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、直列第一詰め物ビット列の後に、ｎ個の圧縮ビット列ｈｉを順番に結合し、更にその後に、直列第二詰め物ビット列を結合して、直列結合ビット列Ｈ＊を生成する。直列詰め物結合部１６２は、ＲＡＭ９１４を用いて、生成した直列結合ビット列Ｈ＊を記憶する。
【００４２】
直列分割部１６３は、分割部１６４、直列生成部１６５を有する。
分割部１６４は、ＣＰＵ９１１を用いて、直列詰め物結合部１６２が記憶した直列結合ビット列Ｈ＊を入力する。分割部１６４は、ＣＰＵ９１１を用いて、入力した直列結合ビット列Ｈ＊に基づいて、直列結合ビット列Ｈ＊をａ２ビットごとに分割した複数のビット列ｘｉ（以下「直列分割ビット列」と呼ぶ。）（ただし、ｉは１以上ｓ以下の整数。ｓは直列分割ビット列の数。）を生成する。分割部１６４は、ＲＡＭ９１４を用いて、生成したｓ個の直列分割ビット列ｘｉを記憶する。
直列生成部１６５は、ＣＰＵ９１１を用いて、直列ハッシュ鍵入力部１２２が記憶した直列ハッシュ鍵Ｋ２と、分割部１６４が記憶したｓ個の直列分割ビット列ｘｉとを入力する。直列生成部１６５は、ＣＰＵ９１１を用いて、入力した直列ハッシュ鍵Ｋ２とｓ個の直列分割ビット列ｘｉとに基づいて、直列ハッシュ鍵Ｋ２とｓ個の直列分割ビット列ｘｉそれぞれとの間の排他的論理和を取り、ｓ個のビット列ｙｉ（以下「直列ビット列」と呼ぶ。）（ただし、ｉは１以上ｓ以下の整数。）を生成する。ここで、直列ハッシュ鍵Ｋ２及びｓ個の直列分割ビット列ｘｉは、それぞれａ２ビットのビット列であり、直列生成部１６５が生成するｓ個の直列ビット列ｙｉも同じく、ａ２ビットのビット列である。
直列生成部１６５は、ＲＡＭ９１４を用いて、生成したｓ個の直列ビット列ｙｉを記憶する。
【００４３】
直列圧縮部１６６は、ＣＰＵ９１１を用いて、直列初期値記憶部１４２が記憶した直列初期値ビット列ＩＶと、直列生成部１６５が記憶したｓ個の直列ビット列ｙｉとを入力する。直列圧縮部１６６は、ＣＰＵ９１１を用いて、入力した直列初期値ビット列ＩＶとｓ個の直列ビット列ｙｉとに基づいて、鍵付きハッシュ値Ｈを算出する。
【００４４】
まず、直列圧縮部１６６は、ＣＰＵ９１１を用いて、ｓ個の直列ビット列ｙｉのうち最初の直列ビット列ｙ１を第一ビット列として直列圧縮関数演算部１８０に入力し、直列初期値ビット列ＩＶを第二ビット列として直列圧縮関数演算部１８０に入力する。直列圧縮部１６６は、ＣＰＵ９１１を用いて、入力した直列ビット列ｙ１及び直列初期値ビット列ＩＶに対して直列圧縮関数演算部１８０が出力した直列出力ビット列を取得して、最初の中間ビット列ｃ１とする。
次に、直列圧縮部１６６は、ＣＰＵ９１１を用いて、ｓ個の直列ビット列ｙｉのうち２番目の直列ビット列ｙ２を第一ビット列として直列圧縮関数演算部１８０に入力し、取得した最初の中間ビット列ｃ１を第二ビット列として直列圧縮関数演算部１８０に入力する。直列圧縮部１６６は、ＣＰＵ９１１を用いて、入力した直列ビット列ｙ２及び中間ビット列ｃ１に対して直列圧縮関数演算部１８０が出力した直列出力ビット列を取得して、２番目の中間ビット列ｃ２とする。
以下、これを繰り返す。すなわち、直列圧縮部１６６は、ＣＰＵ９１１を用いて、ｉ番目の直列ビット列ｙｉを第一ビット列として直列圧縮関数演算部１８０に入力し、ｉ−１番目の中間ビット列ｃｉ−１を第二ビット列として直列圧縮関数演算部１８０に入力する。直列圧縮部１６６は、ＣＰＵ９１１を用いて、入力した直列ビット列ｙｉ及び中間ビット列ｃｉ−１に対して直列圧縮関数演算部１８０が出力した直列出力ビット列を取得して、ｉ番目の中間ビット列ｃｉとする。
ｓ番目の中間ビット列ｃｓを取得した場合、直列圧縮部１６６は、ＲＡＭ９１４を用いて、取得したｓ番目の中間ビット列ｃｓを、鍵付きハッシュ値Ｈとして記憶する。
【００４５】
次に、動作について説明する。
【００４６】
図８は、この実施の形態におけるハッシュ関数演算装置１００が鍵付きハッシュ値を算出するハッシュ関数演算処理の流れの一例を示すフローチャート図である。
ハッシュ関数演算処理は、メッセージ入力工程Ｓ７１０、ハッシュ鍵入力工程Ｓ７２０、並列処理工程Ｓ７３０、直列処理工程Ｓ７６０、ハッシュ値出力工程Ｓ７９０を有する。
【００４７】
メッセージ入力工程Ｓ７１０において、メッセージ入力部１１０は、ＣＰＵ９１１を用いて、入力メッセージＭを入力する。
ハッシュ鍵入力工程Ｓ７２０において、ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、ハッシュ鍵Ｋ（並列ハッシュ鍵Ｋ１及び直列ハッシュ鍵Ｋ２）を入力する。
並列処理工程Ｓ７３０において、並列処理部１３０は、ＣＰＵ９１１を用いて、メッセージ入力工程Ｓ７１０でメッセージ入力部１１０が入力した入力メッセージＭと、ハッシュ鍵入力工程Ｓ７２０でハッシュ鍵入力部１２０が入力した並列ハッシュ鍵Ｋ１とに基づいて、ｎ個の圧縮ビット列ｈｉを生成する。
直列処理工程Ｓ７６０において、直列処理部１６０は、ＣＰＵ９１１を用いて、並列処理工程Ｓ７３０で並列処理部１３０が生成したｎ個の圧縮ビット列ｈｉと、ハッシュ鍵入力工程Ｓ７２０でハッシュ鍵入力部１２０が入力した直列ハッシュ鍵Ｋ２とに基づいて、鍵付きハッシュ値Ｈを生成する。
ハッシュ値出力工程Ｓ７９０において、ハッシュ値出力部１９０は、ＣＰＵ９１１を用いて、直列処理工程Ｓ７６０で直列処理部１６０が生成した鍵付きハッシュ値Ｈを出力する。
【００４８】
図９は、この実施の形態における並列処理部１３０が並列処理をする並列処理工程Ｓ７３０の流れの一例を示すフローチャート図である。
並列処理工程Ｓ７３０は、並列詰め物生成工程Ｓ７３１、並列詰め物結合工程Ｓ７３２、並列分割工程Ｓ７３４、並列生成工程Ｓ７３５、並列圧縮工程Ｓ７３６を有する。
【００４９】
並列詰め物生成工程Ｓ７３１において、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力工程Ｓ７１０でメッセージ入力部１１０が入力した入力メッセージＭに基づいて、並列詰め物Ｐ１を生成する。
並列詰め物結合工程Ｓ７３２において、並列詰め物結合部１３２は、ＣＰＵ９１１を用いて、メッセージ入力工程Ｓ７１０でメッセージ入力部１１０が入力した入力メッセージＭと、並列詰め物生成工程Ｓ７３１で並列詰め物生成部１３１が生成した並列詰め物Ｐ１とに基づいて、並列結合ビット列Ｍ＊を生成する。
【００５０】
次に、並列処理部１３０は、ＣＰＵ９１１を用いて、並列分割工程Ｓ７３４〜並列圧縮工程Ｓ７３６をｎ回繰り返す。なお、この段落において、ｉは何回目の繰り返しであるかを示す１以上ｎ以下の整数を表わす。
並列分割工程Ｓ７３４において、並列分割部１３４は、ＣＰＵ９１１を用いて、並列詰め物結合工程Ｓ７３２で並列詰め物結合部１３２が生成した並列結合ビット列Ｍ＊に基づいて、ｉ番目の並列分割ビット列ｍｉを生成する。
並列生成工程Ｓ７３５において、並列生成部１３５は、ＣＰＵ９１１を用いて、並列分割工程Ｓ７３４で並列分割部１３４が生成したｉ番目の並列分割ビット列ｍｉと、ハッシュ鍵入力工程Ｓ７２０でハッシュ鍵入力部１２０が入力した並列ハッシュ鍵Ｋ１と、並列固定記憶部１４３があらかじめ記憶した並列固定ビット列Ｆとに基づいて、ｉ番目の並列ビット列ｍｉ”を生成する。
並列圧縮工程Ｓ７３６において、並列圧縮部１３６は、ＣＰＵ９１１を用いて、並列生成工程Ｓ７３５で並列生成部１３５が生成したｉ番目の並列ビット列ｍｉ”に基づいて、並列圧縮関数演算部１５０を呼び出し、ｉ番目の圧縮ビット列ｈｉを生成する。
【００５１】
図１０は、この実施の形態における直列処理部１６０が直列処理をする直列処理工程Ｓ７６０の流れの一例を示すフローチャート図である。
直列処理工程Ｓ７６０は、直列詰め物生成工程Ｓ７６１、直列詰め物結合工程Ｓ７６２、直列分割工程Ｓ７６４、直列生成工程Ｓ７６５、直列圧縮工程Ｓ７６６を有する。
【００５２】
直列詰め物生成工程Ｓ７６１において、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、メッセージ入力工程Ｓ７１０でメッセージ入力部１１０が入力した入力メッセージＭに基づいて、直列詰め物Ｐ２（直列第一詰め物ビット列及び直列第二詰め物ビット列）を生成する。
直列詰め物結合工程Ｓ７６２において、直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、ｎ回の並列圧縮工程Ｓ７３６で並列圧縮部１３６が生成したｎ個の圧縮ビット列ｈｉと、直列詰め物生成工程Ｓ７６１で直列詰め物生成部１６１が生成した直列詰め物Ｐ２とに基づいて、直列結合ビット列Ｈ＊を生成する。
【００５３】
次に、直列処理部１６０は、ＣＰＵ９１１を用いて、直列分割工程Ｓ７６４〜直列圧縮工程Ｓ７６６をｓ回繰り返す。なお、この段落において、ｉは何回目の繰り返しであるかを示す１以上ｓ以下の整数を表わす。
直列分割工程Ｓ７６４において、分割部１６４は、ＣＰＵ９１１を用いて、直列詰め物結合工程Ｓ７６２で直列詰め物結合部１６２が生成した直列結合ビット列Ｈ＊に基づいて、ｉ番目の直列分割ビット列ｘｉを生成する。
直列生成工程Ｓ７６５において、直列生成部１６５は、ＣＰＵ９１１を用いて、分割工程Ｓ７６４で分割部１６４が生成したｉ番目の直列分割ビット列ｘｉと、ハッシュ鍵入力工程Ｓ７２０でハッシュ鍵入力部１２０が入力した直列ハッシュ鍵Ｋ２とに基づいて、ｉ番目の直列ビット列ｙｉを生成する。
直列圧縮工程Ｓ７６６において、直列圧縮部１６６は、ＣＰＵ９１１を用いて、直列生成工程Ｓ７６５で直列生成部１６５が生成したｉ番目の直列ビット列ｙｉと、前回の直列圧縮工程Ｓ７６６で直列圧縮部１６６が生成したｉ−１番目の中間ビット列ｃｉ−１とに基づいて、直列圧縮関数演算部１８０を呼び出し、ｉ番目の中間ビット列ｃｉを生成する。なお、１回目の直列圧縮工程Ｓ７６６において、直列圧縮部１６６は、ＣＰＵ９１１を用いて、中間ビット列ｃ０の代わりとして、直列初期値記憶部１４２があらかじめ記憶した直列初期値ビット列ＩＶを使用する。また、ｓ回目の直列圧縮工程Ｓ７６６において、直列圧縮部１６６は、ＲＡＭ９１４を用いて、生成した中間ビット列ｃｓを鍵付きハッシュ値Ｈとして記憶する。
【００５４】
ハッシュ関数演算装置１００は、以上のようにして、鍵付きハッシュ値Ｈを算出する。
【００５５】
証明は省略するが、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
したがって、構成するのが難しいｅＳＰＲ性を満たす圧縮関数を構成する必要はなく、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が、比較的容易に構成できるＳＰＲ性を満たす圧縮関数を計算するよう構成すれば、ｅＴＣＲ性を満たすハッシュ関数を計算するハッシュ関数演算装置１００を構成できる。このため、ハッシュ関数演算装置１００が算出したハッシュ値を用いて、攻撃に対する耐性が強く安全な電子署名システムを構築することができる。
【００５６】
なお、圧縮関数のＳＰＲ性とは、以下のように定義される。
圧縮関数が入力するビット列のビット数をａ、出力するビット列のビット数をｂとし、ｂビットのビット列ｃとａ−ｂビットのビット列ｍとを結合したビット列を入力した場合に、圧縮関数が出力するビット列をｈ（ｃ，ｍ）とする。
攻撃者には、ｂビットのランダムなビット列ｃと、ａ−ｂビットのランダムなビット列ｍとが与えられる。攻撃者は、ｈ（ｃ，ｍ）＝ｈ（ｃ’，ｍ’）となるｂビットのビット列ｃ’とａ−ｂビットのビット列ｍ’との組（ただし、ｃ≠ｃまたはｍ≠ｍ’。）を見つけようとする。総当り攻撃よりも速くビット列ｃ’とビット列ｍ’との組を見つけることができる攻撃者が存在しない場合に、その圧縮関数はＳＰＲ性を満たす。
【００５７】
また、ハッシュ関数のｅＴＣＲ性とは、以下のように定義される。
ハッシュ関数が入力するビット列をＭ、ハッシュ鍵をｋとした場合に、ハッシュ関数が出力するビット列をＨｋ（Ｍ）とする。
攻撃者は、自由にビット列Ｍを決定する。その後、攻撃者には、ランダムなハッシュ鍵ｋが与えられる。攻撃者は、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となるビット列Ｍ’とハッシュ鍵ｋ’との組（ただし、Ｍ≠Ｍ’またはｋ≠ｋ’。）を見つけようとする。総当り攻撃よりも速くビット列Ｍ’とハッシュ鍵ｋ’との組を見つけることができる攻撃者が存在しない場合に、そのハッシュ関数はｅＴＣＲ性を満たす。
【００５８】
この実施の形態におけるハッシュ関数演算装置１００は、データを処理する処理装置（ＣＰＵ９１１）と、並列圧縮関数演算部１５０と、直列圧縮関数演算部１８０と、メッセージ入力部１１０と、並列処理部１３０と、直列処理部１６０と、ハッシュ値出力部１９０とを有する。
上記並列圧縮関数演算部１５０は、上記処理装置（ＣＰＵ９１１）を用いて、ａ１ビット（ただし、ａ１は２以上の所定の整数。）の入力ビット列を入力し、入力した入力ビット列に基づいてｂ１ビット（ただし、ｂ１は１以上ａ１未満の所定の整数。）の並列出力ビット列を生成する。
上記直列圧縮関数演算部１８０は、上記処理装置（ＣＰＵ９１１）を用いて、ａ２ビット（ただし、ａ２は１以上の所定の整数。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、上記ｂ２ビットの直列出力ビット列を生成する。
上記メッセージ入力部１１０は、上記処理装置（ＣＰＵ９１１）を用いて、Ｌ１ビット（ただし、Ｌ１は１以上の任意の整数。）のビット列を入力して入力メッセージＭとする。
上記並列処理部１３０は、上記処理装置（ＣＰＵ９１１）を用いて、上記メッセージ入力部１１０が入力した入力メッセージＭに基づいて、上記ａ１ビットの複数の並列ビット列ｍ”を生成し、生成した複数の並列ビット列ｍ”それぞれを上記入力ビット列として上記並列圧縮関数演算部１５０に入力し、上記並列圧縮関数演算部１５０が入力した複数の並列ビット列ｍ”それぞれに対して生成した複数の並列出力ビット列を取得して複数の圧縮ビット列ｈとする。
上記直列処理部１６０は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列処理部１３０が取得した複数の圧縮ビット列ｈに基づいて、上記ａ２ビットの複数の直列ビット列ｙを生成し、生成した複数の直列ビット列ｙのうち少なくともいずれかの直列ビット列ｙと、上記直列ビット列ｙと異なる他の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算部１８０に入力し、上記直列圧縮関数演算部１８０が入力した直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記直列ビット列ｙに基づいて生成された中間ビット列ｃとし、取得した中間ビット列ｃのうちのいずれかをハッシュ値Ｈとする。
上記ハッシュ値出力部１９０は、上記処理装置（ＣＰＵ９１１）を用いて、上記直列処理部１６０が取得したハッシュ値Ｈを出力する。
【００５９】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００６０】
この実施の形態におけるハッシュ関数演算装置１００は、更に、データを記憶する記憶装置（ＲＯＭ９１３）と、直列初期値記憶部１４２とを有する。
上記直列初期値記憶部１４２は、上記記憶装置（ＲＯＭ９１３）を用いて、上記ｂ２ビットのビット列を直列初期ビット列ＩＶとして記憶する。
上記直列処理部１６０は、上記処理装置（ＣＰＵ９１１）を用いて、生成した複数の直列ビット列ｙのうち最初の直列ビット列ｙと、上記直列初期値記憶部１４２が記憶した直列初期ビット列ＩＶとに基づいて、上記最初の直列ビット列ｙを上記第一ビット列とし上記直列初期ビット列ＩＶを上記第二ビット列として上記直列圧縮関数演算部１８０に入力し、上記直列圧縮関数演算部１８０が入力した最初の直列ビット列ｙ及び直列初期ビット列ＩＶに対して生成した直列出力ビット列を取得して上記最初の直列ビット列ｙに基づいて生成された中間ビット列ｃとし、生成した複数の直列ビット列ｙのうち最初以外の直列ビット列ｙと、上記最初以外の直列ビット列ｙより一つ前の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記最初以外の直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算部１８０に入力し、上記直列圧縮関数演算部１８０が入力した最初以外の直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記最初以外の直列ビット列ｙに基づいて生成された中間ビット列ｃとし、上記複数の直列ビット列ｙのうち最後の直列ビット列ｙに基づいて生成された中間ビット列ｃをハッシュ値Ｈとする。
【００６１】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００６２】
この実施の形態における並列処理部１３０は、並列詰め物生成部１３１と、並列詰め物結合部１３２と、並列分割部１３４と、並列生成部１３５とを有する。
上記並列詰め物生成部１３１は、上記処理装置（ＣＰＵ９１１）を用いて、上記メッセージ入力部１１０が入力した入力メッセージＭに基づいて、ｎ１ビット（ただし、ｎ１は１以上の整数で、ｎ１＋Ｌ１が整数ｄ１の整数倍。Ｌ１は上記入力メッセージＭのビット数。上記整数ｄ１は１以上の所定の整数。）のビット列を生成して並列詰め物Ｐ１とする。
上記並列詰め物結合部１３２は、上記処理装置（ＣＰＵ９１１）を用いて、上記メッセージ入力部１１０が入力した入力メッセージＭと、上記並列詰め物生成部１３１が生成した並列詰め物Ｐ１とに基づいて、上記入力メッセージＭと上記並列詰め物Ｐ１とを結合したビット列を生成して並列結合ビット列Ｍ＊とする。
上記並列分割部１３４は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列詰め物結合部１３２が生成した並列結合ビット列Ｍ＊に基づいて、上記並列結合ビット列Ｍ＊を上記ｄ１ビットごとに分割した複数のビット列を生成して複数の並列分割ビット列ｍとする。
上記並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列分割部１３４が生成した複数の並列分割ビット列ｍそれぞれに基づいて、上記複数の並列ビット列ｍ”を生成する。
【００６３】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００６４】
この実施の形態におけるハッシュ関数演算装置１００は、更に、並列ハッシュ鍵入力部１２１を有する。
上記並列ハッシュ鍵入力部１２１は、上記処理装置（ＣＰＵ９１１）を用いて、上記ｄ１ビットのビット列を入力して並列ハッシュ鍵Ｋ１とする。
上記並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列ハッシュ鍵入力部１２１が入力した並列ハッシュ鍵Ｋ１と、上記並列分割部１３４が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記複数の並列ビット列ｍ”を生成する。
【００６５】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００６６】
この実施の形態における並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列ハッシュ鍵入力部１２１が入力したハッシュ鍵Ｋ１と、上記並列分割部１３４が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記ハッシュ鍵Ｋ１と上記並列分割ビット列ｍとの排他的論理和をそれぞれ算出して複数の並列撹乱ビット列ｍ’とし、算出した複数の並列撹乱ビット列ｍ’それぞれに基づいて、上記複数の並列撹乱ビット列ｍ’と所定の並列固定ビット列とを結合したビット列をそれぞれ生成して上記複数の並列ビット列ｍ”とする。
【００６７】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００６８】
この実施の形態における並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記複数の並列撹乱ビット列ｍ’と１ビットの並列固定ビット列とを結合したビット列をそれぞれ生成して上記複数の並列ビット列ｍ”とする。
【００６９】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００７０】
この実施の形態における並列詰め物生成部１３１は、上記処理装置（ＣＰＵ９１１）を用いて、上記ｄ１個の連続した「０」を含む並列詰め物Ｐ１を生成する。
【００７１】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００７２】
この実施の形態における直列処理部１６０は、直列詰め物生成部１６１と、直列詰め物結合部１６２と、直列分割部１６３とを有する。
上記直列詰め物生成部１６１は、上記処理装置（ＣＰＵ９１１）を用いて、上記メッセージ入力部１１０が入力した入力メッセージＭに基づいて、ｎ２ビット（ただし、ｎ２は１以上の整数で、ｎ２＋Ｌ２が整数ｄ２の整数倍。Ｌ２は上記複数の圧縮ビット列ｈのビット数を合計した整数。上記整数ｄ２は１以上の所定の整数。）のビット列を生成して直列詰め物Ｐ２とする。
上記直列詰め物結合部１６２は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列処理部１３０が取得した複数の圧縮ビット列ｈと、上記直列詰め物生成部１６１が生成した直列詰め物Ｐ２とに基づいて、上記複数の圧縮ビット列ｈと上記直列詰め物Ｐ２とを結合したビット列を生成して直列結合ビット列Ｈ＊とする。
上記直列分割部１６３は、上記処理装置（ＣＰＵ９１１）を用いて、上記直列詰め物結合部１６２が生成した直列結合ビット列Ｈ＊に基づいて、上記複数の直列ビット列ｙを生成する。
【００７３】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００７４】
この実施の形態におけるハッシュ関数演算装置１００は、更に、直列ハッシュ鍵入力部１２２を有する。
上記直列ハッシュ鍵入力部１２２は、上記処理装置（ＣＰＵ９１１）を用いて、上記ｄ２ビットのビット列を入力して直列ハッシュ鍵Ｋ２とする。
上記直列分割部１６３は、上記処理装置（ＣＰＵ９１１）を用いて、上記直列詰め物結合部１６２が生成した直列結合ビット列Ｈ＊に基づいて、上記直列結合ビット列Ｈ＊を上記ｄ２ビットごとに分割した複数のビット列を生成して複数の直列分割ビット列ｘとし、上記直列ハッシュ鍵入力部１２２が入力した直列ハッシュ鍵Ｋ２と、生成した複数の直列分割ビット列ｘそれぞれとに基づいて、上記複数の直列ビット列ｙを生成する。
【００７５】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００７６】
この実施の形態における直列分割部１６３は、上記処理装置（ＣＰＵ９１１）を用いて、上記直列ハッシュ鍵入力部１２２が入力したハッシュ鍵Ｋ２と、生成した複数の直列分割ビット列ｘそれぞれとに基づいて、上記ハッシュ鍵Ｋ２と上記直列分割ビット列ｘとの排他的論理和をそれぞれ算出して複数の直列ビット列ｙとする。
【００７７】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００７８】
この実施の形態における直列詰め物生成部１６１は、上記処理装置（ＣＰＵ９１１）を用いて、上記ｄ２個の連続した「０」を含む直列詰め物Ｐ２を生成する。
【００７９】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００８０】
この実施の形態における直列詰め物生成部１６１は、上記処理装置（ＣＰＵ９１１）を用いて、上記ｄ２個の連続した「０」を含む直列第一詰め物ビット列と、上記入力メッセージＭのビット数Ｌ１をｅ２ビット（ただし、ｅ２は１以上の所定の整数。）の二進数で表現したビット列を含む直列第二詰め物ビット列とからなる直列詰め物Ｐ２を生成する。
上記直列詰め物結合部１６２は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列処理部１３０が取得した複数の圧縮ビット列ｈと、上記直列詰め物生成部１６１が生成した直列詰め物Ｐ２に含まれる直列第一詰め物ビット列及び直列第二詰め物ビット列とに基づいて、上記直列第一詰め物ビット列と上記複数の圧縮ビット列ｈと上記直列第二詰め物ビット列とを結合したビット列を生成して直列結合ビット列Ｈ＊とする。
【００８１】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００８２】
この実施の形態における直列圧縮関数演算部１８０は、上記処理装置（ＣＰＵ９１１）を用いて、ａ２ビット（ただし、ａ２＝ａ１−ｂ１。）の第一ビット列を入力し、ｂ１ビットの第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とを結合したビット列を生成して第三ビット列とし、生成した第三ビット列を上記入力ビット列として上記並列圧縮関数演算部１５０に入力し、上記並列圧縮関数演算部１５０が入力した第三ビット列に対して出力した並列出力ビット列を取得して上記直列出力ビット列とする。
【００８３】
この実施の形態におけるハッシュ関数演算装置１００によれば、圧縮関数を計算する演算部が一つで済むので、ハッシュ関数演算装置１００を論理回路を用いて実現する場合には、回路が小さくなり、ハッシュ関数演算装置１００をプログラムを用いて実現する場合には、プログラムコードが短くなるという効果を奏する。
【００８４】
この実施の形態における並列圧縮関数演算部１５０は、上記処理装置（ＣＰＵ９１１）を用いて、ＳＰＲ性圧縮関数を演算することにより、上記入力ビット列に基づいて上記並列出力ビット列を生成する。
【００８５】
この実施の形態におけるハッシュ関数演算装置１００によれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００８６】
この実施の形態における署名装置８１０は、ハッシュ関数演算装置１００と、署名関数演算部８１３と、署名出力部８１４とを有する。
上記ハッシュ関数演算装置１００は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力する。
上記署名関数演算部８１３は、上記ハッシュ値出力部１９０が出力したハッシュ値Ｈに基づいて、署名ｓを生成する。
上記署名出力部８１４は、上記署名関数演算部８１３が生成した署名ｓを、上記署名対象メッセージに対する署名として出力する。
【００８７】
この実施の形態における署名装置８１０によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、攻撃に対する耐性が強く安全な電子署名を実現することができるという効果を奏する。
【００８８】
この実施の形態における署名装置８１０は、並列ハッシュ鍵生成部（ハッシュ鍵生成部８１２）と、ハッシュ関数演算装置１００と、署名関数演算部８１３と、署名出力部８１４とを有する。
上記並列ハッシュ鍵生成部８１２は、上記ｄ１ビットのビット列ｋ１をランダムに生成する。
上記メッセージ入力部１１０は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力する。
上記並列ハッシュ鍵入力部１２１は、上記並列ハッシュ鍵生成部（ハッシュ鍵生成部８１２）が生成したビット列ｋ１を上記並列ハッシュ鍵Ｋ１として入力する。
上記署名関数演算部８１３は、上記ハッシュ値出力部１９０が出力したハッシュ値Ｈに基づいて、署名ｓを生成する。
上記署名出力部８１４は、上記並列ハッシュ鍵生成部８１２が生成したビット列ｋ１と、上記署名関数演算部８１３が生成した署名ｓとの組を、上記署名対象メッセージに対する署名として出力する。
【００８９】
この実施の形態における署名装置８１０によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、攻撃に対する耐性が強く安全な電子署名を実現することができるという効果を奏する。
【００９０】
この実施の形態における署名装置８１０は、直列ハッシュ鍵生成部（ハッシュ鍵生成部８１２）と、ハッシュ関数演算装置１００と、署名関数演算部８１３と、署名出力部８１４とを有する。
上記直列ハッシュ鍵生成部（ハッシュ鍵生成部８１２）は、上記ｄ２ビットのビット列ｋ２をランダムに生成する。
上記メッセージ入力部１１０は、署名の対象である署名対象メッセージを上記入力メッセージＭとして入力する。
上記直列ハッシュ鍵入力部１２２は、上記直列ハッシュ鍵生成部（ハッシュ鍵生成部８１２）が生成したビット列ｋ２を上記直列ハッシュ鍵Ｋ２として入力する。
上記署名関数演算部８１３は、上記ハッシュ値出力部１９０が出力したハッシュ値Ｈに基づいて、署名ｓを生成する。
上記署名出力部８１４は、上記直列ハッシュ鍵生成部８１２が生成したビット列ｋ２と、上記署名関数演算部８１３が生成した署名ｓとの組を、上記署名対象メッセージに対する署名として出力する。
【００９１】
この実施の形態における署名装置８１０によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、攻撃に対する耐性が強く安全な電子署名を実現することができるという効果を奏する。
【００９２】
この実施の形態におけるハッシュ関数演算装置１００は、データを処理する処理装置（ＣＰＵ９１１）を有するコンピュータをハッシュ関数演算装置１００として機能させるプログラムを、コンピュータが実行することにより実現することができる。
【００９３】
この実施の形態におけるコンピュータプログラムによれば、ＳＰＲ性を満たす圧縮関数に基づいて、ｅＴＣＲ性を満たすハッシュ関数を演算するハッシュ関数演算装置１００を実現することができるという効果を奏する。
【００９４】
この実施の形態におけるハッシュ関数演算装置１００がハッシュ値を計算するハッシュ関数演算方法は、並列圧縮関数演算工程と、直列圧縮関数演算工程とを有する。
並列圧縮関数演算工程において、上記処理装置（ＣＰＵ９１１）が、ａ１ビット（ただし、ａ１は２以上の所定の整数。）の入力ビット列を入力し、入力した入力ビット列に基づいてｂ１ビット（ただし、ｂ１は１以上ａ１以下の所定の整数。）の並列出力ビット列を生成する。
上記直列圧縮関数演算工程において、上記処理装置（ＣＰＵ９１１）が、ａ２ビット（ただし、ａ２は１以上の所定の整数。）の第一ビット列を入力し、ｂ２ビット（ただし、ｂ２は１以上の所定の整数。）の第二ビット列を入力し、入力した第一ビット列と入力した第二ビット列とに基づいて、上記ｂ２ビットの直列出力ビット列を生成する。
上記ハッシュ関数演算方法は、更に、以下の工程を有する。
上記処理装置（ＣＰＵ９１１）が、Ｌ１ビット（ただし、Ｌ１は１以上の任意の整数。）のビット列を入力して入力メッセージＭとする。
上記処理装置（ＣＰＵ９１１）が、入力した入力メッセージＭに基づいて、上記ａ１ビットの複数の並列ビット列ｍ”を生成する。
上記処理装置（ＣＰＵ９１１）が、生成した複数の並列ビット列ｍ”それぞれを上記入力ビット列として上記並列圧縮関数演算工程を実行し、上記並列圧縮関数演算工程で入力した複数の並列ビット列ｍ”それぞれに対して生成した複数の並列出力ビット列を取得して複数の圧縮ビット列ｈとする。
上記処理装置（ＣＰＵ９１１）が、取得した複数の圧縮ビット列ｈに基づいて、上記ａ２ビットの複数の直列ビット列ｙを生成する。
上記処理装置（ＣＰＵ９１１）が、生成した複数の直列ビット列ｙのうち少なくともいずれかの直列ビット列ｙと、上記直列ビット列ｙと異なる他の直列ビット列ｙに基づいて生成された中間ビット列ｃとに基づいて、上記直列ビット列ｙを上記第一ビット列とし上記中間ビット列ｃを上記第二ビット列として上記直列圧縮関数演算工程を実行し、上記直列圧縮関数演算工程で入力した直列ビット列ｙ及び中間ビット列ｃに対して生成した直列出力ビット列を取得して上記直列ビット列ｙに基づいて生成された中間ビット列ｃとし、取得した中間ビット列ｃのうち少なくともいずれかをハッシュ値Ｈとする。
上記処理装置（ＣＰＵ９１１）が、取得したハッシュ値Ｈを出力する。
【００９５】
この実施の形態におけるハッシュ関数演算方法によれば、並列圧縮関数演算工程及び直列圧縮関数演算工程で計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【００９６】
以上説明したハッシュ関数演算装置１００は、ランダムな固定鍵Ｋ１‖Ｋ２（ハッシュ鍵Ｋ）を生成する固定鍵装置（ハッシュ鍵生成部８１２）と、前記固定鍵装置の出力の一部Ｋ１（並列ハッシュ鍵）と任意長のメッセージＭ（入力メッセージ）を受け、任意長のメッセージ（入力メッセージＭ）の長さに依存した長さの値（複数の圧縮ビット列ｈｉ）を出力する並列処理装置（並列処理部１３０）と、並列処理装置の出力（複数の圧縮ビット列ｈｉ）と固定鍵装置の出力の一部Ｋ２（直列ハッシュ鍵）を受け、固定長の値（ハッシュ値Ｈ）を出力する直列処理装置（直列処理部１６０）を有する。
【００９７】
並列処理装置（並列処理部１３０）は、任意長メッセージＭ（入力メッセージ）を受け、Ｍにある値（並列詰め物Ｐ１）をパディングし、ある長さごとにこの値（並列結合ビット列Ｍ＊）を分割する装置（並列分割部１３４）と、この装置の出力値（複数の並列分割ビット列ｍｉ）と鍵の一部Ｋ１（並列ハッシュ鍵）を受け、この値ごとにＫ１を排他的論理和する装置（並列生成部１３５）と、その装置の出力（複数の並列ビット列ｍｉ”）を受け、その値それぞれをＳＰＲ性圧縮関数で計算する装置（並列圧縮部１３６）と、この装置の出力（複数の圧縮ビット列ｈｉ）を受け、値を結合する装置（直列詰め物結合部１６２）を有する。
【００９８】
直列処理装置（並列圧縮関数演算部１５０）は、並列処理装置（並列処理部１３０）の出力（複数の圧縮ビット列ｈｉ）を受け、この値にある値（直列詰め物Ｐ２）をパディングし、ある長さごとにこの値（直列結合ビット列Ｈ＊）を分割する装置（分割部１６４）と、この装置の出力値（複数の直列分割ビット列ｘｉ）と鍵の一部Ｋ２（直列ハッシュ鍵）を受け、装置の出力値をそれぞれＫ２と排他的論理和する装置（直列生成部１６５）と、この装置の出力（複数の直列ビット列ｙｉ）を受け、ＳＰＲ性圧縮関数をＭＤ構造につないだ関数を計算する装置（直列圧縮部１６６）を有する。
【００９９】
以上説明したハッシュ関数演算装置１００によれば、ＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。
【０１００】
以上説明した署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力しｂビットのビット列を出力するＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムな２ａ−ｂ−１ビットの鍵Ｋ１‖Ｋ２（ただし、｜Ｋ１｜＝ａ−１。）を生成する。並列詰め物結合部１３２は、長さがａ−ｂ−１ビットの倍数となる値Ｍ＊＝Ｍ‖０ｕ‖０ａ−ｂ−１を生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａ−ｂ−１ビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ’＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ｍｉ’‖１（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉとする。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数の値Ｈ＊＝０ａ−ｂ‖ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖ‖＜Ｍ＞を生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｘ１‖ｘ２‖…‖ｘｓとする。直列生成部１６５は、ｘｉ（ｉ＝１，２，…，ｓ）とＫ２とを排他的論理和し、ｙｉ＝ｘｉ  ＸＯＲ  Ｋ２（ｉ＝１，２，…，ｓ）とする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここでｃ０＝ＩＶで、ＩＶはｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名として（Ｋ１，Ｋ２，σ（ｃｓ））を出力する。
【０１０１】
以上説明した署名装置８１０によれば、安全かつ効率的な署名を構成することができる。
【０１０２】
以上説明したハッシュ関数演算方法は、ＳＰＲ性圧縮関数を並列に並べ、圧縮関数への入力にランダムな鍵（並列ハッシュ鍵Ｋ１）を排他的論理和する処理と、ＳＰＲ性圧縮関数の出力に別のランダムな鍵（直列ハッシュ鍵Ｋ２）を排他的論理和する処理とを、ＳＰＲ性圧縮関数を直列に並べるＭＤ構造に加えたものである。
【０１０３】
以上説明したハッシュ関数演算方法によれば、ＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。
【０１０４】
以上のように、圧縮関数の繰り返し構造に対して、圧縮関数の並列処理部分とハッシュ鍵を加えることにより、比較的簡易に構成できるＳＰＲ性圧縮関数から、短い長さのハッシュ鍵を用い、署名関数との親和性が高いｅＴＣＲ性ハッシュ関数を構成できる。
【０１０５】
また、メッセージ長にかかわらず、ハッシュ鍵の長さが一定なので、メッセージが長い場合でも署名が長くならず、署名の計算量が少なくて済む。
【０１０６】
実施の形態２．
実施の形態２について、図１１〜図１３を用いて説明する。
【０１０７】
図１１は、この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図である。
なお、実施の形態１で説明したハッシュ関数演算装置１００と共通する部分については、同一の符号を付し、ここでは説明を省略する。
【０１０８】
ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、ａ１ビットのハッシュ鍵Ｋを入力する。ハッシュ鍵入力部１２０が入力するハッシュ鍵Ｋは、ａ１ビットの並列ハッシュ鍵Ｋ１からなる。ハッシュ鍵入力部１２０は、ＲＡＭ９１４を用いて、入力した並列ハッシュ鍵Ｋ１を記憶する。
【０１０９】
直列処理部１６０は、ＣＰＵ９１１を用いて、並列処理部１３０が記憶したｎ個の圧縮ビット列ｈｉを入力する。直列処理部１６０は、入力したｎ個の圧縮ビット列ｈｉと直列ハッシュ鍵Ｋ２とに基づいて、ハッシュ値Ｈを生成する。直列処理部１６０は、ＲＡＭ９１４を用いて、生成したハッシュ値Ｈを記憶する。
【０１１０】
図１２は、この実施の形態における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図である。
なお、実施の形態１で説明したハッシュ関数演算装置１００と共通する部分については、同一の符号を付し、ここでは説明を省略する。
【０１１１】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１よりも大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１の整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットの並列詰め物Ｐ１を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを「０」にした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１ビットが「０」であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【０１１２】
並列分割部１３４は、ＣＰＵ９１１を用いて、並列詰め物結合部１３２が記憶した並列結合ビット列Ｍ＊を入力する。並列分割部１３４は、ＣＰＵ９１１を用いて、入力した並列結合ビット列Ｍ＊に基づいて、並列結合ビット列Ｍ＊をａ１ビットごとに分割した複数の並列分割ビット列ｍｉ（ただし、ｉは１以上ｎ以下の整数。ｎは並列分割ビット列ｍｉの数。）を生成する。並列分割部１３４は、ＲＡＭ９１４を用いて、生成したｎ個の並列分割ビット列ｍｉを記憶する。
【０１１３】
並列生成部１３５は、ＣＰＵ９１１を用いて、並列ハッシュ鍵入力部１２１が記憶した並列ハッシュ鍵Ｋ１と、並列分割部１３４が記憶したｎ個の並列分割ビット列ｍｉとを入力する。並列生成部１３５は、ＣＰＵ９１１を用いて、入力した並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉとに基づいて、並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉそれぞれとの間のビットごとの排他的論理和を取り、ｎ個の並列ビット列ｍｉ”を生成する。ここで、並列ハッシュ鍵Ｋ１及びｎ個の並列分割ビット列ｍｉは、それぞれａ１ビットのビット列であり、並列生成部１３５が生成する並列ビット列ｍｉ”も同じく、ａ１ビットのビット列である。
【０１１４】
図１３は、この実施の形態における直列処理部１６０の内部ブロックの構成の一例を示す詳細ブロック構成図である。
なお、実施の形態１で説明したハッシュ関数演算装置１００と共通する部分については、同一の符号を付し、ここでは説明を省略する。
【０１１５】
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭと、並列圧縮部１３６が記憶した圧縮ビット列ｈｉの数ｎとを入力し、ＣＰＵ９１１を用いて、入力メッセージＭのビット数Ｌ１と、ｎ個の圧縮ビット列ｈｉのビット数を合計した整数Ｌ２とを算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数Ｌ２に基づいて、以下の条件を満たす整数ｎ２を算出する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、整数ｎ２がａ２＋ｅ２より大きく、かつ、整数ｎ２と整数Ｌ２との和ｎ２＋Ｌ２がａ２の整数倍となる整数ｎ２のうち、最小の整数ｎ２を算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数ｎ２に基づいて、ｎ２ビットの直列詰め物Ｐ２を生成する。例えば、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを、入力メッセージＭのビット数Ｌ１を二進数で表現したビット列とした直列詰め物Ｐ２を生成する。
なお、直列詰め物生成部１６１が生成する直列詰め物Ｐ２は、最後からｅ２ビットが入力メッセージＭのビット数Ｌ１を表わす二進数であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
直列詰め物生成部１６１は、ＲＡＭ９１４を用いて、生成した直列詰め物Ｐ２を記憶する。
【０１１６】
直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、並列圧縮部１３６が記憶したｎ個の圧縮ビット列ｈｉと、直列詰め物生成部１６１が生成した直列詰め物Ｐ２とを入力する。直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、入力したｎ個の圧縮ビット列ｈｉと直列詰め物Ｐ２とに基づいて、ｎ個の圧縮ビット列ｈｉと直列詰め物Ｐ２とをすべて結合した直列結合ビット列Ｈ＊を生成する。例えば、直列詰め物結合部１６２は、ＣＰＵ９１１を用いて、ｎ個の圧縮ビット列ｈｉを順番に結合し、その後に直列詰め物Ｐ２を結合して、直列結合ビット列Ｈ＊を生成する。直列詰め物結合部１６２は、ＲＡＭ９１４を用いて、生成した直列結合ビット列Ｈ＊を記憶する。
【０１１７】
直列分割部１６３は、分割部１６４を有する。
分割部１６４は、ＣＰＵ９１１を用いて、直列詰め物結合部１６２が記憶した直列結合ビット列Ｈ＊を入力する。分割部１６４は、ＣＰＵ９１１を用いて、入力した直列結合ビット列Ｈ＊に基づいて、直列結合ビット列Ｈ＊をａ２ビットごとに分割した複数の直列ビット列ｙｉ（ただし、ｉは１以上ｓ以下の整数。ｓは直列分割ビット列の数。）を生成する。分割部１６４は、ＲＡＭ９１４を用いて、生成したｓ個の直列ビット列ｙｉを記憶する。
【０１１８】
以上のような構成とした場合も、実施の形態１と同様、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
また、実施の形態１と比較して、ハッシュ鍵Ｋのビット数が少ないので、署名装置８１０が出力する署名のビット数が少なくなり、記憶装置が署名を記憶するために必要となる記憶容量や、通信装置が署名を送受信するために必要となる通信回線の容量を削減できる。
更に、実施の形態１と比較して、並列生成部１３５の処理や直列分割部１６３の処理が少ないので、ハッシュ関数演算装置１００がハッシュ値を算出する処理にかかる時間が短くなる。また、並列生成部１３５や直列分割部１６３を論理回路を用いて実現する場合には、回路が小さくなり、並列生成部１３５や直列分割部１６３をプログラムを用いて実現する場合には、プログラムコードが短くなる。
【０１１９】
この実施の形態における並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列ハッシュ鍵入力部１２１が入力したハッシュ鍵Ｋ１と、上記並列分割部１３４が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記ハッシュ鍵Ｋ１と上記並列分割ビット列ｍとの排他的論理和をそれぞれ算出して複数の並列ビット列ｍ”とする。
【０１２０】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１２１】
この実施の形態における直列分割部１６３は、上記処理装置（ＣＰＵ９１１）を用いて、上記直列詰め物結合部１６２が生成した直列結合ビット列Ｈ＊に基づいて、上記直列結合ビット列Ｈ＊を上記ｄ２ビットごとに分割した複数のビット列を生成して上記複数の直列ビット列ｙとする。
【０１２２】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１２３】
この実施の形態における直列詰め物生成部１６１は、上記処理装置（ＣＰＵ９１１）を用いて、上記入力メッセージＭのビット数Ｌ１をｅ２ビット（ただし、ｅ２は１以上の所定の整数。）の二進数で表現したビット列を含む直列詰め物Ｐ２を生成する。
【０１２４】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１２５】
以上説明したハッシュ関数演算装置１００は、ランダムな固定鍵Ｋ１（並列ハッシュ鍵）を生成する固定鍵装置（ハッシュ鍵生成部８１２）と、前記固定鍵装置の出力Ｋ１（並列ハッシュ鍵）と任意長のメッセージＭ（入力メッセージ）を受け、任意長のメッセージ（入力メッセージＭ）の長さ（ビット数Ｌ１）に依存した長さの値（複数の圧縮ビット列ｈｉ）を出力する並列処理装置（並列処理部１３０）と、並列処理装置（並列処理部１３０）の出力（複数の圧縮ビット列ｈｉ）を受け、固定長の値（ハッシュ値Ｈ）を出力する直列処理装置（直列処理部１６０）を有する。
【０１２６】
並列処理装置（並列処理部１３０）は、任意長メッセージＭ（入力メッセージ）を受け、Ｍにある値（並列詰め物Ｐ１）をパディングし、ある長さごとにこの値（並列結合ビット列Ｍ＊）を分割する装置（並列分割部１３４）と、この装置の出力値（複数の並列分割ビット列ｍｉ）と鍵Ｋ１（並列ハッシュ鍵）を受け、この値ごとにＫ１を排他的論理和する装置（並列生成部１３５）と、その装置の出力（複数の並列ビット列ｍｉ”）を受け、その値それぞれをＳＰＲ性圧縮関数で計算する装置（並列圧縮部１３６）と、この装置の出力（複数の圧縮ビット列ｈｉ）を受け、値を結合する装置（直列詰め物結合部１６２）を有する。
【０１２７】
直列処理装置（直列処理部１６０）は、並列処理装置（並列処理部１３０）の出力（複数の圧縮ビット列ｈｉ）を受け、この値にある値（直列詰め物Ｐ２）をパディングし、ある長さごとにこの値（直列結合ビット列Ｈ＊）を分割する装置（分割部１６４）と、この装置の出力値（複数の直列ビット列ｙｉ）を受け、ＳＰＲ性圧縮関数をＭＤ構造につないだ関数を計算する装置（直列圧縮部１６６）を有する。
【０１２８】
以上説明したハッシュ関数演算装置１００によれば、ＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。また、以上説明したハッシュ関数演算装置１００を用いれば、安全かつ効率的な署名を構成することができる。
【０１２９】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力しｂビットのビット列を出力するＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムなａビットの鍵Ｋ１（並列ハッシュ鍵）を生成する。並列詰め物結合部１３２は、長さがａビットの倍数となる値Ｍ＊＝Ｍ‖１‖０ｕ‖０ａを生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ”＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ｍｉ”（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉとする。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数の値Ｈ＊＝ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖ‖＜Ｍ＞を生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｙ１‖ｙ２‖…‖ｙｓとする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここで、ｃ０＝ＩＶで、ＩＶはｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名として（Ｋ１，σ（ｃｓ））を出力する。
【０１３０】
以上説明したハッシュ関数演算方法は、ＳＰＲ性圧縮関数を並列に並べ、ＳＰＲ性圧縮関数への入力にランダムな鍵（並列ハッシュ鍵Ｋ１）を排他的論理和する処理を、ＳＰＲ性圧縮関数を直列に並べるＭＤ構造に加えたものである。
【０１３１】
実施の形態３．
実施の形態３について、説明する。
この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成、並列処理部１３０及び直列処理部１６０の内部ブロックの構成は、実施の形態２で説明したものと同様なので、図１１〜図１３を参照しつつ、実施の形態２と異なる部分について説明する。
【０１３２】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１＋ｅ１よりも大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１の整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。なお、ｅ１は、１以上の所定の整数であり、例えば、６４である。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットの並列詰め物Ｐ１を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、最後からａ１ビットを「０」、残りのビットを、入力メッセージＭのビット数Ｌ１を二進数で表現したビット列とした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１ビットが「０」、その前のｅ１ビットが入力メッセージＭのビット数Ｌ１を表わす二進数であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【０１３３】
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、並列圧縮部１３６が記憶した圧縮ビット列ｈｉの数ｎを入力し、ＣＰＵ９１１を用いて、ｎ個の圧縮ビット列ｈｉのビット数を合計した整数Ｌ２を算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数Ｌ２に基づいて、以下の条件を満たす整数ｎ２を算出する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、整数ｎ２と整数Ｌ２との和ｎ２＋Ｌ２がａ２の整数倍となる１以上の整数ｎ２のうち、最小の整数ｎ２を算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数ｎ２に基づいて、ｎ２ビットの直列詰め物Ｐ２を生成する。例えば、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを「０」とした直列詰め物Ｐ２を生成する。
なお、直列詰め物生成部１６１が生成する直列詰め物Ｐ２は、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
【０１３４】
以上のような構成とした場合も、実施の形態２と同様、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
【０１３５】
この実施の形態における並列詰め物生成部１３１は、上記処理装置（ＣＰＵ９１１）を用いて、上記入力メッセージＭのビット数Ｌ１をｅ１ビット（ただし、ｅ１は１以上の所定の整数。）の二進数で表現したビット列を含む並列詰め物Ｐ１を生成する。
【０１３６】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１３７】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力しｂビットのビット列を出力するＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムなａビットの鍵Ｋ１（並列ハッシュ鍵）を生成する。並列詰め物結合部１３２は、長さがａビットの倍数となる値Ｍ＊＝Ｍ‖０ｕ‖＜Ｍ＞‖０ａ−ｂを生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ”＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ｍｉ”（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉ（ｉ＝１，２，…，ｎ）とする。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数の値Ｈ＊＝０ａ−ｂ‖ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖを生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｙ１‖ｙ２‖…‖ｙｓとする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここでｃ０＝ＩＶで、ＩＶはｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名（Ｋ１，σ（ｃｓ））を出力する。
【０１３８】
実施の形態４．
実施の形態４について、図１４を用いて説明する。
【０１３９】
この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成は、実施の形態３で説明したものと同様なので、図１１を参照しつつ、実施の形態３と異なる部分について説明する。
【０１４０】
ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、ａ１−ｂ１ビットのハッシュ鍵Ｋを入力する。ハッシュ鍵入力部１２０が入力するハッシュ鍵Ｋは、ａ１−ｂ１ビットの並列ハッシュ鍵Ｋ１からなる。ハッシュ鍵入力部１２０は、ＲＡＭ９１４を用いて、入力した並列ハッシュ鍵Ｋ１を記憶する。
【０１４１】
図１４は、この実施の形態における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図である。
なお、実施の形態１で説明したハッシュ関数演算装置１００と共通する部分については、同一の符号を付し、ここでは説明を省略する。
【０１４２】
ハッシュ関数演算装置１００は、並列初期値記憶部１４１を有する。
並列初期値記憶部１４１は、ＲＯＭ９１３を用いて、ｂ１ビットのビット列ＩＶ’（以下「並列初期値ビット列」と呼ぶ。）をあらかじめ記憶している。並列初期値ビット列ＩＶ’は、あらかじめ定められた所定のビット列である。なお、並列初期値ビット列ＩＶ’は、直列初期値記憶部１４２が記憶した直列初期値ビット列ＩＶと同じであってもよいし、異なっていてもよい。並列初期値ビット列ＩＶ’と直列初期値ビット列ＩＶとが同じ場合には、一つの初期値記憶部が、並列初期値記憶部１４１と直列初期値記憶部１４２とを兼ねる構成としてもよい。
【０１４３】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１＋ｅ１よりも大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１−ｂ１の整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットの並列詰め物Ｐ１を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、最後からａ１ビットを「０」、残りのビットを、入力メッセージＭのビット数Ｌ１を二進数で表現したビット列とした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１ビットが「０」、その前のｅ１ビットが入力メッセージＭのビット数Ｌ１を表わす二進数であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【０１４４】
並列分割部１３４は、ＣＰＵ９１１を用いて、並列詰め物結合部１３２が記憶した並列結合ビット列Ｍ＊を入力する。並列分割部１３４は、ＣＰＵ９１１を用いて、入力した並列結合ビット列Ｍ＊に基づいて、並列結合ビット列Ｍ＊をａ１−ｂ１ビットごとに分割した複数の並列分割ビット列ｍｉ（ただし、ｉは１以上ｎ以下の整数。ｎは並列分割ビット列ｍｉの数。）を生成する。並列分割部１３４は、ＲＡＭ９１４を用いて、生成したｎ個の並列分割ビット列ｍｉを記憶する。
【０１４５】
並列生成部１３５は、ＣＰＵ９１１を用いて、並列ハッシュ鍵入力部１２１が記憶した並列ハッシュ鍵Ｋ１と、並列初期値記憶部１４１が記憶した並列初期値ビット列ＩＶ’と、並列分割部１３４が記憶したｎ個の並列分割ビット列ｍｉとを入力する。並列生成部１３５は、ＣＰＵ９１１を用いて、入力した並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉとに基づいて、並列ハッシュ鍵Ｋ１とｎ個の並列分割ビット列ｍｉそれぞれとの間の排他的論理和を取り、ｎ個の並列撹乱ビット列ｍｉ’（ただし、ｉは１以上ｎ以下の整数。）を生成する。ここで、並列ハッシュ鍵Ｋ１及びｎ個の並列分割ビット列ｍｉは、それぞれａ１−ｂ１ビットのビット列であり、並列生成部１３５が生成する並列撹乱ビット列ｍｉ’も同じく、ａ１−ｂ１ビットのビット列である。
並列生成部１３５は、ＣＰＵ９１１を用いて、生成したｎ個の並列撹乱ビット列ｍｉ’と、入力した並列初期値ビット列ＩＶ’とに基づいて、ｎ個の並列撹乱ビット列ｍｉ’それぞれと、並列初期値ビット列ＩＶ’とを結合したｎ個の並列ビット列ｍｉ”（ただし、ｉは１以上ｎ以下の整数。）を生成する。例えば、並列生成部１３５は、ＣＰＵ９１１を用いて、ｎ個の並列撹乱ビット列ｍｉ’それぞれの後に、並列初期値ビット列ＩＶ’を結合して、ｎ個の並列ビット列ｍｉ”を生成する。並列生成部１３５が生成するｎ個の並列ビット列ｍｉ”のビット数は、ａ１ビットである。
並列生成部１３５は、ＲＡＭ９１４を用いて、生成したｎ個の並列ビット列ｍｉ”を記憶する。
【０１４６】
この実施の形態における直列処理部１６０の内部ブロックの構成は、実施の形態３で説明したものと同様なので、ここでは説明を省略する。
【０１４７】
証明は省略するが、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がｐＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
一般に、ｐＳＰＲ性を満たす圧縮関数を構成するほうが、ＳＰＲ性を満たす圧縮関数を構成するよりも容易であり、ＳＰＲ性を満たさない圧縮関数であっても、ｐＳＰＲ性を満たす場合がある。
したがって、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０がＳＰＲ性を満たさない場合であっても、ｐＳＰＲ性さえ満たしていれば、ｅＴＣＲ性を満たすハッシュ関数を計算するハッシュ関数演算装置１００を構成できる。例えば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０がＳＰＲ性を満たすと考えられる圧縮関数を計算するよう構成したが、のちに、この圧縮関数がＳＰＲ性を満たさないことが判定した場合であっても、ｐＳＰＲ性を満たしていれば、ハッシュ関数演算装置１００が計算するハッシュ関数のｅＴＣＲ性を確保できる。このため、ハッシュ関数演算装置１００が算出したハッシュ値を用いて、攻撃に対する耐性が強く安全な電子署名システムを構築することができる。
【０１４８】
なお、圧縮関数のｐＳＰＲ性とは、以下のように定義される。
圧縮関数が入力するビット列のビット数をａ、出力するビット列のビット数をｂとし、ｂビットのビット列ｃと、ａ−ｂビットのビット列ｍとを結合したビット列を入力した場合に、圧縮関数が出力するビット列をｈ（ｃ，ｍ）とする。
攻撃者には、あらかじめ定められたｂビットの固定ビット列ｃと、ａ−ｂビットのランダムなビット列ｍとが与えられる。攻撃者は、ｈ（ｃ，ｍ）＝ｈ（ｃ，ｍ’）となるａ−ｂビットのビット列ｍ’（ただし、ｍ≠ｍ’。）を見つけようとする。総当り攻撃よりも速くビット列ｍ’を見つけることができる攻撃者が存在しない場合に、その圧縮関数は、ｐＳＰＲ性を満たす。
【０１４９】
圧縮関数のｐＳＰＲ性を破る攻撃者が存在すると仮定すると、固定ビット列ｃと、その攻撃者が見つけたビット列ｍ’との組は、圧縮関数のＳＰＲ性を破る。
しかし、圧縮関数のＳＰＲ性を破る攻撃者が存在すると仮定しても、その攻撃者が見つけたビット列ｍ’は、ｃ＝ｃ’でない限り、圧縮関数のｐＳＰＲ性を破らない。
したがって、攻撃者にとって、ｐＳＰＲ性を破るほうがＳＰＲ性を破るより難しい。圧縮関数を構成する側の立場から言うと、ｐＳＰＲ性を満たす圧縮関数を構成するほうがＳＰＲ性を満たす圧縮関数を構成するよりも容易である。
【０１５０】
この実施の形態における並列生成部１３５は、上記処理装置（ＣＰＵ９１１）を用いて、上記並列ハッシュ鍵入力部１２１が入力したハッシュ鍵Ｋ１と、上記並列分割部１３４が生成した複数の並列分割ビット列ｍそれぞれとに基づいて、上記ハッシュ鍵Ｋ１と上記並列分割ビット列ｍとの排他的論理和をそれぞれ算出して複数の並列撹乱ビット列ｍ’とし、算出した複数の並列撹乱ビット列ｍ’それぞれに基づいて、上記複数の並列撹乱ビット列ｍ’と所定の並列固定ビット列（並列初期値ビット列ＩＶ’）とを結合したビット列をそれぞれ生成して上記複数の並列ビット列ｍ”とする。
【０１５１】
この実施の形態におけるハッシュ関数演算装置１００によれば、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がｐＳＰＲ性を満たす圧縮関数であれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１５２】
この実施の形態における並列圧縮関数演算部１５０は、上記処理装置（ＣＰＵ９１１）を用いて、ｐＳＰＲ性圧縮関数を演算することにより、上記入力ビット列に基づいて上記並列出力ビット列を生成する。
【０１５３】
この実施の形態におけるハッシュ関数演算装置１００によれば、ｅＴＣＲ性を満たすハッシュ関数を演算することができるという効果を奏する。
【０１５４】
以上説明したハッシュ関数演算装置１００は、ランダムな固定鍵Ｋ１（並列ハッシュ鍵）を生成する固定鍵装置（ハッシュ鍵生成部８１２）と、前記固定鍵装置の出力Ｋ１と任意長のメッセージＭ（入力メッセージ）を受け、任意長のメッセージ（入力メッセージＭ）の長さ（ビット数Ｌ１）に依存した長さの値（複数の圧縮ビット列ｈｉ）を出力する並列処理装置（並列処理部１３０）と、並列処理装置の出力（複数の圧縮ビット列ｈｉ）を受け、固定長の値（ハッシュ値Ｈ）を出力する直列処理装置（直列処理部１６０）を有するｅＴＣＲ性ハッシュ関数装置である。
【０１５５】
並列処理装置（並列処理部１３０）は、任意長メッセージＭ（入力メッセージ）を受け、Ｍにある値（並列詰め物Ｐ１）をパディングし、ある長さごとにこの値（並列結合ビット列Ｍ＊）を分割する装置（並列分割部１３４）と、この装置の出力値（複数の並列分割ビット列ｍｉ）と鍵Ｋ１（並列ハッシュ鍵）を受け、この値ごとにＫ１を排他的論理和する装置（直列生成部１６５）と、その装置の出力（複数の並列ビット列ｍｉ”）を受け、その値それぞれをｐＳＰＲ性圧縮関数で計算する装置（直列圧縮部１６６）と、この装置の出力（複数の圧縮ビット列ｈｉ）を受け、値を結合する装置（直列詰め物結合部１６２）を有する。
【０１５６】
直列処理装置（直列処理部１６０）は、並列処理装置（並列処理部１３０）の出力（複数の圧縮ビット列ｈｉ）を受け、この値にある値（直列詰め物Ｐ２）をパディングし、ある長さごとにこの値（直列結合ビット列Ｈ＊）を分割する装置（分割部１６４）と、この装置の出力値（複数の直列ビット列ｙｉ）を受け、ｐＳＰＲ性圧縮関数をＭＤ構造につないだ関数を計算する装置（直列圧縮部１６６）を有する。
【０１５７】
以上説明したハッシュ関数演算装置１００によれば、ｐＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。
【０１５８】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力してｂビットのビット列を出力するｐＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムなａ−ｂビットの鍵Ｋ１（並列ハッシュ鍵）を生成する。並列詰め物結合部１３２は、長さがａ−ｂビットの倍数となる値Ｍ＊＝Ｍ‖０ｕ‖＜Ｍ＞‖０ａ−ｂを生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａ−ｂビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ’＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ＩＶ’‖ｍｉ’（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉ（ｉ＝１，２，…，ｎ）とする。ここで、ＩＶ’はあらかじめ定められたｂビットの固定値である。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数の値Ｈ＊＝０ａ−ｂ‖ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖを生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｘ１‖ｘ２‖…‖ｘｓとする。直列生成部１６５は、ｘｉ（ｉ＝１，２，…，ｓ）とＫ２とを排他的論理和し、ｙｉ＝ｘｉ  ＸＯＲ  Ｋ２とする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここで、ｃ０＝ＩＶで、ＩＶはＩＶ’と異なるｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名（Ｋ１，σ（ｃｓ））を出力する。
【０１５９】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０によれば、安全かつ効率的な署名を構成することができる。
【０１６０】
以上説明したハッシュ関数演算方法は、ｐＳＰＲ性圧縮関数を並列に並べ、ｐＳＰＲ性圧縮関数への入力にランダムな鍵（並列ハッシュ鍵Ｋ１）を排他的論理和する処理を、ｐＳＰＲ性圧縮関数を直列に並べるＭＤ構造に加えたものである。
【０１６１】
以上説明したハッシュ関数演算方法によれば、ｐＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。
【０１６２】
以上のように、圧縮関数の繰り返し構造に対して、圧縮関数の並列処理部分とハッシュ鍵を加えることにより、比較的簡易に構成できるｐＳＰＲ性圧縮関数から、短い長さのハッシュ鍵を用い、署名関数との親和性が高いｅＴＣＲ性ハッシュ関数を構成できる。
【０１６３】
実施の形態５．
実施の形態５について、説明する。
この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成、並列処理部１３０及び直列処理部１６０の内部ブロックの構成は、実施の形態４で説明したものと同様なので、図１１、図１３、図１４を参照しつつ、実施の形態４と異なる部分について説明する。
【０１６４】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１−ｂ１よりも大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１−ｂ１の整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットの並列詰め物Ｐ１を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを「０」とした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１−ｂ１ビットが「０」であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【０１６５】
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭと、並列圧縮部１３６が記憶した圧縮ビット列ｈｉの数ｎとを入力し、ＣＰＵ９１１を用いて、入力メッセージＭのビット数Ｌ１と、ｎ個の圧縮ビット列ｈｉのビット数を合計した整数Ｌ２とを算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数Ｌ２に基づいて、以下の条件を満たす整数ｎ２を算出する。直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、整数ｎ２がａ２＋ｅ２より大きく、かつ、整数ｎ２と整数Ｌ２との和ｎ２＋Ｌ２がａ２の整数倍となる整数ｎ２のうち、最小の整数ｎ２を算出する。
直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、算出した整数ｎ２に基づいて、ｎ２ビットの直列詰め物Ｐ２を生成する。例えば、直列詰め物生成部１６１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを、入力メッセージＭのビット数Ｌ１を二進数で表現したビット列とした直列詰め物Ｐ２を生成する。
なお、直列詰め物生成部１６１が生成する直列詰め物Ｐ２は、最後からｅ２ビットが入力メッセージＭのビット数Ｌ１を表わす二進数であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
直列詰め物生成部１６１は、ＲＡＭ９１４を用いて、生成した直列詰め物Ｐ２を記憶する。
【０１６６】
以上のような構成とした場合も、実施の形態４と同様、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がｐＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
【０１６７】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力しｂビットのビット列を出力するｐＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムなａ−ｂビットの鍵Ｋ１（並列ハッシュ鍵）を生成する。並列詰め物結合部１３２は、長さがａ−ｂビットの倍数となる値Ｍ＊＝Ｍ‖１‖０ｕ‖０ａ−ｂを生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａ−ｂビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ”＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ＩＶ’‖ｍｉ”（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉとする。ここで、ＩＶ’はあらかじめ定められたｂビットの固定値である。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数の値Ｈ＊＝ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖ‖＜Ｍ＞を生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｙ１‖ｙ２‖…‖ｙｓとする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここでｃ０＝ＩＶで、ＩＶはＩＶ’と異なるｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名として（Ｋ１，σ（ｃｓ））を出力する。
【０１６８】
実施の形態６．
実施の形態６について、説明する。
この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成は、実施の形態１で説明したものと同様なので、図５及び図６を参照しつつ、実施の形態１と異なる部分について説明する。
【０１６９】
ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、ａ１＋ａ２−ｂ１ビットのハッシュ鍵Ｋを入力する。ハッシュ鍵入力部１２０が入力するハッシュ鍵Ｋは、ａ１−ｂ１ビットの並列ハッシュ鍵Ｋ１と、ａ２ビットの直列ハッシュ鍵Ｋ２とが結合したビット列である。ハッシュ鍵入力部１２０は、ＣＰＵ９１１を用いて、並列ハッシュ鍵Ｋ１と直列ハッシュ鍵Ｋ２とを入力する。ハッシュ鍵入力部１２０は、ＲＡＭ９１４を用いて、入力した並列ハッシュ鍵Ｋ１及び直列ハッシュ鍵Ｋ２を記憶する。
【０１７０】
この実施の形態における並列処理部１３０の内部ブロックの構成は、実施の形態４で説明したものと同様なので、図１４を参照しつつ、実施の形態４と異なる部分について説明する。
【０１７１】
並列初期値記憶部１４１は、ＲＯＭ９１３を用いて、直列初期値記憶部１４２が記憶した直列初期値ビット列ＩＶとは異なる並列初期値ビット列ＩＶ’をあらかじめ記憶している。
【０１７２】
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、メッセージ入力部１１０が記憶した入力メッセージＭを入力する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、入力した入力メッセージＭに基づいて、入力メッセージＭのビット数Ｌ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出したビット数Ｌ１に基づいて、以下の条件を満たす整数ｎ１を算出する。並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、整数ｎ１がａ１−ｂ１より大きく、かつ、整数ｎ１とビット数Ｌ１との和ｎ１＋Ｌ１がａ１−ｂ１の整数倍となる整数ｎ１のうち、最小の整数ｎ１を算出する。
並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、算出した整数ｎ１に基づいて、ｎ１ビットの並列詰め物Ｐ１を生成する。例えば、並列詰め物生成部１３１は、ＣＰＵ９１１を用いて、最初のビットを「１」、残りのビットを「０」とした並列詰め物Ｐ１を生成する。
なお、並列詰め物生成部１３１が生成する並列詰め物Ｐ１は、最後からａ１−ｂ１ビットが「０」であればよく、残りのビットは、あらかじめ定めた所定のパターンにしたがっていれば、他の値であってもよい。
並列詰め物生成部１３１は、ＲＡＭ９１４を用いて、生成した並列詰め物Ｐ１を記憶する。
【０１７３】
この実施の形態における直列処理部１６０の内部ブロックの構成は、実施の形態１で説明したものと同様なので、ここでは説明を省略する。
【０１７４】
以上のような構成とした場合も、実施の形態４及び実施の形態５と同様、並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０が計算する圧縮関数がｐＳＰＲ性を満たす場合、ハッシュ関数演算装置１００が計算するハッシュ関数はｅＴＣＲ性を満たす。
【０１７５】
以上説明したハッシュ関数演算装置１００は、ランダムな固定鍵Ｋ１‖Ｋ２（ハッシュ鍵Ｋ）を生成する固定鍵装置（ハッシュ鍵生成部８１２）と、前記固定鍵装置の出力の一部Ｋ１（並列ハッシュ鍵）と任意長のメッセージＭ（入力メッセージ）を受け、任意長のメッセージ（入力メッセージＭ）の長さ（ビット数Ｌ１）に依存した長さの値（複数の圧縮ビット列ｈｉ）を出力する並列処理装置（並列処理部１３０）と、並列処理装置の出力（複数の圧縮ビット列ｈｉ）と固定鍵装置の出力の一部Ｋ２（直列ハッシュ鍵）を受け、固定長の値（ハッシュ値Ｈ）を出力する直列処理装置（直列処理部１６０）を有するｅＴＣＲ性ハッシュ関数装置である。
【０１７６】
並列処理装置（並列処理部１３０）は、任意長メッセージＭ（入力メッセージ）を受け、Ｍにある値（並列詰め物Ｐ１）をパディングし、ある長さごとにこの値（並列結合ビット列Ｍ＊）を分割する装置（並列分割部１３４）と、この装置の出力値（複数の並列分割ビット列ｍｉ）と鍵の一部Ｋ１（並列ハッシュ鍵）を受け、この値ごとにＫ１を排他的論理和する装置（並列生成部１３５）と、その装置の出力（複数の並列ビット列ｍｉ”）を受け、その値それぞれをｐＳＰＲ性圧縮関数で計算する装置（並列圧縮部１３６）と、この装置の出力（複数の圧縮ビット列ｈｉ）を受け、値を結合する装置（直列詰め物結合部１６２）とを有する。
【０１７７】
直列処理装置（直列処理部１６０）は、並列処理装置（並列処理部１３０）の出力を受け、この値（複数の圧縮ビット列ｈｉ）にある値（直列詰め物Ｐ２）をパディングし、ある長さごとにこの値（直列結合ビット列Ｈ＊）を分割する装置（分割部１６４）と、この装置の出力値（複数の直列分割ビット列ｘｉ）と鍵の一部Ｋ２（直列ハッシュ鍵）を受け、装置の出力値をそれぞれＫ２と排他的論理和する装置（直列生成部１６５）と、この装置の出力（複数の直列ビット列ｙｉ）を受け、ｐＳＰＲ性圧縮関数をＭＤ構造につないだ関数を計算する装置（直列圧縮部１６６）とを有する。
【０１７８】
以上説明したハッシュ関数演算装置１００によれば、ｐＳＰＲ性圧縮関数からｅＴＣＲ性ハッシュ関数を構成することができる。
【０１７９】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０は、以下の動作をする。
Ｍを署名をつけたいメッセージとする。並列圧縮関数演算部１５０及び直列圧縮関数演算部１８０は、ａビットのビット列を入力してｂビットのビット列を出力するｐＳＰＲ性圧縮関数を計算する。ハッシュ鍵生成部８１２は、ランダムな２（ａ−ｂ）ビットの鍵Ｋ１‖Ｋ２（ただし、｜Ｋ１｜＝ａ−ｂ。｜Ｋ２｜＝ａ−ｂ。）を生成する。並列詰め物結合部１３２は、長さがａ−ｂビットの倍数となる値Ｍ＊＝Ｍ‖０ｕ‖０ａ−ｂを生成する。ただし、ｕの長さが最小となるようにする。並列分割部１３４は、ａ−ｂビットごとにＭ＊を分割し、Ｍ＊＝ｍ１‖ｍ２‖…‖ｍｎとする。並列生成部１３５は、ｍｉ（ｉ＝１，２，…，ｎ）とＫ１とを排他的論理和し、ｍｉ’＝ｍｉ  ＸＯＲ  Ｋ１（ｉ＝１，２，…，ｎ）とする。並列圧縮部１３６は、ＩＶ’‖ｍｉ’（ｉ＝１，２，…，ｎ）を圧縮関数の入力として並列圧縮関数演算部１５０に計算させ、その出力値をｈｉ（ｉ＝１，２，…，ｎ）とする。ここで、ＩＶ’はあらかじめ定められたｂビットの固定値である。直列詰め物結合部１６２は、ｈ１，ｈ２，…，ｈｎをビット結合し、長さがａ−ｂの倍数となる値Ｈ＊＝０ａ−ｂ‖ｈ１‖ｈ２‖…‖ｈｎ‖１‖０ｖ‖＜Ｍ＞を生成する。ただし、ｖの長さが最小となるようにする。分割部１６４は、Ｈ＊をａ−ｂビットごとに分割し、Ｈ＊＝ｘ１‖ｘ２‖…‖ｘｓとする。直列生成部１６５は、ｘｉ（ｉ＝１，２，…，ｓ）とＫ２とを排他的論理和し、ｙｉ＝ｘｉ  ＸＯＲ  Ｋ２（ｉ＝１，２，…，ｓ）とする。直列圧縮部１６６は、ｃｉ−１‖ｙｉ（ｉ＝１，２，…，ｓ）を圧縮関数の入力として直列圧縮関数演算部１８０に計算させ、ｃｉとする。ここで、ｃ０＝ＩＶで、ＩＶはＩＶ’と異なるｂビットの固定値である。署名関数演算部８１３は、σ（ｃｓ）（ただし、σは署名関数。）を計算する。署名出力部８１４は、Ｍに対する署名（Ｋ１，Ｋ２，σ（ｃｓ））を出力する。
【０１８０】
以上説明したハッシュ関数演算装置１００を用いた署名装置８１０によれば、安全かつ効率的な署名を構成することができる。
【０１８１】
以上説明したハッシュ関数演算方法は、ｐＳＰＲ性圧縮関数を並列に並べ、圧縮関数への入力にランダムな鍵（並列ハッシュ鍵Ｋ１）を排他的論理和する処理と、ｐＳＰＲ性圧縮関数の出力に別のランダムな鍵（直列ハッシュ鍵Ｋ２）を排他的論理和する処理とを、ｐＳＰＲ性圧縮関数を直列に並べるＭＤ構造に加えたものである。
【０１８２】
実施の形態７．
実施の形態７について、図１５を用いて説明する。
【０１８３】
実施の形態２または実施の形態５で説明したハッシュ関数演算装置１００のうち、直列処理部１６０の構成は、ＭＤ５やＳＨＡ−１を計算する既存のハッシュ関数演算装置の構成と共通している。
この実施の形態では、ＭＤ５やＳＨＡ−１を計算する既存のハッシュ関数演算装置を利用して、ハッシュ関数演算装置を構成する方式について説明する。
【０１８４】
図１５は、この実施の形態におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図である。
なお、実施の形態２または実施の形態５で説明したハッシュ関数演算装置１００と共通する部分については、同一の符号を付し、ここでは説明を省略する。
【０１８５】
ハッシュ関数演算装置１００は、圧縮結合部１７０、ハッシュ関数演算装置２００を有する。
ハッシュ関数演算装置２００は、ＭＤ５やＳＨＡ−１を計算する既存のハッシュ関数演算装置である。ハッシュ関数演算装置２００は、任意のビット数のビット列を入力し、所定のビット数のビット列を算出して、出力する。
【０１８６】
圧縮結合部１７０は、ＣＰＵ９１１を用いて、並列処理部１３０が記憶したｎ個の圧縮ビット列ｈｉを入力する。圧縮結合部１７０は、ＣＰＵ９１１を用いて、入力したｎ個の圧縮ビット列ｈｉに基づいて、ｎ個の圧縮ビット列ｈｉをすべて結合したビット列（以下「圧縮結合ビット列Ｍ’」と呼ぶ。）を生成する。圧縮結合部１７０は、ＣＰＵ９１１を用いて、生成した圧縮結合ビット列Ｍ’を、ハッシュ関数演算装置２００に入力する。
【０１８７】
ハッシュ値出力部１９０は、ＣＰＵ９１１を用いて、ハッシュ関数演算装置２００が入力した圧縮結合ビット列Ｍ’に対するハッシュ値として算出したビット列を取得して、ハッシュ値Ｈとする。ハッシュ値出力部１９０は、ＣＰＵ９１１を用いて、取得したハッシュ値Ｈを出力する。
【０１８８】
以上のように構成することにより、既存のハッシュ関数演算装置２００を利用して、ハッシュ関数演算装置１００を構成することができる。特に、ハッシュ関数演算装置１００を論理回路を用いて構成する場合、論理回路を用いて構成された既存のハッシュ関数演算装置２００に、他の機能ブロックを実現する論理回路を付加すればよく、ハッシュ関数演算装置１００の製造コストを低くすることができる。また、既存のハッシュ関数演算装置２００を再利用するので、資源を無駄にせず、環境への負荷を減らすことができる。
【０１８９】
このように、並列圧縮関数演算部１５０が計算する圧縮関数がＳＰＲ性あるいはｐＳＰＲ性を満たすよう構成すれば、直列圧縮関数演算部１８０が計算する圧縮関数としてＭＤ５やＳＨＡ−１を計算するハッシュ関数が使用している圧縮関数を使用しても、ｅＴＣＲ性を満たすハッシュ関数を計算するハッシュ関数演算装置１００を構成できる。このため、ハッシュ関数演算装置１００が算出したハッシュ値を用いて、攻撃に対する耐性が強く安全な電子署名システムを構築することができる。
【図面の簡単な説明】
【０１９０】
【図１】実施の形態１における署名装置８１０の構成の一例を示す全体構成図。
【図２】実施の形態１における署名検証装置８２０の構成の一例を示す全体構成図。
【図３】実施の形態１における署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００の外観の一例を示す図。
【図４】実施の形態１における署名装置８１０、署名検証装置８２０あるいはハッシュ関数演算装置１００のハードウェア資源の一例を示す図。
【図５】実施の形態１におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図６】実施の形態１における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図。
【図７】実施の形態１における直列処理部１６０の内部ブロックの一例を示す詳細ブロック構成図。
【図８】実施の形態１におけるハッシュ関数演算装置１００が鍵付きハッシュ値を算出するハッシュ関数演算処理の流れの一例を示すフローチャート図。
【図９】実施の形態１における並列処理部１３０が並列処理をする並列処理工程Ｓ７３０の流れの一例を示すフローチャート図。
【図１０】実施の形態１における直列処理部１６０が直列処理をする直列処理工程Ｓ７６０の流れの一例を示すフローチャート図。
【図１１】実施の形態２におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図。
【図１２】実施の形態２における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図。
【図１３】実施の形態２における直列処理部１６０の内部ブロックの構成の一例を示す詳細ブロック構成図。
【図１４】実施の形態４における並列処理部１３０の内部ブロックの構成の一例を示す詳細ブロック構成図。
【図１５】実施の形態７におけるハッシュ関数演算装置１００の機能ブロックの構成の一例を示すブロック構成図。
【符号の説明】
【０１９１】
１００  ハッシュ関数演算装置、１１０  メッセージ入力部、１２０  ハッシュ鍵入力部、１２１  並列ハッシュ鍵入力部、１２２  直列ハッシュ鍵入力部、１３０  並列処理部、１３１  並列詰め物生成部、１３２  並列詰め物結合部、１３４  並列分割部、１３５  並列生成部、１３６  並列圧縮部、１４１  並列初期値記憶部、１４２  直列初期値記憶部、１４３  並列固定記憶部、１５０  並列圧縮関数演算部、１６０  直列処理部、１６１  直列詰め物生成部、１６２  直列詰め物結合部、１６３  直列分割部、１６４  分割部、１６５  直列生成部、１６６  直列圧縮部、１７０  圧縮結合部、１８０  直列圧縮関数演算部、１９０  ハッシュ値出力部、２００  ハッシュ関数演算装置、８１０  署名装置、８１１，８２１  署名対象メッセージ入力部、８１２  ハッシュ鍵生成部、８１３  署名関数演算部、８１４  署名出力部、８２０  署名検証装置、８２２  署名入力部、８２３  署名復号演算部、８２４  署名比較部、９０１  表示装置、９０２  キーボード、９０３  マウス、９０４  ＦＤＤ、９０５  ＣＤＤ、９０６  プリンタ装置、９０７  スキャナ装置、９１０  システムユニット、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信装置、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群、９３１  電話器、９３２  ファクシミリ機、９４０  インターネット、９４１  ゲートウェイ、９４２  ＬＡＮ。
【図１】
2009169316.tif 000003
【図２】
2009169316.tif 000004
【図３】
2009169316.tif 000005
【図４】
2009169316.tif 000006
【図５】
2009169316.tif 000007
【図６】
2009169316.tif 000008
【図７】
2009169316.tif 000009
【図８】
2009169316.tif 000010
【図９】
2009169316.tif 000011
【図１０】
2009169316.tif 000012
【図１１】
2009169316.tif 000013
【図１２】
2009169316.tif 000014
【図１３】
2009169316.tif 000015
【図１４】
2009169316.tif 000016
【図１５】
2009169316.tif 000017