(57)【要約】【課題】実装規模が小さく理論的安全性と実装安全性が保証されたハッシュ関数を提供すること。【解決手段】  入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、入力されたメッセージのハッシュ値を生成する制御部１２０を備え、制御部１２０で行う変換処理におけるシフト変換では、シフトするビット数を奇数及び偶数がそれぞれ少なくとも一つずつ含むようにする。【選択図】図１
2007316614.tif 000002
【特許請求の範囲】
【請求項１】
入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備えるハッシュ値生成装置であって、
前記制御部が行う前記変換処理には、シフト変換が含まれており、
前記シフト変換は、入力された二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を予め定められた回数行うものであり、
前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、奇数ビットのシフトを行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、偶数ビットのシフトを行うものであること、
を特徴とするハッシュ値生成装置。
【請求項２】
請求項１に記載のハッシュ値生成装置であって、
前記予め定められた回数は、６回であり、
前記６回のシフト変換でシフトするビット数は、順番にｑ１、ｑ２、ｑ３、ｑ４、ｑ５、ｑ６であり、
ｑ１＋ｑ２、ｑ１＋ｑ４、ｑ３＋ｑ４、ｑ１＋ｑ２＋ｑ３＋ｑ４、ｑ１＋ｑ６、ｑ３＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ６、ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ５＋ｑ６、ｑ１＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、の１３個の値の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにしたこと、
を特徴とするハッシュ値生成装置。
【請求項３】
請求項１に記載のハッシュ値生成装置であって、
前記制御部が行う前記変換処理では、合成変換が行われており、
前記合成変換は、排他的論理和を算出するものであること、
を特徴とするハッシュ値生成装置。
【請求項４】
請求項３に記載のハッシュ値生成装置であって、
前記合成変換には、算術加算は含まれていないこと、
を特徴とするハッシュ値生成装置。
【請求項５】
請求項１に記載のハッシュ値生成装置であって、
ラウンド定数の初期値及びラウンド鍵の初期値を記憶する記憶部を備えており、
前記制御部は、前記変換処理として、
前記記憶部に記憶されている前記ラウンド定数の初期値からラウンド毎のラウンド定数を予め定められた関数で算出する処理と、
ラウンドに対応する前記ラウンド定数と、前記記憶部に記憶されている前記ラウンド鍵の初期値から前回のラウンドで算出されたラウンド鍵と、予め定められた鍵変換関数に入力することによりラウンド毎のラウンド鍵を算出する処理と、
ラウンドに対応する前記ラウンド鍵と、前記メッセージブロックから前回のラウンドで算出された第一平文と、を予め定められた平文変換関数に入力することによりラウンド毎の第一平文を算出する処理と、
を行うものであること、
を特徴とするハッシュ値生成装置。
【請求項６】
請求項５に記載のハッシュ値生成装置であって、
前記鍵変換関数と、前記平文変換関数と、は同じ関数が用いられること、
を特徴とするハッシュ値生成装置。
【請求項７】
請求項６に記載のハッシュ値生成装置であって、
前記鍵変換関数と、前記平文変換関数と、は、
入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）、Ｙ６（ｒ）、Ｙ７（ｒ）に分割し、
Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）の値を、それぞれ、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）に変換し、
Ｙ４（ｒ）と、予め定められた定数と、の排他的論理和を算出したものと、Ｙ５（ｒ）と、を予め定められた非線形関数に入力して算出された算出値の上位ビットと、Ｙ６（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）の値を連結したデータを出力データとするものであること、
を特徴とするハッシュ値生成装置。
【請求項８】
請求項６に記載のハッシュ値生成装置であって、
前記鍵変換関数と、前記平文変換関数と、は、
入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）に分割し、
Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）の値を、それぞれ、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）に変換し、
Ｙ３（ｒ）と、予め定められた定数と、の排他的論理和を算出したものを予め定められた非線形関数に入力して算出された算出値と、Ｙ４（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）の値を連結したデータを出力データとするものであること、
を特徴とするハッシュ値生成装置。
【請求項９】
コンピュータを、
入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御手段、として機能させるプログラムであって、
前記制御手段が行う前記変換処理には、シフト変換が含まれており、
前記シフト変換は、入力された二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を予め定められた回数行うものであり、
前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、奇数ビットのシフトを行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、偶数ビットのシフトを行うものであること、
を特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
前記予め定められた回数は、６回であり、
前記６回のシフト変換でシフトするビット数は、順番にｑ１、ｑ２、ｑ３、ｑ４、ｑ５、ｑ６であり、
ｑ１＋ｑ２、ｑ１＋ｑ４、ｑ３＋ｑ４、ｑ１＋ｑ２＋ｑ３＋ｑ４、ｑ１＋ｑ６、ｑ３＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ６、ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ５＋ｑ６、ｑ１＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、の１３個の値の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにしたこと、
を特徴とするプログラム。
【請求項１１】
請求項９に記載のプログラムであって、
前記制御手段が行う前記変換処理では、合成変換が行われており、
前記合成変換は、排他的論理和を算出するものであること、
を特徴とするプログラム。
【請求項１２】
請求項１１に記載のプログラムであって、
前記合成変換には、算術加算は含まれていないこと、
を特徴とするプログラム。
【請求項１３】
請求項９に記載のプログラムであって、
前記コンピュータをラウンド定数の初期値及びラウンド鍵の初期値を記憶する記憶手段としても機能させ、
前記制御手段は、前記変換処理として、
前記記憶手段に記憶されている前記ラウンド定数の初期値からラウンド毎のラウンド定数を予め定められた関数で算出する処理と、
ラウンドに対応する前記ラウンド定数と、前記記憶手段に記憶されている前記ラウンド鍵の初期値から前回のラウンドで算出されたラウンド鍵と、予め定められた鍵変換関数に入力することによりラウンド毎のラウンド鍵を算出する処理と、
ラウンドに対応する前記ラウンド鍵と、前記メッセージブロックから前回のラウンドで算出された第一平文と、を予め定められた平文変換関数に入力することによりラウンド毎の第一平文を算出する処理と、
を行うものであること、
を特徴とするプログラム。
【請求項１４】
請求項１３に記載のプログラムであって、
前記鍵変換関数と、前記平文変換関数と、は同じ関数が用いられること、
を特徴とするプログラム。
【請求項１５】
請求項１４に記載のプログラムであって、
前記鍵変換関数と、前記平文変換関数と、は、
入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）、Ｙ６（ｒ）、Ｙ７（ｒ）に分割し、
Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）の値を、それぞれ、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）に変換し、
Ｙ４（ｒ）と、予め定められた定数と、の排他的論理和を算出したものと、Ｙ５（ｒ）と、を予め定められた非線形関数に入力して算出された算出値の上位ビットと、Ｙ６（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）の値を連結したデータを出力データとするものであること、
を特徴とするプログラム。
【請求項１６】
請求項１４に記載のプログラムであって、
前記鍵変換関数と、前記平文変換関数と、は、
入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）に分割し、
Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）の値を、それぞれ、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）に変換し、
Ｙ３（ｒ）と、予め定められた定数と、の排他的論理和を算出したものを予め定められた非線形関数に入力して算出された算出値と、Ｙ４（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）の値を連結したデータを出力データとするものであること、
を特徴とするプログラム。
【請求項１７】
入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備えるハッシュ値生成装置が行うハッシュ値生成方法であって、
前記制御部が行う前記変換処理には、シフト変換を行う過程が含まれており、
前記シフト変換を行う過程は、入力された二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を予め定められた回数行うものであり、
前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、奇数ビットのシフトを行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、偶数ビットのシフトを行うものであること、
を特徴とするハッシュ値生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関する。
【背景技術】
【０００２】
近年、携帯電話端末、非接触型ＩＣカード、商品タグ等のようにモビリティの高いデバイスを用いたサービスが急速に拡大している。
【０００３】
このようなモビリティの高いデバイスを用いたサービスでは、サービス提供者や被提供者を識別するために、認証技術が通常用いられる。
【０００４】
ここで、認証技術としては、ＭＡＣ（Message Authentication Code: メッセージ認証子）生成方法を用いたものがよく知られているが、ＭＡＣ生成方法として、暗号学的ハッシュ関数に基づいたＭＡＣ生成方法であるＨＭＡＣ構成法がある。
【０００５】
ハッシュ関数は任意長のメッセージを入力として、ハッシュ値を生成して出力する。一般的に、ハッシュ関数は固定長のメッセージブロックを入力するブロック暗号から構成され、入力されたメッセージに対してブロック暗号化を繰り返し行うことで、メッセージの攪拌を行い、最終的にハッシュ値として出力する。ハッシュ関数の代表例としてはＳＨＡ−１、ＳＨＡ−２５６、Ｗｈｉｒｌｐｏｏｌといったものがある（非特許文献１参照）。
【０００６】
【非特許文献１】「ISO/IEC 10118-3情報セキュリティ-ハッシュ関数-(ISO/IEC 10118-3, third edition, Information technology-Security techniques-Hash-functions-)」, (スイス), 第三版, 2004年3月1日, pp 13-15, pp 19-22
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ハッシュ関数の代表例として知られているＳＨＡ−１、ＳＨＡ−２５６、Ｗｈｉｒｌｐｏｏｌについては、以下のような問題がある。
【０００８】
まず、ＳＨＡ−１については、衝突耐性という理論的安全性に問題があることが指摘されている。
【０００９】
次に、ＳＨＡ−２５６については、安全性の評価を厳密に行うことは困難であり、特に、現存する攻撃方法で最も脅威とされる差分攻撃法に対する耐性についての厳密な安全性評価は今のところ知られていない。
【００１０】
さらに、Ｗｈｉｒｌｐｏｏｌに関しては、その安全性は評価されているが、主に高速性を重点において設計されているため、携帯電話端末、非接触型ＩＣカード、商品タグ等のようにモビリティの高いデバイス等のような軽量実装向けとはいえない。
【００１１】
そこで、本発明は、実装規模が小さく理論的安全性と実装安全性が保証されたハッシュ関数を提供することを目的とする。
【課題を解決するための手段】
【００１２】
以上の課題を解決するため、本発明は、入力されたメッセージを予め定められたデータ長のメッセージブロックに分割し、メッセージブロック毎に予め定められた変換処理を繰り返し行う際に、複数回のシフトを行うシフト変換を実行し、少なくとも一つのシフトでは、奇数ビットのシフトを行い、少なくとも一つのシフトでは、偶数ビットのシフトを行う。
【００１３】
例えば、本発明は、入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備えるハッシュ値生成装置であって、前記制御部が行う前記変換処理には、シフト変換が含まれており、前記シフト変換は、入力された二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を予め定められた回数行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、奇数ビットのシフトを行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、偶数ビットのシフトを行うものであること、を特徴とする。
【発明の効果】
【００１４】
以上のように、本発明によれば、実装規模が小さく理論的安全性と実装安全性が保証されたハッシュ関数を提供することができる。
【発明を実施するための最良の形態】
【００１５】
図１は、本発明の第一の実施形態であるハッシュ値生成装置１００の概略図である。
【００１６】
図示するように、ハッシュ値生成装置１００は、記憶部１１０と、制御部１２０と、入出力部１３０と、を備える。
【００１７】
記憶部１１０は、初期値記憶領域１１１と、鍵ステート記憶領域１１２と、第一の平文ステート記憶領域１１３と、第二の平文ステート記憶領域１１４と、を備える。
【００１８】
初期値記憶領域１１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。
【００１９】
本実施形態においては、ハッシュ値を生成する際の初期値として、ラウンド定数の初期値と、ラウンド鍵の初期値と、が記憶される。
【００２０】
ここで、ラウンド定数の初期値は、例えば、ｃ（０）＝0xcae1ac3f55054a96といった定数が記憶される。
【００２１】
また、ラウンド鍵の初期値は、Ｋ０（０）＝0xbc18bf6d、Ｋ１（０）＝0x369c955b、Ｋ２（０）＝0xbb271cbc、Ｋ３（０）＝0xdd66c368、Ｋ４（０）＝0x356dba5b、Ｋ５（０）＝0x33c00055、Ｋ６（０）＝0x50d2320b、Ｋ７（０）＝0x1c617e21といった定数が記憶される。
【００２２】
なお、ラウンド定数及びラウンド鍵の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【００２３】
鍵ステート記憶領域１１２には、メッセージブロック毎におけるラウンド毎でのラウンド鍵を特定する情報が格納される。
【００２４】
ここで、本実施形態においては、メッセージブロック毎におけるラウンド毎でのラウンド鍵を後述する変換部１２３で生成して、鍵ステート記憶領域１１２に記憶する。
【００２５】
第一の平文ステート記憶領域１１３には、ラウンド毎に算出される第一の平文を特定する情報が格納される。
【００２６】
ここで、本実施形態においては、ラウンド毎に第一の平文を後述する変換部１２３で算出して、第一の平文ステート記憶領域１１３に記憶する。
【００２７】
第二の平文ステート記憶領域１１４には、メッセージブロック毎に算出される第二の平文を特定する情報が格納される。
【００２８】
ここで、本実施形態においては、メッセージブロック毎に第二の平文を後述する変換部１２３で算出して、第二の平文ステート記憶領域１１４に記憶する。
【００２９】
制御部１２０は、メッセージブロック化部１２１と、ラウンド定数生成部１２２と、変換部１２３と、管理部１２４と、全体制御部１２５と、を備える。
【００３０】
メッセージブロック化部１２１は、後述する入出力部１３０を介して入力されたメッセージを予め定められたデータ長のメッセージブロックに分割する処理を行う。
【００３１】
ここで、本実施形態においては、メッセージブロック化部１２１は、後述する入出力部１３０を介して入力されたメッセージを、２５６ビットのメッセージブロックに分割する。
【００３２】
但し、メッセージ長がメッセージブロック（２５６ビット）の倍数ではない場合は、Merkle-Damgaard方式等のパディング方式を用いてメッセージブロックの倍数になるようにパディングを行う。
【００３３】
ラウンド定数生成部１２２は、各ラウンドにおけるラウンド定数を算出する。
【００３４】
本実施形態においては、初期値記憶領域１１１に記憶されているラウンド定数の初期値から各ラウンドにおけるラウンド定数を算出する。
【００３５】
なお、本実施形態では、ラウンド定数生成部１２２として、６４ビットの線形変換である線形フィードバックシフトレジスタＬＲを用いる。
【００３６】
一般に、線形フィードバックシフトレジスタは定義多項式で決定されるが、ここではＬＲを決定する定義多項式ｇ（ｘ）は、次のように定義する。
【００３７】
g(x) = x63 + x62 + x58 + x55 + x54 + x52+ x50 + x49 + x46 + x43 + x40 + x38 + x37 + x35 + x34 + x30 + x28 + x26 + x24 + x23 + x22 + x18 + x17 + x12 + x11 + x10+ x7 + x3 + x2 + 1
但し、ｇは有限体ＧＦ（２）において定義される多項式である。
【００３８】
線形フィードバックシフトレジスタＬＲは、ｃ（０）を初期値とし、第ｒ−１ラウンド定数の基礎値ｃ（ｒ−１）から、第ｒラウンドのラウンド定数の基礎値ｃ（ｒ）を生成する。次に、ラウンド定数生成部１２２はラウンド定数の基礎値ｃ（ｒ）の下位ブロックをラウンド定数Ｃ（ｒ）とする。以下、具体的に説明する。
【００３９】
まず、ラウンド定数生成部１２２は、第ｒ−１ラウンドのラウンド定数の基礎値ｃ（ｒ−１）を線形フィードバックシフトレジスタＬＲに入力することで出力値を算出する（出力値：yH(r)||yL(r) = LR(c(r -1))）。
【００４０】
ここで、ｙLは、基礎値ｃ（ｒ−１）の下位ブロックを予め定められたビット数（本実施形態では、１ビット）だけ、左シフトしたもの。即ち、yL(r) = c(r -1)L << 1  (<< 1は1ビットによる左シフトを表現)。
【００４１】
また、ｙHは、基礎値ｃ（ｒ−１）の上位ブロックを予め定められたビット数（本実施形態では、３１ビット）だけ、左シフトしたもの。即ち、yH(r)= (c(r -1)H << 1)|| (yL >> 31)   (>> 31は31ビットによる右シフトを表現)。
【００４２】
但し、ｃ（ｒ−１）の最上位ビットが「１」の場合のみ、yH(r) =c(r-1)H XOR 0xc4d6496c、yL(r) =c(r-1)L XOR 0x55c61c8d、を用いる。
【００４３】
次に、ラウンド定数生成部１２２は、ＬＲの出力値の上位ビットと下位ビットとを入れ替えることで、第ｒラウンドのラウンド定数の基礎値ｃ（ｒ）を算出する（c(r) = yL(r)||yH(r)）。
【００４４】
そして、ラウンド定数生成部１２２は、次のラウンドのラウンド定数の基礎値ｃ（ｒ）の下位ビットをラウンド定数Ｃ（ｒ）とする（C(r) = c(r)L= yH(r)）。
【００４５】
以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。
【００４６】
C(0) = 0x51151113; C(1) = 0x3b4f5a2f; C(2) = 0x2b0e343a;C(3) = 0x46b151a6; C(4) = 0xac38d0e9; C(5) = 0xde130ff4;C(6) = 0x1b6f7abf; C(7) = 0xbc9a76bc; C(8) = 0xc631d3e6;C(9) = 0xf269daf1; C(10) = 0xdc1106f5; C(11) = 0xa6fd1bb3;C(12) = 0x1f1e6ba2; C(13) = 0x307857d6; C(14) = 0x7c79ae88;C(15) = 0xc1e15f59; C(16) = 0x3530f34d; C(17) = 0x68df0d12;C(18) = 0x7f4ff42f; C(19) = 0x67aa7d25; C(20) = 0x9265a0cb;C(21) = 0xf1f384e2; C(22) = 0xe21aba37; C(23) = 0x03185ae5;C(24) = 0xe73098aa; C(25) = 0xa7ed528f; C(26) = 0x58142bc4;C(27) = 0x34397327; C(28) = 0xa486e67c; C(29) = 0x7b69f586;C(30) = 0x921b99f1; C(31) = 0x29719f74; C(32) = 0xe3e25ede;C(33) = 0xa5c67dd1; C(34) = 0x4b5f3214; C(35) = 0x3c95ce5f;C(36) = 0xe9aa813c; C(37) = 0x59db0067; C(38) = 0x627c4d9d;C(39) = 0x083671eb; C(40) = 0xe6ab4602; C(41) = 0x8b55feb7;C(42) = 0x5e7b5164; C(43) = 0x86dbc3c7; C(44) = 0xbd3b0cfc;C(45) = 0xb0e33606; C(46) = 0xf4ec33f0; C(47) = 0xc38cd819;C(48) = 0x176686ad; C(49) = 0x61691012; C(50) = 0xf61623af;C(51) = 0x41720925; C(52) = 0xb702fecb; C(53) = 0x6a9254e2;C(54) = 0x7787c237; C(55) = 0x6e9f1ae5; C(56) = 0xb14578ab;C(57) = 0xd5261be2; C(58) = 0x6e99dbb7; C(59) = 0x904e26e5;C(60) = 0xd53d1eaa; C(61) = 0xeab4a28f; C(62) = 0x902233c5;C(63) = 0xc588fa4a; C(64) = 0xeb04f60f; C(65) = 0xd2f5a045;C(66) = 0xc349a84b; C(67) = 0x248cf163; C(68) = 0x627cd15a;C(69) = 0x39bffc97; C(70) = 0x4d250c04; C(71) = 0x4d73cb47;C(72) = 0xf042797d; C(73) = 0x5a955d6b; C(74) = 0xae539583;C(75) = 0x050f05da; C(76) = 0x12c26f16; C(77) = 0x143c1768;C(78) = 0x4b09bc58; C(79) = 0x50f05da1; C(80) = 0xe8f0b80d;C(81) = 0x2c9b06f3; C(82) = 0xcc989042; C(83) = 0x19e022d7;C(84) = 0xf6b40864; C(85) = 0xcc0cb247; C(86) = 0x1e0668fd;C(87) = 0x5f68b96a; C(88) = 0xd3959aef; C(89) = 0xb974acc5;C(90) = 0x210c1bca; C(91) = 0x4e5e8a0e; C(92) = 0x84306f29;C(93) = 0xfdac6154; C(94) = 0xbb4d85bf; C(95) = 0x3267cc3c:
変換部１２３は、メッセージブロック毎におけるラウンド毎に、ラウンド鍵及び第一の平文の変換を行う。ここで、変換部で行う変換には、算術加算を含まない。
【００４７】
ここで、本実施形態における変換部１２３は、まず、ラウンド鍵の変換を行う。
【００４８】
ラウンド鍵の変換は、例えば、図２（鍵ステート変換関数ｆｋの概略図）に示す鍵ステート変換関数ｆｋにより行う。
【００４９】
図示するように鍵ステート変換ｆｋは、第ｒラウンドのラウンド鍵を８分割したＫ０（ｒ）、Ｋ１（ｒ）、Ｋ２（ｒ）、Ｋ３（ｒ）、Ｋ４（ｒ）、Ｋ５（ｒ）、Ｋ６（ｒ）、Ｋ７（ｒ）を、それぞれ、Ｋ０（ｒ＋１）、Ｋ１（ｒ＋１）、Ｋ２（ｒ＋１）、Ｋ３（ｒ＋１）、Ｋ４（ｒ＋１）、Ｋ５（ｒ＋１）、Ｋ６（ｒ＋１）、Ｋ７（ｒ＋１）に変換し、変換したこれらの値を連結することで、第ｒ＋１ラウンドのラウンド鍵を生成する関数である。
【００５０】
具体的には、鍵ステート変換関数ｆｋは、まず、変換部１２３が、鍵ステート記憶領域１１２に記憶されている第ｒラウンドのラウンド鍵を、Ｋ０（ｒ）、Ｋ１（ｒ）、Ｋ２（ｒ）、Ｋ３（ｒ）、Ｋ４（ｒ）、Ｋ５（ｒ）、Ｋ６（ｒ）、Ｋ７（ｒ）に８等分する。
【００５１】
次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ０（ｒ）、Ｋ１（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵の内のＫ２（ｒ＋１）、Ｋ３（ｒ＋１）とする。
【００５２】
次に、変換部１２３は、ラウンド定数生成部１２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ４（ｒ）の排他的論理和と、第ｒラウンドのラウンド鍵の内のＫ５（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の上位ビットの値ｂＨを算出する（bH = F(k4 XOR C(r), k5)Ｈ）。
【００５３】
次に、変換部１２３は、ラウンド定数生成部１２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ４（ｒ）の排他的論理和と、第ｒラウンドのラウンド鍵の内のＫ５（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の下位ビットの値ｂＬを算出する（bＬ = F(k4 XOR C(r), k5)Ｌ）。
【００５４】
次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ２（ｒ）、Ｋ３（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵Ｋ４（ｒ＋１）、Ｋ５（ｒ＋１）とする。
【００５５】
次に、変換部１２３は、値ｂＨと、第ｒラウンドのラウンド鍵の内のＫ６（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドのラウンド鍵のＫ０（ｒ＋１）とする。
【００５６】
次に、変換部１２３は、値ｂＬと、第ｒラウンドのラウンド鍵の内のＫ７（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドのラウンド鍵のＫ１（ｒ＋１）とする。
【００５７】
次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ４（ｒ）、Ｋ５（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵Ｋ６（ｒ＋１）、Ｋ７（ｒ＋１）とする。
【００５８】
そして、変換部１２３は、以上のようにして算出したＫ０（ｒ＋１）、Ｋ１（ｒ＋１）、Ｋ２（ｒ＋１）、Ｋ３（ｒ＋１）、Ｋ４（ｒ＋１）、Ｋ５（ｒ＋１）、Ｋ６（ｒ＋１）、Ｋ７（ｒ＋１）を連結して第ｒ＋１ラウンドのラウンド鍵として、第ｒラウンドのラウンド鍵と入れ替えて鍵ステート記憶領域１１２に記憶する。
【００５９】
また、本実施形態における変換部１２３は、第一の平文の変換を行う。
【００６０】
第一の平文の変換は、例えば、図３（平文ステート変換関数ｆＲの概略図）に示す平文ステート変換関数ｆＲにより行う。
【００６１】
図示するように平文ステート変換ｆＲは、第ｒラウンドの第一の平文を８分割したワードＸ０（ｒ）、Ｘ１（ｒ）、Ｘ２（ｒ）、Ｘ３（ｒ）、Ｘ４（ｒ）、Ｘ５（ｒ）、Ｘ６（ｒ）、Ｘ７（ｒ）を、それぞれ、Ｘ０（ｒ＋１）、Ｘ１（ｒ＋１）、Ｘ２（ｒ＋１）、Ｘ３（ｒ＋１）、Ｘ４（ｒ＋１）、Ｘ５（ｒ＋１）、Ｘ６（ｒ＋１）、Ｘ７（ｒ＋１）に変換し、変換したこれらのワードの値を連結することで、第ｒ＋１ラウンドの第一の平文を生成する関数である。
【００６２】
具体的には、平文ステート変換ｆＲは、まず、変換部１２３が、平文ステート変換関数ｆＲを用いて、第一の平文ステート記憶領域１１３に記憶されている第ｒラウンドの第一の平文を、ワードＸ０（ｒ）、Ｘ１（ｒ）、Ｘ２（ｒ）、Ｘ３（ｒ）、Ｘ４（ｒ）、Ｘ５（ｒ）、Ｘ６（ｒ）、Ｘ７（ｒ）に８分割する。
【００６３】
次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ０（ｒ）、Ｘ１（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ２（ｒ＋１）、Ｘ３（ｒ＋１）とする。
【００６４】
次に、変換部１２３は、鍵ステート記憶領域１１２に記憶されているラウンド鍵Ｋ（ｒ）及び第ｒラウンドの第一の平文のワードＸ４（ｒ）の排他的論理和と、第ｒラウンドの第一の平文のワードＸ５（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の上位ビットの値ｂＨを算出する（bH = F(X4 XOR K(r), X5)Ｈ）。
【００６５】
次に、変換部１２３は、鍵ステート記憶領域１１２に記憶されているラウンド鍵Ｋ（ｒ）及び第ｒラウンドの第一の平文のワードＸ４（ｒ）の排他的論理和と、第ｒラウンドの第一の平文のワードＸ５（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の下位ビットの値ｂLを算出する（bL = F(X4 XOR K(r), X5)L）。
【００６６】
次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ２（ｒ）、Ｘ３（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ４（ｒ＋１）、Ｘ５（ｒ＋１）とする。
【００６７】
次に、変換部１２３は、値ｂＨと、第ｒラウンドの第一の平文のワードＸ６（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドの第一の平文のワードＸ０（ｒ＋１）とする。
【００６８】
次に、変換部１２３は、値ｂＬと、第ｒラウンドの第一の平文のワードＸ７（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドの第一の平文のワードＸ１（ｒ＋１）とする。
【００６９】
次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ４（ｒ）、Ｘ５（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ６（ｒ＋１）、Ｘ７（ｒ＋１）とする。
【００７０】
そして、変換部１２３は、以上のようにして算出したワードＸ０（ｒ＋１）、Ｘ１（ｒ＋１）、Ｘ２（ｒ＋１）、Ｘ３（ｒ＋１）、Ｘ４（ｒ＋１）、Ｘ５（ｒ＋１）、Ｘ６（ｒ＋１）、Ｘ７（ｒ＋１）を連結して第ｒ＋１ラウンドの第一の平文として、第ｒラウンドの第一の平文に入れ替えて第一の平文ステート記憶領域１１３に記憶する。
【００７１】
次に、図２及び図３における非線形変換関数Ｆについて図４を用いて説明する。
【００７２】
図４は、非線形変換関数Ｆの概略図である。
【００７３】
図示するように、非線形変換関数Ｆは、非線形変換関数ＮＬと、線形変換関数Ｌと、の合成変換を行う関数である。これらの非線形変換関数ＮＬ及び線形変換関数Ｌは、２ブロック入力かつ２ブロック出力の変換であり、非線形変換関数Ｆは、これらの二つの変換関数の合成として、Ｆ＝Ｌ（ＮＬ）のように定義される。
【００７４】
まず、非線形変換関数ＮＬについて説明する。
【００７５】
ここで、非線形変換関数ＮＬへの二つの入力ブロックをａＨ、ａＬとする。
【００７６】
非線形変換関数ＮＬに入力されるそれぞれのブロックは４ビット毎に区切られ、４ビット毎に対応する値を特定した置換テーブルＳを用いて非線形変換される（aH,i+16||aH, i ||aL, i+16||aL,i ← S[aH,i+16||aH,i||aL, i+16||aL,i ], 0≦ i ＜ 16）。ここで，aH, i (aH, i)は aH (aL),の下位から数えてi番目のビットをそれぞれ表し，記号S[x]は置換表Sの参照を表す。
【００７７】
なお、例えば、置換テーブルＳは、Ｓ[２５６]＝｛４，１４，１５，１，１３，９，１０，０，１１，２，７，１２，３，６，８，５｝として定義される。
【００７８】
また、このような置換テーブルＳではなく、例えば、有限体における逆元演算とアフィン変換の合成変換を用いてもよい。
【００７９】
次に、線形変換関数Ｌについて説明する。
【００８０】
ここで、線形変換関数Ｌへの二つの入力ブロックをｄＨ、ｄＬとする。
【００８１】
線形変換関数Ｌは、巡回シフト関数と排他的論理和で構成されており、以下のように巡回シフト関数を６回適用する変換を行い、ｄＨ、ｄＬの値を更新する。ここで巡回シフト関数ＣＳＨ（ｑ、ｘ）は、ブロック幅におけるｘのｑビットでの左巡回シフトを表す。
【００８２】
まず、変換部１２３は、入力ブロックｄＨの値をｑ１ビットだけ左巡回シフトしたものに、入力ブロックｄＬの値を排他的論理和演算することで、値ｔ１を算出する（t1 = dL XOR CSH(q1, dH)）。
【００８３】
次に、変換部１２３は、値ｔ１をｑ２ビットだけ左巡回シフトしたものに、入力ブロックｄＨの値を排他的論理和演算することで、値ｕ１を算出する（u1 = dH XOR CSH(q2, t1)）。
【００８４】
次に、変換部１２３は、値ｕ１をｑ３ビットだけ左巡回シフトしたものに、値ｔ１を排他的論理和演算することで、値ｔ２を算出する（t2 = t1 XOR CSH(q3, u1)）。
【００８５】
次に、変換部１２３は、値ｔ２をｑ４ビットだけ左巡回シフトしたものに、値ｕ１を排他的論理和演算することで、値ｕ２を算出する（u2 = u1 XOR CSH(q4, t2)）。
【００８６】
次に、変換部１２３は、値ｕ２をｑ５ビットだけ左巡回シフトしたものに、値ｔ２を排他的論理和演算することで、値ｔ３を算出する（t3 = t2 XOR CSH(q5, u2)）。
【００８７】
次に、変換部１２３は、値ｔ３をｑ６ビットだけ左巡回シフトしたものに、値ｕ２を排他的論理和演算することで、値ｕ３を算出する（u3 = u2 XOR CSH (q6, t3)）。
【００８８】
このようにして算出された値ｕ３と値ｔ３とを連結することで、変換部１２３は、出力値ｂを算出する。
【００８９】
ここで、左巡回シフトするｑ１、ｑ２、ｑ３、ｑ４、ｑ５、ｑ６の値は、少なくとも一つは奇数であり、かつ、少なくとも一つは偶数であるような値の組み合わせを用いる。
【００９０】
そして、このような組み合わせの内、１３個の値ｑ１＋ｑ２、ｑ１＋ｑ４、ｑ３＋ｑ４、ｑ１＋ｑ２＋ｑ３＋ｑ４、ｑ１＋ｑ６、ｑ３＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ６、ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ５＋ｑ６、ｑ１＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、ｑ１＋ｑ２＋ｑ３＋ｑ４＋ｑ５＋ｑ６、の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにすることが望ましい。
【００９１】
本実施形態においては、（ｑ１、ｑ２、ｑ３、ｑ４、ｑ５、ｑ６）＝（１、３、４、７、８、１４）を用いているが、このような態様に限定されるわけではない。
【００９２】
なお、以上のように、ｑ１、ｑ２、ｑ３、ｑ４、ｑ５、ｑ６の値を選択することで、従来より少ない処理量で、安全性を保証することができるようになる。即ち、少ないシフト回数で安全性を確保することができる。また、合成処理において算術加算を使用していないので、計算量が少なくてすみ、軽実装が可能となる。
【００９３】
以上に記載されたラウンド定数生成部１２２及び変換部１２３での処理については、図５（ブロック暗号を説明する概略図）に示すブロック暗号を用いたものである。
【００９４】
このブロック暗号ではデータ処理を３つの処理関数に分割しており、図５の左からラウンド定数生成関数、鍵スケジューリング関数、主攪拌関数と呼ぶ。
【００９５】
図からもわかるように、いずれも入力に対して単一関数を繰り返し（本実施形態では、ＲＯＵＮＤ  ＮＵＭ回数）作用させる処理である。３つの処理関数の処理単位関数をそれぞれラウンド定数生成関数ｆＣ、ラウンド鍵生成関数ｆＫ（図２、図９の鍵ステート変換に対応）、ラウンド関数ｆＲ（図３、図１０の平文ステート変換に対応）と呼ぶ。
【００９６】
ラウンド定数生成関数はラウンド定数初期値ｃ（０）をラウンド定数生成関数ｆＣに入力することで、ラウンド定数生成関数ｆＣの処理毎に次々とラウンド定数Ｃ（ｒ）を生成する。
【００９７】
このようにして生成されたラウンド定数Ｃ（ｒ）をラウンド鍵生成関数ｆＫへの補助入力とし、ラウンド鍵の初期値をラウンド鍵生成関数ｆＫに入力することで、鍵スケジューリング関数は、ラウンド鍵生成関数ｆＫの処理毎に次々とラウンド鍵Ｋ（ｒ）を生成する。
【００９８】
そして、鍵スケジューリング関数で生成された生成されたラウンド鍵Ｋ（ｒ）をラウンド関数ｆＲへの補助入力とし、メッセージブロックをラウンド関数ｆＲに入力することで、主攪拌関数は、ラウンド関数ｆＲの処理を予め定められたラウンド繰り返し行うことで、暗号文を出力する。
【００９９】
ここで、本実施形態では、ラウンド鍵生成関数ｆＫとラウンド関数ｆＲとにおいて同じ関数を用いることで、実装規模の小さい装置においても論理安全性と実装安全性が保証されたハッシュ関数を生成することができるようになる。
【０１００】
管理部１２４は、メッセージブロックにおいて予め定められたラウンドの第一の平文の変更処理を終了することにより算出された第一の平文と、第ｎメッセージブロックの第二の平文と、の排他的論理和を算出することで、第ｎ＋１メッセージブロックの第二の平文を算出して、第ｎメッセージブロックの第二の平文と入れ替えて第二の平文ステート記憶領域１１４に記憶する。
【０１０１】
また、管理部１２４は、全てのメッセージブロックについて予め定められたラウンドの第一の平文の変更処理が終了し、第二の平文を算出して第二の平文ステート記憶領域１１４に記憶した場合には、当該第二の平文ステート記憶領域１１４に記憶した第二の平文をハッシュ値として後述する入出力部１３０を介して出力する処理を行う。
【０１０２】
全体制御部１２５は、ハッシュ値生成装置１００においてハッシュ値を生成する処理の全体を制御する。
【０１０３】
特に、本実施形態においては、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に記憶されている情報のリセットや、メッセージブロック数やラウンド数をカウントする処理、鍵ステート記憶領域１１２にラウンド鍵の初期値又は第二の平文をセットする処理を行う。
【０１０４】
入出力部１３０は、データの入出力を行う。
【０１０５】
以上に記載したハッシュ値生成装置１００は、例えば、図６（コンピュータ５００の概略図）に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体５０４から情報を読み出す読取装置５０５と、キーボードやマウスなどの入力装置５０６と、ディスプレイなどの出力装置５０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置５０８と、を備えた一般的なコンピュータ５００で実現できる。
【０１０６】
例えば、記憶部１１０は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部１２０は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入出力部１３０は、ＣＰＵ２０１が出力装置５０７及び入力装置５０６を利用することで実現可能である。
【０１０７】
この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【０１０８】
以上のように構成されるハッシュ値生成装置１００におけるハッシュ値の生成処理を図７に示すフローチャートを用いて説明する。
【０１０９】
まず、ハッシュ値生成装置１００は、入出力部１３０を介してハッシュ値を生成する元となるメッセージを取得する（Ｓ１０）。
【０１１０】
次に、メッセージブロック化部１２１は、入出力部１３０を介して取得したメッセージを予め定められたデータ長に分割することによりＮ個のメッセージブロックを生成する（Ｓ１１）。ここで、本実施形態においては、メッセージを２５６ビットのデータ長のメッセージブロックに分割するようにしている。
【０１１１】
次に、全体制御部１２５は、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に記憶されている情報のリセットを行う（Ｓ１２）。具体的には、全てのビット値を「０」にする。
【０１１２】
次に、全体制御部１２５は、メッセージブロックのカウンタであるメッセージカウンタｎの値を初期化する（Ｓ１３）。ここでは、メッセージカウンタｎの値に「１」を代入する。
【０１１３】
次に、全体制御部１２５は、メッセージカウンタｎの値がメッセージを分割した分割数Ｎに対して、ｎ＝Ｎ＋１となっているか否かを判断する（Ｓ１４）。
【０１１４】
ステップＳ１４で、ｎ＝Ｎ＋１となっている場合には、ステップＳ１５に進み、第二の平文ステート記憶領域１１４に記憶されている第二の平文をハッシュ値として入出力部１３０を介して出力して（Ｓ１５）、処理を終了する。
【０１１５】
ステップＳ１４で、ｎ＝Ｎ＋１となっていない場合には、ステップＳ１６に進む。
【０１１６】
ステップＳ１６では、全体制御部１２５は、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に所定のデータを格納（セット）し、ラウンドのカウンタであるラウンドカウンタｒに初期値を代入する。
【０１１７】
ここで、全体制御部１２５は、ｎ＝１の場合には、初期値記憶領域１１１に記憶されているラウンド鍵の初期値を鍵ステート記憶領域１１２に格納し、メッセージカウンタｎに対応するメッセージブロックＭｎを第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に格納して、ラウンドカウンタｒに「１」を代入する。
【０１１８】
一方、全体制御部１２５は、ｎ＞１の場合には、第二の平文ステート記憶領域１１４に記憶されている第二の平文を鍵ステート記憶領域１１２に格納し、メッセージカウンタｎに対応するメッセージブロックＭｎを第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に格納して、ラウンドカウンタｒに「１」を代入する。
【０１１９】
次に、全体制御部１２５は、ラウンドカウンタｒの値が、予め定められたラウンド数（ＲＯＵＮＤ  ＮＵＭ）に対して、ｒ＝（ＲＯＵＮＤ  ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ１７）。ステップＳ１７において、ｒ＝（ＲＯＵＮＤ  ＮＵＭ）＋１の関係にある場合には、ステップＳ２０に進み、ｒ＝（ＲＯＵＮＤ  ＮＵＭ）＋１の関係にない場合には、ステップＳ１８に進む。
【０１２０】
ステップＳ１８では、ラウンド定数生成部１２２及び変換部１２３において鍵ステート記憶領域１１２に記憶されているラウンド鍵及び第一の平文ステート記憶領域１１３に記憶されている第一の平文を更新する。
【０１２１】
具体的には、ラウンド定数生成部１２２においてラウンドカウンタｒに対応するカウンタにおけるラウンド定数Ｃ（ｒ）を算出する。
【０１２２】
そして、変換部１２３は、ラウンド定数生成部１２２において算出したラウンド定数Ｃ（ｒ）を補助入力として、鍵ステート記憶領域１１２に記憶されているラウンドカウンタｒ−１に対応するラウンドにおけるラウンド鍵Ｋ（ｒ−１）から、ラウンドカウンタｒに対応するラウンドにおけるラウンド鍵Ｋ（ｒ）を算出する。ここで、変換部１２３は、このようにして算出したラウンド鍵Ｋ（ｒ）を、ラウンド鍵Ｋ（ｒ−１）に代えて鍵ステート記憶領域１１２に記憶する。
【０１２３】
そして、変換部１２３は、ラウンド定数生成部１２２において算出したラウンド鍵Ｋ（ｒ）を補助入力として、第一の平文ステート記憶領域１１３に記憶されているラウンドカウンタｒ−１に対応するラウンドにおける第一の平文Ｘ（ｒ−１）からラウンドカウンタｒに対応するラウンドにおける第一の平文Ｘ（ｒ）を算出する。ここで、変換部１２３は、このようにして算出した第一の平文Ｘ（ｒ）を、第一の平文Ｘ（ｒ−１）に代えて第一の平文ステート記憶領域１１３に記憶する。
【０１２４】
次に、全体制御部１２５は、ラウンドカウンタｒの値に「１」をインクリメントして、ステップＳ１７に戻って処理を繰り返す。
【０１２５】
また、ステップＳ２０では、管理部１２４は、第二の平文ステート記憶領域１１４に記憶されている第二の平文と、第一の平文ステート記憶領域１１３に記憶されている第一の平文と、の排他的論理和を算出することにより次の第二の平文を算出し、第二の平文ステート記憶領域１１４に既に記憶されている第二の平文に代えて、算出した次の第二の平文を記憶する。
【０１２６】
そして、全体制御部１２５は、メッセージカウンタｎの値に「１」をインクリメントして（Ｓ２１）、ステップＳ１４に戻って処理を繰り返す。
【０１２７】
以上のように、本実施形態においては、２５６ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができるとともに、変換部でラウンド鍵と第一の平文を変換する関数として同じ関数を用いているため、実装規模を小さくすることが可能となる。
【０１２８】
図８は、本発明の第二の実施形態であるハッシュ値生成装置２００の概略図である。
【０１２９】
第一の実施形態においては、ハッシュ値生成装置１００で生成するハッシュ値は２５６ビットであったが、本実施形態においては、１６０ビットのハッシュ値を生成するようにしている。
【０１３０】
図示するように、ハッシュ値生成装置２００は、記憶部２１０と、制御部２２０と、入出力部１３０と、を備える。
【０１３１】
記憶部２１０は、初期値記憶領域２１１と、鍵ステート記憶領域２１２と、第一の平文ステート記憶領域２１３と、第二の平文ステート記憶領域２１４と、を備える。
【０１３２】
初期値記憶領域２１１には、第一の実施形態と同様に、ハッシュ値を生成する際の初期値として、ラウンド定数の初期値と、ラウンド鍵の初期値と、が記憶される。
【０１３３】
ここで、ラウンド定数の初期値は、例えば、ｃ（０）＝0xcae1ac3f55054a96といった定数が記憶される。
【０１３４】
また、ラウンド鍵の初期値は、例えば、Ｋ０（０）＝0xbc18bf6d、Ｋ１（０）＝0x369c955b、Ｋ２（０）＝0xbb271cbc、Ｋ３（０）＝0xdd66c368、Ｋ４（０）＝0x356dba5bといった定数が記憶される。
【０１３５】
なお、ラウンド定数及びラウンド鍵の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【０１３６】
鍵ステート記憶領域２１２には、第一の実施形態と同様に、各メッセージブロックにおける各ラウンドでのラウンド鍵を特定する情報が格納されるが、本実施形態においては、第一の実施形態と異なり、１６０ビットのラウンド鍵が鍵ステート記憶領域２１２に記憶される。
【０１３７】
第一の平文ステート記憶領域２１３には、第一の実施形態と同様に、ラウンド毎に算出される第一の平文を特定する情報が格納されるが、本実施形態においては、１６０ビットの第一の平文が記憶される。
【０１３８】
第二の平文ステート記憶領域１１４には、第一の実施形態と同様に、メッセージブロック毎に算出される第二の平文を特定する情報が格納されるが、本実施形態においては、１６０ビットの第二の平文が記憶される。
【０１３９】
制御部２２０は、メッセージブロック化部２２１と、ラウンド定数生成部２２２と、変換部２２３と、管理部２２４と、全体制御部２２５と、を備える。
【０１４０】
メッセージブロック化部２２１は、入出力部１３０を介して入力されたメッセージを予め定められたデータ長のブロックに分割する処理を行う。
【０１４１】
ここで、本実施形態においては、メッセージブロック化部２２１は、後述する入出力部１３０を介して入力されたメッセージを、１６０ビットのメッセージブロックに分割する。
【０１４２】
但し、メッセージ長がメッセージブロック（１６０ビット）の倍数ではない場合は、Merkle-Damgaard方式等のパディング方式を用いてメッセージブロックの倍数になるようにパディングを行う。
【０１４３】
ラウンド定数生成部２２２は、第一の実施形態と同様に、各ラウンドにおけるラウンド定数を算出する。
【０１４４】
変換部２２３は、メッセージブロック毎におけるラウンド毎に、ラウンド鍵及び第一の平文の変換を行う。ここで、変換部２２３で行う変換には、算術加算を行わない。
【０１４５】
ここで、本実施形態における変換部２２３は、まず、ラウンド鍵の変換を行う。
【０１４６】
ラウンド鍵の変換は、例えば、図９（鍵ステート変換関数ｆｋの概略図）に示す鍵ステート変換関数ｆｋにより行う。
【０１４７】
図示するように鍵ステート変換ｆｋは、第ｒラウンドのラウンド鍵を５分割したＫ０（ｒ）、Ｋ１（ｒ）、Ｋ２（ｒ）、Ｋ３（ｒ）、Ｋ４（ｒ）を、それぞれ、Ｋ０（ｒ＋１）、Ｋ１（ｒ＋１）、Ｋ２（ｒ＋１）、Ｋ３（ｒ＋１）、Ｋ４（ｒ＋１）に変換し、変換したこれらの値を連結することで、第ｒ＋１ラウンドのラウンド鍵を生成する関数である。
【０１４８】
具体的に、鍵ステート変換ｆｋでは、まず、変換部２２３が、鍵ステート記憶領域２１２に記憶されている第ｒラウンドのラウンド鍵を、Ｋ０（ｒ）、Ｋ１（ｒ）、Ｋ２（ｒ）、Ｋ３（ｒ）、Ｋ４（ｒ）に５等分する。
【０１４９】
次に、変換部２２３は、ラウンド定数生成部２２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ３（ｒ）の排他的論理和を非線形変換関数Ｆに入力した出力値ｂを算出する（b = F(k３ XOR C(r))）。
【０１５０】
次に、変換部２２３は、出力値ｂと、第ｒラウンドのラウンド鍵の内のＫ４（ｒ）と、の排他的論理和を算出して、算出した値を第ｒ＋１ラウンドのラウンド鍵の内のＫ０（ｒ＋１）とする。
【０１５１】
次に、変換部２２３は、第ｒラウンドのラウンド鍵の内のＫ３（ｒ）、Ｋ２（ｒ）、Ｋ１（ｒ）、Ｋ０（ｒ）を、それぞれ、第ｒ＋１ラウンドのラウンド鍵のＫ４（ｒ＋１）、Ｋ３（ｒ＋１）、Ｋ２（ｒ＋１）、Ｋ１（ｒ＋１）とする。
【０１５２】
そして、変換部２２３は、以上のようにして算出したＫ０（ｒ＋１）、Ｋ１（ｒ＋１）、Ｋ２（ｒ＋１）、Ｋ３（ｒ＋１）、Ｋ４（ｒ＋１）を連結して第ｒ＋１ラウンドのラウンド鍵として、第ｒラウンドのラウンド鍵と入れ替えて鍵ステート記憶領域２１２に記憶する。
【０１５３】
また、本実施形態における変換部２２３は、第一の平文の変換を行う。
【０１５４】
第一の平文の変換は、例えば、図１０（平文ステート変換関数ｆＲの概略図）に示す平文ステート変換関数ｆＲにより行う。
【０１５５】
図示するように平文ステート変換ｆＲは、第ｒラウンドの第一の平文を５分割したワードＸ０（ｒ）、Ｘ１（ｒ）、Ｘ２（ｒ）、Ｘ３（ｒ）、Ｘ４（ｒ）を、それぞれ、Ｘ０（ｒ＋１）、Ｘ１（ｒ＋１）、Ｘ２（ｒ＋１）、Ｘ３（ｒ＋１）、Ｘ４（ｒ＋１）に変換し、変換したこれらのワードの値を連結することで、第ｒ＋１ラウンドの第一の平文を生成する関数である。
【０１５６】
平文ステート変換関数ｆＲは、まず、変換部２２３が、第一の平文ステート記憶領域２１３に記憶されている第ｒラウンドの第一の平文を、ワードＸ０（ｒ）、Ｘ１（ｒ）、Ｘ２（ｒ）、Ｘ３（ｒ）、Ｘ４（ｒ）に５分割する。
【０１５７】
次に、変換部２２３は、鍵ステート記憶領域２１２に記憶されているラウンド鍵Ｋ（ｒ）と、ワードＸ３（ｒ）と、の排他的論理和を非線形変換関数Ｆに入力した出力値ｂを算出する（b = F(X３ XOR K(r))）。
【０１５８】
次に、変換部２２３は、出力値ｂと、ワードX４（ｒ）と、の排他的論理和を算出して、算出した値をワードＸ０（ｒ＋１）とする。
【０１５９】
次に、変換部２２３は、ワードＸ３（ｒ）、Ｘ２（ｒ）、Ｘ１（ｒ）、Ｘ０（ｒ）を、それぞれ、ワードＸ４（ｒ＋１）、Ｘ３（ｒ＋１）、Ｘ２（ｒ＋１）、Ｘ１（ｒ＋１）とする。
【０１６０】
そして、変換部２２３は、以上のようにして算出したＸ０（ｒ＋１）、Ｘ１（ｒ＋１）、Ｘ２（ｒ＋１）、Ｘ３（ｒ＋１）、Ｘ４（ｒ＋１）を連結して第ｒ＋１ラウンドの第一の平文として、第ｒラウンドの第一の平文と入れ替えて第一の平文ステート記憶領域２１３に記憶する。
【０１６１】
次に、図９及び図１０における非線形変換関数Ｆについて図１１を用いて説明する。
【０１６２】
図１１は、非線形変換関数Ｆの概略図である。
【０１６３】
図示するように、非線形変換関数Ｆは、非線形変換関数ＮＬと、線形変換関数Ｌと、の合成変換を行う関数である。
【０１６４】
本実施形態におけるこれらの非線形変換関数ＮＬ及び線形変換関数Ｌは、１ブロック入力かつ１ブロック出力の変換であり、非線形変換関数Ｆは、これらの二つの変換関数の合成として、Ｆ＝Ｌ（ＮＬ）のように定義される。
【０１６５】
まず、非線形変換関数ＮＬについて説明する。
【０１６６】
ここで、非線形変換関数ＮＬへの入力ブロックをａとする。
【０１６７】
非線形変換関数ＮＬに入力されるブロックは４ビット毎に区切られ、４ビット毎に対応する値を特定した置換テーブルＳを用いて非線形変換される（di+24||di+16||di+8||di ← S[ai+24||ai+16||ai+8||ai], 0≦ i ＜ 8）。ここで，aiはaの下位から数えてi番目のビットをそれぞれ表し，記号S[x]は置換表Sの参照を表す。
【０１６８】
なお、例えば、置換テーブルＳは、Ｓ[２５６]＝｛４，１４，１５，１，１３，９，１０，０，１１，２，７，１２，３，６，８，５｝として定義される。
【０１６９】
また、このような置換テーブルＳではなく、例えば、有限体における逆元演算とアフィン変換の合成変換を用いてもよい。
【０１７０】
次に、線形変換関数Ｌについて説明する。
【０１７１】
ここで、線形変換関数Ｌでは、入力ブロックｄを、上位ビットのブロックｄＨ、下位ビットのブロックｄＬに分割して、下記のように処理する。
【０１７２】
線形変換関数Ｌは、巡回シフト関数と排他的論理和で構成されており、以下のような変換を行い、ｄＨ、ｄＬの値を更新する。ここで巡回シフト関数ＣＳＨ（ｑ、ｘ）はブロック幅におけるｘのｑビットでの左巡回シフトを表す。
【０１７３】
まず、変換部２２３は、入力ブロックｄＨの値をｑ１ビットだけ左巡回シフトしたものに、入力ブロックｄＬの値を排他的論理和演算することで、値ｔ１を算出する（t1 = dL XOR CSH(q1, dH)）。
【０１７４】
次に、変換部２２３は、値ｔ１をｑ２ビットだけ左巡回シフトしたものに、入力ブロックｄＨの値を排他的論理和演算することで、値ｕ１を算出する（u1 = dH XOR CSH(q2, t1)）。
【０１７５】
次に、変換部２２３は、値ｕ１をｑ３ビットだけ左巡回シフトしたものに、値ｔ１を排他的論理和演算することで、値ｔ２を算出する（t2 = t1 XOR CSH(q3, u1)）。
【０１７６】
次に、変換部１２３は、値ｔ２をｑ４ビットだけ左巡回シフトしたものに、値ｕ１を排他的論理和演算することで、値ｕ２を算出する（u2 = u1 XOR CSH(q4, t2)）。
【０１７７】
このようにして算出された値ｕ２と値ｔ２とを連結することで、変換部２２３は、出力値ｂ（=u2||t2）を算出する。
【０１７８】
ここで、左巡回シフトするｑ１、ｑ２、ｑ３、ｑ４の値は、少なくとも一つは奇数であり、かつ、少なくとも一つは偶数であるような値の組み合わせを用いる。
【０１７９】
本実施形態においては、（ｑ１、ｑ２、ｑ３、ｑ４）＝（１、３、４、７）を用いているが、このような態様に限定されるわけではない。
【０１８０】
以上に記載されたラウンド定数生成部２２２及び変換部２２３での処理については、第一の実施形態と同様に、図５に示すブロック暗号を用いたものである。
【０１８１】
ここで、本実施形態では、ラウンド鍵生成関数ｆＫとラウンド関数ｆＲとにおいて同じ関数を用いることで、実装規模の小さい装置においても論理安全性と実装安全性が保証されたハッシュ関数を生成することができるようになる。
【０１８２】
管理部２２４は、予め定められた全てのラウンドにおける第一の平文の変更処理を終了することにより算出された第一の平文と、第ｎメッセージブロックの第二の平文と、の排他的論理和を算出することで、第ｎ＋１メッセージブロックの第二の平文を算出して、第ｎメッセージブロックの第二の平文と入れ替えて第二の平文ステート記憶領域２１４に記憶する。
【０１８３】
また、管理部２２４は、全てのメッセージブロックについて予め定められた全てのラウンドの第一の平文の変更処理が終了し、第二の平文を算出して第二の平文ステート記憶領域２１４に記憶した場合には、当該第二の平文ステート記憶領域２１４に記憶した第二の平文をハッシュ値として後述する入出力部１３０を介して出力する処理を行う。
【０１８４】
全体制御部２２５は、ハッシュ値生成装置２００においてハッシュ値を生成する処理の全体を制御する。
【０１８５】
特に、本実施形態においては、鍵ステート記憶領域２１２、第一の平文ステート記憶領域２１３及び第二の平文ステート記憶領域２１４に記憶されている情報のリセットや、メッセージブロック数やラウンド数をカウントする処理を行う。
【０１８６】
入出力部１３０は、データの入出力を行う。
【０１８７】
以上に記載したハッシュ値生成装置１００は、例えば、図６に示すようなコンピュータ５００で実現可能である。
【０１８８】
以上のように構成されるハッシュ値生成装置２００におけるハッシュ値の生成処理については、図７に示すフローチャートと同様であるため説明を省略する。
【０１８９】
以上のように、本実施形態においては、１６０ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができるとともに、変換部でラウンド鍵と第一の平文を変換する関数として同じ関数を用いているため、実装規模を小さくすることが可能となる。
【０１９０】
図１２は、本発明の第三の実施形態であるメッセージ識別子生成装置３００の概略図である。
【０１９１】
高速かつ軽量な暗号技術は、ユビキタス社会において、サーバでは高速な処理が要求されるが、クライアントでは実装資源が限られているようなアプリケーションへの応用が期待される。以下では、第一の実施形態を利用したデータの認証および配信システムについて説明する。本実施形態においては、認証技術として、ハッシュ関数に基づいたＭＡＣ生成方法であるＨＭＡＣ構成法を用いる。
【０１９２】
図示するように、メッセージ識別子生成装置３００は、記憶部１１０と、制御部３２０と、入出力部１３０と、通信部３４０と、を備え、記憶部１１０及び入出力部１３０については第一の実施形態と同様であるため、説明を省略する。
【０１９３】
本実施形態における制御部３２０は、メッセージブロック化部１２１と、ラウンド定数生成部１２２と、変換部１２３と、管理部１２４と、全体制御部１２５と、メッセージ識別子生成部３２６と、を備え、第一の実施形態と比較してメッセージ識別子生成部３２６が追加されているため、以下、この点に関連する事項について説明する。
【０１９４】
メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５で生成するハッシュ値を用いて、メッセージ識別子を生成する。
【０１９５】
具体的には、メッセージ識別子生成部３２６は、図１３（メッセージ識別子を生成する手順を示す概略図）に示されているように、入出力部１３０を介して入力されたデータMと、予め定められた鍵情報K１を連結して、メッセージK1||Mを生成する。
【０１９６】
次に、メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５を用いて、メッセージK1||Mのハッシュ値である第一のハッシュ値h(K1||M)を生成する。
【０１９７】
次に、メッセージ識別子生成部３２６は、第一のハッシュ値h(K1||M)と、鍵情報K2と、を連結し、メッセージK2|| (K1||M)を生成する。
【０１９８】
そして、メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５を用いて、メッセージK2|| (K1||M)のハッシュ値である第二のハッシュ値h(K2||h(K1||M))を生成する。
【０１９９】
そして、メッセージ識別子生成部３２６は、この第二のハッシュ値をデータMのメッセージ認証子として、入出力部１３０又は通信部３４０を介して、出力する。
【０２００】
メッセージ識別子生成装置３００は、例えば、図６に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体５０４から情報を読み出す読取装置５０５と、キーボードやマウスなどの入力装置５０６と、ディスプレイなどの出力装置５０７と、通信ネットワークに接続するためのＮＩＣ等の通信装置５０８と、を備えた一般的なコンピュータ５００で実現できる。
【０２０１】
例えば、記憶部１１０は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部３２０は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入出力部１３０は、ＣＰＵ２０１が出力装置５０７及び入力装置５０６を利用することで実現可能であり、通信部３４０は、ＣＰＵ２０１が通信装置５０８を利用することで実現可能である。
【０２０２】
この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【０２０３】
以上のように構成されるメッセージ識別子生成装置３００は、例えば、図１４（配信システム４００の概略図）に示すように、第一のメッセージ識別子生成装置３００Ａと、第二のメッセージ識別子生成装置Ｂと、をネットワーク１６０を介して接続することにより利用することが可能である。
【０２０４】
このような配信システムでは、以下のようにしてデータの送受信を行う。
【０２０５】
なお、第一のメッセージ識別子生成装置３００Ａ及び第二のメッセージ識別子生成装置Ｂは、事前に鍵情報K1とK2を秘密状態で共有しているものとする。
【０２０６】
まず、第一のメッセー識別子生成装置３００Ａは、データMを上述のようにして鍵情報K1とK2を用いてメッセージ認証子生成部３２６において２５６ビットの第一のメッセージ認証子Vを生成する。
【０２０７】
そして、第一のメッセージ識別子生成装置３００Ａは、通信部３４０を介して、第一のメッセージ識別子VとデータMとを連結した結果L=M||Vをネットワーク１６０を通じて第二のメッセージ識別子生成装置３００Ｂに送信する。
【０２０８】
第二のメッセージ識別子生成装置３００Ｂは、通信部３４０を介して、受信したデータL'=M'||V'から、２５６ビットの第二のメッセージ識別子V'を切り出すことで、第二のデータM'を取得する。
【０２０９】
そして、第二のメッセージ識別子生成装置３００Ｂは、第二のデータM'、鍵情報K1及びK2から、上述のように、メッセージ認証子生成部３２６において第三のメッセージ識別子V''を生成する。
【０２１０】
そして、第二のメッセージ識別子生成装置３００Ｂの全体制御部１２５は、第三のメッセージ識別子V''が、第二のメッセージ識別子V'と等しくない場合には、第二のデータM'に改ざんがあったもの判断する。
【０２１１】
一方、これらのメッセージ識別子が等しい場合には、第二のメッセージ識別子生成装置３００Ｂは、受信した第二のデータM'を認証済みのデータとみなす。
【０２１２】
以上のように、本実施形態におけるメッセージ識別子生成装置３００は、送受信するデータを認証するシステムに利用することが可能となる。
【０２１３】
また、第三の実施形態においては、第一の実施形態で説明したハッシュ値によりメッセージ識別子を生成したが、このような態様に限定されず、第二の実施形態で説明したハッシュ値によりメッセージ識別子を生成することも可能である。
【０２１４】
また、以上に記載した実施形態においては、鍵ステート変換ｆＫと、平文ステート変換ｆＲと、を同じ関数で構成したが、実装規模の大きな装置においては、これらの関数を別々の関数にすることも可能である。このような場合には、本実施形態に記載した鍵ステート変換ｆＫ又は平文ステート変換ｆＲの少なくともいずれか一方に、任意のシフト変換や任意の線形又は非線型関数を追加することにより、より安全性の高いハッシュ値を生成することができる。
【０２１５】
さらに、以上に記載した実施形態においては、ハッシュ値生成装置１００、２００を図６で示すようなコンピュータで実現可能としたが、このような態様に限定されず、例えば、ＣＰＵと、発揮性又は不発揮性メモリと、通信装置と、を備える携帯電話端末、非接触型ＩＣカード、商品タグ等の実装規模の小さなデバイスにおいても実現可能である。
【０２１６】
即ち、記憶部１１０、２１０は、メモリにより実現可能で、制御部１２０、２２０は、ＣＰＵにより実現可能で、入出力部１３０は、通信装置を介して外部のデバイスからデータの入出力を受ければよい。
【０２１７】
また、上述したハッシュ値生成装置１００、２００は、コンピュータがプログラムを実行することにより実現されるものでなくてもよい。例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。
【図面の簡単な説明】
【０２１８】
【図１】第一の実施形態であるハッシュ値生成装置の概略図。
【図２】鍵ステート変換関数ｆｋの概略図。
【図３】平文ステート変換関数ｆＲの概略図。
【図４】非線形変換関数Ｆの概略図。
【図５】ブロック暗号を説明する概略図。
【図６】コンピュータの概略図。
【図７】ハッシュ値生成装置におけるハッシュ値の生成処理を示すフローチャート。
【図８】第二の実施形態であるハッシュ値生成装置の概略図。
【図９】鍵ステート変換関数ｆｋの概略図。
【図１０】平文ステート変換関数ｆＲの概略図。
【図１１】非線形変換関数Ｆの概略図。
【図１２】第三の実施形態であるメッセージ識別子生成装置の概略図。
【図１３】メッセージ識別子を生成する手順を示す概略図。
【図１４】配信システムの概略図。
【符号の説明】
【０２１９】
１００、２００  ハッシュ値生成装置
３００  メッセージ識別子生成装置
１１０、２１０  記憶部
１１１、２１１  初期値記憶領域
１１２、２１２  鍵ステート記憶領域
１１３、２１３  第一の平文ステート記憶領域
１１４、２１４  第二の平文ステート記憶領域
１２０、２２０  制御部
１２１、２２１  メッセージブロック化部
１２２、２２２  ラウンド定数生成部
１２３、２２３  変換部
１２４、２２４  管理部
１２５、２２５  全体制御部
３２６  メッセージ識別子生成部
１３０  入出力部
３４０  通信部
【図１】
2007316614.tif 000003
【図２】
2007316614.tif 000004
【図３】
2007316614.tif 000005
【図４】
2007316614.tif 000006
【図５】
2007316614.tif 000007
【図６】
2007316614.tif 000008
【図７】
2007316614.tif 000009
【図８】
2007316614.tif 000010
【図９】
2007316614.tif 000011
【図１０】
2007316614.tif 000012
【図１１】
2007316614.tif 000013
【図１２】
2007316614.tif 000014
【図１３】
2007316614.tif 000015
【図１４】
2007316614.tif 000016