(57)【特許請求の範囲】
【請求項１】
k,b,n,rは正の整数であり、k>b>n>rであるとして、
nビットの内部変数cvを入力として、前記内部変数cvの上位n/2ビットと下位n/2ビットを入れ替えることで、nビットの撹拌内部変数T(cv)を生成する内部変数撹拌部と、
bビットのメッセージmを入力として、kビットの拡大メッセージE(m)を生成する拡大メッセージ生成部と、
前記内部変数cvと前記拡大メッセージE(m)を入力として、あらかじめ定めた第１ラウンド定数constを用いて、nビットの第１撹拌情報Xを出力する第１撹拌情報生成部と、
前記撹拌内部変数T(cv)と前記拡大メッセージE(m)を入力として、あらかじめ定めた第２ラウンド定数const’を用いて、nビットの第２撹拌情報X’を出力する第２撹拌情報生成部と、
前記内部変数cvと前記第１撹拌情報Xと前記第２撹拌情報X’とを入力として、nビットの出力値oを生成する出力値生成部と、
を備える圧縮関数演算装置。
【請求項２】
k,b,n,rは正の整数であり、k>b>n>rであるとして、
nビットの内部変数cvを入力として、前記内部変数cvと少なくとも1つのビットに1が設定されたnビットのマスクとの排他的論理和を計算することにより、nビットの撹拌内部変数T(cv)を生成する内部変数撹拌部と、
bビットのメッセージmを入力として、kビットの拡大メッセージE(m)を生成する拡大メッセージ生成部と、
前記内部変数cvと前記拡大メッセージE(m)を入力として、あらかじめ定めた第１ラウンド定数constを用いて、nビットの第１撹拌情報Xを出力する第１撹拌情報生成部と、
前記撹拌内部変数T(cv)と前記拡大メッセージE(m)を入力として、あらかじめ定めた第２ラウンド定数const’を用いて、nビットの第２撹拌情報X’を出力する第２撹拌情報生成部と、
前記内部変数cvと前記第１撹拌情報Xと前記第２撹拌情報X’とを入力として、nビットの出力値oを生成する出力値生成部と、
を備える圧縮関数演算装置。
【請求項３】
請求項２に記載の圧縮関数演算装置であって、
前記内部変数cvは、少なくとも1つのビットに1が設定されたnビットのビット列であり、
前記内部変数撹拌部は、
前記内部変数cvと、前記内部変数cvの上位n/2ビットと下位n/2ビットを入れ替えたビット列との排他的論理和を計算することにより、前記撹拌内部変数T(cv)を生成する
ことを特徴とする圧縮関数演算装置。
【請求項４】
請求項２に記載の圧縮関数演算装置であって、
前記内部変数撹拌部は、
前記内部変数cvとすべてのビットに1が設定されたnビットのマスクとの排他的論理和を計算することにより、前記撹拌内部変数T(cv)を生成する
ことを特徴とする圧縮関数演算装置。
【請求項５】
k,b,n,rは正の整数であり、k>b>n>rであるとして、
内部変数撹拌部が、nビットの内部変数cvを入力として、前記内部変数cvの上位n/2ビットと下位n/2ビットを入れ替えることで、nビットの撹拌内部変数T(cv)を生成する内部変数撹拌ステップと、
拡大メッセージ生成部が、bビットのメッセージmを入力として、kビットの拡大メッセージE(m)を生成する拡大メッセージ生成ステップと、
第１撹拌情報生成部が、前記内部変数cvと前記拡大メッセージE(m)を入力として、あらかじめ定めた第１ラウンド定数constを用いて、nビットの第１撹拌情報Xを出力する第１撹拌情報生成ステップと、
第２撹拌情報生成部が、前記撹拌内部変数T(cv)と前記拡大メッセージE(m)を入力として、あらかじめ定めた第２ラウンド定数const’を用いて、nビットの第２撹拌情報X’を出力する第２撹拌情報生成ステップと、
出力値生成部が、前記内部変数cvと前記第１撹拌情報Xと前記第２撹拌情報X’とを入力として、nビットの出力値oを生成する出力値生成ステップと、
を含む圧縮関数演算方法。
【請求項６】
k,b,n,rは正の整数であり、k>b>n>rであるとして、
内部変数撹拌部が、nビットの内部変数cvを入力として、前記内部変数cvと少なくとも1つのビットに1が設定されたnビットのマスクとの排他的論理和を計算することにより、nビットの撹拌内部変数T(cv)を生成する内部変数撹拌ステップと、
拡大メッセージ生成部が、bビットのメッセージmを入力として、kビットの拡大メッセージE(m)を生成する拡大メッセージ生成ステップと、
第１撹拌情報生成部が、前記内部変数cvと前記拡大メッセージE(m)を入力として、あらかじめ定めた第１ラウンド定数constを用いて、nビットの第１撹拌情報Xを出力する第１撹拌情報生成ステップと、
第２撹拌情報生成部が、前記撹拌内部変数T(cv)と前記拡大メッセージE(m)を入力として、あらかじめ定めた第２ラウンド定数const’を用いて、nビットの第２撹拌情報X’を出力する第２撹拌情報生成ステップと、
出力値生成部が、前記内部変数cvと前記第１撹拌情報Xと前記第２撹拌情報X’とを入力として、nビットの出力値oを生成する出力値生成ステップと、
を含む圧縮関数演算方法。
【請求項７】
請求項１から４のいずれかに記載の圧縮関数演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号学的圧縮関数を演算する技術に関し、特に、RIPEMD型二重構造を用いる圧縮関数の安全性を高める圧縮関数演算技術に関する。
【背景技術】
【０００２】
暗号学的圧縮関数（以下、単に圧縮関数とも言う。）は、デジタル署名やメッセージ認証符号などのセキュリティ技術で利用されるハッシュ関数を構成するために用いられる関数である。圧縮関数H:{0,1}U→{0,1}V,U>Vは、Uビットの情報を入力として、Uビットよりも短いVビットの情報を出力する。入力値のビット長Uと出力値のビット長Vは、その圧縮関数Hに固有の固定値である。ある圧縮関数Hが高い安全性を実現するためには、圧縮関数Hへの2つの入力値I1とI2とで1ビットでも異なるビットがあれば、それぞれの出力値H(I1)とH(I2)とがランダムに振る舞うこと、つまり入力値の相関が出力値に一切反映されないことが望ましい。
【０００３】
一般的に圧縮関数Hは、nビットの内部変数cvとb(>n)ビットのメッセージmを入力にとる。まず、メッセージ拡大関数Eを用いてk(>b)ビットの拡大メッセージE(m)を計算する。次に、内部変数cvと拡大メッセージE(m)を入力とするデータ撹拌関数Dを計算することにより、撹拌情報Xを計算する。そして、内部変数cvと撹拌情報Xを入力とする出力関数Oを計算することにより、nビットの出力値oを出力する。このとき、データ撹拌関数Dは、拡大メッセージE(m)の一部を入力にとるラウンド関数Rを繰り返し実行することでデータを撹拌する。ラウンド関数Rは比較的簡単な演算であるが、演算回数を重ねることで全体としてランダムな関数を実現する。
【０００４】
圧縮関数の安全性を高めるために、二重構造を用いる圧縮関数が利用されている。二重構造を用いる圧縮関数は、通常の圧縮関数と同様に、nビットの内部変数cvとbビットのメッセージmを入力とし、メッセージ拡大関数Eとデータ撹拌関数Dにより撹拌情報Xを計算する。一方、二重構造を用いる圧縮関数は同時に、メッセージ拡大関数E’とデータ撹拌関数D’により撹拌情報X’も計算する。そして、内部変数cvと撹拌情報Xおよび撹拌情報X’を入力とする出力関数Oを計算して出力値oを計算する。二重構造を用いる圧縮関数では2つの独立なデータ撹拌を行うため、二重構造を用いない通常の圧縮関数よりも強い安全性を実現することができる。
【０００５】
二重構造を用いる圧縮関数として、RIPEMD型二重構造を用いる圧縮関数が提案されている。RIPEMD型二重構造を用いる圧縮関数は、ラウンド関数Rの処理に特徴がある。RIPEMD型二重構造を用いる圧縮関数におけるラウンド関数Rは、nビットの撹拌情報Xiと拡大メッセージE(m)の一部を入力にとり、撹拌情報Xi+1を計算する。ここで、iはラウンド関数Rの実行回数をカウントする変数である。通常の二重構造を用いる圧縮関数におけるラウンド関数Rでは、1回の関数実行においてnビットすべてを更新するが、RIPEMD型二重構造を用いる圧縮関数におけるラウンド関数Rでは、入力されたnビットの撹拌情報Xiのうち一部のみを更新する。
【０００６】
RIPEMD型二重構造を用いる圧縮関数の具体的な仕様としては、ハッシュ関数RIPEMDの仕様で規定されている圧縮関数（非特許文献１）と、ハッシュ関数RIPEMD128の仕様で規定されている圧縮関数（非特許文献２）が提案されている。非特許文献１に記載のハッシュ関数RIPEMDは、2つのメッセージ拡大関数E,E’に関しては同じ関数を利用し、2つのデータ撹拌関数D,D’に関してはラウンド関数R内で用いるパラメータであるラウンド定数以外は同一のものを利用する。非特許文献２に記載のハッシュ関数RIPEMD128は、2つのメッセージ拡大関数E,E’に関しては異なる関数を利用し、2つのデータ撹拌関数D,D’に関しては、基本構造は同一であるがラウンド関数R内で用いるパラメータがすべて異なるように構成されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】RIPE Integrity Primitives, “Integrity Primitives for Secure Information Systems”, Final Report of RACE Integrity Primitives Evaluation RIPE-RACE 1040, volume 1007 of Lecture Notes in Computer Science, pages 69-111, 1995.
【非特許文献２】Hans Dobbertin and Antoon Bosselaers and Bart Preneel, “RIPEMD-160: A Strengthened Version of RIPEMD”, Fast Software Encryption Third International Workshop, volume 1039 of Lecture Notes in Computer Science, pages 71-82, 1996.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
RIPEMD型二重構造を用いる圧縮関数においては、二重構造の利点を活かすために、2つのデータ撹拌関数D,D’の演算をできるだけ相関がないものにする必要がある。非特許文献２に記載されている圧縮関数では、メッセージ拡大関数E,E’もデータ撹拌関数D,D’も異なる関数である。そのため、2つの演算の相関は低くなり、高い安全性を実現している。しかしながら、圧縮関数を構成する要素をすべて別々に実装する必要があるため、実装効率が悪いという問題がある。非特許文献１に記載されている圧縮関数は、2つのメッセージ拡大関数E,E’が同じ関数であるため実装効率は良いが、2つの演算の相関が高くなる。そのため、非特許文献２に記載の圧縮関数と比較して安全性が低い。また、2つのデータ撹拌関数D,D’の入力がいずれも内部変数cvと拡大メッセージE(m)であるため、最初の1ラウンドで更新される値に確定的な相関がある。つまり実質的に1ラウンド分の演算が無意味になっているという問題もある。
【０００９】
この発明はこのような点に鑑みてなされたものであり、2つのデータ撹拌関数D,D’の間でラウンド関数Rが用いるパラメータであるラウンド定数以外の値を同一としながら、最初の1ラウンド後に内部変数cvとメッセージmに依存しない相関がなくなるように構成することで、圧縮関数の安全性を向上することができる圧縮関数演算技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、この発明の圧縮関数演算装置は、内部変数撹拌部と拡大メッセージ生成部と第１撹拌情報生成部と第２撹拌情報生成部と出力値生成部とを備える。k,b,n,rは正の整数であり、k>b>n>rであるとして、内部変数撹拌部は、nビットの内部変数cvを入力として、上位rビットが内部変数cvの上位rビットと少なくとも1ビットが相違するか、もしくは下位n-rビットを入力とするあらかじめ定められた非線形関数NLの出力が内部変数cvの下位n-rビットを入力とする非線形関数NLの出力と少なくとも1ビットが相違するように、nビットの撹拌内部変数T(cv)を生成する。拡大メッセージ生成部は、bビットのメッセージmを入力として、kビットの拡大メッセージE(m)を生成する。第１撹拌情報生成部は、内部変数cvと拡大メッセージE(m)を入力として、あらかじめ定めた第１ラウンド定数constを用いて、nビットの第１撹拌情報Xを出力する。第２撹拌情報生成部は、撹拌内部変数T(cv)と拡大メッセージE(m)を入力として、あらかじめ定めた第２ラウンド定数const’を用いて、nビットの第２撹拌情報X’を出力する。出力値生成部は、内部変数cvと第１撹拌情報Xと第２撹拌情報X’とを入力として、nビットの出力値oを生成する。
【発明の効果】
【００１１】
この発明の圧縮関数演算技術によれば、二重構造の圧縮関数において2つのデータ撹拌関数の演算の相関が低くなり、安全性を向上することができる。また、内部変数を撹拌する操作として、圧縮関数全体の演算量と比較して負荷の軽い演算を適用することができるため、計算コストを維持しながら安全性を向上することができる。
【図面の簡単な説明】
【００１２】
【図１】圧縮関数を説明する図。
【図２】ラウンド関数を用いた圧縮関数を説明する図。
【図３】二重構造の圧縮関数を説明する図。
【図４】従来の圧縮関数演算装置の構成例を示すブロック図。
【図５】従来の第１撹拌情報生成部の構成例を示すブロック図。
【図６】従来の圧縮関数演算装置の動作例を示すフローチャート。
【図７】従来の第１撹拌情報生成部の動作例を示すフローチャート。
【図８】第１の実施形態に係る圧縮関数演算装置の構成例を示すブロック図。
【図９】第１の実施形態に係る第２撹拌情報生成部の構成例を示すブロック図。
【図１０】第１の実施形態に係る圧縮関数演算装置の動作例を示すフローチャート。
【図１１】第１の実施形態に係る第２撹拌情報生成部の動作例を示すフローチャート。
【発明を実施するための形態】
【００１３】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。実施形態の説明に先立って、従来の圧縮関数演算装置の課題について詳細に説明する。
［圧縮関数の説明］
図１を参照して、圧縮関数の基本的な構成について説明する。図中において矢印に交差する直線とその近傍の記号は、その入出力される情報のビット長を表している。例えば、データ撹拌関数Dに入力される内部変数cvはビット長がnビットであることを表している。圧縮関数は、nビットの内部変数cvとbビットのメッセージmを入力として、nビットの出力値oを出力する。メッセージ拡大関数Eは、bビットのメッセージmを入力として、メッセージmをkビットに拡大した拡大メッセージE(m)をデータ撹拌関数Dに対して出力する。一般的に、k>b>nの関係があるが、具体的なビット長は圧縮関数の実装において仕様として規定される。データ撹拌関数Dは、内部変数cvとメッセージ拡大関数Eの出力する拡大メッセージE(m)を入力として、nビットの撹拌情報Xを出力関数Oに対して出力する。出力関数Oは、内部変数cvとデータ撹拌関数Dの出力する撹拌情報Xを入力として、nビットの出力値oを出力する。
【００１４】
［ラウンド関数を用いた圧縮関数の説明］
図２を参照して、ラウンド関数を用いた圧縮関数について説明する。ラウンド関数を用いた圧縮関数は、データ撹拌関数D以外の処理は図１を参照して説明した圧縮関数の基本的な構成と同一であるので、ここではデータ撹拌関数Dのみについて説明する。
ラウンド関数を用いた圧縮関数におけるデータ撹拌関数Dは、演算がラウンドという単位で分割される。ここでは、分割したラウンド1回の処理をラウンド関数Rという。ラウンド関数Rは拡大メッセージE(m)の一部とnビットの撹拌情報Xiを入力にとり、データを撹拌して撹拌情報Xi+1を出力する。データ撹拌関数Dは、内部変数cvを撹拌情報X0に設定し、ラウンド関数Rをt回繰り返し実行し、生成された撹拌情報Xtを出力する。したがって、ラウンド関数を用いた圧縮関数の処理は、以下の式で表すことができる。
【００１５】
【数１】
0005791562.tif 000002
【００１６】
一般的に、ラウンド関数Rは比較的簡単な演算であるが、演算回数を重ねることでデータ撹拌関数D全体としてランダムな関数を実現している。ラウンド関数Rの具体的な処理は、圧縮関数の実装により異なる。
【００１７】
［二重構造を用いた圧縮関数の説明］
図３を参照して、二重構造を用いた圧縮関数について説明する。二重構造を用いた圧縮関数は、ラウンド関数を用いた圧縮関数と同様に、nビットの内部変数cvとbビットのメッセージmを入力として、メッセージ拡大関数Eとデータ撹拌関数Dにより撹拌情報Xtを計算する。一方、二重構造を用いた圧縮関数は同時に、メッセージ拡大関数E’とデータ撹拌関数D’により撹拌情報X’tも計算する。そして、内部変数cvと撹拌情報XtおよびX’tを入力として、出力関数Oにより出力値oを計算する。したがって、二重構造を用いた圧縮関数の処理は、以下の式で表すことができる。
【００１８】
【数２】
0005791562.tif 000003
【００１９】
二重構造を用いた圧縮関数では2つの独立なデータ撹拌を行うため、二重構造を用いない圧縮関数よりも強い安全性を実現することができる。
【００２０】
［従来の圧縮関数演算装置］
＜構成＞
図４を参照して、従来の圧縮関数演算装置１９の構成例を詳細に説明する。圧縮関数演算装置１９は、非特許文献１に記載されているRIPEMD型二重構造を用いる圧縮関数の演算を行う。圧縮関数演算装置１９は、拡大メッセージ生成部１１０と第１撹拌情報生成部１３０と第２撹拌情報生成部１３１と出力値生成部１４０と第１ラウンド定数記憶部１９０と第２ラウンド定数記憶部１９１を備える。
【００２１】
図５に第１撹拌情報生成部１３０の構成例を示す。第１撹拌情報生成部１３０は、カウンタ初期化手段１３００１と撹拌情報初期化手段１３００２と撹拌情報分割手段１３００３とメッセージ加算手段１３００４とラウンド定数加算手段１３００５と非線形関数演算手段１３００６と分割情報加算手段１３００７と左巡回シフト手段１３００８と分割情報結合手段１３００９とカウンタ加算手段１３０１０と撹拌情報出力手段１３０１１を備える。
【００２２】
図６を参照して、圧縮関数演算装置１９の動作例を実際に行われる手続きの順に従って詳細に説明する。
【００２３】
第１ラウンド定数記憶部１９０には、あらかじめ定められたt個のランダムな整数であるラウンド定数consti(i=0,1,…,t-1)が記憶されている。ただし、t(≧1)はラウンド関数Rの実行回数であり、あらかじめ定められている。第２ラウンド定数記憶部１９１には、あらかじめ定められたt個のランダムな整数であるラウンド定数const’iが記憶されている。第１ラウンド定数constiと第２ラウンド定数const’iは含まれるすべての数が異なるものであることが望ましいが、この限りではない。
【００２４】
拡大メッセージ生成部１１０は、bビットのメッセージmを入力として、メッセージ拡大関数Eを実行することにより、kビットの拡大メッセージE(m)を生成する（Ｓ１１０）。メッセージ拡大関数Eは、入力されたビット列をパディングして拡大したkビットのビット列を出力する。メッセージ拡大関数Eの具体的な処理内容は、周知のRIPEMD型二重構造を用いる圧縮関数で用いられるメッセージ拡大関数と同様である。処理の詳細は、非特許文献１や非特許文献２を参照されたい。
【００２５】
第１撹拌情報生成部１３０は、nビットの内部変数cvとkビットの拡大メッセージE(m)を入力として、第１ラウンド定数記憶部１９０に記憶されている第１ラウンド定数constiを用いてデータ撹拌関数Dを実行することにより、nビットの撹拌情報Xtを出力する（Ｓ１３０）。第１撹拌情報生成部１３０の処理の詳細は後述する。
【００２６】
第２撹拌情報生成部１３１は、nビットの内部変数cvとkビットの拡大メッセージE(m)を入力として、第２ラウンド定数記憶部１９１に記憶されている第２ラウンド定数const’iを用いてデータ撹拌関数Dを実行することにより、nビットの撹拌情報X’tを出力する（Ｓ１３０）。第２撹拌情報生成部１３１の処理の詳細は後述する。
【００２７】
出力値生成部１４０は、nビットの内部変数cvとnビットの撹拌情報Xとnビットの撹拌情報X’tを入力として、出力関数Oを実行することにより、nビットの出力値oを出力する（Ｓ１４０）。出力関数Oの具体的な処理内容は、周知のRIPEMD型二重構造を用いる圧縮関数で用いられる出力関数と同様である。処理の詳細は、非特許文献１や非特許文献２を参照されたい。
【００２８】
図７を参照して、第１撹拌情報生成部１３０の動作例を実際に行われる手続きの順に従って詳細に説明する。なお、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１とはデータ撹拌関数Dを実行する際に用いるラウンド定数が異なる以外は相違点がないため、第２撹拌情報生成部１３１の動作例についての説明は省略する。
【００２９】
図７中における表記方法について説明する。E(m)|iは、拡大メッセージE(m)のうち、i回目のラウンド関数R実行時に撹拌情報Xiの更新に用いられる部分を表す。「<<<・」は、・ビットの左巡回シフトを表す。左巡回シフトとは、ビット列を上位方向に指定されたビット数だけ移動し、桁を超えたビットを下位に順次移動するビット操作である。例えば、8桁のビット列「11010100」を3ビット左巡回シフトしたのであれば、操作後のビット列は上位3ビット「110」が下位に移動して「10100110」となる。Ｓ１３００４，Ｓ１３００５，Ｓ１３００７に表される以下の記号は、算術加算を表す。
【００３０】
【数３】
0005791562.tif 000004
【００３１】
カウンタ初期化手段１３００１は、カウンタ変数iを0に初期化する（１３００１）。撹拌情報初期化手段１３００２は、入力された内部変数cvを撹拌情報Xiとして設定する（１３００２）。撹拌情報分割手段１３００３は、撹拌情報Xiの上位r(≦n-1)ビットを分割情報XiAとして設定し、撹拌情報Xiの下位n-rビットを分割情報XiBとして設定する（Ｓ１３００３）。すなわち、分割情報XiAは、撹拌情報Xiの1ビット目からrビット目までが設定される。分割情報XiBは、撹拌情報Xiのr+1ビット目からnビット目までが設定される。rはあらかじめ定められた整数であり、撹拌情報Xiのうちラウンド関数において更新されるビット数である。rの具体的な値は圧縮関数の実装により規定される。メッセージ加算手段１３００４は、一時変数tempに、分割情報XiAに拡大メッセージの一部であるE(m)|iを加算して更新する（Ｓ１３００４）。ラウンド定数加算手段１３００５は、一時変数tempに、第１ラウンド定数記憶部１９０の記憶されている第１ラウンド定数constiを加算して更新する（Ｓ１３００５）。非線形関数演算手段１３００６は、分割情報XiBを入力として、あらかじめ定めた非線形関数NLを計算し、分割情報NL(XiB)を算出する（Ｓ１３００６）。非線形関数NLは、周知のRIPEMD型二重構造を用いる圧縮関数で用いられる非線形関数であればいずれでもよい。例えば、非特許文献１や非特許文献２に記載の非線形関数を適用することができる。分割情報加算手段１３００７は、一時変数tempに、分割情報NL(XiB)を加算して更新する（Ｓ１３００７）。左巡回シフト手段１３００８は、一時変数tempをsi(≧1)ビット左巡回シフトする（Ｓ１３００８）。siは、あらかじめ定められたt個のランダムな整数であり、i回目のラウンド関数における左巡回シフトのビット数である。左巡回シフトのビット数siは、含まれるすべての数が異なるものであることが望ましいが、この限りではない。左巡回シフトの結果、操作後の一時変数tempは、操作前の一時変数tempのsi+1ビット目からnビット目と、操作前の一時変数tempの1ビット目からsiビット目を順に結合したビット列となる。分割情報結合手段１３００９は、撹拌情報Xi+1に、分割情報XiBと一時変数tempを順に結合したビット列を設定する（Ｓ１３００９）。カウンタ加算手段１３０１０は、カウンタ変数iに1を加算する（Ｓ１３０１０）。撹拌情報出力手段１３０１１は、カウンタ変数iとラウンド回数tを比較して、i<tであれば、Ｓ１３００３へ処理を戻す。i≧tであれば、撹拌情報Xiを出力する（Ｓ１３０１１）。
【００３２】
＜課題＞
上記を踏まえて、従来の圧縮関数演算装置１９の課題について説明する。RIPEMD型二重構造を用いる圧縮関数においては、二重構造の利点を活かすために、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１の処理ができるだけ相関がないものにする必要がある。圧縮関数演算装置１９では、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１に入力される拡大メッセージE(m)をいずれも拡大メッセージ生成部１１０が生成するため、実装効率はよいものの安全性に問題がある。また、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１それぞれの1ラウンド目の処理で更新される値に確定的な相関があるため、実質的に1ラウンド分の演算が無意味になっているという問題がある。より具体的には、第１撹拌情報生成部１３０の1ラウンド目で更新された一時変数tempをtemp1とし、第２撹拌情報生成部１３１の1ラウンド目で更新された一時変数tempをtemp’1とし、非線形関数をNL(x)とすると、temp1とtemp’1の値は以下の式で表すことができる。
【００３３】
【数４】
0005791562.tif 000005
【００３４】
ただし、
【数５】
0005791562.tif 000006
は、算術加算を表す。
【００３５】
したがって、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１の違いは、以下の式で表すことができる。
【００３６】
【数６】
0005791562.tif 000007
【００３７】
ただし、
【数７】
0005791562.tif 000008
は、算術減算を表す。
【００３８】
このように、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１の違いは、第１ラウンド定数constiと第２ラウンド定数const’iの違いだけであり、従来の圧縮関数演算装置１９では、第１撹拌情報生成部１３０と第２撹拌情報生成部１３１の演算に確定的な相関があると言える。したがって、従来のRIPEMD型二重構造を用いる圧縮関数では、二重構造を用いてもデータの撹拌が十分でなく、安全性に問題がある。
【００３９】
［第１の実施形態］
この発明の第１の実施形態では、第１撹拌情報生成部１３０の1ラウンド目の処理における撹拌情報X0と第２撹拌情報生成部１３１の1ラウンド目の処理における撹拌情報X’0に内部変数cvとメッセージmに依存しない相関がなくなるように構成する。
【００４０】
＜構成＞
図８を参照して、この実施形態に係る圧縮関数演算装置１０の構成例を詳細に説明する。圧縮関数演算装置１０は、従来の圧縮関数演算装置１９と同様に、拡大メッセージ生成部１１０と第１撹拌情報生成部１３０と出力値生成部１４０と第１ラウンド定数記憶部１９０と第２ラウンド定数記憶部１９１を備え、第２撹拌情報生成部１３１の替わりに第２撹拌情報生成部１３２を備え、さらに、内部変数撹拌部１２０を備える。第１ラウンド定数記憶部１９０と第２ラウンド定数記憶部１９１は、例えば、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００４１】
図９に第２撹拌情報生成部１３２の構成例を示す。第２撹拌情報生成部１３２は、従来の圧縮関数演算装置１９の備える第１撹拌情報生成部１３０と同様に、カウンタ初期化手段１３００１と撹拌情報分割手段１３００３とメッセージ加算手段１３００４とラウンド定数加算手段１３００５と非線形関数演算手段１３００６と分割情報加算手段１３００７と左巡回シフト手段１３００８と分割情報結合手段１３００９とカウンタ加算手段１３０１０と撹拌情報出力手段１３０１１を備え、撹拌情報初期化手段１３００２の替わりに撹拌情報初期化手段１３００２’を備える。すなわち、第１撹拌情報生成部１３０と第２撹拌情報生成部１３２との相違点は、撹拌情報初期化手段の処理が異なる点のみである。
【００４２】
図１０を参照して、圧縮関数演算装置１０の動作例を実際に行われる手続きの順に従って詳細に説明する。ただし、Ｓ１１０、Ｓ１３０、Ｓ１４０の処理は、従来の圧縮関数演算装置１９と同様であるので、ここでは説明を省略する。
【００４３】
内部変数撹拌部１２０は、nビットの内部変数cvを入力として操作関数Tを実行することにより、nビットの撹拌内部変数T(cv)を生成する（Ｓ１２０）。操作関数Tは、入力されたビット列と出力するビット列とで、出力するビット列の上位rビットが入力されたビット列の上位rビットと少なくとも1ビットが相違するか、もしくは出力するビット列の下位n-rビットを入力とする非線形関数NLの出力が、入力されたビット列の下位n-rビットを入力とする非線形関数NLの出力と少なくとも1ビットが相違するか、を満たす操作であればどのような操作でもよい。例えば、任意のビット位置の入れ替えを行なってもよいし、負荷の軽い線形演算であってもよい。
【００４４】
より具体的には、操作関数Tをビット位置の入れ替え操作とするのであれば、例えば、上位n/2ビットのビット列と下位n/2ビットのビット列を入れ替える操作が考えられる。すなわち、内部変数cvの1ビット目からn/2ビット目までを撹拌内部変数T(cv)のn/2+1ビット目からnビット目として設定し、内部変数cvのn/2+1ビット目からnビット目までを撹拌内部変数T(cv)の1ビット目からn/2ビット目として設定することで、撹拌内部変数T(cv)を生成する。ビット位置の入れ替え操作はハードウェアでの実装において計算コストが実質的に0である。したがって、内部変数撹拌部１２０を追加したことが圧縮関数演算装置１０の計算コストへ影響することはない。
【００４５】
また、操作関数Tを軽い線形演算とするのであれば、例えば、内部変数cvと同じビット長のマスクと排他的論理和を計算することにより撹拌内部変数T(cv)を生成するように構成すればよい。このとき、すべてのビットが1であるマスクを利用し、内部変数cvのすべてのビットを反転させたビット列を撹拌内部変数T(cv)としてもよい。もしくは、内部変数cvの上位n/2ビットと下位n/2ビットを入れ替えたビット列をマスクとして利用して、撹拌内部変数T(cv)を生成するように構成してもよい。
【００４６】
第２撹拌情報生成部１３２は、nビットの撹拌内部変数T(cv)とkビットの拡大メッセージE(m)を入力として、第２ラウンド定数記憶部１９１に記憶されている第２ラウンド定数const’iを用いてデータ撹拌関数Dを実行することにより、nビットの撹拌情報X’tを出力する（Ｓ１３２）。
【００４７】
図１１を参照して、第２撹拌情報生成部１３２の動作例をより詳細に説明する。第２撹拌情報生成部１３２は、従来の圧縮関数演算装置１９の備える第２撹拌情報生成部１３１と撹拌情報初期化手段の動作が異なる。撹拌情報初期化手段１３００２’は、入力された撹拌内部変数T(cv)を撹拌情報Xiに設定する（１３００２’）。以降の処理は、第１撹拌情報生成部１３０の処理と同様であるので説明は省略する。
【００４８】
＜効果＞
第１の実施形態に係る圧縮関数演算装置１０は、内部変数撹拌部１２０を備えることにより、入力された内部変数cvから撹拌内部変数T(cv)を生成する。そして、第１撹拌情報生成部１３０は、内部変数cvと拡大メッセージE(m)を入力として第１撹拌情報Xtを生成し、第２撹拌情報生成部１３２は、撹拌内部変数T(cv)と拡大メッセージE(m)を入力として第２撹拌情報X’tを生成する。このように構成することで、第１撹拌情報生成部１３０の1ラウンド目の処理における撹拌情報X0と第２撹拌情報生成部１３１の1ラウンド目の処理における撹拌情報X’0が異なるものとなる。そのため、第１撹拌情報生成部１３０と第２撹拌情報生成部１３２における分割情報X0A、および分割情報X0Bを入力として非線形関数NLの出力する分割情報NL(X0B)は等しくなることがない。したがって、第１撹拌情報生成部１３０と第２撹拌情報生成部１３２の処理とで、内部変数cvとメッセージmに依存しない相関がなくなる。
【００４９】
第１撹拌情報生成部１３０と第２撹拌情報生成部１３２の違いは、以下の式で表すことができる。このように内部変数cvとメッセージmに依存しない相関が消えていることが確認できる。
【００５０】
【数８】
0005791562.tif 000009
【００５１】
このように、この発明の圧縮関数演算装置１０は、2つのデータ撹拌関数Dの演算の間で内部変数cvとメッセージmに依存しない相関がなく、RIPEMD型二重構造を用いた圧縮関数の安全性を向上することができる。また、内部変数撹拌部１２０が内部変数cvから撹拌内部変数T(cv)を生成する演算は負荷の軽い演算で実装できるため、圧縮関数全体での計算コストに与える影響が小さい。したがって、圧縮関数演算装置１０は、従来の圧縮関数演算装置１９と比較して、計算コストを維持しながら、安全性を向上することができる。
【００５２】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５５】
１０，１９  圧縮関数演算装置
１１０  拡大メッセージ生成部
１２０  内部変数撹拌部
１３０  第１撹拌情報生成部
１３１，１３２  第２撹拌情報生成部
１４０  出力値生成部
１９０  第１ラウンド定数記憶部
１９１  第２ラウンド定数記憶部
１３００１  カウンタ初期化手段
１３００２，１３００２’  撹拌情報初期化手段
１３００３  撹拌情報分割手段
１３００４  メッセージ加算手段
１３００５  ラウンド定数加算手段
１３００６  非線形関数演算手段
１３００７  分割情報加算手段
１３００８  左巡回シフト手段
１３００９  分割情報結合手段
１３０１０  カウンタ加算手段
１３０１１  撹拌情報出力手段
【図１】
0005791562.tif 000010
【図２】
0005791562.tif 000011
【図３】
0005791562.tif 000012
【図４】
0005791562.tif 000013
【図５】
0005791562.tif 000014
【図６】
0005791562.tif 000015
【図７】
0005791562.tif 000016
【図８】
0005791562.tif 000017
【図９】
0005791562.tif 000018
【図１０】
0005791562.tif 000019
【図１１】
0005791562.tif 000020