(57)【要約】【課題】圧縮関数実行部の改善された構成を実現する。【解決手段】メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力してデータ圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。【選択図】図１５
2010049127.tif 000002
【特許請求の範囲】
【請求項１】
メッセージデータを入力してハッシュ値を生成するデータ変換部を有し、
前記データ変換部は、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行する構成であり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う構成であり、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成であるデータ変換装置。
【請求項２】
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一のメッセージスケジュール部を複数の圧縮関数実行部で共有した共有メッセージスケジュール部を有し、
前記共有メッセージスケジュール部は、前記メッセージデータの分割データを入力してメッセージスケジュール処理により生成した出力データを複数の連鎖値処理部に出力する構成であり、
前記複数の連鎖値処理部は、前記共有メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する処理を並列に実行する構成である請求項１に記載のデータ変換装置。
【請求項３】
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一の連鎖値処理部を複数の圧縮関数実行部で共有した共有連鎖値処理部を有し、
並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データを前記共有連鎖値処理部に出力する構成であり、
前記共有連鎖値処理部は、前記複数のメッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する構成である請求項１に記載のデータ変換装置。
【請求項４】
前記並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データの排他的論理和演算結果を前記共有連鎖値処理部に出力する構成である請求項３に記載のデータ変換装置。
【請求項５】
前記メッセージスケジュール部は、置換処理を繰り返し実行し、各置換処理結果を中間値として出力する構成を持つ中間出力付き置換関数実行部によって構成され、
前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力を付加入力として、置換処理を繰り返し実行する付加入力付き置換関数実行部を有する構成である請求項１に記載のデータ変換装置。
【請求項６】
前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力と前段の置換処理結果との排他的論理和結果を次の置換処理の入力データとして設定する構成である請求項５に記載のデータ変換装置。
【請求項７】
前記置換関数実行部の実行する複数の置換処理の各々は、
入力データの少なくとも一部データに対する非線形変換処理と、データ入れ替え処理としてのスワップ処理とを含む構成である請求項５に記載のデータ変換装置。
【請求項８】
前記非線形変換処理は、コンスタント（定数）を適用した排他的論理和演算と、非線形変換処理と、線形変換行列を適用した線形変換処理を含む処理である請求項７に記載のデータ変換装置。
【請求項９】
前記置換関数実行部の実行する複数の置換処理の各々において行われる線形変換処理は、複数の異なる行列を適用するＤＳＭ（Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）に従った処理として実行する構成である請求項７に記載のデータ変換装置。
【請求項１０】
前記置換関数実行部の実行する複数の置換処理の各々は、それぞれ異なるコンスタント（定数）集合を入力したデータ処理を行う構成であり、
１つの置換処理に適用するコンスタント集合を基本集合として、該基本集合に対するデータ変換により生成した異なるコンスタント集合を各置換処理に適用する構成である請求項５に記載のデータ変換装置。
【請求項１１】
前記基本集合となるコンスタント集合は、
異なる複数の初期値Ｓ，Ｔに対して予め設定した変換ルールを適用して生成した複数のコンスタントから構成され、
前記変換ルールは、前記初期値に対して、
Ｓ←Ｓ・ｘａ、Ｔ←Ｔ・ｘｂ
ただしａ≠ｂ
とする更新処理を含む構成である請求項１０に記載のデータ変換装置。
【請求項１２】
前記基本集合に対するデータ変換処理は、
前記基本集合を構成するコンスタントの構成ビットのローテーション処理、または、予め規定したマスクデータとの演算処理である請求項１０に記載のデータ変換装置。
【請求項１３】
前記データ変換部は、
最終的に出力するハッシュ値のビット数削減処理として切り詰め処理を行う構成を有し、
前記データ変換部の出力部を構成する複数のデータ出力系列各々の出力ビットに対するビット削減数を、予め規定した算出式に従って算出し、算出結果に従った切り詰め処理を実行する構成である請求項１に記載のデータ変換装置。
【請求項１４】
前記データ変換部は、さらに、
入力データに対するデータ攪拌処理を実行する攪拌処理部を有し、
前記複数の圧縮関数実行部は、前記メッセージデータの分割データのすべてを入力可能とした複数段の圧縮関数実行部として構成され、
前記複数段の圧縮関数実行部の一部は、前記攪拌処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、
前記複数段の圧縮関数実行部の一部は、前段の圧縮処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、
前記複数段の圧縮関数実行部の最終段の圧縮処理部は、前記メッセージデータのハッシュ値を出力する構成である請求項１に記載のデータ変換装置。
【請求項１５】
データ変換装置において実行するデータ変換処理方法であり、
データ変換部が、メッセージデータを入力してハッシュ値を生成するデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行するステップであり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行ない、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行うデータ変換方法。
【請求項１６】
データ変換装置においてデータ変換処理を実行させるプログラムであり、
データ変換部に、メッセージデータを入力してハッシュ値を生成させるデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行させるステップであり、
前記プログラムは、前記複数の圧縮関数実行部の各々に、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を実行させ、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部に、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有させて、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行わせるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ変換装置、およびデータ変換方法、並びにプログラムに関する。さらに詳細には、例えば入力メッセージデータに対するハッシュ値生成処理を行うデータ変換装置、およびデータ変換方法、並びにプログラムに関する。
【背景技術】
【０００２】
暗号処理などのデータ変換処理においては、入力データに対するハッシュ処理を実行するハッシュ関数が用いられる場合が多い。ハッシュ関数は与えられたメッセージに対して固定長の長さの圧縮値（ダイジェスト）を計算するための関数である。すでに知られているハッシュ関数としては１２８ビットの出力値を持つＭＤ５や、１６０ビットの出力値を持つＳＨＡ−１、さらに２５６ビットの出力値を持つＳＨＡ−２５６などがある。
【０００３】
例えば解析困難性を高める要請等に基づいて、ハッシュ関数には以下のような耐性が求められる。
原像計算困難性（Ｐｒｅｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）
第二原像計算困難性（２ｎｄ  Ｐｒｅｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）
衝突計算困難性（Ｃｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ）
【０００４】
これらの耐性について簡単に説明する。
入力をｘ、ハッシュ関数をｈとしてｙ＝ｈ（ｘ）を出力とするハッシュ関数において、
原像計算困難性は、出力ｙについてｈ（ｘ）＝ｙとなる入力ｘを計算する困難性に相当する。
第二原像計算困難性は、１つの入力値ｘが既知のとき、ｈ（ｘ'）＝ｈ（ｘ）を満たす異なる入力値ｘ'を見つけることの困難性に相当する。
衝突計算困難性は、ｈ（ｘ'）＝ｈ（ｘ）を満たす２つの異なる入力値ｘ、ｘ'を見つけることの困難性に相当する。
これらの困難性が高いほど、安全性の高いハッシュ関数であると言える。
【０００５】
従来から、利用されてきたハッシュ関数は、近年の解析方法の発展により、上記の耐性についての脆弱性が明らかになってきている。例えば、これまでハッシュ関数として多く利用されてきたＭＤ５やＳＨＡ−１などは衝突計算困難性（Ｃｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ）が多くのシステム要求レベルを満足していないことが明らかになってきている。また、既存のハッシュ関数として比較的長い出力長を持つＳＨＡ−２５６などがあるが、このＳＨＡ２５６もＳＨＡ−１の設計方針を踏襲していることから安全性上の不安が残り、別の設計方針に基づく、安全性の高いハッシュ関数の登場が望まれている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、上記問題点に鑑みてなされたものであり、安全性が高く処理効率の高いハッシュ関数を実現するデータ変換装置、およびデータ変換方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の第１の側面は、
メッセージデータを入力してハッシュ値を生成するデータ変換部を有し、
前記データ変換部は、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行する構成であり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う構成であり、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成であるデータ変換装置にある。
【０００８】
さらに、本発明のデータ変換装置の一実施態様において、前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一のメッセージスケジュール部を複数の圧縮関数実行部で共有した共有メッセージスケジュール部を有し、前記共有メッセージスケジュール部は、前記メッセージデータの分割データを入力してメッセージスケジュール処理により生成した出力データを複数の連鎖値処理部に出力する構成であり、前記複数の連鎖値処理部は、前記共有メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する処理を並列に実行する構成である。
【０００９】
さらに、本発明のデータ変換装置の一実施態様において、前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一の連鎖値処理部を複数の圧縮関数実行部で共有した共有連鎖値処理部を有し、並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データを前記共有連鎖値処理部に出力する構成であり、前記共有連鎖値処理部は、前記複数のメッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する構成である。
【００１０】
さらに、本発明のデータ変換装置の一実施態様において、前記並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データの排他的論理和演算結果を前記共有連鎖値処理部に出力する構成である。
【００１１】
さらに、本発明のデータ変換装置の一実施態様において、前記メッセージスケジュール部は、置換処理を繰り返し実行し、各置換処理結果を中間値として出力する構成を持つ中間出力付き置換関数実行部によって構成され、前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力を付加入力として、置換処理を繰り返し実行する付加入力付き置換関数実行部を有する構成である。
【００１２】
さらに、本発明のデータ変換装置の一実施態様において、前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力と前段の置換処理結果との排他的論理和結果を次の置換処理の入力データとして設定する構成である。
【００１３】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々は、入力データの少なくとも一部データに対する非線形変換処理と、データ入れ替え処理としてのスワップ処理とを含む構成である。
【００１４】
さらに、本発明のデータ変換装置の一実施態様において、前記非線形変換処理は、コンスタント（定数）を適用した排他的論理和演算と、非線形変換処理と、線形変換行列を適用した線形変換処理を含む処理である。
【００１５】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々において行われる線形変換処理は、複数の異なる行列を適用するＤＳＭ（Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）に従った処理として実行する構成である。
【００１６】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々は、それぞれ異なるコンスタント（定数）集合を入力したデータ処理を行う構成であり、１つの置換処理に適用するコンスタント集合を基本集合として、該基本集合に対するデータ変換により生成した異なるコンスタント集合を各置換処理に適用する構成である。
【００１７】
さらに、本発明のデータ変換装置の一実施態様において、前記基本集合となるコンスタント集合は、異なる複数の初期値Ｓ，Ｔに対して予め設定した変換ルールを適用して生成した複数のコンスタントから構成され、前記変換ルールは、前記初期値に対して、
Ｓ←Ｓ・ｘａ、Ｔ←Ｔ・ｘｂ
ただしａ≠ｂ
とする更新処理を含む構成である。
【００１８】
さらに、本発明のデータ変換装置の一実施態様において、前記基本集合に対するデータ変換処理は、前記基本集合を構成するコンスタントの構成ビットのローテーション処理、または、予め規定したマスクデータとの演算処理である。
【００１９】
さらに、本発明のデータ変換装置の一実施態様において、前記データ変換部は、最終的に出力するハッシュ値のビット数削減処理として切り詰め処理を行う構成を有し、前記データ変換部の出力部を構成する複数のデータ出力系列各々の出力ビットに対するビット削減数を、予め規定した算出式に従って算出し、算出結果に従った切り詰め処理を実行する構成である。
【００２０】
さらに、本発明のデータ変換装置の一実施態様において、前記データ変換部は、さらに、入力データに対するデータ攪拌処理を実行する攪拌処理部を有し、前記複数の圧縮関数実行部は、前記メッセージデータの分割データのすべてを入力可能とした複数段の圧縮関数実行部として構成され、前記複数段の圧縮関数実行部の一部は、前記攪拌処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、前記複数段の圧縮関数実行部の一部は、前段の圧縮処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、前記複数段の圧縮関数実行部の最終段の圧縮処理部は、前記メッセージデータのハッシュ値を出力する構成である。
【００２１】
さらに、本発明の第２側面は、
データ変換装置において実行するデータ変換処理方法であり、
データ変換部が、メッセージデータを入力してハッシュ値を生成するデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行するステップであり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行ない、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行うデータ変換方法にある。
【００２２】
さらに、本発明の第３の側面は、
データ変換装置においてデータ変換処理を実行させるプログラムであり、
データ変換部に、メッセージデータを入力してハッシュ値を生成させるデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行させるステップであり、
前記プログラムは、前記複数の圧縮関数実行部の各々に、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を実行させ、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部に、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有させて、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行わせるプログラムにある。
【００２３】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な汎用システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体によって提供可能なプログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００２４】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２５】
本発明の一実施例においては、メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する構成を有する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力し入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成とした。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【発明を実施するための最良の形態】
【００２６】
以下、図面を参照しながら本発明のデータ変換装置、およびデータ変換方法、並びにプログラムの詳細について説明する。
【００２７】
説明は、以下の項目順に行う。
１．定義域拡張法
２．出力サイズを拡大する新しい定義域拡張法
３．新しい定義域拡張法の処理効率向上法
４．攪拌関数Ｆの実現方法
５．定義域拡大法の一般化
６．攪拌関数Ｆの構成の一般化
７．異なる圧縮関数の利用について
８．圧縮関数の内部処理の効率的な実現法
９．入力メッセージ長の拡張法
１０．ＣＶ処理部とＭＳ部に繰り返し型置換を利用したハッシュ関数実現法
１１．ＭＳ部のサイズ拡大法
１２．ＣＶ処理部のサイズ拡大法
１３．ＣＶ処理部とＭＳ部のサイズ拡大法
１４．定義域拡大法用の攪拌関数Ｆの構成法
１５．拡散性能の高い置換処理実現方法
１６．独立性の高い出力をもつ置換関数の生成法
１７．置換関数に適用するコンスタントの生成処理
１８．複数の全体置換に対するコンスタントの生成法
１９．ハッシュ関数の出力値の切り詰め手法
２０．データ変換装置の構成例
【００２８】
［１．定義域拡張法］
先に説明したように、ハッシュ関数実行部は上述した各種の耐性、すなわち、
原像計算困難性（Ｐｒｅｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）
第二原像計算困難性（２ｎｄ  Ｐｒｅｉｍａｇｅ  Ｒｅｓｉｓｔａｎｃｅ）
衝突計算困難性（Ｃｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ）
これらの耐性を備えたものであることが要請される。
【００２９】
なお、本発明のデータ変換装置は、以下において説明するハッシュ関数実行部や、圧縮関数実行部等、各種の関数実行部を有する。以下の説明において、単に［〜関数］として表記としているものは、本発明のデータ変換装置においては、各関数を実行する関数実行部において実行される。なお、関数実行部は、ハードウェアまたはソフトウェア、あるいは両者を用いて実現される。
【００３０】
ハッシュ関数は、与えられたメッセージに対して固定長の長さの圧縮値（ダイジェスト）を計算する圧縮関数（Ｃｏｍｐｒｅｓｓｉｏｎ  Ｆｕｎｃｔｉｏｎ）を利用している。ハッシュ関数を実行するハードウェアやソフトウェアからなるハッシュ処理部を構築する際には、上述した各種の耐性を考慮した構成とすることが要求される。ハッシュ処理部の構成は大きく２つの階層に分けることができる。
（１）第１階層は、定義域拡張（Ｄｏｍａｉｎ  Ｅｘｔｅｎｓｉｏｎ）」部分、
（２）第２階層は、圧縮関数の内部構成、
これらの２つの階層である。
【００３１】
定義域とは、ハッシュ関数の入力値として許容可能なビットサイズ（入力サイズ）である。１つの圧縮関数実行部は固定長の入力値を固定長の出力値に変換する処理を行うが、一般的に１つの圧縮関数実行部では、許容可能な入力ビットサイズが小さく、ビッサイズの大きな入力値は処理できない、従って、複数の圧縮関数を接続して任意長のメッセージ入力を取り扱うように拡張することが行われる。このような処理により、ビット長の長い入力データのハッシュ処理が可能となる。定義域拡張（Ｄｏｍａｉｎ  Ｅｘｔｅｎｓｉｏｎ）」処理とはこのような処理である。
【００３２】
この第１階層としての定義域拡張構成や、第２階層としての圧縮関数の内部構成が上述した耐性のレベルを左右することになる。
【００３３】
はじめに、ここでは前者の定義域拡張処理についての新しい方式について説明する。圧縮関数は、入力値のビット列を、入力ビット長より短い長さのビット列に変換する関数である。図１は圧縮処理部としての圧縮関数（ｆ）を図で表したものである。
【００３４】
図１に示す圧縮関数１０は、入力値としてのＸ：ａビットと、初期値Ｙ：ｂビットの計ａ＋ｂビットを入力して、ｂビット値の出力Ｚを出力する関数である。圧縮関数の入力値として許容可能なビットサイズは定義域（入力サイズ）と呼ばれる。１つの圧縮関数１０単独では長い入力メッセージを取り扱うことができないので、圧縮関数同士を適切に接続することで定義域（入力サイズ）の拡張を行い入力メッセージサイズの拡大を図ることができる。すなわち長いビット長を持つデータを入力することが可能となる。
【００３５】
図２は代表的な定義域拡張法であるメッセージパディング付きのＭＤ構成（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  Ｃｏｎｓｔｒｕｃｔｉｏｎ）を表したものである。なお、この構成については、例えば、［参考文献：Ｒ．Ｍｅｒｋｌｅ，"Ｏｎｅ  ｗａｙ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ｄｅｓ．"ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ'８９（Ｇ．Ｂｒａｓｓａｒｄ，ｅｄ．），ｎｏ．４３５  ｉｎ  ＬＮＣＳ，ｐｐ．４２８−４４６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９８９．
Ｉ．Ｄａｍｇａｒｄ，"Ａ  ｄｅｓｉｇｎ  ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ．"ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ'８９（Ｇ．  Ｂｒａｓｓａｒｄ，ｅｄ．），ｎｏ．４３５  ｉｎ  ＬＮＣＳ，ｐｐ．４１７−４２７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９８９．）］
【００３６】
ＭＤ構成は図２のように圧縮関数（ｆ）を直列に並べて、入力サイズを拡大することを可能とした構成である。入力メッセージは、ビット長調整のためのビットデータ付与処理として行われるパディング（Ｐａｄｄｉｎｇ）処理により圧縮関数のメッセージ入力部サイズであるａビットの整数倍の値になるように補正される。パディング処理後の入力メッセージをａビット単位に分割したものをＭ０，Ｍ１，Ｍ２，・・・，Ｍｎ−２，Ｍｎ−１｜Ｐａｄｄｉｎｇとする。［Ｍｎ−１｜Ｐａｄｄｉｎｇ］は、入力メッセージの末尾データ［Ｍｎ−１］に付加ビットとしてパディングデータを付加して入力ビットサイズをａビットにしているデータである。
【００３７】
メッセージに対するダイジェストを作るためには、あらかじめ決められたｂビットの初期値ＩＶ（Ｉｎｉｔｉａｌ  Ｖａｌｕｅ）と第一の分割メッセージＭ０とを、圧縮関数１１に入力して圧縮してｂビットの値を中間値として出力し、その中間値出力との続くメッセージとを圧縮関数１２に入力して圧縮するという動作を、複数の圧縮関数を用いて繰り返すことで最終的にハッシュ値（Ｈ）を得る構成である。このときの中間値は、連鎖値（Ｃｈａｉｎｉｎｇ  Ｖａｒｉａｂｌｅ）と呼ばれる。
【００３８】
この構成は、個々の圧縮関数自体にＣｏｌｌｉｓｉｏｎ  Ｒｅｓｉｓｔａｎｃｅ（衝突耐性）が存在していれば、ハッシュ関数全体の衝突耐性があることを示すことができることが知られており、実際のハッシュ関数によく用いられている構成である。この構成を利用した代表的なハッシュ関数としてＭＤ５やＳＨＡ−１がある。
【００３９】
［２．出力サイズを拡大する新しい定義域拡張法］
上記構成ではｂビットの出力の場合について説明したが、次に、長いビット長の２ｂビットのハッシュ値を生成するハッシュ関数の構成について考える。
【００４０】
上記のＭＤ構成をそのまま利用する場合には２ｂビットの出力をもつ圧縮関数を準備する必要がある。しかし一般的には大きいサイズの出力をもつ安全性の高い圧縮関数を新たに生成することは難しい。新たな圧縮関数を設計して安全性を評価する必要があり、この設計や評価は、サイズが大きくなればその困難性が増加する。従って、すでに評価がなされているｂビット出力の圧縮関数を使って２ｂビット出力のハッシュ関数を構成できることが望ましい。
【００４１】
出力ビットサイズが小さい圧縮関数を利用して出力ビットサイズの大きいハッシュ値を実現する従来技術としては、カスケードハッシュ（ｃａｓｃａｄｉｎｇ  ｈａｓｈ）構成が知られている。カスケードハッシュ構成について図３を参照して説明する。
【００４２】
カスケードハッシュ構成は２つの圧縮関数を並列に用いて出力サイズの大きなハッシュ値を出力可能とした構成である。図３に示すように、カスケードハッシュは単純に２つの圧縮関数ｆ１，ｆ２を並列に並べたものである。この構成により、２ｂビットの出力を持つハッシュ関数を構成することが可能となる。
【００４３】
しかしながら、このようなｂビット出力の圧縮関数を２つ並べて２ｂビット出力を実行させるハッシュ関数の安全性は２ｂビットの出力サイズを持つハッシュ関数に求められるレベルを達成していない。あくまで、ｂビット分の出力サイズをもつハッシュ関数と同程度の安全性しかないことが知られている。このことは、例えば、以下の文献に記載されている。［Ａ．Ｊｏｕｘ，"Ｍｕｌｔｉｃｏｌｌｉｓｉｏｎｓ  ｉｎ  ｉｔｅｒａｔｅｄ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ．ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｃａｓｃａｄｅｄ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ．"  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ'０４（Ｍ．Ｆｒａｎｋｌｉｎ，ｅｄ．），ｎｏ．３１５２  ｉｎ  ＬＮＣＳ，  ｐ．３０６−３１６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００４．］
【００４４】
次に、本発明の一実施例に係る安全性を高めた圧縮処理部（圧縮関数）の構成について図４を参照して説明する。図４には、ａビット入力、２ｂビット出力の圧縮処理部である圧縮関数ユニット５０を示している。図４に示す圧縮関数ユニット５０は、ａ＋ｂビット入力、ｂビット出力の独立した２つのデータ圧縮処理部としての圧縮関数ｆ１，ｆ２と、２ｂビット入出力のデータ攪拌処理部としての攪拌関数Ｆを有する。すなわち１つの攪拌関数Ｆと２系列の圧縮関数ｆ１，ｆ２を持つ。
【００４５】
圧縮関数ユニット５０は、入力としてａビットの［Ｘ］、２ｂビットの［Ｙ］の計２ｂ＋ａビットの入力を受け取る。入力のうち２ｂビット分のデータ［Ｙ］は２ｂビット入出力を持つ攪拌関数Ｆを通過して攪拌される。続いて攪拌関数Ｆの２ｂビット出力はｂビットずつに分割され、片方のｂビットデータと圧縮関数ユニット５０の残りの入力のａビットデータＸとがユニット内部の圧縮関数ｆ１により処理される。もう片方のｂビットデータとａビットデータＸがユニット内部の圧縮関数ｆ２により並列処理される。最終的にｆ１とｆ２の出力を結合した２ｂビットが圧縮関数５０の出力となる。なお、攪拌関数Ｆは入力された２ｂビットのデータを攪拌して出力する関数であり、２つの圧縮関数ｆ１とｆ２は異なる圧縮関数である。
【００４６】
長い入力ビットを処理可能とする定義域拡張のために、図４に示す圧縮関数ユニット５０をＭＤ構成として接続したハッシュ関数構成例を図５に示す。図５に示すデータ変換装置は、ＭＤ構成からなるデータ変換部を有する。図５に示す構成は、図４を参照して説明した圧縮関数ユニット５０をｎ段持つデータ変換部からなる構成である。すなわち、２ｂビット入出力の１つの攪拌関数Ｆと、ａ＋ｂビット入力ｂビット出力の２系列の圧縮関数ｆ１，ｆ２を有する圧縮関数ユニット５０をｎ段構成としたハッシュ関数実行部としてのデータ変換装置である。
【００４７】
図５に示すハッシュ関数は、圧縮関数ユニット５０−０〜（ｎ−１）をｎ段構成として繰り返し適用して最終段の圧縮関数ユニット５０−（ｎ−１）から２ｂビットのハッシュ値（Ｈ１｜Ｈ２）を出力する。
【００４８】
第１段の圧縮関数ユニット５０−０は、入力ビットＭ０〜Ｍｎ−１の最初のａビットＭ０と、２つのｂビット初期値ＩＶ１とＩＶ２を入力し、各圧縮関数ｆ１，ｆ２がそれぞれｂビット、計２ｂビットを出力する。その後は、前段の圧縮関数ユニットの内部の圧縮関数ｆ１，ｆ２の出力する２ｂビットと、Ｍ０〜Ｍｎ−１の構成ビットであるａビットを入力して２ｂビットを出力する。以下、同様の処理を繰り返し実行し、最終段では、前段の出力２ｂビットと、Ｍｎ−１とパディングデータからなるａビットを入力して、ｂビットの出力Ｈ１，Ｈ２の計２ｂビットのハッシュ値（Ｈ１｜Ｈ２）を出力する。
【００４９】
この構成は、圧縮関数ユニット５０を構成する内部の圧縮関数ｆ１，ｆ２と、攪拌関数Ｆがランダムオラクルと呼ばれる性質を満たしていれば十分な安全性があることが示される。ランダムオラクルとは入力が与えられると内部で乱数を発生しその乱数を出力し、すでに与えられたことのある入力が再度与えられた場合には過去に出した乱数を再度出力する関数である。実際にはランダムオラクルのようなふるまいを近似する乱数生成の不要な決定的な手続きで出力を演算する関数を設計して置き換えることにより実現する。この構成により圧縮関数内部において安全性の評価がしやすく処理の軽い部品を利用できるため、設計がしやすく効率的の高いハッシュ関数が実現可能である。
【００５０】
本実施例によれば、複数ラウンドからなる圧縮処理ラウンドの少なくとも一定タイミング毎に攪拌処理を実行させる構成としたので、解析困難性を高めた安全性の高いハッシュ値生成を行うデータ変換装置が実現される。
【００５１】
また、図５で示した構成の変形例として、図６に示すように圧縮関数内部で攪拌関数Ｆと圧縮関数ｆ１およびｆ２の順序を入れ替えた圧縮関数ユニット５５を利用した場合も同じ効果のあるハッシュ関数として利用することが可能である。
【００５２】
さらに、図５、図６で示した構成の変形例として、図７に示すように図６に示す構成における最終部分の攪拌関数Ｆを削除した構成でも安全性上は同じ効果のあるハッシュ関数として利用することが可能である。図５に示す構成において最初の攪拌関数Ｆの出力をＩＶ１，ＩＶ２として定義しなおすことでこの構成を得られることからも同様のことが導かれる。
【００５３】
このように２ｂビット出力の専用の圧縮関数を作ることなく、より小さなｂビット出力の圧縮関数と攪拌関数Ｆにより、安全性の高い２ｂビット出力のハッシュ関数が構成できる。
【００５４】
また図５、図６、図７に示した構成では、圧縮関数ユニット内の内部の圧縮関数ｆ１とｆ２の出力ビット数が両者ともｂビットであり、中間値、すなわち連鎖値（Ｃｈａｉｎｉｎｇ  Ｖａｒｉａｂｌｅ）が、内部圧縮関数ｆ１とｆ２とで一致する構成とした。
【００５５】
しかし、これらの内部圧縮関数ｆ１，ｆ２の連鎖値（ＣＶ）のビットサイズが一致している必要はない。例えば内部圧縮関数ｆ１はｂビットの連鎖値（ＣＶ）を出力し、内部圧縮関数ｆ２はｃビットの連鎖値（ＣＶ）を出力する設定として、全体としての連鎖値（ＣＶ）をｂ＋ｃビットとする構成にしてもよい。このような構成でも、圧縮関数ユニットは、より小さい関数の構成により実現できるため、安全性の確認されている小さいビットサイズ対応の圧縮関数を内部圧縮関数として適用することができる。
【００５６】
［３．新しい定義域拡張法の処理効率向上法］
続いて、図５，図６を参照して説明した定義域拡張法の処理効率を向上させたハッシュ関数の構成例について、図８を参照して説明する。図８は攪拌関数Ｆを挿入する間隔を圧縮関数の２回分の処理ごとに設定したハッシュ関数構成例である。
【００５７】
圧縮関数ユニット６０は、攪拌関数Ｆと、２段の内部圧縮関数ｆ１、ｆ３、２段の内部圧縮関数ｆ２、ｆ４によって構成される。なお圧縮関数ユニット６０に含まれる４つの内部圧縮関数は、それぞれが異なる独立した圧縮関数である。すなわち、２つの攪拌関数Ｆに挟まれた領域内に含まれる４つの圧縮関数は独立した圧縮関数である。
【００５８】
第１段の圧縮関数ユニット６０は、２つのｂビット初期値ＩＶ１とＩＶ２を入力し、攪拌関数Ｆは入力された２ｂビットのデータを攪拌してｂビットずつ各圧縮関数ｆ１，ｆ２に出力する。各圧縮関数ｆ１，ｆ２は、入力ビットＭ０〜Ｍｎ−１の最初のａビットＭ０と、攪拌関数Ｆからの出力ｂビットをそれぞれ入力して、ｂビット出力を生成して、後段の圧縮関数ｆ３，ｆ４に出力する。
【００５９】
圧縮関数ｆ３，ｆ４は、入力ビットＭ０〜Ｍｎ−１のａビットＭ１と、前段の圧縮関数ｆ１，ｆ２からの出力ｂビットをそれぞれ入力して、ｂビット出力を生成して、後段の圧縮関数ユニットの攪拌関数Ｆに出力する。
【００６０】
その後は、前段の圧縮関数ユニットの内部の圧縮関数出力する２ｂビットと、Ｍ０〜Ｍｎ−１の構成ビットである２ａビットを入力して２ｂビットを出力する。以下、同様の処理を繰り返し実行し、最終段では、前段の出力２ｂビットと、ａビットのＭｎ−２と、Ｍｎ−１とパディングデータからなるａビットを入力して、ｂビットの出力Ｈ１，Ｈ２の計２ｂビットのハッシュ値（Ｈ１｜Ｈ２）を出力する。
【００６１】
この構成では図５に示す構成に比較して同じ長さのメッセージを処理する際の攪拌関数Ｆの呼び出し回数が削減されているため処理効率が向上する。具体的には図５に示す構成では、２つ分のａビットメッセージを処理する間に必要とされる処理は攪拌関数Ｆを２回と圧縮関数４回であるのに対し、図８に示す方式では攪拌関数Ｆを１回と圧縮関数４回の処理で行えるため、１回分のＦの処理を削減可能となり、処理の効率化が実現される。
【００６２】
図８に示す構成は、攪拌関数Ｆと２段階の圧縮関数を繰り返し実行する設定としている。攪拌関数の処理回数をさらに削減し、３段階以上の圧縮関数ごとに攪拌関数Ｆを設定するといった構成も可能である。攪拌関数Ｆの挿入間隔を圧縮関数ｋ回ごとに設定した一般化したハッシュ関数実行部の構成例を図９に示す。図９に示す構成において、圧縮関数ユニット７０は、２ｂビット入出力の１つの攪拌関数Ｆと、ａ＋ｂビット入力、ｂビット出力のｋ段の圧縮関数を２系列とした構成を持つ。
【００６３】
第１段の圧縮関数ユニット７０は、２つのｂビット初期値ＩＶ１とＩＶ２を入力し、攪拌関数Ｆは入力された２ｂビットのデータを攪拌して２系列構成とされた各圧縮関数ｆ１，ｆ２にｂビットずつ出力する。各圧縮関数ｆ１，ｆ２は、入力ビットＭ０〜Ｍｎ−１の最初のａビットＭ０と、攪拌関数Ｆからの出力ｂビットをそれぞれ入力して、ｂビット出力を生成して、後段の圧縮関数ｆ３，ｆ４に出力する。
【００６４】
圧縮関数ｆ３，ｆ４は、入力ビットＭ０〜Ｍｎ−１のａビットＭ１と、前段の圧縮関数ｆ１，ｆ２からの出力ｂビットをそれぞれ入力してｂビット出力を生成して、次の圧縮関数に出力する。以下、前段の圧縮関数の出力と、入力ビットＭ０〜Ｍｎ−１を構成するａビットが後段の圧縮関数の入力となり、それぞれｂビットを出力するこれをｋ回繰り返し、ｋ回目の２系列の圧縮関数の出力が次の圧縮関数ユニット７１の攪拌関数Ｆの入力とされる。
【００６５】
圧縮関数ユニット７１の処理は圧縮関数ユニット７０の処理と同様である。ただし入力ビットＭ０〜Ｍｎ−１の後半のビットデータとパディングデータが入力される。最終的に、圧縮関数ユニット７１の際集団の２系列の圧縮関数からそれぞれｂビットの出力Ｈ１，Ｈ２の計２ｂビットのハッシュ値（Ｈ１｜Ｈ２）が出力される。
【００６６】
なお攪拌関数Ｆの挿入間隔はハッシュ値としての出力長２ｂに応じて安全性を落とさない範囲で決められる値である。例えばｂ＝２５６の時にｋ＝８とする構成があげられる。ｋが大きければ大きいほど処理効率が向上する。
【００６７】
図９に示す構成は、図５に示す構成と同様、攪拌関数Ｆが初期値を入力して、攪拌関数Ｆの後段に２系列の圧縮関数を設定した構成であるが、先に図６等を参照して説明した２系列の圧縮関数が初期値を入力して、複数段の２系列の圧縮関数を実行させた後、攪拌関数Ｆを最終的に実行させる設定とした圧縮関数ユニットを利用する構成も可能である。
【００６８】
［４．攪拌関数Ｆの実現方法］
攪拌関数Ｆは、入力ビットを攪拌して入力ビットと同一のビット数のデータを出力する関数である。具体的な攪拌関数の実現構成について図１０を参照して説明する。図１０は、攪拌関数Ｆを２つの圧縮関数を用いて実現した構成である。
【００６９】
図１０（１）に示す攪拌関数Ｆ８０は、２ｂビット入出力の攪拌関数Ｆ８０をｂビット入力ａビット出力の２つの変換部８１，８２と２つのａ＋ｂビット入力ｂビット出力の圧縮関数８３，８４により実現した例である。攪拌関数Ｆ８０に入力される分割された２つのｂビットデータはそれぞれ圧縮関数８３，８４の入力のｂビット分として供給される。
【００７０】
また同時に、それぞれのｂビットデータは変換部８１，８２に入力されてａビットデータに変換され、圧縮関数８３，８４のａビット分の入力データとしてそれぞれ供給される。変換部８１，８２はビット長を調整するための単純な処理でよく例えばビットの複製による拡張、ＸＯＲなどの単純な演算処理構成により実現可能である。
【００７１】
変換部８１，８２は以下の条件を満足する設定とすることが好ましい。すなわち、それぞれの圧縮関数８３，８４の入力ａ＋ｂビットに攪拌関数Ｆ８０の入力２ｂビットのすべてのビットが影響を及ぼす設定とすることである。図１０に示す構成によって攪拌関数Ｆは構成可能であり、結果として２つの圧縮関数にかかる処理程度で攪拌関数Ｆを実現することが可能である。
【００７２】
図１０（２）に示す攪拌関数Ｆ８５は、変換部８６，８７の入力を２ｂビットとした例である。変換部８６，８７は、たとえばａ＞ｂである場合に２つのｂビットデータを連結したのちに切り詰め、ＸＯＲなどの単純な操作によりａビットを作り出す関数によって構成される。変換部８６，８７も以下の条件を満足する設定とすることが好ましい。すなわち、それぞれの圧縮関数８８，８９の入力ａ＋ｂビットには攪拌関数Ｆ８５の入力２ｂビットのすべてのビットが影響を及ぼす設定とすることである。この構成でも、２つの圧縮関数にかかる処理程度で攪拌関数Ｆを実現することが可能である。
【００７３】
この図１０に示す攪拌関数Ｆの構成は、図５〜図９を参照したハッシュ関数の構成における攪拌関数Ｆとして利用できる。このような構成を利用することで、図５〜図９に示す圧縮関数ユニットに元々設定されている圧縮関数を再利用して攪拌関数Ｆを実現することが可能である。このような部品の共有化によりハードウェア実装時のゲート規模の削減効果が発揮され、装置の小型化、コストダウンが可能となる。
【００７４】
［５．定義域拡大法の一般化］
図５〜図９を参照して説明したＭＤ構成を持つハッシュ関数は、１つの攪拌関数Ｆの出力を２系列の圧縮関数に対して入力する構成、あるいは２系列の圧縮関数の出力を１つの攪拌関数Ｆに出力する設定であった。すなわち、圧縮関数は２つの系列を用いた設定である。
【００７５】
圧縮関数の系列数は、２に限るものではなく、３以上の系列を用いる構成としてもよい。系列数＝ｍ、ただしｍは２以上の整数としたハッシュ関数の一般化構成例を図１１に示す。
【００７６】
図１１の構成は、図９に示す構成をベースとして、圧縮関数の系列数を２からｍに変更した構成である。圧縮関数ユニット９０は、ｍｂビット入出力の攪拌関数Ｆと、ｍ系列構成とされた圧縮関数を複数段有する。最初の段のｍ個の圧縮関数ｆ１〜ｆｍは、Ｆ関数からｍｂビットのビットデータからのｂビットと、入力ビットＭ０〜Ｍｎ−１の最初のａビットＭ０とを入力して、それぞれｂビットを出力し後段の圧縮関数に入力する。ｋ段のｍ系列圧縮関数は、それぞれ前段の圧縮関数からの出力と入力ビットＭ０〜Ｍｎ−１のａビットとを入力してｂビットを出力する。ｋ段の圧縮関数の処理の後、圧縮関数ユニット９０の最終段の圧縮関数の出力ｍｂビットは、次の圧縮関数ユニットの攪拌関数Ｆに入力される。
【００７７】
最終段の圧縮関数ユニット９１の最終段のｍ個の圧縮関数の各々の出力ｂビットの出力Ｈ１〜Ｈｍの計２ｍｂビットがハッシュ値（Ｈ１｜Ｈ２｜・・・｜Ｈｍ）として出力される。得られるハッシュ値Ｈ１，Ｈ２，...，Ｈｍは最大でｍｂビットである。この手法によりより長いサイズの出力を持つハッシュ関数の実現が容易となる。
【００７８】
［６．攪拌関数Ｆの構成の一般化］
次に、攪拌関数Ｆの一般化された構成について説明する。攪拌関数Ｆの具体的構成については、先に図１０を参照して説明した。図１０を参照して説明した攪拌関数Ｆは、２系列の圧縮関数を適用した構成であった。
【００７９】
これを一般化したｍｂビット入出力の攪拌関数Ｆの構成例を図１２に示す。図１２に示す攪拌関数Ｆ１００は、ｍ系列のｃビット入力ｂビット出力の圧縮関数ｆ１〜ｆｍと、その前段のｍ個の変換部によって構成される。
【００８０】
図１２に示す例ではｍ種類の異なる独立な各圧縮関数ｆ１〜ｆｍの入力サイズはそれぞれｃビットとしている。各圧縮関数ｆ１〜ｆｍへはすべての入力ビットの影響が及ぼされるようにｍｂビットの入力がすべていったん変換部に入力され、圧縮関数の入力サイズに合うように切り詰められる。変換部では例えば排他的論理和（ＸＯＲ）や、ビットサイズ拡大処理などによりｍｂビット入力からｃビット出力を生成する。
【００８１】
変換部に求められる条件は、ｃビットの出力のいずれかのビットに、攪拌関数Ｆ１００に対する入力ビットであるｍｂビットのすべてのビットが影響を与えているようにすることである。これは簡単な操作により実現可能である。例えば、ｃ＝ｍｂであった場合には、変換部は入力をそのまま連結して出力すれば良い。
【００８２】
［７．異なる圧縮関数の利用について］
以上の説明において、複数系列の多段構成とした圧縮関数ｆ１，ｆ２，...，ｆｍを持つ圧縮関数ユニットにおいて、圧縮関数ユニット内の圧縮関数ｆ１〜ｆｍは、それぞれ異なる構成であるものとして説明した。もっとも安全性が高いことを客観的に示すことができるのがこの構成であり、たとえ単一の圧縮関数を用いた場合に即座に安全性が損なわれているわけではない。単一の圧縮関数を繰り返し使った方が実装上のメリットがある場合もあるため、別の実施の形態としてすべての圧縮関数を同じものにする構成も可能である。また単一にしなくとも、より少ない種類の圧縮関数を繰り返し用いる構成も同様に可能である。
【００８３】
［８．圧縮関数の内部処理の効率的な実現法］
次に上記の説明において示した圧縮関数ユニット内に設定する圧縮関数ｆｉの具体的な構成例について説明する。圧縮関数ｆの内部構成例を図１３に示す。図１３は、図５〜図１２を参照して説明した圧縮関数ユニット内に設定する圧縮関数ｆｉ、さらに、攪拌関数Ｆの構成要素として利用可能な圧縮関数ｆｉの構成例である。
【００８４】
図１３に示すように圧縮関数１２０は、メッセージスケジュール部（ＭＳ部）１２１と、連鎖値（ＣＶ：Ｃｈａｉｎｉｎｇ  Ｖａｒｉａｂｌｅ）処理部１２２を有する。圧縮関数１２０に対する入力であるａ＋ｂビット中、［Ｘ］ａビットはメッセージスケジュール部（ＭＳ部）１２１に入力され、残りの［Ｙ］ｂビットが連鎖値（ＣＶ）処理部１２２に入力される。
【００８５】
メッセージスケジュール部（ＭＳ部）１２１は、ａビット入力に基づくメッセージスケジュール処理により、ｃビット出力を生成して連鎖値（ＣＶ）処理部１２２に入力する。連鎖値（ＣＶ）処理部１２２は、圧縮関数１２０に対する入力ｂビットと、メッセージスケジュール部（ＭＳ部）１２１からの入力ｃビットのｂ＋ｃビットを入力して、圧縮関数１２０の出力としてｂビット出力［Ｚ］を生成する。
【００８６】
この図１３に示す圧縮関数、すなわち、メッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部とによって構成される圧縮関数を、先に図５を参照して説明したＭＤ構成を持つハッシュ関数に設定した構成例を図１４に示す。
【００８７】
図１４に示す圧縮関数ユニット１３０は、先に図５を参照して説明したと同様、攪拌関数Ｆと、２系列の圧縮関数ｆ１，ｆ２によって構成される。この圧縮関数ｆ１，ｆ２の各々が、図１３を参照して説明した構成を持つ。すなわち、メッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部とによって構成される圧縮関数である。
【００８８】
図１４に示す例では２種類の圧縮関数ｆ１，ｆ２内のメッセージスケジュール部（ＭＳ部）をＭＳ１、ＭＳ２とし、連鎖値（ＣＶ）処理部をＣＶ１，ＣＶ２として示している。この構成によってハッシュ関数を実現することができる。以下では、さらなる処理効率の向上を実現する構成について説明する。
【００８９】
図１４に示す圧縮関数ユニット１３０−０〜１３０−（ｎ−１）の各々には、メッセージＭｉが２つの圧縮関数内のメッセージスケジュール部ＭＳ１およびＭＳ２に同時に入力されている。従って上下に並ぶ２系列の圧縮関数においてメッセージスケジュール部の共有化を行うことで処理の削減を行うことができる。
【００９０】
図１５はメッセージスケジュール部の共有を行ったハッシュ関数の構成例を示したものである。図１４において、各圧縮関数ユニット１３０−０〜１３０−（ｎ−１）に含まれていた上下２つの圧縮関数のメッセージスケジュール部を共有化して１つのメッセージスケジュール部（ＭＳ部）１４１とした圧縮関数１４２を設定している。この１つのメッセージスケジュール部（ＭＳ部）１４１を持つ圧縮関数１４２の構成を適用すれば、１つの圧縮関数ユニット１４０において実行するメッセージスケジュール部（ＭＳ部）の演算処理が１回の処理で済むことになり、必要な演算処理を少なくすることが可能である。例えば、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【００９１】
図１５を参照して説明した複数の圧縮関数におけるメッセージスケジュール部の共有化構成は、前述の複数のハッシュ構成において適用できる。すなわち、図５〜図１２を参照して説明した複数系列の圧縮関数を持つ圧縮関数ユニットや攪拌関数Ｆ内の圧縮関数においても適用できる。
【００９２】
［９．入力メッセージ長の拡張法］
次に、圧縮関数内の入力メッセージサイズを拡張する方法について検討する。図１６に示す圧縮関数１５０は、図１３を参照して説明した圧縮関数１２０と同様、メッセージスケジュール部（ＭＳ部）１５１と連鎖値（ＣＶ）処理部１５２から構成される。先に説明した図１３に示す圧縮関数１２０はメッセージスケジュール部（ＭＳ部）１２１に対するメッセージ入力としてａビット入力構成であった。これに対して、図１６に示す圧縮関数１５０は、２ａビット入力に対応したメッセージスケジュール部１５１を有する。
【００９３】
一般的にはａビット入力に対応した関数と２ａビット入力に対応した関数は別物であり、異なる安全性評価基準に基づいて評価しなくてはいけない。よって、できる限り、すでに安全性や性能の評価ができているａビット入力に対応した関数を組み合わせて、２ａビットに対応したメッセージスケジュール部を構成できる方が望ましい。また、そうすることによってほかに存在するａビット入力に対応した関数を再利用することも可能となる。具体的な関数の構成例は後段で説明するものとし、ここではａビット入力に対応した関数を利用して２ａビット入力やそれ以上の入力に対応した圧縮関数を構成する方法について述べる。
【００９４】
図１７に、メッセージスケジュール部を２つの部分に分割した構成を持つ圧縮関数１６０の構成例を示す。圧縮関数１６０に対するメッセージ入力２ａビットデータは２つのａビットデータに分割されたのち、各々がメッセージスケジュール部１６１，１６２においてｃビット出力を生成する処理が行われる。２つのメッセージスケジュール部１６１，１６２の出力ｃビットはいずれも１つの連鎖値（ＣＶ）処理部１６３に供給される。
【００９５】
連鎖値（ＣＶ）処理部１６３は、２つのメッセージスケジュール部１６１，１６２の出力ｃビットと、圧縮関数１６０に対する入力ｂビットを入力として、圧縮関数の出力であるｂビット出力［Ｚ］を生成して出力する。この構成のメリットとしては２ａビットより短いａビット入力に対応した関数（メッセージスケジュール部）を利用して２ａビットのメッセージ入力を実現する圧縮関数を構成可能となる点である。
【００９６】
図１８に示す圧縮関数１７０は、図１７に示す圧縮関数１６０と同様、メッセージスケジュール部を２つの部分に分割した構成を持つ圧縮関数１７０の構成例である。この圧縮関数１７０は排他的論理和演算（ＸＯＲ）部１７４を有する。
【００９７】
圧縮関数１７０に対するメッセージ入力２ａビットデータは２つのａビットデータに分割されたのち、各々がメッセージスケジュール部１７１，１７２においてｃビット出力を生成する処理が行われる。２つのメッセージスケジュール部１７１，１７２の出力ｃビットは、排他的論理和演算（ＸＯＲ）部１７４において排他的論理和演算がなされた後、１つの連鎖値（ＣＶ）処理部１７３に供給される。
【００９８】
２つのメッセージスケジュール部同士の出力が一旦、排他的論理和演算部１７４で処理されたのちに連鎖値（ＣＶ）処理部１７３に供給される構成である。この構成のメリットとしては連鎖値（ＣＶ）処理部１７３が受け取るメッセージサイズは増加しないことにより連鎖値（ＣＶ）処理部１７３の内部が簡素化できる点である。なお排他的論理和部分をモジュロ加算処理に置き換えてもよい。
【００９９】
図１９は、図１７に示す圧縮関数１６０の構成を一般化してｎａビットの入力に対応するように設定した圧縮関数２１０の構成例を示している。圧縮関数２１０に入力されたｎａビットのメッセージはｎ個のａビットメッセージに分割されそれぞれが独立にａビット入力に対応したメッセージスケジュール部（ＭＳ部）２１１−１〜ｎによって処理されて、各メッセージスケジュール部（ＭＳ部）２１１−１〜ｎがｃビット出力を生成する。
【０１００】
各メッセージスケジュール部（ＭＳ部）２１１−１〜ｎのｃビット出力は連鎖値（ＣＶ）処理部２１２に供給される。連鎖値（ＣＶ）処理部２１２は、ｎ個のメッセージスケジュール部（ＭＳ部）２１１−１〜ｎの出力ｎｃビットと、圧縮関数２１０に対する入力ｂビットを入力として、圧縮関数の出力であるｂビット出力［Ｚ］を生成して出力する。
【０１０１】
この構成も、先に図１７を参照して説明したと同様のメリットを有する。すなわち、ｎａビットより短いａビット入力に対応した関数（メッセージスケジュール部）を利用してｎａビットのメッセージ入力を実現する圧縮関数が構成可能となる。
【０１０２】
図２０は、図１８に示す圧縮関数１７０の構成を一般化してｎａビットの入力に対応するように設定した圧縮関数２２０の構成例を示している。圧縮関数２２０に入力されたｎａビットのメッセージはｎ個のａビットメッセージに分割されそれぞれが独立にａビット入力に対応したメッセージスケジュール部（ＭＳ部）２２１−１〜ｎによって処理されて、各メッセージスケジュール部（ＭＳ部）２２１−１〜ｎがｃビット出力を生成する。
【０１０３】
各メッセージスケジュール部（ＭＳ部）２２１−１〜ｎのｃビット出力は、排他的論理和演算部（ＸＯＲ）２２３−１〜ｎにおいて排他的論理和演算がなされた後、１つの連鎖値（ＣＶ）処理部２２２に供給される。連鎖値（ＣＶ）処理部２２２は、排他的論理和演算部（ＸＯＲ）２２３−ｎの出力ｃビットと、圧縮関数２２０に対する入力ｂビットを入力として、圧縮関数の出力であるｂビット出力［Ｚ］を生成して出力する。この構成も、ｎａビットより短いａビット入力に対応した関数（メッセージスケジュール部）を利用してｎａビットのメッセージ入力を実現する圧縮関数が構成可能となる。なお、排他的論理和演算部をモジュロ加算処理部とする構成も可能である。
【０１０４】
このように本発明の一実施例に係るデータ変換装置は、メッセージデータの分割データを並列に入力する複数の処理系列を有し、複数の圧縮関数実行部（ｆ）を適用したデータ変換処理を実行する構成を有する。
【０１０５】
複数の圧縮関数実行部（ｆ）の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部（ＭＳ部）を適用した処理と、メッセージスケジュール部（ＭＳ部）の出力と、前段処理部からの出力である中間値（連鎖値）を入力し、入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値（ＣＶ）処理部を適用した処理を行う構成である。
【０１０６】
複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部（ＭＳ部）、または連鎖値（ＣＶ）処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行う。このような構成により、例えば、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【０１０７】
［１０．ＣＶ処理部とＭＳ部に繰り返し型置換を利用したハッシュ関数実現法］
上述したように、圧縮関数は、メッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部を構成用素として実現可能である。このメッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部の具体的な構成例について説明する。
【０１０８】
メッセージスケジュール部（ＭＳ部）や、連鎖値（ＣＶ）処理部は置換関数をベースとしているものが一般的に知られている。例えば、ハッシュ関数として知られるＳＨＡ−１，Ｗｈｉｒｌｐｏｏｌなどが置換関数をベースとした構成を持つ。
【０１０９】
メッセージスケジュール部（ＭＳ部）や、連鎖値（ＣＶ）処理部に適用する置換関数は、攪拌性能の高い置換関数が好ましい。
【０１１０】
比較的単純な置換関数を繰り返し適用して攪拌性能を高めた置換関数の構成例について説明する。以下の説明において、置換関数内において繰り返される比較的単純な置換を「内部置換」とよび、その結果できる置換を「全体置換」と呼ぶものとする。
【０１１１】
なお、置換関数は、入出力サイズが同一であり、かつ、それぞれの入出力値が一対一で対応するように入力値に基づいて出力値を生成する関数である。なお、置換関数は、この性質により逆関数が存在する。
【０１１２】
全体置換の内部では、２つの内部置換処理同士の間の中間データに対して外部からデータの加算を行ったり、その中間データを関数外部へ出力したりすることが可能である。圧縮関数では、この中間データを利用して全体置換の本来の入出力以外の位置に対するデータ入力や、追加データの出力を行う場合がある。そのように本来の入力以外に与えられるデータを付加入力と呼び、中間データを本来の出力以外に出力とするときにはそのデータを中間出力と呼ぶ。
【０１１３】
図２１に示す置換関数（置換処理部）３１０は、付加入力３１１のある置換関数の例である。また、図２２に示す置換関数（置換処理部）３２０は、中間出力３２１のある置換関数の例である。
【０１１４】
図２１、図２２に示す置換関数は、ともにａビット入出力に対応した全体置換をベースとしている。内部では内部置換１から内部置換ｋまでが繰り返し適用される構成である。図２１に示す置換関数３１０は、付加入力３１１が内部置換の出力値である中間データに排他的論理和され、後段の内部置換処理部に出力、あるいは外部出力する構成を持つ。図２２に示す置換関数３２０は内部置換の出力値である中間データが中間出力３２１として外部に出力される。以降ではこのようなタイプの全体置換と通常の全体置換を区別するために、それぞれ、図２１に示すタイプの置換関数を付加入力付き置換関数、図２２に示すタイプの置換関数を中間出力付き置換関数と呼ぶものとする。
【０１１５】
なお、付加入力つき置換関数では、
＊付加入力が固定されたときは入力，出力が１対１対応する
という置換本来の性質を継承している。
また、中間出力付き置換関数では、
＊入力とそれぞれの中間出力は１対１対応
という置換関数由来の性質をもつという特徴がある。
【０１１６】
ハッシュ関数を構成する圧縮関数は、先に図１３〜図２０を参照して説明したように、メッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部とによって構成される。
連鎖値（ＣＶ）処理部に付加入力付き置換関数を用い、
メッセージスケジュール部（ＭＳ部）に中間出力付きの置換関数を用いて互いに接続して圧縮関数を構成することについてはすでに知られていた（Ｗｈｉｒｌｐｏｏｌ）。
【０１１７】
図２３に、この既存の置換関数を用いた圧縮関数３３０の構成例を示す。図２３に示す圧縮関数３３０は、メッセージスケジュール部（ＭＳ部）３３１を、中間出力付きａビット置換関数として設定し、この中間出力を連鎖値（ＣＶ）処理部３３２に用いた付加入力付きのａビット置換関数の付加入力に接続した構成を持つ。
【０１１８】
図２３に示す構成では、説明を容易にするためにメッセージスケジュール部（ＭＳ部）３３１と、連鎖値（ＣＶ）処理部３３２をともにａビット置換関数としているが、必ずしもメッセージスケジュール部（ＭＳ部）３３１と、連鎖値（ＣＶ）処理部３３２の置換のサイズが一致しなくてもよい。長さが異なる場合には適切に拡張・切り詰め操作を行い調整することも可能である。また必ずしも図２３に示すようにすべての中間出力を、メッセージスケジュール部（ＭＳ部）３３１と、連鎖値（ＣＶ）処理部３３２との間で接続する必要もなく、安全性や処理効率を考慮して適切に間引くなどの処理を実行し、メッセージスケジュール部（ＭＳ部）３３１と、連鎖値（ＣＶ）処理部３３２との間を接続する中間データは取捨選択してもよい。
【０１１９】
［１１．ＭＳ部のサイズ拡大法］
圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例を図２４に示す。図２４に示す圧縮関数３４０は、入力ビットが３ａビットに拡大された圧縮関数である。この図２４に示す圧縮関数３４０は、先に、図１８を参照して説明した構成と同様の構成であり、２つのメッセージスケジュール部（ＭＳ部）３４１，３４２と、２つのメッセージスケジュール部（ＭＳ部）３４１，３４２の出力の排他的論理和演算（ＸＯＲ）結果を入力する１つの連鎖値（ＣＶ）処理部３４３を有する。
【０１２０】
２つのメッセージスケジュール部（ＭＳ部）３４１，３４２は、いずれも中間出力付き置換関数によって構成される。１つの連鎖値（ＣＶ）処理部３４３は、付加入力付き置換関数によって構成される。
【０１２１】
図２４に示す置換関数３４０は、２ａビットの入力Ｘがａビットずつに分割されそれぞれが２つのメッセージスケジュール部（ＭＳ部）３４１，３４２に入力され、これらの２つのメッセージスケジュール部（ＭＳ部）３４１，３４２の中間出力が１つの連鎖値（ＣＶ）処理部３４３に供給される構成である。このように付加入力付き置換関数、中間出力付き置換関数を用いれば容易に入力長の増大が可能となる。
【０１２２】
またこの図２４に示す置換関数３４０の構成は、メッセージスケジュール部（ＭＳ部）として利用される２つの置換関数は同一のものであってはならない、同一である場合にはそれぞれの置換に対して同じａビットデータが入力された場合には対応する中間出力同士が一致してしまい排他的論理和演算（ＸＯＲ）した結果がキャンセルされるためである。このためこの２者間には必ず異なる置換関数を準備する必要がある。これは内部置換の構成を異なるものにすることで実現可能である。
【０１２３】
この図２４に示す圧縮関数の構成を一般化して入力Ｘを３ａビット以上に拡大することも可能である。例えば、メッセージスケジュール部（ＭＳ部）の追加によって実現できる。
【０１２４】
図２４に示す構成において処理量を減らし高速化を図る方法を示す。ハッシュ関数を構成する多段構成の圧縮関数において、例えば図４、図５等を参照して説明したように、圧縮関数が入力する値は、データ［Ｘ］としてメッセージ、データＹとして中間値、すなわち連鎖値（ＣＶ）である。
【０１２５】
この際、メッセージ処理用の置換の繰り返し回数と連鎖値（ＣＶ）の系列用置換の繰り返し回数は必ずしも一致させる必要があるわけではない。例えば安全性を損なわない範囲でメッセージ処理用の置換の繰り返し回数を半分にする場合を考える。
【０１２６】
図２５は、図２４と同様、入力ビットが３ａビットに拡大された圧縮関数３５０である。圧縮関数３５０に対する２ａビットの入力Ｘがａビットずつに分割されそれぞれが２つのメッセージスケジュール部（ＭＳ部）３５１，３５２に入力され、これらの２つのメッセージスケジュール部（ＭＳ部）３５１，３５２の中間出力が１つの連鎖値（ＣＶ）処理部３５３に入力される。
【０１２７】
図２５に示す２つのメッセージスケジュール部（ＭＳ部）３５１，３５２の内部置換の繰り返し回数は、連鎖値（ＣＶ）処理部３５３の内部置換の繰り返し回数の半分として設定されている。
【０１２８】
メッセージスケジュール部（ＭＳ部）３５１は偶数番目の置換を取り除き、メッセージスケジュール部（ＭＳ部）３５２は奇数番目の置換を取り除いて、２つのメッセージスケジュール部（ＭＳ部）３５１，３５２の内部置換の繰り返し回数を半分としている。この構成により、メッセージ処理に必要とされる演算が半減できる。
【０１２９】
この図２５に示す圧縮関数３５０は、図２４に示す圧縮関数３４０の構成に比べて処理が削減されることになりソフトウェア処理の向上が期待できる。メッセージスケジュール部（ＭＳ部）３５１，３５２で互い違いに関数を削除することで、ハードウェア実装時に同時に処理をすることが可能な置換を２つに設定でき、小さな回路規模で処理を実現することが可能というハードウェアの小型化を実現できるメリットがある。
【０１３０】
さらに図２６に示す圧縮関数３６０は、図２５と同様、入力ビットが３ａビットに拡大された圧縮関数３６０である。圧縮関数３６０に対する２ａビットの入力Ｘがａビットずつに分割されそれぞれが２つのメッセージスケジュール部（ＭＳ部）３６１，３６２に入力され、これらの２つのメッセージスケジュール部（ＭＳ部）３６１，３６２の中間出力が１つの連鎖値（ＣＶ）処理部３６３に入力される。
【０１３１】
図２６に示す圧縮関数３６０における連鎖値（ＣＶ）処理部３６３は、図２５に示す圧縮関数３５０における連鎖値（ＣＶ）処理部３５３の最前段に内部置換部３６４を１つ追加した構成であり、内部置換の繰り返し数を一つ追加した構成である。
【０１３２】
図２６に示す圧縮関数３６０では、連鎖値（ＣＶ）処理部３６３用の全体置換のはじめに内部置換が一つ分追加されている。この変更に伴い、上側のメッセージスケジュール部（ＭＳ部）３６１の入力値が連鎖値（ＣＶ）処理部３６３の入力値に排他的論理和される構成になっている。
【０１３３】
本構成の特徴は、片方のメッセージスケジュール部（ＭＳ部）に着目した時に、連鎖値（ＣＶ）処理部３６３に供給される中間データが必ず連鎖値（ＣＶ）処理部３６３の２つの置換関数ごとになっている点である。この構成により上下のメッセージスケジュール部（ＭＳ部）３６１，３６２からの影響が均等に連鎖値（ＣＶ）処理部３６３の系列に作用しバランスのとれた攪拌が可能となる。この結果、安全性評価が容易になるというメリットがある。
【０１３４】
［１２．ＣＶ処理部のサイズ拡大法］
図２７に示す圧縮関数３７０は、先に図１５を参照して説明した２系列の圧縮関数のメッセージスケジュール部の共有を行った構成を示したものである。図１５で提示した定義域拡大法のｂ＝ａとした場合に適用することで、連鎖値（ＣＶ）処理部のサイズを拡大している。
【０１３５】
図２７に示す圧縮関数３７０は、メッセージ［Ｘ］の構成ビットであるａビットをメッセージスケジュール部（ＭＳ部）３７１に入力し、中間値としての２つの連鎖値（ＣＶ）であるａビットをそれぞれ連鎖値（ＣＶ）処理部３７２，３７３に入力する。
【０１３６】
メッセージスケジュール部（ＭＳ部）３７１は、中間出力付き置換関数によって構成される。２つの連鎖値（ＣＶ）処理部３７２，３７３は、付加入力付き置換関数によって構成される。メッセージスケジュール部（ＭＳ部）３７１の中間出力は、２つの連鎖値（ＣＶ）処理部３７２，３７３の付加入力として設定される。メッセージスケジュール部（ＭＳ部）３７１の中間出力は、２つの連鎖値（ＣＶ）処理部３７２，３７３各々において、入力または中間値と排他的論理和演算されて内部置換部に入力される。あるいは出力値の生成に利用する。
【０１３７】
［１３．ＣＶ処理部とＭＳ部のサイズ拡大法］
図２８に示す圧縮関数３８０は、図２７に示す圧縮関数３７０の変形例であり、先に、図２４を参照して説明した圧縮関数３４０と同様の手法で、圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例である。図２８に示す圧縮関数３８０は、入力ビットが３ａビットに拡大された圧縮関数である。この図２８に示す圧縮関数３８０は、２つのメッセージスケジュール部（ＭＳ部）３８１，３８２と、２つのメッセージスケジュール部（ＭＳ部）３８１，３８２の出力の排他的論理和演算（ＸＯＲ）結果を入力する１つの連鎖値（ＣＶ）処理部３８３，３８４を有する。
【０１３８】
２つのメッセージスケジュール部（ＭＳ部）３８１，３８２は、中間出力付き置換関数によって構成される。２つの連鎖値（ＣＶ）処理部３８３，３８４は、付加入力付き置換関数によって構成される。メッセージスケジュール部（ＭＳ部）３８１の中間出力は、連鎖値（ＣＶ）処理部３８３の付加入力として設定される。メッセージスケジュール部（ＭＳ部）３８２の中間出力は、連鎖値（ＣＶ）処理部３８４の付加入力として設定される。２つの連鎖値（ＣＶ）処理部３８３，３８４は、付加入力を入力または中間値と排他的論理和演算して内部置換部に入力、あるいは出力値の生成に利用する。
【０１３９】
［１４．定義域拡大法用の攪拌関数Ｆの構成法］
中間出力付き置換関数と、付加入力付き置換関数の組み合わせによって攪拌関数Ｆを構成することも可能である。図２９は、２つの中間出力付き置換関数と、２つの付加入力付き置換関数の組み合わせによって構成した攪拌関数Ｆ３９０の構成例である。
【０１４０】
攪拌関数Ｆ３９０は、２つのメッセージスケジュール部（ＭＳ部）３９１，３９２と、２つのメッセージスケジュール部（ＭＳ部）３９１，３９２の出力の排他的論理和演算（ＸＯＲ）結果を入力する１つの連鎖値（ＣＶ）処理部３９３，３９４を有する。
【０１４１】
２つのメッセージスケジュール部（ＭＳ部）３９１，３９２は、中間出力付き置換関数によって構成される。２つの連鎖値（ＣＶ）処理部３９３，３９４は、付加入力付き置換関数によって構成される。
【０１４２】
メッセージスケジュール部（ＭＳ部）３９１の中間出力は、連鎖値（ＣＶ）処理部３９３の付加入力として設定される。メッセージスケジュール部（ＭＳ部）３９２の中間出力は、連鎖値（ＣＶ）処理部３９４の付加入力として設定される。２つの連鎖値（ＣＶ）処理部３９３，３９４は、付加入力を入力または中間値と排他的論理和演算して内部置換部に入力、あるいは出力値の生成に利用する。
【０１４３】
攪拌関数Ｆ３９０は、入力［Ｙ］として２ａビットを入力し、２ａビットの出力［Ｚ］を生成して出力する。なお、本発明のデータ変換装置内部置換については、先に説明した図２５、図２６の構成と同様、一部を削減した構成としてもよい。
【０１４４】
［１５．拡散性能の高い置換処理実現方法］
メッセージスケジュール部（ＭＳ部）や、連鎖値（ＣＶ）処理部に適用する置換関数は、上述したように、比較的単純な置換関数としての内部置換を繰り返し適用して実現できる。このような比較的単純な置換関数を繰り返し適用することで攪拌性能を高めた置換関数が構成できる。
【０１４５】
内部置換として利用できる置換関数の具体的構成例について、図３０を参照して説明する。図３０は、攪拌性能の高い繰り返し型置換関数を構成するため、全体置換を実行する置換関数の内部で利用される内部置換としての置換関数の構成例である。この内部置換が繰り返し連結されて適用されることで全体置換が構成される。図３０の内部置換処理部（置換関数）４１０は、２５６ビット入出力の置換を行う構成を示している。
【０１４６】
内部置換処理部（置換関数）４１０に入力する２５６ビットのデータは３２バイトのデータとして表わされる。各バイトは、図に示す一本の入力データ線に対応する。
【０１４７】
まず左から４バイト（３２ビット）単位でデータを区切り、８つのグループ（Ｇ１〜Ｇ８）に分けて考える。初めに左から奇数番目にあるグループ（Ｇ１，Ｇ３，Ｇ５，Ｇ７）に含まれる４バイトデータに対して、それぞれ対応する非線形変換部４１１において非線形変換処理を行う。
【０１４８】
これら４つのグループ（Ｇ１，Ｇ３，Ｇ５，Ｇ７）の各４バイト（３２ビット）データは、非線形変換部４１１から出力されると、排他的論理和（ＸＯＲ）演算部４１２において、それぞれ右隣にあるグループのバイト単位データとの排他的論理和演算を実行して、偶数番目の４つのグループ（Ｇ２，Ｇ４，Ｇ６，Ｇ８）の各４バイト（３２ビット）データを更新する。
【０１４９】
すなわち、
グループ（Ｇ１）の４バイトデータの非線形変換結果データと、グループ（Ｇ２）の入力データとの排他的論理和演算を実行する。
グループ（Ｇ３）の４バイトデータの非線形変換結果データと、グループ（Ｇ４）の入力データとの排他的論理和演算を実行する。
グループ（Ｇ５）の４バイトデータの非線形変換結果データと、グループ（Ｇ６）の入力データとの排他的論理和演算を実行する。
グループ（Ｇ７）の４バイトデータの非線形変換結果データと、グループ（Ｇ８）の入力データとの排他的論理和演算を実行する。
これらの処理により、偶数番目の４つのグループ（Ｇ２，Ｇ４，Ｇ６，Ｇ８）の各４バイト（３２ビット）データを更新する。
【０１５０】
次に、スワップ処理部４１３において、１バイト単位の各データのスワップ処理を行う。
非線形変換部４１１から出力されたデータからなる４つのグループ（Ｇ１，Ｇ３，Ｇ５，Ｇ７）のデータは、各グループ単位で左端のグループは右端のグループの位置に、それ以外のグループは一つ左のグループのあった位置に移動する。
すなわち、
グループ（Ｇ１）は出力グループ（Ｇｏｕｔ８）の位置に出力、
グループ（Ｇ３）は出力グループ（Ｇｏｕｔ２）の位置に出力、
グループ（Ｇ５）は出力グループ（Ｇｏｕｔ４）の位置に出力、
グループ（Ｇ７）は出力グループ（Ｇｏｕｔ６）の位置に出力、
このような対応でスワップ処理を実行して出力する。
【０１５１】
一方、排他的論理和（ＸＯＲ）演算部４１２において、排他的論理和演算を実行して更新された偶数番目の４つのグループ（Ｇ２，Ｇ４，Ｇ６，Ｇ８）の各４バイト（３２ビット）データは、バイト単位で分割されてそれぞれが異なるグループに移動するスワップ処理を行う。
【０１５２】
グループ（Ｇ２）の４バイトデータに対しては以下のようなスワップ処理が行われる。
グループ（Ｇ２）の４バイトデータを１バイト単位で先頭からＡＢＣＤとする。
グループ（Ｇ２）の１番目の１バイトデータＡは、出力グループ（Ｇｏｕｔ１）の１番目の１バイトデータとして出力、
グループ（Ｇ２）の２番目の１バイトデータＢは、出力グループ（Ｇｏｕｔ３）の２番目の１バイトデータとして出力、
グループ（Ｇ２）の３番目の１バイトデータＣは、出力グループ（Ｇｏｕｔ５）の３番目の１バイトデータとして出力、
グループ（Ｇ２）の４番目の１バイトデータＤは、出力グループ（Ｇｏｕｔ７）の４番目の１バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【０１５３】
グループ（Ｇ４）の４バイトデータに対しては以下のようなスワップ処理が行われる。
グループ（Ｇ４）の４バイトデータを１バイト単位で先頭からＥＦＧＨとする。
グループ（Ｇ４）の１番目の１バイトデータＥは、出力グループ（Ｇｏｕｔ３）の１番目の１バイトデータとして出力、
グループ（Ｇ４）の２番目の１バイトデータＦは、出力グループ（Ｇｏｕｔ５）の２番目の１バイトデータとして出力、
グループ（Ｇ４）の３番目の１バイトデータＧは、出力グループ（Ｇｏｕｔ７）の３番目の１バイトデータとして出力、
グループ（Ｇ４）の４番目の１バイトデータＨは、出力グループ（Ｇｏｕｔ１）の４番目の１バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【０１５４】
グループ（Ｇ６）の４バイトデータに対しては以下のようなスワップ処理が行われる。
グループ（Ｇ６）の４バイトデータを１バイト単位で先頭からＩＪＫＬとする。
グループ（Ｇ６）の１番目の１バイトデータＩは、出力グループ（Ｇｏｕｔ５）の１番目の１バイトデータとして出力、
グループ（Ｇ６）の２番目の１バイトデータＪは、出力グループ（Ｇｏｕｔ７）の２番目の１バイトデータとして出力、
グループ（Ｇ６）の３番目の１バイトデータＫは、出力グループ（Ｇｏｕｔ１）の３番目の１バイトデータとして出力、
グループ（Ｇ６）の４番目の１バイトデータＬは、出力グループ（Ｇｏｕｔ３）の４番目の１バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【０１５５】
グループ（Ｇ８）の４バイトデータに対しては以下のようなスワップ処理が行われる。
グループ（Ｇ８）の４バイトデータを１バイト単位で先頭からＭＮＯＰとする。
グループ（Ｇ８）の１番目の１バイトデータＭは、出力グループ（Ｇｏｕｔ７）の１番目の１バイトデータとして出力、
グループ（Ｇ８）の２番目の１バイトデータＮは、出力グループ（Ｇｏｕｔ１）の２番目の１バイトデータとして出力、
グループ（Ｇ８）の３番目の１バイトデータＯは、出力グループ（Ｇｏｕｔ３）の３番目の１バイトデータとして出力、
グループ（Ｇ８）の４番目の１バイトデータＰは、出力グループ（Ｇｏｕｔ５）の４番目の１バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【０１５６】
なお、次のラウンドの内部置換処理部（置換関数）においては、出力グループ（Ｇｏｕｔ１，Ｇｏｕｔ３，Ｇｏｕｔ５，Ｇｏｕｔ７）が非線形変換に入力される。
【０１５７】
このように、入出力を入れ替えるスワップ処理を実行することで各バイト単位データのが各ラウンドにおいて異なる種類の変換処理が実行されることになることが保証される。
【０１５８】
図３０に示す内部置換処理部（置換関数）４１０の出力部に記載したように、３２バイトの出力をｘ１〜ｘ３２とする。例えば、図２２に示す中間出力付き置換関数における中間出力は、これらの出力に相当する。すなわち、図２３〜図２７を参照して説明した圧縮関数または攪拌関数Ｆの各構成におけるメッセージスケジュール部（ＭＳ部）は、中間出力付き置換関数によって構成されるが、これらのメッセージスケジュール部（ＭＳ部）の出力する中間出力に相当する。
【０１５９】
この中間出力は、図２１に示す付加入力付き置換関数における付加入力として入力される。例えば、図２３〜図２７を参照して説明した圧縮関数または攪拌関数Ｆの各構成における連鎖値（ＣＶ）処理部は、付加入力付き置換関数によって構成されるが、これらの連鎖値（ＣＶ）処理部の付加入力として、図３０に示す内部置換処理部（置換関数）４１０の出力部の３２バイト出力：ｘ１〜ｘ３２が入力される。
【０１６０】
なお、図３０に示す内部置換処理部（置換関数）４１０の構成は、図２３〜図２７を参照して説明したように、圧縮関数や攪拌関数Ｆの内部に多数設定されることになる。この内部置換処理部（置換関数）の生成する中間データのすべての出力値ｘ１〜ｘ３２を利用する設定としてもよいし、一部のみを利用する設定としてもよい。
【０１６１】
例えば、図３０に示す内部置換処理部（置換関数）４１０の構造に着目して非線形変換部４１１の出力側ｘ５〜ｘ８、ｘ１３〜ｘ１６、ｘ２１〜ｘ２４、ｘ２９〜ｘ３２のみを中間出力として利用する構成としてもよい。あるいは、逆に次の置換関数で非線形変換部に入力されるｘ１〜ｘ４、ｘ９〜ｘ１２、ｘ１７〜ｘ２０、ｘ２５〜ｘ２８のみを中間値として利用する構成としてもよい。
【０１６２】
次に図３０を参照して説明した内部置換処理部（置換関数）４１０内に構成される非線形変換部４１１の内部構成の一例について図３１を参照して説明する。非線形変換部４１１は４バイトのデータを受け取り、４バイトのデータを出力する置換関数として構成可能である。
【０１６３】
図３１に示す非線形変換部４１１は４バイトデータを入力する。図３１に示す１本のラインが１バイトデータに相当する。入力されたデータは、排他的論理和（ＸＯＲ）演算部４２１において、非線形変換部４１１ごとにあらかじめ定められた４つのコンスタント値（定数）Ｃ１，Ｃ２，Ｃ３，Ｃ４とそれぞれ排他的論理和される。なお、図３０を参照して説明した内部置換処理部（置換関数）４１０内に構成される非線形変換部４１１は４つあるが、これらの４つの非線形変換部にはそれぞれ異なるコンスタント値（定数）が設定される。このコンスタント値（定数）設定処理については後述する。
【０１６４】
排他的論理和（ＸＯＲ）演算部４２１において、非線形変換部４１１ごとにあらかじめ定められた４つのコンスタント値（定数）Ｃ１，Ｃ２，Ｃ３，Ｃ４とそれぞれ排他的論理和されたデータは、次に小非線形変換部４２２において、１バイト入出力の非線形変換処理が実行される。
【０１６５】
小非線形変換部４２２の出力は、線形変換部４２３に入力されて、線形変換が施されて出力される。なおここで説明した小非線形変換部４２２は、Ｓ−ｂｏｘと呼ばれることがあり、２５６個の１バイトデータの変換テーブルとして表現することが可能である。また線形変換部４２３は、入力データに対する線形変換行列（Ｍ）を適用した変換処理によって出力データを算出する処理として実行される。線形変換行列（Ｍ）は、拡散行列とも呼ばれＧＦ（２８）の要素を持つ４ｘ４の行列として表現されることがある。
【０１６６】
なお、置換関数はあるデータがなるべく多くのデータに影響すると同時に、入出力に含まれる非ゼロ要素の総和ができるだけ低い水準にならないことも求められている。これは、解析困難性を高め、脆弱性を排除するために有効である。具体的には差分攻撃や線形攻撃に対しての対策となる。
【０１６７】
図３０に示す内部置換処理部（置換関数）４１０の構成は、図２３〜図２７を参照して説明したように、圧縮関数や攪拌関数Ｆの内部に多数設定されることになる。すなわち、図３０に示す内部置換処理部（置換関数）４１０を複数ラウンド繰り返した処理が行われることになる。
【０１６８】
暗号アルゴリズムにおいても、同一の置換処理構成を複数ラウンド繰り返すラウンド演算を実行する構成としたものが多いが、全てのラウンドにおいて適用する線形変換行列［Ｍ］を１つの固定行列とするのではなく複数の異なる行列、例えば２つの行列［Ｍ１］，［Ｍ２］を利用する、いわゆるＤＳＭ（Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）を適用することが脆弱性に対する対策として有効であることが知られている。なお、ＤＳＭを適用した暗号アルゴリズムについては、例えば本出願人と同一の特許出願である特開２００７−１９９１５６などに記載されている。
【０１６９】
このＤＳＭによる脆弱性の改善効果は、ハッシュ関数においても効果があると考えられる。すなわち、全てのラウンドにおいて適用する線形変換行列［Ｍ］を１つの固定行列とするのではなく複数の異なる行列を利用することでランダム関数との区別を出来にくくすることが可能となり、様々な解析処理に対する困難性を高めることが可能となる。
【０１７０】
圧縮関数や攪拌関数Ｆの内部に多数設定される図３０に示す内部置換処理部（置換関数）４１０の非線形変換部４１１において利用する線形変換行列［Ｍ］に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を図３２に示す。
【０１７１】
図３２は圧縮関数や攪拌関数Ｆの内部に多数設定される図３０に示す内部置換処理部（置換関数）を２ラウンド分の結合構成を簡略化して表した図である。内部置換処理部（置換関数）４４０は、図３０に示す内部置換処理部（置換関数）４１０と同様の構成である。内部置換処理部（置換関数）４５０は次の内部置換を実行するラウンドを示している。入力の各ラインは４バイトデータに相当する。
【０１７２】
内部置換処理部（置換関数）４４０は、図３０に示す内部置換処理部（置換関数）４１０と同様、非線形変換部４４１、排他的論理和演算（ＸＯＲ）部４４２、スワップ処理部４４３を有する。非線形変換部４４１は、図３１を参照して説明した構成を有する。
【０１７３】
非線形変換部４４１は、図３１を参照して説明したように、排他的論理和演算部と、小非線形変換部と線形変換部を有する。線形変換部は、線形変換行列Ｍを適用した線形変換処理を実行する。
【０１７４】
図３２では、非線形変換部４４１として設定される４バイトデータ単位の非線形変換処理部を４つ示しているが、これらは、それぞれ図３１を参照して説明した構成を有する。この４つの非線形変換部内の線形変換部において適用する線形変換行列Ｍを、図３２では、左からそれぞれＭ１，Ｍ２，Ｍ３，Ｍ４として示している。線形変換行列Ｍ１，Ｍ２，Ｍ３，Ｍ４はそれぞれ異なる線形変換行列である。
【０１７５】
各ラウンドの、内部置換処理部（置換関数）４４０，４５０は同じ構成を有している。すなわち、内部置換処理部（置換関数）４４０，４５０のいずれも、４つの非線形変換部内の線形変換部において適用する線形変換行列Ｍは、左からそれぞれＭ１，Ｍ２，Ｍ３，Ｍ４である。このように内部置換では同じ行列が同じ位置で用いられている。
【０１７６】
図３２に示すラウンド間を接続するライン（太線）から理解されるように、上段のラウンドの内部置換処理部（置換関数）４４０内の非線形変換の出力は下段のラウンドの内部置換処理部（置換関数）４５０の１つの非線形変換の出力と排他的論理和されている。
【０１７７】
例えば上段のラウンドの内部置換処理部（置換関数）４４０内の非線形変換部４４１の左端の線形変換行列Ｍ１を持つ非線形変換部４４１ａの出力（図中の出力Ａ）は、下段のラウンドの内部置換処理部（置換関数）４５０内の非線形変換部４５１の右端の線形変換行列Ｍ４を持つ非線形変換部４５１ｄの出力（図中の出力Ｂ）と、排他的論理和演算部４５２において、排他的論理和されている。この結果の出力が図に示す出力Ｃである。
【０１７８】
上段のラウンドの内部置換処理部（置換関数）４４０内の非線形変換部４４１の４つの非線形変換部の出力は、いずれも、下段のラウンドの内部置換処理部（置換関数）４５０内の非線形変換部４５１の４つの非線形変換部の出力のいずれかと排他的論理和演算がなされている。
【０１７９】
上下の各ラウンドの排他的論理和演算のなされる非線形変換部４４１の出力と、非線形変換部４５１の出力との組み合わせを各非線形変換部内の線形変換行列［Ｍ］の組み合わせとして示すと以下のようになる。
（１）Ｍ１とＭ４（非線形変換部４４１ａと４５１ｄ）
（２）Ｍ２とＭ１（非線形変換部４４１ｂと４５１ａ）
（３）Ｍ３とＭ２（非線形変換部４４１ｃと４５１ｂ）
（４）Ｍ４とＭ３（非線形変換部４４１ｄと４５１ｃ）
【０１８０】
この様に、異なる線形変換行列を適用した線形変換処理の実行結果を相互作用させる構成とすることで、上述のＤＳＭ（Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）の適用構成を実現でき、解析困難性を高めることができる。
【０１８１】
なお、２つの行列の連結を記号｜を利用して表すとして、上述の（１）〜（４）の行列ペアＭ１｜Ｍ４、Ｍ２｜Ｍ１、Ｍ３｜Ｍ２、Ｍ４｜Ｍ３これらの連結行列の分岐数が高くなる（例えば３以上）となる設定とした行列を選択して利用する構成とすれば、さらに解析困難性を高めることが可能である。またはそれぞれの逆行列を転置して得られる行列を並べて得られる行列ｔＭ１−１｜ｔＭ４−１，ｔＭ２−１｜ｔＭ１−１，ｔＭ３−１｜ｔＭ２−１，ｔＭ４−１｜ｔＭ３−１の分岐数を３以上とする構成である。
【０１８２】
このように分岐数を高くする構成にすることで差分攻撃や線形攻撃に対する耐性を向上させることが可能である。
【０１８３】
このように、繰り返しラウンド演算として実行する内部置換処理部（置換関数）内の非線形変換部に設定される線形変換行列は、ＤＳＭ構成を採用して異なる行列を利用した構成とすることが好ましい。また、利用する行列は、相互に影響しあう行列のペアの連結行列の分岐数が高くなるような行列に設定する構成とすることが好ましい。
【０１８４】
なお、図３２を参照した説明では、４つの行列を用いて説明を行ったが、同じ分岐数の条件を満たすためには２つの行列でも実現可能である。例えば、Ｍ１｜Ｍ２の分岐数が３以上、また逆行列を転置して得られる行列を並べて得られる行列ｔＭ１−１｜ｔＭ２−１の分岐数が３以上として図３３に示す構成のように行列配置を行なう構成としてもよい。
【０１８５】
図３３に示す構成において、上下の各ラウンドの排他的論理和演算のなされる非線形変換部４４１の出力と、非線形変換部４５１の出力との組み合わせを各非線形変換部内の線形変換行列［Ｍ］の組み合わせとして示すと以下のようになる。
（１）Ｍ１とＭ２（非線形変換部４６１ａと４７１ｄ）
（２）Ｍ２とＭ１（非線形変換部４６１ｂと４７１ａ）
（３）Ｍ１とＭ２（非線形変換部４６１ｃと４７１ｂ）
（４）Ｍ２とＭ１（非線形変換部４６１ｄと４７１ｃ）
【０１８６】
この図３３に示す構成は、実装上の観点からは行列に必要なハードウェア回路やメモリ上のテーブルサイズを削減できることからさらに望ましい構成であると言える。
【０１８７】
この様に、異なる線形変換行列を適用した線形変換処理の実行結果を相互作用させる構成とすることで、上述のＤＳＭ（Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）の適用構成を実現でき、解析困難性を高めることができる。
【０１８８】
以上、攪拌性能を高めた全体関数を実現するための内部置換の構成例について説明した。なお、上述の処理例は２５６ビット入力の例として説明したが、これは、一例であり、データサイズは様々な設定が可能であり、データサイズに応じた構成とすることは可能である。その場合小非線形変換部の入出力サイズ、線形変換部もサイズに対応した処理を行う設定とする。
【０１８９】
［１６．独立性の高い出力をもつ置換関数の生成法］
上述した処理例では、圧縮関数や攪拌関数Ｆの内部に多数設定される内部置換処理構成は、例えば、図３０に示す内部置換処理構成を用い、この同一構成を複数回繰り返す設定とした処理例として説明した。この内部置換処理の非線形変換部内の線形変換処理行列を上記のように構成することなどによって解析困難性を高めることができる。
【０１９０】
さらに複数の全体置換関数を必要とする構成においては、置換同士が独立にふるまうような複数の全体置換を利用することで解析困難性を高める場合がある。その場合、それら全体置換に含まれる内部置換を異なるものとすることにより実現する方法がある。その構成例を説明する。
【０１９１】
複数の異なる全体置換処理を実現するためには、それぞれの全体置換内の内部置換に含まれる部品を変化させる手法が有効である。しかしながら実装効率や、安全性評価処理の容易性の観点から、異なる部品を多数利用することは必ずしも望ましいことではない。できる限り利用部品を少なくして多様な処理を実現することが好ましい。
【０１９２】
全体置換ごとに異なる内部置換処理とするための構成としては、例えば以下のような構成が考えられる。
＊全体置換ごとに利用されるコンスタント値（図３１の排他的論理和演算部４２１で利用）を別のものに置き換える変更をする。
＊全体置換に含まれる内部置換処理の部品である非線形変換部としてのＳ−ｂｏｘ（図３１の小非線形変換部４２２）や線形変換行列（図３１の線形変換部４２３）を異なるものしそれを繰り返し利用して全体置換とする。
【０１９３】
なお、コンスタント値は、図３０、図３１を参照して説明した内部置換処理部４１０の非線形変換部４１１の排他的論理和（ＸＯＲ）演算部４２１において入力する定数である。
【０１９４】
しかし、全体置換ごとのコンスタント値の全面的な変更や、Ｓ−ｂｏｘや行列などの変更を行うためには、これらの異なるデータの供給や部品構成が必要となり、回路やメモリ容量を増大させることか必要となる。このような回路やメモリ容量を増大させることは実装上のデメリットであり、また安全性の再評価コストが高くなってしまう。という問題がある。
【０１９５】
そこで、本発明では、以下のような構成により、全体置換ごとの内部置換処理構成を異なる設定とする。
（ａ）複数の異なる小非線形演算（Ｓ−ｂｏｘ）（図３１の小非線形変換部４２２）が利用されている場合は、内部置換の小非線形演算（Ｓ−ｂｏｘ）を全体置換ごとに入れ替える
（ｂ）線形変換部（図３１の線形変換部４２３）として利用される行列を、１つの行列から生成する複数の異なる行列に設定して、内部置換の行列を全体置換ごと異なる行列を設定する。例えば、行の入れ替えや列の入れ替えを行うことで１つの行列から複数の異なる行列を生成する。
（ｃ）線形変換部（図３１の線形変換部４２３）として利用される行列に複数種類の行列が利用されている場合は、内部置換の行列を全体置換ごとに入れ替える。（前述のＤＳＭを利用した場合などはＤＳＭの条件を崩さない範囲で変更する）
（ｄ）上記の（ａ）〜（ｃ）のいずれかの組み合わせ
【０１９６】
上記の（ａ）〜（ｄ）のような設定として繰り返し実行される内部置換処理における置換処理構成を効率的に変更することができる。すなわち、回路規模やメモリ容量を大きく増大させることなく、異なる置換処理を実行させることが可能となる。
【０１９７】
特に、上記の（ｃ）と（ｂ）の組み合わせとすれば効率的に異なる全体置換を実現させることができる。すなわち、上述したＤＳＭ構成を適用して２種類以上の線形変換行列がメモリに格納されている場合、これらの行列の行や列を入れ替えて新たな行列を生成して、線形変換行列として利用する構成とする。このような設定とすれば、少ないデータに基づいて効率的に異なる線形変換処理を行うことができる。
【０１９８】
なお、ＤＳＭを利用し、複数の異なる線形変換行列を備えた構成において、行列の行や列の入れ替え処理を行った場合の安全性の評価が問題になるが、行列として所定の規則を持つ行列、例えば、ｃｉｒｃｕｌａｎｔ  ｍａｔｒｉｘやＨａｄａｍａｒｄ−ｍａｔｒｉｘを使用すれば、行や列の入れ替えによって生成される行列を適用しても安全性評価に影響を与えないことが分かっている。従って、安全性評価は容易であり、簡便な変更で異なる置換関数を作り出す有効な手段であると言える。
【０１９９】
［１７．置換関数に適用するコンスタントの生成処理］
先に説明したように、各ラウンドの置換処理構成を異なる設定とする１つの手法として、各ラウンド単位または複数ラウンド単位でコンスタント（図３１の排他的論理和演算部４２１で利用する［Ｃ］）を別のものに置き換える変更をする手法が有効であることは先に説明した。
【０２００】
しかし、多数のラウンド数に対応するコンスタントを保持するためには大きなメモリ容量が必要となる。以下では、少ない数のコンスタントから、多数の異なるコンスタントを効率的に生成して、置換関数で使用可能とした構成例について説明する。
【０２０１】
はじめに置換関数に必要とされるコンスタントを定義する。ここでは４バイトをまとめて１ワードと呼ぶこととする。例えば図３０示す内部置換処理部（置換関数）４１０には４つの非線形変換部があり、各非線形変換部の構成は、図３１に示す構成を有する。図３１に示すように、１つの非線形変換部４１１には４つのコンスタントを利用する。各コンスタントは、１バイト入力データとの排他的論理和演算に使用されるので、１つのコンスタントＣｎは１バイトデータである。１つの非線形変換部４１１には４つのコンスタントを利用するので、１つの非線形変換当たり１ワードのコンスタントが必要となる。
【０２０２】
図３０示す内部置換処理部（置換関数）４１０には４つの非線形変換部があるので、１つの内部置換処理のために、４ワードのコンスタントが必要となる。この基本置換をｋ回繰り返して全体置換を構成する場合には合計４ｋワードのコンスタントが必要となる。
【０２０３】
ここでｋ個の内部置換のうち、入力側から数えてｉ番目の内部置換に含まれるｊ番目のコンスタント値をＣｉ，ｊで表す。すると、１つの全体置換で必要とされるコンスタントは以下のように書き表すことができる。
（一つの全体置換で必要とされるコンスタントの集合の例）
１番目の内部置換：Ｃ１，１，Ｃ１，２，Ｃ１，３，Ｃ１，４
２番目の内部置換：Ｃ２，１，Ｃ２，２，Ｃ２，３，Ｃ２，４
３番目の内部置換：Ｃ３，１，Ｃ３，２，Ｃ３，３，Ｃ３，４
４番目の内部置換：Ｃ４，１，Ｃ４，２，Ｃ４，３，Ｃ４，４
：
ｋ−１番目の内部置換：Ｃｋ−１，１，Ｃｋ−１，２，Ｃｋ−１，３，Ｃｋ−１，４
ｋ番目の内部置換：Ｃｋ，１，Ｃｋ，２，Ｃｋ，３，Ｃｋ，４
【０２０４】
コンスタントの生成手法を開示した従来技術としては、例えば特開２００８−５８８２７に開示された技術がある。この従来技術は、６４ビットのコンスタントを生成するために、８ビットの変数に格納された値を８回利用して作り出し、さらに次のコンスタントを生成するためには変数内の値をＧＦ（２８）上の要素とみなしてｘ倍またはｘ−１倍の演算を施すことで順次データの種類を増やしながら生成するという方法である。なおここで用いるｘとは利用する有限体ＧＦ（２ｎ）を定義する既約多項式を多項式ｆ（ｘ）で表現した際の変数ｘである。
【０２０５】
以下、コンスタント生成処理構成として、一部のコンスタントをコンスタント生成用データに対するｘ倍の演算によって得られる系列に基いて生成し、残りはｘ−１倍の演算によって得られる系列に基づいて生成する方法について説明する。この方法により生成の手間を上げずにコンスタント値同士のシンプルな関係を局所的に崩すことが可能となる。その結果、コンスタントの乱雑性を上げることができる。本例では２つのワードに相当する６４ビット分を１つの１６ビット値から作り出す例を用いて説明する。
【０２０６】
本発明に従ったコンスタント生成処理について、上記の従来技術（特開２００８−５８８２７）に開示されたコンスタント生成処理について対比しながら説明する。
【０２０７】
まず、従来のコンスタント生成手順について説明する。従来のコンスタント生成手順は以下の通りである。
［１］１６ビットの変数Ｓにそれぞれ初期値を格納する
［２］ｉ＝１...ｋに対して以下の処理を行う
（２．１）Ｃｉ，１＝（Ｓ  ｘｏｒ  Ｍａｓｋ１）＜＜＜Ｒｏｔ１｜（Ｓ  ｘｏｒ  Ｍａｓｋ２）＜＜＜Ｒｏｔ２
Ｃｉ，２＝（Ｓ  ｘｏｒ  Ｍａｓｋ３）＜＜＜Ｒｏｔ３｜（Ｓ  ｘｏｒ  Ｍａｓｋ４）＜＜＜Ｒｏｔ４
Ｃｉ，３＝（Ｓ  ｘｏｒ  Ｍａｓｋ５）＜＜＜Ｒｏｔ５｜（Ｓ  ｘｏｒ  Ｍａｓｋ６）＜＜＜Ｒｏｔ６
Ｃｉ，４＝（Ｓ  ｘｏｒ  Ｍａｓｋ７）＜＜＜Ｒｏｔ７｜（Ｓ  ｘｏｒ  Ｍａｓｋ８）＜＜＜Ｒｏｔ８
［２．２］Ｓ←Ｓ・ｘ
【０２０８】
なお、Ｍａｓｋｎ，Ｒｏｔｎは別途定められた定数である。なお、ここで記号｜はビットの連結を示している。（Ａ  ｘｏｒ  Ｂ）はＡとＢの排他的論理和演算（ＸＯＲ）処理を示している。
【０２０９】
このように生成された４つのコンスタント（Ｃｉ，１〜Ｃｉ，４）は一見乱数のように見える場合があるが、マスク演算とローテーションシフト演算のみで変化させているだけであるのでＳがどんな値であろうともコンスタントの間には常にある特定の線形演算で表現される関係が維持される特徴がある。ブロック暗号の例からもわかるように線形変換のみでは乱雑性を上げることが不十分な場合が多く、できるだけ非線形な性質があった方が望ましい。
【０２１０】
次に、実装コストをあげず、パフォーマンスを低下させることなくコンスタント間に非線形な関係を導入して本発明に従ったコンスタント生成手法について以下説明する。
［１］１６ビットの変数Ｓ，Ｔにそれぞれ初期値を格納する
［２］ｉ＝１...ｋに対して以下の処理を行う
（２．１）Ｃｉ，１＝（Ｓ  ｘｏｒ  Ｍａｓｋ１）＜＜＜Ｒｏｔ１｜（Ｓ  ｘｏｒ  Ｍａｓｋ２）＜＜＜Ｒｏｔ２
Ｃｉ，２＝（Ｓ  ｘｏｒ  Ｍａｓｋ３）＜＜＜Ｒｏｔ３｜（Ｓ  ｘｏｒ  Ｍａｓｋ４）＜＜＜Ｒｏｔ４
Ｃｉ，３＝（Ｔ  ｘｏｒ  Ｍａｓｋ５）＜＜＜Ｒｏｔ５｜（Ｔ  ｘｏｒ  Ｍａｓｋ６）＜＜＜Ｒｏｔ６
Ｃｉ，４＝（Ｔ  ｘｏｒ  Ｍａｓｋ７）＜＜＜Ｒｏｔ７｜（Ｔ  ｘｏｒ  Ｍａｓｋ８）＜＜＜Ｒｏｔ８
［２．２］Ｓ←Ｓ・ｘ，  Ｔ←Ｔ・ｘ−１
【０２１１】
上記の処理に従って、１６ビットの変数Ｓ，Ｔを適用して４つのコンスタント（Ｃｉ，１〜Ｃｉ，４）を生成することで、各内部置換に含まれる４つのコンスタントのうち半分はｘ倍の系列となり残り半分はｘ−１倍の系列に属することになる。
【０２１２】
このように構成すれば、Ｓから生成されるコンスタントとＴから構成されるコンスタントの間には一定の線形関係が維持されることがなくなり、独立性が向上するという効果が得られる。
【０２１３】
上記のコンスタント生成処理を一般化して説明すると、ｘａ，ｘｂというように異なる指数を持つ値を用いて、初期値ＳとＴの更新を行う処理であると説明できる。このような変数Ｓ，Ｔを適用して複数のコンスタントを生成することで、生成されるコンスタントのうち半分はｘａ倍の系列となり残り半分はｘｂ倍の系列に属することになる。
【０２１４】
なお、さらにＳ，Ｔの２つの系列だけではなく、初期値が増えることが許容できれば３つ以上の系列を用いてコンスタントを生成する構成も可能である。
【０２１５】
［１８．複数の全体置換に対するコンスタントの生成法］
圧縮関数においては複数の全体置換が存在しており、各全体置換それぞれに対して複数のコンスタントからなるコンスタント値の集合を準備する必要がある。仮に、全体置換の数がｍ個あるとしてそれらをＰ１，Ｐ２，...，Ｐｍで表すとする。前述のコンスタント生成手法を適用すれば、これらの全体置換数ｍに応じて、ｍ組の初期値を全体置換ごとに変更して、全体置換内の内部置換において適用するコンスタント値をそれぞれ生成する方法が適用できる。しかし、このような手法を行うとコンスタント値の生成の手間がｍ倍になり、効率的ではない。
【０２１６】
複数の全体置換に適用するためのコンスタント集合の生成処理を簡素化する手法について以下説明する。例えば圧縮関数内にｍ個の全体置換がある場合、１つ目の全体置換に必要なコンスタントは前述の複数の初期値Ｓ，Ｔを利用した方法により作り出し、２つ目以降の全体置換に適用するコンスタントは、１つ目の全体置換用に生成したコンスタントに対して簡単な演算を施して生成する。
【０２１７】
１つのデータ変換処理構成、例えば圧縮関数内にｍ個の全体置換が設定された構成において、ｘ番目の全体置換の入力側から数えてｉ番目の内部置換に含まれるｊ番目のコンスタント値（ワード）をＣｉ，ｊ（ｘ）で表す。１番目の全体置換用のコンスタントＣｉ，ｊ（１）は、上述の複数の初期値Ｓ，Ｔを利用した方法により生成されているものとする。
【０２１８】
このとき２番目以降の全体置換用のコンスタントＣｉｊ（２），Ｃｉｊ（３），．．，Ｃｉｊ（ｍ）を生成する。図３４を参照して、２番目以降の全体置換用のコンスタントＣｉｊ（２），Ｃｉｊ（３），．．，Ｃｉｊ（ｍ）を生成する手法について説明する。
【０２１９】
図３４には、ｍ個の全体置換に必要とされるコンスタント集合として、上述の複数の初期値Ｓ，Ｔを利用した方法により生成される第１番目のコンスタント集合４８０と、第１番目のコンスタント集合４８０の変換処理によって生成する第２のコンスタント集合４８１、第３のコンスタント集合４８２、第ｍのコンスタント集合４８３を示している。
【０２２０】
ｍ個の全体置換のすべてにおいて、全体置換１つにｋ個の内部置換が含まれ、内部置換１つに４つのコンスタントのワードが必要とされる設定とした例である。
【０２２１】
第２〜第ｍのコンスタント集合は、第１のコンスタント集合４８０に対する変換処理によって生成する。変換処理の具体例について説明する。
【０２２２】
変換処理としては、以下の３種類の変換処理のいずれかを適用することができる。
（変換処理例１）
全体置換ごとに定められた異なるローテーション量をＲｘとし、Ｃｉ，ｊ（ｘ）＝Ｃｉ，ｊ（１）＜＜＜Ｒｘとしてコンスタントを生成する。
Ｃｉ，ｊ（１）は上述の複数の初期値Ｓ，Ｔを利用した方法により生成される第１番目のコンスタント集合４８０の要素としてのコンスタントである。
ｘは、コンスタント集合の識別番号であり、２〜ｍの値をとる。
【０２２３】
（変換処理例２）
全体置換ごとに定められた異なるマスク値（ワード）をＭｘとし、Ｃｉ，ｊ（ｘ）＝Ｃｉ，ｊ（１）  ｘｏｒ  Ｍｘとしてコンスタントを生成する。
Ｃｉ，ｊ（１）は上述の複数の初期値Ｓ，Ｔを利用した方法により生成される第１番目のコンスタント集合４８０の要素としてのコンスタントである。
ｘは、コンスタント集合の識別番号であり、２〜ｍの値をとる。
【０２２４】
（変換処理例３）
上記の変換処理例１，２を組み合わせた方法
Ｃｉ，ｊ（ｘ）＝（Ｃｉ，ｊ（１）＜＜＜Ｒｘ）ｘｏｒ  ＭｘまたはＣｉ，ｊ（ｘ）＝（Ｃｉ，ｊ（１）  ｘｏｒ  Ｍｘ）＜＜＜Ｒｘとしてコンスタントを生成する。
Ｃｉ，ｊ（１）は上述の複数の初期値Ｓ，Ｔを利用した方法により生成される第１番目のコンスタント集合４８０の要素としてのコンスタントである。
ｘは、コンスタント集合の識別番号であり、２〜ｍの値をとる。
【０２２５】
上記変換処理例１〜３のいずれかを適用して、１つのコンスタント集合から複数の異なるコンスタント集合を生成することが可能であり、これらを各全体置換に適用するコンスタントとして設定する。
【０２２６】
なお、上記の変換処理例１の場合にはＣｉ，ｊ（０）が特殊なビットパターンを持たない限り任意のｘ，ｙに対してＣｉ，ｊ（ｘ）とＣｉ，ｊ（ｙ）を排他的論理和した演算結果が０にならないことが保証できるので、異なる全体置換を構成可能となる。また上記の変換処理例２の場合にも排他的論理和した結果が０にはならないことが保証できるため、この処理例でも異なる全体置換を生み出すのに適している。
【０２２７】
なお、上記の変換処理例において示したローテーション量およびマスク値は全体置換ごとに定められた値を用いる構成としたが、一つの全体置換に必要な複数のコンスタント値をつくるために複数の値を設定して利用する構成でも同様の効果が期待できる。
【０２２８】
これらの方式の採用により、一番目の置換関数用のコンスタント値の集合があれば、軽い処理コストで別の置換関数用のコンスタント値の集合を作成することができるため、処理の高速化が期待できる。
【０２２９】
とくにデータ変換装置に、プログラム実行機能、すなわちソフトウェアを実装した場合には、すべての全体置換に対するコンスタント値の集合をいったんメモリ上に展開することなく必要に応じて動的に作り出す形のプログラミング形態が可能となるためメモリ利用効率の向上が期待できる。
【０２３０】
なお、上記の例ではローテーション操作対象をワード単位での例を挙げて説明したが、２ワード分やそれ以上のワードを結合した単位でローテーションを施す形に変形してもよく、上記で説明した同様な効果が期待できる。
【０２３１】
［１９．ハッシュ関数の出力値の切り詰め手法］
次に、ハッシュ値の生成処理構成において、ｎビットのハッシュ値を出力する関数を準備し、ｋビット分の出力を切り詰めてｎ−ｋビットのハッシュ値を出力可能としたデータ変換装置の構成例について説明する。
【０２３２】
例えば２５６ビット出力を持つハッシュ関数を準備しておき、その出力の３２ビット分を切り詰めて２２４ビットハッシュ関数とする構成である。
【０２３３】
図３５は、図３０に示した内部置換処理部（置換関数）４１０と同様の構成であり、全体置換の最終段の内部置換処理構成を示している。出力ｙ１〜ｙ８は全体置換の出力であり、ハッシュ関数の出力としてのハッシュ値を示している。なお、図３５では１ワード（４バイト）のデータ線を一本のデータ線として簡略化して示している。出力ｙ１〜ｙ８全体で、４×８＝３２バイト＝２５６ビット出力となる。
【０２３４】
なお、説明を容易にするために出力の直前では排他的論理和後のデータを入れ替える処理は行わないものとする。さらに出力直前にデータ系列に対して排他的論理和されるデータＸｉはこの圧縮関数に入力されている中間地としての連鎖値（ＣＶ：Ｃｈａｉｎｉｎｇ  Ｖａｒｉａｂｌｅ）やメッセージなどにより構成されるフィードフォワードされたデータを表しているものとする。
【０２３５】
ここで出力のｎビットのデータのうちｋビットのデータを切り詰めデータとして削除して出力データの切り詰めを行う方法を考える。図の出力系列：ｙ１〜ｙ８までのうちの、どのデータ系列に含まれるビットを切り詰めるかを決定する必要がある。ひとつの方法として左から順にｋビット分を切り詰める方式がある。その場合には次のような問題が考えられる。もしもｋビットが左から２本分のデータ線のサイズの和を超えている場合には、切り詰めた結果の出力データを見たときに左端の非線形変換の処理結果が残された出力のどのビットにも影響を及ぼさないことになる。これはこの部分の計算に無駄であったことがわかる。
【０２３６】
このような無駄を避けるための特定のデータ系列に偏らない切り詰め手法について、以下２つの処理手法を説明する。
【０２３７】
（データ切り詰め手法１）
出力データ系列数をｍ，切り詰めるビット数（削除ビット数）をｋとする。
ｋビットをできるだけ均等にｍ個に分けるために、以下の数式に従ってパラメータａ，ｂを算出する。
【０２３８】
【数１】
2010049127.tif 000003
【０２３９】
上記式によって、ａ，ｂを算出する。
なお、ａ＋ｂ＝ｍである。
出力として得られるｍ個の系列ｙ１からｙｍのうちのａ個の出力系列の出力データの各々から、ｆ（ｋ／ｍ）ビット分ずつ切り詰める。さらに、残りのｂ個の出力系列の出力データの各々から、ｆ（ｋ／ｍ）＋１ビット分ずつ切り詰める。すなわち、図３６に示すように、各出力系列に対するデータ切り詰め処理を実行する。
【０２４０】
置換を利用した場合には連続したビット列を切り捨てるよりも、飛び飛びに切り捨てることによりすべての非線形変換の結果がいずれかの出力に影響するように保証できるため、出力値の生成処理に無駄が発生しない。
【０２４１】
上記の出力ビット切り詰め処理では、すべての出力データ系列をデータ切り詰め対象として処理を行ったが、一部の出力系列のみを選択してデータ切り詰め処理を実行する構成としてもよい。
【０２４２】
例えば、図３３に示す内部置換処理構成では、左から２本ずつの出力データには同じ非線形変換の出力が影響しているため、たとえば左から奇数番目（あるいは偶数番目）のデータ系列のみを切り詰めの対象として選択する構成としてもよい。このような処理を行っても、処理の無駄が発生しないという上記同様の効果は期待でき、さらに切り詰める個所が少なくなることで処理の手間が削減できる。なお、この系列選択構成は、出力系列数＝ｎとしたとき、切り詰めるビット長がｎ／２を超えない場合に適用可能である。
【０２４３】
（データ切り詰め手法２）
出力データ系列数をｍ，切り詰めるビット数（削除ビット数）をｋとする。
ｋビットをできるだけ均等にｍ個に分けるために、以下の数式に従ってパラメータａ，ｂを算出する。
【０２４４】
【数２】
2010049127.tif 000004
【０２４５】
上記式によって、ａ，ｂを算出する。
なお、ａ＋ｂ＝ｍ／２である。
出力として得られるｍ個の系列ｙ１からｙｍのうちのｍ／２個の奇数番目の出力ｙ１，ｙ３，ｙ５，...，ｙ２ｍ−１のうちのａ個の出力系列の出力データの各々から、ｆ（２ｋ／ｍ）ビット分ずつ切り詰める。さらに、ｍ／２個の奇数番目の出力の残りのｂ個の出力系列の出力データの各々から、ｆ（２ｋ／ｍ）＋１ビット分ずつ切り詰める。
【０２４６】
このように一部の出力系列のみを選択してデータ切り詰め処理を実行する構成としてもよい。この処理例では、切り詰める個所が少なくなることで処理の手間が削減できる。
【０２４７】
［２０．データ変換装置の構成例］
最後に、上述した実施例に従った処理を実行する装置としてのＩＣモジュール７００の構成例を図３７に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能である。また、各処理は、論理回路を構成したハード回路やプログラム、あるいはその双方を適用して実行可能である。処理を実行する一例として例えば、図３７に示すＩＣモジュール７００があり、このようなＩＣモジュール７００は様々な機器に搭載することが可能である。
【０２４８】
図３７に示すＣＰＵ(Central processing Unit)７０１は、暗号処理やハッシュ処理等のデータ変換処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ７０２は暗号処理やハッシュ処理等のデータ変換処理に必要な鍵データや、データ変換処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０２４９】
データ変換部７０３は、例えば上述した各種の処理、すなわちハッシュ関数、圧縮関数、置換関数、攪拌関数などの各関数に対応するデータ変換処理、コンスタント算出、出力データ切り詰め処理などの各種処理を実行する。なお、これらの各関数の実行においては、各関数の実行において規定されている線形変換や、非線形変換や、排他的論理和演算などを、予め設定されたシーケンスに従って実行することになる。これらの処理は、ハードウェア、またはソフトウェア、またはその組み合わせ構成によって実現される。
【０２５０】
なお、ここでは、データ変換部を個別モジュールとした例を示したが、このような独立したモジュールを設けず、例えば暗号処理やハッシュ処理プログラムをＲＯＭに格納し、ＣＰＵ７０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。各関数の実行、コンスタント算出、出力データ切り詰め処理などの各種処理をＣＰＵ７０１がプログラムに従って実行する構成としてもよい。
【０２５１】
乱数発生器７０４は、暗号処理やハッシュ処理に必要となる鍵やパラメータの生成などにおいて必要となる乱数の発生処理を実行する。
【０２５２】
送受信部７０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０２５３】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０２５４】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２５５】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２５６】
上述したように、本発明の一実施例の構成によれば、メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する構成を有する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力し入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成とした。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【図面の簡単な説明】
【０２５７】
【図１】データ圧縮処理部としての圧縮関数（ｆ）について説明する図である。
【図２】代表的な定義域拡張法であるメッセージパディング付きのＭＤ構成（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  Ｃｏｎｓｔｒｕｃｔｉｏｎ）について説明する図である。
【図３】出力ビットサイズが小さい圧縮関数を利用して出力ビットサイズの大きいハッシュ値を実現するカスケードハッシュ構成について説明する図である。
【図４】安全性を高めた圧縮処理部（圧縮関数）の構成について説明する図である。
【図５】図４に示す圧縮関数ユニット５０をＭＤ構成として接続したハッシュ関数構成例について説明する図である。
【図６】図５で示した構成の変形例であり圧縮関数内部で攪拌関数Ｆと圧縮関数ｆ１およびｆ２の順序を入れ替えた圧縮関数ユニット５５を利用したハッシュ関数構成例について説明する図である。
【図７】図６に示す構成における最終部分の攪拌関数Ｆを削除した構成例について説明する図である。
【図８】攪拌関数Ｆを挿入する間隔を圧縮関数の２回分の処理ごとに設定した構成例について説明する図である。
【図９】攪拌関数Ｆの挿入間隔を圧縮関数ｋ回ごとに設定した一般化したハッシュ関数実行部の構成例について説明する図である。
【図１０】攪拌関数Ｆを２つの圧縮関数を用いて実現した構成例について説明する図である。
【図１１】系列数＝ｍ、ただしｍは２以上の整数としたハッシュ関数の一般化構成例について説明する図である。
【図１２】ｍｂビット入出力の攪拌関数Ｆの構成例について説明する図である。
【図１３】圧縮関数ｆの内部構成例について説明する図である。
【図１４】メッセージスケジュール部（ＭＳ部）と連鎖値（ＣＶ）処理部とによって構成される圧縮関数を、ＭＤ構成を持つハッシュ関数に設定した構成例について説明する図である。
【図１５】メッセージスケジュール部の共有を行ったハッシュ関数の構成例について説明する図である。
【図１６】圧縮関数内の入力メッセージサイズを拡張する圧縮関数の構成例について説明する図である。
【図１７】メッセージスケジュール部を２つの部分に分割した構成を持つ圧縮関数の構成例について説明する図である。
【図１８】メッセージスケジュール部を２つの部分に分割した構成を持ち、排他的論理和演算部（ＸＯＲ）を有する圧縮関数の構成例について説明する図である。
【図１９】図１７に示す圧縮関数の構成を一般化してｎａビットの入力に対応するように設定した圧縮関数の構成例について説明する図である。
【図２０】図１８に示す圧縮関数の構成を一般化してｎａビットの入力に対応するように設定した圧縮関数の構成例について説明する図である。
【図２１】付加入力のある置換関数の例について説明する図である。
【図２２】中間出力のある置換関数の例について説明する図である。
【図２３】既存の置換関数を用いた圧縮関数の構成例について説明する図である。
【図２４】圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例について説明する図である。
【図２５】入力ビットが３ａビットに拡大された圧縮関数の構成例について説明する図である。
【図２６】入力ビットが３ａビットに拡大された圧縮関数の構成例について説明する図である。
【図２７】２系列の圧縮関数のメッセージスケジュール部の共有を行った構成例について説明する図である。
【図２８】圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例について説明する図である。
【図２９】２つの中間出力付き置換関数と、２つの付加入力付き置換関数の組み合わせによって構成した攪拌関数Ｆの構成例について説明する図である。
【図３０】内部置換として利用できる置換関数の具体的構成例について説明する図である。
【図３１】内部置換処理部（置換関数）内に構成される非線形変換部の内部構成の一例について説明する図である。
【図３２】内部置換処理部（置換関数）の非線形変換部において利用する線形変換行列［Ｍ］に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を説明する図である。
【図３３】線形変換行列［Ｍ］に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を説明する図である。
【図３４】全体置換用のコンスタントＣｉｊ（２），Ｃｉｊ（３），．．，Ｃｉｊ（ｍ）を生成する手法について説明する図である。
【図３５】ハッシュ関数の出力ビットの切り詰め手法の一例について説明する図である。
【図３６】ハッシュ関数の出力ビットの切り詰め手法の一例について説明する図である。
【図３７】本発明に係る処理を実行するデータ変換装置としてのＩＣモジュールの構成例を示す図である。
【符号の説明】
【０２５８】
１０  圧縮関数
５０  圧縮関数ユニット
５５  圧縮関数ユニット
６０  圧縮関数ユニット
７０，７１  圧縮関数ユニット
８０，８５  攪拌関数Ｆ
８１，８２，８６，８７  変換部
８３，８４，８８，８９  圧縮関数
９０，９１  圧縮関数ユニット
１００  攪拌関数Ｆ
１２０  圧縮関数
１２１  メッセージスケジュール部（ＭＳ部）
１２２  連鎖値（ＣＶ）処理部
１３０  圧縮関数ユニット
１４０  圧縮関数ユニット
１４１  メッセージスケジュール部（ＭＳ部）
１４２  圧縮関数
１５０  圧縮関数
１５１  メッセージスケジュール部（ＭＳ部）
１５２  連鎖値（ＣＶ）処理部
１６０  圧縮関数
１６１，１６２  メッセージスケジュール部（ＭＳ部）
１６３  連鎖値（ＣＶ）処理部
１７０  圧縮関数
１７１，１７２  メッセージスケジュール部（ＭＳ部）
１７３  連鎖値（ＣＶ）処理部
１７４  排他的論理和演算（ＸＯＲ）部
２１０  圧縮関数
２１１  メッセージスケジュール部（ＭＳ部）
２１２  連鎖値（ＣＶ）処理部
２２０  圧縮関数
２２１  メッセージスケジュール部（ＭＳ部）
２２２  連鎖値（ＣＶ）処理部
２２３  排他的論理和演算（ＸＯＲ）部
３１０  置換関数（置換処理部）
３１１  付加入力
３２０  置換関数（置換処理部）
３２１  中間出力
３３０  圧縮関数
３３１  メッセージスケジュール部（ＭＳ部）
３３２  連鎖値（ＣＶ）処理部
３４０  圧縮関数
３４１，３４２  メッセージスケジュール部（ＭＳ部）
３４３  連鎖値（ＣＶ）処理部
３５０  圧縮関数
３５１，３５２  メッセージスケジュール部（ＭＳ部）
３５３  連鎖値（ＣＶ）処理部
３６０  圧縮関数
３６１，３６２  メッセージスケジュール部（ＭＳ部）
３６３  連鎖値（ＣＶ）処理部
３７０  圧縮関数
３７１  メッセージスケジュール部（ＭＳ部）
３７２，３７３  連鎖値（ＣＶ）処理部
３８０  圧縮関数
３８１，３８２  メッセージスケジュール部（ＭＳ部）
３８３，３８４  連鎖値（ＣＶ）処理部
３９０  攪拌関数Ｆ
３９１，３９２  メッセージスケジュール部（ＭＳ部）
３９３，３９４  連鎖値（ＣＶ）処理部
４１０  内部置換処理部（置換関数）
４１１  非線形変換部
４１２  排他的論理和（ＸＯＲ）演算部
４１３  スワップ処理部
４２１  排他的論理和（ＸＯＲ）演算部
４２２  小非線形変換部
４２３  線形変換部
４４０  内部置換処理部（置換関数）
４４１  非線形変換部
４４２  排他的論理和演算（ＸＯＲ）部
４４３  スワップ処理部
４５１  非線形変換部
４５２  排他的論理和演算（ＸＯＲ）部
４６０  内部置換処理部（置換関数）
４６１  非線形変換部
４７０  内部置換処理部（置換関数）
４７１  非線形変換部
４８０〜４８４  コンスタント集合
７００  ＩＣモジュール
７０１  ＣＰＵ(Central processing Unit)
７０２  メモリ
７０３  データ変換部
７０４  乱数発生器
７０５  送受信部
【図１】
2010049127.tif 000005
【図２】
2010049127.tif 000006
【図３】
2010049127.tif 000007
【図４】
2010049127.tif 000008
【図５】
2010049127.tif 000009
【図６】
2010049127.tif 000010
【図７】
2010049127.tif 000011
【図８】
2010049127.tif 000012
【図９】
2010049127.tif 000013
【図１０】
2010049127.tif 000014
【図１１】
2010049127.tif 000015
【図１２】
2010049127.tif 000016
【図１３】
2010049127.tif 000017
【図１４】
2010049127.tif 000018
【図１５】
2010049127.tif 000019
【図１６】
2010049127.tif 000020
【図１７】
2010049127.tif 000021
【図１８】
2010049127.tif 000022
【図１９】
2010049127.tif 000023
【図２０】
2010049127.tif 000024
【図２１】
2010049127.tif 000025
【図２２】
2010049127.tif 000026
【図２３】
2010049127.tif 000027
【図２４】
2010049127.tif 000028
【図２５】
2010049127.tif 000029
【図２６】
2010049127.tif 000030
【図２７】
2010049127.tif 000031
【図２８】
2010049127.tif 000032
【図２９】
2010049127.tif 000033
【図３０】
2010049127.tif 000034
【図３１】
2010049127.tif 000035
【図３２】
2010049127.tif 000036
【図３３】
2010049127.tif 000037
【図３４】
2010049127.tif 000038
【図３５】
2010049127.tif 000039
【図３６】
2010049127.tif 000040
【図３７】
2010049127.tif 000041