(57)【特許請求の範囲】
【請求項１】
ハッシュ関数を用いた処理を行うハッシュ手段を１以上備え、データＭに対するメッセージ認証子τを出力するメッセージ認証子生成装置であって、
前記ハッシュ手段の少なくとも１つは、
当該ハッシュ手段への入力Ｄに対して、あらかじめ定めたパディングを行うことでＮ×（ｃ＋ｂ）ビット（ただし、Ｎ、ｃ、ｂは正の整数）のビット列であるデータＭ＊を求めるパディング部と、
前記データＭ＊を、Ｎ個のｃビットのメッセージブロックｍ２ｎ−１とＮ個のｂビットのメッセージブロックｍ２ｎ（ただし、ｎは１以上Ｎ以下の整数）に分割するメッセージブロック生成部と、
最初の中間変数ｖ０を求める初期値設定部と、
中間変数ｖｎ−１とメッセージブロックｍ２ｎ−１との排他的論理和に、メッセージブロックｍ２ｎを結合したビット列を、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｈによって圧縮して中間変数ｖｎを求める処理を、ｎ＝１からｎ＝Ｎまで繰り返して中間変数ｖＮを求める中間変数計算部と
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記初期値設定部は、ｃビットのビット列である鍵Ｋ１＊を最初の中間変数ｖ０とする
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
請求項２記載のメッセージ認証子生成装置であって、
ｂ≧ｃであり、
ｃビットのビット列である鍵Ｋ２＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理部も備える
ことを特徴とするメッセージ認証子生成装置。
【請求項４】
請求項１記載のメッセージ認証子生成装置であって、
前記初期値設定部は、ｃビットのビット列である鍵Ｋ＊とｂ個の“０”のビット列を結合したビット列を、前記圧縮関数ｈによって圧縮して最初の中間変数ｖ０を求める
ことを特徴とするメッセージ認証子生成装置。
【請求項５】
請求項４記載のメッセージ認証子生成装置であって、
ｂ≧ｃであり、
前記鍵Ｋ＊とｂ個の“１”のビット列を結合したビット列を前記圧縮関数ｈによって圧縮したビット列と、前記中間変数ｖＮと、（ｂ−ｃ）個の“１”のビット列とを連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理部も備える
ことを特徴とするメッセージ認証子生成装置。
【請求項６】
請求項４記載のメッセージ認証子生成装置であって、
ｂ＞ｃであり、
前記鍵Ｋ＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理部も備える
ことを特徴とするメッセージ認証子生成装置。
【請求項７】
データＭとメッセージ認証子τとを入力とし、データＭの検証を行うメッセージ認証子検証装置であって、
前記データＭからメッセージ認証子τ’を生成する請求項１から６のいずれかに記載のメッセージ認証子生成装置と、
前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＭの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項８】
ハッシュ関数を用いた処理を行うハッシュ過程を１以上有し、データＭに対するメッセージ認証子τを出力するメッセージ認証子生成方法であって、
前記ハッシュ過程の少なくとも１つは、
パディング部で、当該ハッシュ過程への入力Ｄに対して、あらかじめ定めたパディングを行うことでＮ×（ｃ＋ｂ）ビット（ただし、Ｎ、ｃ、ｂは正の整数）のビット列であるデータＭ＊を求めるパディングステップと、
メッセージブロック生成部で、前記データＭ＊を、Ｎ個のｃビットのメッセージブロックｍ２ｎ−１とＮ個のｂビットのメッセージブロックｍ２ｎ（ただし、ｎは１以上Ｎ以下の整数）に分割するメッセージブロック生成ステップと、
初期値設定部で、最初の中間変数ｖ０を求める初期値設定ステップと、
中間変数計算部で、中間変数ｖｎ−１とメッセージブロックｍ２ｎ−１との排他的論理和に、メッセージブロックｍ２ｎを結合したビット列を、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｈによって圧縮して中間変数ｖｎを求める処理を、ｎ＝１からｎ＝Ｎまで繰り返して中間変数ｖＮを求める中間変数計算ステップと
を有するメッセージ認証子生成方法。
【請求項９】
請求項８記載のメッセージ認証子生成方法であって、
前記初期値設定ステップは、ｃビットのビット列である鍵Ｋ１＊を最初の中間変数ｖ０とする
ことを特徴とするメッセージ認証子生成方法。
【請求項１０】
請求項９記載のメッセージ認証子生成方法であって、
ｂ≧ｃであり、
後処理部で、ｃビットのビット列である鍵Ｋ２＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理ステップも有する
ことを特徴とするメッセージ認証子生成方法。
【請求項１１】
請求項８記載のメッセージ認証子生成方法であって、
前記初期値設定ステップは、ｃビットのビット列である鍵Ｋ＊とｂ個の“０”のビット列を結合したビット列を、前記圧縮関数ｈによって圧縮して最初の中間変数ｖ０を求める
ことを特徴とするメッセージ認証子生成方法。
【請求項１２】
請求項１１記載のメッセージ認証子生成方法であって、
ｂ≧ｃであり、
後処理部で、前記鍵Ｋ＊とｂ個の“１”のビット列を結合したビット列を前記圧縮関数ｈによって圧縮したビット列と、前記中間変数ｖＮと、（ｂ−ｃ）個の“１”のビット列とを連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理ステップも有する
ことを特徴とするメッセージ認証子生成方法。
【請求項１３】
請求項１１記載のメッセージ認証子生成方法であって、
ｂ＞ｃであり、
後処理部で、前記鍵Ｋ＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める後処理ステップも有する
ことを特徴とするメッセージ認証子生成方法。
【請求項１４】
データＭとメッセージ認証子τとを入力とし、データＭの検証を行うメッセージ認証子検証方法であって、
前記データＭからメッセージ認証子τ’を生成する請求項８から１３のいずれかに記載のメッセージ認証子生成方法の各ステップと、
比較部で、前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＭの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項１５】
請求項１から７のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【請求項１６】
請求項１５記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証が行えるようにするためのメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＧは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子τを生成する（τ←ＧＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＧと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
【０００３】
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵Ｋ（通常、鍵は１つだが、２つ以上の場合もある）とデータＭからメッセージ認証子τを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子τ’を生成する。そして、τとτ’とを比較する。τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００４】
従来のメッセージ認証コードには、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを２回適用して安全性を高めたもの（非特許文献１）などがある。非特許文献１のメッセージ認証コードＧＫ（Ｍ）は、次式のようにメッセージ認証子τを求める。
【数１】
0005006770.tif 000002
ただし、“‖”はビット列の結合を意味する記号、“０ｃ−ｋ”は“０”がｃ−ｋ個並んだビット列を示す記号、ＩＰＡＤとＯＰＡＤはｃビットのあらかじめ定められた定数である。このメッセージ認証コードは、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である（非特許文献２）。図１は、式（１）の処理を行うメッセージ認証子生成装置の機能構成例を示す図である。メッセージ認証子生成装置９００は、鍵パディング手段９１０とハッシュ手段９２０とを備える。鍵パディング手段９１０は、式（１）の１行目を実行し、ｋビットの鍵をｄビットにする。ハッシュ手段９２０は、式（１）の２行目と３行目を実行し、メッセージ認証子τを出力する。図２は、ハッシュ手段９２０の機能構成例である。ハッシュ手段９２０は、パディング部９２１、メッセージブロック生成部９２２、初期設定部９２３、中間変数計算部９２４から構成されている。パディング部９２１は、ハッシュ関数ＨＭＤへ入力されたビット列Ｄを、パディングによりＮ×ｂビットのビット列Ｍ＊に変換する（ただし、Ｎとｂは正の整数）。メッセージブロック生成部９２２は、ビット列Ｍ＊をＮ個のｂビットのメッセージブロックｍｎに分割する（ただし、ｎは１以上Ｎ以下の整数）。初期設定部９２３は、最初の中間変数ｖ０をあらかじめ定めた定数に設定する。中間変数計算部９２４は、
ｖｎ←ｈ（ｖｎ−１‖ｍｎ）                                          （２）
をｎ＝１からｎ＝Ｎまで繰り返し、ｖＮを求め、出力する。中間変数ｖｎはｃビットのビット列であり、ｈは（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数である。なお、このメッセージ認証コードに用いる圧縮関数ｈの場合、ｃとｂの値に対する制約はなく、ｃ＞ｂでもｃ＜ｂでもかまわない。また、このメッセージ認証コードは、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である（非特許文献２、非特許文献３）。
【非特許文献１】M. Bellare, R. Canetti, H. Krawczyk, “Keying hash functions for message authentication,” CRYPTO 1996, LNCS vol.1109, pp.1-15, Springer, Heidelberg (1996).
【非特許文献２】M. Bellare, “New proofs for NMAC and HMAC: Security without collision-resistance,” CRYPTO 2006, LNCS vol.4117, pp.602-619, Springer, Heidelberg (2006).
【非特許文献３】M. Bellare, R. Canetti, H. Krawczyk, “Pseudorandom functions revisited: The cascade construction and its concrete security,” IEEE Symposium on Foundations of Computer Science, pp.514-523 (1996).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に示したメッセージ認証コードでは、反復方法にマークル・ダンガード反復を用いているため、ｍビットのデータＭを処理するためには、１つのハッシュ関数で、約ｍ／ｂ回も圧縮関数ｈを呼び出す（繰り返す）必要があり、効率が悪かった。
本発明の目的は、安全性を維持しながら、関数の呼び出し回数（繰返し処理の回数）を少なくしたメッセージ認証コードを提供することである。
【課題を解決するための手段】
【０００６】
本発明のメッセージ認証子生成装置は、ハッシュ関数を用いた処理を行うハッシュ手段を１以上備え、データＭに対するメッセージ認証子τを出力する。本発明のメッセージ認証子生成装置内の少なくとも１つのハッシュ手段は、パディング部、メッセージブロック生成部、初期値設定部、中間変数計算部を備える。パディング部は、ハッシュ手段への入力Ｄに対して、あらかじめ定めたパディングを行うことでＮ×（ｃ＋ｂ）ビット（ただし、Ｎ、ｃ、ｂは正の整数）のビット列であるデータＭ＊を求める。メッセージブロック生成部は、データＭ＊を、Ｎ個のｃビットのメッセージブロックｍ２ｎ−１とＮ個のｂビットのメッセージブロックｍ２ｎ（ただし、ｎは１以上Ｎ以下の整数）に分割する。初期値設定部は、最初の中間変数ｖ０を求める。中間変数計算部は、中間変数ｖｎ−１とメッセージブロックｍ２ｎ−１との排他的論理和に、メッセージブロックｍ２ｎを結合したビット列を、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｈによって圧縮して中間変数ｖｎを求める。中間変数計算部は、この処理を、ｎ＝１からｎ＝Ｎまで繰り返して中間変数ｖＮを求める。そして、本発明のメッセージ認証子生成装置は、中間変数ｖＮに対して、後処理、またはマークル・ダンガード反復を用いたハッシュ関数での処理をさらに行う。
【０００７】
本発明のメッセージ認証子検証装置は、本発明のメッセージ認証子生成装置と比較部とを備え、データＭとメッセージ認証子τとを入力とし、データＭの検証を行う。メッセージ認証子生成装置は、データＭからメッセージ認証子τ’を生成する。比較部は、メッセージ認証子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【０００８】
本発明のメッセージ認証子生成装置によれば、ｍビットのデータＭを処理するためには、１つのハッシュ関数で約ｍ／（ｃ＋ｂ）回だけ圧縮関数ｈを呼び出せばよい。また、非特許文献３に記載されている方法を関係鍵攻撃モデルに適用することにより、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である。したがって、安全性を維持しながら、関数の呼び出し回数（繰返し処理の回数）を少なくできる。また、同じ効果がメッセージ認証子検証装置でも得られる。
【発明を実施するための最良の形態】
【０００９】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
まず、図３を用いて本発明のメッセージ認証子生成の原理を説明する。図３は、ハッシュ手段での圧縮関数ｈの呼び出し（繰返し）のイメージを示す図である。図３（Ａ）に非特許文献１のメッセージ認証コードの例を、図３（Ｂ）に本発明のメッセージ認証コードの例を示す。非特許文献１のメッセージ認証コードの場合、式（２）に示すように、中間変数ｖｎ−１にメッセージブロックｍｎを結合したビット列を、圧縮関数ｈによって圧縮して中間変数ｖｎを求める。一方、本発明のメッセージ認証コードの場合、中間変数ｖｎ−１とメッセージブロックｍ２ｎ−１との排他的論理和に、メッセージブロックｍ２ｎを結合したビット列を、圧縮関数ｈによって圧縮して中間変数ｖｎを求める。式で表現すると、
【数２】
0005006770.tif 000003
となる。つまり、データＭがｍビットの場合、非特許文献１のハッシュ手段は、約ｍ／ｂ回も圧縮関数ｈを呼び出す（繰り返す）。一方、本発明のハッシュ手段は、約ｍ／（ｃ＋ｂ）回だけ圧縮関数ｈを呼び出す（繰り返す）。したがって、圧縮関数ｈを呼び出す回数（繰返し回数）を少なくでき、効率的である。
【００１０】
図３（Ｃ）は第１実施形態、図３（Ｄ）は第２実施形態、図３（Ｅ）は第３実施形態での圧縮関数ｈの呼び出しのイメージを示す図である。各実施形態で、最初の中間変数の定め方と、中間変数ｖｎを求めた後の処理が異なる。
【００１１】
まず、最初の中間変数ｖ０の定め方についてまとめる。第１実施形態では、ｃビットのビット列である鍵Ｋ１＊を最初の中間変数ｖ０とする。第２実施形態では、ｃビットのビット列である鍵Ｋ＊とｂ個の“０”のビット列を結合したビット列を、圧縮関数ｈによって圧縮して最初の中間変数ｖ０を求める。第３実施形態では、ｃビットのビット列である鍵Ｋ＊とｂ個の“０”のビット列を結合したビット列を、圧縮関数ｈによって圧縮して最初の中間変数ｖ０を求める。
【００１２】
次に中間変数ｖｎを求めた後の処理についてまとめる。第１実施形態では、ｃビットのビット列である鍵Ｋ２＊と中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、圧縮関数ｈによって圧縮して変数ｚを求める。ただし、ｂ≧ｃでなければならない。第２実施形態では、鍵Ｋ＊とｂ個の“１”のビット列を結合したビット列を圧縮関数ｈによって圧縮したビット列と、中間変数ｖＮと、（ｂ−ｃ）個の“１”のビット列とを連結したビット列を、圧縮関数ｈによって圧縮して変数ｚを求める。ただし、ｂ≧ｃでなければならない。第３実施形態では、鍵Ｋ＊と中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、圧縮関数ｈによって圧縮して変数ｚを求める。ただし、ｂ＞ｃでなければならない。
【００１３】
このような原理なので、データＭがｍビットの場合、第１実施形態のハッシュ手段ではＮ＋１回、第２実施形態のハッシュ手段ではＮ＋３回、第３実施形態のハッシュ手段ではＮ＋２回圧縮関数ｈを呼び出す。また、第１実施形態のハッシュ手段には２つの鍵が必要であるが、第２実施形態と第３実施形態のハッシュ手段は１つの鍵でよい。
なお、どの実施形態でも、本発明のハッシュ手段を式（１）の２行目の処理の代わりに用い、中間変数ｖｎをハッシュ手段の出力ｖとしてもよい。この場合には、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを用いて、式（１）の３行目の処理を行い、メッセージ認証子τを求めればよい。したがって、中間変数ｖｎを求めた後の処理（後処理）は行わない。
【００１４】
［第１実施形態］
図４に本発明のメッセージ認証子生成装置の機能構成例を、図５にハッシュ手段の機能構成例を示す。また、図６に本発明のメッセージ認証子生成装置の処理フローを、図７にハッシュ手段の処理フローを示す。メッセージ認証子生成装置１００は、少なくとも鍵パディング手段１１０とハッシュ手段１２０を備えている。
鍵パディング手段１１０は、ｋビットの鍵Ｋをパディングなどによりｃビットの鍵Ｋ＊に変換する（Ｓ１１０）。具体的には、Ｋ＊←Ｋ‖０ｃ−ｋのようにパディングしてもよいし、Ｋ＊←Ｋ‖Ｋ‖・・・のようにしてもよい。
【００１５】
ハッシュ手段１２０は、パディング部１２１、メッセージブロック生成部１２２、初期値設定部１２３、中間変数計算部１２４、後処理部１２５を備える。パディング部１２１は、ハッシュ手段への入力Ｄに対して、あらかじめ定めたパディングを行うことでＮ×（ｃ＋ｂ）ビット（ただし、Ｎ、ｃ、ｂは正の整数）のビット列であるデータＭ＊を求める（Ｓ１２１）。メッセージブロック生成部１２２は、データＭ＊を、Ｎ個のｃビットのメッセージブロックｍ２ｎ−１とＮ個のｂビットのメッセージブロックｍ２ｎ（ただし、ｎは１以上Ｎ以下の整数）に分割する（Ｓ１２２）。初期値設定部１２３は、ｃビットのビット列である鍵Ｋ１＊を最初の中間変数ｖ０とする（Ｓ１２３）。中間変数計算部１２４は、中間変数ｖｎ−１とメッセージブロックｍ２ｎ−１との排他的論理和に、メッセージブロックｍ２ｎを結合したビット列を、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｈによって圧縮して中間変数ｖｎを求める。式で表現すると式（３）である。代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。中間変数計算部１２４は、この処理を、ｎ＝１からｎ＝Ｎまで繰り返して中間変数ｖＮを求める（Ｓ１２４）。後処理部１２５は、ｃビットのビット列である鍵Ｋ２＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める（Ｓ１２５）。
【００１６】
メッセージ認証子生成装置１００は、変数ｚをメッセージ認証子τとして出力してもよいし、変数ｚを用いてさらにハッシュ手段１２０で処理を行い、その結果をメッセージ認証子τとしてもよい。
また、メッセージ認証子生成装置１００は、ハッシュ手段１２０から後処理部１２５を削除し、ハッシュ手段９２０を備えてもよい。この場合は、ハッシュ手段１２０が計算した中間変数ｖＮを変数ｖとし、ハッシュ手段９２０が式（１）の３行目の処理を行えばよい。
【００１７】
第１実施形態のメッセージ認証子生成装置によれば、ｍビットのデータＭを処理するためには、１つのハッシュ関数でｍ／（ｃ＋ｂ）＋１回だけ圧縮関数ｈを呼び出せばよい。ただし、２つの鍵が必要である。また、非特許文献３に記載されている方法を関係鍵攻撃モデルに適用することにより、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である。したがって、安全性を維持しながら、関数の呼び出し回数（繰返し処理の回数）を少なくできる。
【００１８】
［第２実施形態］
第２実施形態も、図４がメッセージ認証子生成装置の機能構成例、図５がハッシュ手段の機能構成例である。また、図６がメッセージ認証子生成装置の処理フロー、図７がハッシュ手段の処理フローである。メッセージ認証子生成装置２００は、少なくとも鍵パディング手段１１０とハッシュ手段２２０を備えている。
【００１９】
ハッシュ手段２２０は、パディング部１２１、メッセージブロック生成部１２２、初期値設定部２２３、中間変数計算部１２４、後処理部２２５を備える。第１実施形態とは、初期値設定部２２３と後処理部２２５が異なる。初期値設定部２２３は、ｃビットのビット列である鍵Ｋ＊とｂ個の“０”のビット列を結合したビット列を、圧縮関数ｈによって圧縮し、最初の中間変数ｖ０を求める（Ｓ２２３）。後処理部２２５は、鍵Ｋ＊とｂ個の“１”のビット列を結合したビット列を圧縮関数ｈによって圧縮したビット列と、中間変数ｖＮと、（ｂ−ｃ）個の“１”のビット列とを連結したビット列を、圧縮関数ｈによって圧縮して変数ｚを求める（Ｓ２２５）。
【００２０】
メッセージ認証子生成装置２００も、変数ｚをメッセージ認証子τとして出力してもよいし、変数ｚを用いてさらにハッシュ手段２２０で処理を行い、その結果をメッセージ認証子τとしてもよい。
また、メッセージ認証子生成装置２００は、ハッシュ手段２２０から後処理部２２５を削除し、ハッシュ手段９２０を備えてもよい。この場合は、ハッシュ手段２２０が計算した中間変数ｖＮを変数ｖとし、ハッシュ手段９２０が式（１）の３行目の処理を行えばよい。
【００２１】
第２実施形態のメッセージ認証子生成装置によれば、ｍビットのデータＭを処理するためには、１つのハッシュ関数でｍ／（ｃ＋ｂ）＋３回だけ圧縮関数ｈを呼び出せばよい。また、鍵の数が１つでよい。さらに、非特許文献３に記載されている方法を関係鍵攻撃モデルに適用することにより、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である。したがって、安全性を維持しながら、関数の呼び出し回数（繰返し処理の回数）を少なくできる。
【００２２】
［第３実施形態］
第３実施形態も、図４がメッセージ認証子生成装置の機能構成例、図５がハッシュ手段の機能構成例である。また、図６がメッセージ認証子生成装置の処理フロー、図７がハッシュ手段の処理フローである。メッセージ認証子生成装置３００は、少なくとも鍵パディング手段１１０とハッシュ手段３２０を備えている。
ハッシュ手段３２０は、パディング部１２１、メッセージブロック生成部１２２、初期値設定部２２３、中間変数計算部１２４、後処理部３２５を備える。第２実施形態とは、後処理部３２５が異なる。後処理部３２５は、鍵Ｋ＊と前記中間変数ｖＮと（ｂ−ｃ）個の“１”のビット列を連結したビット列を、前記圧縮関数ｈによって圧縮して変数ｚを求める（Ｓ３２５）。
【００２３】
メッセージ認証子生成装置３００も、変数ｚをメッセージ認証子τとして出力してもよいし、変数ｚを用いてさらにハッシュ手段３２０で処理を行い、その結果をメッセージ認証子τとしてもよい。
また、メッセージ認証子生成装置３００は、ハッシュ手段３２０から後処理部３２５を削除し、ハッシュ手段９２０を備えてもよい。この場合は、ハッシュ手段２２０が計算した中間変数ｖＮを変数ｖとし、ハッシュ手段９２０が式（１）の３行目の処理を行えばよい。ただし、後処理部３２５を削除すると、第２実施形態と同じになる。
【００２４】
第３実施形態のメッセージ認証子生成装置によれば、ｍビットのデータＭを処理するためには、１つのハッシュ関数でｍ／（ｃ＋ｂ）＋２回だけ圧縮関数ｈを呼び出せばよい。また、鍵の数が１つでよい。さらに、非特許文献３に記載されている方法を関係鍵攻撃モデルに適用することにより、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である。したがって、安全性を維持しながら、関数の呼び出し回数（繰返し処理の回数）を少なくできる。
【００２５】
［第４実施形態］
図８に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図９に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置５００は、第１実施形態から第３実施形態で示したいずれかのメッセージ認証子生成装置１００、２００、または３００と比較部５１０と記録部５９０を備え、データＭとメッセージ認証子τが入力、検証結果が出力である。
【００２６】
メッセージ認証子検証装置５００内のメッセージ認証子生成装置１００（２００、３００）は、データＭとあらかじめ記録しておいた鍵Ｋからメッセージ認証子τ’を生成する（Ｓ１００、Ｓ２００、またはＳ３００）。比較部５１０は、メッセージ認証子τとメッセージ認証子τ’とを比較する。そして、τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。
【００２７】
このような構成なので、メッセージ認証子検証装置５００でも、メッセージ認証子生成装置１００（２００、３００）と同じ効果を得ることができる。
図１０に、コンピュータの機能構成例を示す。なお、本発明のメッセージ認証子生成装置およびメッセージ認証子検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００２８】
【図１】従来のメッセージ認証子生成装置の機能構成例を示す図。
【図２】従来のハッシュ手段の機能構成例を示す図。
【図３】本発明のメッセージ認証子生成の原理を説明する図。
【図４】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図５】本発明のハッシュ手段の機能構成例を示す図。
【図６】本発明のメッセージ認証子生成装置の処理フローを示す図。
【図７】本発明のハッシュ手段の処理フローを示す図。
【図８】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図９】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【図１０】コンピュータの機能構成例を示す図。
【符号の説明】
【００２９】
１００、２００、３００、９００  メッセージ認証子生成装置
１１０、９１０  鍵パディング手段
１２０、２２０、３２０、９２０  ハッシュ手段
１２１、９２１  パディング部
１２２、９２２  メッセージブロック生成部
１２３、２２３、９２３  初期値設定部
１２４、９２４  中間変数計算部
１２５、２２５、３２５  後処理部
５００  メッセージ認証子検証装置
５１０  比較部
５９０  記録部
【図１】
0005006770.tif 000004
【図２】
0005006770.tif 000005
【図３】
0005006770.tif 000006
【図４】
0005006770.tif 000007
【図５】
0005006770.tif 000008
【図６】
0005006770.tif 000009
【図７】
0005006770.tif 000010
【図８】
0005006770.tif 000011
【図９】
0005006770.tif 000012
【図１０】
0005006770.tif 000013