ハッシュ値生成装置、ハッシュ値生成方法およびプログラム
【課題】入力メッセージを複数のメッセージブロックに分割するとともに、前のラウンドのハッシュ値をフィードバックする際とメッセージブロックをフィードフォワードする場合に、フィードバックとフィードフォワードを動的に変化させる。
【解決手段】メッセージ分割手段は、入力メッセージを複数のメッセージブロックに分割し、入力手段は、その分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する。そして、暗号化手段は、その入力したメッセージを暗号化して、ハッシュ値を生成し、出力手段は、そのハッシュ値を出力する。
【解決手段】メッセージ分割手段は、入力メッセージを複数のメッセージブロックに分割し、入力手段は、その分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する。そして、暗号化手段は、その入力したメッセージを暗号化して、ハッシュ値を生成し、出力手段は、そのハッシュ値を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値生成装置、ハッシュ値生成方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、ＩＣカードやＲＦＩＤタグ等でも利用可能な安全な暗号学的ハッシュ関数が重要となっている。現在、最もよく使われているハッシュ関数としてＭＤ５(例えば、非特許文献１参照。)やＳＨＡ−１(例えば、非特許文献２参照。)がある。
【０００３】
しかし、ＭＤ５は安全性に問題があることが指摘されている。また、ＳＨＡ−１はＭＤ５に比べて安全であるものの、演算量が大きく、ＲＦＩＤタグやＩＣカード等の処理能力の低い機器では処理に時間がかかるという問題がある。
【０００４】
一方で、近年、ＣＰＵのマルチコアが一般的になってきている。ところが、現在、複数コアを同時に利用することで高速化を可能とするようなハッシュ関数はほとんど提案されていない。
【０００５】
ところで、ＲＦＩＤタグ等でも高速に処理が可能な手法として特許文献１に示されるようにストリーム暗号を基にしたハッシュ関数が知られている。さらに、特許文献１の方法では、メッセージをＭＮビット、ハッシュ値をＭＮビットとした時、Ｎビットのハッシュ値を生成するハッシュ関数をＭ個並列に接続することで処理回数を約１／Ｍに削減した手法が提案されている。この手法では前ブロックのハッシュ値をフィードバックする手法と前ブロックのハッシュ値をフィードフォワードする手法が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−２９３１４７号公報
【非特許文献】
【０００７】
【非特許文献１】Ｒ．Ｒｉｖｅｓｔ，“Ｔｈｅ ＭＤ５ Ｍｅｓｓａｇｅ Ｄｉｇｅｓｔ Ａｌｇｏｒｉｔｈｍ，” ＲＦＣ１３２１， １９９２．
【非特許文献２】ＮＩＳＴ，“Ｓｅｃｕｒｅ Ｈａｓｈ Ｓｔａｎｄａｒｄ，” ＦＩＰＳ１８０−１，１９９５．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に示される手法では、フィードフォワードとフィードバックする先が予め固定されており、ハッシュ値の計算途中で変更することはできない。つまり、フィードフォワードとフィードバックする先を能動的に変化させる場合に比べて、攪拌効率が低くなるという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、入力メッセージを複数のメッセージブロックに分割するとともに、前のラウンドのハッシュ値をフィードバックする際とメッセージブロックをフィードフォワードする場合に、フィードバックとフィードフォワードを動的に変化させるハッシュ値生成装置、ハッシュ値生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１１】
（１）本発明は、入力メッセージを複数のメッセージブロックに分割するメッセージ分割手段（例えば、図１のメッセージ分割部２に相当）と、該分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する入力手段（例えば、図１のメッセージ入力部３ａ、３ｂに相当）と、該入力したメッセージを暗号化して、ハッシュ値を生成する暗号化手段（例えば、図１の暗号化部６ａ、６ｂに相当）と、該ハッシュ値を出力する出力手段と、を備えることを特徴とするハッシュ値生成装を提案している。
【００１２】
この発明によれば、メッセージ分割手段は、入力メッセージを複数のメッセージブロックに分割する。入力手段は、その分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する。暗号化手段は、その入力したメッセージを暗号化して、ハッシュ値を生成する。そして、出力手段は、そのハッシュ値を出力する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。
【００１３】
（２）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段の出力に演算手段を有し、前記入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成され、前記暗号化手段が出力する前記ハッシュ値を入力し、該ハッシュ値を前記入力手段に戻すフィードバック手段（例えば、図１のフィードバック部５に相当）と、前記入力手段からの出力されるメッセージを入力し、該メッセージを前記演算手段に出力するフィードフォワード手段（例えば、図１のフィードフォワード部４に相当）と、を備えたことを特徴とするハッシュ値生成装置を提案している。
【００１４】
この発明によれば、暗号化手段の出力に演算手段を有し、入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成されている。また、フィードバック手段は、暗号化手段が出力するハッシュ値を入力し、そのハッシュ値を入力手段に戻し、フィードフォワード手段は、入力手段からの出力されるメッセージを入力し、そのメッセージを演算手段に出力する。したがって、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。
【００１５】
（３）本発明は、（１）または（２）のハッシュ値生成装置について、入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う前処理手段（例えば、図１の前処理部１に相当）を前記メッセージ分割手段の入力側に備えたことを特徴とするハッシュ値生成装置を提案している。
【００１６】
この発明によれば、前処理手段は、入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う。したがって、適正なビット長を持ったメッセージを分割して処理することができる。
【００１７】
（４）本発明は、（２）のハッシュ値生成装置について、前記フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定するとともに、前記フィードフォワード手段は、入力したメッセージをどの演算手段（例えば、図１の演算部７ａ、７ｂに相当）に出力するのかを能動的に決定することを特徴とするハッシュ値生成装置を提案している。
【００１８】
この発明によれば、フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定する。また、フィードフォワード手段は、入力したメッセージをどの演算手段に出力するのかを能動的に決定する。したがって、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、さらに、攪拌効率を向上させることができる。
【００１９】
（５）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段が、ストリーム暗号によりハッシュ値を生成することを特徴とするハッシュ値生成装置を提案している。
【００２０】
この発明によれば、暗号化手段は、ストリーム暗号によりハッシュ値を生成する。したがって、暗号化手段としてストリーム暗号を用いたことから、従来に比べて、処理速度の向上を図ることができる。なお、ここで、ストリーム暗号は、特定のストリーム暗号である必要はない。
【００２１】
（６）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段が、ブロック暗号によりハッシュ値を生成することを特徴とするハッシュ値生成装置を提案している。
【００２２】
この発明によれば、暗号化手段が、ブロック暗号によりハッシュ値を生成する。したがって、暗号化手段としてブロック暗号を用いたことから、ストリーム暗号に比べて、鍵のサイズを減らすことができる。なお、ここで、ブロック暗号は、特定のブロック暗号である必要はない。
【００２３】
（７）本発明は、（２）のハッシュ値生成装置について、前記演算手段が排他的論理和演算器であることを特徴とするハッシュ値生成装置を提案している。
【００２４】
この発明によれば、演算手段が排他的論理和演算器である。したがって、簡易な演算でラウンドごとのハッシュ値を結合させることができる。
【００２５】
（８）本発明は、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップ（例えば、図３のステップＳ１０１に相当）と、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップ（例えば、図３のステップＳ１０２に相当）と、メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップ（例えば、図３のステップＳ１０５に相当）と、フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップ（例えば、図３のステップＳ１０６に相当）と、入力メッセージがまだあるか否かを確認する第７のステップと（例えば、図３のステップＳ１０７に相当）、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップ（例えば、図３のステップＳ１０８に相当）と、該得られた複数のハッシュ値を演算手段によって結合する第１０のステップ（例えば、図３のステップＳ１０９に相当）と、を備えたことを特徴とするハッシュ値生成方法を提案している。
【００２６】
この発明によれば、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行い、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する。メッセージ入力手段は、分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力し、暗号化手段は、その入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する。フィードバック手段は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力し、フィードフォワード手段は、入力メッセージのフィードフォワード先の演算手段を決定して、出力する。次に、入力メッセージがまだあるか否かを確認し、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記の処理を繰り返す。そして、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力し、その得られた複数のハッシュ値を演算手段によって結合する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、さらに、攪拌効率を向上させることができる。
【００２７】
（９）本発明は、コンピュータに、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップ（例えば、図３のステップＳ１０１に相当）と、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップ（例えば、図３のステップＳ１０２に相当）と、メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップ（例えば、図３のステップＳ１０５に相当）と、フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップ（例えば、図３のステップＳ１０６に相当）と、入力メッセージがまだあるか否かを確認する第７のステップと（例えば、図３のステップＳ１０７に相当）、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップ（例えば、図３のステップＳ１０８に相当）と、該得られた複数のハッシュ値を演算手段によって結合する第１０のステップ（例えば、図３のステップＳ１０９に相当）と、を実行させるためのプログラムを提案している。
【００２８】
この発明によれば、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行い、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する。メッセージ入力手段は、分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力し、暗号化手段は、その入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する。フィードバック手段は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力し、フィードフォワード手段は、入力メッセージのフィードフォワード先の演算手段を決定して、出力する。次に、入力メッセージがまだあるか否かを確認し、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記の処理を繰り返す。そして、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力し、その得られた複数のハッシュ値を演算手段によって結合する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができる。
【発明の効果】
【００２９】
本発明によれば、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となるという効果がある。
【００３０】
また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となるという効果がある。
【００３１】
さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができるという効果がある。
【図面の簡単な説明】
【００３２】
【図１】第１の実施形態に係る構成図である。
【図２】第１の実施形態に係る暗号化部の構成を示す図である。
【図３】第１の実施形態に係る処理フローである。
【図４】第２の実施形態に係る暗号化部の構成を示す図である。
【図５】第２の実施形態に係る暗号化部の構成を示す図である。
【図６】応用例に係る構成図である。
【図７】従来例に係る構成図である。
【発明を実施するための形態】
【００３３】
以下、図面を用いて、本発明の実施形態について詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組み合わせを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３４】
＜第１の実施形態＞
図１から図３を用いて、本発明に係る第１の実施形態について説明する。
【００３５】
＜ハッシュ値生成装置の構成＞
図１に示すように、本実施形態に係るハッシュ値生成装置は、前処理部１と、メッセージ分割部２と、メッセージ入力部３ａ、３ｂと、フィードフォワード部４と、フィードバック部５と、暗号化部６ａ、６ｂと、演算部７ａ、７ｂとから構成されている。つまり、図１に示すように、メッセージ入力部、暗号化部、演算部の構成が２段の並列接続となっている。
【００３６】
ここで、前処理部１は、入力メッセージが並列段数と暗号化部６ａ、６ｂの出力ビット長の整数倍になるように、パディング処理を行う。メッセージ分割部２は、入力メッセージを複数のメッセージブロックに分割する。
【００３７】
メッセージ入力部３ａ、３ｂは、メッセージ分割部２において分割されたメッセージを入力して、暗号化部６ａ、６ｂに出力する。暗号化部６ａ、６ｂは、入力したメッセージを暗号化して、ハッシュ値を生成する。なお、暗号化部６ａ、６ｂの構成の詳細については、後述する。演算部７ａ、７ｂは、暗号化部６ａ、６ｂから出力される複数のハッシュ値を結合する。なお、演算部７ａ、７ｂは、排他的論理和演算器で構成することが好ましいがこれに限るものではない。なお、排他的論理和演算器で構成した場合には、簡易な演算でラウンドごとのハッシュ値を結合させることができる。
【００３８】
フィードフォワード部４は、メッセージ入力部３ａ、３ｂからの出力されるメッセージを入力し、そのメッセージを演算部７ａ、７ｂにフィードフォワードする。フィードバック部５は、暗号化部６ａ、６ｂが出力するハッシュ値を入力し、そのハッシュ値をメッセージ入力部３ａ、３ｂにフィードバックする。なお、フィードフォワード部４およびフィードバック部５が、データをフィードフォワードあるいはフィードバックする箇所は、一定である必要はなく、フィードフォワード部４およびフィードバック部５が、ハッシュ値やメッセージのあるビットの値等により動的に決定する。これによって、攪拌効率を向上させることができる。
【００３９】
＜暗号化部の構成＞
本実施形態に係る暗号化部は、ストリーム暗号を用いたものであり、その構成は、例えば、図２に示すようになっている。具体的には、ストリーム暗号部１０と、ＸＯＲ１１とからなり、ストリーム暗号部１０には、メッセージデータ入力端子と前ラウンドのハッシュ値をメッセージ入力部３ａ、３ｂを介して、入力するハッシュ値入力端子を備えている。
【００４０】
ストリーム暗号部１０は、Ｎビットのメッセージデータと前ラウンドのハッシュ値とを入力し、ストリーム暗号による暗号化を実施する。なお、最初のラウンドでは、前ラウンドのハッシュ値が存在しないため、任意の初期ベクトルを使用する。
【００４１】
ＸＯＲ１１は、ストリーム暗号部１０の出力データとメッセージデータ、前ラウンドのハッシュ値の排他的論理和を演算し、出力する。これにより、Ｎビットのハッシュ値が出力されることになる。
【００４２】
暗号化部の詳細な処理については、以下のようになる。なお、説明の前提として、メッセージ長をＬ、ストリーム暗号部の内部状態の長さをＴ、ハッシュ出力をＮビットとする。
【００４３】
ストリーム暗号部１０の内部状態へハッシュ値を計算したいメッセージ長ＬのメッセージをＭ＿ｉとして先頭から入力する。なお、入力されるメッセージは、前処理部１によりＮビット単位とされている。
【００４４】
次に、初回のラウンドにおいては、前ラウンドのハッシュ値が存在しないため、例えば、１００１・・・等の任意の初期ベクトルをＨ＿ｉ−１として入力する。ストリーム暗号部は、入力したＭ＿ｉとＨ＿ｉ−１に基づいて、ストリーム暗号による暗号化を実施し、その結果を出力する。
【００４５】
次に、ストリーム暗号部１０の出力と入力メッセージＭ＿ｉ、任意の初期ベクトルＨ＿ｉ−１がＸＯＲ１１に入力されると、これらの排他的論理和がとられハッシュ値Ｈ＿ｉが出力される。そして、次のメッセージＭ＿ｉと前ラウンドのハッシュ値Ｈ＿ｉ−１とが順次、ストリーム暗号部１０に入力され、ハッシュ値Ｈ＿ｉが出力される。
【００４６】
こうした処理を（Ｌ−Ｔ）／Ｎ回実行して、最終的なハッシュ値を得て、その値をメッセージのハッシュ値とする。なお、処理回数が（Ｌ−Ｔ）／Ｎ回に満たない場合には、例えば、１０１０１０・・・等の固定メッセージを入力して、空回しを行うことにより、十分な安全性を確保する。
【００４７】
＜ハッシュ値生成装置の処理＞
図３を用いて、本実施形態に係るハッシュ値生成装置の処理について、説明する。
【００４８】
まず、前処理として、入力メッセージが並列段数と暗号化部６ａ、６ｂの出力ビット長の整数倍となるようにパディングを行う（ステップＳ１０１）。メッセージ分割部２は、入力メッセージを複数のメッセージブロックに分割する（ステップＳ１０２）。
【００４９】
メッセージ入力部３ａ、３ｂは、分割されたメッセージブロックと前ラウンドのハッシュ値とをそれぞれ暗号化部６ａ、６ｂに出力する（ステップＳ１０３）。暗号化部６ａ、６ｂは、入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する（ステップＳ１０４）。
【００５０】
フィードバック部５は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力部３ａ、３ｂを決定して、出力する（ステップＳ１０５）。フィードフォワード部４は、入力メッセージのフィードフォワード先の演算部７ａ、７ｂを決定して、出力する（ステップＳ１０６）。
【００５１】
次に、入力メッセージがまだあるか否かを確認し（ステップＳ１０７）、入力メッセージがまだある場合に（ステップＳ１０７の「Ｙｅｓ」）、入力メッセージがなくなるまで、ステップＳ１０３からステップＳ１０６までを繰り返す。すべてのメッセージの処理が終了したとき（ステップＳ１０７の「Ｎｏ」）は、ハッシュ値を出力し（ステップＳ１０８）、その得られた複数のハッシュ値を演算部７ａ、７ｂによって結合する（ステップＳ１０９）。
【００５２】
したがって、本実施形態によれば、ストリーム暗号を用いたハッシュ値生成装置において、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、２段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができる。
【００５３】
＜第２の実施形態＞
図４および図５を用いて、第２の実施形態について説明する。なお、第１の実施形態においては、暗号化部において、ストリーム暗号を用いる例について、説明したが、本実施形態においては、暗号化部において、ブロック暗号を用いる例について、説明する。また、暗号化部の以外の構成要素については、第１の実施形態と同様であるため、詳細な説明は、省略する。
【００５４】
＜暗号化部の構成＞
図４および図５は、本実施形態に係る暗号化部の構成を示すブロック図である。図４は、ブロック暗号のデータランダム化部、図５は、鍵生成部の構成であって、所定長のビット列からなる入力ブロックを、あるビット長のビット列からなる所望の鍵に基づいて、ある入力ブロックと同長の出力ブロックに変換するものであって、データランダム化部２１と、鍵生成部２２とを有する。
【００５５】
データランダム化部２１は、初期転置部２３と、非線形関数部２４と、逆初期転置部２５とから構成されている。初期転置部２３は、入力ブロックを所定の区間に分割し、鍵の各区間に対応するように定める位置の各ビット列の値を、その入力ブロック内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のブロックを非線形関数部２４に渡し、その移動の前後のその区間相互間の対応を示す情報を逆初期転置部２５に渡すものである。
【００５６】
非線形関数部２４は、複数段のインボリューション処理部２６ａ〜２６ｃを有し、初期転置部２３から受け取るブロックを等しい長さの左ビット列及び右ビット列に２等分し、その左ビット列を左入力Ｌとし、その左ビット列と右ビット列との排他的論理和を右入力Ｒとして、第１段のインボリューション処理部２６ａに入力し、順次各段のインボリューション処理部２６ａ〜２６ｃの左出力を次段の右入力Ｒとし、右出力を左入力Ｌとして、最終段の左出力と、その左出力と右出力との排他的論理和とを結合したビット列のブロックを逆初期転置部２５に渡すものである。
【００５７】
各インボリューション処理部２６は、関数部２７ａ〜２７ｃを有し、鍵生成部２２が生成する中間鍵の各所定の１つと右入力Ｒとを入力として関数部２７が生成するビット列と、左入力Ｌとの排他的論理和をその左出力とし、右入力Ｒをその右出力とするものである。
【００５８】
各関数部２７は、右入力Ｒを所定の区間に分割し、その中間鍵の各区間に対応するように定める位置の各ビット列の値を、その右入力内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のビット列について所定の変換を実行するものである。
【００５９】
逆初期転置部２５は、非線形関数部２４から受け取るブロックについて、初期転置部２３から受け取るその区間相互間の対応情報に従って、初期転置部２３の行ったその区間間の移動と逆の移動を行ったブロックを、その出力ブロックとして出力するものである。
【００６０】
鍵生成部２２は、非線形関数部２４と同じ段数の鍵処理部２８ａ〜２８ｃを有し、その鍵を等しい長さの左ビット列及び右ビット列に２等分し、その左ビット列を左鍵入力ＫＬとし、その左ビット列と右ビット列との排他的論理和を右鍵入力ＫＲとして、第１段の鍵処理部２８ａに入力し、順次各段の鍵処理部２８の左鍵出力を次段の右鍵入力ＫＲとし、右鍵出力を左鍵入力ＫＬとして、各段のその左鍵出力を各中間鍵として非線形関数部２４に渡すものである。
【００６１】
各鍵処理部２８は、鍵関数部２９ａ〜２９ｃを有し、所望の初期ベクトルと右鍵入力ＫＲとを入力として鍵関数部２９ａ〜２９ｃが生成するビット列と、左鍵入力ＫＬとの排他的論理和をその左鍵出力とし、右鍵入力ＫＲをその右鍵出力とするものである。
【００６２】
各鍵関数部２９は、右鍵入力ＫＲを所定の区間に分割し、その初期ベクトルの各区間に対応するように定める位置の各ビット列の値を、右鍵入力ＫＲ内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のビット列について所定の変換を実行するものである。
【００６３】
したがって、本実施形態によれば、ブロック暗号を用いたハッシュ値生成装置においても、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。
【００６４】
＜応用例＞
図６を用いて、本発明の応用例について説明する。本応用例は、図６に示すように、メッセージ入力部、暗号化部、演算部の構成がｎ段の並列接続となっている。なお、それ以外の構成については、第１および第２の実施形態と同様であるため、詳細な説明は省略する。
【００６５】
このような構成によれば、装置の規模はやや大きくなるものの、上記実施形態の構成に比べて、より攪拌効率を高めることができる。また、ここで、ｎは、２以上の整数である。
【００６６】
なお、上述の一連の処理をプログラムとしてコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをハッシュ値生成装置に読み込ませ、実行することによって本発明のハッシュ値生成装置を実現することができる。
【００６７】
また、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００６８】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００６９】
なお、本発明は、ＵＩＭカード等に適用しても、高速なハッシュ演算を可能とすることができる。したがって、ストリーム暗号やブロック暗号を使用するようなブロードバンド事業や携帯電話をはじめとするモバイル通信におけるシステム構築に広く利用することが可能である。
【００７０】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７１】
１・・・前処理部
２・・・メッセージ分割部
３ａ・・・メッセージ入力部
３ｂ・・・メッセージ入力部
４・・・フィードフォワード部
５・・・フィードバック部
６ａ・・・暗号化部
６ｂ・・・暗号化部
７ａ・・・演算部
７ｂ・・・演算部
１０・・・ストリーム暗号部
１１・・・ＸＯＲ
２１・・・データランダム化部
２２・・・鍵生成部
２３・・・初期転置部
２４・・・非線形関数部
２５・・・逆初期転置部
２６ａ・・・インボリューション処理部
２６ｂ・・・インボリューション処理部
２６ｃ・・・インボリューション処理部
２７ａ・・・関数部
２７ｂ・・・関数部
２７ｃ・・・関数部
２８ａ・・・鍵処理部
２８ｂ・・・鍵処理部
２８ｃ・・・鍵処理部
２９ａ・・・鍵関数部
２９ｂ・・・鍵関数部
２９ｃ・・・鍵関数部
【技術分野】
【０００１】
本発明は、ハッシュ値生成装置、ハッシュ値生成方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、ＩＣカードやＲＦＩＤタグ等でも利用可能な安全な暗号学的ハッシュ関数が重要となっている。現在、最もよく使われているハッシュ関数としてＭＤ５(例えば、非特許文献１参照。)やＳＨＡ−１(例えば、非特許文献２参照。)がある。
【０００３】
しかし、ＭＤ５は安全性に問題があることが指摘されている。また、ＳＨＡ−１はＭＤ５に比べて安全であるものの、演算量が大きく、ＲＦＩＤタグやＩＣカード等の処理能力の低い機器では処理に時間がかかるという問題がある。
【０００４】
一方で、近年、ＣＰＵのマルチコアが一般的になってきている。ところが、現在、複数コアを同時に利用することで高速化を可能とするようなハッシュ関数はほとんど提案されていない。
【０００５】
ところで、ＲＦＩＤタグ等でも高速に処理が可能な手法として特許文献１に示されるようにストリーム暗号を基にしたハッシュ関数が知られている。さらに、特許文献１の方法では、メッセージをＭＮビット、ハッシュ値をＭＮビットとした時、Ｎビットのハッシュ値を生成するハッシュ関数をＭ個並列に接続することで処理回数を約１／Ｍに削減した手法が提案されている。この手法では前ブロックのハッシュ値をフィードバックする手法と前ブロックのハッシュ値をフィードフォワードする手法が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−２９３１４７号公報
【非特許文献】
【０００７】
【非特許文献１】Ｒ．Ｒｉｖｅｓｔ，“Ｔｈｅ ＭＤ５ Ｍｅｓｓａｇｅ Ｄｉｇｅｓｔ Ａｌｇｏｒｉｔｈｍ，” ＲＦＣ１３２１， １９９２．
【非特許文献２】ＮＩＳＴ，“Ｓｅｃｕｒｅ Ｈａｓｈ Ｓｔａｎｄａｒｄ，” ＦＩＰＳ１８０−１，１９９５．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に示される手法では、フィードフォワードとフィードバックする先が予め固定されており、ハッシュ値の計算途中で変更することはできない。つまり、フィードフォワードとフィードバックする先を能動的に変化させる場合に比べて、攪拌効率が低くなるという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、入力メッセージを複数のメッセージブロックに分割するとともに、前のラウンドのハッシュ値をフィードバックする際とメッセージブロックをフィードフォワードする場合に、フィードバックとフィードフォワードを動的に変化させるハッシュ値生成装置、ハッシュ値生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１１】
（１）本発明は、入力メッセージを複数のメッセージブロックに分割するメッセージ分割手段（例えば、図１のメッセージ分割部２に相当）と、該分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する入力手段（例えば、図１のメッセージ入力部３ａ、３ｂに相当）と、該入力したメッセージを暗号化して、ハッシュ値を生成する暗号化手段（例えば、図１の暗号化部６ａ、６ｂに相当）と、該ハッシュ値を出力する出力手段と、を備えることを特徴とするハッシュ値生成装を提案している。
【００１２】
この発明によれば、メッセージ分割手段は、入力メッセージを複数のメッセージブロックに分割する。入力手段は、その分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する。暗号化手段は、その入力したメッセージを暗号化して、ハッシュ値を生成する。そして、出力手段は、そのハッシュ値を出力する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。
【００１３】
（２）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段の出力に演算手段を有し、前記入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成され、前記暗号化手段が出力する前記ハッシュ値を入力し、該ハッシュ値を前記入力手段に戻すフィードバック手段（例えば、図１のフィードバック部５に相当）と、前記入力手段からの出力されるメッセージを入力し、該メッセージを前記演算手段に出力するフィードフォワード手段（例えば、図１のフィードフォワード部４に相当）と、を備えたことを特徴とするハッシュ値生成装置を提案している。
【００１４】
この発明によれば、暗号化手段の出力に演算手段を有し、入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成されている。また、フィードバック手段は、暗号化手段が出力するハッシュ値を入力し、そのハッシュ値を入力手段に戻し、フィードフォワード手段は、入力手段からの出力されるメッセージを入力し、そのメッセージを演算手段に出力する。したがって、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。
【００１５】
（３）本発明は、（１）または（２）のハッシュ値生成装置について、入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う前処理手段（例えば、図１の前処理部１に相当）を前記メッセージ分割手段の入力側に備えたことを特徴とするハッシュ値生成装置を提案している。
【００１６】
この発明によれば、前処理手段は、入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う。したがって、適正なビット長を持ったメッセージを分割して処理することができる。
【００１７】
（４）本発明は、（２）のハッシュ値生成装置について、前記フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定するとともに、前記フィードフォワード手段は、入力したメッセージをどの演算手段（例えば、図１の演算部７ａ、７ｂに相当）に出力するのかを能動的に決定することを特徴とするハッシュ値生成装置を提案している。
【００１８】
この発明によれば、フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定する。また、フィードフォワード手段は、入力したメッセージをどの演算手段に出力するのかを能動的に決定する。したがって、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、さらに、攪拌効率を向上させることができる。
【００１９】
（５）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段が、ストリーム暗号によりハッシュ値を生成することを特徴とするハッシュ値生成装置を提案している。
【００２０】
この発明によれば、暗号化手段は、ストリーム暗号によりハッシュ値を生成する。したがって、暗号化手段としてストリーム暗号を用いたことから、従来に比べて、処理速度の向上を図ることができる。なお、ここで、ストリーム暗号は、特定のストリーム暗号である必要はない。
【００２１】
（６）本発明は、（１）のハッシュ値生成装置について、前記暗号化手段が、ブロック暗号によりハッシュ値を生成することを特徴とするハッシュ値生成装置を提案している。
【００２２】
この発明によれば、暗号化手段が、ブロック暗号によりハッシュ値を生成する。したがって、暗号化手段としてブロック暗号を用いたことから、ストリーム暗号に比べて、鍵のサイズを減らすことができる。なお、ここで、ブロック暗号は、特定のブロック暗号である必要はない。
【００２３】
（７）本発明は、（２）のハッシュ値生成装置について、前記演算手段が排他的論理和演算器であることを特徴とするハッシュ値生成装置を提案している。
【００２４】
この発明によれば、演算手段が排他的論理和演算器である。したがって、簡易な演算でラウンドごとのハッシュ値を結合させることができる。
【００２５】
（８）本発明は、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップ（例えば、図３のステップＳ１０１に相当）と、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップ（例えば、図３のステップＳ１０２に相当）と、メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップ（例えば、図３のステップＳ１０５に相当）と、フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップ（例えば、図３のステップＳ１０６に相当）と、入力メッセージがまだあるか否かを確認する第７のステップと（例えば、図３のステップＳ１０７に相当）、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップ（例えば、図３のステップＳ１０８に相当）と、該得られた複数のハッシュ値を演算手段によって結合する第１０のステップ（例えば、図３のステップＳ１０９に相当）と、を備えたことを特徴とするハッシュ値生成方法を提案している。
【００２６】
この発明によれば、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行い、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する。メッセージ入力手段は、分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力し、暗号化手段は、その入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する。フィードバック手段は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力し、フィードフォワード手段は、入力メッセージのフィードフォワード先の演算手段を決定して、出力する。次に、入力メッセージがまだあるか否かを確認し、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記の処理を繰り返す。そして、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力し、その得られた複数のハッシュ値を演算手段によって結合する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、さらに、攪拌効率を向上させることができる。
【００２７】
（９）本発明は、コンピュータに、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップ（例えば、図３のステップＳ１０１に相当）と、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップ（例えば、図３のステップＳ１０２に相当）と、メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップ（例えば、図３のステップＳ１０５に相当）と、フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップ（例えば、図３のステップＳ１０６に相当）と、入力メッセージがまだあるか否かを確認する第７のステップと（例えば、図３のステップＳ１０７に相当）、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップ（例えば、図３のステップＳ１０８に相当）と、該得られた複数のハッシュ値を演算手段によって結合する第１０のステップ（例えば、図３のステップＳ１０９に相当）と、を実行させるためのプログラムを提案している。
【００２８】
この発明によれば、入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行い、メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する。メッセージ入力手段は、分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力し、暗号化手段は、その入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する。フィードバック手段は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力し、フィードフォワード手段は、入力メッセージのフィードフォワード先の演算手段を決定して、出力する。次に、入力メッセージがまだあるか否かを確認し、入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記の処理を繰り返す。そして、すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力し、その得られた複数のハッシュ値を演算手段によって結合する。したがって、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができる。
【発明の効果】
【００２９】
本発明によれば、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となるという効果がある。
【００３０】
また、ｎ段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となるという効果がある。
【００３１】
さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができるという効果がある。
【図面の簡単な説明】
【００３２】
【図１】第１の実施形態に係る構成図である。
【図２】第１の実施形態に係る暗号化部の構成を示す図である。
【図３】第１の実施形態に係る処理フローである。
【図４】第２の実施形態に係る暗号化部の構成を示す図である。
【図５】第２の実施形態に係る暗号化部の構成を示す図である。
【図６】応用例に係る構成図である。
【図７】従来例に係る構成図である。
【発明を実施するための形態】
【００３３】
以下、図面を用いて、本発明の実施形態について詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組み合わせを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３４】
＜第１の実施形態＞
図１から図３を用いて、本発明に係る第１の実施形態について説明する。
【００３５】
＜ハッシュ値生成装置の構成＞
図１に示すように、本実施形態に係るハッシュ値生成装置は、前処理部１と、メッセージ分割部２と、メッセージ入力部３ａ、３ｂと、フィードフォワード部４と、フィードバック部５と、暗号化部６ａ、６ｂと、演算部７ａ、７ｂとから構成されている。つまり、図１に示すように、メッセージ入力部、暗号化部、演算部の構成が２段の並列接続となっている。
【００３６】
ここで、前処理部１は、入力メッセージが並列段数と暗号化部６ａ、６ｂの出力ビット長の整数倍になるように、パディング処理を行う。メッセージ分割部２は、入力メッセージを複数のメッセージブロックに分割する。
【００３７】
メッセージ入力部３ａ、３ｂは、メッセージ分割部２において分割されたメッセージを入力して、暗号化部６ａ、６ｂに出力する。暗号化部６ａ、６ｂは、入力したメッセージを暗号化して、ハッシュ値を生成する。なお、暗号化部６ａ、６ｂの構成の詳細については、後述する。演算部７ａ、７ｂは、暗号化部６ａ、６ｂから出力される複数のハッシュ値を結合する。なお、演算部７ａ、７ｂは、排他的論理和演算器で構成することが好ましいがこれに限るものではない。なお、排他的論理和演算器で構成した場合には、簡易な演算でラウンドごとのハッシュ値を結合させることができる。
【００３８】
フィードフォワード部４は、メッセージ入力部３ａ、３ｂからの出力されるメッセージを入力し、そのメッセージを演算部７ａ、７ｂにフィードフォワードする。フィードバック部５は、暗号化部６ａ、６ｂが出力するハッシュ値を入力し、そのハッシュ値をメッセージ入力部３ａ、３ｂにフィードバックする。なお、フィードフォワード部４およびフィードバック部５が、データをフィードフォワードあるいはフィードバックする箇所は、一定である必要はなく、フィードフォワード部４およびフィードバック部５が、ハッシュ値やメッセージのあるビットの値等により動的に決定する。これによって、攪拌効率を向上させることができる。
【００３９】
＜暗号化部の構成＞
本実施形態に係る暗号化部は、ストリーム暗号を用いたものであり、その構成は、例えば、図２に示すようになっている。具体的には、ストリーム暗号部１０と、ＸＯＲ１１とからなり、ストリーム暗号部１０には、メッセージデータ入力端子と前ラウンドのハッシュ値をメッセージ入力部３ａ、３ｂを介して、入力するハッシュ値入力端子を備えている。
【００４０】
ストリーム暗号部１０は、Ｎビットのメッセージデータと前ラウンドのハッシュ値とを入力し、ストリーム暗号による暗号化を実施する。なお、最初のラウンドでは、前ラウンドのハッシュ値が存在しないため、任意の初期ベクトルを使用する。
【００４１】
ＸＯＲ１１は、ストリーム暗号部１０の出力データとメッセージデータ、前ラウンドのハッシュ値の排他的論理和を演算し、出力する。これにより、Ｎビットのハッシュ値が出力されることになる。
【００４２】
暗号化部の詳細な処理については、以下のようになる。なお、説明の前提として、メッセージ長をＬ、ストリーム暗号部の内部状態の長さをＴ、ハッシュ出力をＮビットとする。
【００４３】
ストリーム暗号部１０の内部状態へハッシュ値を計算したいメッセージ長ＬのメッセージをＭ＿ｉとして先頭から入力する。なお、入力されるメッセージは、前処理部１によりＮビット単位とされている。
【００４４】
次に、初回のラウンドにおいては、前ラウンドのハッシュ値が存在しないため、例えば、１００１・・・等の任意の初期ベクトルをＨ＿ｉ−１として入力する。ストリーム暗号部は、入力したＭ＿ｉとＨ＿ｉ−１に基づいて、ストリーム暗号による暗号化を実施し、その結果を出力する。
【００４５】
次に、ストリーム暗号部１０の出力と入力メッセージＭ＿ｉ、任意の初期ベクトルＨ＿ｉ−１がＸＯＲ１１に入力されると、これらの排他的論理和がとられハッシュ値Ｈ＿ｉが出力される。そして、次のメッセージＭ＿ｉと前ラウンドのハッシュ値Ｈ＿ｉ−１とが順次、ストリーム暗号部１０に入力され、ハッシュ値Ｈ＿ｉが出力される。
【００４６】
こうした処理を（Ｌ−Ｔ）／Ｎ回実行して、最終的なハッシュ値を得て、その値をメッセージのハッシュ値とする。なお、処理回数が（Ｌ−Ｔ）／Ｎ回に満たない場合には、例えば、１０１０１０・・・等の固定メッセージを入力して、空回しを行うことにより、十分な安全性を確保する。
【００４７】
＜ハッシュ値生成装置の処理＞
図３を用いて、本実施形態に係るハッシュ値生成装置の処理について、説明する。
【００４８】
まず、前処理として、入力メッセージが並列段数と暗号化部６ａ、６ｂの出力ビット長の整数倍となるようにパディングを行う（ステップＳ１０１）。メッセージ分割部２は、入力メッセージを複数のメッセージブロックに分割する（ステップＳ１０２）。
【００４９】
メッセージ入力部３ａ、３ｂは、分割されたメッセージブロックと前ラウンドのハッシュ値とをそれぞれ暗号化部６ａ、６ｂに出力する（ステップＳ１０３）。暗号化部６ａ、６ｂは、入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する（ステップＳ１０４）。
【００５０】
フィードバック部５は、その得られたハッシュ値を入力し、フィードバック先のメッセージ入力部３ａ、３ｂを決定して、出力する（ステップＳ１０５）。フィードフォワード部４は、入力メッセージのフィードフォワード先の演算部７ａ、７ｂを決定して、出力する（ステップＳ１０６）。
【００５１】
次に、入力メッセージがまだあるか否かを確認し（ステップＳ１０７）、入力メッセージがまだある場合に（ステップＳ１０７の「Ｙｅｓ」）、入力メッセージがなくなるまで、ステップＳ１０３からステップＳ１０６までを繰り返す。すべてのメッセージの処理が終了したとき（ステップＳ１０７の「Ｎｏ」）は、ハッシュ値を出力し（ステップＳ１０８）、その得られた複数のハッシュ値を演算部７ａ、７ｂによって結合する（ステップＳ１０９）。
【００５２】
したがって、本実施形態によれば、ストリーム暗号を用いたハッシュ値生成装置において、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。また、２段の並列構成により、並列して処理を行うことができるため、高速に処理が可能となる。さらに、フィードバック手段およびフィードフォワード手段が、フィードバック先およびフィードフォワード先を能動的に決定するため、フィードバック先あるいはフィードフォワード先が予め固定されている場合に比べて、より攪拌効率を向上させることができる。
【００５３】
＜第２の実施形態＞
図４および図５を用いて、第２の実施形態について説明する。なお、第１の実施形態においては、暗号化部において、ストリーム暗号を用いる例について、説明したが、本実施形態においては、暗号化部において、ブロック暗号を用いる例について、説明する。また、暗号化部の以外の構成要素については、第１の実施形態と同様であるため、詳細な説明は、省略する。
【００５４】
＜暗号化部の構成＞
図４および図５は、本実施形態に係る暗号化部の構成を示すブロック図である。図４は、ブロック暗号のデータランダム化部、図５は、鍵生成部の構成であって、所定長のビット列からなる入力ブロックを、あるビット長のビット列からなる所望の鍵に基づいて、ある入力ブロックと同長の出力ブロックに変換するものであって、データランダム化部２１と、鍵生成部２２とを有する。
【００５５】
データランダム化部２１は、初期転置部２３と、非線形関数部２４と、逆初期転置部２５とから構成されている。初期転置部２３は、入力ブロックを所定の区間に分割し、鍵の各区間に対応するように定める位置の各ビット列の値を、その入力ブロック内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のブロックを非線形関数部２４に渡し、その移動の前後のその区間相互間の対応を示す情報を逆初期転置部２５に渡すものである。
【００５６】
非線形関数部２４は、複数段のインボリューション処理部２６ａ〜２６ｃを有し、初期転置部２３から受け取るブロックを等しい長さの左ビット列及び右ビット列に２等分し、その左ビット列を左入力Ｌとし、その左ビット列と右ビット列との排他的論理和を右入力Ｒとして、第１段のインボリューション処理部２６ａに入力し、順次各段のインボリューション処理部２６ａ〜２６ｃの左出力を次段の右入力Ｒとし、右出力を左入力Ｌとして、最終段の左出力と、その左出力と右出力との排他的論理和とを結合したビット列のブロックを逆初期転置部２５に渡すものである。
【００５７】
各インボリューション処理部２６は、関数部２７ａ〜２７ｃを有し、鍵生成部２２が生成する中間鍵の各所定の１つと右入力Ｒとを入力として関数部２７が生成するビット列と、左入力Ｌとの排他的論理和をその左出力とし、右入力Ｒをその右出力とするものである。
【００５８】
各関数部２７は、右入力Ｒを所定の区間に分割し、その中間鍵の各区間に対応するように定める位置の各ビット列の値を、その右入力内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のビット列について所定の変換を実行するものである。
【００５９】
逆初期転置部２５は、非線形関数部２４から受け取るブロックについて、初期転置部２３から受け取るその区間相互間の対応情報に従って、初期転置部２３の行ったその区間間の移動と逆の移動を行ったブロックを、その出力ブロックとして出力するものである。
【００６０】
鍵生成部２２は、非線形関数部２４と同じ段数の鍵処理部２８ａ〜２８ｃを有し、その鍵を等しい長さの左ビット列及び右ビット列に２等分し、その左ビット列を左鍵入力ＫＬとし、その左ビット列と右ビット列との排他的論理和を右鍵入力ＫＲとして、第１段の鍵処理部２８ａに入力し、順次各段の鍵処理部２８の左鍵出力を次段の右鍵入力ＫＲとし、右鍵出力を左鍵入力ＫＬとして、各段のその左鍵出力を各中間鍵として非線形関数部２４に渡すものである。
【００６１】
各鍵処理部２８は、鍵関数部２９ａ〜２９ｃを有し、所望の初期ベクトルと右鍵入力ＫＲとを入力として鍵関数部２９ａ〜２９ｃが生成するビット列と、左鍵入力ＫＬとの排他的論理和をその左鍵出力とし、右鍵入力ＫＲをその右鍵出力とするものである。
【００６２】
各鍵関数部２９は、右鍵入力ＫＲを所定の区間に分割し、その初期ベクトルの各区間に対応するように定める位置の各ビット列の値を、右鍵入力ＫＲ内の区間位置アドレスとし、各区間のビット列を対応するその区間位置アドレスによって定まる区間と所定の位置関係を有する区間に順次移動して、移動した結果のビット列について所定の変換を実行するものである。
【００６３】
したがって、本実施形態によれば、ブロック暗号を用いたハッシュ値生成装置においても、入力メッセージを複数のメッセージブロックに分割することにより、使用メモリの削減が可能になりＲＦＩＤタグ等においても高速に処理が可能となる。
【００６４】
＜応用例＞
図６を用いて、本発明の応用例について説明する。本応用例は、図６に示すように、メッセージ入力部、暗号化部、演算部の構成がｎ段の並列接続となっている。なお、それ以外の構成については、第１および第２の実施形態と同様であるため、詳細な説明は省略する。
【００６５】
このような構成によれば、装置の規模はやや大きくなるものの、上記実施形態の構成に比べて、より攪拌効率を高めることができる。また、ここで、ｎは、２以上の整数である。
【００６６】
なお、上述の一連の処理をプログラムとしてコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをハッシュ値生成装置に読み込ませ、実行することによって本発明のハッシュ値生成装置を実現することができる。
【００６７】
また、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００６８】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００６９】
なお、本発明は、ＵＩＭカード等に適用しても、高速なハッシュ演算を可能とすることができる。したがって、ストリーム暗号やブロック暗号を使用するようなブロードバンド事業や携帯電話をはじめとするモバイル通信におけるシステム構築に広く利用することが可能である。
【００７０】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７１】
１・・・前処理部
２・・・メッセージ分割部
３ａ・・・メッセージ入力部
３ｂ・・・メッセージ入力部
４・・・フィードフォワード部
５・・・フィードバック部
６ａ・・・暗号化部
６ｂ・・・暗号化部
７ａ・・・演算部
７ｂ・・・演算部
１０・・・ストリーム暗号部
１１・・・ＸＯＲ
２１・・・データランダム化部
２２・・・鍵生成部
２３・・・初期転置部
２４・・・非線形関数部
２５・・・逆初期転置部
２６ａ・・・インボリューション処理部
２６ｂ・・・インボリューション処理部
２６ｃ・・・インボリューション処理部
２７ａ・・・関数部
２７ｂ・・・関数部
２７ｃ・・・関数部
２８ａ・・・鍵処理部
２８ｂ・・・鍵処理部
２８ｃ・・・鍵処理部
２９ａ・・・鍵関数部
２９ｂ・・・鍵関数部
２９ｃ・・・鍵関数部
【特許請求の範囲】
【請求項１】
入力メッセージを複数のメッセージブロックに分割するメッセージ分割手段と、
該分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する入力手段と、
該入力したメッセージを暗号化して、ハッシュ値を生成する暗号化手段と、
該ハッシュ値を出力する出力手段と、
を備えることを特徴とするハッシュ値生成装置。
【請求項２】
前記暗号化手段の出力に演算手段を有し、
前記入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成され、
前記暗号化手段が出力する前記ハッシュ値を入力し、該ハッシュ値を前記入力手段に戻すフィードバック手段と、
前記入力手段からの出力されるメッセージを入力し、該メッセージを前記演算手段に出力するフィードフォワード手段と、
を備えたことを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項３】
入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う前処理手段を前記メッセージ分割手段の入力側に備えたことを特徴とする請求項１または請求項２に記載のハッシュ値生成装置。
【請求項４】
前記フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定するとともに、前記フィードフォワード手段は、入力したメッセージをどの演算手段に出力するのかを能動的に決定することを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項５】
前記暗号化手段が、ストリーム暗号によりハッシュ値を生成することを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項６】
前記暗号化手段が、ブロック暗号によりハッシュ値を生成することを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項７】
前記演算手段が排他的論理和演算器であることを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項８】
入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップと、
メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップと、
メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップと、
該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップと、
フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップと、
フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップと、
入力メッセージがまだあるか否かを確認する第７のステップと、
入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、
すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップと、
該得られた複数のハッシュ値を演算手段によって結合する第１０のステップと、
を備えたことを特徴とするハッシュ値生成方法。
【請求項９】
コンピュータに、
入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップと、
メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップと、
メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップと、
該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップと、
フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップと、
フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップと、
入力メッセージがまだあるか否かを確認する第７のステップと、
入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、
すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップと、
該得られた複数のハッシュ値を演算手段によって結合する第１０のステップと、
を実行させるためのプログラム。
【請求項１】
入力メッセージを複数のメッセージブロックに分割するメッセージ分割手段と、
該分割された入力メッセージブロックと前ラウンドで得られたハッシュ値とを入力する入力手段と、
該入力したメッセージを暗号化して、ハッシュ値を生成する暗号化手段と、
該ハッシュ値を出力する出力手段と、
を備えることを特徴とするハッシュ値生成装置。
【請求項２】
前記暗号化手段の出力に演算手段を有し、
前記入力手段と暗号化手段と演算手段とがｎ（ｎは、２以上の整数）段並列になって構成され、
前記暗号化手段が出力する前記ハッシュ値を入力し、該ハッシュ値を前記入力手段に戻すフィードバック手段と、
前記入力手段からの出力されるメッセージを入力し、該メッセージを前記演算手段に出力するフィードフォワード手段と、
を備えたことを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項３】
入力メッセージが前記並列段数と前記暗号化手段の出力ビット長の整数倍になるように、パディング処理を行う前処理手段を前記メッセージ分割手段の入力側に備えたことを特徴とする請求項１または請求項２に記載のハッシュ値生成装置。
【請求項４】
前記フィードバック手段は、入力したハッシュ値をどの入力手段に戻すかを能動的に決定するとともに、前記フィードフォワード手段は、入力したメッセージをどの演算手段に出力するのかを能動的に決定することを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項５】
前記暗号化手段が、ストリーム暗号によりハッシュ値を生成することを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項６】
前記暗号化手段が、ブロック暗号によりハッシュ値を生成することを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項７】
前記演算手段が排他的論理和演算器であることを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項８】
入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップと、
メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップと、
メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップと、
該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップと、
フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップと、
フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップと、
入力メッセージがまだあるか否かを確認する第７のステップと、
入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、
すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップと、
該得られた複数のハッシュ値を演算手段によって結合する第１０のステップと、
を備えたことを特徴とするハッシュ値生成方法。
【請求項９】
コンピュータに、
入力メッセージが並列段数と暗号化手段の出力ビット長の整数倍となるようにパディングを行う第１のステップと、
メッセージ分割手段が入力メッセージを複数のメッセージブロックに分割する第２のステップと、
メッセージ入力手段が分割されたメッセージブロックと前ラウンドのハッシュ値をそれぞれ暗号化手段に出力する第３のステップと、
該入力されたメッセージブロックと前ブロックのハッシュ値とを暗号化して、ハッシュ値を生成する第４のステップと、
フィードバック手段が、該得られたハッシュ値を入力し、フィードバック先のメッセージ入力手段を決定して、出力する第５のステップと、
フィードフォワード手段が入力メッセージのフィードフォワード先の演算手段を決定して、出力する第６のステップと、
入力メッセージがまだあるか否かを確認する第７のステップと、
入力メッセージがまだある場合に、入力メッセージがなくなるまで、上記第３のステップから第６のステップまでを繰り返す第８のステップと、
すべてのメッセージの処理が終了したときに、出力手段からハッシュ値を出力する第９のステップと、
該得られた複数のハッシュ値を演算手段によって結合する第１０のステップと、
を実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−２５６７４９（Ｐ２０１０−２５６７４９Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０８８２８（Ｐ２００９−１０８８２８）
【出願日】平成２１年４月２８日（２００９．４．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２８日（２００９．４．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]