(57)【特許請求の範囲】
【請求項１】
メッセージから前記メッセージに対するメッセージ認証子を計算するメッセージ認証子生成装置であって、
一時使用数値を用いて撹乱情報を生成する処理を行う撹乱情報生成部と、
前記メッセージから変換メッセージを計算する処理を行うメッセージ変換部と、
前記撹乱情報と前記変換メッセージから前記メッセージ認証子を計算する処理を行う認証子計算部とを備え、
前記認証子計算部が行う前記メッセージ認証子を計算する処理は、
前記変換メッセージから第一の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第一の中間データを変換して第二の中間データを生成する処理ステップと、
前記第二の中間データから第三の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第三の中間データを変換して第四の中間データを生成する処理ステップと、
前記第四の中間データから前記メッセージ認証子を計算する処理ステップとを実行することを特徴とするメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置において、
前記撹乱情報生成部が行う前記撹乱情報を生成する処理は、前記一時使用数値に対して暗号化する処理ステップを実行することを特徴とするメッセージ認証子生成装置。
【請求項３】
請求項２記載のメッセージ認証子生成装置において、
前記メッセージ変換部が行う前記変換メッセージを計算する処理は、前記メッセージをメッセージブロックに分割して、前記メッセージブロックに対して暗号化する処理ステップを実行することを特徴とするメッセージ認証子生成装置。
【請求項４】
請求項３記載のメッセージ認証子生成装置において、
前記認証子計算部が行う前記メッセージ認証子を計算する処理は、ＯＭＡＣを用いた処理であることを特徴とするメッセージ認証子生成装置。
【請求項５】
請求項３記載のメッセージ認証子生成装置において、
前記認証子計算部が行う前記メッセージ認証子を計算する処理は、ＰＭＡＣを用いた処理であることを特徴とするメッセージ認証子生成装置。
【請求項６】
請求項４記載のメッセージ認証子生成装置において、
前記認証子計算部が行う前記メッセージ認証子を計算する処理は、前記メッセージブロックによる変換メッセージごとに、排他的論理和もしくは算術加算による加算と、その出力の暗号化とを用いて、連鎖処理することにより実現され、
前記連鎖処理では、第１のメッセージブロックによる変換メッセージと前記撹乱情報とによる加算を計算しその出力を暗号化して第１の中間データを得る処理ステップと、次に第２のメッセージブロックによる変換メッセージと前記第１の中間データとによる加算を計算しその出力を暗号化して第２の中間データを得る処理ステップと、以後同様に連鎖処理するステップと、第ｍのメッセージブロックによる変換メッセージと第（ｍ−１）の中間データとによる加算を計算しその出力を暗号化して前記メッセージ認証子を得る処理ステップと、を実行することを特徴とするメッセージ認証子生成装置。
【請求項７】
請求項５記載のメッセージ認証子生成装置において、
前記認証子計算部が行う前記メッセージ認証子を計算する処理は、前記メッセージブロックによる変換メッセージごとに、グレイコードと０に対する暗号化結果とのバイナリ体における乗算結果（γｊＬ）を作用させる排他的論理和もしくは算術加算による第１の加算と、その出力の暗号化と、排他的論理和もしくは算術加算による第２の加算とを用いて連鎖処理することにより実現され、
前記連鎖処理では、第１のメッセージブロックによる変換メッセージとγ１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と前記撹乱情報とによる第２の加算により第１の中間データを得る処理ステップと、次に第２のメッセージブロックによる変換メッセージとγ２Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と前記第１の中間データとによる第２の加算により第２の中間データを得る処理ステップと、以後同様に連鎖処理するステップと、第（ｍ−１）のメッセージブロックによる変換メッセージとγｍ−１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と前記第（ｍ−２）の中間データとによる第２の加算により第（ｍ−１）の中間データを得る処理ステップと、第ｍのメッセージブロックによる変換メッセージとγｍＬとによる第１の加算を計算し、その出力を暗号化し、その出力と前記第（ｍ−１）の中間データとによる第２の加算により前記メッセージ認証子を得る処理ステップと、を実行することを特徴とするメッセージ認証子生成装置。
【請求項８】
メッセージと前記メッセージの真正性を検証するために用いる第一のメッセージ認証子から、前記メッセージの真正性を検証するメッセージ認証子検証装置であって、
前記メッセージと一時使用数値とから第二のメッセージ認証子を生成する処理を行う処理ステップと、
前記第一のメッセージ認証子と前記第二のメッセージ認証子とを比較して結果を得る処理を行う処理ステップとを実行するものであり、
前記第二のメッセージ認証子を生成する処理ステップでは、
前記一時使用数値を用いて撹乱情報を生成する処理を行う処理ステップと、
前記メッセージから変換メッセージを計算する処理を行う処理ステップと、
前記撹乱情報と前記変換メッセージから前記第二のメッセージ認証子を計算する処理を行う処理ステップとを実行し、
前記第二のメッセージ認証子を計算する処理は、
前記変換メッセージから第一の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第一の中間データを変換して第二の中間データを生成する処理ステップと、
前記第二の中間データから第三の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第三の中間データを変換して第四の中間データを生成する処理ステップと、
前記第四の中間データから前記メッセージ認証子を計算する処理ステップとを実行することを特徴とするメッセージ認証子検証装置。
【請求項９】
メッセージから前記メッセージに対する第一のメッセージ認証子を計算するメッセージ認証子生成装置と、
前記メッセージ認証子生成装置からのメッセージと前記メッセージの真正性を検証するために用いる第一のメッセージ認証子から、前記メッセージの真正性を検証するメッセージ認証子検証装置とを有するメッセージ認証システムであって、
前記メッセージ認証子生成装置では、
前記メッセージと一時使用数値とから第一のメッセージ認証子を生成する処理として、
前記一時使用数値を用いて撹乱情報を生成する処理を行う処理ステップと、
前記メッセージから変換メッセージを計算する処理を行う処理ステップと、
前記撹乱情報と前記変換メッセージから前記第一のメッセージ認証子を計算する処理を行う処理ステップとを実行し、
前記第一のメッセージ認証子を計算する処理は、
前記変換メッセージから第一の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第一の中間データを変換して第二の中間データを生成する処理ステップと、
前記第二の中間データから第三の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第三の中間データを変換して第四の中間データを生成する処理ステップと、
前記第四の中間データから前記メッセージ認証子を計算する処理ステップとを実行し、
前記メッセージ認証子検証装置では、
前記メッセージと一時使用数値とから第二のメッセージ認証子を生成する処理として、
前記一時使用数値を用いて撹乱情報を生成する処理を行う処理ステップと、
前記メッセージから変換メッセージを計算する処理を行う処理ステップと、
前記撹乱情報と前記変換メッセージから前記第二のメッセージ認証子を計算する処理を行う処理ステップとを実行し、
前記第二のメッセージ認証子を計算する処理は、
前記変換メッセージから第一の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第一の中間データを変換して第二の中間データを生成する処理ステップと、
前記第二の中間データから第三の中間データを生成する処理ステップと、
前記撹乱情報を用いて前記第三の中間データを変換して第四の中間データを生成する処理ステップと、
前記第四の中間データから前記メッセージ認証子を計算する処理ステップとを実行し、
更に前記第一のメッセージ認証子と前記第二のメッセージ認証子とを比較して結果を得る処理を行うことを特徴とするメッセージ認証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関し、特に、メッセージ認証子（MAC：Message Authentication Code）を用いた認証の技術に関する。
【背景技術】
【０００２】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証のために暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件を満たすことは難しい。
【０００３】
暗号技術には、共通鍵暗号と公開鍵暗号がある。共通鍵暗号には、メッセージの暗号化・復号化を行ういわゆる暗号と、メッセージの真正性を示すためのメッセージ認証とがある。
【０００４】
メッセージ認証では、与えられたメッセージに対して、その真正性を示すためのデータであるメッセージ認証子（第一のメッセージ認証子）を、鍵を用いて生成する。メッセージの真正性の確認ないし検証では、与えられたメッセージに対して、上記鍵と同じ鍵を用いてメッセージ認証子（第二のメッセージ認証子）を再度生成し、それらのメッセージ認証子が一致するかどうかによって判定する。メッセージ認証の方法（特にＯＭＡＣやＰＭＡＣ）について、非特許文献１および非特許文献２に記載されている。
【０００５】
また、暗号技術の安全性としては、統計解析などの数学理論を前提としたものの他、暗号実行時に暗号装置から観測される物理量、例えば計算時間や電力消費量などを用いて秘密情報を特定するサイドチャネル攻撃といった攻撃に対する耐性などが求められる。サイドチャネル攻撃に関して、非特許文献３に記載されている。
【０００６】
また、メッセージ認証に対するサイドチャネル攻撃に関して、非特許文献４に記載されている。メッセージ認証において次のような排他的論理和（XOR）が存在する場合、そのメッセージ認証はサイドチャネル攻撃に対して脆弱となる。即ち、排他的論理和の二つの入力に対して、一つは固定値かつ攻撃者にとって秘密の値、もう一つは攻撃者にとって既知の値であって攻撃者がその値を変更できる、というような場合である。
【非特許文献１】T. Iwata and K. Kurosawa, “OMAC: One-Key CBC MAC,” in the proceedings of Fast Software Encryption (FSE 2003), Lecture Note in Computer Science 2887, Springer-Verlag, pp. 129-153, (2003).
【非特許文献２】J. Black and P. Rogaway, “A Block-Cipher Mode of Operation for Parallelizable Message Authentication,” in the proceedings of EUROCRYPT 2002, Lecture Note in Computer Science 2332, Springer-Verlag, pp. 384-397, (2002).
【非特許文献３】P.C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis,” in the proceedings of CRYPTO 1999, Lecture Note in Computer Science 1666, Springer-Verlag, pp.388-397, (1999).
【非特許文献４】K. Okeya, and T.Iwara, “Side Channel Attacks on Message Authentication Codes,” in the proceedings of Security and Privacy in Ad-hoc and Sensor Networks: Second European Workshop, ESAS 2005, Lecture Note in Computer Science 3813, Springer-Verlag, pp.205-217, (2005).
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述のようにメッセージ認証を用いれば、メッセージの真正性を検証することができる。しかしながら、前記非特許文献１，２の技術では、メッセージ認証の方法を提供しているが、サイドチャネル攻撃への耐性については十分に考慮されていない。
【０００８】
本発明は以上のような問題に鑑みてなされたものであり、その目的は、サイドチャネル攻撃に対して安全なメッセージ認証の技術を提供することである。
【課題を解決するための手段】
【０００９】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。前記目的を達成するために、本発明は、メッセージ認証子（必要に応じＭＡＣと略称する）を用いたメッセージ認証の技術であって、以下に示す技術的手段を備えることを特徴とする。
【００１０】
（１−１）本発明の装置（メッセージ認証子生成装置）は、メッセージ（メッセージ認証対象となるデータ：記号Ｍで表す）からメッセージ認証子（ＭＡＣ：記号ＣやＴで表す）を計算（生成）するものであって、下記に示すような、撹乱情報生成部、メッセージ変換部、及び認証子（ＭＡＣ）計算部を備え各部で対応する処理を実行することを特徴とする。撹乱情報生成部は、一時使用数値（nonce：記号Ｎで表す）を用いて撹乱情報（記号Ｒで表す）を生成する処理（撹乱情報生成処理）を行う。メッセージ変換部は、上記メッセージ（Ｍ）から変換メッセージ（記号Ｍ’で表す）を計算する処理（メッセージ変換処理）を行う。認証子計算部は、上記撹乱情報（Ｒ）と上記変換メッセージ（Ｍ’）から、上記メッセージ認証子（Ｃ）を計算する処理（認証子計算処理）を行う。これによって、サイドチャネル攻撃に対して安全なメッセージ認証の方法及びその方法に従い処理動作する装置を実現している。
【００１１】
（１−２）また、本装置では、上記撹乱情報（Ｒ）を生成する処理を、上記一時使用数値（Ｎ）に対して暗号化（特にブロック暗号化（Ｅ））する処理ステップを実行することによって行ってもよい。
【００１２】
（１−３）また、本装置では、上記変換メッセージ（Ｍ’）を計算する処理を、上記メッセージ（Ｍ）をメッセージブロック（記号Ｂ及びＭ[ｉ]で表す）に分割して、そのメッセージブロック（Ｂ）に対して暗号化（特にブロック暗号化（Ｅ））する処理ステップを実行することによって行ってもよい。
【００１３】
（１−４）また、本装置では、上記メッセージ認証子（Ｃ）を計算する処理を、公知技術であるＯＭＡＣ（One-Key CBC MAC）もしくはＰＭＡＣ（Parallelizable MAC）の処理に従って行ってもよい。
【００１４】
ＯＭＡＣ適用の構成において、認証子計算部及びその処理では、例えば、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、排他的論理和または算術加算による加算と、暗号化（ブロック暗号化）とを有する。その構成で、最初（第１）のメッセージブロックによる変換メッセージ（Ｍ’）と撹乱情報（Ｒ）とによる加算を計算しその出力を暗号化して第１の処理結果を得る。次に、第２のメッセージブロックによる変換メッセージ（Ｍ’）と上記第１の処理結果とによる加算を計算しその出力を暗号化して第２の処理結果を得る。以後同様に連鎖処理し、第ｍのメッセージブロックによる変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果とによる加算を計算しその出力を暗号化して第ｍの処理結果がメッセージ認証子（Ｔ）として得られる。
【００１５】
ＰＭＡＣ適用の構成において、認証子計算部及びその処理では、例えば、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、排他的論理和または算術加算による第１（第１種）の加算と、暗号化（ブロック暗号化）と、排他的論理和または算術加算による第２（第２種）の加算とを有する。その構成で、最初（第１）のメッセージブロックによる変換メッセージ（Ｍ’）とγ１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と撹乱情報（Ｒ）とによる第２の加算により第１の処理結果を得る。次に、第２のメッセージブロックによる変換メッセージ（Ｍ’）とγ２Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と第１の処理結果とによる第２の加算により第２の処理結果を得る。以後同様に連鎖処理し、第（ｍ−１）のメッセージブロックによる変換メッセージ（Ｍ’）とγｍ−１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力と第（ｍ−２）の処理結果とによる第２の加算により第（ｍ−１）の処理結果を得る。最後に、第ｍのメッセージブロックによる変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果とによる加算を計算しその出力を暗号化して第ｍの処理結果がメッセージ認証子（Ｔ）として得られる。
【００１６】
（１−５）また、本装置では、上記メッセージ認証子（Ｃ）を計算する処理を以下のように行ってもよい。認証子計算部及び処理では、上記変換メッセージ（Ｍ’）から第１の加算と暗号化を通じて、第一の中間データ（ｄ１）を生成する処理ステップと、上記撹乱情報（Ｒ）を用いて上記第一の中間データ（ｄ１）を変換して第二の中間データ（ｄ２）を生成する処理ステップと、上記第二の中間データ（ｄ２）からＬｕ−１を用いて第三の中間データ（ｄ３）を生成する処理ステップと、上記撹乱情報を（Ｒ）用いて上記第三の中間データを変換して第四の中間データ（ｄ４）を生成する処理ステップと、上記第四の中間データ（ｄ４）から暗号化を通じて上記メッセージ認証子（Ｃ）を計算する処理ステップとを実行する。
【００１７】
本構成において、認証子計算部及びその処理では、例えば、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、排他的論理和または算術加算による第１（第１種）の加算と、暗号化（ブロック暗号化）と、排他的論理和または算術加算による第２（第１種）の加算と、排他的論理和または算術加算による第３（第３種）の加算とを有する。その構成で、最初（第１）のメッセージブロックによる変換メッセージ（Ｍ’）とγ１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力（第一の中間データ：ｄ１）と撹乱情報（Ｒ）とによる第２の加算により第１の処理結果（第二の中間データ：ｄ２）を得る。次に、第２のメッセージブロックによる変換メッセージ（Ｍ’）とγ２Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力（ｄ１）と第１の処理結果（ｄ２）とによる第２の加算により第２の処理結果（ｄ２）を得る。以後同様に連鎖処理し、第（ｍ−１）のメッセージブロックによる変換メッセージ（Ｍ’）とγｍ−１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力（ｄ１）と第（ｍ−２）の処理結果（ｄ２）とによる第２の加算により第（ｍ−１）の処理結果（第ｄ２）を得る。そして、第ｍのメッセージブロックによる変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果（ｄ２）とＬｕ−１とによる加算を計算した出力（第三の中間データ：ｄ３）を得る。そして、その出力（ｄ３）と、前記最初（第１）の処理で用いたのと同じ撹乱情報（Ｒ）とを加算した出力（第四の中間データ：ｄ４）を得て、その出力（ｄ４）を暗号化した第ｍの処理結果がメッセージ認証子（Ｔ）として得られる。
【００１８】
（２）本発明の装置（メッセージ認証子検証装置）は、メッセージ（メッセージ認証対象となるデータ：Ｍ）及び第一のメッセージ認証子（Ｃ１：検証前のもの）の入力に基づき、上記メッセージ（Ｍ）の真正性を検証する処理（メッセージ認証子検証処理ないしメッセージ認証処理）を行うものであって、上記メッセージ（Ｍ）と一時使用数値（Ｎ）から第二のメッセージ認証子（Ｃ２：検証に用いるためのもの）を生成する処理（メッセージ認証子生成処理）と、上記第一のメッセージ認証子（Ｃ１）と上記第二のメッセージ認証子（Ｃ２）とを比較してその結果を得る処理とを実行する。上記メッセージ認証子（Ｃ１，Ｃ２）を生成する処理では、前記（１）のようなメッセージ認証子生成装置ないしその処理を用いて行う。
【００１９】
（３）本発明のシステム（メッセージ認証システム）は、メッセージ認証子生成装置からのメッセージ及び第一のメッセージ認証子（Ｃ１）をメッセージ認証子検証装置において検証するものであって、前記（１）のようなメッセージ認証子生成装置が、前記第一のメッセージ認証子（Ｃ１）を生成する処理を行って前記メッセージと第一のメッセージ認証子（Ｃ１）を前記（２）のようなメッセージ認証子検証装置に送信し、前記（２）のようなメッセージ認証子検証装置理では、前記メッセージから第二のメッセージ認証子（Ｃ２）を生成する処理と、更に前記第一のメッセージ認証子（Ｃ１）と前記第二のメッセージ認証子（Ｃ２）とを比較して結果を得る処理を行う。
【発明の効果】
【００２０】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。本発明によれば、サイドチャネル攻撃に対して安全なメッセージ認証の技術を提供できる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一符号を付し、その繰り返しの説明は省略する。
【００２２】
（実施の形態１）
図１〜図６は、本発明の実施の形態１の構成を示す。図１は、本発明によるメッセージ認証子計算方法を適用した、実施の形態１のメッセージ認証システム、メッセージ認証子生成装置及びメッセージ認証子検証装置の構成を示す。
【００２３】
＜システム構成＞
図１において、メッセージ認証子（ＭＡＣ）生成装置であるコンピュータ（Ａ）１０１と、メッセージ認証子（ＭＡＣ）検証装置であるコンピュータ（Ｂ）１２１とが、ネットワーク１４２により接続されたシステム構成を示している。コンピュータ（Ａ）１０１及び（Ｂ）１２１は、ＭＡＣ処理部（１１２，１３２）を備えるＭＡＣ処理装置であって、特にコンピュータ（Ａ）１０１は、ＭＡＣの生成を行う機能を備えるＭＡＣ生成装置であり、特にコンピュータ（Ｂ）１２１は、ＭＡＣの検証を行う機能を備えるＭＡＣ検証装置である。コンピュータ（Ａ）１０１，（Ｂ）１２１は、ＭＡＣ処理部（１１２，１３２）が主な特徴部であるが、セキュリティ処理等に係わるその他の処理機能を備えていてもよい。例えば、暗号処理モジュールの一部としてＭＡＣ処理部（１１２，１３２）を有する構成である。コンピュータ（Ａ）１０１と（Ｂ）１２１は、全体のメッセージ認証システムを構成する対応した装置であり、共通の部分（特にＭＡＣ生成機能）を有する構成である。
【００２４】
まず、本システムにおけるメッセージ認証処理の概要は以下である。図１のメッセージ認証システムにおけるコンピュータ（Ａ）１０１と（Ｂ）１２１は、予め、暗号処理に用いる鍵（Ｋ）を秘密裏に共有しておく。
【００２５】
コンピュータ（Ａ）１０１は、上記の鍵（Ｋ）を用いて、メッセージ（Ｍ）に対するメッセージ認証子（第一のＭＡＣ：Ｃ１）を生成する。コンピュータ（Ａ）１０１は、上記メッセージ（Ｍ）と上記生成したメッセージ認証子（Ｃ１）とを、データ１４１として、ネットワーク１４２を通じてコンピュータ（Ｂ）１２１に送信する。
【００２６】
コンピュータ（Ｂ）１２１は、受け取ったデータ１４１であるメッセージ（Ｍ）とメッセージ認証子（Ｃ１）に対して、上記の共有している鍵（Ｋ）を用いてメッセージ（Ｍ）の真正性を検証する処理を行う。メッセージ（Ｍ）の真正性の検証には、上記の鍵（Ｋ）を用いて上記メッセージ（Ｍ）に対するメッセージ認証子（第二のＭＡＣ：Ｃ２）を再生成し、再生成したメッセージ認証子（Ｃ２）と受け取ったメッセージ認証子（Ｃ１）とが比較して一致するかどうかで検証結果を判定する。即ち、一致する場合はメッセージ（Ｍ）の真正性が保たれていると判定し、一致しない場合はメッセージ（Ｍ）の真正性が保たれていないと判定する。言うまでもなく、上記メッセージ認証子（Ｃ２）の再生成の時点では、検証前であるため、コンピュータ（Ｂ）１２１と（Ａ）１０１とで同じ内容のデータを生成している保証は無い。例えば上記受け取ったメッセージ認証子（Ｃ１）は改ざんされたデータである可能性がある。コンピュータ（Ｂ）１２１は、コンピュータ（Ａ）１０１に対し、検証結果などをデータ１４３として返す。
【００２７】
ネットワーク１４２には、メッセージ（Ｍ）とメッセージ認証子（Ｃ）のみが送信され、鍵（Ｋ）は送信されない。メッセージ認証子（Ｃ）の生成には鍵（Ｋ）が用いられるため、鍵（Ｋ）を保持しているものだけがメッセージ認証子（Ｃ）を生成できる。上記コンピュータ（Ｂ）１２１で再生成したメッセージ認証子（Ｃ２）が、上記受信したメッセージ認証子（Ｃ１）と一致する場合、上記受信したメッセージ認証子（Ｃ１）は、同じ鍵（Ｋ）を保有しているもの（即ちコンピュータ（Ａ）１０１）が生成したことを示している。換言すると、ネットワーク１４２を通じたデータ１４１の送信の際に、メッセージ（Ｍ）及びメッセージ認証子（Ｃ）が改ざんされていないこと、即ち、メッセージ（Ｍ）の真正性を示している。
【００２８】
＜装置構成＞
次に装置構成などを説明する。コンピュータ（Ａ）１０１及び（Ｂ）１２１は、例えば、ＩＣカードないしそれに搭載されるＩＣチップの形態でもよいし、またＰＣ等の形態でもよい。コンピュータ（Ｂ）１２１は、コンピュータ（Ａ）１０１と同様のＭＡＣ生成機能に加え、ＭＡＣ検証（比較）機能を備える。
【００２９】
コンピュータ（Ａ）１０１は、ＣＰＵ（主処理装置）１１３やコプロセッサ（数値計算用処理装置）１１４などの演算装置（処理部１１１に含まれる）、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ（Ａ）１０１の外部とのデータ入出力を行うための入出力インタフェース１１０などを具備している。コンピュータ（Ａ）１０１の外部には、コンピュータ（Ａ）１０１をユーザが操作するためのディスプレイ（表示装置）１０８やキーボード（入力装置）１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。また、コンピュータ（Ａ）１０１は、入出力インタフェース１１０を通じてネットワーク１４２に接続される。
【００３０】
更にコンピュータ（Ａ）１０１は、上記記憶装置によって記憶部１０２を実現し、上記演算装置が記憶部１０２に格納されたプログラムを実行することにより、処理部１１１の一部であるメッセージ認証子（ＭＡＣ）処理部１１２を実現する。ＭＡＣ処理部１１２は、入力されたメッセージ（Ｍ）に対するメッセージ認証子（Ｃ１）の生成を行う。処理部１１１は、ＭＡＣ処理部１１２を用いてメッセージ認証に係わる処理などを行う。記憶部１０２は、例えばＲＡＭ１０３に、定数１０４（例えば初期値やビット長などのパラメータである）、秘密情報１０５（例えば鍵（Ｋ）である）などを安全に記憶している。
【００３１】
コンピュータ（Ｂ）１２１は、コンピュータ（Ａ）１０１と同様の構成を備え、主に処理部１３１が異なる。コンピュータ（Ｂ）１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１２７などの記憶装置によって記憶部１２２を実現し、ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納されたプログラムを実行することにより、処理部１３１の一部であるＭＡＣ処理部１３２を実現する。ＭＡＣ処理部１３２は、受け取ったメッセージ（Ｍ）とメッセージ認証子（Ｃ１）に対して、メッセージ認証子（Ｃ２）の再生成及び比較により、メッセージ（Ｍ）の真正性を検証する。処理部１３１は、ＭＡＣ処理部１３２を用いてメッセージ認証に係わる処理などを行う。記憶部１２２は、例えばＲＡＭ１２３に、定数１２４、秘密情報１２５（例えば鍵（Ｋ）である）などを安全に記憶している。
【００３２】
なお、各実施の形態の構成において、コンピュータ（Ａ）１０１,（Ｂ）１２１は、以下の構成が可能である。コンピュータ（Ａ）１０１，（Ｂ）１２１内のプログラムやデータは、予め、記憶部（１０２，１２２）に格納されていても良いし、必要なときに、コンピュータ（Ａ）１０１，（Ｂ）１２１が利用可能な媒体、及び入出力インタフェース（１１０，１３０）を介して他の装置から上記記憶部（１０２，１２２）に導入されてもよい。更に、コンピュータ（Ａ）１０１，（Ｂ）１２１内のプログラムやデータは、必要なときに、入出力インタフェース（１１０，１３０）を介して接続する他のコンピュータまたは当該コンピュータが利用可能な媒体を介して上記記憶部（１０２，１２２）に導入されてもよい。上記利用可能な媒体とは、例えば当該コンピュータに着脱可能な記憶媒体、または通信媒体（ネットワークまたはネットワークを伝搬する搬送波やディジタル信号など）を指す。
【００３３】
なお、コンピュータ（Ａ）１０１と（Ｂ）１２１とが秘密裏に共有する上記の鍵（Ｋ）は、入出力インタフェース（１１０，１３０）を介して鍵（Ｋ）のデータが入力される他には、鍵（Ｋ）を暗号化したデータが入力されてコンピュータ（Ａ）１０１または（Ｂ）１２１が当該暗号化データを復号化することにより、鍵（Ｋ）の共有が実現されてもよい。また、公開鍵暗号の技術を利用し、公開鍵に関する情報を相手側のコンピュータにネットワーク１４２を介して送信し、受信した相手側公開鍵の情報から、自らの秘密情報を用いて新たな鍵を導出することにより、鍵（Ｋ）の共有が実現されてもよい。
【００３４】
＜ＭＡＣ生成処理＞
次に、図１のメッセージ認証システムにおけるコンピュータ（Ａ）１０１のＭＡＣ処理部１１２が行うＭＡＣ生成処理を、図２〜図４を参照して説明する。実施の形態１では、図２で示される機能ブロック構成のＭＡＣ処理部１１２を用いる。
【００３５】
図２において、ＭＡＣ処理部１１２は、撹乱情報生成部２１０、メッセージ変換部２２０、認証子計算部２３０からなる。撹乱情報生成部２１０は、ブロック暗号計算部２１１を有する。メッセージ変換部２２０は、パディング部２２１、ブロック暗号計算部２２２を有する。認証子計算部２３０は、論理算術演算部２３１、ブロック暗号計算部２３２を有する。
【００３６】
ＭＡＣ処理部１１２は、メッセージ（Ｍ）及び一時使用数値（Ｎ）を入力し、ＭＡＣ生成処理によって生成したＭＡＣ認証子（Ｃ）を出力する。撹乱情報生成部２１０は、一時使用数値（Ｎ）をもとに撹乱情報（Ｒ）を生成する。メッセージ変換部２２０は、メッセージ（Ｍ）をもとに変換メッセージ（Ｍ’）を生成する。認証子計算部２３０は、撹乱情報（Ｒ）と変換メッセージ（Ｍ’）をもとにメッセージ認証子（Ｃ）を計算する。
【００３７】
それぞれのブロック暗号計算部は、ＤＥＳやＡＥＳといったブロック暗号の計算を行う。このブロック暗号を記号Ｅとして表す。ブロック暗号Ｅは、予め定められたビット長（鍵長）の鍵Ｋと予め定められたビット長（ブロック長）のメッセージＭ０という二つの入力を持ち、鍵Ｋを用いたメッセージＭ０の暗号化結果ＥＫ（Ｍ０）を出力する。鍵長とブロック長は同じであってもよい。また、鍵Ｋを明示的に示す必要がない場合は、Ｅ（Ｍ０）のように鍵Ｋを省略して表記する。なお、本例において、ブロック暗号計算部は、撹乱情報生成部２１０、メッセージ変換部２２０、及び認証子計算部２３０にそれぞれ含まれているが、これらのブロック暗号計算部（２１１，２２２，２３２）を統合し、撹乱情報生成部２１０、メッセージ変換部２２０、及び認証子計算部２３０の各々から呼び出すことで構成してもよい。そのような構成により、回路規模やプログラムコードを削減できる。
【００３８】
パディング部２２１は、入力されたメッセージ（Ｍ）をブロック長ごとに分割することによりメッセージブロック（Ｂ）を生成する際の最後のメッセージブロック（Ｂ）に対して、適当なバイナリ列を追加してビット長をブロック長に一致させる（パディング処理）。論理算術演算部２３１は、排他的論理和（ＸＯＲ）や算術加算といった論理演算や算術演算を行う。
【００３９】
図３は、本ＭＡＣ生成方法に従う、コンピュータ（Ａ）１０１のＭＡＣ処理部１１２のＭＡＣ生成処理における情報の受け渡しを例示している。図４は、同ＭＡＣ処理部１１２のＭＡＣ生成処理の概要を例示している。Ｓは処理ステップを表す。
【００４０】
図３及び図４において、まず、ＭＡＣ処理部１１２は、入力としてメッセージ（Ｍ）及び一時使用数値（Ｎ）を受け取る（Ｓ３０１）。次に、ＭＡＣ処理部１１２は、一時使用数値（Ｎ）を撹乱情報生成部２１０に送付する（Ｓ３０２）。次に、撹乱情報生成部２１０は、一時使用数値（Ｎ）を用いて撹乱情報（Ｒ）を生成する撹乱情報生成処理（４０１）を行う。次に、撹乱情報生成部２１０は、生成した撹乱情報（Ｒ）をＭＡＣ処理部１１２へ送付する（Ｓ３０３）。
【００４１】
次に、ＭＡＣ処理部１１２は、メッセージ（Ｍ）をメッセージ変換部２２０へ送付する（Ｓ３０４）。次に、メッセージ変換部２２０は、メッセージ（Ｍ）を変換（メッセージブロック（Ｂ）への変換を含む）することで変換メッセージ（Ｍ’）を得るメッセージ変換処理（４０２）を行う。次に、メッセージ変換部２２０は、得た変換メッセージ（Ｍ’）をＭＡＣ処理部１１２へ送付する（Ｓ３０５）。
【００４２】
次に、ＭＡＣ処理部１１２は、撹乱情報（Ｒ）と変換メッセージ（Ｍ’）を認証子計算部２３０へ送付する（Ｓ３０６）。次に、認証子計算部２３０は、撹乱情報（Ｒ）と変換メッセージ（Ｍ’）を用いてメッセージ認証子（Ｔ）を計算する認証子計算処理（４０３）を行う。次に、認証子計算部２３０は、計算して得たメッセージ認証子（Ｔ）をＭＡＣ処理部１１２へ送付する（Ｓ３０７）。
【００４３】
次に、ＭＡＣ処理部１１２は、受け取ったメッセージ認証子（Ｔ）に基づき、メッセージ（Ｍ）に対するメッセージ認証子（Ｃ）（特に第一のＭＡＣ：Ｃ１）を定めて、出力する（Ｓ３０８）。
【００４４】
なお、上記一時使用数値（Ｎ）については、同じ値の一時使用数値（Ｎ）は、一回だけ（その場限り）、メッセージ認証子（Ｃ）の生成に用いられる。即ち、異なるメッセージ（Ｍ）に対しては、異なる値の一時使用数値（Ｎ）を用いる。一時使用数値（Ｎ）の例としては、カウンタや乱数を用いる方法などがある。例えば、コンピュータ（Ａ）１０１，（Ｂ）１２１に、カウンタや乱数生成部を備え、カウンタでのインクリメント値や乱数生成部で生成した乱数値を用いる。
【００４５】
＜第１の構成＞
実施の形態１では、メッセージ認証子として前記非特許文献１記載のＯＭＡＣの方法を基にして構成する例（ＭＡＣ処理部１１２の第１の構成）を説明する。図５及び図６を用いて、ＭＡＣ処理部１１２における撹乱情報生成部２１０、メッセージ変換部２２０、認証子計算部２３０の行う処理について詳細に説明する。図５は、図２のＭＡＣ処理部１１２に対応したＭＡＣ生成方法及びそのブロック構成と処理を例示している。図６は、同ＭＡＣ生成処理の詳細を例示している。図５に示すブロック構成は、撹乱情報生成部２１０が行う撹乱情報生成処理（４０１）、メッセージ変換部２２０が行うメッセージ変換処理（４０２）、及び認証子計算部２３０が行う認証子計算処理（４０３）と、以下で示す詳細な処理との関連を示している。
【００４６】
図５において、第１の構成において、撹乱情報生成部２１０及びその処理（４０１）では、一時使用数値Ｎ（５０２）をブロック暗号化Ｅ（５１１）して撹乱情報（Ｒ）を生成する。メッセージ変換部２２０及びその処理（４０２）では、メッセージＭ（５０１）から、所定ブロック長への分割によりメッセージブロック（Ｂ）：Ｍ[１]（５２１）〜Ｍ[ｍ]（５２３）を得る。１０ｉ（５２４）は、パディング用の値である。また、上記各メッセージブロック（Ｂ）をブロック暗号化Ｅ（５３１〜５３３）して変換メッセージ（Ｍ’）を得る。認証子計算部２３０及びその処理（４０３）では、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、排他的論理和（５１〜５３）と、ブロック暗号化Ｅ（５４１〜５４３）とを有する。その構成で、最初（第１）のメッセージブロック（Ｍ[１]）による変換メッセージ（Ｍ’）と撹乱情報（Ｒ）とによる排他的論理和（５１）を計算しその出力をブロック暗号化Ｅ（５４１）して第１の処理結果を得る。次に、第２のメッセージブロック（Ｍ[２]）による変換メッセージ（Ｍ’）と上記第１の処理結果とによる排他的論理和（５２）を計算しその出力をブロック暗号化Ｅ（５４２）して第２の処理結果を得る。以後同様に連鎖処理し、第ｍのメッセージブロック（Ｍ[ｍ]）による変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果とによる排他的論理和（５３）を計算しその出力をブロック暗号化Ｅ（５４３）して第ｍの処理結果がメッセージ認証子（Ｔ）（５５１）として得られる。
【００４７】
図５及び図６において、ＭＡＣ処理部１１２は、メッセージＭと一時使用数値Ｎを入力として受け取る（Ｓ６０１）。撹乱情報生成部２１０は、一時使用数値Ｎに対して、ブロック暗号計算部２１１を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｎ）を計算し、その結果Ｅ（Ｎ）を撹乱情報（Ｒ）として変数Ｔ１に格納する（Ｓ６０２）。
【００４８】
ＭＡＣ処理部１１２は、ｍにメッセージＭのブロック数を、変数ｊに１を代入する（Ｓ６０３）。ここでブロック数（ｍ）とは、メッセージＭをブロック長ごとに分割した際の、分割して得たメッセージブロック（Ｂ）の数のことである。メッセージＭ（５０１）は、分割により、メッセージブロック（Ｂ）：Ｍ[１]〜Ｍ[ｍ]（５２１〜５２３）となる。
【００４９】
ＭＡＣ処理部１１２は、ｊ＜ｍかどうかを判定する（Ｓ６１１）。この条件が成立する場合（TRUE）はＳ６１２へ行く。条件が成立しない場合（FALSE）はＳ６２１へ行く。
【００５０】
Ｓ６１１で条件が成立した場合、Ｓ６１２で、メッセージ変換部２２０は、メッセージブロックＭ[ｊ]に対して、ブロック暗号計算部２２２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｍ[ｊ]）を計算し、その結果を変換メッセージ（Ｍ’）の一部として変数Ｔ２に格納する（Ｓ６１２）。次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ２との排他的論理和（Ｔ１xor Ｔ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ６１３）。次に、認証子計算部２３０は、変数Ｔ１に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ１）を計算し、その結果を変数Ｔ１に格納する（Ｓ６１４）。次に、ＭＡＣ処理部１１２は、変数ｊにｊ＋１を代入し、Ｓ６１１へと戻る（Ｓ６１５）。
【００５１】
Ｓ６１１で条件が成立しなかった場合、Ｓ６２１で、メッセージ変換部２２０は、パディング部２２１を用いて、メッセージブロックＭ［ｍ］（最後のメッセージブロック（Ｂ））に対してパディングを行う（Ｓ６２１）。本例では、Ｍ[ｍ]に対してパディングされる値を１０ｉ＝‘10…0’（５２４）とする。なお、メッセージブロックＭ[ｍ]のビット長が分割に用いたブロック長と一致する場合、パディングは行わなくてもよい。またその場合、（ｍ＋１）番目のメッセージブロック（Ｂ）として新たなメッセージブロックＭ[ｍ＋１]を追加する形態としてもよい。（ｍ＋１）番目のメッセージブロックを追加する場合は、Ｍ[ｍ]に対してＳ６１２〜Ｓ６１５の処理を行い、Ｓ６２１以降の処理は（ｍ＋１）番目のメッセージブロックに対して行う。
【００５２】
次に、メッセージ変換部２２０は、最後のメッセージブロック（Ｂ）である、パディングされたメッセージブロックＭ[ｍ] | 10…0 に対して、ブロック暗号計算部２２２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｍ[ｍ] | 10…0 )を計算し、その結果を変換メッセージ（Ｍ’）の一部として変数Ｔ２に格納する（Ｓ６２２）。なお、“Ｍ[ｍ] | 10…0”という表現は、Ｍ[ｍ]のパディング前の元データの直後に、パディング（値）の一例として１０ｉ＝‘10…0’（先頭が１でその後ろｉ個のすべてが０）を付加していることを表している。このようなパディングの付加により、Ｍ[ｍ]から元データを取り出す処理などが可能となる。
【００５３】
次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ２との排他的論理和（Ｔ１ xor Ｔ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ６２３）。次に、認証子計算部２３０は、変数Ｔ１に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ１）を計算し、その結果を認証子計算部２３０が出力するメッセージ認証子（Ｔ）として変数Ｔ１に格納する（Ｓ６２４）。そして、ＭＡＣ処理部１１２は、変数Ｔ１から予め定めたビット数を切り出し、メッセージ認証子（Ｔ、特にＣ１）として出力する（Ｓ６２５）。
【００５４】
なお、上記処理は、以下のような変形も可能である。Ｓ６１２，Ｓ６２３で行う演算を排他的論理和（xor）としたが、算術加算でもよい。また、撹乱情報生成部２１０への入力である一時使用数値（Ｎ）は、撹乱情報生成部２１０内で生成してもよい。その場合は、生成した一時使用数値（Ｎ）を出力する必要がある。
【００５５】
また、撹乱情報生成部２１０、メッセージ変換部２２０、及び認証子計算部２３０で用いるブロック暗号Ｅにおける鍵（Ｋ）は、異なる鍵を用いてもよい。また、各ブロック暗号Ｅの計算において、異なる鍵を用いてもよい。ただし、コンピュータ（Ａ）１０１側でＭＡＣ（Ｃ１）を生成する時と、コンピュータ（Ｂ）１２１側で検証時にＭＡＣ（Ｃ２）を再生成する時とで、各々対応するブロック暗号Ｅの計算において同じ鍵を用いることが前提である。
【００５６】
また、上記説明では、メッセージ変換部２２０がメッセージ変換を行う場合を説明したが、メッセージ変換を行わなくともよい。その場合、メッセージ認証の安全性は低下する可能性があるが、ブロック暗号Ｅによる暗号化の処理の回数を削減できるため、高速化することができる。
【００５７】
また、ブロック暗号Ｅに用いる鍵は、コンピュータ（Ａ）１０１と（Ｂ）１２１とが秘密裏に共有している鍵（Ｋ）をそのまま用いてもよいが、鍵（Ｋ）から導出される値を新たな鍵として用いてもよい。例えば、ＥＫ（０）を鍵としてもよい。
【００５８】
また、Ｓ６２１で、ｍ番目のメッセージブロックＭ[ｍ]に対するパディングを行うが、パディング方式としては１０ｉ＝‘10…0’（５２４）を追加する以外にも、‘01…1’やブロック数（ｍ）を示す数値などの他の値を追加してもよい。
【００５９】
また、上記説明は、メッセージ変換処理（４０２）と認証子計算処理（４０３）を、各々分割し、分割した処理を交互に行う場合である。即ち、本例では、まず１番目のメッセージブロックＭ[１]に対する変換処理（５２１，５３１）、次にＭ[１]に対する計算処理（５１，５４１）、次に２番目のメッセージブロックＭ[２]に対する変換処理（５２２，５３２）、次にＭ[２]に対する計算処理（５２，５４２）、……といったような順番で処理している。しかしながら、すべてのメッセージブロックＭ[１]〜Ｍ[ｍ]についてのメッセージ変換処理（４０２）が完了した後に、それらすべての変換メッセージ（Ｍ’）に対する認証子計算処理（４０３）を開始してもよい。また、認証子計算処理（４０３）は、撹乱情報生成処理（４０１）およびメッセージ変換処理（４０２）の後に行えばよく、撹乱情報生成処理（４０１）とメッセージ変換処理（４０２）の順序はどちらでもよい。例えば、メッセージ変換処理（４０２）の後に撹乱情報生成処理（４０１）を行ってもよい。
【００６０】
また、メッセージ変換処理（４０２）では、変換処理すなわちメッセージブロック（Ｂ）：Ｍ[１]〜Ｍ[ｍ]の計算の際、並列計算による高速化を行ってもよい。例えば、Ｅ（Ｍ[１]）とＥ（Ｍ[２]）の暗号化計算を並列に行ってもよい。また、メッセージブロック（Ｂ）の計算順序を入れかえてもよい。例えば、Ｅ（Ｍ[２]）の暗号化計算の後に、Ｅ（Ｍ[１]）の暗号化計算を行ってもよい。
【００６１】
また、本例では、ＭＡＣ処理部１１２の一連のブロック暗号Ｅ（公知技術）の全体はサイドチャネル攻撃に対する耐性を備えると前提している構成であるが、各ブロック暗号Ｅの計算に対して個別にサイドチャネル攻撃への対策を施している構成としてもよい。そのような構成により、メッセージ認証子（Ｃ）の生成において、より一層安全性が増すことになる。
【００６２】
上記説明ではＯＭＡＣを例に構成したが、他のＣＢＣ（Cipher-Block Chaining：暗号ブロック連鎖）モードのメッセージ認証子に対して構成してもよい。ＣＢＣは、ブロック暗号（ＣＢ）の使用方法（モード）の１つである。ＯＭＡＣは、ＣＢＣモードを用いたＭＡＣのうちの１つである。
【００６３】
以上、本実施の形態１によれば、処理中における排他的論理和（５１〜５３）への入力値を、撹乱情報（Ｒ）を用いることで隠蔽および撹乱しており、サイドチャネル攻撃を無効化している。詳しくは以下である。
【００６４】
上記サイドチャネル攻撃は、秘密情報を特定する際に固定値の入力や既知の値の入力を必要とするものを指している。前記非特許文献４によれば、メッセージ認証において次のような排他的論理和が存在する場合、そのメッセージ認証はサイドチャネル攻撃に対して脆弱となる。それは、排他的論理和の二つの入力に対して、一つは固定値かつ攻撃者にとって秘密の値、もう一つは攻撃者にとって既知の値であって攻撃者がその値を変更できる、というような場合である。このような場合を考えて、認証子計算処理部４０３に対応する従来の認証子計算処理部の全体では、サイドチャネル攻撃に対する耐性が無かったと言える。
【００６５】
一方、本実施の形態１では、例えば排他的論理和５１についてみてみると、その一方の入力値である撹乱情報（Ｒ）は、その都度変わる値であって攻撃者にとって秘密の値であるため、他方の入力値である変換メッセージ（Ｍ’）が攻撃者にとって既知の値であったとしても、排他的論理和５１の出力結果を予測できない。他の排他的論理和（５１〜５３）に関しても同様である。このように、認証子計算処理部４０３における排他的論理和（５１〜５３）への入力値を隠蔽および撹乱している本実施の形態１の構成では、サイドチャネル攻撃の無効化が実現されている。
【００６６】
以上説明した通り、実施の形態１による上記メッセージ認証およびＭＡＣ生成の方法及び処理は、サイドチャネル攻撃への耐性に関して優れるという特長がある。
【００６７】
（実施の形態２）
次に、図７〜図８を参照して本発明の実施の形態２を説明する。実施の形態２では、メッセージ認証子として前記非特許文献２記載のＰＭＡＣの方法を基にして構成する例（ＭＡＣ処理部１１２の第２の構成）を説明する。実施の形態２では、基本的に実施の形態１と共通する構成において、主に認証子計算処理（４０３）が異なる。
【００６８】
＜第２の構成＞
図７及び図８を用いて、ＭＡＣ処理部１１２における撹乱情報生成部２１０、メッセージ変換部２２０、及び認証子計算部２３０の行う処理について詳細に説明する。図７のブロック構成は、撹乱情報生成部２１０が行う撹乱情報生成処理（４０１）、メッセージ変換部２２０が行うメッセージ変換処理（４０２）、認証子計算部２３０が行う認証子計算処理（４０３）と、以下で示す詳細な処理との関連を示している。
【００６９】
図７において、第２の構成において、撹乱情報生成部２１０及びその処理（４０１）では、一時使用数値Ｎ（７０２）をブロック暗号化Ｅ（７１１）して撹乱情報（Ｒ）を生成する。メッセージ変換部２２０及びその処理（４０２）では、メッセージＭ（７０１）から、所定ブロック長への分割によりメッセージブロック（Ｂ）：Ｍ[１]（７２１）〜Ｍ[ｍ]（７２４）を得る。１０ｉ（７２５）は、パディング用の値である。また、上記各メッセージブロック（Ｂ）をブロック暗号化Ｅ（７３１〜７３４）して変換メッセージ（Ｍ’）を得る。認証子計算部２３０及びその処理（４０３）では、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、第１の排他的論理和（７１〜７３，７７）と、ブロック暗号化Ｅ（７５１〜７５４）と、第２の排他的論理和（７４〜７６）とを有する。その構成で、最初（第１）のメッセージブロック（Ｍ[１]）による変換メッセージ（Ｍ’）とγ１Ｌ（７４１）とによる排他的論理和（７１）を計算し、その出力をブロック暗号化Ｅ（７５１）し、その出力と撹乱情報（Ｒ）とによる排他的論理和（７４）により第１の処理結果を得る。次に、第２のメッセージブロック（Ｍ[２]）による変換メッセージ（Ｍ’）とγ２Ｌ（７４２）とによる排他的論理和（７２）を計算し、その出力をブロック暗号化Ｅ（７５２）し、その出力と第１の処理結果とによる排他的論理和（７５）により第２の処理結果を得る。以後同様に連鎖処理し、第（ｍ−１）のメッセージブロック（Ｍ[ｍ−１]）による変換メッセージ（Ｍ’）とγｍ−１Ｌ（７４３）とによる排他的論理和（７３）を計算し、その出力をブロック暗号化Ｅ（７５３）し、その出力と第（ｍ−２）の処理結果とによる排他的論理和（７６）により第（ｍ−１）の処理結果を得る。最後に、第ｍのメッセージブロック（Ｍ[ｍ]）による変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果とによる排他的論理和（７７）を計算しその出力を暗号化（７５４）して第ｍの処理結果がメッセージ認証子（Ｔ）（７６１）として得られる。
【００７０】
図７及び図８において、ＭＡＣ処理部１１２は、メッセージＭ、一時使用数値Ｎ、を入力として受け取る（Ｓ８０１）。次に、撹乱情報生成部２１０は、一時使用数値Ｎに対して、ブロック暗号計算部２１１を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｎ）を計算し、その結果を撹乱情報（Ｒ）として変数Ｔ１に格納する（Ｓ８０２）。次に、ＭＡＣ処理部１１２は、ｍにメッセージＭのブロック数を、変数ｊに１を代入する（Ｓ８０３）。
【００７１】
次に、ＭＡＣ処理部１１２はｊ＜ｍかどうかを判定する（Ｓ８１１）。条件が成立する場合(TRUE)は、Ｓ８１２へ行く。条件が成立しない場合（FALSE）はＳ８２１へ行く。
【００７２】
Ｓ８１１で条件が成立した場合、Ｓ８１２で、メッセージ変換部２２０は、メッセージブロックＭ[ｊ]に対して、ブロック暗号計算部２２２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｍ[ｊ]）を計算し、その結果を変換メッセージ（Ｍ’）の一部として変数Ｔ２に格納する（Ｓ８１２）。
【００７３】
次に、認証子計算部２３０は、変数Ｔ２と数値γｊＬとの排他的論理和（Ｔ２ xor γｊＬ）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ２に格納する（Ｓ８１３）。ここで、Ｌは０に対するブロック暗号Ｅの暗号化結果Ｌ＝ＥＫ（０）により与えられる数値であり、γｊはグレイコードと呼ばれるもので、各ｉに対してγｉとγｉ＋１とは１ビットのみ異なる。具体的には、γ０＝０とし、ｉ＝０，１，……に対して、γｉ＋１＝γｉxor ((0…01) << ntz(ｉ))と定めることにより構成できる。ただし、“ａ << ｂ”は、ａをｂビットだけ左シフトすることを表し、ntz(ｉ)は、数値ｉをバイナリ表現で表したときにビットの値が１となる一番右のビット位置である。例えば、ntz(７)＝０、ntz(８)＝３である。また、γｊＬは、γｊとＬとのバイナリ体における乗算結果である。
【００７４】
次に、認証子計算部２３０は、変数Ｔ２に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ２）を計算し、その結果を変数Ｔ２に格納する（Ｓ８１４）。次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ２との排他的論理和（Ｔ１xor Ｔ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ８１５）。次に、ＭＡＣ処理部１１２は、変数ｊにｊ＋１を代入し、Ｓ８１１へと戻る（Ｓ８１６）。
【００７５】
Ｓ８１１で条件が成立しなかった場合、Ｓ８２１で、メッセージ変換部２２０は、パディング部２２１を用いてメッセージブロックＭ[ｍ]に対してパディングを行う。なお、メッセージブロックＭ[ｍ]のビット長がブロック長と一致する場合、パディングは行わなくてもよい。また、（ｍ＋１）番目のメッセージブロック（Ｂ）として新たなメッセージブロックＭ[ｍ＋１]を追加してもよい。（ｍ＋１）番目のメッセージブロックＭ[ｍ＋１]を追加する場合は、Ｍ[ｍ]に対してＳ８１２〜Ｓ８１６の処理を行い、Ｓ８２１以降の処理は（ｍ＋１）番目のメッセージブロックＭ[ｍ＋１]に対して行う。
【００７６】
次に、メッセージ変換部２２０は、パディングされたメッセージブロックＭ[ｍ] | 10…0 に対して、ブロック暗号計算部２２２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｍ[ｍ] | 10…0）を計算し、その結果を変換メッセージ（Ｍ’）の一部として変数Ｔ２に格納する（Ｓ８２２）。次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ２の排他的論理和（Ｔ１xor Ｔ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ８２３）。次に、認証子計算部２３０は、変数Ｔ１に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ１）を計算し、その結果を認証子計算部２３０が出力するメッセージ認証子（Ｔ）として変数Ｔ１に格納する（Ｓ８２４）。次に、ＭＡＣ処理部１１２は、変数Ｔ１から予め定めたビット数を切り出し、メッセージ認証子（Ｔ、特にＣ１）として出力する（Ｓ８２５）。
【００７７】
なお、上記処理は、実施の形態１で説明したのと同様の各種の変形が可能である。
【００７８】
以上、本実施の形態２によれば、処理中における排他的論理和（７４〜７７）への入力値を隠蔽および撹乱しており、サイドチャネル攻撃の無効化を実現している。実施の形態１と同様に、実施の形態２によるメッセージ認証及びＭＡＣ生成の方法及び処理は、サイドチャネル攻撃への耐性に関して優れるという特長がある。
【００７９】
（実施の形態３）
次に、図９〜図１０を参照して本発明の実施の形態３を説明する。実施の形態３では、メッセージ認証子として前記非特許文献２記載のＰＭＡＣの方法を基にして構成し、更にオリジナルのＰＭＡＣ（既に確立されている手法）の出力するメッセージ認証子と同じ値のメッセージ認証子を出力する構成とした例（ＭＡＣ処理部１１２の第３の構成）を説明する。実施の形態３では、基本的に実施の形態１や２と共通する構成において、主にメッセージ変換処理（４０２）及び認証子計算処理（４０３）が異なる。実施の形態３のメッセージ変換部２２０は、ブロック暗号計算部２２２を備えない。そのような構成により、回路規模やプログラムのコードサイズを削減することができる。前記実施の形態２では、ＰＭＡＣに対し、入力値（Ｍ）が同じでも出力値（Ｔ）は異なるものとなる。実施の形態３では、本構成のＰＭＡＣに対し、その入力値（Ｍ）が、オリジナルのＰＭＡＣの入力値と同じであるなら、それらの出力値（Ｔ）が同じとなる。出力が同じになることは、互換性などの点で利点がある。
【００８０】
＜第３の構成＞
図９及び図１０を用いて、ＭＡＣ処理部１１２における撹乱情報生成部２１０、メッセージ変換部２２０、及び認証子計算部２３０の行う処理について詳細に説明する。図９のブロック構成は、撹乱情報生成部２１０が行う撹乱情報生成処理（４０１）、メッセージ変換部２２０が行うメッセージ変換処理（４０２）、認証子計算部２３０が行う認証子計算処理（４０３）と、以下で示す詳細の処理との関連を示している。
【００８１】
図９において、第３の構成において、認証子計算部２３０及びその処理（４０３）では、メッセージブロック（Ｂ）による変換メッセージ（Ｍ’）ごとに、第１（第１種）の排他的論理和（９１〜９３）と、ブロック暗号化Ｅ（９４１〜９４３）と、第２（第２種）の排他的論理和（９４〜９７）と、第３（第３種）の排他的論理和（９８）とを有する。認証子計算処理（４０３）における各種処理中の中間データ（ｄ１〜ｄ４）を用いて説明する。その構成で、最初（第１）のメッセージブロックによる変換メッセージ（Ｍ’）とγ１Ｌ（９３１）とによる第１の排他的論理和（９１）を計算し、その出力をブロック暗号化Ｅ（９４１）し、その出力（第一の中間データ：ｄ１）と撹乱情報（Ｒ）とによる第２の排他的論理和（９４）により第１の処理結果（第二の中間データ：ｄ２）を得る。次に、第２のメッセージブロックによる変換メッセージ（Ｍ’）とγ２Ｌ（９３２）とによる第１の排他的論理和（９２）を計算し、その出力をブロック暗号化Ｅ（９４２）し、その出力（ｄ１）と第１の処理結果（ｄ２）とによる第２の排他的論理和（９５）により第２の処理結果（ｄ２）を得る。以後同様に連鎖処理し、第（ｍ−１）のメッセージブロックによる変換メッセージ（Ｍ’）とγｍ−１Ｌとによる第１の加算を計算し、その出力を暗号化し、その出力（ｄ１）と第（ｍ−２）の処理結果（ｄ２）とによる第２の加算により第（ｍ−１）の処理結果（ｄ２）を得る。そして、第ｍのメッセージブロックによる変換メッセージ（Ｍ’）と第（ｍ−１）の処理結果（ｄ２）とＬｕ−１とによる加算を計算した出力（第三の中間データ：ｄ３）を得る。そして、その出力（ｄ３）と、前記最初（第１）の処理で用いたのと同じ撹乱情報（Ｒ）とを加算した出力（第四の中間データ：ｄ４）を得て、その出力（ｄ４）を暗号化した第ｍの処理結果がメッセージ認証子（Ｔ）として得られる。
【００８２】
図９及び図１０において、ＭＡＣ処理部１１２は、メッセージＭ、一時使用数値Ｎ、を入力として受け取る（Ｓ１００１）。次に、撹乱情報生成部２１０は、一時使用数値Ｎに対して、ブロック暗号計算部２１１を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｎ）を計算し、その結果を撹乱情報（Ｒ）として変数Ｔ１及びＴ３に格納する（Ｓ１００２）。次に、ＭＡＣ処理部１１２は、ｍにメッセージＭのブロック数を、変数ｊに１を代入する（Ｓ１００３）。
【００８３】
次に、ＭＡＣ処理部１１２は、ｊ＜ｍかどうかを判定する（Ｓ１０１１）。条件が成立する場合（TRUE）はＳ１０１２へ行く。条件が成立しない場合（FALSE）はＳ１０２１へ行く。
【００８４】
Ｓ１０１１で条件が成立した場合、Ｓ１０１２で、メッセージ変換部２２０は、メッセージブロックＭ[ｊ]の値を変換メッセージ（Ｍ’）の一部として変数Ｔ２に格納する（Ｓ１０１２）。次に、認証子計算部２３０は、変数Ｔ２と数値γｊＬとの排他的論理和（Ｔ２xor Ｌ）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ２に格納する（Ｓ１０１３）。
【００８５】
次に、認証子計算部２３０は、変数Ｔ２に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ２）を計算し、その結果を変数Ｔ２に格納する（Ｓ１０１４）。次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ２との排他的論理和（Ｔ１ xorＴ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ１０１５）。次に、ＭＡＣ処理部１１２は、変数ｊにｊ＋１を代入し、Ｓ１０１１へと戻る（Ｓ１０１６）。
【００８６】
Ｓ１０１１で条件が成立しなかった場合、Ｓ１０２１で、メッセージ変換部２２０は、パディング部２２１を用いてメッセージブロックＭ[ｍ]に対してパディングを行い、その結果を変換メッセージ（Ｍ’）の一部とする。なお、メッセージブロックＭ[ｍ]のビット長がブロック長と一致する場合、パディングは行わない。
【００８７】
次に、認証子計算部２３０は、パディングされたメッセージブロックＭ[ｍ] | 10…0 に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｍ[ｍ] | 10…0）を計算し、その結果を変数Ｔ２に格納する（Ｓ１０２２）。次に、  認証子計算部２３０は、変数Ｔ１、変数Ｔ２、及び数値Ｌｕ−１（９４４）との排他的論理和（Ｔ１xor Ｔ２ xor Ｌｕ−１）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ１０２３）。ただし、数値Ｌｕ−１との排他的論理和を行うのは、メッセージブロックＭ[ｍ]がブロック長と一致する場合、すなわちパディングを行わない場合である。パディングを行わない場合は、排他的論理和（Ｔ１xor Ｔ２）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する。また、ｕは‘0…010’を示す数値であり、ｕ−１はバイナリ体におけるｕの逆元である。すなわち、ｕ−１はバイナリ体の乗算においてｕｕ−１＝１を満たす数値である。Ｌｕ−１は、Ｌとｕ−１とのバイナリ体における乗算結果である。
【００８８】
次に、認証子計算部２３０は、変数Ｔ１と変数Ｔ３との排他的論理和（Ｔ１ xor Ｔ３）を、論理算術演算部２３１を用いて計算し、その結果を変数Ｔ１に格納する（Ｓ１０２４）。次に、認証子計算部２３０は、変数Ｔ１に対して、ブロック暗号計算部２３２を用いてブロック暗号Ｅによる暗号化結果Ｅ（Ｔ１）を計算し、その結果を認証子計算部２３０が出力するメッセージ認証子（Ｔ）として変数Ｔ１に格納する（Ｓ１０２５）。次に、ＭＡＣ処理部１１２は、変数Ｔ１から予め定めたビット数を切り出し、メッセージ認証子（Ｔ、特にＣ１）として出力する（Ｓ１０２６）。
【００８９】
認証子計算処理（４０３）におけるブロック暗号化Ｅ後の排他的論理和（９４，９８）を通じた処理において、Ｓ１０１５で最初の排他的論理和（９４）にて付加された撹乱情報（Ｒ）は、Ｓ１０２４で最後の排他的論理和（９４）にてキャンセルされる（取り除かれる）。そのため、本実施の形態３での出力するメッセージ認証子（Ｔ）の値は、オリジナルのＰＭＡＣでの出力するメッセージ認証子の値と等しくなる。
【００９０】
なお、上記処理は、実施の形態１で説明したのと同様の各種の変形が可能である。
【００９１】
以上、本実施の形態３によれば、処理中における排他的論理和（９４〜９８）への入力値を隠蔽および撹乱しており、サイドチャネル攻撃の無効化を実現している。実施の形態１や２と同様に、実施の形態３によるメッセージ認証及びＭＡＣ生成の方法及び処理は、サイドチャネル攻撃への耐性に関して優れ、また、オリジナルのＰＭＡＣと同じメッセージ認証子を出力するという特長がある。
【００９２】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。例えば、各実施の形態におけるＭＡＣ処理部、撹乱情報生成部、メッセージ変換部、認証子計算部、論理算術演算部、ブロック暗号計算部、パディング部などの処理は、コプロセッサまたは専用のハードウェアを用いて行ってもよい。
【産業上の利用可能性】
【００９３】
本発明は、メッセージ認証を用いる情報処理装置などに利用可能である。
【図面の簡単な説明】
【００９４】
【図１】本発明の実施の形態１〜３におけるメッセージ認証システムの構成を示す図である。
【図２】本発明の実施の形態１〜３におけるメッセージ認証子処理部の構成を示す図である。
【図３】本発明の実施の形態１〜３におけるメッセージ認証子生成処理における情報の受け渡しを例示するシーケンス図である。
【図４】本発明の実施の形態１〜３におけるメッセージ認証子生成方法及び処理の概要を例示するフローチャートである。
【図５】本発明の実施の形態１におけるメッセージ認証子生成方法及びそのブロック構成と処理を例示する図である。
【図６】本発明の実施の形態１におけるメッセージ認証子生成方法及び処理の詳細を例示するフローチャートである。
【図７】本発明の実施の形態２におけるメッセージ認証子生成方法及びそのブロック構成と処理を例示する図である。
【図８】本発明の実施の形態２におけるメッセージ認証子生成方法及び処理の詳細を例示するフローチャートである。
【図９】本発明の実施の形態３におけるメッセージ認証子生成方法及びそのブロック構成と処理を例示する図である。
【図１０】本発明の実施の形態３におけるメッセージ認証子生成方法及び処理の詳細を例示するフローチャートである。
【符号の説明】
【００９５】
１０１…コンピュータ（Ａ）（ＭＡＣ生成装置）、１０２，１２２…記憶部、１０３，１２３…ＲＡＭ、１０４，１２４…定数、１０５，１２５…秘密情報、１０６，１２６…ＲＯＭ、１０７，１２７…外部記憶装置、１０８，１２８…ディスプレイ、１０９，１２９…キーボード、１１０，１３０…入出力インタフェース、１１１，１３１…処理部、１１２，１３２…ＭＡＣ処理部、１１３，１３３…ＣＰＵ、１１４，１３４…コプロセッサ、１２１…コンピュータ（Ｂ）（ＭＡＣ検証装置）、１４１，１４３…データ、１４２…ネットワーク、２１０…撹乱情報生成部、２２０…メッセージ変換部、２３０…認証子計算部、２１１，２２２，２３２…ブロック暗号計算部、２２１…パディング部、２３１…論理算術演算部、４０１…撹乱情報生成処理、４０２…メッセージ変換処理、４０３…認証子計算処理。
【図１】
0004810289.tif 000002
【図２】
0004810289.tif 000003
【図３】
0004810289.tif 000004
【図４】
0004810289.tif 000005
【図５】
0004810289.tif 000006
【図６】
0004810289.tif 000007
【図７】
0004810289.tif 000008
【図８】
0004810289.tif 000009
【図９】
0004810289.tif 000010
【図１０】
0004810289.tif 000011