メッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、およびプログラム
【課題】時間のかかる圧縮関数を用いる処理に、並列処理を利用する。
【解決手段】本発明のメッセージ認証子生成装置は、パディング部、メッセージ分割部、第１排他的論理和計算部、中間変数計算部、重み付き排他的論理和計算部、第２排他的論理和計算部、後処理部を備える。第１排他的論理和計算部は、データｍ１，…，ｍＮの排他的論理和をＳＭとする。中間変数計算部は、Δ・２ｎとｍｎとの排他的論理和を圧縮関数への入力として中間変数ｖ０，…，ｖＮ−１を求める。重み付き排他的論理和計算部は、中間変数ｖ０，…，ｖＮ−１の重み付き排他的論理和をＷとする。第２排他的論理和計算部は、中間変数ｖ０，…，ｖＮ−１の排他的論理和をＳＶとする。後処理部は、ＳＭ、Ｗ、ＳＶから圧縮関数を用いてメッセージ認証子τを求める。
【解決手段】本発明のメッセージ認証子生成装置は、パディング部、メッセージ分割部、第１排他的論理和計算部、中間変数計算部、重み付き排他的論理和計算部、第２排他的論理和計算部、後処理部を備える。第１排他的論理和計算部は、データｍ１，…，ｍＮの排他的論理和をＳＭとする。中間変数計算部は、Δ・２ｎとｍｎとの排他的論理和を圧縮関数への入力として中間変数ｖ０，…，ｖＮ−１を求める。重み付き排他的論理和計算部は、中間変数ｖ０，…，ｖＮ−１の重み付き排他的論理和をＷとする。第２排他的論理和計算部は、中間変数ｖ０，…，ｖＮ−１の排他的論理和をＳＶとする。後処理部は、ＳＭ、Ｗ、ＳＶから圧縮関数を用いてメッセージ認証子τを求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証が行えるようにするためのメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、およびプログラムに関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＭＡＣは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子τを生成する（τ←ＭＡＣＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＭＡＣと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
【０００３】
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵Ｋ（通常、鍵は１つだが、２つ以上の場合もある）とデータＭからメッセージ認証子τを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子τ’を生成する。そして、τとτ’とを比較する。τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００４】
従来のメッセージ認証コードには、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを２回適用して安全性を高めたものとして、非特許文献１などがある。また、圧縮関数を用いたメッセージ認証コードであって、いわゆる誕生日限界を超えるような高い安全性を有するものには、例えば非特許文献２の構成法がある。しかし、非特許文献２の方法では、圧縮関数を呼び出す回数が、データＭを圧縮関数に入力するために分割した数よりも多くなる。しかも、分割数を越えて圧縮関数を呼び出す回数も、データＭの長さに依存しているため、処理量が多くなるという問題があった。
【０００５】
高い安全性を確保しながら、分割数を超える圧縮関数を呼び出す回数がデータＭの長さに依存しないようなメッセージ認証子生成方法として、特許文献１の方法がある。特許文献１のメッセージ認証子生成装置の構成を図１に、処理フローを図２に示す。さらに、図３に、各構成部での処理の流れを示す。メッセージ認証子生成装置１００は、任意のビット長（メッセージ長）のデータＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置１００は、パディング部１１０、メッセージ分割部１２０、第１チェックサム計算部１３０、中間変数計算部１４０、第２チェックサム計算部１５０、後処理部１６０を備える。
【０００６】
パディング部１１０は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成する（Ｓ１１０）。メッセージ分割部１２０は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する（Ｓ１２０）。第１チェックサム計算部１３０は、データｍ１，…，ｍＮの排他的論理和
【０００７】
【数１】
【０００８】
を計算し、第１チェックサムＳ１とする（Ｓ１３０）。中間変数計算部１４０は、まず、ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定める。例えば、ｃ個の“０”からなるビット列とあらかじめ定めておいてもよい。ｎ＝１からｎ＝Ｎまで順番に、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【０００９】
【数２】
【００１０】
を行う。この繰り返し処理で、中間変数ｖＮを求める（Ｓ１４０）。ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列である。例えば、ｆｋ（ｍ）は、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｆを用いて、
ｆｋ（ｍ）：＝ｆ（ｋ‖ｍ）
のように定義すればよい。また、代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。
【００１１】
第２チェックサム計算部１５０は、中間変数ｖ１，…，ｖＮの排他的論理和
【００１２】
【数３】
【００１３】
を計算し、第２チェックサムＳ２とする（Ｓ１５０）。後処理部１６０は、計算
【００１４】
【数４】
【００１５】
によってメッセージ認証子τを求める（Ｓ１６０）。ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数である。なお、Δ１，…，ΔＮ、およびΔ’１，Δ’２，Δ’３は互いに異なるビット列である。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００９−１８８７９４号公報
【非特許文献】
【００１７】
【非特許文献１】M. Bellare, R. Canetti, H. Krawczyk, “Keying hash functions for message authentication,” CRYPTO 1996, LNCS vol.1109, pp.1-15, Springer, Heidelberg (1996).
【非特許文献２】K. Yasuda, “Multilane HMAC - Security beyond the Birthday Limit,” INDOCRYPT 2007, LNCS vol.4859, pp.18-32, Springer, Heidelberg (2007).
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、従来技術は特許文献１のメッセージ認証子生成装置では、圧縮関数を用いる中間変数計算部１４０は、ｎ＝１からｎ＝Ｎまで順番に、中間変数ｖｎ−１から中間変数ｖｎを求める処理を行う。したがって、並列処理を利用して中間変数ｖｎ’とｖｎ”（ただしｎ’≠ｎ”）を同時に求めることはできなかった。
【００１９】
本発明は、時間のかかる圧縮関数を用いる処理に、並列処理を利用できる技術を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明のメッセージ認証子生成装置は、データＤに対するメッセージ認証子τを出力する。本発明のメッセージ認証子生成装置は、パディング部、メッセージ分割部、第１排他的論理和計算部、中間変数計算部、重み付き排他的論理和計算部、第２排他的論理和計算部、後処理部を備える。
【００２１】
【数５】
【００２２】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とする。
【００２３】
パディング部は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成する。メッセージ分割部は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する。第１排他的論理和計算部は、
【００２４】
【数６】
【００２５】
を計算し、第１排他的論理和ＳＭとする。中間変数計算部は、ｎ＝０〜Ｎ−１に対して
【００２６】
【数７】
【００２７】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める。重み付き排他的論理和計算部は、ｗ０←ｖ０とし、ｎ＝１〜Ｎ−１に対して
【００２８】
【数８】
【００２９】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする。第２排他的論理和計算部は、
【００３０】
【数９】
【００３１】
を計算し、第２排他的論理和ＳＶとする。後処理部は、
【００３２】
【数１０】
【００３３】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする。
【００３４】
また、本発明のメッセージ認証子検証装置は、本発明のメッセージ認証子生成装置と比較部とを備え、データＭとメッセージ認証子τとを入力とし、データＭの検証を行う。メッセージ認証子生成装置は、データＭからメッセージ認証子τ’を生成する。比較部は、メッセージ認証子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【００３５】
本発明のメッセージ認証子生成方法によれば、圧縮関数を用いて中間変数ｖｎを求める処理で、中間変数ｖｎ−１を用いない。したがって、並列処理を利用して複数の中間変数を同時に求めることができる。
【図面の簡単な説明】
【００３６】
【図１】特許文献１のメッセージ認証子生成装置の構成を示す図。
【図２】特許文献１のメッセージ認証子生成装置の処理フローを示す図。
【図３】特許文献１のメッセージ認証子生成装置の各構成部での処理の流れを示す図。
【図４】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図５】本発明のメッセージ認証子生成装置の処理フロー例を示す図。
【図６】本発明のメッセージ認証子生成装置の各構成部での処理の流れを示す図。
【図７】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図８】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【発明を実施するための形態】
【００３７】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３８】
図４に、本発明のメッセージ認証子生成装置の機能構成例を示す。また、図５に、本発明のメッセージ認証子生成装置の処理フロー例を示す。さらに、図６に、各構成部での処理の流れを示す。以下の説明では、
【００３９】
【数１１】
【００４０】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｎは０以上Ｎ−１以下の整数、ｆｋは圧縮関数、Δはｂビットのあらかじめ定めたビット列とする。なお、図６の圧縮関数の表示は図３とは異なるが、同じ意味であり、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数である。具体的には、
ｆｋ（ｍ）：＝ｆ（ｋ‖ｍ）
のように定義すればよい。代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。“‖”はビット列の結合を意味する記号、“０ｂ”は“０”がｂ個並んだビット列、“０ｃ”は“０”がｃ個並んだビット列、２ｂは整数２のｂビット表現、２ｃは整数２のｃビット表現を意味する。また、Δは、
【００４１】
【数１２】
【００４２】
で求められるビット列の先頭のｂビットとすればよい。
【００４３】
メッセージ認証子生成装置２００は、任意のビット長（メッセージ長）のデータＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置２００は、パディング部１１０、メッセージ分割部２２０、第１排他的論理和計算部２３０、中間変数計算部２４０、重み付き排他的論理和計算部２４５、第２排他的論理和計算部２５０、後処理部２６０を備える。
【００４４】
パディング部１１０は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成する（Ｓ１１０）。メッセージ分割部２２０は、データＭを、Ｎ個に分割し、ｂビットのデータｍ０，…，ｍＮ−１を生成する（Ｓ２２０）。第１排他的論理和計算部２３０は、
【００４５】
【数１３】
【００４６】
を計算し、第１排他的論理和ＳＭとする（Ｓ２３０）。なお、図６の第１排他的論理和計算部２３０は、
【００４７】
【数１４】
【００４８】
の処理を行うように表記されている。これは、初期値を０ｂとおいてｎ＝０〜Ｎ−１の繰返し処理を行う方法を示しており、初期値が０ｂなので２つの式は同じ意味である。
【００４９】
中間変数計算部２４０は、ｎ＝０〜Ｎ−１に対して
【００５０】
【数１５】
【００５１】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める（Ｓ２４０）。なお、例えば、圧縮関数がｓｈａ１やｓｈａ２５６のようなｂ＝５１２の場合であれば、既約多項式をｘ５１２＋ｘ１２＋ｘ７＋ｘ２＋１とすればよい。上記の式から分かるように、中間変数ｖｎを求めるときに中間変数ｖｎ−１は不要であり、どの中間変数からでも求めることができるし、並列に求めることも可能である。
【００５２】
重み付き排他的論理和計算部２４５は、ｗ０←ｖ０とし、ｎ＝１〜Ｎ−１に対して順番に
【００５３】
【数１６】
【００５４】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする（Ｓ２４５）。図６の重み付き排他的論理和計算部２４５は、
【００５５】
【数１７】
【００５６】
としている。これは、ｗ０←ｖ０と同じ意味である。なお、例えば、圧縮関数がｓｈａ１のようなｃ＝１６０の場合であれば、既約多項式をｘ１６０＋ｘ５＋ｘ３＋ｘ２＋１とし、ｓｈａ２５６のようなｃ＝２５６の場合であれば、既約多項式をｘ２５６＋ｘ１０＋ｘ５＋ｘ２＋１とすればよい。また、この処理は並列処理を利用できないが、乗算と排他的論理和の計算だけなので、計算効率を特に意識する必要はない。
【００５７】
第２排他的論理和計算部２５０は、
【００５８】
【数１８】
【００５９】
を計算し、第２排他的論理和ＳＶとする（Ｓ２５０）。なお、図６の第２排他的論理和計算部２５０は、
【００６０】
【数１９】
【００６１】
を行っている。これは、初期値を０ｃとおいてｎ＝０〜Ｎ−１の繰返し処理を行う方法を示しており、初期値が０ｃなので２つの式は同じ意味である。
【００６２】
後処理部２６０は、
【００６３】
【数２０】
【００６４】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする（Ｓ２６０）。
【００６５】
このように構成するので、本発明のメッセージ認証子生成装置は、誕生日限界を超える高い安全性を有し、特許文献１の発明と同等である。また、図６から分かるように、本発明のメッセージ認証子生成装置は、ｂ×Ｎビット（メッセージ長ｍ）のデータＭのメッセージ認証子τを求めるために、Ｎ＋３回圧縮関数を呼び出している。ＮはデータＭを圧縮関数に入力するために分割した数である。つまり、本発明のメッセージ認証子生成装置は、圧縮関数を呼び出す回数は、データＭの分割数（Ｎ回に相当）よりも３回多いだけであり、特許文献１と同じである。さらに、圧縮関数を用いて中間変数ｖｎを求める処理（Ｓ２４０）で、中間変数ｖｎ−１を用いない。したがって、中間変数ｖｎを順番に求める必要がなく、並列処理を利用して複数の中間変数を同時に求めることができる。この点が特許文献１の発明よりも優れている。
【実施例２】
【００６６】
図７に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図８に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置５００は、実施例１で示したメッセージ認証子生成装置２００と比較部５１０と記録部５９０を備え、データＭとメッセージ認証子τが入力、検証結果が出力である。
【００６７】
メッセージ認証子検証装置５００内のメッセージ認証子生成装置２００は、データＤからメッセージ認証子τ’を生成する（Ｓ２００）。比較部５１０は、メッセージ認証子τとメッセージ認証子τ’とを比較する。そして、τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。このような構成なので、メッセージ認証子検証装置５００でも、メッセージ認証子生成装置２００と同じ効果を得ることができる。
【００６８】
＜プログラム、記録媒体＞
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７４】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証を行うシステムに利用することができる。
【符号の説明】
【００７５】
２００ メッセージ認証子生成装置 １１０ パディング部
２２０ メッセージ分割部 ２３０ 排他的論理和計算部
２４０ 中間変数計算部 ２４５ 排他的論理和計算部
２５０ 排他的論理和計算部 ２６０ 後処理部
５００ メッセージ認証子検証装置 ５１０ 比較部
５９０ 記録部
【技術分野】
【０００１】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証が行えるようにするためのメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、およびプログラムに関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＭＡＣは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子τを生成する（τ←ＭＡＣＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＭＡＣと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
【０００３】
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵Ｋ（通常、鍵は１つだが、２つ以上の場合もある）とデータＭからメッセージ認証子τを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子τ’を生成する。そして、τとτ’とを比較する。τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００４】
従来のメッセージ認証コードには、マークル・ダンガード反復を用いたハッシュ関数ＨＭＤを２回適用して安全性を高めたものとして、非特許文献１などがある。また、圧縮関数を用いたメッセージ認証コードであって、いわゆる誕生日限界を超えるような高い安全性を有するものには、例えば非特許文献２の構成法がある。しかし、非特許文献２の方法では、圧縮関数を呼び出す回数が、データＭを圧縮関数に入力するために分割した数よりも多くなる。しかも、分割数を越えて圧縮関数を呼び出す回数も、データＭの長さに依存しているため、処理量が多くなるという問題があった。
【０００５】
高い安全性を確保しながら、分割数を超える圧縮関数を呼び出す回数がデータＭの長さに依存しないようなメッセージ認証子生成方法として、特許文献１の方法がある。特許文献１のメッセージ認証子生成装置の構成を図１に、処理フローを図２に示す。さらに、図３に、各構成部での処理の流れを示す。メッセージ認証子生成装置１００は、任意のビット長（メッセージ長）のデータＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置１００は、パディング部１１０、メッセージ分割部１２０、第１チェックサム計算部１３０、中間変数計算部１４０、第２チェックサム計算部１５０、後処理部１６０を備える。
【０００６】
パディング部１１０は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×Ｎビット（ただし、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数）のデータＭを生成する（Ｓ１１０）。メッセージ分割部１２０は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する（Ｓ１２０）。第１チェックサム計算部１３０は、データｍ１，…，ｍＮの排他的論理和
【０００７】
【数１】
【０００８】
を計算し、第１チェックサムＳ１とする（Ｓ１３０）。中間変数計算部１４０は、まず、ｃビット（ただし、ｃはあらかじめ定めた整数）の最初の中間変数ｖ０を定める。例えば、ｃ個の“０”からなるビット列とあらかじめ定めておいてもよい。ｎ＝１からｎ＝Ｎまで順番に、中間変数ｖｎ−１から中間変数ｖｎを求める計算
【０００９】
【数２】
【００１０】
を行う。この繰り返し処理で、中間変数ｖＮを求める（Ｓ１４０）。ただし、ｎは１以上Ｎ以下の整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、“‖”はビット列の結合を意味する記号、“０ｂ−ｃ”は“０”がｂ−ｃ個並んだビット列、Δｎはｂビットのあらかじめ定めたビット列である。例えば、ｆｋ（ｍ）は、（ｃ＋ｂ）ビットのビット列をｃビットのビット列に圧縮する圧縮関数ｆを用いて、
ｆｋ（ｍ）：＝ｆ（ｋ‖ｍ）
のように定義すればよい。また、代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。
【００１１】
第２チェックサム計算部１５０は、中間変数ｖ１，…，ｖＮの排他的論理和
【００１２】
【数３】
【００１３】
を計算し、第２チェックサムＳ２とする（Ｓ１５０）。後処理部１６０は、計算
【００１４】
【数４】
【００１５】
によってメッセージ認証子τを求める（Ｓ１６０）。ただし、Δ’ｊはｂビットのあらかじめ定めたビット列、ｊは１から３の整数である。なお、Δ１，…，ΔＮ、およびΔ’１，Δ’２，Δ’３は互いに異なるビット列である。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００９−１８８７９４号公報
【非特許文献】
【００１７】
【非特許文献１】M. Bellare, R. Canetti, H. Krawczyk, “Keying hash functions for message authentication,” CRYPTO 1996, LNCS vol.1109, pp.1-15, Springer, Heidelberg (1996).
【非特許文献２】K. Yasuda, “Multilane HMAC - Security beyond the Birthday Limit,” INDOCRYPT 2007, LNCS vol.4859, pp.18-32, Springer, Heidelberg (2007).
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、従来技術は特許文献１のメッセージ認証子生成装置では、圧縮関数を用いる中間変数計算部１４０は、ｎ＝１からｎ＝Ｎまで順番に、中間変数ｖｎ−１から中間変数ｖｎを求める処理を行う。したがって、並列処理を利用して中間変数ｖｎ’とｖｎ”（ただしｎ’≠ｎ”）を同時に求めることはできなかった。
【００１９】
本発明は、時間のかかる圧縮関数を用いる処理に、並列処理を利用できる技術を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明のメッセージ認証子生成装置は、データＤに対するメッセージ認証子τを出力する。本発明のメッセージ認証子生成装置は、パディング部、メッセージ分割部、第１排他的論理和計算部、中間変数計算部、重み付き排他的論理和計算部、第２排他的論理和計算部、後処理部を備える。
【００２１】
【数５】
【００２２】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とする。
【００２３】
パディング部は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成する。メッセージ分割部は、データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成する。第１排他的論理和計算部は、
【００２４】
【数６】
【００２５】
を計算し、第１排他的論理和ＳＭとする。中間変数計算部は、ｎ＝０〜Ｎ−１に対して
【００２６】
【数７】
【００２７】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める。重み付き排他的論理和計算部は、ｗ０←ｖ０とし、ｎ＝１〜Ｎ−１に対して
【００２８】
【数８】
【００２９】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする。第２排他的論理和計算部は、
【００３０】
【数９】
【００３１】
を計算し、第２排他的論理和ＳＶとする。後処理部は、
【００３２】
【数１０】
【００３３】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする。
【００３４】
また、本発明のメッセージ認証子検証装置は、本発明のメッセージ認証子生成装置と比較部とを備え、データＭとメッセージ認証子τとを入力とし、データＭの検証を行う。メッセージ認証子生成装置は、データＭからメッセージ認証子τ’を生成する。比較部は、メッセージ認証子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【００３５】
本発明のメッセージ認証子生成方法によれば、圧縮関数を用いて中間変数ｖｎを求める処理で、中間変数ｖｎ−１を用いない。したがって、並列処理を利用して複数の中間変数を同時に求めることができる。
【図面の簡単な説明】
【００３６】
【図１】特許文献１のメッセージ認証子生成装置の構成を示す図。
【図２】特許文献１のメッセージ認証子生成装置の処理フローを示す図。
【図３】特許文献１のメッセージ認証子生成装置の各構成部での処理の流れを示す図。
【図４】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図５】本発明のメッセージ認証子生成装置の処理フロー例を示す図。
【図６】本発明のメッセージ認証子生成装置の各構成部での処理の流れを示す図。
【図７】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図８】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【発明を実施するための形態】
【００３７】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００３８】
図４に、本発明のメッセージ認証子生成装置の機能構成例を示す。また、図５に、本発明のメッセージ認証子生成装置の処理フロー例を示す。さらに、図６に、各構成部での処理の流れを示す。以下の説明では、
【００３９】
【数１１】
【００４０】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｎは０以上Ｎ−１以下の整数、ｆｋは圧縮関数、Δはｂビットのあらかじめ定めたビット列とする。なお、図６の圧縮関数の表示は図３とは異なるが、同じ意味であり、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数である。具体的には、
ｆｋ（ｍ）：＝ｆ（ｋ‖ｍ）
のように定義すればよい。代表的な圧縮関数には、ｃ＝１６０、ｂ＝５１２のｓｈａ１やｃ＝２５６、ｂ＝５１２のｓｈａ２５６などがある（NIST, “Secure hash standard.” FIPS PUB 180-2 (2002)）。“‖”はビット列の結合を意味する記号、“０ｂ”は“０”がｂ個並んだビット列、“０ｃ”は“０”がｃ個並んだビット列、２ｂは整数２のｂビット表現、２ｃは整数２のｃビット表現を意味する。また、Δは、
【００４１】
【数１２】
【００４２】
で求められるビット列の先頭のｂビットとすればよい。
【００４３】
メッセージ認証子生成装置２００は、任意のビット長（メッセージ長）のデータＤに対するメッセージ認証子τを出力する。メッセージ認証子生成装置２００は、パディング部１１０、メッセージ分割部２２０、第１排他的論理和計算部２３０、中間変数計算部２４０、重み付き排他的論理和計算部２４５、第２排他的論理和計算部２５０、後処理部２６０を備える。
【００４４】
パディング部１１０は、データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成する（Ｓ１１０）。メッセージ分割部２２０は、データＭを、Ｎ個に分割し、ｂビットのデータｍ０，…，ｍＮ−１を生成する（Ｓ２２０）。第１排他的論理和計算部２３０は、
【００４５】
【数１３】
【００４６】
を計算し、第１排他的論理和ＳＭとする（Ｓ２３０）。なお、図６の第１排他的論理和計算部２３０は、
【００４７】
【数１４】
【００４８】
の処理を行うように表記されている。これは、初期値を０ｂとおいてｎ＝０〜Ｎ−１の繰返し処理を行う方法を示しており、初期値が０ｂなので２つの式は同じ意味である。
【００４９】
中間変数計算部２４０は、ｎ＝０〜Ｎ−１に対して
【００５０】
【数１５】
【００５１】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める（Ｓ２４０）。なお、例えば、圧縮関数がｓｈａ１やｓｈａ２５６のようなｂ＝５１２の場合であれば、既約多項式をｘ５１２＋ｘ１２＋ｘ７＋ｘ２＋１とすればよい。上記の式から分かるように、中間変数ｖｎを求めるときに中間変数ｖｎ−１は不要であり、どの中間変数からでも求めることができるし、並列に求めることも可能である。
【００５２】
重み付き排他的論理和計算部２４５は、ｗ０←ｖ０とし、ｎ＝１〜Ｎ−１に対して順番に
【００５３】
【数１６】
【００５４】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする（Ｓ２４５）。図６の重み付き排他的論理和計算部２４５は、
【００５５】
【数１７】
【００５６】
としている。これは、ｗ０←ｖ０と同じ意味である。なお、例えば、圧縮関数がｓｈａ１のようなｃ＝１６０の場合であれば、既約多項式をｘ１６０＋ｘ５＋ｘ３＋ｘ２＋１とし、ｓｈａ２５６のようなｃ＝２５６の場合であれば、既約多項式をｘ２５６＋ｘ１０＋ｘ５＋ｘ２＋１とすればよい。また、この処理は並列処理を利用できないが、乗算と排他的論理和の計算だけなので、計算効率を特に意識する必要はない。
【００５７】
第２排他的論理和計算部２５０は、
【００５８】
【数１８】
【００５９】
を計算し、第２排他的論理和ＳＶとする（Ｓ２５０）。なお、図６の第２排他的論理和計算部２５０は、
【００６０】
【数１９】
【００６１】
を行っている。これは、初期値を０ｃとおいてｎ＝０〜Ｎ−１の繰返し処理を行う方法を示しており、初期値が０ｃなので２つの式は同じ意味である。
【００６２】
後処理部２６０は、
【００６３】
【数２０】
【００６４】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする（Ｓ２６０）。
【００６５】
このように構成するので、本発明のメッセージ認証子生成装置は、誕生日限界を超える高い安全性を有し、特許文献１の発明と同等である。また、図６から分かるように、本発明のメッセージ認証子生成装置は、ｂ×Ｎビット（メッセージ長ｍ）のデータＭのメッセージ認証子τを求めるために、Ｎ＋３回圧縮関数を呼び出している。ＮはデータＭを圧縮関数に入力するために分割した数である。つまり、本発明のメッセージ認証子生成装置は、圧縮関数を呼び出す回数は、データＭの分割数（Ｎ回に相当）よりも３回多いだけであり、特許文献１と同じである。さらに、圧縮関数を用いて中間変数ｖｎを求める処理（Ｓ２４０）で、中間変数ｖｎ−１を用いない。したがって、中間変数ｖｎを順番に求める必要がなく、並列処理を利用して複数の中間変数を同時に求めることができる。この点が特許文献１の発明よりも優れている。
【実施例２】
【００６６】
図７に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図８に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置５００は、実施例１で示したメッセージ認証子生成装置２００と比較部５１０と記録部５９０を備え、データＭとメッセージ認証子τが入力、検証結果が出力である。
【００６７】
メッセージ認証子検証装置５００内のメッセージ認証子生成装置２００は、データＤからメッセージ認証子τ’を生成する（Ｓ２００）。比較部５１０は、メッセージ認証子τとメッセージ認証子τ’とを比較する。そして、τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ５１０）。なお、記録部５９０を備えず、その他の構成部でこれらの情報を記録してもよい。このような構成なので、メッセージ認証子検証装置５００でも、メッセージ認証子生成装置２００と同じ効果を得ることができる。
【００６８】
＜プログラム、記録媒体＞
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７４】
本発明は、通信路上または記録媒体上のデータに対し、送信者またはデータ作成者の認証を行うシステムに利用することができる。
【符号の説明】
【００７５】
２００ メッセージ認証子生成装置 １１０ パディング部
２２０ メッセージ分割部 ２３０ 排他的論理和計算部
２４０ 中間変数計算部 ２４５ 排他的論理和計算部
２５０ 排他的論理和計算部 ２６０ 後処理部
５００ メッセージ認証子検証装置 ５１０ 比較部
５９０ 記録部
【特許請求の範囲】
【請求項１】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成装置であって、
【数２１】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とし、
前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成するパディング部と、
前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割部と、
【数２２】
を計算し、第１排他的論理和ＳＭとする第１排他的論理和計算部と、
ｎ＝０〜Ｎ−１に対して
【数２３】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める中間変数計算部と、
ｗ０←ｖ０とし、
ｎ＝１〜Ｎ−１に対して
【数２４】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする重み付き排他的論理和計算部と、
【数２５】
を計算し、第２排他的論理和ＳＶとする第２排他的論理和計算部と、
【数２６】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする後処理部と
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記ビット列Δが
【数２７】
で求められるビット列の先頭のｂビットとする
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証装置であって、
前記データＤからメッセージ認証子τ’を生成する請求項１または２記載のメッセージ認証子生成装置と、
前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項４】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成方法であって、
【数２８】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とし、
パディング部が、前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成するパディングステップと、
分割部が、前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割ステップと、
第１排他的論理和計算部が、
【数２９】
を計算し、第１排他的論理和ＳＭとする第１排他的論理和計算ステップと、
中間変数計算部が、ｎ＝０〜Ｎ−１に対して
【数３０】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める中間変数計算ステップと、
重み付き排他的論理和計算部が、ｗ０←ｖ０とし、
ｎ＝１〜Ｎ−１に対して
【数３１】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする重み付き排他的論理和計算ステップと、
第２排他的論理和計算部が、
【数３２】
を計算し、第２排他的論理和ＳＶとする第２排他的論理和計算ステップと、
後処理部が
【数３３】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする後処理ステップと
を有するメッセージ認証子生成方法。
【請求項５】
請求項４記載のメッセージ認証子生成方法であって、
前記ビット列Δが
【数３４】
で求められるビット列の先頭のｂビットとする
ことを特徴とするメッセージ認証子生成方法。
【請求項６】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証方法であって、
前記データＤからメッセージ認証子τ’を生成する請求項４または５記載のメッセージ認証子生成方法の各ステップと、
比較部で、前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項７】
請求項１から３のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【請求項１】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成装置であって、
【数２１】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とし、
前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成するパディング部と、
前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割部と、
【数２２】
を計算し、第１排他的論理和ＳＭとする第１排他的論理和計算部と、
ｎ＝０〜Ｎ−１に対して
【数２３】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める中間変数計算部と、
ｗ０←ｖ０とし、
ｎ＝１〜Ｎ−１に対して
【数２４】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする重み付き排他的論理和計算部と、
【数２５】
を計算し、第２排他的論理和ＳＶとする第２排他的論理和計算部と、
【数２６】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする後処理部と
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記ビット列Δが
【数２７】
で求められるビット列の先頭のｂビットとする
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証装置であって、
前記データＤからメッセージ認証子τ’を生成する請求項１または２記載のメッセージ認証子生成装置と、
前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項４】
データＤに対するメッセージ認証子τを出力するメッセージ認証子生成方法であって、
【数２８】
はデータを２進表現したときのビットごとの排他的論理和、ｂはあらかじめ定めた整数、Ｎはｂ×ＮがデータＤのメッセージ長よりも長くなる整数、ｆｋはｃビットの鍵ｋを用いてｂビットのビット列をｃビットのビット列に圧縮する圧縮関数、Δはｂビットのあらかじめ定めたビット列とし、
パディング部が、前記データＤに対して、あらかじめ定めたパディングを行うことで、ｂ×ＮビットのデータＭを生成するパディングステップと、
分割部が、前記データＭを、Ｎ個に分割し、ｂビットのデータｍ１，…，ｍＮを生成するメッセージ分割ステップと、
第１排他的論理和計算部が、
【数２９】
を計算し、第１排他的論理和ＳＭとする第１排他的論理和計算ステップと、
中間変数計算部が、ｎ＝０〜Ｎ−１に対して
【数３０】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、中間変数ｖ０，…，ｖＮ−１を求める中間変数計算ステップと、
重み付き排他的論理和計算部が、ｗ０←ｖ０とし、
ｎ＝１〜Ｎ−１に対して
【数３１】
ただし、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｃ）の乗算
の計算を行って得られるｗＮ−１を、重み付き排他的論理和Ｗとする重み付き排他的論理和計算ステップと、
第２排他的論理和計算部が、
【数３２】
を計算し、第２排他的論理和ＳＶとする第２排他的論理和計算ステップと、
後処理部が
【数３３】
ただし、０ｂ−２ｃは０がｂ−２ｃ個並んだビット列、この式の“・”は有限体ＧＦ（２）上の既約多項式の剰余環によって表現される有限体ＧＦ（２）の拡大体ＧＦ（２ｂ）の乗算
を計算し、メッセージ認証子τとする後処理ステップと
を有するメッセージ認証子生成方法。
【請求項５】
請求項４記載のメッセージ認証子生成方法であって、
前記ビット列Δが
【数３４】
で求められるビット列の先頭のｂビットとする
ことを特徴とするメッセージ認証子生成方法。
【請求項６】
データＤとメッセージ認証子τとを入力とし、データＤの検証を行うメッセージ認証子検証方法であって、
前記データＤからメッセージ認証子τ’を生成する請求項４または５記載のメッセージ認証子生成方法の各ステップと、
比較部で、前記メッセージ認証子τと前記メッセージ認証子τ’とを比較してデータＤの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項７】
請求項１から３のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−２５９３８９（Ｐ２０１１−２５９３８９Ａ）
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願番号】特願２０１０−１３４４００（Ｐ２０１０−１３４４００）
【出願日】平成２２年６月１１日（２０１０．６．１１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願日】平成２２年６月１１日（２０１０．６．１１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]