(57)【特許請求の範囲】
【請求項１】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成装置であって、
前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成するパディング部と、
前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割部と、
前記データｍ１，…，ｍＮの排他的論理和
【数１】
0004914381.tif 000012
を計算し、第１チェックサムＳ１とする第１チェックサム計算部と、
ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定め、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【数２】
0004914381.tif 000013
（ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列）をＮ回繰り返して中間変数ｖＮを求める中間変数計算部と、
中間変数ｖ１，…，ｖＮの排他的論理和
【数３】
0004914381.tif 000014
を計算し、第２チェックサムＳ２とする第２チェックサム計算部と、
計算
【数４】
0004914381.tif 000015
（ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数）によってメッセージ認証子τを求める後処理部と
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記ｂが５１２、ｘが有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体の乗法群の元、ビット列Δ０が
【数５】
0004914381.tif 000016
で求められるビット列の先頭のｂビット、“・”が拡大体の乗算を示す記号であるときに、
ビット列Δｎをｘｎ・Δ０、ビット列Δ’ｊをｘＮ・（ｘ＋１）ｊ・Δ０とする
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証装置であって、
前記データＤからメッセージ認証子τ’を生成する請求項１または２記載のメッセージ認証子生成装置と、
前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項４】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成方法であって、
パディング部が、前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成するパディングステップと、
メッセージ分割部が、前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割ステップと、
第１チェックサム計算部が、前記データｍ１，…，ｍＮの排他的論理和
【数６】
0004914381.tif 000017
を計算し、第１チェックサムＳ１とする第１チェックサム計算ステップと、
中間変数計算部が、ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定め、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【数７】
0004914381.tif 000018
（ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列）をＮ回繰り返して中間変数ｖＮを求める中間変数計算ステップと、
第２チェックサム計算部が、中間変数ｖ１，…，ｖＮの排他的論理和
【数８】
0004914381.tif 000019
を計算し、第２チェックサムＳ２とする第２チェックサム計算ステップと、
後処理部が、計算
【数９】
0004914381.tif 000020
（ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数）によってメッセージ認証子τを求める後処理ステップと
を有するメッセージ認証子生成方法。
【請求項５】
請求項４記載のメッセージ認証子生成方法であって、
前記ｂが５１２、ｘが有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体の乗法群の元、ビット列Δ０が
【数１０】
0004914381.tif 000021
で求められるビット列の先頭のｂビット、“・”が拡大体の乗算を示す記号であるときに、
ビット列Δｎをｘｎ・Δ０、ビット列Δ’ｊをｘＮ・（ｘ＋１）ｊ・Δ０とする
ことを特徴とするメッセージ認証子生成方法。
【請求項６】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証方法であって、
前記データＤからメッセージ認証子τ’を生成する請求項４または５記載のメッセージ認証子生成方法の各ステップと、
比較部で、前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項７】
請求項１から３のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【請求項８】
請求項７記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証が行えるようにするためのメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＭＡＣは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子τを生成する（τ←ＭＡＣＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＭＡＣと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
【０００３】
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵Ｋ（通常、鍵は１つだが、２つ以上の場合もある）とデータＭからメッセージ認証子τを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子τ’を生成する。そして、τとτ’とを比較する。τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００４】
従来のメッセージ認証コードには、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを２回適用して安全性を高めたもの（非特許文献１）などがある。非特許文献１のメッセージ認証コードＭＡＣＫ（Ｍ）は、次式のようにメッセージ認証子τを求める。
【０００５】
【数１１】
0004914381.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).
【非特許文献３】K. Yasuda, “Multilane HMAC - Security beyond the Birthday Limit,” INDOCRYPT 2007, LNCS vol.4859, pp.18-32, Springer, Heidelberg (2007).
【発明の開示】
【発明が解決しようとする課題】
【０００７】
非特許文献１に示したメッセージ認証コードでは、反復方法にマークル・ダンガード反復を用いているため、ｍビットのデータＭを処理するためには、１つのハッシュ関数で、約ｍ／ｂ回圧縮関数ｈを呼び出す（繰り返す）必要がある。そして、高い安全性を有する非特許文献３の方法は、圧縮関数を呼び出す回数がｍ／ｂ回よりも多くなる。しかも、圧縮関数を呼び出す回数のｍ／ｂ回よりも多い部分も、ｍに依存しているため、処理量が多くなるという問題があった。
【０００８】
本発明の目的は、高い安全性を確保しながら、ｍ／ｂ回を超える圧縮関数を呼び出す回数がｍに依存しないようなメッセージ認証子生成方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明のメッセージ認証子生成装置は、データＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置は、パディング部、メッセージ分割部、第１チェックサム計算部、中間変数計算部、第２チェックサム計算部、後処理部を備える。パディング部は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成する。メッセージ分割部は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する。第１チェックサム計算部は、データｍ１，…，ｍＮの排他的論理和
【００１０】
【数１２】
0004914381.tif 000003
を計算し、第１チェックサムＳ１とする。中間変数計算部は、ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定め、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【００１１】
【数１３】
0004914381.tif 000004
（ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列）をＮ回繰り返して中間変数ｖＮを求める。第２チェックサム計算部は、中間変数ｖ１，…，ｖＮの排他的論理和
【００１２】
【数１４】
0004914381.tif 000005
を計算し、第２チェックサムＳ２とする。後処理部は、計算
【００１３】
【数１５】
0004914381.tif 000006
（ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数）によってメッセージ認証子τを求める。
【００１４】
また、本発明のメッセージ認証子検証装置は、本発明のメッセージ認証子生成装置と比較部とを備え、データＭとメッセージ認証子τとを入力とし、データＭの検証を行う。メッセージ認証子生成装置は、データＭからメッセージ認証子τ’を生成する。比較部は、メッセージ認証子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【００１５】
本発明のメッセージ認証子生成方法によれば、ｍビットのデータＭを処理するために、ｍ／ｂ回を超える圧縮関数を呼び出す回数をｍに依存しない少ない回数にできる。また、高い安全性も確保できる。
【発明を実施するための最良の形態】
【００１６】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
【００１７】
［第１実施形態］
図３に、本発明のメッセージ認証子生成装置の機能構成例を示す。また、図４に、本発明のメッセージ認証子生成装置の処理フロー例を示す。さらに、図５に、各構成部での処理の流れを示す。メッセージ認証子生成装置１００は、任意のビット長（メッセージ長）のデータＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置１００は、パディング部１１０、メッセージ分割部１２０、第１チェックサム計算部１３０、中間変数計算部１４０、第２チェックサム計算部１５０、後処理部１６０を備える。
【００１８】
パディング部１１０は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成する（Ｓ１１０）。メッセージ分割部１２０は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する（Ｓ１２０）。第１チェックサム計算部１３０は、データｍ１，…，ｍＮの排他的論理和
【００１９】
【数１６】
0004914381.tif 000007
を計算し、第１チェックサムＳ１とする（Ｓ１３０）。中間変数計算部１４０は、まず、ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定める。例えば、ｃ個の“０”からなるビット列とあらかじめ定めておいてもよい。ｎ＝１からｎ＝Ｎまで順番に、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【００２０】
【数１７】
0004914381.tif 000008
を行う。この繰り返し処理で、中間変数ｖＮを求める（Ｓ１４０）。ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列である。例えば、ｆｋ（ｍ）は、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｆを用いて、
ｆｋ（ｍ）：＝ｆ（ｋ‖ｍ）                                  （９）
のように定義すればよい。また、代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。
【００２１】
第２チェックサム計算部１５０は、中間変数ｖ１，…，ｖＮの排他的論理和
【数１８】
0004914381.tif 000009
を計算し、第２チェックサムＳ２とする（Ｓ１５０）。後処理部１６０は、計算
【００２２】
【数１９】
0004914381.tif 000010
によってメッセージ認証子τを求める（Ｓ１６０）。ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数である。なお、Δ１，…，ΔＮ、およびΔ’１，Δ’２，Δ’３は互いに異なるビット列である。
【００２３】
例えば、圧縮関数がｓｈａ１やｓｈａ２５６のようなｂ＝５１２の場合であれば、Δ１，…，ΔＮ、およびΔ’１，Δ’２，Δ’３を次のように決めればよい。有限体ＧＦ（２）上の既約多項式ｘ５１２＋ｘ１２＋ｘ７＋ｘ２＋１の剰余環によって表現される有限体ＧＦ（２）の拡大体の乗法群を考える。この乗法群において単項式ｘ（の同値類）という元を考えると、元ｘは、ほとんど全ての非零元を生成するが、位数１７の部分群を生成しない。一方、元ｘ＋１は位数１７の部分群を生成する。そこで、まず、ビット列Δ０を
【００２４】
【数２０】
0004914381.tif 000011
で求められるビット列の先頭のｂビットとする。そして、ビット列Δｎをｘｎ・Δ０、ビット列Δ’ｊをｘＮ・（ｘ＋１）ｊ・Δ０とする。ただし、“・”は拡大体の乗算を示す記号である。
【００２５】
このように構成するので、本発明のメッセージ認証子生成装置は、誕生日限界を超える高い安全性を有する。また、図５から分かるように、本発明のメッセージ認証子生成装置は、ｂ×Ｎビット（メッセージ長ｍ）のデータＭのメッセージ認証子τを求めるために、Ｎ＋３回圧縮関数を呼び出している。つまり、圧縮関数を呼び出す回数のｍ／ｂ回（Ｎ回に相当）よりも多い部分は、３回だけである。また、メッセージ長ｍに依存しない定数にできている。
【００２６】
［第２実施形態］
図６に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図７に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置５００は、第１実施形態で示したメッセージ認証子生成装置１００と比較部５１０と記録部５９０を備え、データＭとメッセージ認証子τが入力、検証結果が出力である。
【００２７】
メッセージ認証子検証装置５００内のメッセージ認証子生成装置１００は、データＤからメッセージ認証子τ’を生成する（Ｓ１００）。比較部５１０は、メッセージ認証子τとメッセージ認証子τ’とを比較する。そして、τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。
【００２８】
このような構成なので、メッセージ認証子検証装置５００でも、メッセージ認証子生成装置１００と同じ効果を得ることができる。
【００２９】
図８に、コンピュータの機能構成例を示す。なお、本発明のメッセージ認証子生成装置およびメッセージ認証子検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００３０】
【図１】従来のメッセージ認証子生成装置の機能構成例を示す図。
【図２】ハッシュ手段９２０の機能構成例を示す図。
【図３】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図４】本発明のメッセージ認証子生成装置の処理フロー例を示す図。
【図５】本発明のメッセージ認証子生成装置の各構成部での処理の流れを示す図。
【図６】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図７】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【図８】コンピュータの機能構成例を示す図。
【符号の説明】
【００３１】
１００、９００  メッセージ認証子生成装置    １１０、９２１  パディング部
１２０  メッセージ分割部                    １３０  チェックサム計算部
１４０、９２４  中間変数計算部              １５０  チェックサム計算部
１６０  後処理部                            ５００  メッセージ認証子検証装置
５１０  比較部                              ５９０  記録部
９１０  鍵パディング手段                    ９２０  ハッシュ手段
９２２  メッセージブロック生成部            ９２３  初期設定部
【図１】
0004914381.tif 000022
【図２】
0004914381.tif 000023
【図３】
0004914381.tif 000024
【図４】
0004914381.tif 000025
【図５】
0004914381.tif 000026
【図６】
0004914381.tif 000027
【図７】
0004914381.tif 000028
【図８】
0004914381.tif 000029