(57)【特許請求の範囲】
【請求項１】
メッセージを入力する入力手段と、
前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、
１ブロック目の入力と鍵との排他的論理和をとり、その結果をブロック暗号の部品を基にした鍵付き又は鍵なしの１ブロック置換に入力し、得られた出力と２ブロック目の入力との排他的論理和の結果が出力となる２ブロック入力１ブロック出力の鍵付きハッシュ関数を前記２ブロック入力１ブロック出力の鍵付きハッシュ関数を木の深さごとに異なる鍵を使用して繰り返して構成される２分木の葉の部分へ前記メッセージを入力することで前記２分木の根の部分において１ブロックのハッシュ値を出力することにより前記パディング済みメッセージを圧縮する修正木ハッシュ手段と、
前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、
前記タグと前記メッセージとを連結して出力する出力手段と、
を備えたことを特徴とするメッセージ認証装置。
【請求項２】
メッセージを入力する入力手段と、
前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、
ブロック暗号と該ブロック暗号の一部分から導出される置換処理とを、前記パディング済みメッセージを１ブロックずつ足しながら連鎖させて１ブロックのハッシュ値へ圧縮する交替型連鎖手段と、
前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、
前記タグと前記メッセージとを連結して出力する出力手段と、
を備えたことを特徴とするメッセージ認証装置。
【請求項３】
メッセージを入力する入力手段と、
前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、
前記パディング済みメッセージを、請求項２記載の交替型連鎖手段の一部の処理を請求項１記載の修正木ハッシュ手段で置き換えた構造により圧縮して１ブロック分のハッシュ値を出力する修正木連鎖ハッシュ手段と、
前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、
前記タグと前記メッセージとを連結して出力する出力手段と、
を備えたことを特徴とするメッセージ認証装置。
【請求項４】
前記修正木ハッシュ手段が、ＡＥＳの段関数の４回以上の繰り返しを用いて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項１記載のメッセージ認証装置。
【請求項５】
前記交替型連鎖手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項２記載のメッセージ認証装置。
【請求項６】
前記修正木連鎖ハッシュ手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項３記載のメッセージ認証装置。
【請求項７】
ブロック暗号と、該ブロック暗号の段関数を利用した置換処理とを用いることを特徴とする請求項１から３のいずれか１項に記載のメッセージ認証装置。
【請求項８】
入力手段が、メッセージを入力する第１のステップと、
パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、
修正木ハッシュ手段が、１ブロック目の入力と鍵との排他的論理和をとり、その結果をブロック暗号の部品を基にした鍵付き又は鍵なしの１ブロック置換に入力し、得られた出力と２ブロック目の入力との排他的論理和の結果が出力となる２ブロック入力１ブロック出力の鍵付きハッシュ関数を前記２ブロック入力１ブロック出力の鍵付きハッシュ関数を木の深さごとに異なる鍵を使用して繰り返して構成される２分木の葉の部分へ前記メッセージを入力することで前記２分木の根の部分において１ブロックのハッシュ値を出力することにより前記パディング済みメッセージを圧縮する第３のステップと、
調整値付暗号化手段が、前記出力されたハッシュ値を暗号化してタグとする第４のステップと、
出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップと、
を有することを特徴とするメッセージ認証方法。
【請求項９】
入力手段が、メッセージを入力する第１のステップと、
パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、
交替型連鎖手段が、ブロック暗号と該ブロック暗号の一部分から導出される置換処理とを、前記出力されたパディング済みメッセージを１ブロックずつ足しながら連鎖させて１ブロックのハッシュ値へ圧縮する第３のステップと、
調整値付暗号化手段が、前記ハッシュ値を暗号化してタグとする第４のステップと、
出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップと、
を有することを特徴とするメッセージ認証方法。
【請求項１０】
入力手段が、メッセージを入力する第１のステップと、
パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、
修正木連鎖ハッシュ手段が、前記出力されたパディング済みメッセージを、請求項２記載の交替型連鎖手段の一部の処理を請求項１記載の修正木ハッシュ手段で置き換えた構造により圧縮して１ブロック分のハッシュ値を出力する第３のステップと、
調整値付暗号化手段が、前記ハッシュ値を暗号化してタグとする第４のステップと、
出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップと、
を有することを特徴とするメッセージ認証方法。
【請求項１１】
前記修正木ハッシュ手段が、ＡＥＳの段関数の４回以上の繰り返しを用いて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項８記載のメッセージ認証方法。
【請求項１２】
前記交替型連鎖手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項９記載のメッセージ認証方法。
【請求項１３】
前記修正木連鎖ハッシュ手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成されることを特徴とする請求項１０記載のメッセージ認証方法。
【請求項１４】
ブロック暗号と、該ブロック暗号の段関数を利用した置換処理とを用いることを特徴とする請求項８から１０のいずれか１項に記載のメッセージ認証方法。
【請求項１５】
請求項８から１０のいずれか１項に記載のメッセージ認証方法を、コンピュータに実行させるためのメッセージ認証プログラム。
【請求項１６】
請求項１５記載のメッセージ認証プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロック暗号と、ブロック暗号の一部の処理との組合せにより構築された、汎用的で高速な、メッセージ認証装置、メッセージ認証方法、メッセージ認証プログラムとその記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証とは、メッセージに対して秘密鍵を知るものだけが計算できるタグを付与することであり、メッセージが正当であることを保証する技術である。例えば、メッセージ認証を用いれば、秘密鍵を共有した２者の通信において、通信の間に行われた、第３者による改ざんを検知することが可能となる。
【０００３】
具体的には、送信者がメッセージとタグを受信者に送ったとき、受信者側では受け取ったメッセージからタグを計算し、受信したタグとの一致をみることで、メッセージが正当な送信者から送られたものかどうかを判断することができる。なお、通常のメッセージ認証方式ではタグの生成方法さえ決まれば受信者側の認証方法は一意に定まるため、タグの生成方法だけを記述すれば十分である。
【０００４】
メッセージ認証の方法として、ブロック暗号を用いた方式が数多く知られている。これらはブロック暗号のメッセージ認証モードとも呼ばれ、古典的なＣＢＣ−ＭＡＣモードをはじめとして、ＣＢＣ−ＭＡＣを改良したＥＭＡＣ、ＸＣＢＣ、ＯＭＡＣなどが知られている。ＣＢＣ−ＭＡＣは可変長ブロックメッセージを受け入れた場合には安全でなく、また、メッセージがブロック長の倍数でない場合の処理が定められていないという欠点が知られている。
【０００５】
また、ＥＭＡＣ、ＸＣＢＣ、ＯＭＡＣなどの改良されたモードは、ＣＢＣ−ＭＡＣとほぼ同等の処理量であり、任意の長さ（ビット）のメッセージについて安全である。ＣＢＣ−ＭＡＣを含めたこれらのモードについては、例えば非特許文献１に記載されている。
【０００６】
ここで、例として、ＯＭＡＣのブロック図を図１に示す。図１に示すように、これらのモードはシンプルであるが、タグの生成においておよそメッセージのブロック数だけブロック暗号を動作させる必要がある。そのため、その速度は常にブロック暗号の速度を超えることはない。
【０００７】
一方、ブロック暗号だけを用いるのではなく、ユニバーサルハッシュ関数と呼ばれる鍵つきの関数を組み合わせてメッセージ認証を実現する方法もよく知られている。これはユニバーサルハッシュ関数の提案者の名前を取って、Ｃａｒｔｅｒ−Ｗｅｇｍａｎ認証方式とも呼ばれる。実装環境に応じて最適化されたユニバーサルハッシュ関数は現在よく使われるブロック暗号よりも数倍高速に動作することが報告されている。このようなユニバーサルハッシュ関数は、例えば非特許文献２に記載されている。
【０００８】
また、小さな入出力幅のユニバーサルハッシュ関数を用いて、入力幅を任意に拡大する（出力幅はそのまま）方法がいくつか知られている。その一つの方式が非特許文献３に記載されている修正木ハッシュである。この修正木ハッシュを、２ブロック入力、１ブロック出力のユニバーサルハッシュ関数Ｈを用いる場合で以下に説明する。入力Ｘがｍブロック（Ｘ＝（Ｘ1、Ｘ2・・・Ｘm））であるとし、Ｈi（但し、ｉ＝１、２・・・）をそれぞれ独立な鍵を用いるＨの実現とする。Ｈによる修正木ハッシュをＭＴHとすると、以下に示す式（１）で表される。
【０００９】
ＭＴH(X)＝Ｇ［ＨS］（Ｇ［ＨS-1］（・・・Ｇ［Ｈ1］（Ｘ）・・・））・・・式（１）
入力が偶数ブロック数の場合：
Ｇ［Ｈi］（Ｘ）＝Ｈi（Ｘ1，Ｘ2）‖Ｈi（Ｘ3，Ｘ4）‖・・・‖Ｈi（Ｘm-1，Ｘm）
入力が奇数ブロック数の場合：
Ｇ［Ｈi］（Ｘ）＝Ｈi（Ｘ1，Ｘ2）‖Ｈi（Ｘ3，Ｘ4）‖・・・‖Ｈi（Ｘm-2，Ｘm-1）‖Ｘm
但し、ｓ＝ｌｏｇ（ｍ）（対数の底は２）以上の最小の整数
【００１０】
ＭＴHは、ブロック長の整数倍の長さの任意のメッセージを受け入れ、その出力は常に１ブロックの長さになる。
式（１）が示すように、ｍブロック平文を処理するのに修正木ハッシュは高々ｌｏｇ（ｍ）＋１個のＨの鍵を用意すればよい。非特許文献３では、修正木ハッシュを非特許文献２に記載のＭＭＨハッシュを用いて実現している。
【００１１】
Ｃａｒｔｅｒ−Ｗｅｇｍａｎ認証方式では、タグ生成の速度はユニバーサルハッシュ関数の速度にほぼ一致するため、一般的にＣＢＣ−ＭＡＣなどのブロック暗号のみの認証モードよりも高速である。しかし、どのような計算機環境でも実装可能で、かつ高速であるユニバーサルハッシュ関数は知られていないため、ユニバーサルハッシュ関数が高速に実装可能な環境でないと使用できないことと、二つの部品を実装するためプログラムのサイズが一般に大きくなることが問題となる。
【００１２】
これらの問題を解決する一つのアプローチが、ブロック暗号とその部品とを組み合わせることである。非特許文献４において、そのような組合せによるメッセージ認証方式が提案されている。これはブロック暗号の一部の段関数をＣＢＣ−ＭＡＣのように反復処理させることで、ブロック暗号の速度よりも高速なタグ生成処理を実現している。
【００１３】
しかし、この方式には非特許文献１に記載のブロック暗号認証モードや、ユニバーサルハッシュ関数とブロック暗号を組み合わせる方式が持つ理論的な安全性の保証がないという大きな欠点がある。ここでの理論的安全性とは、認証方式の安全性が常にブロック暗号そのものの安全性に帰着できるという性質を指す。詳しい定義などは非特許文献１に記載されている。理論的安全性を持たない認証方式の場合、使用しているブロック暗号がどんなに強いものであろうとタグの偽造が容易にできてしまう可能性がある。
【００１４】
また、特許文献１には、メッセージ認証において、ＸＣＢＣにおける安全性を損なうことなく処理コストを削減する技術が開示されている。本技術は、デジタルデータのデータ長がブロック長の倍数である場合は、最終ブロックに鍵Ｋ１及び別の鍵Ｋ２のいずれか一方の鍵と排他的論理輪をとって暗号化を行い、デジタルデータのデータ長がブロック長の倍数でない場合は、最終ブロックの末尾に１を付加し、さらにブロック長に収まるよう０を付加したデータを上記鍵Ｋ１及び別の鍵Ｋ２のいずれか一方の鍵とは異なる別の鍵Ｋ２及び鍵Ｋ１のいずれか一方の鍵との排他的論理和をとって暗号化を行うものである。
【特許文献１】
特開２００３−３３３０３６号公報
【非特許文献１】
岩田  哲、ブロック暗号利用モードの安全性に関する調査、独立行政法人情報処理推進機構（IPA）暗号技術関連の調査報告、2003年
【非特許文献２】
S. Halevi and H. Krawczyk, MMH:Software Message Authentication iｎ  ｔｈｅ  Ｇｂｉｔ／ｓｅｃｏｎｄ  ｒａｔｅｓ，Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，ＦＳＥ’９７，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ；Ｖｏｌ．１２６７，Ｆｅｂ．１９９７
非特許文献３：Ｍａｒｔｉｎ  Ｂｏｅｓｇａａｒｄ，Ｏｖｅ  Ｓｃａｖｅｎｉｕｓ，Ｔｈｏｍａｓ  Ｐｅｄｅｒｓｅｎ，Ｔｈｏｍａｓ  Ｃｈｒｉｓｔｅｎｓｅｎ，Ｅｒｉｋ  Ｚｅｎｎｅｒ，Ｂａｄｇｅｒ−Ａ  Ｆａｓｔ  ａｎｄ  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  ＭＡＣ，Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｎｅｔｗｏｒｋ  Ｓｅｃｕｒｉｔｙ（ＡＣＮＳ）２００５
非特許文献４：Ｊ．Ｄａｅｍｅｎ  ａｎｄ  Ｖ．Ｒｉｊｍｅｎ，Ａ  Ｎｅｗ  ＭＡＣ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ＡＬＲＥＤ  ａｎｄ  ａ  Ｓｐｅｃｉｆｉｃ  Ｉｎｓｔａｎｃｅ  ＡＬＰＨＡ−ＭＡＣ、Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，ＦＳＥ  ２００５，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ；Ｖｏｌ．３５５７，Ｆｅｂ．２００５
発明の開示
発明が解決しようとする課題
［００１５］
しかし、ＣＢＣ−ＭＡＣなどの現在知られている安全なブロック暗号の認証モードでは、すべての入力されたメッセージの各ブロック毎にブロック暗号を適用するため、ブロック暗号そのものの速度を超えた速度は達成できないという問題点があった。
［００１６］
また、あらゆる環境で高速に動作するユニバーサルハッシュ関数は知られていないということ、及び、ブロック暗号とユニバーサルハッシュ関数の両方を実装するためにプログラムサイズが大きくなるという理由から、ブロック暗号モードよりも高速なＣａｒｔｅｒ−Ｗｅｇｍａｎ認証は、実装できる環境が限定されるという問題があった。
［００１７］
本発明は、上記のような問題点に鑑み、ブロック暗号とその一部の部品を組み合わせて、既存のブロック暗号の認証モードより高速で、理論的安全性を有し、事前処理や使用するメモリ量の点でも効率のよい、メッセージ認証装置、メッセージ認証方法、メッセージ認証プログラムとその記録媒体を提供することを目的とする。
課題を解決するための手段
［００１８］
請求項１に記載の発明は、メッセージを入力する入力手段と、前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、１ブロック目の入力と鍵との排他的論理和をとり、その結果をブロック暗号の部品を基にした鍵付き又は鍵なしの１ブロック置換に入力し、得られた出力と２ブロック目の入力との排他的論理和の結果が出力となる２ブロック入力１ブロック出力の鍵付きハッシュ関数を前記２ブロック入力１ブロック出力の鍵付きハッシュ関数を木の深さごとに異なる鍵を使用して繰り返して構成される２分木の葉の部分へ前記メッセージを入力することで前記２分木の根の部分において１ブロックのハッシュ値を出力することにより前記パディング済みメッセージを圧縮する修正木ハッシュ手段と、前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、前記タグと前記メッセージとを連結して出力する出力手段とを備えたメッセージ認証装置としたことを特徴とする。
【００１９】
請求項２に記載の発明は、メッセージを入力する入力手段と、前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、ブロック暗号と該ブロック暗号の一部分から導出される置換処理とを、前記パディング済みメッセージを１ブロックずつ足しながら連鎖させて１ブロックのハッシュ値へ圧縮する交替型連鎖手段と、前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、前記タグと前記メッセージとを連結して出力する出力手段とを備えたメッセージ認証装置としたことを特徴とする。
【００２０】
請求項３に記載の発明は、メッセージを入力する入力手段と、前記メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、前記パディング済みメッセージを、請求項２記載の交替型連鎖手段の一部の処理を請求項１記載の修正木ハッシュ手段で置き換えた構造により圧縮して１ブロック分のハッシュ値を出力する修正木連鎖ハッシュ手段と、前記ハッシュ値を暗号化してタグとする調整値付暗号化手段と、前記タグと前記メッセージとを連結して出力する出力手段とを備えたメッセージ認証装置としたことを特徴とする。
【００２１】
請求項４に記載の発明は、前記修正木ハッシュ手段が、ＡＥＳの段関数の４回以上の繰り返しを用いて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項１記載のメッセージ認証装置としたことを特徴とする。
【００２２】
請求項５に記載の発明は、前記交替型連鎖手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項２記載のメッセージ認証装置としたことを特徴とする。
【００２３】
請求項６に記載の発明は、前記修正木連鎖ハッシュ手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項３記載のメッセージ認証装置としたことを特徴とする。
【００２４】
請求項７に記載の発明は、ブロック暗号と、該ブロック暗号の段関数を利用した置換処理とを用いる請求項１から３のいずれか１項に記載のメッセージ認証装置としたことを特徴とする。
［００２５］
請求項８に記載の発明は、入力手段が、メッセージを入力する第１のステップと、パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、修正木ハッシュ手段が、１ブロック目の入力と鍵との排他的論理和をとり、その結果をブロック暗号の部品を基にした鍵付き又は鍵なしの１ブロック置換に入力し、得られた出力と２ブロック目の入力との排他的論理和の結果が出力となる２ブロック入力１ブロック出力の鍵付きハッシュ関数を前記２ブロック入力１ブロック出力の鍵付きハッシュ関数を木の深さごとに異なる鍵を使用して繰り返して構成される２分木の葉の部分へ前記メッセージを入力することで前記２分木の根の部分において１ブロックのハッシュ値を出力することにより前記パディング済みメッセージを圧縮する第３のステップと、調整値付暗号化手段が、前記出力されたハッシュ値を暗号化してタグとする第４のステップと、出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップとを有するメッセージ認証方法としたことを特徴とする。
［００２６］
請求項９に記載の発明は、入力手段が、メッセージを入力する第１のステップと、パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、交替型連鎖手段が、ブロック暗号と該ブロック暗号の一部分から導出される置換処理とを、前記出力されたパディング済みメッセージを１ブロックずつ足しながら連鎖させて１ブロックのハッシュ値へ圧縮する第３のステップと、調整値付暗号化手段が、前記ハッシュ値を暗号化してタグとする第４のステップと、出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップとを有するメッセージ認証方法としたことを特徴とする。
［００２７］
請求項１０に記載の発明は、入力手段が、メッセージを入力する第１のステップと、パディング手段が、前記入力されたメッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力する第２のステップと、修正木連鎖ハッシュ手段が、前記出力されたパディング済みメッセージを、請求項２記載の交替型連鎖手段の一部の処理を請求項１記載の修正木ハッシュ手段で置き換えた構造により圧縮して１ブロック分のハッシュ値を出力する第３のステップと、調整値付暗号化手段が、前記ハッシュ値を暗号化してタグとする第４のステップと、出力手段が、前記暗号化されたタグと前記メッセージとを連結して出力する第５のステップとを有するメッセージ認証方法としたことを特徴とする。
［００２８］
請求項１１に記載の発明は、前記修正木ハッシュ手段が、ＡＥＳの段関数の４回以上の繰り返しを用いて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項８記載のメッセージ認証方法としたことを特徴とする。
【００２９】
請求項１２に記載の発明は、前記交替型連鎖手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項９記載のメッセージ認証方法としたことを特徴とする。
【００３０】
請求項１３に記載の発明は、前記修正木連鎖ハッシュ手段が、ＡＥＳとＡＥＳの段関数の４回以上の繰り返しとを組み合わせて構成され、前記調整値付暗号化手段が、ＡＥＳを用いて構成される請求項１０記載のメッセージ認証方法としたことを特徴とする。
【００３１】
請求項１４に記載の発明は、ブロック暗号と、該ブロック暗号の段関数を利用した置換処理とを用いる請求項８から１０のいずれか１項に記載のメッセージ認証方法としたことを特徴とする。
【００３２】
請求項１５に記載の発明は、請求項８から１０のいずれか１項に記載のメッセージ認証方法を、コンピュータに実行させるためのメッセージ認証プログラムとしたことを特徴とする。
【００３３】
請求項１６に記載の発明は、請求項１５記載のメッセージ認証プログラムを記録した記録媒体としたことを特徴とする。
【発明の効果】
【００３４】
本発明によれば、ブロック暗号とその一部の部品を組み合わせて、既存のブロック暗号の認証モードより高速で、理論的安全性を有し、事前処理や使用するメモリ量の点でも効率のよい、メッセージ認証装置、メッセージ認証方法、メッセージ認証プログラムとその記録媒体を実現することができる。
【発明を実施するための最良の形態】
【００３５】
本発明を実施するための最良の形態は、メッセージを入力する入力手段と、メッセージをパディングしてその長さを常にブロック長の定数にしてパディング済みメッセージとして出力するパディング手段と、パディング済みメッセージをブロック暗号の部品を基に作った小さい入出力幅のハッシュ関数をメッセージ分だけ並べた処理を繰り返すことで、１ブロックのハッシュ値を出力する修正木ハッシュ手段と、ハッシュ値を暗号化してタグとする調整値付暗号化手段と、タグとメッセージとを連結して出力する出力手段とを備えたメッセージ認証装置とする。
【００３６】
以下に、本発明の好適な実施形態を添付図面に基づいて詳細に説明する。尚、以下に述べる実施形態は本発明の好適な具体例であるから、技術的に好ましい種々の限定が付されているが、本発明の範囲は、以下の説明において特に本発明を限定する旨の記載がない限り、これらの実施形態に限られるものではない。
【００３７】
（実施形態１）
まず、本実施形態のメッセージ認証装置の構成及び各部の機能について添付図面を用いて以下に説明する。図２は、本実施形態のメッセージ認証装置の構成を示すブロック図である。図２に示すように、本実施形態のメッセージ認証装置１０は、入力手段１００、パディング手段１０１、修正木ハッシュ手段１０２、調整値付暗号化手段１０３、及び、出力手段１０４を備えている。なお、本実施形態のメッセージ認証装置１０は、コンピュータが一般的に備えている、ＣＰＵ（処理装置）、メモリ（主記憶装置）、及び、ディスク（補助記憶装置）等を用いることにより実現することが可能である。
【００３８】
図３は、一般的なコンピュータの構成を示したブロック図である。図３に示すように、一般的なコンピュータは、キーボード、マウス等の入力装置１、処理装置（ＣＰＵ）２、記憶装置３、ディスプレイやプリンタ等の出力装置４を備えている。処理装置（ＣＰＵ）２は、制御装置５、演算装置６を備えており、計算などの処理を行う中心となる部分である。記憶装置３は、主記憶装置７（メインメモリ）、補助記憶装置８を備えており、データを一時的又は／及び永久的に記憶する。
【００３９】
図２に示す本実施形態のメッセージ認証装置１０の備える各手段は、メッセージ認証に必要なプログラムをコンピュータのディスク（図３に示す補助記憶装置８）に格納しておき、このプログラムをＣＰＵ（図３に示す処理装置２）上で動作させることにより実現することができる。図２に示す入力手段１００は、タグを付与する対象となる平文（メッセージ）を入力する手段である。これは例えばキーボードなどの文字入力装置（図３に示す入力装置１）により実現される。
【００４０】
パディング手段１０１は、メッセージ長を常にブロックの倍数に変換する手段である。ブロック長は用いるブロック暗号の入力幅によって決まる。もし１ブロックがｎビットで、平文長をｎで割った余りが（ｎ−ｔ）の場合、最初が１で残りがすべて０のｔビットを平文に付加することで長さをブロックの倍数にする。既にブロックの倍数である平文については何も処理しない。
【００４１】
この方式に限らず、パディングの仕方は、メッセージ長がブロック長の倍数でない、異なる長さのメッセージ同士でパディングした結果が常に異なり、メッセージ長がブロック長の倍数であるメッセージについては何もしないという条件さえ守られるならばどのようなパディング方法でもよい。パディング手段１０１は、パディングされたメッセージと、パディング手段１０１においてパディングが行われたかどうか、すなわち元のメッセージ長がｎの倍数だったかどうかを示すインジケータをｄ（１ならばｎの倍数、２ならばそうでない）として出力する。
【００４２】
修正木ハッシュ手段１０２は、パディング手段１０１が出力するパディングされたメッセージを、ブロック暗号の部品を基に作った小さい入出力幅のハッシュ関数をメッセージ分だけ並べた処理を繰り返すことで１ブロックに圧縮する手段である。１ブロックをｎビットとし、ｎビットブロック暗号をＥとする。また、ｎビットの決定的置換をｆとする。
【００４３】
修正木ハッシュ手段１０２の処理は、以下に示す式（２）から成り立っている。この処理は２ｎビット入力、ｎビット出力の鍵付き関数である。鍵はブロック暗号Ｅの鍵である。
Ｘ＝（Ｘ1，Ｘ2）について、Ｄi（Ｘ）＝Ｘ2＋ｆ（Ｅ（ｉ）＋Ｘ1）・・・式（２）
但し、ｉ＝２^（ｎ）−１以下の非負整数、式（２）において加算はビット毎の排他的論理和を表す。
【００４４】
ここで、式（２）で示されるｎビット関数ｆの最大差分確率ＤＰ（ｆ）について説明する。ｎビット関数ｆの最大差分確率ＤＰ（ｆ）とは、ａは０以外のｎビット値、ｂは任意のｎビット値としたときのＰｒ（ｆ（Ｘ）−ｆ（Ｘ＋ａ）＝ｂ）の最小値を指す。ただし、確率はＸを一様にランダムなｎビット値としたもとで計算される。また、加算も減算も排他的論理和を表す。
【００４５】
式（２）で示されるｎビット関数ｆは、上記最大差分確率ＤＰ（ｆ）が十分小さい、つまり２^（−ｎ）に十分近いことが要求される。ｎビット置換の場合、最大差分確率は、理論的に２^（−ｎ＋１）まで小さくできることが知られているが、ｎが大きい場合に最大差分確率が十分小さい置換を作ることは現実には容易ではない。
【００４６】
しかし、決定的置換のかわりに鍵つきの置換（いくつかの置換の集合からランダムな鍵がひとつの置換を指定する。）を用いることも可能である。このときは、以下に説明する平均最大差分確率ＥＤＰ（ｆKp）が小さいことが求められる。
【００４７】
ｎビット鍵付き関数ｆKp（ただしＫPが鍵を表す。）の平均最大差分確率ＥＤＰ（ｆKp）とは、ａは０以外のｎビット値、ｂは任意のｎビット値としたときのＰｒ（ｆKp（Ｘ）−ｆKp（Ｘ＋ａ）＝ｂ）の最小値を指す。ただし、確率はＸを一様にランダムなｎビット値とし、さらに鍵をランダムとしたもとで計算される。また、加算も減算も排他的論理和を表す。
【００４８】
ブロック暗号を差分攻撃から守るときには、ブロック暗号の上記平均最大差分確率が小さいことが必要であるため、平均最大差分確率の小さい鍵付き置換はブロック暗号の部品となっていることが多い。例えばブロック暗号ＡＥＳの場合については４段の段関数が平均最大差分確率の小さい鍵付き置換となることが「S. Park, S. H. Sung, S. Lee, and J. Lim, Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structure and AES, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, Feb. 2003」に記載されている。
【００４９】
修正木ハッシュ手段１０２は、非特許文献３の修正木ハッシュを式（２）に示すＤiを用いて実行することが可能である。すなわち、式（１）に従い、ｍブロック入力Ｘ＝（Ｘ1，Ｘ2・・・Ｘm）について、ＭＴD(X)＝Ｇ［ＤS］（Ｇ［ＤS−１］（・・・Ｇ［Ｄ1］（Ｘ）・・・））（但し、ｓ＝ｌｏｇ（ｍ）（対数の底は２）以上の最小の整数）を求め、１ブロックのＭＴD(X)を出力する。このＭＴD(X)を修正木ハッシュ値と呼ぶ。
【００５０】
Ｅ（１）、Ｅ（２）、・・・、Ｅ（ｓ）は、ＭＴD(X)を求めるのに用いられ、ハッシュ鍵と呼ばれる。ＫPを鍵とした鍵付き置換ｆKpをｆの代わりとして用いる場合、式（２）において各Ｄ1、Ｄ2、・・・の鍵ＫPはそれぞれ同一であるか、もしくはそれぞれ異なる独立な値であるかのいずれでもよいが、ランダムに生成されている必要がある。鍵ＫPはブロック暗号Ｅの鍵と合わせてメッセージ認証装置の秘密鍵とするか、もしくは、ハッシュ鍵がＥ（１）、Ｅ（２）、・・・、Ｅ（ｓ）である場合に、Ｅ（ｓ＋１）、Ｅ（ｓ＋１）・・・を必要なだけ連結してＫPとしてもよい。
【００５１】
各Ｄ1、Ｄ2、・・・では、ハッシュ鍵Ｅ（１）、Ｅ（２）、・・・を必要とするが、これはあらかじめ生成しておいてもよい。非特許文献３においては、異なる長さのメッセージ間でのハッシュ値の衝突を防ぐために、修正木ハッシュ値に長さ情報を付加することが提案されているが、長さ情報を付加しなくとも、異なる長さの入力間での衝突確率は小さいため、非特許文献３に記載の修正木ハッシュを利用して、修正木ハッシュ手段１０２を実現する場合、長さ情報を付加しなくてよい。
【００５２】
また、修正木ハッシュを変形して用いることも可能である。例えば、式（１）を変形した、以下に示す式（３）を用いることができる。
ＭＴH(X)＝Ｇ［ＨS］（Ｇ［ＨS-1］（・・・Ｇ［Ｈ1］（Ｘ）・・・））・・・式（３）
入力が偶数ブロック数の場合：
Ｇ［Ｈ1］（Ｘ）＝Ｈi（Ｘ1，Ｘ2）‖Ｈi（Ｘ3，Ｘ4）‖・・・‖Ｈi（Ｘm-1，Ｘm）
入力が奇数ブロック数の場合：
Ｇ［Ｈ1］（Ｘ）＝Ｈi（Ｘ1，Ｘ2）‖Ｈi（Ｘ3，Ｘ4）‖・・・‖Ｈi（Ｘm-2，Ｘm-1）‖Ｈi（Ｘm，０００・・０）
但し、ｓ＝ｌｏｇ（ｍ）（対数の底は２）以上の最小の整数、０００・・０は全てゼロの系列
【００５３】
これは非特許文献３に記載されている、基本的な木ハッシュの構成である。ただし、この木ハッシュを用いる場合は、異なる長さのメッセージ間でのハッシュ値の衝突を防ぐため、もとのメッセージの長さ情報を最後に連結して、出力としなければならない。
【００５４】
調整値付暗号化手段１０３は、修正木ハッシュ手段１０２の出力である修正木ハッシュ値を暗号化する手段である。暗号化は、以下に示す式（４）にしたがって行われる。
ＴＢ［Ｅ］（ｘ，ｄ）＝Ｅ（（Ｌ＊ｕd）＋Ｙ）・・・式（４）
ｎビットのｕ1とｕ2を、互いに異なる、１か０でない任意の定数とする。
任意のｎビット値ａ，ｂについてａ＊ｂを有限体ＧＦ（２＾（ｎ））上の積とする。
ブロック暗号Ｅについて、Ｌ＝Ｅ（０）とする（但し、ｄ＝１もしくは２）。
【００５５】
調整値付暗号化手段１０３は、修正木ハッシュ手段１０２の出力をＹとすると、ＴＢ［Ｅ］（Ｙ，ｄ）を出力する。ここでｄは、パディング手段１０１が出力するパディングの有無、すなわちメッセージ長がｎの倍数だったかを示すインジケータである。ｄが１ならばメッセージ長がｎの倍数、２ならばそうでないとする。Ｌ＝Ｅ（０）、もしくはＬ＊ｕ1とＬ＊ｕ2は事前に計算してメモリに保持しておいてもよい。
【００５６】
インジケータｄにより暗号化の処理内容が変わることから、Ｌ＊ｕ1とＬ＊ｕ2のことを調整値と呼ぶ。有限体上の積＊は、ｕ1とｕ2が定数であるため、ビットシフトと条件付の定数との排他的論理和という、ごく簡単な演算で実行できる。例えば、ｕ1＝２、とｕ2＝４とした場合の計算が、「Tetsu Iwata, Kaoru Kurosawa, OMAC: One-Key CBC MAC、Fast Software Encryption, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, Feb. 2003」に記載されている。
【００５７】
出力手段１０４は、調整値付暗号化手段１０３が出力したされた暗号文をタグとし、入力手段１００に入力されたメッセージと連結してコンピュータディスプレイやプリンタなどへ出力する手段である。例として、ｍブロック入力でのメッセージ認証装置１０の動作例を図４示す。図４は、メッセージがちょうどｍブロック分の長さだったとし、入力手段１００、パディング手段１０１、及び、出力手段１０４は省略してある。図１おいて、Ｅはブロック暗号、ｆはある決定的置換もしくは鍵つき置換である。鍵がＫでメッセージがＸの時の暗号化をＥK(X)とすれば、ハッシュ鍵はＥK(1)，ＥK(2)，・・・，ＥK(d)に相当する。
【００５８】
次に、本実施形態のメッセージ認証装置１０の動作について図５を用いて以下に詳細に説明する。図５は、本実施形態のメッセージ認証装置１０の動作について説明するためのフローチャートである。図５に示すように、まず、修正木ハッシュ手段１０２と調整値付暗号化手段１０３が用いるハッシュ鍵と調整値をあらかじめ生成されているかを調べる（ステップ１０１）。もしすでに生成されているのであればステップ１０３へ進み、まだであればハッシュ鍵と調整値を生成する（ステップ１０２）。
【００５９】
次にメッセージを入力し（ステップ１０３）、パディングを実行する（ステップ１０４）。パディングされたメッセージに対して修正木ハッシュを実行し（ステップ１０５）、修正木ハッシュの出力に対して調整値付暗号化を適用してタグとする（ステップ１０６）。最後にタグとメッセージを連結し、出力する（ステップ１０７）。
【００６０】
（実施形態２）
まず、本実施形態のメッセージ認証装置の構成及び各部の機能について添付図面を用いて以下に説明する。図６は、本実施形態のメッセージ認証装置の構成を示すブロック図である。図６に示すように、本実施形態のメッセージ認証装置２０は、入力手段２００、パディング手段２０１、交替型連鎖手段２０２、調整値付暗号化手段２０３、及び、出力手段２０４を備えている。なお、本実施形態のメッセージ認証装置２０は、コンピュータが一般的に備えている、ＣＰＵ（処理装置）、メモリ（主記憶装置）、及び、ディスク（補助記憶装置）等を用いることにより実現することが可能である。
【００６１】
図３は、一般的なコンピュータの構成を示したブロック図である。図３に示すように、一般的なコンピュータは、キーボード、マウス等の入力装置１、処理装置（ＣＰＵ）２、記憶装置３、ディスプレイやプリンタ等の出力装置４を備えている。処理装置（ＣＰＵ）２は、制御装置５、演算装置６を備えており、計算などの処理を行う中心となる部分である。記憶装置３は、主記憶装置７（メインメモリ）、補助記憶装置８を備えており、データを一時的又は／及び永久的に記憶する。
【００６２】
図６に示す本実施形態のメッセージ認証装置２０の備える各手段は、メッセージ認証に必要なプログラムをコンピュータのディスク（図３に示す補助記憶装置８）に格納しておき、このプログラムをＣＰＵ（図３に示す処理装置２）上で動作させることにより実現することができる。図６に示す入力手段２００は、タグを付与する対象となる平文（メッセージ）を入力する手段である。これは例えばキーボードなどの文字入力装置（図３に示す入力装置１）により実現される。
【００６３】
パディング手段２０１は、メッセージ長を常にブロックの倍数に変換する手段である。ブロック長は用いるブロック暗号の入力幅によって決まる。もし１ブロックがｎビットで、平文長をｎで割った余りが（ｎ−ｔ）の場合、最初が１で残りがすべて０のｔビットを平文に付加することで長さをブロックの倍数にする。既にブロックの倍数である平文については何も処理しない。
【００６４】
この方式に限らず、パディングの仕方は、メッセージ長がブロック長の倍数でない、異なる長さのメッセージ同士でパディングした結果が常に異なり、メッセージ長がブロック長の倍数であるメッセージについては何もしないという条件さえ守られるならばどのようなパディング方法でもよい。パディング手段２０１は、パディングされたメッセージと、パディング手段２０１においてパディングが行われたかどうか、すなわち元のメッセージ長がｎの倍数だったかどうかを示すインジケータをｄ（１ならばｎの倍数、２ならばそうでない）として出力する。
【００６５】
交替型連鎖手段２０２は、ｎビットブロック暗号Ｅと、Ｅの一部分から導出されるｎビット置換ｆとを、メッセージを一ブロックずつ足しながら連鎖させてパディング手段２０１の出力を１ブロックへ圧縮する手段である。交替型連鎖手段２０２の処理は、以下に示す式（５）から成り立っている。ｔをある非負の整数として、この処理はｎ（ｔ＋３）ビット入力、ｎビット出力の鍵付き関数である。鍵はブロック暗号Ｅの鍵と補助鍵ＫＡｕｘ1，ＫＡｕｘ2，・・・，ＫＡｕｘtである。ｔが０であっても、つまり補助鍵がなしでもよい。
【００６６】
＜処理ＡＣＢＣ＞
ＡＣＢＣ（Ｘ）＝（Ｓt+1）＋Ｘt+3・・・式（５）
Ｘ＝（Ｘ1，Ｘ2，・・・，Ｘt+3）について、Ｓ1＝ｆ（Ｅ（Ｘ1）＋Ｘ2）
１＜ｉ＜ｔ＋２について、Ｓi＝ｆ（（Ｓi-1）＋（ＫＡｕｘi-1）＋Ｘi+1）
【００６７】
交替型連鎖手段２０２は、上記式（５）に記載の処理ＡＣＢＣを連鎖する。すなわち最初の（ｔ＋３）入力ブロックをＸとすると、ＸへＡＣＢＣを適用し式（５）に従いＡＣＢＣ（Ｘ）を求め、ＡＣＢＣ（Ｘ）と次の（ｔ＋２）入力ブロックとを連結して、再度ＡＣＢＣへ入力する。この処理を繰り返し、最後の入力ブロックを足した時点でただちに停止し、その結果を出力する。最後の入力ブロックに対応する補助鍵は足してもよいし、足さなくてもよい。
【００６８】
補助鍵はブロック暗号の鍵と独立な鍵でもよいが、後述の調整値付暗号化手段２０３を用いた処理にしたがって生成してもよい。実施形態１における修正木ハッシュ手段１０２の場合と同様、式（５）のＡＣＢＣで用いるｆが、最大差分確率の小さい置換であることが必要である。さらに、以下に説明するｎビット関数ｆの最大自己差分確率ＳＤＰ（ｆ）が小さいことも必要となる。
【００６９】
ｎビット関数ｆの最大自己差分確率ＳＤＰ（ｆ）とは、ａは任意のｎビット値としたときのＰｒ（Ｘ−ｆ（Ｘ）＝ａ）の最小値を指す。但し、確率は、Ｘを一様にランダムなｎビット値としたもとで計算される。また、加算も減算も排他的論理和を表す。
【００７０】
また、実施形態１における修正木ハッシュ手段１０２の場合と同様に、ＡＣＢＣにおいて、Ｋを鍵とする鍵付きの置換ｆKpをｆの代わりに使うことが可能である。この場合、Ｋｐは一度設定した後はずっと変更しないか、もしくはｔ＋１個、つまり補助鍵の数＋１個、の独立でランダムな値を用意し、メッセージブロックを処理するたびに周期的に変更させてもよい。但し、鍵付きの置換ｆKpを用いる場合、ｆKpの平均最大差分確率と、以下に説明する平均最大自己差分確率ＥＳＤＰ（ｆKp）の両方が小さいことが必要となる。
【００７１】
ｎビット鍵付き関数ｆKp（但し、Ｋpが鍵を表す。）の平均最大自己差分確率ＥＳＤＰ（ｆKp）とは、ａは任意のｎビット値としたときのＰｒ（Ｘ−ｆKp（Ｘ）＝ａ）の最小値を指す。但し、確率は、Ｘを一様にランダムなｎビット値とし、さらに鍵Ｋｐをランダムとしたもとで計算される。また、加算も減算も排他的論理和を表す。
【００７２】
ブロック暗号の段関数において、鍵を中間変数へ排他的論理和することは一般的である。このような構造の場合、段関数の平均最大自己差分確率は最小となることが容易に示せる。例えば、ＡＥＳの段関数では、何段であれ平均最大自己差分確率が最小値２＾（−１２８）となる。交替型連鎖手段２０２の出力を交替型連鎖ハッシュ値と呼ぶことにする。
【００７３】
調整値付暗号化手段２０３は、以下に示す処理Ａにしたがい、交替型連鎖ハッシュ値を暗号化する。
＜処理Ａ＞
ｎビットのｕ1とｕ2を、互いに異なる、１か０でない任意の定数とする。任意のｎビット値ａ，ｂについてａ＊ｂを有限体ＧＦ（２＾（ｎ））上の積とする。ブロック暗号Ｅについて、Ｌをブロック暗号の鍵と独立でランダムなｎビット値とする。Ｌはブロック暗号の鍵と合わせてメッセージ認証装置の鍵となる。ｄが０，１，２のどれかをとるとし、ＴＴＢ［Ｅ，Ｌ］（Ｙ，ｄ）を、ｄ＝０ならＥ（Ｌ＋Ｙ）と、ｄ＝１ならＥ（（Ｌ＊ｕ1）＋Ｙ）と、ｄ＝２ならＥ（（Ｌ＊ｕ2）＋Ｙ）と、する。
【００７４】
調整値付暗号化手段２０３は、パディング手段２０１が出力するパディングの有無のインジケータをｄとして、交替型連鎖手段２０２の出力をＴＴＢ［Ｅ，Ｌ］に基づき暗号化する。交替型連鎖手段２０２の出力をＹとすれば、調整値付暗号化手段２０２の出力は、ｄが１ならＥ（（Ｌ＊ｕ1）＋Ｙ）、ｄが２ならＥ（（Ｌ＊ｕ2）＋Ｙ）である。Ｌ＊ｕ1とＬ＊ｕ2のことを調整値と呼ぶ。実施形態１における調整値付暗号化手段１０３同様、ｕ1とｕ2の値をそれぞれ２と４とした場合の計算方法は、「Tetsu Iwata, Kaoru Kurosawa, OMAC: One-Key CBC MAC、Fast Software Encryption, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, Feb. 2003」に記載されている。
【００７５】
交替型連鎖手段２０２における補助鍵がｔ個ある場合、Ｅ（Ｌ＋０），Ｅ（Ｌ＋１），・・・，Ｅ（Ｌ＋ｔ−１）を補助鍵ＫＡｕｘ1，・・・，ＫＡｕｘtとしてもよい。また、上記処理Ａにおけるｄの値による場合分けの処理は、任意に入れ替えてもよい。例えば、パディングの有無のインジケータがｄで交替型連鎖手段２０２の出力がＹのとき、ｄ＝１でＥ（Ｌ＋Ｙ）を、ｄ＝２でＥ（Ｌ＊ｕ1＋Ｙ）を出力とし、補助鍵がｔ個ある場合、Ｅ（（Ｌ＊ｕ2）＋０），Ｅ（（Ｌ＊ｕ2）＋１），・・・，Ｅ（（Ｌ＊ｕ2）＋ｔ−１）を補助鍵としてもよい。
【００７６】
出力手段２０４は、実施形態１におけるメッセージ認証装置１０の出力手段１０４と同様である。例として、ある長さのメッセージに対するメッセージ認証装置２０の動作例を図７に示す。メッセージ長がちょうどブロック長の整数倍だったとし、入力手段２００、パディング手段２０１、及び、出力手段２０４は省略してある。補助鍵がない場合と１個の場合を例として記載している。図７においてＥはブロック暗号、ｆはある決定的置換もしくは鍵つき置換を示す。
【００７７】
次に、本実施形態のメッセージ認証装置２０の動作について図８を用いて以下に詳細に説明する。図８は、本実施形態のメッセージ認証装置２０の動作について説明するためのフローチャートである。図８に示すように、まず、交替型連鎖手段２０２と調整値付暗号化手段２０３が用いる補助鍵と調整値をあらかじめ生成されているかを調べる（ステップ２０１）。もしすでに生成されているのであればステップ２０３へ進み、まだであれば補助鍵と調整値を生成する（ステップ２０２）。
【００７８】
次にメッセージを入力し（ステップ２０３）、パディングを実行する（ステップ２０４）。パディングされたメッセージに対して交替型連鎖手段２０２を実行し（ステップ２０５）、交替型連鎖手段２０２の出力交替型連鎖ハッシュ値に対して調整値付暗号化を適用してタグとする（ステップ２０６）。最後にタグとメッセージを連結し、出力する（ステップ２０７）。
【００７９】
（実施形態３）
まず、本実施形態のメッセージ認証装置の構成及び各部の機能について添付図面を用いて以下に説明する。図９は、本実施形態のメッセージ認証装置の構成を示すブロック図である。図９に示すように、本実施形態のメッセージ認証装置３０は、入力手段３００、パディング手段３０１、修正木連鎖ハッシュ手段３０２、調整値付暗号化手段３０３、及び、出力手段３０４を備えている。なお、本実施形態のメッセージ認証装置３０は、コンピュータが一般的に備えている、ＣＰＵ（処理装置）、メモリ（主記憶装置）、及び、ディスク（補助記憶装置）等を用いることにより実現することが可能である。
【００８０】
図３は、一般的なコンピュータの構成を示したブロック図である。図３に示すように、一般的なコンピュータは、キーボード、マウス等の入力装置１、処理装置（ＣＰＵ）２、記憶装置３、ディスプレイやプリンタ等の出力装置４を備えている。処理装置（ＣＰＵ）２は、制御装置５、演算装置６を備えており、計算などの処理を行う中心となる部分である。記憶装置３は、主記憶装置７（メインメモリ）、補助記憶装置８を備えており、データを一時的又は／及び永久的に記憶する。
【００８１】
図９に示す本実施形態のメッセージ認証装置３０の備える各手段は、メッセージ認証に必要なプログラムをコンピュータのディスク（図３に示す補助記憶装置８）に格納しておき、このプログラムをＣＰＵ（図３に示す処理装置２）上で動作させることにより実現することができる。図９に示す入力手段３００及びパディング手段３０１は、実施形態１のメッセージ認証装置１０の各手段と同様である。調整値付暗号化手段３０３は、実施形態２のメッセージ認証装置２０の調整値付暗号化手段２０３と同様である。
【００８２】
修正木連鎖ハッシュ手段３０２の処理は、実施形態１の交替型連鎖手段１０２における一部の処理を、実施形態２の修正木ハッシュ手段２０２で置き換えたものである。まず１以上の整数ｔを定める。ｔ個のハッシュ鍵（Ｒ1，Ｒ2，．．．，Ｒt）を用いるものとする。この場合、パディング手段３０１の出力に対し、最初の１ブロック目をブロック暗号Ｅで暗号化しＹ0を得る。次の２＾（ｔ＋１）ブロック分の入力を、（Ｒ1，Ｒ2，．．．，Ｒt，Ｙ0）をハッシュ鍵とした修正木ハッシュを適用する。但し、Ｙ0は、最後の２ブロックを１ブロックへ圧縮する処理に用いられるものとする。
【００８３】
この修正木ハッシュの出力をブロック暗号で暗号化し、Ｙ1を得る。次の２＾（ｔ＋１）ブロック分の入力を、今度は（Ｒ1，Ｒ2，．．．，Ｒt，Ｙ1）をハッシュ鍵とした修正木ハッシュで圧縮する。この処理を繰り返す。最後の修正木ハッシュの出力が修正木連鎖ハッシュ手段３０２の出力となる。但し、最後の修正木ハッシュへの入力が２＾（ｔ＋１）ブロックより短い場合は、その出力は以下に従う。上記の処理をｓ回繰り返したとして、ハッシュ鍵を（Ｒ1，Ｒ2，．．．，Ｒt，ＹS）とする。
【００８４】
最後の修正木ハッシュへの入力が１ブロックのみのｘである場合、（ＹS）＋ｘを出力する。２ブロック以上の入力の場合、修正木ハッシュにおいて常に最後の２ブロックを１ブロックへ圧縮する処理でＹSを用いるものとする。つまり修正木ハッシュが式（１）の処理を繰り返して入力を短くしていき、２ブロック（ｚ1，ｚ2）を得たとき、ｆ（ｚ1＋ＹS）＋Ｚ2が出力となる。
【００８５】
修正木ハッシュをある決定的置換ｆで実現する場合、ｆは最大差分確率と最大自己差分確率が小さいことが求められる。また、Ｋｐを鍵としたもし鍵付きの置換ｆKpで実現する場合には、ｆKpは平均最大差分確率と平均最大自己差分確率が小さいことが求められる。ｔ個のハッシュ鍵（Ｒ1，Ｒ2，．．．，Ｒt）はブロック暗号Ｅの鍵と独立でもよいし、実施形態２における補助鍵と同様にＥ（Ｌ＋０），Ｅ（Ｌ＋１），．．．，Ｅ（Ｌ＋ｔ−１）をそれぞれＲ1，．．．，Ｒtとしてもよい。修正木連鎖ハッシュ手段３０２の出力を修正木連鎖ハッシュ値と呼ぶことにする。
【００８６】
調整値付暗号化手段３０３は、実施形態２の調整値付暗号化手段２０３と同様である。出力手段３０４は、実施形態１の出力手段１０４と同様である。例として、ある長さのメッセージに対するメッセージ認証装置３０の動作例を図１０に示す。メッセージ長がちょうどブロック長の整数倍だったとし、入力手段３００、パディング手段３０１、及び、出力手段３０４は省略してある。図１０においてＥ，ｆ，ｇR1，．．．ｇRtは、図４及び図７と同様である。
【００８７】
次に、本実施形態のメッセージ認証装置３０の動作について図１１を用いて以下に詳細に説明する。図１１は、本実施形態のメッセージ認証装置３０の動作について説明するためのフローチャートである。図１１に示すように、まず、修正木連鎖ハッシュ手段３０２と調整値付暗号化手段３０３が用いるハッシュ鍵と調整値をあらかじめ生成されているかを調べる（ステップ３０１）。もしすでに生成されているのであればステップ３０１へ進み、まだであればハッシュ鍵と調整値を生成する（ステップ３０２）。
【００８８】
次にメッセージを入力し（ステップ３０３）、パディングを実行する（ステップ３０４）。パディングされたメッセージに対して修正木連鎖ハッシュ手段３０２を実行し（ステップ３０５）、修正木連鎖ハッシュ手段３０２の出力に対して調整値付暗号化を適用してタグとする（ステップ３０６）。最後にタグとメッセージを連結し、出力する（ステップ３０７）。
【００８９】
本発明によれば、第１の効果は、ＣＢＣ−ＭＡＣなどのブロック暗号の認証モードよりも高速処理なことである。その理由は、ブロック暗号の段関数など、一部分の処理を取り出してメッセージの処理に用いるからである。わずかな事前処理の時間を除けば、任意のメッセージ長においてＣＢＣ−ＭＡＣの処理量よりも少ない処理量で実行可能である。メッセージが１ブロックのときはＣＢＣ−ＭＡＣとほぼ同等となるが、これは明らかに必要不可欠な処理である。
【００９０】
例として「J. Daemen and V. Rijmen, AES Proposal: Rijndael, AES submission, 1998.」に記載のブロック暗号ＡＥＳと、ＡＥＳの段関数の４回の繰り返し（４段ＡＥＳ）とを用いた場合、ＡＥＳのＣＢＣ−ＭＡＣよりも約１．３から約２．５倍高速となる。高速化の度合いは実施の形態によって異なり、どの実施の形態が望ましいかは使用可能な動的メモリの量や、許容される事前処理の時間などで決まる。
【００９１】
本発明によれば、第２の効果は、ＣＢＣ−ＭＡＣなどのブロック暗号の認証モードとほぼ同等のプログラムサイズとなることである。その理由は、ブロック暗号とその一部分のみを用いるためである。その他に必要な演算は排他的論理和などの極めて単純な関数のみである。
【００９２】
本発明によれば、第３の効果は、本発明を既知のブロック暗号に適用したとき、ＣＢＣ−ＭＡＣなどのブロック暗号の認証モードと同等の理論的安全性を有するように構成できることである。その理由は、本発明で用いるブロック暗号の一部分が差分攻撃に理論的安全性を持つ、すなわち平均最大差分確率が十分小さい場合には、本発明は非特許文献１に記載の理論的安全性の意味で安全な認証方式となるからである。
【００９３】
ここで、ブロック暗号の段関数の数回の繰り返しが小さい平均最大差分確率を持つことは、十分な安全性を持つブロック暗号の必須条件と言えるため、近年提案されたブロック暗号の多くがこの性質を持つように設計されていることに注意されたい。例えばＡＥＳでは、４段ＡＥＳが十分小さい平均最大差分確率を持つことが「S. Park, S. H. Sung, S. Lee, and J. Lim, Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structure and AES, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, Feb. 2003」に記載されている。
【００９４】
本発明の実施の形態によっては、使用するブロック暗号の一部分に、平均最大差分確率だけでなく、平均最大自己差分確率と呼ばれる値が十分小さいことも要求されるが、これは弱い追加条件である。実際、ＡＥＳを含めた多くのブロック暗号で、段関数が繰り返し回数に関わらず理論的に最小の平均最大自己差分確率をとることが示せる。
【００９５】
本発明は、無線もしくは有線のデータ通信における改ざんを防ぐといった用途や、ストレージ上のデータの改ざん防止といった用途に適用することができる。
【図面の簡単な説明】
【００９６】
【図１】ＯＭＡＣを示したブロック図である。
【図２】第１の実施形態におけるメッセージ認証装置の構成を示すブロック図である。
【図３】一般的なコンピュータの構成を示したブロック図である。
【図４】第１の実施形態のメッセージ認証装置における、ｍブロック入力での動作例を示した図である。
【図５】第１の実施形態のメッセージ認証装置の動作について説明するためのフローチャートである。
【図６】第２の実施形態におけるメッセージ認証装置の構成を示すブロック図である。
【図７】第２の実施形態のメッセージ認証装置における、ある長さのメッセージに対する動作例を示した図である。
【図８】第２の実施形態のメッセージ認証装置の動作について説明するためのフローチャートである。
【図９】第３の実施形態におけるメッセージ認証装置の構成を示すブロック図である。
【図１０】第３の実施形態のメッセージ認証装置における、ある長さのメッセージに対する動作例を示した図である。
【図１１】第３の実施形態のメッセージ認証装置の動作について説明するためのフローチャートである。
【符号の説明】
【００９７】
１    入力装置
２    処理装置（ＣＰＵ）
３    記憶装置
４    出力装置
５    制御装置
６    演算装置
７    主記憶装置
８    補助記憶装置
１０、２０、３０    メッセージ認証装置
１００、２００、３００    入力手段
１０１、２０１、３０１    パディング手段
１０２    修正木ハッシュ手段
１０３、２０３、３０３    調整値付暗号化手段
１０４、２０４、３０４    出力手段
２０２    交替型連鎖手段
３０２    修正木連鎖ハッシュ手段
【図１】
0004735644.tif 000002
【図２】
0004735644.tif 000003
【図３】
0004735644.tif 000004
【図４】
0004735644.tif 000005
【図５】
0004735644.tif 000006
【図６】
0004735644.tif 000007
【図７】
0004735644.tif 000008
【図８】
0004735644.tif 000009
【図９】
0004735644.tif 000010
【図１０】
0004735644.tif 000011
【図１１】
0004735644.tif 000012