(57)【特許請求の範囲】
【請求項１】
データＭに対するメッセージ認証子ｔａｇを出力するメッセージ認証子生成装置であって、
Ｌ＋１個のｃビット（ただし、ｃはあらかじめ定めた整数）の鍵Ｋ１，…，ＫＬ，Ｋ’を出力する鍵パディング手段と、
Φ＝｛φｉ｝１≦ｉ≦Ｌ（ただし、Ｌは２以上の整数、φｉ：Ｍ→Ｄｉ）と表され、もしＭ≠Ｍ’ならば「φｉ（Ｍ）≠φｉ（Ｍ’）かつφｊ（Ｍ）≠φｊ（Ｍ’）となる１≦ｉ＜ｊ≦Ｌが存在する」という条件を満たすＤＩＬ関数Φを用いて、前記データＭから、Ｌ個のｂビット（ただし、ｂはあらかじめ定めた整数）の整数倍のデータＤ１，…，ＤＬを生成するＤＩＬ手段と、
前記データＤｉ（ただし、ｉは１以上Ｌ以下の整数）ごとに、ｃＡＵ関数と鍵Ｋｉを用いて、ｃビットの中間変数ｙｉを求めるｃＡＵ手段と、
Ｌ個の前記中間変数ｙ１，…，ｙＬから、擬似乱数関数族と鍵Ｋ’を用いて、メッセージ認証子ｔａｇを求める擬似乱数手段と
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記データＤｉのいずれかは、前記データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたビット列である
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
請求項１記載のメッセージ認証子生成装置であって、
Ｌは３以上の整数であり、
前記ＤＩＬ手段は、
ｂビットの整数倍のデータＭ＊を、Ｎ個のｂビットのメッセージブロックｍｎ（ただし、ｎは１以上Ｎ以下の整数）に分割するメッセージブロック生成部と、
ｉ＝１からｉ＝Ｌ−１の前記データＤｉを、メッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）（ただし、ｊは１以上の整数）を、ｊ＝１から
【数１】
0004914329.tif 000008
の範囲で連結したビット列とし、前記データＤＬを、ｉ＝１からｉ＝Ｌ−１のメッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）の排他的論理和を、ｊは１以上の整数）を、ｊ＝１から
【数２】
0004914329.tif 000009
の範囲で連結したビット列とするデータ生成部と
を備えることを特徴とするメッセージ認証子生成装置。
【請求項４】
データＭとメッセージ認証子ｔａｇとを入力とし、データＭの検証を行うメッセージ認証子検証装置であって、
前記データＭからメッセージ認証子ｔａｇ’を生成する請求項１から３のいずれかに記載のメッセージ認証子生成装置と、
前記メッセージ認証子ｔａｇと前記メッセージ認証子ｔａｇ’とを比較してデータＭの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項５】
データＭに対するメッセージ認証子ｔａｇを出力するメッセージ認証子生成方法であって、
鍵パディング手段で、Ｌ＋１個のｃビット（ただし、ｃはあらかじめ定めた整数）の鍵Ｋ１，…，ＫＬ，Ｋ’を出力する鍵パディングステップと、
ＤＩＬ手段で、Φ＝｛φｉ｝１≦ｉ≦Ｌ（ただし、Ｌは２以上の整数、φｉ：Ｍ→Ｄｉ）と表され、もしＭ≠Ｍ’ならば「φｉ（Ｍ）≠φｉ（Ｍ’）かつφｊ（Ｍ）≠φｊ（Ｍ’）となる１≦ｉ＜ｊ≦Ｌが存在する」という条件を満たすＤＩＬ関数Φを用いて、前記データＭから、Ｌ個のｂビット（ただし、ｂはあらかじめ定めた整数）の整数倍のデータＤ１，…，ＤＬを生成するＤＩＬステップと、
ｃＡＵ手段で、前記データＤｉ（ただし、ｉは１以上Ｌ以下の整数）ごとに、ｃＡＵ関数と鍵Ｋｉを用いて、ｃビットの中間変数ｙｉを求めるｃＡＵステップと、
擬似乱数手段で、Ｌ個の前記中間変数ｙ１，…，ｙＬから、擬似乱数関数族と鍵Ｋ’を用いて、メッセージ認証子ｔａｇを求める擬似乱数ステップと
を有するメッセージ認証子生成方法。
【請求項６】
請求項５記載のメッセージ認証子生成方法であって、
前記データＤｉのいずれかは、前記データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたビット列である
ことを特徴とするメッセージ認証子生成方法。
【請求項７】
請求項５記載のメッセージ認証子生成方法であって、
Ｌは３以上の整数であり、
前記ＤＩＬステップは、
ｂビットの整数倍のデータＭ＊を、Ｎ個のｂビットのメッセージブロックｍｎ（ただし、ｎは１以上Ｎ以下の整数）に分割するメッセージブロック生成サブステップと、
ｉ＝１からｉ＝Ｌ−１の前記データＤｉを、メッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）（ただし、ｊは１以上の整数）を、ｊ＝１から
【数３】
0004914329.tif 000010
の範囲で連結したビット列とし、前記データＤＬを、ｉ＝１からｉ＝Ｌ−１のメッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）の排他的論理和を、ｊは１以上の整数）を、ｊ＝１から
【数４】
0004914329.tif 000011
の範囲で連結したビット列とするデータ生成サブステップと
を有することを特徴とするメッセージ認証子生成方法。
【請求項８】
データＭとメッセージ認証子ｔａｇとを入力とし、データＭの検証を行うメッセージ認証子検証方法であって、
前記データＭからメッセージ認証子ｔａｇ’を生成する請求項５から７のいずれかに記載のメッセージ認証子生成方法の各ステップと、
比較部で、前記メッセージ認証子ｔａｇと前記メッセージ認証子ｔａｇ’とを比較してデータＭの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項９】
請求項１から４のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証が行えるようにするためのメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＭＡＣは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子ｔａｇを生成する（ｔａｇ←ＭＡＣＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＭＡＣと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
【０００３】
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵Ｋ（通常、鍵は１つだが、２つ以上の場合もある）とデータＭからメッセージ認証子ｔａｇを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子ｔａｇ’を生成する。そして、ｔａｇとｔａｇ’とを比較する。ｔａｇ＝ｔａｇ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。ｔａｇ≠ｔａｇ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００４】
従来のメッセージ認証コードには、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを２回適用して安全性を高めたもの（非特許文献１）などがある。非特許文献１のメッセージ認証コードＭＡＣＫ（Ｍ）は、次式のようにメッセージ認証子ｔａｇを求める。
【０００５】
【数５】
0004914329.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).
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１のメッセージ認証コードＭＡＣＫ（Ｍ）の安全性は、誕生日限界と呼ばれるレベルまでしか保証されておらず、実際に誕生日攻撃に弱い。そこで、本発明の目的は、誕生日限界を超える安全性を有するメッセージ認証コードを提供することである。
【課題を解決するための手段】
【０００７】
本発明のメッセージ認証子生成装置は、鍵パディング手段、ＤＩＬ手段、ｃＡＵ手段、擬似乱数手段を備える。鍵パディング手段は、Ｌ＋１個のｃビット（ただし、ｃはあらかじめ定めた整数）の鍵Ｋ１，…，ＫＬ，Ｋ’を出力する。あらかじめＬ＋１個の鍵Ｋ１，…，ＫＬ，Ｋ’を記録しておいてもよいし、１つの鍵ＫからＬ＋１個の鍵を生成してもよい。ＤＩＬ手段は、ＤＩＬ関数Φを用いて、データＭから、Ｌ個（ただし、Ｌは２以上の整数）のｂビット（ただし、ｂはあらかじめ定めた整数）の整数倍のデータＤ１，…，ＤＬを生成する。ｃＡＵ手段は、データＤｉ（ただし、ｉは１以上Ｌ以下の整数）ごとに、ｃＡＵ関数と鍵Ｋｉを用いて、ｃビットの中間変数ｙｉを求める。擬似乱数手段は、Ｌ個の前記中間変数ｙ１，…，ｙＬから、擬似乱数関数族を用いて、メッセージ認証子ｔａｇを求める。
なお、ＤＩＬ関数Φは、Ｌを２以上の整数とするときに、
Φ＝｛φｉ｝１≦ｉ≦Ｌ
と表される関数であり（ただし、φｉ：Ｍ→Ｄｉ）、もしＭ≠Ｍ’ならば「φｉ（Ｍ）≠φｉ（Ｍ’）かつφｊ（Ｍ）≠φｊ（Ｍ’）となる１≦ｉ＜ｊ≦Ｌが存在する」という条件を満たす関数である。
【０００８】
ＤＩＬ手段は、例えば、データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたビット列を、すべてのデータＤ１，…，ＤＬとしてもよい（この場合は、Ｄ１＝Ｄ２＝…＝ＤＬ）。あるいは、ＤＩＬ手段を以下のようにしてもよい。ＤＩＬ手段に、パディング部、メッセージブロック生成部、データ生成部を備えさせる。そして、パディング部で、データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたデータＭ＊を求める。なお、ＤＩＬ手段に入力されるデータＭが、ｂビットの整数倍に限定されるのであれば、パディング部は不要である。メッセージブロック生成部で、ｂビットの整数倍のデータＭ＊を、Ｎ個のｂビットのメッセージブロックｍｎ（ただし、ｎは１以上Ｎ以下の整数）に分割する。データ生成部で、ｉ＝１からｉ＝Ｌ−１のデータＤｉを、メッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）（ただし、ｊは１以上の整数）を、ｊ＝１から
【０００９】
【数６】
0004914329.tif 000003
の範囲で連結したビット列とし、データＤＬを、ｉ＝１からｉ＝Ｌ−１のメッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）の排他的論理和を、ｊは１以上の整数）を、ｊ＝１から
【００１０】
【数７】
0004914329.tif 000004
の範囲で連結したビット列とする。
本発明のメッセージ認証子検証装置は、本発明のメッセージ認証子生成装置と比較部とを備え、データＭとメッセージ認証子τとを入力とし、データＭの検証を行う。メッセージ認証子生成装置は、データＭからメッセージ認証子ｔａｇ’を生成する。比較部は、メッセージ認証子ｔａｇとメッセージ認証子ｔａｇ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【００１１】
本発明のメッセージ認証子生成装置は、ＤＩＬ手段によって、メッセージが異なれば少なくとも２列分は異なっているＬ列分のデータが出力され、各データはそれぞれｃＡＵ手段によって並列に処理され、Ｌ個の出力全てが同時に擬似乱数手段によって処理される。したがって、従来のような１列のｃＡＵ手段と擬似乱数手段を用いた方法に比べ、セキュリティレベルは２倍となり、誕生日限界を超えるセキュリティを確保できる。
【００１２】
さらに、ＤＩＬ手段で、例えば排他的論理和を用いた方法を採用すれば、データＭを分割してデータＤ１，…，ＤＬを生成でき、列ごとのｃＡＵ手段の処理量が減少するので、処理量を並列な処理を行わない場合に近づけることができる。したがって、処理量の増加を抑えながら、誕生日限界を超えたセキュリティレベルを確保できる。
【発明を実施するための最良の形態】
【００１３】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
【００１４】
［第１実施形態］
図３に、本発明のメッセージ認証子生成装置の機能構成例を示す。また、図４に、本発明のメッセージ認証子生成装置の処理フローを示す。さらに、図５に、Ｌ＝２の場合の本実施形態のＤＩＬ手段、ｃＡＵ手段、擬似乱数手段での処理を示す。メッセージ認証子生成装置１００は、鍵パディング手段１１０、ＤＩＬ手段１２０、ｃＡＵ手段１３０、擬似乱数手段１４０を備える。
【００１５】
なお、以下の説明で使用するｃＡＵ関数と擬似乱数関数族の定義は非特許文献１に示されており、この定義に従う。ＤＩＬ関数Φは、Ｌを２以上の整数とするときに、
Φ＝｛φｉ｝１≦ｉ≦Ｌ
と表される関数であり（ただし、φｉ：Ｍ→Ｄｉ）、もしＭ≠Ｍ’ならば「φｉ（Ｍ）≠φｉ（Ｍ’）かつφｊ（Ｍ）≠φｊ（Ｍ’）となる１≦ｉ＜ｊ≦Ｌが存在する」という条件を満たす関数である。言い換えれば、「φｉ（Ｍ）＝φｉ（Ｍ’）が少なくともＬ−１個の値ｉ∈｛１，２，…，Ｌ｝について満たされるならば、Ｍ＝Ｍ’が成立する」という条件を満たす関数である。
【００１６】
鍵パディング手段１１０は、ｃビット（ただし、ｃはあらかじめ定めた整数）のＬ＋１個の鍵Ｋ１，…，ＫＬ，Ｋ’を出力する（Ｓ１１０）。なお、Ｌ＋１個の鍵Ｋ１，…，ＫＬ，Ｋ’は、１つの鍵から生成することもできる。したがって、何個の鍵を記録しておき、どのようにＬ＋１個の鍵Ｋ１，…，ＫＬ，Ｋ’を生成するのかは適宜設計すればよい。
【００１７】
ＤＩＬ手段１２０は、ＤＩＬ関数Φを用いて、データＭから、Ｌ個（ただし、Ｌは２以上の整数）のｂビット（ただし、ｂはあらかじめ定めた整数）の整数倍のデータＤ１，…，ＤＬ＝ｍ１‖ｍ２‖…‖ｍＮ（ただし、ｍｎはｂビットのビット列である。ここで、ｎは１以上Ｎ以下の整数である。）を生成する（Ｓ１２０）。データＤ１，…，ＤＬは、データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたビット列である（この場合は、Ｄ１＝Ｄ２＝…＝ＤＬ）。または、データＭをパディングなどによってｂビットの整数倍にしたビット列Ｍ＊を、ＤＩＬ手段１２０への入力とし、ＤＩＬ手段１２０ではパディングは行わないこととしてもよい。
【００１８】
ｃＡＵ手段１３０は、データＤｉ（ただし、ｉは１以上Ｌ以下の整数）ごとに、ｃＡＵ関数と鍵Ｋｉを用いて、ｃビットの中間変数ｙｉを求める（Ｓ１３０−１，…，Ｓ１３０−Ｌ）。具体的には、ｂビットのビット列ｍ１とｃビットの鍵Ｋｉを圧縮関数ｆでｃビットに圧縮する。そして、その圧縮の結果とｂビットのビット列ｍ２を圧縮関数ｆでｃビットに圧縮する。このように、圧縮関数ｆを繰り返し呼び出すことで、中間変数ｙｉを求める。なお、Ｌ個のｃＡＵ関数の処理（Ｓ１３０−１，…，Ｓ１３０−Ｌ）は、Ｌ個のｃＡＵ手段（１３０−１，…，１３０−Ｌ）によって実行してもよいし、１個のｃＡＵ手段１３０によって実行してもよい。また、代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。
【００１９】
擬似乱数手段１４０は、Ｌ個の前記中間変数ｙ１，…，ｙＬから、擬似乱数関数族と鍵Ｋ’を用いて、メッセージ認証子ｔａｇを求める（Ｓ１４０）。例えば、圧縮関数ｆに、ｂビットのビット列ｙ１‖…‖ｙＬ‖０ｂ-Ｌｃとｃビットの鍵Ｋ’を入力し、メッセージ認証子ｔａｇを求めればよい。ただし、この例の場合、Ｌｃ≦ｂでなければならない。
【００２０】
本実施形態のメッセージ認証子生成装置は、ｃＡＵ手段によってＬ列の並列な処理を行うので、セキュリティレベルを上げることができる。例えば、Ｌを２にすることでセキュリティレベルは２倍となり、誕生日限界を超えるセキュリティを確保できる。ただし、Ｌを増やしすぎても、セキュリティレベルが無駄に高くなるだけである。一方、Ｌを増やすと処理量が増加してしまうという欠点がある。
【００２１】
［第２実施形態］
第１実施形態では、Ｌを増やすと処理量が増加してしまった。本実施形態では、ＤＩＬ関数の設計によってＬを増やすことで処理量を軽減する方法を示す。
【００２２】
本実施形態のメッセージ認証子生成装置の機能構成例も図３に示す。また、本発明のメッセージ認証子生成装置の処理フローも図４に示す。図６に本実施形態のＤＩＬ手段の機能構成、図７に本実施形態のＤＩＬ手段の処理フローを示す。さらに、図８に、Ｌ＝３の場合の本実施形態のＤＩＬ手段、ｃＡＵ手段、擬似乱数手段での処理を示す。
【００２３】
メッセージ認証子生成装置２００は、鍵パディング手段１１０、ＤＩＬ手段２２０、ｃＡＵ手段１３０、擬似乱数手段１４０を備える。
なお、第１実施形態と同じように、以下の説明で使用するｃＡＵ関数と擬似乱数関数族の定義は非特許文献１に示されており、この定義に従う。ＤＩＬ関数Φは、Ｌを２以上の整数とするときに、
Φ＝｛φｉ｝１≦ｉ≦Ｌ
と表される関数であり（ただし、φｉ：Ｍ→Ｄｉ）、もしＭ≠Ｍ’ならば「φｉ（Ｍ）≠φｉ（Ｍ’）かつφｊ（Ｍ）≠φｊ（Ｍ’）となる１≦ｉ＜ｊ≦Ｌが存在する」という条件を満たす関数である。言い換えれば、「φｉ（Ｍ）＝φｉ（Ｍ’）が少なくともＬ−１個の値ｉ∈｛１，２，…，Ｌ｝について満たされるならば、Ｍ＝Ｍ’が成立する」という条件を満たす関数である。
【００２４】
鍵パディング手段１１０は、第１実施形態と同じであり、Ｌ＋１個の鍵Ｋ１，…，ＫＬ，Ｋ’を出力する（Ｓ１１０）。ＤＩＬ手段２２０は、図６に示すように、パディング部２２１、メッセージブロック生成部２２２、データ生成部２２３を備える。パディング部２２１で、データＭに対して、あらかじめ定めたパディングを行うことでｂビットの整数倍にしたデータＭ＊を求める（Ｓ２２１）。なお、ＤＩＬ手段２２０に入力されるデータＭが、ｂビットの整数倍に限定されるのであれば、パディング部２２１は不要である。メッセージブロック生成部２２２で、データＭ＊を、Ｎ個のｂビットのメッセージブロックｍｎ（ただし、ｎは１以上Ｎ以下の整数）に分割する（Ｓ２２２）。データ生成部２２３で、ｉ＝１からｉ＝Ｌ−１のデータＤｉを、メッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）（ただし、ｊは１以上の整数）を、ｊ＝１から
【００２５】
【数８】
0004914329.tif 000005
の範囲で連結したビット列とする。例えば、Ｌ＝３、Ｎが偶数の場合は、Ｄ１＝ｍ１‖ｍ３‖…‖ｍＮ−１、Ｄ２＝ｍ２‖ｍ４‖…‖ｍＮとなる（図８）。また、データＤＬを、ｉ＝１からｉ＝Ｌ−１のメッセージブロックｍｉ＋（ｊ−１）（Ｌ−１）の排他的論理和を、ｊは１以上の整数）を、ｊ＝１から
【００２６】
【数９】
0004914329.tif 000006
の範囲で連結したビット列とする（Ｓ２２３）。例えば、Ｌ＝３、Ｎが偶数の場合は、
【００２７】
【数１０】
0004914329.tif 000007
となる（図８）。
【００２８】
ｃＡＵ手段１３０は、第１実施形態と同じように、データＤｉ（ただし、ｉは１以上Ｌ以下の整数）ごとに、ｃＡＵ関数と鍵Ｋｉを用いて、ｃビットの中間変数ｙｉを求める（Ｓ１３０−１，…，Ｓ１３０−Ｌ）。
【００２９】
擬似乱数手段１４０は、第１実施形態と同じように、Ｌ個の前記中間変数ｙ１，…，ｙＬから、擬似乱数関数族と鍵Ｋ’を用いて、メッセージ認証子ｔａｇを求める（Ｓ１４０）。
【００３０】
本実施形態のＤＩＬ手段では、データＭ＊をデータＤ１，…，ＤＬ−１に分配するので、Ｄｉのビット数は、データＭ＊のビット数のＬ−１分の１になる。したがて、ｃＡＵ手段で圧縮関数ｆを呼び出す回数は、非特許文献１の方法で圧縮関数ｆを呼び出す回数の１＋１／（Ｌ−１）倍となる。つまり、Ｌ＝２の場合は２倍、Ｌ＝３の場合は１．５倍、Ｌ＝４の場合は１．３３倍である。このようにＬを増やすことで処理量を減少できる。ただし、Ｌを増やすと必要な鍵の数が増える。したがって、処理量、記録容量などを考慮し、Ｌの値を適宜設計すればよい。
【００３１】
本実施形態のメッセージ認証子生成装置は、ｃＡＵ手段によってＬ列の並列な処理を行うので、第１実施形態と同じように、誕生日限界を超えるセキュリティを確保できる。さらに、処理量を抑えながら誕生日限界を超えるセキュリティを確保できる（効率がよい）。
【００３２】
［第３実施形態］
図９に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図１０に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置５００は、第１実施形態、第２実施形態で示したいずれかのメッセージ認証子生成装置１００または２００と比較部５１０と記録部５９０を備え、データＭとメッセージ認証子ｔａｇが入力、検証結果が出力である。
【００３３】
メッセージ認証子検証装置５００内のメッセージ認証子生成装置１００（２００）は、データＭからメッセージ認証子ｔａｇ’を生成する（Ｓ１００、またはＳ２００）。比較部５１０は、メッセージ認証子ｔａｇとメッセージ認証子ｔａｇ’とを比較する。そして、ｔａｇ＝ｔａｇ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。ｔａｇ≠ｔａｇ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。
【００３４】
このような構成なので、メッセージ認証子検証装置５００でも、メッセージ認証子生成装置１００（２００）と同じ効果を得ることができる。
【００３５】
図１１に、コンピュータの機能構成例を示す。なお、本発明のメッセージ認証子生成装置およびメッセージ認証子検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００３６】
【図１】従来のメッセージ認証子生成装置の機能構成例を示す図。
【図２】従来のハッシュ手段の機能構成例を示す図。
【図３】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図４】本発明のメッセージ認証子生成装置の処理フローを示す図。
【図５】Ｌ＝２の場合の第１実施形態のＤＩＬ手段、ｃＡＵ手段、擬似乱数手段での処理を示す図。
【図６】第２実施形態のＤＩＬ手段の機能構成例を示す図。
【図７】第２実施形態のＤＩＬ手段の処理フローを示す図。
【図８】Ｌ＝３の場合の第２実施形態のＤＩＬ手段、ｃＡＵ手段、擬似乱数手段での処理を示す図。
【図９】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図１０】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【図１１】コンピュータの機能構成例を示す図。
【符号の説明】
【００３７】
１００、２００、９００  メッセージ認証子生成装置
１１０、９１０  鍵パディング手段      １２０、２２０  ＤＩＬ手段
１３０  ｃＡＵ手段                    １４０  擬似乱数手段
２２１、９２１  パディング部          ２２２、９２２  メッセージブロック生成部
２２３  データ生成部                  ５００  メッセージ認証子検証装置
５１０  比較部                        ５９０  記録部
９２０  ハッシュ手段                  ９２３  初期値設定部
９２４  中間変数計算部
【図１】
0004914329.tif 000012
【図２】
0004914329.tif 000013
【図３】
0004914329.tif 000014
【図４】
0004914329.tif 000015
【図５】
0004914329.tif 000016
【図６】
0004914329.tif 000017
【図７】
0004914329.tif 000018
【図８】
0004914329.tif 000019
【図９】
0004914329.tif 000020
【図１０】
0004914329.tif 000021
【図１１】
0004914329.tif 000022