認証のためにメッセージを処理する方法
【課題】安全性の証明をも提供しながら、長短両方のメッセージがＨＭＡＣより効率的にメッセージ認証されることを可能にする。
【解決手段】メッセージ認証コード（ＭＡＣ）を生成するメッセージ認証システムは、メッセージが鍵つき圧縮関数の１入力ブロック内に収まるときにその圧縮関数の１回のみの実行を使用する。１ブロックより大きいメッセージに対しては、このＭＡＣシステムは、ネスト化ハッシュ関数を使用する。本発明のもう１つの特徴によれば、ＭＡＣシステムは、ネスト化ハッシュ関数への入力として、メッセージの一部を使用する。例えば、メッセージ認証システムは、メッセージを第１部分と第２部分に分割することができる。ハッシュ関数がメッセージの第１部分を入力として実行されて中間結果を得、鍵つきハッシュ関数がメッセージの第２部分および中間結果を入力として使用して実行される。
【解決手段】メッセージ認証コード（ＭＡＣ）を生成するメッセージ認証システムは、メッセージが鍵つき圧縮関数の１入力ブロック内に収まるときにその圧縮関数の１回のみの実行を使用する。１ブロックより大きいメッセージに対しては、このＭＡＣシステムは、ネスト化ハッシュ関数を使用する。本発明のもう１つの特徴によれば、ＭＡＣシステムは、ネスト化ハッシュ関数への入力として、メッセージの一部を使用する。例えば、メッセージ認証システムは、メッセージを第１部分と第２部分に分割することができる。ハッシュ関数がメッセージの第１部分を入力として実行されて中間結果を得、鍵つきハッシュ関数がメッセージの第２部分および中間結果を入力として使用して実行される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信に関し、特に、メッセージの認証に関する。
【背景技術】
【０００２】
図１は、地理的領域１４および１６のそれぞれの内部に位置するワイヤレス（無線）装置（例えば、ワイヤレス装置１２ａ〜ｃ）にワイヤレス通信サービスを提供する第１および第２のワイヤレス通信システムの概略図である。移動通信交換局（ＭＳＣ）（例えば、ＭＳＣ２０および２４）は、とりわけ、ワイヤレス装置間の呼、ワイヤレス装置とワイヤライン（有線）装置（例えば、ワイヤライン装置２５）との間の呼、あるいは、ワイヤレス装置とインターネットのようなパケットデータネットワーク（ＰＤＮ：packet data network）との間のコネクションを確立し維持する責任を負う。このため、ＭＳＣは、その地理的領域内のワイヤレス装置を公衆交換電話網（ＰＳＴＮ）２８あるいはパケットデータネットワーク（ＰＤＮ）２９と相互接続する。ＭＳＣによってサービスされる地理的エリアは、「セル」と呼ばれる空間的に相異なるエリアに分割される。図１に示されているように、各セルは、模式的には、蜂の巣パターンの１つの六角形によって表される。しかし、実際には、各セルは、そのセルの周囲の地形に依存する不規則な形状を有する。
【０００３】
一般に、各セルは基地局（例えば、基地局２２ａ〜ｅおよび２６ａ〜ｅ）を有する。基地局は、そのセル内のワイヤレス装置と通信するために使用する無線機およびアンテナを有する。基地局はまた、その地理的エリア内のＭＳＣと通信するために使用する伝送装置も有する。例えば、ＭＳＣ２０は、地理的エリア１４内の基地局２２ａ〜ｅに接続され、ＭＳＣ２４は、地理的エリア１６内の基地局２６ａ〜ｅに接続される。１つの地理的領域内で、ＭＳＣは、ワイヤレス装置がセル間を移動していくのとともにリアルタイムで基地局間で呼を交換する。これを呼ハンドオフという。具体的実現化に依存して、基地局コントローラ（ＢＳＣ）は、いくつかの基地局に接続された別個の基地局コントローラ（ＢＳＣ）（図示せず）であることも可能であり、あるいは、各基地局に配置され、基地局のワイヤレス資源を管理し情報をＭＳＣに中継することも可能である。
【０００４】
ＭＳＣ２０および２４は、シグナリングネットワーク（信号網）３２を使用する。シグナリングネットワーク３２は、例えば、ＴＩＡ／ＥＩＡ−４１−Ｄとして指定された、"Cellular Radiotelecommunications Intersystem Operations", December 1997（ＩＳ−４１）という名称の標準に準拠するシグナリングネットワークである。これは、それぞれの地理的エリア１４および１６内をローミングしているワイヤレス装置に関する情報の交換を可能にする。例えば、ワイヤレス装置１２ａは、もともと割り当てられたＭＳＣ２０（ホームＭＳＣ）の地理的エリア１４を離れるとき、ローミングしている。ローミングワイヤレス装置が呼を受け取ることができることを保証するため、ローミングワイヤレス装置１２ａは、現在位置のＭＳＣ２４（在圏ＭＳＣ）にその存在を通知することによって、在圏ＭＳＣ２４に登録する。ローミングワイヤレス装置１２ａが在圏ＭＳＣ２４によって識別されると、在圏ＭＳＣ２４は、シグナリングネットワーク３２を通じて、ホームＭＳＣ２０に登録要求を送り、ホームＭＳＣ２０は、在圏ＭＳＣ２４の識別によってデータベース３４（ホームロケーションレジスタ（ＨＬＲ）という）を更新することにより、ローミングワイヤレス装置１２ａの位置をホームＭＳＣ２０に提供する。ローミングワイヤレス装置が認証された後、ホームＭＳＣ２０は、在圏ＭＳＣ２４に顧客プロファイルを提供する。在圏ＭＳＣ２４は、顧客プロファイルを受け取った後、ホームＭＳＣ２０と同じ機能を提供するために、データベース３６（在圏ロケーションレジスタ（ＶＬＲ）という）を更新する。ＨＬＲ、ＶＬＲおよび認証局（ＡＣ：authentication center）は、ＭＳＣとコロケートされることも可能であり、リモートアクセスされることも可能である。
【０００５】
ＵＭＴＳ(Universal Mobile Telecommunications System)および３Ｇ ＩＳ−４１では、ワイヤレス装置は、呼を発信し、または、受信するとき、認証されなければ、呼設定に進むことができない。認証された後、ある秘密鍵を用いて生成された１２８ビットの完全性鍵（ＩＫ：integrity key）が有効化され、ワイヤレス装置とシステムの間で送信されるメッセージの完全性(integrity)のチェックすなわちメッセージ認証に使用されることが可能となる。
【０００６】
よいメッセージ認証方式の設計は、暗号技術の重要な分野の１つである。メッセージ認証方式の目標は、受信側が受信するメッセージに改竄があったかどうかを受信側が判断することができるように、送信側が受信側へメッセージを効率的に送信することである。図２に、ワイヤレス通信システムにおいてワイヤレス装置でどのようにメッセージ認証が実行されるかを示す。この環境には、ワイヤレス装置およびワイヤレス通信システムという二当事者が関与し、これらは秘密鍵ｋに関して合意している。使用されるアルゴリズムとして、署名アルゴリズムＳｋおよび検証アルゴリズムＶｋの２つがある。ワイヤレス装置がメッセージＭをワイヤレス通信システムへ送信したい場合、ワイヤレス装置は、まず、ＭＡＣジェネレータ５０を用いて、タグすなわちメッセージ認証コード（ＭＡＣ）μ＝Ｓｋ（Ｍ）を計算する。ワイヤレス装置は、メッセージとタグのペア（Ｍ，μ）をワイヤレス通信システムへ送信する。ワイヤレス通信システムは、ペア（Ｍ，μ）を受信すると、Ｖｋ（Ｍ，μ）を計算し、ＭＡＣが正当な場合には１を返し、そうでない場合には０を返す。図２には、ワイヤレス通信システムがメッセージおよびｋをＭＡＣジェネレータ５２に入力し、ＭＡＣジェネレータ５２がタグ’を出力し、ワイヤレス装置から受信されたタグ（μ）とシステムで生成されたタグ’の間の比較５４が行われることが示されている。これらが同一である場合、メッセージは正当であるとして受容され、そうでない場合、メッセージは拒否される。秘密鍵ｋを知らなければ、検証アルゴリズムが正当であるとして受容することになるメッセージおよび対応するＭＡＣを、敵が構成することはほとんど不可能である。
【０００７】
同じメッセージ認証方式が、ワイヤレス通信システムからワイヤレス装置へのメッセージの送信において実行される。例えば、図３に、ワイヤレス通信システムが、保護されたメッセージをどのようにしてワイヤレス装置へ送信するかを示す。まず、ワイヤレス通信システムは、メッセージおよび秘密鍵ｋを入力としてＭＡＣジェネレータ５６でタグを生成する。ワイヤレス通信システムは、メッセージをタグとともにワイヤレス装置へ送信する。ワイヤレス装置は、メッセージおよび秘密鍵ｋをＭＡＣジェネレータ５８に入力してタグ’を生成する。ワイヤレス装置は、タグ’と、ワイヤレス通信システムから受信されたタグとの間の比較６０を行う。これらのタグが一致した場合、メッセージは正当であるとして受容される。一致しない場合、メッセージは、変更された、あるいは、不正であるとして、拒否される。
【０００８】
メッセージ認証コードに対するセキュリティ要件は次のように説明することができる。ｋは秘密のまま、選択されたメッセージに対するＭＡＣ Ｓｋ，Ｖｋを問い合わせることができるときに、Ｖｋ（Ｍ＊，μ＊）＝１であるがメッセージＭ＊はＳｋへの入力となったことがないような正当なペア（Ｍ＊，μ＊）を敵が思いつくことができる場合、敵がＭＡＣを偽造している。
【０００９】
実際に広くみられるメッセージ認証への１つの一般的なアプローチは、暗号ハッシュ関数を用いるものである。ハッシュ関数は、一般に、ある長さの入力から、より短い長さの出力に写像する関数として特徴づけることができる。さらに、同じ出力に写像される２つの入力を見つけるのは困難である。暗号ハッシュ関数に基づくこれらのＭＡＣ方式が良好であるのは、高速で安全な暗号構成ブロックを使用するからである。一般に、暗号ハッシュ関数Ｆ（ｘ）は、任意の長さの入力ｘを短い出力に写像する、公開され、鍵なし（キーレス、すなわち、鍵がかけられていない）、衝突を起こしにくい（衝突耐性がある、耐衝突性）関数である。衝突を起こしにくいとは、Ｆ（ｘ１）＝Ｆ（ｘ２）であるような２つのメッセージｘ１およびｘ２を見つけるのが計算量的に実行不能であることを意味する。ＭＤ５、ＳＨＡ−１、およびＲＩＰＥ−ＭＤは、広く用いられている暗号ハッシュ関数である。耐衝突性とともに、ハッシュ関数は通常、他の目的で使用するため、および、耐衝突性の可能性を高めるために、他の性質も有するように設計される。
【００１０】
ＭＤ５やＳＨＡ−１のようなほとんどの暗号ハッシュ関数は、入力メッセージがブロックごとに処理されるという反復構成を使用する。図４に示すように、基本構成ブロックは、圧縮関数ｆと呼ばれ、これは、サイズｔおよびｂの２つの入力をとり、長さｔの、より短い出力に写像するハッシュ関数である。ＭＤ５では、サイズｔの入力は長さ１２８ビットであり、サイズｂの入力は長さ５１２ビットである。ＳＨＡ−１では、サイズｔの入力は長さ１６０ビットであり、サイズｂの入力は長さ５１２ビットである。サイズｔの入力は連鎖変数と呼ばれ、サイズｂの入力（ペイロードあるいはブロック）は、実際にメッセージｘを一度にｂビットずつ処理するために使用される。図５に示すように、この場合、ハッシュ関数Ｆ（ｘ）は、ｈｉを連鎖変数とし、ｘｉをペイロードとして、以下のステップに従って、メッセージｍに対して圧縮関数ｆを反復して作用させることによって形成される。
１．適当な手続きを用いてメッセージ長を付加し、パディングして、入力をブロックサイズｂの倍数にする。入力は、ブロックサイズの断片ｘ＝ｘ１，...，ｘｎに分解することができる。
２．ｈ０＝ＩＶ（一定）
３．Ｆｏｒ ｉ＝１ ｔｏ ｎ
４．ｈｉ＝ｆ（ｈｉ−１，ｘｉ）
５．ｈｎをＦ（ｘ）として出力する。
例えば、ＳＨＡ−１ハッシュ関数を使用する場合、ＳＨＡ−１ハッシュ関数のそれぞれへの呼出しは、１６０ビットの初期ベクトル（ＩＶ：initial vector）を有し、５１２ビットの入力（ペイロード）をとり、これが１６０ビットの出力に写像される。ＩＶは、ＳＨＡ−１ハッシュ関数に対する標準（National Institute of Standards and Technology, NIST FIPS PUB 180, "Secure Hash Standard", U. S. Department of Commerce, May 1993）で規定されたＩＶとなるように設定される。
【００１１】
暗号ハッシュ関数は、設計上、鍵なし（キーレス）である。しかし、メッセージ認証は秘密鍵の使用を必要とするため、ハッシュ関数に鍵をかける方法が必要となる。ハッシュ関数に鍵をかける１つの方法は、固定された既知のＩＶの代わりに秘密鍵を使用することである。図６に示すように、鍵ｋで、圧縮関数ｆ（連鎖変数，ｘ１）における連鎖変数を置き換えて、ｆｋ（ｘ１）＝ｆ（ｋ，ｘ１）をつくる。ただし、ｘ１のブロックサイズはｂである。反復されたハッシュ関数Ｆ（ＩＶ，ｘ）は、固定のＩＶを秘密鍵ｋで置き換えてＦｋ（ｘ）＝Ｆ（ｋ，ｘ）を形成することによって修正される。鍵がかけられた（鍵つき）関数の耐衝突性は、鍵なし関数のものとは異なる、その理由は、敵は、任意の時点に、ユーザに問い合わせることなくＦｋ（ｘ）を評価することはできないからである。この要件は、標準的な衝突要件より弱いため、関数Ｆｋ（ｘ）を「弱耐衝突性」であると呼ぶことにする。
【００１２】
鍵つき暗号ハッシュ関数の安全性を改善するため、次のように定義されるネスト化ＭＡＣ関数（ＮＭＡＣ）が開発された。
ＮＭＡＣｋ（ｘ）＝Ｆｋ１（Ｆｋ２（ｘ））
ただし、暗号ハッシュ関数Ｆは、まず、ＩＶの代わりに秘密鍵ｋ２で鍵がかけられ、メッセージｘが反復的にハッシュされてＦｋ２（ｘ）の出力となる。次に、図７に示すように、この出力Ｆｋ２（ｘ）が、Ｆのパディング方式に従って、あるブロックサイズにパディングされた後、Ｆｋ２（ｘ）の結果は秘密鍵ｋ１で鍵がかけられ、外側ハッシュ関数Ｆでハッシュされる。このように、ＮＭＡＣ鍵ｋは２つの部分ｋ＝（ｋ１，ｋ２）を有する。ＮＭＡＣの安全性を、基礎となる暗号ハッシュ関数の安全性と関連づけることに関する次の定理が、M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for Message Authentication", In Proc. CRYPTO 96, Lecture Notes in Computer Science, Springer-Verlag, 1996、に証明されている。
【００１３】
定理１： ｔ回のステップおよびｑ回の問合せで、鍵つき圧縮関数ｆがεｆ安全なＭＡＣであり、かつ、鍵つき反復ハッシュＦがεＦ弱耐衝突性であるならば、ＮＭＡＣ関数は（εｆ＋εＦ）安全なＭＡＣである。
【００１４】
このＮＭＡＣの構成は、圧縮関数への少なくとも２回の呼出しを行う。Ｆｋ２（ｘ）への内側の呼出しは、鍵なしハッシュ関数Ｆ（ｘ）と同じコストを有する。このため、Ｆｋ１への外側の呼出しは、鍵なしハッシュ関数によって要求されるものを超える追加の呼出しである。外側の関数呼出しは、基本的に、鍵つき圧縮関数ｆｋ１への呼出しである。その理由は、Ｆｋ２（ｘ）のサイズ１の出力は、圧縮関数へのサイズｂの入力にはめ込むことができるからである。多くのブロックからなる大きいｘに対しては、追加の外側圧縮呼出しのコストは重要ではない。しかし、サイズの小さいメッセージｘの場合、追加の外側圧縮関数は、鍵なしハッシュ関数に比べたとき、割合でみると、相当高い程度の非効率性を生じる。表１に、ＳＨＡ−１ハッシュ関数の場合に、小さいｘに対する非効率性を示す。基礎となるハッシュ関数によって、および、ＮＭＡＣによって必要とされる圧縮呼出しの回数が、３０バイトずつ増大するさまざまな小さいｘに対して比較されている。基礎となるハッシュ関数に対するＮＭＡＣの非効率性も表中に記載されている。
【００１５】
【表１】
表１： さまざまなサイズの短いメッセージに対する圧縮呼出し回数の比較
【００１６】
表からわかるように、小さいメッセージに対する不利益は大きくなる。特に、１ブロック内に収まるメッセージの場合、不利益は１００％である。その理由は、ＮＭＡＣでは２回の圧縮関数呼出しが要求されるのに対して、基礎となる暗号ハッシュ関数により要求されるのは１回の圧縮呼出しであるからである。
【００１７】
圧縮関数ｆにはアクセスすることができず、メッセージで暗号ハッシュ関数Ｆを呼び出すことだけができるような実装に対する、ＮＭＡＣの実用的変形がＨＭＡＣである。このような実装の場合、鍵は、連鎖変数とすることはできず、関数Ｆは、最初の圧縮関数で用いられた固定の既知のＩＶで呼び出される。ＨＭＡＣ関数は次のように定義される。
【数１】
ただし、鍵ｋが使用され、バーｋは、反復されるハッシュ関数のブロックサイズｂに達するようにｋをゼロでパディングしたものである。バーｋの値はｏｐａｄとビットごとの排他的論理和がとられ、その結果がメッセージＸに連結される、ハッシュ関数Ｆは、連結されたメッセージ全体で呼び出される。図８に示すように、圧縮関数ｆの最初の実行（イタレーション）の後、鍵ｋ２がｋ２＝ｆ（バーｋ（＋）ｉｐａｄ）として生成される。（本願の明細書および図面において、記号（＋）と、数１に現れた排他的論理和の記号（円内に＋）とは、同一の記号を表すものとする。）ハッシュ関数Ｆが完了した後、結果の値Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ）が生成される。次に、バーｋ（＋）ｏｐａｄ（すなわち、バーｋとｏｐａｄのビットごとの排他的論理和演算）の値からなるメッセージで、ハッシュ関数Ｆが再び呼び出される。ハッシュ関数Ｆの第２の呼出し内の最初の実行の後、圧縮関数ｆ（ＩＶ，バーｋ（＋）ｏｐａｄ）から鍵ｋ１が得られる。ｉｐａｄおよびｏｐａｄの値は、M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for Message Authentication", In Proc. CRYPTO 96, Lecture Notes in Computer Science, Springer-Verlag, 1996、に記載されているような固定された定数である。ハッシュ関数への第２の呼出し内の第２の実行は、圧縮関数ｆ（ｋ１，Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ））を用いて、ＨＭＡＣ関数Ｆ（バーｋ（＋）ｏｐａｄ，Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ））を生成する。
【００１８】
ｋ１＝ｆ（バーｋ（＋）ｏｐａｄ）およびｋ２＝ｆ（バーｋ（＋）ｉｐａｄ）と定義することにより、ＨＭＡＣｋ（ｘ）はＮＭＡＣ（ｋ１，ｋ２）（ｘ）となる。ＨＭＡＣは、メッセージ認証のためのインターネット標準である。示されるように、ＨＭＡＣの安全性の証明は、ＮＭＡＣに関係しており、基礎となる暗号ハッシュが（弱）耐衝突性であること、および、基礎となる圧縮関数が、両方とも適切に鍵がかけられた場合には安全なＭＡＣであること、を仮定する。ＨＭＡＣは、長いメッセージに対しては効率的であるが、短いメッセージに対しては、ネスト化された構成のために相当な非効率性が生じる。圧縮関数へのアクセスが許可されない場合に１ブロックより短いメッセージのＭＡＣを生成するため、ＨＭＡＣは、圧縮関数への４回の呼出しを必要とする。圧縮関数へのアクセスが許可されている場合、ｋ１およびｋ２を事前に計算し、圧縮関数の連鎖変数に挿入することができるため、圧縮関数への呼出しは２回でよい。この非効率性は、シグナリングメッセージのメッセージ認証のようないくつかのアプリケーションでは特に大きくなることがある。その場合、個々のメッセージはすべて１個または２個のブロック内に収まるからである。ＴＣＰ／ＩＰトラフィックの場合にも、多数のパケット（例えば、確認応答(acknowledgment)）が、ほとんどの暗号ハッシュの１ブロック内に収まる４０バイト程度のサイズを有することがよく知られている。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明は、安全性の証明をも提供しながら、長短両方のメッセージがＨＭＡＣより効率的にメッセージ認証されることを可能にする改良を提案する。
【課題を解決するための手段】
【００２０】
本発明の１つの特徴によれば、メッセージ認証コード（ＭＡＣ）を生成するメッセージ認証システムは、メッセージが鍵つき圧縮関数の１入力ブロック内に収まるときにその圧縮関数の１回のみの実行を使用することにより、効率を改善する。１ブロックより大きいメッセージに対しては、このＭＡＣシステムは、ネスト化ハッシュ関数を使用する。本発明のもう１つの特徴によれば、ＭＡＣシステムおよび方法は、ネスト化ハッシュ関数への入力として、メッセージの一部を使用する。例えば、メッセージ認証システムは、メッセージを第１部分と第２部分に分割することができる。ハッシュ関数がメッセージの第１部分を入力として実行されて中間結果を得、鍵つきハッシュ関数がメッセージの第２部分および中間結果を入力として使用して実行される。こうして、内側ハッシュ関数によって処理されることを必要とするメッセージの部分を少なくすることにより、小さいメッセージの場合には特に、効率が改善される。
【図面の簡単な説明】
【００２１】
【図１】本発明の原理によるＭＡＣ生成システムを使用可能なワイヤレス通信システムの概略図である。
【図２】ワイヤレス装置からワイヤレス通信システムへ送信されるメッセージを認証するためにＭＡＣがどのように使用されるかを示す概略図である。
【図３】ワイヤレス通信システムからワイヤレス装置へ送信されるメッセージを認証するためにＭＡＣがどのように使用されるかを示す概略図である。
【図４】圧縮関数ｆのブロック図である。
【図５】与えられた圧縮関数ｆに対するハッシュ関数Ｆの反復構成を示すブロック図である。
【図６】鍵つきハッシュ関数を示すブロック図である。
【図７】ネスト化ハッシュ関数（ＮＭＡＣ）を示すブロック図である。
【図８】ＨＭＡＣとして知られるＮＭＡＣの変形を示すブロック図である。
【図９】本発明の原理によるメッセージ認証システムにおける単一ブロックの場合のブロック図である。
【図１０】本発明の原理によるメッセージ認証システムにおける多重ブロックの場合のブロック図である。
【図１１】本発明の原理によるメッセージ認証システムのＥＮＭＡＣ実施例のブロック図である。
【図１２】本発明の原理によるメッセージ認証システムのＥＮＭＡＣ実施例の流れ図である。
【図１３】本発明の原理によるメッセージ認証システムのＥＨＭＡＣ実施例のブロック図である。
【図１４】本発明の原理によるメッセージ認証システムのＳＭＡＣ実施例のブロック図である。
【図１５】本発明の原理によるメッセージ認証システムのＳＭＡＣ実施例の流れ図である。
【発明を実施するための形態】
【００２２】
任意長のメッセージを処理するための、改善された効率を提供する、本発明の原理によるＭＡＣ生成システムおよび方法の実施例について以下で説明する。以下の説明では、ハッシュ関数という用語は、圧縮関数ｆおよび反復ハッシュ関数Ｆを包含する。ハッシュ関数は、鍵なしであることも鍵つきであることも可能であり、Ｆｋは鍵つき反復ハッシュ関数を表し、ｆｋは鍵つき圧縮関数を表す。想起すべき点であるが、ｆｋ（ｘ）は、鍵つき圧縮関数であり、その入力ブロックサイズはｂビットであり、出力サイズはｔビットであり、連鎖変数のサイズ、したがって鍵サイズもまたｔビットである。本発明の１つの特徴によれば、メッセージのサイズに依存して、ＭＡＣジェネレータは、異なるハッシュ関数構成を用いてＭＡＣを生成する。例えば、ＭＡＣジェネレータは、メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数ｆの１入力ブロックに収まる場合には、ハッシュ関数として鍵つき圧縮関数の１回のみの実行を行うことが可能である。入力ブロック内に収まらないメッセージの場合、ＭＡＣジェネレータは、ネスト化ハッシュ関数を使用する。図９に示すように、メッセージｘは、必要なパディング、メッセージ長フィールド、ブロックインジケータフィールドあるいはメッセージｘに付加されるその他のフィールドとともに、圧縮関数ｆに入力される。メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数の入力ブロック内に収まる場合、メッセージｘおよび鍵ｋを用いて鍵つき圧縮関数ｆ（９０）が１回のみ実行され、メッセージｘに対するＭＡＣ ｆｋ（ｘ）が生成される。
【００２３】
これに対して、図１０に示すように、メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数ｆの１入力ブロック内に収まらない場合、メッセージブロックｘは、部分１および部分２のように、複数の部分に分割される。メッセージブロックの部分部分は、メッセージｘを構成するビットの重なり合うセットであることも重なり合わないセットであることも可能である。本発明のもう１つの特徴によれば、第１部分は内側ハッシュ関数Ｆで使用され、第２部分は外側ハッシュ関数（これは、圧縮関数ｆＣＶ１として示されている）で使用される。例えば、部分２は、内側ハッシュ関数Ｆに提供され、そこで、圧縮関数１００ａ〜１００ｎ（必要であれば）の呼出し（実行）が、部分２のブロックである部分２１〜部分２ｎについて（付加されたパディングあるいはフィールドがあればそれも含む）行われる（ここで、ｎ≧１である）。圧縮関数ｆの最初の実行（呼出し）１００ａは、連鎖変数ＣＶ２を使用する。連鎖変数ＣＶ２は、実施例に依存して、鍵であることも、鍵から導出された鍵であることも、ハッシュ関数Ｆの標準の初期値であることも可能である。内側ハッシュ関数ＦＣＶ２（部分２）の結果は、メッセージｘの部分１および連鎖変数ＣＶ１とともに、外側ハッシュ（圧縮）関数ｆ（１０２）に提供される。連鎖変数ＣＶ１は、実施例に依存して、鍵であることも、鍵から導出された鍵であることも、ハッシュ関数Ｆの標準の初期値ＩＶであることも可能である。その結果の値ｆＣＶ１（部分１，ＦＣＶ２（部分２））は、メッセージ認証で用いられるＭＡＣを生成するために使用されることが可能となる。
【００２４】
上記の一般的記述を用いて、従来技術のＭＡＣ生成方式よりも改善された性能を提供することができる。例えば、短いメッセージに対してＮＭＡＣよりも改善された効率を可能にするとともに、より長いメッセージに対しても多少の改善を可能にするため、以下のＭＡＣ生成法が提供される。想起すべき点であるが、ｆｋ（ｘ）は、その入力ブロックサイズがｂビットであり、出力サイズがｔビットであり、連鎖変数のサイズ、したがって鍵サイズもまたｔビットであるような圧縮関数である。図１１ａおよび図１１ｂに示すように、本発明の原理によるＭＡＣの生成の具体的実施例は次の通りである。
【数２】
ただし、第１の場合、ブロック内の最初のｂ−２ビットが、メッセージｘを入れるために使用される。メッセージｘが最初のｂ−２ビットに満たない場合、パディングが必要であり、ブロックの残りは、最終ビットが義務的に１とされることを除いては、その後には０が続く（ないこともある）。メッセージの長さがｂ−２ビットである場合、ｂ−１番目のビットが１にセットされる。この実施例では、ブロックの最終ビットが、ＥＮＭＡＣで単一圧縮呼出しが使用されているかどうかを示す。ブロックの最終ビットは、単一圧縮呼出しの場合には１にセットされ、圧縮関数ｆの多重呼出し（実行）が必要とされるときには０にセットされる。１ブロックに収まらないという第２の場合、ストリングｘは、次のような２つの部分（セグメント）ｘｐｒｅｆおよびｘｓｕｆｆに分解される。
ｘｐｒｅｆ＝ｘ１...ｘｂ−ｔ−１
ｘｓｕｆｆ＝ｘｂ−ｔ...ｘ｜ｘ｜
まず、ｘｓｕｆｆが鍵値ｋ２を用いてハッシュされ、Ｆｋ２（ｘｓｕｆｆ）のｔビットの結果が生成される。次に、外側圧縮呼出しが鍵値ｋ１を用いて実行される。ここで、最初のｂ−ｔ−１ビットにｘｐｒｅｆがセットされ、次のｔビットに結果Ｆｋ２（ｘｓｕｆｆ）がセットされ、最終ビットに０がセットされる。
【００２５】
上記のＥＮＭＡＣ生成法は、具体的に図１２を参照して以下で説明するように、基礎となる暗号ハッシュ関数としてＳＨＡ−１ハッシュ関数を使用することができる。ブロック１１０に示されているように、ＥＮＭＡＣ生成法を実現する処理回路は、ｘの長さ｜ｘ｜が５１０ビット以下であるかどうかを判断する。ｘの長さ｜ｘ｜が５１０ビット以下である場合、処理回路はステップ１１２に進み、ｘを最初の５１０ビットにロードすることによって、ｆｋ１（）の５１２ビットのペイロードを形成する。次に、ブロック１１４で、「１」をｘに付加し、ステップ１１６で、必要な個数の０（ないこともある）を用いて５１１ビットを満たす。｜ｘ｜が５１０ビットより小さい場合、１の後にゼロがパディングされるが、｜ｘ｜が５１０ビットである場合、ゼロはパディングされず、ブロック１１４では、１個の１が５１１番目のビット位置に付加されるだけである。ブロック１１８で、メッセージが単一ブロックに収まることを示すために、最後の５１２番目のビット（ブロックインジケータビット）が１にセットされる。ブロック１２０で、鍵ｋ１を１６０ビットの連鎖変数とし、メッセージｘ、パディングビットおよびブロックインジケータビットを５１２ビットのペイロード（入力ブロック）として、鍵つき圧縮関数ｆｋ１（ｘ，ｐａｄ，１）が実行される。その後、ブロック１２２で、結果ｆｋ１（ｘ，ｐａｄ，１）が出力され、ＭＡＣを生成するために使用される。
【００２６】
ブロック１１０で、メッセージｘが５１０ビットより長い場合、処理回路はブロック１２４に進み、メッセージは２つの部分ｘｐｒｅｆおよびｘｓｕｆｆに分割される。ただし、ｘｐｒｅｆ＝ｘ１...ｘ３５１およびｘｓｕｆｆ＝ｘ３５２...ｘ｜ｘ｜である。次に、ブロック１２６で、処理回路は、鍵ｋ２と、メッセージ部分ｘｓｕｆｆとを、追加のパディングビットやビットフィールドがあればそれとともにペイロードとして、鍵つきハッシュ関数Ｆｋ２を実行し、Ｆｋ２（ｘｓｕｆｆ）の１６０ビットの結果を得る。ブロック１２８で、外側圧縮関数ｆｋ１のペイロードの最初の３５１ビットにｘｐｒｅｆをセットし、ブロック１３０で、ペイロードの次の１６０ビットに、ブロック１２６で計算したＦｋ２（ｘｓｕｆｆ）の結果をセットする。ブロック１３２で、ペイロードの最後の５１２番目のビットを０にセットする。最後に、ブロック１３４で、外側鍵つき圧縮関数ｆｋ１が、ブロック１２８〜１３２で形成された５１２ビットのペイロードに適用され、ブロック１３６で、その結果ｆｋ１（ｘｐｒｅｆ，Ｆｋ２（ｘｓｕｆｆ），０）が、ＭＡＣを生成するために出力される。
【００２７】
次の表２は、３０バイトずつ増大するさまざまなサイズの短いメッセージに対して、基礎となるハッシュ関数ＳＨＡ−１によって、および、ＥＮＭＡＣによって必要とされる圧縮呼出しの個数を比較している。表２と、ふつうのＮＭＡＣの比較をした前の表１との間には重要な相違点が存在する。短いサイズの多くのものについて、ＮＭＡＣは、基礎となるハッシュ関数と同じ効率を有する。長いメッセージの場合、ＮＭＡＣ、ＥＮＭＡＣおよび基礎となるハッシュ関数の効率は互いに相当異なる。サイズが４８０ビットのメッセージの場合、表２の記載事項が意外にも示しているように、ＥＮＭＡＣは基礎となるハッシュ関数より効率がよい。この例外的なことが起こる理由は、基礎となるＳＨＡ−１関数がサイズ情報のために６４ビットを確保するのに対して、ＥＮＭＡＣは、５１０ビットより短いメッセージについては２ビットしか確保しないためである。このため、ＥＮＭＡＣを使用する結果の節約は、１ないし数ブロックに収まるメッセージについてはかなり大きい。
【００２８】
【表２】
表２： さまざまなサイズの短いメッセージに対する圧縮呼出し回数の比較
【００２９】
１ブロックに収まるメッセージのＭＡＣを生成するために異なる鍵ｋ３を使用し、より長いメッセージのＭＡＣを生成するためにＮＭＡＣを用いて鍵ｋ＝（ｋ１，ｋ２）を使用すると仮定すると、システムが安全であることを示すことができる。本質的には、これが実際に行われていることであるが、異なる鍵を用いて異なるＭＡＣを生成する代わりに、メッセージが１ブロックに収まる場合にはトレーリングビットが１にセットされ、その他の場合には０にセットされている。第２に、ＮＭＡＣは、外側圧縮呼出しのペイロードをゼロでパディングするのに対して、ＥＮＭＡＣは、メッセージの一部を外側呼出しに入れる。
【００３０】
ＥＮＭＡＣ安全性の結果は、ＮＭＡＣと同様であり、以下で、教育的目的で主張し証明する。
【００３１】
定理２： ｔ回のステップおよびｑ回の問合せで、鍵つき圧縮関数ｆがεｆ安全なＭＡＣであり、かつ、鍵つき反復ハッシュＦがεＦ弱耐衝突性であるならば、ＥＮＭＡＣ関数は（εｆ＋εＦ）安全なＭＡＣである。
【００３２】
証明： 敵ＡＥが、ｔ回のステップと、ｑ回の適応的に選択されたＥＮＭＡＣ関数への問合せとを仮定して、確率εＥでＥＮＭＡＣに対して成功したとする。この敵は、以前に問い合わせていないメッセージに関して、鍵つき圧縮関数に関連するＭＡＣを偽装する別の敵Ａｆを形成するために使用される。ＭＡＣを破るこの確率は、εＥと、εＦ、すなわち、敵が時間ｔおよびｑ回の問合せでハッシュ関数Ｆにおける衝突を見つける最良の確率、に関して限界づけられる。ＡＥを用いて、この特定の方法でＭＡＣを破る確率は、任意の方法でＭＡＣを破る確率εｆより小さくなければならない。これを用いて、εＥについての限界を得ることができる。鍵つき圧縮ＭＡＣを偽造するために用いられるアルゴリズムＡｆを次に示す。
【００３３】
ランダムなｋ２を選ぶ
Ｆｏｒ ｉ．．．ｑ
ＡＥ→ｘｉ
Ｉｆ ｘｉ＜ｂ−２
ＡＥ←ｆｋ１（ｘｉ，ｐａｄ，１）
ｅｌｓｅ
ＡＥ←ｆｋ１（１，ｘｉ，ｐｒｅｆ，Ｆｋ２（ｘｉ，ｓｕｆｆ），０）
ＡＥ→（ｘ，ｙ）
Ｉｆ ｘ＜ｂ−２
（ｘ，ｐａｄ，１），ｙ を出力
ｅｌｓｅ
（ｘｐｒｅｆ，Ｆｋ２（ｘｓｕｆｆ），０），ｙ を出力
【００３４】
εＥ＝εＥ１＋εＥ＋とおく。ここで、εＥ１は、ＥＮＭＡＣが攻撃され、ＡＥによって偽造されたＥＮＭＡＣメッセージがおよそ１ブロックサイズである（正確にいえば、ｂ−２より小さい）確率である。また、Ｅ＋およびεＥ＋はそれぞれ、ＥＮＭＡＣが攻撃され、ＡＥによって偽造されたＥＮＭＡＣメッセージが１ブロックサイズより大きい事象および確率であるとする。さらに、εＥ＋＝εＥ＋，ｐｒｅｆ≠＋εＥ＋，ｐｒｅｆ＝である。ここで、εＥ＋，ｐｒｅｆ≠は、ＥＮＭＡＣが多重ブロックメッセージで偽造され、メッセージのプレフィクスが、以前にＡＥによって問合せされたいずれのメッセージのプレフィクスとも等しくない確率である。また、εＥ＋，ｐｒｅｆ＝は、ＥＮＭＡＣが多重ブロックメッセージで偽造され、メッセージのプレフィクスが、以前にＡＥによって問合せされたいずれかのメッセージのプレフィクスに等しい確率である。この場合、偽造メッセージのサフィクスは、同じプレフィクスを有するメッセージのサフィクスとは異ならなければならない。
【００３５】
Ｐ［ｆのＭＡＣを偽造］＝Ｐ［ｆのＭＡＣがＥ１により偽造される］＋Ｐ［ｆのＭＡＣがＥ＋により偽造される］ （１）
＝εＥ１＋Ｐ［ｆのＭＡＣがＥ＋により偽造される］
＝εＥ１＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ≠により偽造される］＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される］ （２）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される］
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋Ｐ［Ｅ＋，ｐｒｅｆ＝∩同じプレフィクスの集合内にサフィクス衝突がない］ （３）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝∪同じプレフィクスの集合内にサフィクス衝突がある］ （４）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝］−Ｐ［集合内に衝突がある］＋Ｐ［バーＥ＋，ｐｒｅｆ＝∩集合内に衝突がある］
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝］−Ｐ［集合内に衝突がある］ （５）
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−１＋εＥ＋，ｐｒｅｆ＝−Ｐ［ｑ個の問合せ内に衝突がある］ （６）
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−１＋εＥ＋，ｐｒｅｆ＝−εＦ
≧εＥ１＋εＥ＋−εＦ
≧εＥ−εＦ （７）
εｆ≧Ｐ［ＥＮＭＡＣを偽造することによりｆのＭＡＣを偽造］≧εＥ−εＦ （８）
εｆ≧εＥ−εＦ
ゆえに、εＥ≦εｆ＋εＦ （９）
【００３６】
式１は、ｆの新しいＭＡＣを偽造する確率を、単一ブロックまたは多重ブロックのいずれかの、ＥＮＭＡＣのＭＡＣを偽造することによりｆの新しいＭＡＣを偽造する確率に分解する。多重ブロックＥＮＭＡＣを破ることによりｆを破る確率は、式２において、どのプレフィクスもすべての問合せされたメッセージの他のいずれかのプレフィクスに等しくない場合と、問合せされたメッセージのうちに等しいプレフィクスがある場合とに分解される。式３では、ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される確率が、Ｅ＋，ｐｒｅｆ＝が起こり、かつ、同じプレフィクスを有するメッセージのうちにサフィクスのハッシュの衝突が起こらない確率と等値される。式４は、ドモルガンの法則を用いた式３の書き換えである。式６では、同じプレフィクスを有する集合中での衝突の確率が、ｑ個のすべての問合せでの衝突の確率で置き換えられる。式９は、ＥＮＭＡＣを偽造する確率εＥが、ＭＡＣを偽造する確率εｆと、衝突を見つける確率εＦの和より小さいという、われわれの求める結果である。
【００３７】
実際には、データはバイト単位で処理されることが多いため、メッセージｘの長さが、上で指定したｂ−２ビットではなくｂ−８ビットより小さいときに、単一ブロックの場合を実行するほうが適当かもしれない。多重ブロックＥＮＭＡＣの場合、非ワード境界から開始してｘｓｕｆｆを形成すると、ｘｓｕｆｆにおける全ワードの再配置（アラインメントのしなおし）を引き起こすことがある。これは、次のように、実用的な目的のために、ビットではなくバイトサイズを用いたＥＮＭＡＣの変形を用いることにより回避することができる。
【数３】
ここで、基礎となる暗号ハッシュ関数ｆとしてＳＨＡ−１を用いた場合、
ｘｐｒｅｆ＝ｘ１...ｘ｜ｘ｜−３４４
ｘｓｕｆｆ＝ｘ｜ｘ｜−３４３...ｘ｜ｘ｜
である。６３バイト（５０４ビット）までの長さのメッセージについては、メッセージを５０４ビットにパディングするための１つの１とそれに続く０の追加的なパディングに加えて、最終バイトが、ブロックインジケータのために、すなわち「Ｘ００００００１」として予約される。ここで、１は単一ブロックメッセージを示し、Ｘは、５０４ビットのパディングなしメッセージにつづく「１」であることが可能である。５０４ビットより短いパディングなしメッセージの場合、Ｘは「０」である。５０４ビットより長いメッセージの場合、メッセージは部分ｘｐｒｅｆおよびｘｓｕｆｆに分割される。ここで、ｘｓｕｆｆの長さは４３バイト（３４４ビット）であり、ｘｐｒｅｆの長さ＝メッセージの長さ−３４４ビット、である。
【００３８】
上記の実施例に加えて、本発明の原理によるメッセージ認証システムは、入力パラメータや圧縮（ハッシュ）関数あるいはその他の演算、鍵値の省略あるいは追加を行うことや、上記のシステムの変形あるいは一部を使用することも可能である。例えば、図１３ａおよび図１３ｂは、次のような改良されたＨＭＡＣとして使用されるメッセージ認証システムの実施例を示す。
【数４】
第１の図１３ａの場合、メッセージｘは単一ブロックに収まる。これは、メッセージｘが、ｂ−１−他フィールド、より小さくなければならないことを意味する。ここで、他フィールドには、ハッシュ関数Ｆのパディングあるいは長さ付加方式によるいくつかのビットが含まれる。ｘが十分小さいと仮定すると、最初の部分がｋ（＋）ｏｐａｄで、それにｘが続き、さらにそれに１にセットされた１ビットが続くという、より長い入力が形成される。このより長いメッセージは、基礎となるハッシュ関数Ｆに入力される。Ｆの内部を見ると、まず、鍵ｋ１が、圧縮関数ｆ（ｋ（＋）ｏｐａｄ）を呼び出すことによって生成される。ここで、ｋは、適当な長さにパディングされなければならない可能性がある。その結果は、圧縮関数への次の呼出しのための連鎖変数として使用される。そのペイロードは、（ｘ，１）に、ハッシュ関数Ｆの仕様に従ってパディングあるいは長さ付加したものである。
【００３９】
図１３ｂは、メッセージｘが、必要な付加フィールドとともに、１ブロックに収まらない場合であり、この場合、ストリングｘは、２つの部分（セグメント）ｘｐｒｅｆおよびｘｓｕｆｆに分解される。ここで、
ｘｐｒｅｆ＝ｘ１...ｘｂ−ｔ−１−ｏｔｈｅｒ
ｘｓｕｆｆ＝ｘの残りの部分
である。まず、内側ハッシュ関数１３０で、鍵ｋとｉｐａｄの間のビットごとの排他的論理和を実行してｋ２を生成する。このｋ２は、入力ブロックｘｓｕｆｆ１とともに連鎖変数として使用される。ブロックｘｓｕｆｆｎが最後の圧縮関数に入力されるまで、圧縮関数ｆが、パディング、付加長フィールドあるいはその他のフィールドとともに呼び出され、Ｆ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ）のハッシュ関数の結果が生成される。ここで、ｋは、適当な長さにパディングされなければならないこともある。外側ハッシュ関数１３２では、値ＩＶを連鎖変数とし、ｋ（＋）ｏｐａｄを入力として圧縮関数１３４を呼び出すことによって、鍵ｋ１が決定される。値ｋ１は、ｘｐｒｅｆの後にＦ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ）を付加しその後にゼロを付加したものを入力とする圧縮関数１３６のための連鎖変数として使用される。その結果のＦ（ｋ（＋）ｏｐａｄ，ｘｐｒｅｆ，Ｆ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ），０）は、ＭＡＣを提供するために使用することができる。
【００４０】
図１４ａおよび図１４ｂは、バイト単位での具体的実装例に関して以下で説明するようなＳＭＡＣシステムとして使用される、メッセージ認証システムのもう１つの実施例を示す。
【数５】
ｘｐｒｅｆ： バイトｘ１...ｘ｜ｘ｜−４３
ｘｓｕｆｆ： バイトｘ｜ｘ｜−４２...ｘ｜ｘ｜
【００４１】
他の実施例と同様、ＳＭＡＣは２つの場合からなる。すなわち、図１４ａの単一ブロック（≦６３バイト）の場合、および、図１４ｂの多重ブロック（＞６３バイト）の場合である。いずれの場合でも、ＳＨＡ関数のような鍵つき圧縮関数ｆへの呼出しが行われる。単一ブロックの場合、他の関数呼び出しは不要である。しかし、多重ブロックの場合、標準のＳＨＡ１＿ＨＡＳＨのような鍵なしハッシュ関数Ｆ（１４０）が、メッセージの最初の部分ｘｐｒｅｆに適用される。次に、そのハッシュ結果と、メッセージの残りの部分が入力すなわちペイロードブロックに入れられ、鍵つき圧縮関数ｆ（１４２）への呼出しが行われる。ＳＨＡ−１圧縮関数ｆの引数の詳細を下記の表３および表４に示す。
【００４２】
示されているように、ｓｈａ１圧縮関数の５１２番目のビットは、「単一ブロックインジケータビット」として使用され、単一ブロックの場合には１にセットされ、多重ブロックの場合には０にセットされる。この実施例ではメッセージはバイトの倍数で処理されるため、最終バイト内の残りのビットはいずれも、メッセージを処理するために使用することはできない。したがって、圧縮関数の最終（６４番目の）バイト全体が予約される。多重ブロックの場合、表４に示すように、ビット５０５〜５１１もまたゼロにセットされる。単一ブロックの場合、ビット５０６〜５１１はゼロにセットされるが、５０５番目のビットは追加のパディングビットとして使用される。その機能は、単一ブロックの場合に使用されるパディング方式について説明した後には明らかになるであろう。
【００４３】
１ブロックを部分的に満たすメッセージはパディング方法を必要とする。多重ブロックの場合は、圧縮関数を満たすためにパディング方法を必要としない。その理由は、ブロックは表４に示すように完全に満たされるからである。しかし、ＳＨＡ１＿ＨＡＳＨ関数は、ｘｐｒｅｆをハッシュするときに、その固有のパディングを使用する。単一ブロックの場合にメッセージをパディングするため、１個の１をメッセージに付加した後、ブロック内の残りのビット数が満たされるまで（より正確には、５０５番目のビットが満たされるまで）の個数のゼロ（ないこともある）を付加する。例として、単一ブロックメッセージの長さが６３バイトすなわち５０４ビットである特殊な場合には、１個の１が５０５番目のビットに付加される。残りのビット５０６〜５１２は前述のように満たされる。
【００４４】
多重ブロックの場合、ハッシュ関数Ｆ（１４０）は、ブロックｘｐｒｅｆ１〜ｘｐｒｅｆｎにおいては、メッセージの最後の４３バイト以外のすべてのバイトに適用され、２０バイトのダイジェストを出力する。最後の４３バイトは、圧縮関数ｆ（１４２）によって処理されるようにするため、ハッシュ関数Ｆでは処理されない。４３バイトである理由は、表４に示すように、利用可能な６４バイトのうち、最初の２０バイトはダイジェストとして使用され、最終バイトは、ＳＨＡ−１ハッシュ関数およびＳＨＡ−１圧縮関数のために特別に予約されるからである。
【００４５】
【表３】
表３： 単一ブロックの場合： ｓｈａ１圧縮関数の引数
【００４６】
【表４】
表４： 多重ブロックの場合： ｓｈａ１圧縮関数の引数
【００４７】
図１５に、ＳＭＡＣ関数の流れ図を示す。最初に、ステップ１４８で、鍵がＩＶとＸＯＲされ、ｓｈａ１圧縮関数の連鎖変数にロードされる。ブロック１５０で、処理回路は、｜ｘ｜＞６３バイトであるかどうかを判断する。｜ｘ｜＞６３バイトでない場合、処理回路は単一ブロックの場合に進み、ブロック１５２で、メッセージｘが圧縮関数ｆの５１２ビットブロックの左側にロードされる。ブロック１５４で、処理回路は、次のビットに「１」を付加する。ブロック１５６で、最後の５１２番目のビットまで、ブロックの残りの部分がゼロで満たされる。ブロック１５８で、最後の５１２番目のビットは１にセットされる。ブロック１６０で、連鎖変数（Ｋ ＸＯＲ ＩＶ）と、ブロック１５２〜１５８からのペイロードとを用いて圧縮関数ｆが呼び出される。ブロック１６２で、２０バイトのＭＡＣが返される。
【００４８】
ブロック１５０で、｜ｘ｜＞６３バイトである場合、処理回路は多重ブロックの場合に進む。ブロック１６４で、メッセージｘは２つの断片、すなわち、ｘｐｒｅｆ：バイトｘ１...ｘ｜ｘ｜−４３と、ｘｓｕｆｆ：バイトｘ｜ｘ｜−４２...ｘ｜ｘ｜、に分割される。ブロック１６６で、ＳＨＡ１＿ＨＡＳＨ関数がｘｐｒｅｆで呼び出され、２０バイトの結果が生成される。ブロック１６８で、この２０バイトの結果が、ｓｈａ１圧縮関数の６４バイトブロックの左側にロードされ、ｘｓｕｆｆがバイト２１〜６３に付加される。ブロック１７０で、最後の６４番目のバイトが０にセットされる。最後に、ブロック１７２で、最初に計算された連鎖変数（Ｋ ＸＯＲ ＩＶ）と、ブロック１６８および１７０からのペイロードとを用いて、ｓｈａ１圧縮関数が呼び出される。ブロック１６２で、２０バイトのＭＡＣが返される。
【００４９】
ＳＭＡＣはＨＭＡＣよりもＮＭＡＣに近いため、ＳＭＡＣをＨＭＡＣではなくＮＭＡＣと比較することにする。ＮＭＡＣは、ハッシュ関数Ｆへの内側呼出しと、圧縮関数ｆへの外側呼出しを有する。ＳＭＡＣは、６３バイトより長いメッセージに対しては同じことを行うが、それより短いメッセージに対してはハッシュ呼出しをスキップする。長いメッセージの場合、ＳＭＡＣは、メッセージの一部を外側圧縮呼出しで処理するため、内側ハッシュ関数呼び出しにより処理されるテキストが少なくなる。ＮＭＡＣはこれを行わないが、代わりに、外側圧縮呼出しのペイロードの残りをゼロで満たす。ＮＭＡＣでは、内側ハッシュ関数は鍵つきであるのに対して、ＳＭＡＣは、内側呼出しに鍵をかけない。ＳＭＡＣの内側呼出しに鍵をかけることも可能であるが、効率性の目的のために、本実施例ではそのようにしなかった。その安全性は基本的に影響を受けない。その理由は、鍵なしＳＨＡ１＿ＨＡＳＨ関数であっても衝突を見つけるのは実行不可能であると考えられているからである。
【００５０】
以下は、ＳＭＡＣを実装するために使用可能なコードである。
【００５１】
内側格納データへの出力：
MAC 32 bits
/* smacは次の関数を呼び出す */
sha1_comp(unsigned char cv[20], unsigned char temp[64], unsigned char adigest[20])
{ /* sha1_compはｓｈａ１圧縮関数であり、cvは１６０ビットの連鎖変数であり、tempは５１２ビットのペイロードであり、結果は１６０ビットのadigestに出力される */
...
}
SHA1_HASH(unsigned char *M, int textlen, unsigned char adigest[20])
{ /* SHA1_HASHはハッシュ関数であり、Mはメッセージであり、textlenはメッセージ内のバイト数であり、結果は１６０ビットのadigestに出力される */
...
}
smac(int keylen, unsigned char *K, int textlen, unsigned char *M, unsigned char mac[20])
{ int i, j;
unsigned char cv[20], temp[64];
/* ２０バイトの連鎖変数cvをｆｉｐｓ１８０で定義されるようにセット */
cv[0]=0x67; cv[1]=0x45; cv[2]=0x23; cv[3]=0x01; cv[4]=0xef;
cv[5]=0xcd; cv[6]=0xab; cv[7]=0x89; cv[8]=0x98; cv[9]=0xba;
cv[10]=0xdc; cv[11]=0xfe; cv[12]=0x10; cv[13]=0x32; cv[14]=0x54;
cv[15]=0x76; cv[16]=0xc3; cv[17]=0xd2; cv[18]=0xe1; cv[19]=0xf0;
/* 鍵を連鎖変数とＸＯＲする */
for(i=0; i<keylen; i++)
cv[i] = cv[i] ^ K[i];
/* temp圧縮ブロックをオールゼロにセット */
for(i=0; i<64; i++) temp[i] = 0;
if ( textlen <= 63 ) {
/* メッセージを最も左側にロード */
for(i=0; i<textlen; i++)
temp[i] = M[i];
temp[i] = 0x80; /* '1'を付加。残りのビットは事前に０にセットされる */
temp[63] = temp[63] | 0x01; /* ５１２番目のビットを'1'にセット */
sha1_comp(cv, temp, mac);
}
else { /* textlen > 63 */
/* Mのプレフィクスに対するSHA1_HASH */
SHA1_HASH(M, textlen-43, mac);
for(i=0; i<20; i++)
temp[i] = mac[i]; /* ダイジェストを最も左側にコピー */
for(i=20; i<63; i++)
temp[i] = M[textlen-43+(i-20)]; /* 次にMのサフィクスをコピー */
temp[63] = 0x00; /* 最終バイトをゼロにセット */
sha1_comp(cv, temp, mac);
}
}
【００５２】
以上、ＭＡＣシステムについて、ＳＨＡ−１のような特定のハッシュ（圧縮）関数とともに使用されるものとして説明したが、他のハッシュ関数や関連する暗号関数、また、別のあるいは追加の関数を使用することも可能である。さらに、メッセージ、ペイロード、連鎖変数および鍵値について、特定のビットあるいはバイトが記載されているが、実施例に依存して、これらの数は変更可能である。さらに、鍵値は、鍵またはその一部から導出された鍵であることも可能である。理解されるべき点であるが、さまざまな値、入力およびアーキテクチャブロックについて、異なる記法、用語および特徴づけを使用することも可能である。例えば、圧縮関数ｆという用語が使用され、ハッシュ関数Ｆという用語が使用され、反復ハッシュ関数Ｆは、圧縮関数ｆの反復（連鎖）を用いて構成されている。理解されるべき点であるが、圧縮関数はハッシュ関数でもある。
【００５３】
代替実施例では、メッセージ認証システムについて記載された関数は、ホーム認証センタ、ホームロケーションレジスタ（ＨＬＲ）、ホームＭＳＣ、在圏認証センタ、在圏ロケーションレジスタ（ＶＬＲ）あるいは在圏ＭＳＣにある処理回路で実行されることが可能である。さらに、メッセージ認証センタおよびその各部分は、ワイヤレス装置、基地局、基地局コントローラ、ＭＳＣ、ＶＬＲ、ＨＬＲあるいはその他のワイヤレス通信システムのサブシステムで実行されることが可能である。実施例に依存して、ＭＡＣは、メッセージとともに送信されることが可能であり、その場合、ＭＡＣは、受信端で生成されたＭＡＣと比較・検証される。ＭＡＣがメッセージとともに送信される前に、追加機能がＭＡＣを変更あるいは変換することが可能であり、その場合、同じ機能が、比較・検証（メッセージ認証）のために、受信端で生成されるＭＡＣに対して実行されることが可能である。最後に、ＭＡＣが送信され、追加機能が、受信されたＭＡＣと受信端で生成されたＭＡＣを変更あるいは変換してメッセージ認証を実行することも可能である。追加機能の一例は、メッセージ認証を実行する際の比較・検証機能のために、ＭＡＣの下位３２ビットを使用するものである。こうして、ＭＡＣ、あるいは、変更または変換されたＭＡＣは、ＭＡＣまたはタグと呼ぶことが可能である。
【００５４】
さらに、上記では、メッセージ認証システムはワイヤレス通信システムに関連して説明されているが、メッセージ認証システムは、送信側から受信側へ任意のネットワークあるいは通信媒体を通じて送信される通信メッセージを認証（その完全性を検証）するために使用可能である。
【００５５】
[発明の効果]
以上述べたごとく、本発明によれば、長短両方のメッセージがＨＭＡＣより効率的にメッセージ認証されることが可能となる。
【００５６】
特許請求の範囲の発明の要件の後に括弧で記載した番号がある場合は、本発明の一実施例の対応関係を示すものであって、本発明の範囲を限定するものと解釈すべきではない。
【符号の説明】
【００５７】
１２ ワイヤレス装置
１４，１６ 地理的領域（地理的エリア）
２０，２４ 移動通信交換局（ＭＳＣ）
２２，２６ 基地局
２５ ワイヤライン装置
２８ 公衆交換電話網（ＰＳＴＮ）
２９ パケットデータネットワーク（ＰＤＮ）
３２ シグナリングネットワーク（信号網）
３４ ホームロケーションレジスタ（ＨＬＲ）
３６ 在圏ロケーションレジスタ（ＶＬＲ）
５０，５２，５６，５８ ＭＡＣジェネレータ
９０ 鍵つき圧縮関数ｆ
１０２ 外側ハッシュ（圧縮）関数ｆ
１３０ 内側ハッシュ関数
１３２ 外側ハッシュ関数
１３４，１３６ 圧縮関数
１４０ 鍵なしハッシュ関数Ｆ
１４２ 鍵つき圧縮関数ｆ
【技術分野】
【０００１】
本発明は、通信に関し、特に、メッセージの認証に関する。
【背景技術】
【０００２】
図１は、地理的領域１４および１６のそれぞれの内部に位置するワイヤレス（無線）装置（例えば、ワイヤレス装置１２ａ〜ｃ）にワイヤレス通信サービスを提供する第１および第２のワイヤレス通信システムの概略図である。移動通信交換局（ＭＳＣ）（例えば、ＭＳＣ２０および２４）は、とりわけ、ワイヤレス装置間の呼、ワイヤレス装置とワイヤライン（有線）装置（例えば、ワイヤライン装置２５）との間の呼、あるいは、ワイヤレス装置とインターネットのようなパケットデータネットワーク（ＰＤＮ：packet data network）との間のコネクションを確立し維持する責任を負う。このため、ＭＳＣは、その地理的領域内のワイヤレス装置を公衆交換電話網（ＰＳＴＮ）２８あるいはパケットデータネットワーク（ＰＤＮ）２９と相互接続する。ＭＳＣによってサービスされる地理的エリアは、「セル」と呼ばれる空間的に相異なるエリアに分割される。図１に示されているように、各セルは、模式的には、蜂の巣パターンの１つの六角形によって表される。しかし、実際には、各セルは、そのセルの周囲の地形に依存する不規則な形状を有する。
【０００３】
一般に、各セルは基地局（例えば、基地局２２ａ〜ｅおよび２６ａ〜ｅ）を有する。基地局は、そのセル内のワイヤレス装置と通信するために使用する無線機およびアンテナを有する。基地局はまた、その地理的エリア内のＭＳＣと通信するために使用する伝送装置も有する。例えば、ＭＳＣ２０は、地理的エリア１４内の基地局２２ａ〜ｅに接続され、ＭＳＣ２４は、地理的エリア１６内の基地局２６ａ〜ｅに接続される。１つの地理的領域内で、ＭＳＣは、ワイヤレス装置がセル間を移動していくのとともにリアルタイムで基地局間で呼を交換する。これを呼ハンドオフという。具体的実現化に依存して、基地局コントローラ（ＢＳＣ）は、いくつかの基地局に接続された別個の基地局コントローラ（ＢＳＣ）（図示せず）であることも可能であり、あるいは、各基地局に配置され、基地局のワイヤレス資源を管理し情報をＭＳＣに中継することも可能である。
【０００４】
ＭＳＣ２０および２４は、シグナリングネットワーク（信号網）３２を使用する。シグナリングネットワーク３２は、例えば、ＴＩＡ／ＥＩＡ−４１−Ｄとして指定された、"Cellular Radiotelecommunications Intersystem Operations", December 1997（ＩＳ−４１）という名称の標準に準拠するシグナリングネットワークである。これは、それぞれの地理的エリア１４および１６内をローミングしているワイヤレス装置に関する情報の交換を可能にする。例えば、ワイヤレス装置１２ａは、もともと割り当てられたＭＳＣ２０（ホームＭＳＣ）の地理的エリア１４を離れるとき、ローミングしている。ローミングワイヤレス装置が呼を受け取ることができることを保証するため、ローミングワイヤレス装置１２ａは、現在位置のＭＳＣ２４（在圏ＭＳＣ）にその存在を通知することによって、在圏ＭＳＣ２４に登録する。ローミングワイヤレス装置１２ａが在圏ＭＳＣ２４によって識別されると、在圏ＭＳＣ２４は、シグナリングネットワーク３２を通じて、ホームＭＳＣ２０に登録要求を送り、ホームＭＳＣ２０は、在圏ＭＳＣ２４の識別によってデータベース３４（ホームロケーションレジスタ（ＨＬＲ）という）を更新することにより、ローミングワイヤレス装置１２ａの位置をホームＭＳＣ２０に提供する。ローミングワイヤレス装置が認証された後、ホームＭＳＣ２０は、在圏ＭＳＣ２４に顧客プロファイルを提供する。在圏ＭＳＣ２４は、顧客プロファイルを受け取った後、ホームＭＳＣ２０と同じ機能を提供するために、データベース３６（在圏ロケーションレジスタ（ＶＬＲ）という）を更新する。ＨＬＲ、ＶＬＲおよび認証局（ＡＣ：authentication center）は、ＭＳＣとコロケートされることも可能であり、リモートアクセスされることも可能である。
【０００５】
ＵＭＴＳ(Universal Mobile Telecommunications System)および３Ｇ ＩＳ−４１では、ワイヤレス装置は、呼を発信し、または、受信するとき、認証されなければ、呼設定に進むことができない。認証された後、ある秘密鍵を用いて生成された１２８ビットの完全性鍵（ＩＫ：integrity key）が有効化され、ワイヤレス装置とシステムの間で送信されるメッセージの完全性(integrity)のチェックすなわちメッセージ認証に使用されることが可能となる。
【０００６】
よいメッセージ認証方式の設計は、暗号技術の重要な分野の１つである。メッセージ認証方式の目標は、受信側が受信するメッセージに改竄があったかどうかを受信側が判断することができるように、送信側が受信側へメッセージを効率的に送信することである。図２に、ワイヤレス通信システムにおいてワイヤレス装置でどのようにメッセージ認証が実行されるかを示す。この環境には、ワイヤレス装置およびワイヤレス通信システムという二当事者が関与し、これらは秘密鍵ｋに関して合意している。使用されるアルゴリズムとして、署名アルゴリズムＳｋおよび検証アルゴリズムＶｋの２つがある。ワイヤレス装置がメッセージＭをワイヤレス通信システムへ送信したい場合、ワイヤレス装置は、まず、ＭＡＣジェネレータ５０を用いて、タグすなわちメッセージ認証コード（ＭＡＣ）μ＝Ｓｋ（Ｍ）を計算する。ワイヤレス装置は、メッセージとタグのペア（Ｍ，μ）をワイヤレス通信システムへ送信する。ワイヤレス通信システムは、ペア（Ｍ，μ）を受信すると、Ｖｋ（Ｍ，μ）を計算し、ＭＡＣが正当な場合には１を返し、そうでない場合には０を返す。図２には、ワイヤレス通信システムがメッセージおよびｋをＭＡＣジェネレータ５２に入力し、ＭＡＣジェネレータ５２がタグ’を出力し、ワイヤレス装置から受信されたタグ（μ）とシステムで生成されたタグ’の間の比較５４が行われることが示されている。これらが同一である場合、メッセージは正当であるとして受容され、そうでない場合、メッセージは拒否される。秘密鍵ｋを知らなければ、検証アルゴリズムが正当であるとして受容することになるメッセージおよび対応するＭＡＣを、敵が構成することはほとんど不可能である。
【０００７】
同じメッセージ認証方式が、ワイヤレス通信システムからワイヤレス装置へのメッセージの送信において実行される。例えば、図３に、ワイヤレス通信システムが、保護されたメッセージをどのようにしてワイヤレス装置へ送信するかを示す。まず、ワイヤレス通信システムは、メッセージおよび秘密鍵ｋを入力としてＭＡＣジェネレータ５６でタグを生成する。ワイヤレス通信システムは、メッセージをタグとともにワイヤレス装置へ送信する。ワイヤレス装置は、メッセージおよび秘密鍵ｋをＭＡＣジェネレータ５８に入力してタグ’を生成する。ワイヤレス装置は、タグ’と、ワイヤレス通信システムから受信されたタグとの間の比較６０を行う。これらのタグが一致した場合、メッセージは正当であるとして受容される。一致しない場合、メッセージは、変更された、あるいは、不正であるとして、拒否される。
【０００８】
メッセージ認証コードに対するセキュリティ要件は次のように説明することができる。ｋは秘密のまま、選択されたメッセージに対するＭＡＣ Ｓｋ，Ｖｋを問い合わせることができるときに、Ｖｋ（Ｍ＊，μ＊）＝１であるがメッセージＭ＊はＳｋへの入力となったことがないような正当なペア（Ｍ＊，μ＊）を敵が思いつくことができる場合、敵がＭＡＣを偽造している。
【０００９】
実際に広くみられるメッセージ認証への１つの一般的なアプローチは、暗号ハッシュ関数を用いるものである。ハッシュ関数は、一般に、ある長さの入力から、より短い長さの出力に写像する関数として特徴づけることができる。さらに、同じ出力に写像される２つの入力を見つけるのは困難である。暗号ハッシュ関数に基づくこれらのＭＡＣ方式が良好であるのは、高速で安全な暗号構成ブロックを使用するからである。一般に、暗号ハッシュ関数Ｆ（ｘ）は、任意の長さの入力ｘを短い出力に写像する、公開され、鍵なし（キーレス、すなわち、鍵がかけられていない）、衝突を起こしにくい（衝突耐性がある、耐衝突性）関数である。衝突を起こしにくいとは、Ｆ（ｘ１）＝Ｆ（ｘ２）であるような２つのメッセージｘ１およびｘ２を見つけるのが計算量的に実行不能であることを意味する。ＭＤ５、ＳＨＡ−１、およびＲＩＰＥ−ＭＤは、広く用いられている暗号ハッシュ関数である。耐衝突性とともに、ハッシュ関数は通常、他の目的で使用するため、および、耐衝突性の可能性を高めるために、他の性質も有するように設計される。
【００１０】
ＭＤ５やＳＨＡ−１のようなほとんどの暗号ハッシュ関数は、入力メッセージがブロックごとに処理されるという反復構成を使用する。図４に示すように、基本構成ブロックは、圧縮関数ｆと呼ばれ、これは、サイズｔおよびｂの２つの入力をとり、長さｔの、より短い出力に写像するハッシュ関数である。ＭＤ５では、サイズｔの入力は長さ１２８ビットであり、サイズｂの入力は長さ５１２ビットである。ＳＨＡ−１では、サイズｔの入力は長さ１６０ビットであり、サイズｂの入力は長さ５１２ビットである。サイズｔの入力は連鎖変数と呼ばれ、サイズｂの入力（ペイロードあるいはブロック）は、実際にメッセージｘを一度にｂビットずつ処理するために使用される。図５に示すように、この場合、ハッシュ関数Ｆ（ｘ）は、ｈｉを連鎖変数とし、ｘｉをペイロードとして、以下のステップに従って、メッセージｍに対して圧縮関数ｆを反復して作用させることによって形成される。
１．適当な手続きを用いてメッセージ長を付加し、パディングして、入力をブロックサイズｂの倍数にする。入力は、ブロックサイズの断片ｘ＝ｘ１，...，ｘｎに分解することができる。
２．ｈ０＝ＩＶ（一定）
３．Ｆｏｒ ｉ＝１ ｔｏ ｎ
４．ｈｉ＝ｆ（ｈｉ−１，ｘｉ）
５．ｈｎをＦ（ｘ）として出力する。
例えば、ＳＨＡ−１ハッシュ関数を使用する場合、ＳＨＡ−１ハッシュ関数のそれぞれへの呼出しは、１６０ビットの初期ベクトル（ＩＶ：initial vector）を有し、５１２ビットの入力（ペイロード）をとり、これが１６０ビットの出力に写像される。ＩＶは、ＳＨＡ−１ハッシュ関数に対する標準（National Institute of Standards and Technology, NIST FIPS PUB 180, "Secure Hash Standard", U. S. Department of Commerce, May 1993）で規定されたＩＶとなるように設定される。
【００１１】
暗号ハッシュ関数は、設計上、鍵なし（キーレス）である。しかし、メッセージ認証は秘密鍵の使用を必要とするため、ハッシュ関数に鍵をかける方法が必要となる。ハッシュ関数に鍵をかける１つの方法は、固定された既知のＩＶの代わりに秘密鍵を使用することである。図６に示すように、鍵ｋで、圧縮関数ｆ（連鎖変数，ｘ１）における連鎖変数を置き換えて、ｆｋ（ｘ１）＝ｆ（ｋ，ｘ１）をつくる。ただし、ｘ１のブロックサイズはｂである。反復されたハッシュ関数Ｆ（ＩＶ，ｘ）は、固定のＩＶを秘密鍵ｋで置き換えてＦｋ（ｘ）＝Ｆ（ｋ，ｘ）を形成することによって修正される。鍵がかけられた（鍵つき）関数の耐衝突性は、鍵なし関数のものとは異なる、その理由は、敵は、任意の時点に、ユーザに問い合わせることなくＦｋ（ｘ）を評価することはできないからである。この要件は、標準的な衝突要件より弱いため、関数Ｆｋ（ｘ）を「弱耐衝突性」であると呼ぶことにする。
【００１２】
鍵つき暗号ハッシュ関数の安全性を改善するため、次のように定義されるネスト化ＭＡＣ関数（ＮＭＡＣ）が開発された。
ＮＭＡＣｋ（ｘ）＝Ｆｋ１（Ｆｋ２（ｘ））
ただし、暗号ハッシュ関数Ｆは、まず、ＩＶの代わりに秘密鍵ｋ２で鍵がかけられ、メッセージｘが反復的にハッシュされてＦｋ２（ｘ）の出力となる。次に、図７に示すように、この出力Ｆｋ２（ｘ）が、Ｆのパディング方式に従って、あるブロックサイズにパディングされた後、Ｆｋ２（ｘ）の結果は秘密鍵ｋ１で鍵がかけられ、外側ハッシュ関数Ｆでハッシュされる。このように、ＮＭＡＣ鍵ｋは２つの部分ｋ＝（ｋ１，ｋ２）を有する。ＮＭＡＣの安全性を、基礎となる暗号ハッシュ関数の安全性と関連づけることに関する次の定理が、M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for Message Authentication", In Proc. CRYPTO 96, Lecture Notes in Computer Science, Springer-Verlag, 1996、に証明されている。
【００１３】
定理１： ｔ回のステップおよびｑ回の問合せで、鍵つき圧縮関数ｆがεｆ安全なＭＡＣであり、かつ、鍵つき反復ハッシュＦがεＦ弱耐衝突性であるならば、ＮＭＡＣ関数は（εｆ＋εＦ）安全なＭＡＣである。
【００１４】
このＮＭＡＣの構成は、圧縮関数への少なくとも２回の呼出しを行う。Ｆｋ２（ｘ）への内側の呼出しは、鍵なしハッシュ関数Ｆ（ｘ）と同じコストを有する。このため、Ｆｋ１への外側の呼出しは、鍵なしハッシュ関数によって要求されるものを超える追加の呼出しである。外側の関数呼出しは、基本的に、鍵つき圧縮関数ｆｋ１への呼出しである。その理由は、Ｆｋ２（ｘ）のサイズ１の出力は、圧縮関数へのサイズｂの入力にはめ込むことができるからである。多くのブロックからなる大きいｘに対しては、追加の外側圧縮呼出しのコストは重要ではない。しかし、サイズの小さいメッセージｘの場合、追加の外側圧縮関数は、鍵なしハッシュ関数に比べたとき、割合でみると、相当高い程度の非効率性を生じる。表１に、ＳＨＡ−１ハッシュ関数の場合に、小さいｘに対する非効率性を示す。基礎となるハッシュ関数によって、および、ＮＭＡＣによって必要とされる圧縮呼出しの回数が、３０バイトずつ増大するさまざまな小さいｘに対して比較されている。基礎となるハッシュ関数に対するＮＭＡＣの非効率性も表中に記載されている。
【００１５】
【表１】
表１： さまざまなサイズの短いメッセージに対する圧縮呼出し回数の比較
【００１６】
表からわかるように、小さいメッセージに対する不利益は大きくなる。特に、１ブロック内に収まるメッセージの場合、不利益は１００％である。その理由は、ＮＭＡＣでは２回の圧縮関数呼出しが要求されるのに対して、基礎となる暗号ハッシュ関数により要求されるのは１回の圧縮呼出しであるからである。
【００１７】
圧縮関数ｆにはアクセスすることができず、メッセージで暗号ハッシュ関数Ｆを呼び出すことだけができるような実装に対する、ＮＭＡＣの実用的変形がＨＭＡＣである。このような実装の場合、鍵は、連鎖変数とすることはできず、関数Ｆは、最初の圧縮関数で用いられた固定の既知のＩＶで呼び出される。ＨＭＡＣ関数は次のように定義される。
【数１】
ただし、鍵ｋが使用され、バーｋは、反復されるハッシュ関数のブロックサイズｂに達するようにｋをゼロでパディングしたものである。バーｋの値はｏｐａｄとビットごとの排他的論理和がとられ、その結果がメッセージＸに連結される、ハッシュ関数Ｆは、連結されたメッセージ全体で呼び出される。図８に示すように、圧縮関数ｆの最初の実行（イタレーション）の後、鍵ｋ２がｋ２＝ｆ（バーｋ（＋）ｉｐａｄ）として生成される。（本願の明細書および図面において、記号（＋）と、数１に現れた排他的論理和の記号（円内に＋）とは、同一の記号を表すものとする。）ハッシュ関数Ｆが完了した後、結果の値Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ）が生成される。次に、バーｋ（＋）ｏｐａｄ（すなわち、バーｋとｏｐａｄのビットごとの排他的論理和演算）の値からなるメッセージで、ハッシュ関数Ｆが再び呼び出される。ハッシュ関数Ｆの第２の呼出し内の最初の実行の後、圧縮関数ｆ（ＩＶ，バーｋ（＋）ｏｐａｄ）から鍵ｋ１が得られる。ｉｐａｄおよびｏｐａｄの値は、M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for Message Authentication", In Proc. CRYPTO 96, Lecture Notes in Computer Science, Springer-Verlag, 1996、に記載されているような固定された定数である。ハッシュ関数への第２の呼出し内の第２の実行は、圧縮関数ｆ（ｋ１，Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ））を用いて、ＨＭＡＣ関数Ｆ（バーｋ（＋）ｏｐａｄ，Ｆ（バーｋ（＋）ｉｐａｄ，Ｘ））を生成する。
【００１８】
ｋ１＝ｆ（バーｋ（＋）ｏｐａｄ）およびｋ２＝ｆ（バーｋ（＋）ｉｐａｄ）と定義することにより、ＨＭＡＣｋ（ｘ）はＮＭＡＣ（ｋ１，ｋ２）（ｘ）となる。ＨＭＡＣは、メッセージ認証のためのインターネット標準である。示されるように、ＨＭＡＣの安全性の証明は、ＮＭＡＣに関係しており、基礎となる暗号ハッシュが（弱）耐衝突性であること、および、基礎となる圧縮関数が、両方とも適切に鍵がかけられた場合には安全なＭＡＣであること、を仮定する。ＨＭＡＣは、長いメッセージに対しては効率的であるが、短いメッセージに対しては、ネスト化された構成のために相当な非効率性が生じる。圧縮関数へのアクセスが許可されない場合に１ブロックより短いメッセージのＭＡＣを生成するため、ＨＭＡＣは、圧縮関数への４回の呼出しを必要とする。圧縮関数へのアクセスが許可されている場合、ｋ１およびｋ２を事前に計算し、圧縮関数の連鎖変数に挿入することができるため、圧縮関数への呼出しは２回でよい。この非効率性は、シグナリングメッセージのメッセージ認証のようないくつかのアプリケーションでは特に大きくなることがある。その場合、個々のメッセージはすべて１個または２個のブロック内に収まるからである。ＴＣＰ／ＩＰトラフィックの場合にも、多数のパケット（例えば、確認応答(acknowledgment)）が、ほとんどの暗号ハッシュの１ブロック内に収まる４０バイト程度のサイズを有することがよく知られている。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明は、安全性の証明をも提供しながら、長短両方のメッセージがＨＭＡＣより効率的にメッセージ認証されることを可能にする改良を提案する。
【課題を解決するための手段】
【００２０】
本発明の１つの特徴によれば、メッセージ認証コード（ＭＡＣ）を生成するメッセージ認証システムは、メッセージが鍵つき圧縮関数の１入力ブロック内に収まるときにその圧縮関数の１回のみの実行を使用することにより、効率を改善する。１ブロックより大きいメッセージに対しては、このＭＡＣシステムは、ネスト化ハッシュ関数を使用する。本発明のもう１つの特徴によれば、ＭＡＣシステムおよび方法は、ネスト化ハッシュ関数への入力として、メッセージの一部を使用する。例えば、メッセージ認証システムは、メッセージを第１部分と第２部分に分割することができる。ハッシュ関数がメッセージの第１部分を入力として実行されて中間結果を得、鍵つきハッシュ関数がメッセージの第２部分および中間結果を入力として使用して実行される。こうして、内側ハッシュ関数によって処理されることを必要とするメッセージの部分を少なくすることにより、小さいメッセージの場合には特に、効率が改善される。
【図面の簡単な説明】
【００２１】
【図１】本発明の原理によるＭＡＣ生成システムを使用可能なワイヤレス通信システムの概略図である。
【図２】ワイヤレス装置からワイヤレス通信システムへ送信されるメッセージを認証するためにＭＡＣがどのように使用されるかを示す概略図である。
【図３】ワイヤレス通信システムからワイヤレス装置へ送信されるメッセージを認証するためにＭＡＣがどのように使用されるかを示す概略図である。
【図４】圧縮関数ｆのブロック図である。
【図５】与えられた圧縮関数ｆに対するハッシュ関数Ｆの反復構成を示すブロック図である。
【図６】鍵つきハッシュ関数を示すブロック図である。
【図７】ネスト化ハッシュ関数（ＮＭＡＣ）を示すブロック図である。
【図８】ＨＭＡＣとして知られるＮＭＡＣの変形を示すブロック図である。
【図９】本発明の原理によるメッセージ認証システムにおける単一ブロックの場合のブロック図である。
【図１０】本発明の原理によるメッセージ認証システムにおける多重ブロックの場合のブロック図である。
【図１１】本発明の原理によるメッセージ認証システムのＥＮＭＡＣ実施例のブロック図である。
【図１２】本発明の原理によるメッセージ認証システムのＥＮＭＡＣ実施例の流れ図である。
【図１３】本発明の原理によるメッセージ認証システムのＥＨＭＡＣ実施例のブロック図である。
【図１４】本発明の原理によるメッセージ認証システムのＳＭＡＣ実施例のブロック図である。
【図１５】本発明の原理によるメッセージ認証システムのＳＭＡＣ実施例の流れ図である。
【発明を実施するための形態】
【００２２】
任意長のメッセージを処理するための、改善された効率を提供する、本発明の原理によるＭＡＣ生成システムおよび方法の実施例について以下で説明する。以下の説明では、ハッシュ関数という用語は、圧縮関数ｆおよび反復ハッシュ関数Ｆを包含する。ハッシュ関数は、鍵なしであることも鍵つきであることも可能であり、Ｆｋは鍵つき反復ハッシュ関数を表し、ｆｋは鍵つき圧縮関数を表す。想起すべき点であるが、ｆｋ（ｘ）は、鍵つき圧縮関数であり、その入力ブロックサイズはｂビットであり、出力サイズはｔビットであり、連鎖変数のサイズ、したがって鍵サイズもまたｔビットである。本発明の１つの特徴によれば、メッセージのサイズに依存して、ＭＡＣジェネレータは、異なるハッシュ関数構成を用いてＭＡＣを生成する。例えば、ＭＡＣジェネレータは、メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数ｆの１入力ブロックに収まる場合には、ハッシュ関数として鍵つき圧縮関数の１回のみの実行を行うことが可能である。入力ブロック内に収まらないメッセージの場合、ＭＡＣジェネレータは、ネスト化ハッシュ関数を使用する。図９に示すように、メッセージｘは、必要なパディング、メッセージ長フィールド、ブロックインジケータフィールドあるいはメッセージｘに付加されるその他のフィールドとともに、圧縮関数ｆに入力される。メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数の入力ブロック内に収まる場合、メッセージｘおよび鍵ｋを用いて鍵つき圧縮関数ｆ（９０）が１回のみ実行され、メッセージｘに対するＭＡＣ ｆｋ（ｘ）が生成される。
【００２３】
これに対して、図１０に示すように、メッセージｘ（および追加的に要求されるビットがあればそれも）が圧縮関数ｆの１入力ブロック内に収まらない場合、メッセージブロックｘは、部分１および部分２のように、複数の部分に分割される。メッセージブロックの部分部分は、メッセージｘを構成するビットの重なり合うセットであることも重なり合わないセットであることも可能である。本発明のもう１つの特徴によれば、第１部分は内側ハッシュ関数Ｆで使用され、第２部分は外側ハッシュ関数（これは、圧縮関数ｆＣＶ１として示されている）で使用される。例えば、部分２は、内側ハッシュ関数Ｆに提供され、そこで、圧縮関数１００ａ〜１００ｎ（必要であれば）の呼出し（実行）が、部分２のブロックである部分２１〜部分２ｎについて（付加されたパディングあるいはフィールドがあればそれも含む）行われる（ここで、ｎ≧１である）。圧縮関数ｆの最初の実行（呼出し）１００ａは、連鎖変数ＣＶ２を使用する。連鎖変数ＣＶ２は、実施例に依存して、鍵であることも、鍵から導出された鍵であることも、ハッシュ関数Ｆの標準の初期値であることも可能である。内側ハッシュ関数ＦＣＶ２（部分２）の結果は、メッセージｘの部分１および連鎖変数ＣＶ１とともに、外側ハッシュ（圧縮）関数ｆ（１０２）に提供される。連鎖変数ＣＶ１は、実施例に依存して、鍵であることも、鍵から導出された鍵であることも、ハッシュ関数Ｆの標準の初期値ＩＶであることも可能である。その結果の値ｆＣＶ１（部分１，ＦＣＶ２（部分２））は、メッセージ認証で用いられるＭＡＣを生成するために使用されることが可能となる。
【００２４】
上記の一般的記述を用いて、従来技術のＭＡＣ生成方式よりも改善された性能を提供することができる。例えば、短いメッセージに対してＮＭＡＣよりも改善された効率を可能にするとともに、より長いメッセージに対しても多少の改善を可能にするため、以下のＭＡＣ生成法が提供される。想起すべき点であるが、ｆｋ（ｘ）は、その入力ブロックサイズがｂビットであり、出力サイズがｔビットであり、連鎖変数のサイズ、したがって鍵サイズもまたｔビットであるような圧縮関数である。図１１ａおよび図１１ｂに示すように、本発明の原理によるＭＡＣの生成の具体的実施例は次の通りである。
【数２】
ただし、第１の場合、ブロック内の最初のｂ−２ビットが、メッセージｘを入れるために使用される。メッセージｘが最初のｂ−２ビットに満たない場合、パディングが必要であり、ブロックの残りは、最終ビットが義務的に１とされることを除いては、その後には０が続く（ないこともある）。メッセージの長さがｂ−２ビットである場合、ｂ−１番目のビットが１にセットされる。この実施例では、ブロックの最終ビットが、ＥＮＭＡＣで単一圧縮呼出しが使用されているかどうかを示す。ブロックの最終ビットは、単一圧縮呼出しの場合には１にセットされ、圧縮関数ｆの多重呼出し（実行）が必要とされるときには０にセットされる。１ブロックに収まらないという第２の場合、ストリングｘは、次のような２つの部分（セグメント）ｘｐｒｅｆおよびｘｓｕｆｆに分解される。
ｘｐｒｅｆ＝ｘ１...ｘｂ−ｔ−１
ｘｓｕｆｆ＝ｘｂ−ｔ...ｘ｜ｘ｜
まず、ｘｓｕｆｆが鍵値ｋ２を用いてハッシュされ、Ｆｋ２（ｘｓｕｆｆ）のｔビットの結果が生成される。次に、外側圧縮呼出しが鍵値ｋ１を用いて実行される。ここで、最初のｂ−ｔ−１ビットにｘｐｒｅｆがセットされ、次のｔビットに結果Ｆｋ２（ｘｓｕｆｆ）がセットされ、最終ビットに０がセットされる。
【００２５】
上記のＥＮＭＡＣ生成法は、具体的に図１２を参照して以下で説明するように、基礎となる暗号ハッシュ関数としてＳＨＡ−１ハッシュ関数を使用することができる。ブロック１１０に示されているように、ＥＮＭＡＣ生成法を実現する処理回路は、ｘの長さ｜ｘ｜が５１０ビット以下であるかどうかを判断する。ｘの長さ｜ｘ｜が５１０ビット以下である場合、処理回路はステップ１１２に進み、ｘを最初の５１０ビットにロードすることによって、ｆｋ１（）の５１２ビットのペイロードを形成する。次に、ブロック１１４で、「１」をｘに付加し、ステップ１１６で、必要な個数の０（ないこともある）を用いて５１１ビットを満たす。｜ｘ｜が５１０ビットより小さい場合、１の後にゼロがパディングされるが、｜ｘ｜が５１０ビットである場合、ゼロはパディングされず、ブロック１１４では、１個の１が５１１番目のビット位置に付加されるだけである。ブロック１１８で、メッセージが単一ブロックに収まることを示すために、最後の５１２番目のビット（ブロックインジケータビット）が１にセットされる。ブロック１２０で、鍵ｋ１を１６０ビットの連鎖変数とし、メッセージｘ、パディングビットおよびブロックインジケータビットを５１２ビットのペイロード（入力ブロック）として、鍵つき圧縮関数ｆｋ１（ｘ，ｐａｄ，１）が実行される。その後、ブロック１２２で、結果ｆｋ１（ｘ，ｐａｄ，１）が出力され、ＭＡＣを生成するために使用される。
【００２６】
ブロック１１０で、メッセージｘが５１０ビットより長い場合、処理回路はブロック１２４に進み、メッセージは２つの部分ｘｐｒｅｆおよびｘｓｕｆｆに分割される。ただし、ｘｐｒｅｆ＝ｘ１...ｘ３５１およびｘｓｕｆｆ＝ｘ３５２...ｘ｜ｘ｜である。次に、ブロック１２６で、処理回路は、鍵ｋ２と、メッセージ部分ｘｓｕｆｆとを、追加のパディングビットやビットフィールドがあればそれとともにペイロードとして、鍵つきハッシュ関数Ｆｋ２を実行し、Ｆｋ２（ｘｓｕｆｆ）の１６０ビットの結果を得る。ブロック１２８で、外側圧縮関数ｆｋ１のペイロードの最初の３５１ビットにｘｐｒｅｆをセットし、ブロック１３０で、ペイロードの次の１６０ビットに、ブロック１２６で計算したＦｋ２（ｘｓｕｆｆ）の結果をセットする。ブロック１３２で、ペイロードの最後の５１２番目のビットを０にセットする。最後に、ブロック１３４で、外側鍵つき圧縮関数ｆｋ１が、ブロック１２８〜１３２で形成された５１２ビットのペイロードに適用され、ブロック１３６で、その結果ｆｋ１（ｘｐｒｅｆ，Ｆｋ２（ｘｓｕｆｆ），０）が、ＭＡＣを生成するために出力される。
【００２７】
次の表２は、３０バイトずつ増大するさまざまなサイズの短いメッセージに対して、基礎となるハッシュ関数ＳＨＡ−１によって、および、ＥＮＭＡＣによって必要とされる圧縮呼出しの個数を比較している。表２と、ふつうのＮＭＡＣの比較をした前の表１との間には重要な相違点が存在する。短いサイズの多くのものについて、ＮＭＡＣは、基礎となるハッシュ関数と同じ効率を有する。長いメッセージの場合、ＮＭＡＣ、ＥＮＭＡＣおよび基礎となるハッシュ関数の効率は互いに相当異なる。サイズが４８０ビットのメッセージの場合、表２の記載事項が意外にも示しているように、ＥＮＭＡＣは基礎となるハッシュ関数より効率がよい。この例外的なことが起こる理由は、基礎となるＳＨＡ−１関数がサイズ情報のために６４ビットを確保するのに対して、ＥＮＭＡＣは、５１０ビットより短いメッセージについては２ビットしか確保しないためである。このため、ＥＮＭＡＣを使用する結果の節約は、１ないし数ブロックに収まるメッセージについてはかなり大きい。
【００２８】
【表２】
表２： さまざまなサイズの短いメッセージに対する圧縮呼出し回数の比較
【００２９】
１ブロックに収まるメッセージのＭＡＣを生成するために異なる鍵ｋ３を使用し、より長いメッセージのＭＡＣを生成するためにＮＭＡＣを用いて鍵ｋ＝（ｋ１，ｋ２）を使用すると仮定すると、システムが安全であることを示すことができる。本質的には、これが実際に行われていることであるが、異なる鍵を用いて異なるＭＡＣを生成する代わりに、メッセージが１ブロックに収まる場合にはトレーリングビットが１にセットされ、その他の場合には０にセットされている。第２に、ＮＭＡＣは、外側圧縮呼出しのペイロードをゼロでパディングするのに対して、ＥＮＭＡＣは、メッセージの一部を外側呼出しに入れる。
【００３０】
ＥＮＭＡＣ安全性の結果は、ＮＭＡＣと同様であり、以下で、教育的目的で主張し証明する。
【００３１】
定理２： ｔ回のステップおよびｑ回の問合せで、鍵つき圧縮関数ｆがεｆ安全なＭＡＣであり、かつ、鍵つき反復ハッシュＦがεＦ弱耐衝突性であるならば、ＥＮＭＡＣ関数は（εｆ＋εＦ）安全なＭＡＣである。
【００３２】
証明： 敵ＡＥが、ｔ回のステップと、ｑ回の適応的に選択されたＥＮＭＡＣ関数への問合せとを仮定して、確率εＥでＥＮＭＡＣに対して成功したとする。この敵は、以前に問い合わせていないメッセージに関して、鍵つき圧縮関数に関連するＭＡＣを偽装する別の敵Ａｆを形成するために使用される。ＭＡＣを破るこの確率は、εＥと、εＦ、すなわち、敵が時間ｔおよびｑ回の問合せでハッシュ関数Ｆにおける衝突を見つける最良の確率、に関して限界づけられる。ＡＥを用いて、この特定の方法でＭＡＣを破る確率は、任意の方法でＭＡＣを破る確率εｆより小さくなければならない。これを用いて、εＥについての限界を得ることができる。鍵つき圧縮ＭＡＣを偽造するために用いられるアルゴリズムＡｆを次に示す。
【００３３】
ランダムなｋ２を選ぶ
Ｆｏｒ ｉ．．．ｑ
ＡＥ→ｘｉ
Ｉｆ ｘｉ＜ｂ−２
ＡＥ←ｆｋ１（ｘｉ，ｐａｄ，１）
ｅｌｓｅ
ＡＥ←ｆｋ１（１，ｘｉ，ｐｒｅｆ，Ｆｋ２（ｘｉ，ｓｕｆｆ），０）
ＡＥ→（ｘ，ｙ）
Ｉｆ ｘ＜ｂ−２
（ｘ，ｐａｄ，１），ｙ を出力
ｅｌｓｅ
（ｘｐｒｅｆ，Ｆｋ２（ｘｓｕｆｆ），０），ｙ を出力
【００３４】
εＥ＝εＥ１＋εＥ＋とおく。ここで、εＥ１は、ＥＮＭＡＣが攻撃され、ＡＥによって偽造されたＥＮＭＡＣメッセージがおよそ１ブロックサイズである（正確にいえば、ｂ−２より小さい）確率である。また、Ｅ＋およびεＥ＋はそれぞれ、ＥＮＭＡＣが攻撃され、ＡＥによって偽造されたＥＮＭＡＣメッセージが１ブロックサイズより大きい事象および確率であるとする。さらに、εＥ＋＝εＥ＋，ｐｒｅｆ≠＋εＥ＋，ｐｒｅｆ＝である。ここで、εＥ＋，ｐｒｅｆ≠は、ＥＮＭＡＣが多重ブロックメッセージで偽造され、メッセージのプレフィクスが、以前にＡＥによって問合せされたいずれのメッセージのプレフィクスとも等しくない確率である。また、εＥ＋，ｐｒｅｆ＝は、ＥＮＭＡＣが多重ブロックメッセージで偽造され、メッセージのプレフィクスが、以前にＡＥによって問合せされたいずれかのメッセージのプレフィクスに等しい確率である。この場合、偽造メッセージのサフィクスは、同じプレフィクスを有するメッセージのサフィクスとは異ならなければならない。
【００３５】
Ｐ［ｆのＭＡＣを偽造］＝Ｐ［ｆのＭＡＣがＥ１により偽造される］＋Ｐ［ｆのＭＡＣがＥ＋により偽造される］ （１）
＝εＥ１＋Ｐ［ｆのＭＡＣがＥ＋により偽造される］
＝εＥ１＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ≠により偽造される］＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される］ （２）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋Ｐ［ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される］
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋Ｐ［Ｅ＋，ｐｒｅｆ＝∩同じプレフィクスの集合内にサフィクス衝突がない］ （３）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝∪同じプレフィクスの集合内にサフィクス衝突がある］ （４）
＝εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝］−Ｐ［集合内に衝突がある］＋Ｐ［バーＥ＋，ｐｒｅｆ＝∩集合内に衝突がある］
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−Ｐ［バーＥ＋，ｐｒｅｆ＝］−Ｐ［集合内に衝突がある］ （５）
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−１＋εＥ＋，ｐｒｅｆ＝−Ｐ［ｑ個の問合せ内に衝突がある］ （６）
≧εＥ１＋εＥ＋，ｐｒｅｆ≠＋１−１＋εＥ＋，ｐｒｅｆ＝−εＦ
≧εＥ１＋εＥ＋−εＦ
≧εＥ−εＦ （７）
εｆ≧Ｐ［ＥＮＭＡＣを偽造することによりｆのＭＡＣを偽造］≧εＥ−εＦ （８）
εｆ≧εＥ−εＦ
ゆえに、εＥ≦εｆ＋εＦ （９）
【００３６】
式１は、ｆの新しいＭＡＣを偽造する確率を、単一ブロックまたは多重ブロックのいずれかの、ＥＮＭＡＣのＭＡＣを偽造することによりｆの新しいＭＡＣを偽造する確率に分解する。多重ブロックＥＮＭＡＣを破ることによりｆを破る確率は、式２において、どのプレフィクスもすべての問合せされたメッセージの他のいずれかのプレフィクスに等しくない場合と、問合せされたメッセージのうちに等しいプレフィクスがある場合とに分解される。式３では、ｆのＭＡＣがＥ＋，ｐｒｅｆ＝により偽造される確率が、Ｅ＋，ｐｒｅｆ＝が起こり、かつ、同じプレフィクスを有するメッセージのうちにサフィクスのハッシュの衝突が起こらない確率と等値される。式４は、ドモルガンの法則を用いた式３の書き換えである。式６では、同じプレフィクスを有する集合中での衝突の確率が、ｑ個のすべての問合せでの衝突の確率で置き換えられる。式９は、ＥＮＭＡＣを偽造する確率εＥが、ＭＡＣを偽造する確率εｆと、衝突を見つける確率εＦの和より小さいという、われわれの求める結果である。
【００３７】
実際には、データはバイト単位で処理されることが多いため、メッセージｘの長さが、上で指定したｂ−２ビットではなくｂ−８ビットより小さいときに、単一ブロックの場合を実行するほうが適当かもしれない。多重ブロックＥＮＭＡＣの場合、非ワード境界から開始してｘｓｕｆｆを形成すると、ｘｓｕｆｆにおける全ワードの再配置（アラインメントのしなおし）を引き起こすことがある。これは、次のように、実用的な目的のために、ビットではなくバイトサイズを用いたＥＮＭＡＣの変形を用いることにより回避することができる。
【数３】
ここで、基礎となる暗号ハッシュ関数ｆとしてＳＨＡ−１を用いた場合、
ｘｐｒｅｆ＝ｘ１...ｘ｜ｘ｜−３４４
ｘｓｕｆｆ＝ｘ｜ｘ｜−３４３...ｘ｜ｘ｜
である。６３バイト（５０４ビット）までの長さのメッセージについては、メッセージを５０４ビットにパディングするための１つの１とそれに続く０の追加的なパディングに加えて、最終バイトが、ブロックインジケータのために、すなわち「Ｘ００００００１」として予約される。ここで、１は単一ブロックメッセージを示し、Ｘは、５０４ビットのパディングなしメッセージにつづく「１」であることが可能である。５０４ビットより短いパディングなしメッセージの場合、Ｘは「０」である。５０４ビットより長いメッセージの場合、メッセージは部分ｘｐｒｅｆおよびｘｓｕｆｆに分割される。ここで、ｘｓｕｆｆの長さは４３バイト（３４４ビット）であり、ｘｐｒｅｆの長さ＝メッセージの長さ−３４４ビット、である。
【００３８】
上記の実施例に加えて、本発明の原理によるメッセージ認証システムは、入力パラメータや圧縮（ハッシュ）関数あるいはその他の演算、鍵値の省略あるいは追加を行うことや、上記のシステムの変形あるいは一部を使用することも可能である。例えば、図１３ａおよび図１３ｂは、次のような改良されたＨＭＡＣとして使用されるメッセージ認証システムの実施例を示す。
【数４】
第１の図１３ａの場合、メッセージｘは単一ブロックに収まる。これは、メッセージｘが、ｂ−１−他フィールド、より小さくなければならないことを意味する。ここで、他フィールドには、ハッシュ関数Ｆのパディングあるいは長さ付加方式によるいくつかのビットが含まれる。ｘが十分小さいと仮定すると、最初の部分がｋ（＋）ｏｐａｄで、それにｘが続き、さらにそれに１にセットされた１ビットが続くという、より長い入力が形成される。このより長いメッセージは、基礎となるハッシュ関数Ｆに入力される。Ｆの内部を見ると、まず、鍵ｋ１が、圧縮関数ｆ（ｋ（＋）ｏｐａｄ）を呼び出すことによって生成される。ここで、ｋは、適当な長さにパディングされなければならない可能性がある。その結果は、圧縮関数への次の呼出しのための連鎖変数として使用される。そのペイロードは、（ｘ，１）に、ハッシュ関数Ｆの仕様に従ってパディングあるいは長さ付加したものである。
【００３９】
図１３ｂは、メッセージｘが、必要な付加フィールドとともに、１ブロックに収まらない場合であり、この場合、ストリングｘは、２つの部分（セグメント）ｘｐｒｅｆおよびｘｓｕｆｆに分解される。ここで、
ｘｐｒｅｆ＝ｘ１...ｘｂ−ｔ−１−ｏｔｈｅｒ
ｘｓｕｆｆ＝ｘの残りの部分
である。まず、内側ハッシュ関数１３０で、鍵ｋとｉｐａｄの間のビットごとの排他的論理和を実行してｋ２を生成する。このｋ２は、入力ブロックｘｓｕｆｆ１とともに連鎖変数として使用される。ブロックｘｓｕｆｆｎが最後の圧縮関数に入力されるまで、圧縮関数ｆが、パディング、付加長フィールドあるいはその他のフィールドとともに呼び出され、Ｆ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ）のハッシュ関数の結果が生成される。ここで、ｋは、適当な長さにパディングされなければならないこともある。外側ハッシュ関数１３２では、値ＩＶを連鎖変数とし、ｋ（＋）ｏｐａｄを入力として圧縮関数１３４を呼び出すことによって、鍵ｋ１が決定される。値ｋ１は、ｘｐｒｅｆの後にＦ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ）を付加しその後にゼロを付加したものを入力とする圧縮関数１３６のための連鎖変数として使用される。その結果のＦ（ｋ（＋）ｏｐａｄ，ｘｐｒｅｆ，Ｆ（ｋ（＋）ｉｐａｄ，ｘｓｕｆｆ），０）は、ＭＡＣを提供するために使用することができる。
【００４０】
図１４ａおよび図１４ｂは、バイト単位での具体的実装例に関して以下で説明するようなＳＭＡＣシステムとして使用される、メッセージ認証システムのもう１つの実施例を示す。
【数５】
ｘｐｒｅｆ： バイトｘ１...ｘ｜ｘ｜−４３
ｘｓｕｆｆ： バイトｘ｜ｘ｜−４２...ｘ｜ｘ｜
【００４１】
他の実施例と同様、ＳＭＡＣは２つの場合からなる。すなわち、図１４ａの単一ブロック（≦６３バイト）の場合、および、図１４ｂの多重ブロック（＞６３バイト）の場合である。いずれの場合でも、ＳＨＡ関数のような鍵つき圧縮関数ｆへの呼出しが行われる。単一ブロックの場合、他の関数呼び出しは不要である。しかし、多重ブロックの場合、標準のＳＨＡ１＿ＨＡＳＨのような鍵なしハッシュ関数Ｆ（１４０）が、メッセージの最初の部分ｘｐｒｅｆに適用される。次に、そのハッシュ結果と、メッセージの残りの部分が入力すなわちペイロードブロックに入れられ、鍵つき圧縮関数ｆ（１４２）への呼出しが行われる。ＳＨＡ−１圧縮関数ｆの引数の詳細を下記の表３および表４に示す。
【００４２】
示されているように、ｓｈａ１圧縮関数の５１２番目のビットは、「単一ブロックインジケータビット」として使用され、単一ブロックの場合には１にセットされ、多重ブロックの場合には０にセットされる。この実施例ではメッセージはバイトの倍数で処理されるため、最終バイト内の残りのビットはいずれも、メッセージを処理するために使用することはできない。したがって、圧縮関数の最終（６４番目の）バイト全体が予約される。多重ブロックの場合、表４に示すように、ビット５０５〜５１１もまたゼロにセットされる。単一ブロックの場合、ビット５０６〜５１１はゼロにセットされるが、５０５番目のビットは追加のパディングビットとして使用される。その機能は、単一ブロックの場合に使用されるパディング方式について説明した後には明らかになるであろう。
【００４３】
１ブロックを部分的に満たすメッセージはパディング方法を必要とする。多重ブロックの場合は、圧縮関数を満たすためにパディング方法を必要としない。その理由は、ブロックは表４に示すように完全に満たされるからである。しかし、ＳＨＡ１＿ＨＡＳＨ関数は、ｘｐｒｅｆをハッシュするときに、その固有のパディングを使用する。単一ブロックの場合にメッセージをパディングするため、１個の１をメッセージに付加した後、ブロック内の残りのビット数が満たされるまで（より正確には、５０５番目のビットが満たされるまで）の個数のゼロ（ないこともある）を付加する。例として、単一ブロックメッセージの長さが６３バイトすなわち５０４ビットである特殊な場合には、１個の１が５０５番目のビットに付加される。残りのビット５０６〜５１２は前述のように満たされる。
【００４４】
多重ブロックの場合、ハッシュ関数Ｆ（１４０）は、ブロックｘｐｒｅｆ１〜ｘｐｒｅｆｎにおいては、メッセージの最後の４３バイト以外のすべてのバイトに適用され、２０バイトのダイジェストを出力する。最後の４３バイトは、圧縮関数ｆ（１４２）によって処理されるようにするため、ハッシュ関数Ｆでは処理されない。４３バイトである理由は、表４に示すように、利用可能な６４バイトのうち、最初の２０バイトはダイジェストとして使用され、最終バイトは、ＳＨＡ−１ハッシュ関数およびＳＨＡ−１圧縮関数のために特別に予約されるからである。
【００４５】
【表３】
表３： 単一ブロックの場合： ｓｈａ１圧縮関数の引数
【００４６】
【表４】
表４： 多重ブロックの場合： ｓｈａ１圧縮関数の引数
【００４７】
図１５に、ＳＭＡＣ関数の流れ図を示す。最初に、ステップ１４８で、鍵がＩＶとＸＯＲされ、ｓｈａ１圧縮関数の連鎖変数にロードされる。ブロック１５０で、処理回路は、｜ｘ｜＞６３バイトであるかどうかを判断する。｜ｘ｜＞６３バイトでない場合、処理回路は単一ブロックの場合に進み、ブロック１５２で、メッセージｘが圧縮関数ｆの５１２ビットブロックの左側にロードされる。ブロック１５４で、処理回路は、次のビットに「１」を付加する。ブロック１５６で、最後の５１２番目のビットまで、ブロックの残りの部分がゼロで満たされる。ブロック１５８で、最後の５１２番目のビットは１にセットされる。ブロック１６０で、連鎖変数（Ｋ ＸＯＲ ＩＶ）と、ブロック１５２〜１５８からのペイロードとを用いて圧縮関数ｆが呼び出される。ブロック１６２で、２０バイトのＭＡＣが返される。
【００４８】
ブロック１５０で、｜ｘ｜＞６３バイトである場合、処理回路は多重ブロックの場合に進む。ブロック１６４で、メッセージｘは２つの断片、すなわち、ｘｐｒｅｆ：バイトｘ１...ｘ｜ｘ｜−４３と、ｘｓｕｆｆ：バイトｘ｜ｘ｜−４２...ｘ｜ｘ｜、に分割される。ブロック１６６で、ＳＨＡ１＿ＨＡＳＨ関数がｘｐｒｅｆで呼び出され、２０バイトの結果が生成される。ブロック１６８で、この２０バイトの結果が、ｓｈａ１圧縮関数の６４バイトブロックの左側にロードされ、ｘｓｕｆｆがバイト２１〜６３に付加される。ブロック１７０で、最後の６４番目のバイトが０にセットされる。最後に、ブロック１７２で、最初に計算された連鎖変数（Ｋ ＸＯＲ ＩＶ）と、ブロック１６８および１７０からのペイロードとを用いて、ｓｈａ１圧縮関数が呼び出される。ブロック１６２で、２０バイトのＭＡＣが返される。
【００４９】
ＳＭＡＣはＨＭＡＣよりもＮＭＡＣに近いため、ＳＭＡＣをＨＭＡＣではなくＮＭＡＣと比較することにする。ＮＭＡＣは、ハッシュ関数Ｆへの内側呼出しと、圧縮関数ｆへの外側呼出しを有する。ＳＭＡＣは、６３バイトより長いメッセージに対しては同じことを行うが、それより短いメッセージに対してはハッシュ呼出しをスキップする。長いメッセージの場合、ＳＭＡＣは、メッセージの一部を外側圧縮呼出しで処理するため、内側ハッシュ関数呼び出しにより処理されるテキストが少なくなる。ＮＭＡＣはこれを行わないが、代わりに、外側圧縮呼出しのペイロードの残りをゼロで満たす。ＮＭＡＣでは、内側ハッシュ関数は鍵つきであるのに対して、ＳＭＡＣは、内側呼出しに鍵をかけない。ＳＭＡＣの内側呼出しに鍵をかけることも可能であるが、効率性の目的のために、本実施例ではそのようにしなかった。その安全性は基本的に影響を受けない。その理由は、鍵なしＳＨＡ１＿ＨＡＳＨ関数であっても衝突を見つけるのは実行不可能であると考えられているからである。
【００５０】
以下は、ＳＭＡＣを実装するために使用可能なコードである。
【００５１】
内側格納データへの出力：
MAC 32 bits
/* smacは次の関数を呼び出す */
sha1_comp(unsigned char cv[20], unsigned char temp[64], unsigned char adigest[20])
{ /* sha1_compはｓｈａ１圧縮関数であり、cvは１６０ビットの連鎖変数であり、tempは５１２ビットのペイロードであり、結果は１６０ビットのadigestに出力される */
...
}
SHA1_HASH(unsigned char *M, int textlen, unsigned char adigest[20])
{ /* SHA1_HASHはハッシュ関数であり、Mはメッセージであり、textlenはメッセージ内のバイト数であり、結果は１６０ビットのadigestに出力される */
...
}
smac(int keylen, unsigned char *K, int textlen, unsigned char *M, unsigned char mac[20])
{ int i, j;
unsigned char cv[20], temp[64];
/* ２０バイトの連鎖変数cvをｆｉｐｓ１８０で定義されるようにセット */
cv[0]=0x67; cv[1]=0x45; cv[2]=0x23; cv[3]=0x01; cv[4]=0xef;
cv[5]=0xcd; cv[6]=0xab; cv[7]=0x89; cv[8]=0x98; cv[9]=0xba;
cv[10]=0xdc; cv[11]=0xfe; cv[12]=0x10; cv[13]=0x32; cv[14]=0x54;
cv[15]=0x76; cv[16]=0xc3; cv[17]=0xd2; cv[18]=0xe1; cv[19]=0xf0;
/* 鍵を連鎖変数とＸＯＲする */
for(i=0; i<keylen; i++)
cv[i] = cv[i] ^ K[i];
/* temp圧縮ブロックをオールゼロにセット */
for(i=0; i<64; i++) temp[i] = 0;
if ( textlen <= 63 ) {
/* メッセージを最も左側にロード */
for(i=0; i<textlen; i++)
temp[i] = M[i];
temp[i] = 0x80; /* '1'を付加。残りのビットは事前に０にセットされる */
temp[63] = temp[63] | 0x01; /* ５１２番目のビットを'1'にセット */
sha1_comp(cv, temp, mac);
}
else { /* textlen > 63 */
/* Mのプレフィクスに対するSHA1_HASH */
SHA1_HASH(M, textlen-43, mac);
for(i=0; i<20; i++)
temp[i] = mac[i]; /* ダイジェストを最も左側にコピー */
for(i=20; i<63; i++)
temp[i] = M[textlen-43+(i-20)]; /* 次にMのサフィクスをコピー */
temp[63] = 0x00; /* 最終バイトをゼロにセット */
sha1_comp(cv, temp, mac);
}
}
【００５２】
以上、ＭＡＣシステムについて、ＳＨＡ−１のような特定のハッシュ（圧縮）関数とともに使用されるものとして説明したが、他のハッシュ関数や関連する暗号関数、また、別のあるいは追加の関数を使用することも可能である。さらに、メッセージ、ペイロード、連鎖変数および鍵値について、特定のビットあるいはバイトが記載されているが、実施例に依存して、これらの数は変更可能である。さらに、鍵値は、鍵またはその一部から導出された鍵であることも可能である。理解されるべき点であるが、さまざまな値、入力およびアーキテクチャブロックについて、異なる記法、用語および特徴づけを使用することも可能である。例えば、圧縮関数ｆという用語が使用され、ハッシュ関数Ｆという用語が使用され、反復ハッシュ関数Ｆは、圧縮関数ｆの反復（連鎖）を用いて構成されている。理解されるべき点であるが、圧縮関数はハッシュ関数でもある。
【００５３】
代替実施例では、メッセージ認証システムについて記載された関数は、ホーム認証センタ、ホームロケーションレジスタ（ＨＬＲ）、ホームＭＳＣ、在圏認証センタ、在圏ロケーションレジスタ（ＶＬＲ）あるいは在圏ＭＳＣにある処理回路で実行されることが可能である。さらに、メッセージ認証センタおよびその各部分は、ワイヤレス装置、基地局、基地局コントローラ、ＭＳＣ、ＶＬＲ、ＨＬＲあるいはその他のワイヤレス通信システムのサブシステムで実行されることが可能である。実施例に依存して、ＭＡＣは、メッセージとともに送信されることが可能であり、その場合、ＭＡＣは、受信端で生成されたＭＡＣと比較・検証される。ＭＡＣがメッセージとともに送信される前に、追加機能がＭＡＣを変更あるいは変換することが可能であり、その場合、同じ機能が、比較・検証（メッセージ認証）のために、受信端で生成されるＭＡＣに対して実行されることが可能である。最後に、ＭＡＣが送信され、追加機能が、受信されたＭＡＣと受信端で生成されたＭＡＣを変更あるいは変換してメッセージ認証を実行することも可能である。追加機能の一例は、メッセージ認証を実行する際の比較・検証機能のために、ＭＡＣの下位３２ビットを使用するものである。こうして、ＭＡＣ、あるいは、変更または変換されたＭＡＣは、ＭＡＣまたはタグと呼ぶことが可能である。
【００５４】
さらに、上記では、メッセージ認証システムはワイヤレス通信システムに関連して説明されているが、メッセージ認証システムは、送信側から受信側へ任意のネットワークあるいは通信媒体を通じて送信される通信メッセージを認証（その完全性を検証）するために使用可能である。
【００５５】
[発明の効果]
以上述べたごとく、本発明によれば、長短両方のメッセージがＨＭＡＣより効率的にメッセージ認証されることが可能となる。
【００５６】
特許請求の範囲の発明の要件の後に括弧で記載した番号がある場合は、本発明の一実施例の対応関係を示すものであって、本発明の範囲を限定するものと解釈すべきではない。
【符号の説明】
【００５７】
１２ ワイヤレス装置
１４，１６ 地理的領域（地理的エリア）
２０，２４ 移動通信交換局（ＭＳＣ）
２２，２６ 基地局
２５ ワイヤライン装置
２８ 公衆交換電話網（ＰＳＴＮ）
２９ パケットデータネットワーク（ＰＤＮ）
３２ シグナリングネットワーク（信号網）
３４ ホームロケーションレジスタ（ＨＬＲ）
３６ 在圏ロケーションレジスタ（ＶＬＲ）
５０，５２，５６，５８ ＭＡＣジェネレータ
９０ 鍵つき圧縮関数ｆ
１０２ 外側ハッシュ（圧縮）関数ｆ
１３０ 内側ハッシュ関数
１３２ 外側ハッシュ関数
１３４，１３６ 圧縮関数
１４０ 鍵なしハッシュ関数Ｆ
１４２ 鍵つき圧縮関数ｆ
【特許請求の範囲】
【請求項１】
ワイヤレス装置とワイヤレス通信システムが呼を設定する際、
前記ワイヤレス装置内のメッセージ認証コード（ＭＡＣ）ジェネレータが、前記ワイヤレス通信システムへ送信すべきメッセージからワイヤレス装置のＭＡＣを生成し、それを前記メッセージとともに前記ワイヤレス通信システムへ送信し、
前記ワイヤレス通信システム内のＭＡＣジェネレータが送信されてきたメッセージからワイヤレス通信システムのＭＡＣを生成し、それら両方のＭＡＣが同一であることを照合した後に呼を設定するシステムにおいて、
各々のＭＡＣジェネレータがＭＡＣを生成する方法は、
前記メッセージが圧縮関数の１入力ブロック内に収まるときに、第１の鍵および前記メッセージを入力として使用して、前記圧縮関数を一度実行するステップと、
前記メッセージが前記圧縮関数の１入力ブロック内に収まらないときに、前記メッセージを処理するために、第２の鍵を使用する鍵つきハッシュ関数内にネストされたハッシュ関数を使用するステップと、
前記圧縮関数の結果を用いてＭＡＣを生成するステップとを含むことを特徴とする方法。
【請求項２】
前記使用するステップは、
前記メッセージの第１部分および第２部分を提供するステップと、
前記第１部分を入力として使用して前記ハッシュ関数を実行して結果を得るステップと、
前記第２部分および前記結果を入力として使用して前記鍵つきハッシュ関数を実行するステップとを有することを特徴とする請求項１記載の方法。
【請求項３】
前記ハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであり、前記鍵つきハッシュ関数は鍵つき圧縮関数ｆであることを特徴とする請求項２記載の方法。
【請求項４】
前記ハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであり、前記鍵つきハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであることを特徴とする請求項２記載の方法。
【請求項５】
前記圧縮関数の結果を用いてメッセージ認証コードを生成するステップと、
前記メッセージ認証コードを用いて前記メッセージを認証するために、前記メッセージとともに前記メッセージ認証コードを送信するステップとをさらに有することを特徴とする請求項１記載の方法。
【請求項６】
前記圧縮関数の結果を用いてメッセージ認証コードを生成するステップと、
前記メッセージ認証コードを、前記メッセージとともに受信された受信メッセージ認証コードと比較するステップとをさらに有し、
前記メッセージ認証コードと前記受信メッセージ認証コードが一致した場合に前記メッセージは真正であることを特徴とする請求項１記載の方法。
【請求項７】
メディア・アクセス制御（ＭＡＣ）ジェネレータにおいて認証のためにメッセージを処理する方法において、
前記メッセージの第１部分および第２部分を用意するステップと、
結果を得るために、前記第１部分を入力として使用してハッシュ関数を実行するステップと、
前記第２部分および前記結果を入力として使用して鍵つきハッシュ関数を実行するステップと、
前記メッセージが圧縮関数の１入力ブロック内に収まるかどうかを判断するステップと、
前記メッセージが圧縮関数の１入力ブロック内に収まらないときに、前記用意するステップ、前記ハッシュ関数を実行するステップおよび前記鍵つきハッシュ関数を実行するステップを実行するステップとを有することを特徴とする方法。
【請求項８】
メディア・アクセス制御（ＭＡＣ）ジェネレータ内に実装されるメッセージ認証システムであって、
メッセージが圧縮関数の１入力ブロック内に収まるときに、第１の鍵および前記メッセージを入力として使用して、前記圧縮関数を一度実行し、前記メッセージが前記圧縮関数の１入力ブロック内に収まらないときに、前記メッセージを処理するために、第２の鍵を使用する鍵つきハッシュ関数内にネストされたハッシュ関数を使用するように構成された処理回路を有することを特徴とするメッセージ認証システム。
【請求項１】
ワイヤレス装置とワイヤレス通信システムが呼を設定する際、
前記ワイヤレス装置内のメッセージ認証コード（ＭＡＣ）ジェネレータが、前記ワイヤレス通信システムへ送信すべきメッセージからワイヤレス装置のＭＡＣを生成し、それを前記メッセージとともに前記ワイヤレス通信システムへ送信し、
前記ワイヤレス通信システム内のＭＡＣジェネレータが送信されてきたメッセージからワイヤレス通信システムのＭＡＣを生成し、それら両方のＭＡＣが同一であることを照合した後に呼を設定するシステムにおいて、
各々のＭＡＣジェネレータがＭＡＣを生成する方法は、
前記メッセージが圧縮関数の１入力ブロック内に収まるときに、第１の鍵および前記メッセージを入力として使用して、前記圧縮関数を一度実行するステップと、
前記メッセージが前記圧縮関数の１入力ブロック内に収まらないときに、前記メッセージを処理するために、第２の鍵を使用する鍵つきハッシュ関数内にネストされたハッシュ関数を使用するステップと、
前記圧縮関数の結果を用いてＭＡＣを生成するステップとを含むことを特徴とする方法。
【請求項２】
前記使用するステップは、
前記メッセージの第１部分および第２部分を提供するステップと、
前記第１部分を入力として使用して前記ハッシュ関数を実行して結果を得るステップと、
前記第２部分および前記結果を入力として使用して前記鍵つきハッシュ関数を実行するステップとを有することを特徴とする請求項１記載の方法。
【請求項３】
前記ハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであり、前記鍵つきハッシュ関数は鍵つき圧縮関数ｆであることを特徴とする請求項２記載の方法。
【請求項４】
前記ハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであり、前記鍵つきハッシュ関数は圧縮関数の連鎖を用いて構成される反復ハッシュ関数Ｆであることを特徴とする請求項２記載の方法。
【請求項５】
前記圧縮関数の結果を用いてメッセージ認証コードを生成するステップと、
前記メッセージ認証コードを用いて前記メッセージを認証するために、前記メッセージとともに前記メッセージ認証コードを送信するステップとをさらに有することを特徴とする請求項１記載の方法。
【請求項６】
前記圧縮関数の結果を用いてメッセージ認証コードを生成するステップと、
前記メッセージ認証コードを、前記メッセージとともに受信された受信メッセージ認証コードと比較するステップとをさらに有し、
前記メッセージ認証コードと前記受信メッセージ認証コードが一致した場合に前記メッセージは真正であることを特徴とする請求項１記載の方法。
【請求項７】
メディア・アクセス制御（ＭＡＣ）ジェネレータにおいて認証のためにメッセージを処理する方法において、
前記メッセージの第１部分および第２部分を用意するステップと、
結果を得るために、前記第１部分を入力として使用してハッシュ関数を実行するステップと、
前記第２部分および前記結果を入力として使用して鍵つきハッシュ関数を実行するステップと、
前記メッセージが圧縮関数の１入力ブロック内に収まるかどうかを判断するステップと、
前記メッセージが圧縮関数の１入力ブロック内に収まらないときに、前記用意するステップ、前記ハッシュ関数を実行するステップおよび前記鍵つきハッシュ関数を実行するステップを実行するステップとを有することを特徴とする方法。
【請求項８】
メディア・アクセス制御（ＭＡＣ）ジェネレータ内に実装されるメッセージ認証システムであって、
メッセージが圧縮関数の１入力ブロック内に収まるときに、第１の鍵および前記メッセージを入力として使用して、前記圧縮関数を一度実行し、前記メッセージが前記圧縮関数の１入力ブロック内に収まらないときに、前記メッセージを処理するために、第２の鍵を使用する鍵つきハッシュ関数内にネストされたハッシュ関数を使用するように構成された処理回路を有することを特徴とするメッセージ認証システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００９−１５９６１８（Ｐ２００９−１５９６１８Ａ）
【公開日】平成２１年７月１６日（２００９．７．１６）
【国際特許分類】
【出願番号】特願２００９−２３６３７（Ｐ２００９−２３６３７）
【出願日】平成２１年２月４日（２００９．２．４）
【分割の表示】特願２００２−１３６１２０（Ｐ２００２−１３６１２０）の分割
【原出願日】平成１４年５月１０日（２００２．５．１０）
【出願人】（５９６０９２６９８）アルカテル−ルーセント ユーエスエー インコーポレーテッド (965)
【Ｆターム（参考）】
【公開日】平成２１年７月１６日（２００９．７．１６）
【国際特許分類】
【出願日】平成２１年２月４日（２００９．２．４）
【分割の表示】特願２００２−１３６１２０（Ｐ２００２−１３６１２０）の分割
【原出願日】平成１４年５月１０日（２００２．５．１０）
【出願人】（５９６０９２６９８）アルカテル−ルーセント ユーエスエー インコーポレーテッド (965)
【Ｆターム（参考）】
[ Back to top ]