(57)【要約】【課題】  マルチホップ通信環境下で、メッセージ送信装置へのなりすましに対する耐性を高くする。  【解決手段】  メッセージ送信装置がメッセージ受信装置によるメッセージの受信を確認し、メッセージ受信装置が受信したメッセージが正しいメッセージであることを認証するメッセージ認証システムに関する。メッセージ送信装置は、メッセージを生成するメッセージ生成手段と、メッセージを送信するメッセージ送信手段と、メッセージ受信装置がメッセージを受信したことを確認する受信確認手段と、自身の認証情報を管理する認証情報管理手段と、自身の認証情報を公開する認証情報公開手段とを有する。メッセージ受信装置は、メッセージを保持するメッセージ保持手段と、メッセージの受信確認を返す受信確認返信手段と、メッセージ送信装置の認証情報を検証する認証情報検証手段と、メッセージを認証するメッセージ認証手段と有する。【選択図】      図１
2006157856.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップ通信環境下で、メッセージ送信装置がメッセージ受信装置に対してメッセージの受信を確認し、メッセージ受信装置が、受信したメッセージがメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証方法であって、
メッセージ送信装置がメッセージ受信装置に対してメッセージの受信を確認する第１の工程と、
メッセージ送信装置が上記メッセージをメッセージ受信装置に認証させるための情報を公開する第２の工程と、
メッセージ受信装置が上記認証させるための情報を検証する第３の工程と、
メッセージ受信装置が上記メッセージを認証する第４の工程と
を含むことを特徴とするメッセージ認証方法。
【請求項２】
上記第１の工程は、
メッセージ送信装置がメッセージを送信する第１のサブ工程と、
メッセージ受信装置がメッセージの受信証明情報を生成する第２のサブ工程と、
メッセージ受信装置が、メッセージの受信証明情報を利用してメッセージの受信確認情報を生成する第３のサブ工程と、
メッセージ受信装置がメッセージの受信確認情報を受信確認情報検証装置に送る第４のサブ工程と、
受信確認情報検証装置が受信した受信確認情報を検証する第５のサブ工程と、
メッセージ送信装置が、上記第５の工程による検証結果に基づいて、メッセージ受信装置に対するメッセージの受信確認を得る第６のサブ工程とを含む
ことを特徴とする請求項１に記載のメッセージ認証方法。
【請求項３】
メッセージ送信装置がメッセージをメッセージ受信装置に認証させるための情報は、任意の値に一方向性関数を複数回施して生成した認証鍵連鎖の値であることを特徴とする請求項１又は２に記載のメッセージ認証方法。
【請求項４】
上記第２の工程は、上記認証鍵連鎖の値を生成した順と逆順に公開することを特徴とする請求項３に記載のメッセージ認証方法。
【請求項５】
上記第１の工程において、メッセージの受信が確認できたメッセージ受信装置と、メッセージの受信が確認できなかったメッセージ受信装置を把握してから、上記第２の工程を実行することを特徴とする請求項１〜４のいずれかに記載のメッセージ認証方法。
【請求項６】
上記第３の工程は、メッセージ受信装置が一つ前に受信した上記認証させるための情報を保持しておくサブ工程を含み、現在受信した認証させるための情報に所定の関数変換を施した結果が、保持する情報と一致したときに、現在受信した認証させるための情報に対し、検証成功とみなすことを特徴とする請求項１〜５のいずれかに記載のメッセージ認証方法。
【請求項７】
上記第４の工程は、上記第３の工程の検証結果が成功により上記メッセージを認証することを特徴とする請求項１〜６のいずれかに記載のメッセージ認証方法。
【請求項８】
メッセージ送信装置がメッセージの送信証明情報を生成してメッセージに付加する第５の工程をさらに有することを特徴とする請求項１〜６のいずれかに記載のメッセージ認証方法。
【請求項９】
上記第５の工程は、ネットワーク内に未公開の上記認証させるための情報、若しくは、上記認証させるための情報から派生した情報を、メッセージ送信装置の認証鍵として、メッセージの送信証明情報を生成することを特徴とする請求項８に記載のメッセージ認証方法。
【請求項１０】
上記認証させるための情報から派生した情報は、上記認証させるための情報に対して、所定の一方向性関数を１回以上施した出力値であることを特徴とする請求項９に記載のメッセージ認証方法。
【請求項１１】
上記メッセージの送信証明情報は、メッセージ送信装置の認証鍵を使用した、メッセージに対するＭＡＣであることを特徴とする請求項８〜１０のいずれかに記載のメッセージ認証方法。
【請求項１２】
上記第４の工程は、上記メッセージ送信装置の認証鍵を用いてメッセージに対するＭＡＣを生成し、上記メッセージと共に受信したＭＡＣと一致することで認証することを特徴とする請求項１１に記載のメッセージ認証方法。
【請求項１３】
上記第４の工程は、上記第３の工程にて検証が成功することにより、上記認証させるための情報、若しくは、その情報から派生する情報をメッセージ送信装置の認証鍵とみなすことを特徴とする請求項９〜１２のいずれかに記載のメッセージ認証方法。
【請求項１４】
上記第５の工程と、上記第１の工程とを複数回繰り返すことを特徴とする請求項６〜１３のいずれかに記載のメッセージ認証方法。
【請求項１５】
上記第４の工程で認証する上記メッセージは、メッセージ送信装置が過去に送信したメッセージであるが、上記第５の工程で生成するメッセージの送信証明情報は、上記過去に送信したメッセージとは異なることを特徴とする請求項１４に記載のメッセージ認証方法。
【請求項１６】
上記第４の工程は、複数のメッセージを受信したとき、受信した順番に検証し、いずれかのメッセージの認証が成功すると、それ以降のメッセージを認証しないことを特徴とする請求項１４又は１５に記載のメッセージ認証方法。
【請求項１７】
上記第４の工程は、複数のメッセージを受信したとき、受信した順番に検証し、所定数のメッセージのみ認証することを特徴とする請求項１４又は１５に記載のメッセージ認証方法。
【請求項１８】
上記第５の工程と、上記第１の工程とを複数のメッセージに対して並行して実行することを特徴とする請求項１４〜１７のいずれかに記載のメッセージ認証方法。
【請求項１９】
上記第５の工程は、１つ又は複数のメッセージに対して１つの上記メッセージ送信装置の認証鍵を用いることを特徴とする請求項１８に記載のメッセージ認証方法。
【請求項２０】
上記複数のメッセージは、メッセージ毎にメッセージの識別情報を含むことを特徴とする請求項１７〜１９のいずれかに記載のメッセージ認証方法。
【請求項２１】
上記第１の工程内の上記第３のサブ工程は、上記受信確認情報に、さらに受信確認情報を生成したメッセージの識別情報を付加することを特徴とする請求項１７〜２０のいずれかに記載のメッセージ認証方法。
【請求項２２】
上記第１の工程内の上記第３のサブ工程は、他のメッセージ受信装置から与えられた受信確認情報に付加されている上記メッセージの識別情報に対応するメッセージに対して、受信確認情報を生成することを特徴とする方請求項２０又は２１に記載のメッセージ認証法。
【請求項２３】
上記第１の工程内の上記第５のサブ工程は、与えられた受信確認情報に付加されている上記メッセージの識別情報に対応するメッセージに対して受信確認情報の検証を実行することを特徴とする請求項２１又は２２に記載のメッセージ認証方法。
【請求項２４】
上記第２の工程は、複数の全メッセージに対して、メッセージの受信が確認できたメッセージ受信装置と、メッセージの受信が確認できなかったメッセージ受信装置を把握してから実行することを特徴とする方請求項１８〜２３のいずれかに記載のメッセージ認証法。
【請求項２５】
メッセージ送信装置がメッセージをメッセージ受信装置に認証させるための情報は、任意の値に一方向性関数を複数回施して生成した認証鍵連鎖の値であり、上記第２の工程は、上記認証鍵連鎖の値を生成した順と逆順に所定数毎に公開することを特徴とする請求項１８〜２４のいずれかに記載のメッセージ認証方法。
【請求項２６】
上記第３の工程は、メッセージ受信装置が一つ前に受信した上記認証させるための情報を保持しており、現在受信した認証させるための情報に一方向性関数を所定回数施した結果が、保持する情報と一致することで成功とみなすことを特徴とする請求項２５に記載のメッセージ認証方法。
【請求項２７】
上記第４の工程は、上記第３の工程にて検証が成功することにより、上記認証させるための情報、及び、認証鍵連鎖において上記認証させるための情報と上記保持する情報との間に存在する全ての認証鍵連鎖の鍵、又は、それら情報から派生する情報をメッセージ送信装置の認証鍵とみなすことを特徴とする請求項２５又は２６に記載のメッセージ認証方法。
【請求項２８】
上記第４の工程は、複数の上記認証鍵が存在する場合に、１つの認証鍵につき、１つ又は複数のメッセージを認証することを特徴とする請求項１９に記載のメッセージ認証方法。
【請求項２９】
メッセージを送信する上記第１の工程内の上記第１のサブ工程と、認証させるための情報を公開する上記第２の工程とを同時に行うことを特徴とする請求項３〜２８のいずれかに記載のメッセージ認証方法。
【請求項３０】
上記第３の工程は、認証させるための情報の検証が成功しないときに、受信した認証させるための情報を含め受信した全ての情報を破棄することを特徴とする請求項１〜２９のいずれかに記載のメッセージ認証方法。
【請求項３１】
マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムにおける、メッセージ送信装置が該当する通信端末装置であって、
メッセージを生成するメッセージ生成手段と、
メッセージを送信するメッセージ送信手段と、
メッセージ受信装置がメッセージを受信したことを確認する受信確認手段と、
自身の認証情報を管理する認証情報管理手段と、
自身の認証情報を公開する認証情報公開手段と
を有することを特徴とする通信端末装置。
【請求項３２】
上記受信確認手段は、
メッセージ受信装置の情報を管理する第１のサブ手段と、
受信確認情報を受信する第２のサブ手段と、
受信した受信確認情報を検証する第３のサブ手段とを有する
ことを特徴とする請求項３１に記載の通信端末装置。
【請求項３３】
上記受信確認手段は、メッセージ受信装置の情報を管理する手段と、受信確認情報を受信する手段と、受信した受信確認情報を検証する手段とを有する外部装置から、メッセージ受信装置がメッセージを受信したことの情報を得ることを特徴とする請求項３１に記載の通信端末装置。
【請求項３４】
上記認証情報管理手段は、初期値に一方向性関数を複数回施した全演算結果を、生成した順番と共に管理することを特徴とする請求項３１〜３３のいずれかに記載の通信端末装置。
【請求項３５】
上記認証情報管理手段は、上記演算結果を得る算出構成を有することを特徴とする請求項３４に記載の通信端末装置。
【請求項３６】
上記認証情報公開手段は、上記認証情報管理手段が管理する一方向性関数の出力値を、生成した順と逆順でメッセージ受信装置に公開することを特徴とする請求項３４又は３５に記載の通信端末装置。
【請求項３７】
上記認証情報公開手段は、上記認証情報管理手段が管理する一方向性関数の出力値を、生成した順と逆順で所定数おきにメッセージ受信装置に公開することを特徴とする請求項３６に記載の通信端末装置。
【請求項３８】
メッセージの送信証明情報を生成してメッセージに付加する送信証明情報生成・付加手段をさらに有することを特徴とする請求項３１〜３７のいずれかに記載の通信端末装置。
【請求項３９】
上記送信証明情報生成・付加手段は、上記認証情報公開手段によって、未公開で、次に公開することが決定している上記認証情報管理手段で管理する認証情報、若しくは、その認証情報から派生する情報を自身の認証鍵として用いることを特徴とする請求項３８に記載の通信端末装置。
【請求項４０】
上記送信証明情報生成・付加手段は、上記自身の認証鍵を用いて、メッセージのＭＡＣを生成し、そのＭＡＣをメッセージに付加することを特徴とする請求項３８又は３９に記載の通信端末装置。
【請求項４１】
上記送信証明情報生成・付加手段は、１つ又は複数のメッセージに対して、１つの上記自身の認証鍵を用いることを特徴とする請求項３８〜４０のいずれかに記載の通信端末装置。
【請求項４２】
送信したメッセージを再送する再送手段をさらに有することを特徴とする請求項３１〜４１のいずれかに記載の通信端末装置。
【請求項４３】
上記再送手段は、メッセージの再送にあたり、過去に送信したメッセージの送信証明情報と、上記送信証明情報生成・付加手段にて生成するメッセージの送信証明情報が同じにならないように、再送するメッセージに処理を加えることを特徴とする請求項４２に記載の通信端末装置。
【請求項４４】
上記メッセージ生成手段は、メッセージと共にメッセージの識別情報を生成することを特徴とする請求項３１〜４３のいずれかに記載の通信端末装置。
【請求項４５】
上記再送手段は、メッセージの識別情報で指定されるメッセージに対して実行することを特徴とする請求項４４に記載の通信端末装置。
【請求項４６】
上記受信確認手段は、受信した受信確認情報の検証を、メッセージの識別情報で指定されるメッセージに対して実行することを特徴とする請求項４４又は４５に記載の通信端末装置。
【請求項４７】
上記認証情報公開手段は、上記メッセージ送信手段と同時に処理を実行することを特徴とする請求項３１〜４６のいずれかに記載の通信端末装置。
【請求項４８】
マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムにおける、メッセージ受信装置が該当する通信端末装置であって、
メッセージを保持するメッセージ保持手段と、
メッセージの受信確認を返す受信確認返信手段と、
メッセージ送信装置の認証情報を検証する認証情報検証手段と、
メッセージを認証するメッセージ認証手段と
を有することを特徴とする通信端末装置。
【請求項４９】
上記受信確認返信手段は、
メッセージを受信する第１のサブ手段と、
メッセージの受信証明情報を生成する第２のサブ手段と、
隣接する通信端末装置の情報を管理する第３のサブ手段と、
メッセージの受信確認情報を生成する第４のサブ手段と、
受信確認情報を送信する第５のサブ信手段とを有する
ことを特徴とする請求項４８に記載の通信端末装置。
【請求項５０】
上記認証情報検証手段は、メッセージ送信装置が公開した認証情報を保持することを特徴とする請求項４８又は４９に記載の通信端末装置。
【請求項５１】
上記認証情報検証手段は、与えられた情報に一方向性関数を施した出力値が、保持する情報と一致することで、与えられた情報をメッセージ送信装置の認証情報であると判断することを特徴とする請求項５０に記載の通信端末装置。
【請求項５２】
上記メッセージ認証手段は、上記認証情報検証手段が、メッセージ送信装置が公開した認証情報を検証できたことにより、上記メッセージ保持手段にて保持するメッセージをメッセージ送信装置からの正しいメッセージであると認証することを特徴とする請求項４８〜５１のいずれかに記載の通信端末装置。
【請求項５３】
上記メッセージ保持手段は、１つ又は複数のメッセージを受信した順に管理・保持することを特徴とする請求項４８〜５２のいずれかに記載の通信端末装置。
【請求項５４】
上記メッセージ保持手段は、メッセージと共にメッセージの送信証明情報を保持することを特徴とする請求項４８〜５３のいずれかに記載の通信端末装置。
【請求項５５】
上記受信確認返信手段は、メッセージとそのメッセージに付加されている全ての情報に対して受信確認を実行することを特徴とする請求項４８〜５４のいずれかに記載の通信端末装置。
【請求項５６】
上記認証情報検証手段は、与えられた情報に一方向性関数を施した出力値が、保持する情報と一致することで、与えられた情報をメッセージ送信装置の認証情報であると判断した認証情報、若しくは、その情報から派生する情報をメッセージ送信装置の認証鍵であると判断することを特徴とする請求項５０〜５５のいずれかに記載の通信端末装置。
【請求項５７】
上記メッセージ認証手段は、上記メッセージ保持手段が複数のメッセージを管理・保持する場合に、管理する順番で最初に認証したメッセージをメッセージ送信装置からの正しいメッセージであると認証することを特徴とする請求項５３に記載の通信端末装置。
【請求項５８】
上記メッセージ認証手段は、上記メッセージ保持手段が複数のメッセージを管理・保持する場合に、管理する順番に検証し、所定数のメッセージのみをメッセージ送信装置からの正しいメッセージであると認証することを特徴とする請求項５３に記載の通信端末装置。
【請求項５９】
上記メッセージ認証手段は、上記メッセージ送信装置の認証鍵を用いて、上記メッセージ保持手段にて管理・保持するメッセージに対して生成した送信証明情報と、そのメッセージと共に保持する送信証明情報とが一致することでそのメッセージを認証することを特徴とする請求項５７又は５８に記載の通信端末装置。
【請求項６０】
上記受信確認返信手段の、メッセージの受信確認情報を生成する第４のサブ手段は、メッセージの識別子と受信証明情報の組を管理することを特徴とする請求項４９に記載の通信端末装置。
【請求項６１】
上記受信確認返信手段は、受信確認情報にその受信確認情報がどのメッセージに対して生成したものかを示すために、メッセージの識別子を付加することを特徴とする請求項６０に記載の通信端末装置。
【請求項６２】
上記受信確認返信手段の、メッセージの受信確認情報を生成する第４のサブ手段は、マルチホップのツリー構造上で自己が接続するエンド側の通信端末装置が該当する子ノードから与えられた受信確認情報に付加されているメッセージの識別子に応じ、その識別子に対応する受信証明情報を用いて受信確認情報を生成することを特徴とする請求項６０又は６１に記載の通信端末装置。
【請求項６３】
上記認証情報検証手段は、与えられた情報に一方向性関数を任意回数施した出力値が、保持する情報と一致することで、与えられた情報をメッセージ送信装置の認証情報であると判断し、上記メッセージ送信装置の認証情報と、上記保持する情報を出力するまでに存在した全ての中間値、若しくは、それら情報から派生する情報をメッセージ送信装置の認証鍵であると判断することを特徴とする請求項５０〜５５のいずれかに記載の通信端末装置。
【請求項６４】
上記メッセージ認証手段は、上記メッセージ保持手段にて管理・保持するメッセージに対して、認証鍵を用いて生成した送信証明情報と、そのメッセージと共に保持する送信証明情報とが一致することでそのメッセージを認証することを、メッセージ送信装置の複数の認証鍵のそれぞれで、対応する１つ又は複数のメッセージに対して行うことを特徴とする請求項６３に記載の通信端末装置。
【請求項６５】
上記認証情報検証手段は、与えられた情報から検証し得ないときに、与えられた情報を含むメッセージ全体を破棄することを特徴とする請求項４８〜６４のいずれかに記載の通信端末装置。
【請求項６６】
マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムであって、
メッセージ送信装置として請求項３１の通信端末装置を適用し、
メッセージ受信装置として請求項４８の通信端末装置を適用した
ことを特徴とするメッセージ認証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメッセージ認証方法、通信端末装置及びメッセージ認証システムに関し、例えば、センサネットワークシステムのような、システムを集中制御するサーバと、低コストで構成される膨大な数のセンサノードからなるシステムにおいて、サーバがセンサノードにメッセージをブロードキャストし、そのメッセージが、サーバが送信したものであることをセンサノードが認証する場合に適用し得るものである。
【背景技術】
【０００２】
近年、無線通信機能を持つセンサを多数設置して設備の管理や環境の観測などに役立てるセンサネットワークシステムが提案されている。センサネットワークシステムは、システムを管理・制御するサーバと、低コストで構成される膨大な数のセンサノードとから構成され、マルチホップ通信により情報を授受することが想定される。ここで、センサネットワークにおける情報発信の形態の１つに、サーバから全ノードに対する情報発信（ブロードキャスト）がある。例えば、ノードに搭載するソフトウェアの更新データなど、サーバが全ノードに対して重要な情報を発信するときは、サーバはノードに正しいデータが届けられたことを確認したい。また、ノードは受信したデータが改竄されていないことと確かにサーバからのデータであることを認証したい。本発明は、例えば、このようなセンサネットワークシステムのような、システムを管理・制御するサーバと、低コストで構成される膨大な数のノードから成るシステムで、サーバがノードにメッセージをブロードキャストしてその受信確認を行い、また、ノードが受信したデータをサーバからの正しいデータであると認証する場合に適用し得る。
【０００３】
ここで、サーバが自身の発信したブロードキャストデータに対して、ノードから受信確認を得ることは、次のような問題（ａ）、（ｂ）がある。
【０００４】
（ａ）膨大な数のノードが存在するセンサネットワークシステムにおいて、受信確認の返信は、ネットワークの通信オーバヘッドが大きい。
【０００５】
（ｂ）マルチホップ通信環境では、受信確認メッセージは複数のノードを中継して返信されるため、受信確認メッセージ自体に信憑性がない。例えば、不正なノードが受信確認メッセージを偽造しているかもしれない。
【０００６】
また、センサノードは処理能力に関する制約があり、処理負荷の軽いアルゴリズムでサーバからのデータを認証することが望まれる。例えば、全ノードに共通のサーバ認証鍵を持たせて、共通鍵暗号を用いて認証する方法があるが、この場合、全ノードがサーバの認証鍵を知っているので、任意のノードがサーバになりすますことを許してしまう。さらに、低コストで構成されるセンサノードには、必ずしも高コストな耐タンパ性装置を搭載するとは限らず、もし任意の１ノードの持つ内部情報が解析されてサーバの認証鍵が漏洩してしまった場合は、第３者がサーバになりすましてセンサネットワークシステムを制御できる可能性がある。
【０００７】
非特許文献１は、サーバからのブロードキャストデータをノードが認証する方式について記載したものであり、その２．１節で、認証鍵連鎖についての説明がある。認証鍵連鎖は、任意の値にハッシュ関数のような一方向関数を繰り返し適用して、それら全演算結果を生成した順と逆順に認証情報として用いる概念である。この概念は、例えば、Ｓ／ＫＥＹ［ＲＦＣ１９３８］などのワンタイムパスワード方式に利用されている。
【０００８】
サーバからのデータの認証に、認証鍵連鎖を利用することは、次のような利点（ａ）〜（ｃ）がある。
【０００９】
（ａ）サーバからのデータを認証するための情報は毎回異なるので盗聴されても再利用不可能である。
【００１０】
（ｂ）サーバからのデータの認証にあたり、ノードが保持しておく情報は、後に公開されるサーバからのデータを認証するための情報を検証するための情報であるため、漏洩しても支障はない。
【００１１】
（ｃ）処理負荷の軽い共通鍵暗号系のみを用いて実現できる。
【非特許文献１】Ａ．Ｐｅｒｒｉｇ，  Ｒ．Ｃａｎｅｔｔｉ，  Ｊ．Ｄ．Ｔｙｇａｒ  ａｎｄ  Ｄ．Ｓｏｎｇ，“Ｔｈｅ  ＴＥＳＬＡ  Ｂｒｏａｄｃａｓｔ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ”，  ＲＳＡ  ＣｒｙｐｔｏＢｙｔｅｓ，  ５（Ｓｕｍｍｅｒ）、２００２．
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、非特許文献１の認証鍵連鎖（認証鍵）の概念は、マルチホップ通信環境を想定していない。
【００１３】
マルチホップ通信環境では、サーバが発信するデータを、先に受信するノードと、複数のノードが中継した後に受信するノードが存在する。そのため、次に公開されるサーバの認証情報を、先に知るノードと、後に知るノードが存在することになる。この場合、公開されたサーバの認証情報を先に知るノードが、後に知るノードに対して、サーバへなりすますことが可能になるという課題があった。
【００１４】
そのため、マルチホップ通信環境下でも、メッセージ送信装置へのなりすましに対する耐性を高くできるメッセージ認証方法、通信端末装置及びメッセージ認証システムが望まれている。
【課題を解決するための手段】
【００１５】
第１の本発明は、マルチホップ通信環境下で、メッセージ送信装置がメッセージ受信装置に対してメッセージの受信を確認し、メッセージ受信装置が、受信したメッセージがメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証方法であって、メッセージ送信装置がメッセージ受信装置に対してメッセージの受信を確認する第１の工程と、メッセージ送信装置が上記メッセージをメッセージ受信装置に認証させるための情報を公開する第２の工程と、メッセージ受信装置が上記認証させるための情報を検証する第３の工程と、メッセージ受信装置が上記メッセージを認証する第４の工程とを含むことを特徴とする。
【００１６】
第２の本発明は、マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムにおける、メッセージ送信装置が該当する通信端末装置であって、メッセージを生成するメッセージ生成手段と、メッセージを送信するメッセージ送信手段と、メッセージ受信装置がメッセージを受信したことを確認する受信確認手段と、自身の認証情報を管理する認証情報管理手段と、自身の認証情報を公開する認証情報公開手段とを有することを特徴とする。
【００１７】
第３の本発明は、マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムにおける、メッセージ受信装置が該当する通信端末装置であって、メッセージを保持するメッセージ保持手段と、メッセージの受信確認を返す受信確認返信手段と、メッセージ送信装置の認証情報を検証する認証情報検証手段と、メッセージを認証するメッセージ認証手段と有することを特徴とする。
【００１８】
第４の本発明は、マルチホップ通信環境において、メッセージ送信装置がメッセージ受信装置に対して送信したメッセージの受信を確認し、メッセージ受信装置が受信したメッセージをメッセージ送信装置からの正しいメッセージであることを認証するメッセージ認証システムであって、メッセージ送信装置として第２の本発明の通信端末装置を適用し、メッセージ受信装置として第３の本発明の通信端末装置を適用したことを特徴とする。
【発明の効果】
【００１９】
本発明によれば、マルチホップ通信環境下でも、メッセージ送信装置へのなりすましに対する耐性を高くすることができる。
【発明を実施するための最良の形態】
【００２０】
以下で説明する各実施形態は、サーバが、自身の発信したブロードキャストデータに対するノードの受信確認を得た後に、サーバがまだ公開していないＯｎｅ−ｗａｙ  ｃｈａｉｎ（以下、認証鍵連鎖と呼ぶ）の鍵（以下、適宜、サーバの認証鍵と呼ぶ）を公開することにより、従来の課題を解決しようとしたものである。
【００２１】
（Ａ）第１の実施形態
以下、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第１の実施形態を、図面を参照しながら詳述する。
【００２２】
この第１の実施形態では、サーバがデータをブロードキャストし、ノードが受信したブロードキャストデータに対する受信確認をサーバに返信し、サーバがノードに正しいデータが届いたことを確認できた後に、まだネットワーク内に公開していないサーバの認証鍵を公開し、ノードが、公開された鍵が確かにサーバの認証鍵であることを確かめることで、既に受信しているデータをサーバからの正しいデータであると認証することを特徴としている。
【００２３】
（Ａ−１）第１の実施形態の構成
第１の実施形態のメッセージ受信確認システムが前提とするネットワークは、図１に示すように、サーバ１に対し、多数（図１では５個）のノード２がツリー状に接続された構成を有している。なお、サーバ１、各ノード２が、通信端末装置に該当する。
【００２４】
図２は、第１の実施形態におけるサーバ（ブロードキャストデータの送信装置）１の内部構成を示すブロック図である。
【００２５】
図２において、サーバ１は、サーバ認証鍵管理部１１、データ生成部１２、ノード情報管理部１３、受信確認情報検証部１４、送信部１５及び受信部１６を有する。
【００２６】
サーバ認証鍵管理部１１は、サーバ１が管理下のノード２に対して、自身を証明するための認証鍵（認証鍵連鎖）を管理するものである。
【００２７】
図４は、この第１の実施形態のサーバ１の認証鍵（認証鍵連鎖）の概要を示す説明図である。サーバ１は、ランダムに初期値Ｋｎを選び、システムで予め決められた一方向性を持った関数Ｆ（・）を適用し、その出力値に対して関数Ｆ（・）を適用し、この関数Ｆ（・）を複数回適用することで、認証鍵の連鎖を生成する。適用する一方向性関数は、例えば、ＭＤ５（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  ５）やＳＨＡ−１（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ  １）などのハッシュ関数である。サーバ１は、管理下のノード２に自身を証明するために、保持する認証鍵（の連鎖）を生成した順と逆順で公開する。
【００２８】
ハッシュ関数の出力値から入力値を求めることは計算量的に困難なので、サーバ以外のものが、サーバの認証鍵連鎖におけるまだ公開されていない認証鍵を、サーバ１が公開する前に知ることは困難である。
【００２９】
サーバ認証鍵管理部１１は、受信確認情報検証部１４より、検証結果一致のメッセージを受けて、ネットワーク内に認証鍵連鎖の未公開の次の鍵を送信部１５へ与えて管理下のノード２に公開する。
【００３０】
データ生成部１２は、全てのノード２へブロードキャストするデータを生成するものである。データ生成部１２は、生成したブロードキャストデータを、受信確認情報検証部１４と送信部１５へ与える。
【００３１】
ノード情報管理部１３は、管理下のノード２の情報を管理するものであり、管理するノード情報を受信確認情報検証部１４へ与えるものである。ここで、ノード情報とは、図１に示すように、ノードＩＤと、ノード認証鍵と、そのノードへのルート情報より構成されている。ノードＩＤとは、ノードを識別するのに用いる情報で、例えば、６４ｂｉｔ−ＩＥＥＥアドレスなどを適用し得る。ノード認証鍵とは、サーバ１と各ノード２とが１対１で共有する鍵情報であり、任意のビット列で表される。ノードへのルート情報は、サーバ１と全てのノード２との間のルート情報が分かれば良く、特に、そのデータ形式などは限定されない。
【００３２】
受信確認情報検証部１４は、データ生成部１２より与えられたデータと、ノード情報管理部１３より与えられたノード情報と、受信部１６より与えられた受信確認情報から、発信したデータが管理下の全てのノード２に届いたか、そうでないかを検証するものである。
【００３３】
受信確認情報検証部１４は、例えば、ＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）生成アルゴリズムとハッシュ関数を有する。ＭＡＣ生成アルゴリズムは、例えば、ＡＥＳ暗号等のブロック暗号を用いたＣＢＣ−ＭＡＣ（Ｃｉｐｈｅｒ  Ｂｌｏｋ  Ｃｈａｉｎｉｎｇ−Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）であり、ハッシュ関数は、例えば、ＭＤ５やＳＨＡ−１である。これらＭＡＣ生成アルゴリズムとハッシュ関数は、サーバ１とノード２との間で予め決定し、保持している必要がある。
【００３４】
受信確認情報検証部１４は、ノード情報管理部１３より与えられる管理下のノード２へのルート情報に従い、隣接ノードが返信すると想定する受信確認情報を求める。例えば、図１のようなノード情報をサーバ１が保持している場合、受信確認情報検証部１４での演算は、データ生成部１２より与えられたデータと、ノード認証鍵を用いて、図５中の式１のように行う。すなわち、受信確認情報検証部１４は、エンドノードに関しては、発信したデータＸに対するＭＡＣをそのノードの認証鍵を用いて計算し、計算で得られたＭＡＣに対してハッシュ関数を施し、ルータノードに関しては、発信したデータＸに対するＭＡＣをそのノードの認証鍵を用いて計算したものに、さらに、そのノードが中継している１つ又は複数のノードにおける計算結果を連結し、連結後のデータに対してハッシュ関数を施す、というように、各ノード２における計算結果を重畳して最終的な演算結果を得る。
【００３５】
ここで、ルータノードとは、ツリー構造における親ノードのように、１つ又は複数のノードへの中継ノードとなるノードを指し、エンドノードとは、ツリー構造における子ノードを持たないノードのように、次ホップノードへの中継ノードとならないノードを指す。
【００３６】
受信確認情報検証部１４は、受信確認情報検証部１４での演算結果と、受信部１６より与えられた受信確認情報が一致することで、発信したデータが、管理下のノード２に正しく届けられたことが分かり、検証結果一致のメッセージをサーバ認証鍵管理部１１へ与える。
【００３７】
送信部１５は、データ生成部１２より与えられるデータを、管理下のノード２へブロードキャストするものである。また、送信部１５は、サーバ認証鍵管理部１１より与えられる、ネットワーク内に未公開の認証鍵連鎖の鍵を管理下のノード２へ公開するものである。
【００３８】
受信部１６は、隣接する管理下のノード２から受信した受信確認情報を、受信確認情報検証部１４へ与えるものである。ここで、「隣接する」とは、１ホップでデータの送受信が可能な範囲を表す。
【００３９】
図３は、第１の実施形態におけるノード（ブロードキャストデータの受信装置）２の内部構成を示すブロック図である。なお、図３は、各ノードがブロードキャストデータを受信したことをサーバ側に伝える構成面から構成要素を記載しており、ブロードキャストデータを、子ノード側に中継送信する構成については省略している。
【００４０】
図３において、ノード２は、受信データ保持部３１、自ノード認証鍵管理部３２、ＭＡＣ生成部３３、子ノード情報管理部３４、受信確認情報生成部３５、サーバ認証鍵検証部３６、受信部３７及び送信部３８を有する。
【００４１】
受信データ保持部３１は、受信部３７より与えられるサーバ１のブロードキャストデータを保持しておくものである。また、受信データ保持部３１は、受信部３７より与えられたデータをＭＡＣ生成部３３へ与えるものである。さらに、受信データ保持部３１は、サーバ認証鍵検証部３６より検証結果一致のメッセージを与えられて、保持するブロードキャストデータをサーバ１からの正しいデータであると判断する。
【００４２】
自ノード認証鍵管理部３２は、サーバ１と当該ノード２とが１対１で共有する鍵を管理するものであり、管理する鍵をＭＡＣ生成部３３へ与える。ここで、管理する鍵は、サーバ１に当該ノード２を認証せしめる認証鍵として用いられる。
【００４３】
ＭＡＣ生成部３３は、受信データ保持部３１から与えられるブロードキャストデータに対して、自ノード認証鍵管理部３２から与えられる当該ノード２の認証鍵を用いて、ＭＡＣを生成するものであり、生成したＭＡＣを受信確認情報生成部３５へ与えるものである。ここで、ＭＡＣ生成部３３は、ＭＡＣ生成アルゴリズムを有する。このＭＡＣ生成アルゴリズムは、サーバ１との間で事前に決定されたものであり、サーバ１が受信確認情報検証部１４に有するＭＡＣ生成アルゴリズムと同じものである。
【００４４】
子ノード情報管理部３４は、当該ノード２がルータノードであるか又はエンドノードであるか、ルータノードの場合は、さらに、当該ノード２が中継となっている子ノードの情報を管理するものであり、管理する情報を受信確認情報生成部３５へ与えるものである。
【００４５】
子ノード情報管理部３４に、ノード情報を管理していないことにより、当該ノード２がエンドノードであることが分かる。また、子ノード情報管理部３４に、ノード情報を管理していることで、当該ノード２がルータノードであることが分かる。当該ノード２がルータノードの場合に管理する子ノードの情報は、子ノードの識別情報と、その子ノードがルータノードであるかエンドノードであるかという情報である。
【００４６】
受信確認情報生成部３５は、子ノード情報管理部３４より与えられる情報と、ＭＡＣ生成部３３より与えられるＭＡＣと、受信部３７より与えられる子ノードの生成した受信確認情報より、当該ノード２の受信確認情報を生成するものであり、生成した受信確認情報を送信部３８へ与える。ここで、受信確認情報生成部３５は、ハッシュ関数を有する。このハッシュ関数は、サーバ１との間で事前に決定されたものであり、サーバ１が受信確認情報検証部１４に有するハッシュ関数と同じものである。受信確認情報生成部３５は、子ノード情報管理部３４より当該ノード２がエンドノードであることを受けて、ＭＡＣ生成部３３より与えられるＭＡＣに対してハッシュ関数を施し、それを当該ノードの受信確認情報として送信部３８へ与える。一方、受信確認情報生成部３５は、子ノード情報管理部３４より、当該ノード２がルータノードであることと、１又は複数の子ノードのＩＤを受けて、ＭＡＣ生成部３３より与えられるＭＡＣと、受信部３７より与えられる全ての子ノードの受信確認情報を連結したものに対して、ハッシュ関数を施し、それを当該ノード２の受信確認情報として送信部３８へ与える。ここで、複数の子ノードより受信確認情報を与えられた場合の受信確認情報の連結の順番は、特に限定されない。例えば、ノードＩＤの大小に従って連結する順番を決定しても良い。但し、サーバ１との間で事前に決定された仕様に従う必要がある。
【００４７】
サーバ認証鍵検証部３６は、受信部３７より与えられる認証情報が、確かにサーバ１が管理する認証鍵連鎖における未公開だった鍵であるかどうかを検証するものである。また、  サーバ認証鍵検証部３６は、サーバ１が一番最近に公開した認証鍵連鎖の鍵を保持する。さらに、サーバ認証鍵検証部３６は、一方向性関数を有する。この一方向性関数は、サーバ１との間で事前に決定されたものであり、サーバ１がサーバ認証鍵管理部１１に有する一方向性関数と同じものである。サーバ認証鍵検証部３６は、受信部３７より与えられた鍵情報に一方向性関数を施し、その出力値が、保持するサーバ１が一番最近に公開した鍵の値と一致することで、受信した鍵情報をサーバ１が一番最近に公開した認証鍵連鎖の鍵であると認証し、保持する鍵を更新する。さらに、サーバ認証鍵検証部３６は、検証結果一致のメッセージを受信データ保持部３１へ与える。
【００４８】
受信部３７は、サーバ１からのブロードキャストデータを受信データ保持部３１へ、子ノード２からの受信確認情報を受信確認情報生成部３５へ、ネットワーク内に公開されたサーバ１の認証鍵をサーバ認証鍵検証部３６へ与えるものである。
【００４９】
送信部３８は、受信確認情報生成部３５より与えられる当該ノード２の受信確認情報を自身の親ノード（親がサーバの場合はサーバ）に送信するものである。
【００５０】
（Ａ−２）第１の実施形態の動作
次に、第１の実施形態のメッセージ認証システムの動作（第１の実施形態のメッセージ認証方法）を、図６〜図９をも参照しながら説明する。ここで、第１の実施形態のメッセージ認証システムの動作は、大きくは、７段階の動作（Ｓ１０１〜Ｓ１０７）でなっている。
【００５１】
「第１段階Ｓ１０１（図６）」
サーバ１は、データ生成部１２においてデータＸを生成し、送信部１５を通して管理下のノード２にブロードキャストする。
【００５２】
「第２段階Ｓ１０２（図６）」
ノード２は、受信部３７によって受信したブロードキャストデータＸを受信データ保持部３１に保持する。なお、ノード２がルータノードであれば、ブロードキャストデータＸの子ノードへの中継送信も行う。
【００５３】
「第３段階Ｓ１０３（図７）」
ノード２は、ＭＡＣ生成部３３において、受信データ保持部３１より与えられるブロードキャストデータＸと、自ノード認証鍵管理部３２により与えられる当該ノード２の認証鍵を入力して、受信データのＭＡＣを生成し、受信確認情報生成部３５へ与える。
【００５４】
ノード２は、受信確認情報生成部３５において、子ノード情報管理部３４から与えられる情報より自身がエンドノードかルータノードかを判断する。エンドノード（図１のネットワーク構成であれば、ＩＤが「０３」〜「０５」のノード）である場合には、ＭＡＣ生成部３３より与えられるＭＡＣに対してハッシュ関数を施したハッシュ値を自身の受信確認情報として送信部３８から親ノードに送信する。ルータノード（図１のネットワーク構成であれば、ＩＤが「０１」、「０２」のノード）の場合には、受信部３７を通して全ての子ノードの受信確認情報が与えられることで、ＭＡＣ生成部３３より与えられるＭＡＣと、全ての子ノードの受信確認情報とを連結させ、その連結させたものに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報として送信部３８から親ノードに送信する。
【００５５】
例えば、図７のＩＤが「０４」のエンドノードにおいては、ＭＡＣ生成部３３が、サーバ１からのブロードキャストデータＸ（図７では誤って届いている可能性もあるので、Ｘ’で表している）と、当該ノードの認証鍵Ｋ０４’を入力して、受信データのＭＡＣを生成し、受信確認情報生成部３５が、そのＭＡＣに対してハッシュ関数Ｈ（・）を施したハッシュ値を、自身の受信確認情報として、送信部３８から親ノード（「０２」のノード）に送信する。
【００５６】
また例えば、図７のＩＤが「０２」のルータノードにおいては、受信確認情報生成部３５は、ＭＡＣ生成部３３より与えられるＭＡＣと、全ての子ノード（「０４」及び「０５」）の受信確認情報ｈ’０４、ｈ’０５とを連結させたものに対してハッシュ関数Ｈ（・）を施したハッシュ値を、自身の受信確認情報として送信部３８から親ノード（「０１」のノード）に送信する。
【００５７】
「第４段階Ｓ１０４（図７）」
サーバ１は、受信確認情報検証部１４において、データ生成部１２より与えられるブロードキャストデータＸと、ノード情報管理部１３より与えられるノードＩＤ、ノード認証鍵、ルート情報から、隣接ノードから返信されるであろう受信確認情報を算出する。この際の受信確認情報の算出方法は、ツリー構造の各ノードが実行すると同様な処理を、エンドノード側からトップノードへかけて順次行うものである。
【００５８】
「第５段階Ｓ１０５（図８）」
サーバ１は、受信確認情報検証部１４において、算出した受信確認情報と、受信部１６より受けた隣接ノードからの受信確認情報が一致するかどうかを検証する。サーバ１は、検証結果が一致することで、サーバ認証鍵管理部１１で管理するネットワーク内に認証鍵連鎖の未公開の次の鍵Ｋｉをネットワーク内に公開することを許可する。一方、サーバ１は、検証結果が一致しないことで、鍵Ｋｉを公開することを許可しない。
【００５９】
「第６段階Ｓ１０６（図８）」
サーバ１は、ネットワーク内に認証鍵連鎖の未公開の鍵Ｋｉを、送信部１５からネットワーク内に公開する。
【００６０】
「第７段階Ｓ１０７（図９）」
ノード２は、受信部３７によって受信した鍵をサーバ認証鍵検証部３６に与え、受信した鍵が、確かにサーバ２がネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを、受信した鍵に一方向性関数を施した結果が、既にサーバ認証鍵検証部３６にて保持するサーバ１が一番最近に公開した鍵と一致するかどうかを確かめることで検証する。
【００６１】
ノード２は、検証結果が一致することで、受信した鍵を、サーバ１がネットワーク内に未公開にしていた認証鍵連鎖の鍵であると認証し、受信データ保持部３１に保持するデータＸをサーバ１からの正しいデータであると認証する。また、認証した鍵を、サーバ１によって一番最近に公開された鍵としてサーバ認証鍵検証部３６に保持する。
【００６２】
（Ａ−３）第１の実施形態の効果
第１の実施形態によれば、サーバ１がデータをブロードキャストし、ノード２が受信したデータに対する受信確認をサーバ１に返信し、サーバ１がノード２に正しいデータが届いたことを確認した後で、サーバ２がまだネットワーク内に公開していない認証鍵連鎖上の鍵（ノード２がサーバ１を認証する鍵）を公開することを許可し、ノード２が公開された鍵が確かにサーバ１の有する認証鍵連鎖上の鍵であることを確かめることで、既に保持しているデータをサーバ１からの正しいデータであると認証する。
【００６３】
サーバ１が認証鍵連鎖上の次の未公開の鍵を公開するときは、管理下のノード２に正しいデータが届けられたことを確認できた状態であるため、ノード２は公開された鍵が確かに認証鍵連鎖上の次に公開される鍵（サーバの認証鍵）かどうかを検証することで、既に保持するデータがサーバ１からの正しいデータであると認証できる。
【００６４】
マルチホップ通信環境のように、サーバ１の認証鍵を先に知るノードと後に知るノードが混在する状況であっても、サーバ１の認証鍵が公開されるときは、ノード２が既にサーバ１からの正しいデータを受信した後であるので、サーバ１の認証鍵を先に知るノードが後に知るノードに対して、サーバ１になりすまして不正なデータを認証させることはできない。
【００６５】
（Ｂ）第２の実施形態
次に、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第２の実施形態を、図面を参照しながら説明する。
【００６６】
上述した第１の実施形態は、サーバのブロードキャストデータに対して、ノードが必ず受信確認情報を返すことを前提としたものであった。しかし、例えば、ノードの故障や、ノードが本来のあるべき場所に存在しないなどの理由で、受信確認情報を応答しない場合が想定される。そういった場合に、第１の実施形態では、サーバは受信確認を得られないので、それ以降の動作が止まってしまう。
【００６７】
第２の実施形態では、各ルータノードが受信確認情報に、受信確認情報を得られなかった子ノードのＩＤを付加することで、サーバが、データが不達の可能性があるノードを検知してから、ネットワークに認証鍵連鎖の未公開の次の鍵を公開することを特徴とする。
【００６８】
（Ｂ−１）第２の実施形態の構成
図１０は、第２の実施形態のサーバ（ブロードキャストデータの送信装置）１Ｂの構成を示すブロック図であり、第１の実施形態に係る図２との同一、対応部分には同一符号を付して示している。
【００６９】
第２の実施形態のサーバ１Ｂは、サーバ認証鍵管理部１１、データ生成部１２、ノード情報管理部１３、受信確認情報検証部１４、不達ノードＩＤ管理部１７、送信部１５及び受信部１６を有する。第１の実施形態に比較すると、不達ノードＩＤ管理部１７が追加されており、また、受信確認情報検証部１４及び受信部１６の機能も多少異なっている。以下では、第１の実施形態と異なる構成要素について説明する。
【００７０】
第２の実施形態の受信確認情報検証部１４は、以下の点が、第１の実施形態の受信確認情報検証部１４と異なっている。
【００７１】
第２の実施形態の受信確認情報検証部１４には、受信部１６より０以上の不達ノードＩＤが付加された受信確認情報を与えられる。不達ノードＩＤ付き受信確認情報は、例えば、受信確認情報の後にノードＩＤが連結された形式をとっており、受信確認情報検証部１４では、予めシステムで設定されているピット長に従い、受信確認情報と、０以上の不達ノードＩＤとを抽出する。例えば、不達ノードのＩＤが存在する場合は、図１２のように、その不達ノードを含め、その不達ノードより下流のノードには届かなかったと認識し、図１２中の式２のように、ブロードキャストデータが到達したノードに係る情報だけを用いた演算を実行する。受信確認情報検証部１４での演算結果と、受信部１６より与えられた受信確認情報とが、一致するか否かにより、サーバ１Ｂがブロードキャストした正しいデータが、サーバ１Ｂが管理するノードの中で、不達ノードとそれより下流のノード以外に届いたか否かを把握できる。受信確認情報検証部１４は、検証結果が一致すると、不達ノードのＩＤを不達ノードＩＤ管理部１７へ与え、検証結果一致のメッセージをサーバ認証鍵管理部１１へ与える。
【００７２】
不達ノードＩＤ管理部１７は、受信確認情報検証部１４より与えられる不達ノードＩＤを保持するものである。ここで、ＩＤを保持することは、ＩＤを保持する不達ノードと、それよりも下流のノードにはブロードキャストデータが正しく届いたか否かが分からないことを表している。
【００７３】
受信部１６は、隣接する管理下のノード２Ｂから受信した０以上の不達ノードＩＤ付き受信確認情報を、受信確認情報検証部１４へ与えるものである。
【００７４】
図１１は、第２の実施形態の各ノード（ブロードキャストデータの受信装置）２Ｂの構成を示すブロック図であり、第１の実施形態に係る図３との同一、対応部分には同一符号を付して示している。
【００７５】
第２の実施形態のノード２Ｂは、受信データ保持部３１、自ノード認証鍵管理部３２、ＭＡＣ生成部３３、子ノード情報管理部３４、受信確認情報生成部３５、サーバ認証鍵検証部３６、不達ノードＩＤ管理部３９、ノードＩＤ付加部４０、受信部３７及び送信部３８を有している。
【００７６】
以下では、第１の実施形態では存在しなかった不達ノードＩＤ管理部３９及びノードＩＤ付加部４０と、第１の実施形態における対応要素と機能が多少異なっている受信確認情報生成部３５、受信部３７及び送信部３８について説明する。
【００７７】
第２の実施形態の受信確認情報生成部３５については、第１の実施形態の受信確認情報生成部と異なるところについて説明する。第２の実施形態の受信確認情報生成部３５は、受信部３７より与えられる子ノードの受信確認情報に不達ノードＩＤが付加されている場合には、全ての不達ノードＩＤを取り除いたものを子ノードからの受信確認情報とする。
【００７８】
不達ノードＩＤが付加された受信確認情報は、例えば、受信確認情報の後にノードＩＤがビット連結された形式をとっており、受信確認情報生成部３５は、予めシステムで設定されているビット長に従い、受信確認情報と、０以上の不達ノードＩＤとを抽出する。
【００７９】
また、受信確認情報生成部３５は、ある子ノードへブロードキャストデータを中継送信した時点から所定時間を経過しても、受信部３７からその子ノードの受信確認情報を与えられないと、ＭＡＣ生成部３３より与えられたＭＡＣと、受信部３７より既に与えられている０以上の受信確認情報を連結したものに対して、ハッシュ関数を施し、それを当該ノードの受信確認情報として、ノードＩＤ付加部４０へ与える。ここで、上述の所定時間は、例えば、システムに共通の値としても良く、子ノードがルータノードかエンドノードか等により各々値を変えて設定しても良い。
【００８０】
さらに、受信確認情報生成部３５は、受信部３７より与えられた受信確認情報に付加されている０以上の不達ノードＩＤと、受信部３７より受信確認情報を与えられなかった０以上の全ての子ノードのＩＤを、不達ノードＩＤ管理部３９へ与える。
【００８１】
不達ノードＩＤ管理部３９は、受信確認情報生成部３５より与えられる不達ノードＩＤを管理するものである。また、不達ノードＩＤ管理部３９は、受信確認情報生成部３５より不達ノードのＩＤを与えられることで、必要に応じて、その不達ノードのＩＤをノードＩＤ付加部４０へ与える。
【００８２】
ノードＩＤ付加部４０は、不達ノードＩＤ管理部３９より０以上の不達ノードのＩＤを与えられることで、受信確認情報生成部３５より与えられる当該ノードの受信確認情報に、不達ノードＩＤを付加して不達ノードＩＤ付き受信確認情報を生成するものであり、生成した不達ノードＩＤ付き受信確認情報を送信部３８へ与える。不達ノードＩＤ付受信確認情報の形式は、予めシステムで設定されている。
【００８３】
受信部３７は、サーバ１Ｂからのブロードキャストデータを受信データ保持部３１へ、また、子ノードからの０以上の不達ノードＩＤ付き受信確認情報を受信確認情報生成部３５へ、さらに、ネットワーク内に公開されたサーバの認証鍵をサーバ認証鍵検証部３６へ与えるものである。
【００８４】
送信部３８は、ノードＩＤ付加部３９より与えられる０以上の不達ノードＩＤ付き受信確認情報を、自身の親ノード（親がサーバの場合はサーバ）に送信するものである。
【００８５】
（Ｂ−２）第２の実施形態の動作
次に、第２の実施形態のメッセージ認証システムの動作（第２の実施形態のメッセージ認証方法）を、図１３〜図１７をも参照しながら説明する。ここで、第２の実施形態のメッセージ認証システムの動作は、大きくは、７段階の動作（Ｓ２０１〜Ｓ２０７）でなっている。
【００８６】
「第１段階Ｓ２０１（図１３）」
サーバ１Ｂは、データ生成部１２においてデータＸを生成し、送信部１５を通して管理下のノード２Ｂにブロードキャストする。
【００８７】
「第２段階Ｓ２０２（図１３）」
ノード２Ｂは、受信部３７によって受信したブロードキャストデータＸを受信データ保持部３１に保持する。
【００８８】
「第３段階Ｓ２０３（図１４）」
ノード２Ｂは、ＭＡＣ生成部３３において、受信データ保持部３１より与えられるブロードキャストデータＸと、自ノード認証鍵管理部３２により与えられる当該ノード２Ｂの認証鍵を入力して、受信データのＭＡＣを生成し、受信確認情報生成部３５へ与える。
【００８９】
ノード２Ｂは、受信確認情報生成部３５において、子ノード情報管理部３４から与えられる情報より自身がエンドノードかルータノードかを判断する。そして、エンドノードである場合は、ＭＡＣ生成部３３より与えられるＭＡＣに対してハッシュ関数を施したハッシュ値を、自身の受信確認情報としてノードＩＤ付加部４０へ与える。一方、ルータノードの場合は、受信部３７を通して全ての子ノードの受信確認情報が与えられることで、ＭＡＣ生成部３３より与えられるＭＡＣと全ての子ノードの受信確認情報とを連結させたものに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報としてノードＩＤ付加部４０へ与える。但し、所定時間だけ経過しても、いずれかの子ノードから受信確認情報が与えられない場合には、その子ノードのＩＤを不達ノードＩＤ管理部３９へ与え、ＭＡＣ生成部３３より与えられるＭＡＣと既に与えられている０以上の子ノードの受信確認情報とを連結させたものに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報としてノードＩＤ付加部４０へ与える。また、受信部３７より与えられた子ノードの受信確認情報に不達ノードＩＤが付加されている場合には、その不達ノードＩＤを不達ノードＩＤ管理部３９へ与え、不達ノードＩＤを取り除いた受信確認情報を子ノードの受信確認情報として扱う。
【００９０】
ノード２Ｂは、ノードＩＤ付加部４０において、不達ノードＩＤ管理部３９より０以上の不達ノードのＩＤが与えられることにより、受信確認情報生成部３５より与えられた当該ノード２Ｂの受信確認情報に不達ノードＩＤを付加して、不達ノードＩＤ付き受信確認情報を生成し、送信部３８を通して親ノードに送信する。
【００９１】
図１４において、例えば、ＩＤが「０２」のノードでは、「０４」の子ノードからの受信確認情報が所定時間経過しても届かないので、受信確認情報生成部３５は、ＭＡＣ生成部３３より与えられるＭＡＣと、既に与えられている他の全ての子ノード（ここでは「０５」のノードだけ）からの受信確認情報とを連結させたものに対してハッシュ関数を施したハッシュ値を、自身の受信確認情報として、ノードＩＤ付加部４０へ与え、ノードＩＤ付加部４０は、この受信確認情報（ハッシュ値）に、不達ノードＩＤ「０４」を連結させて、受信応答情報として送信部３８より親ノード（「０１」のノード）に送信させる。
【００９２】
また例えば、ＩＤが「０１」のノードでは、「０２」の子ノードからの受信確認情報は不達ノードＩＤ「０４」が付加されているので、不達ノードＩＤ「０４」と受信確認情報とを分離し、他方の「０３」の子ノードからの受信確認情報は所定時間だけ経過しても届かないので、受信確認情報生成部３５は、所定時間の経過時に、ＭＡＣ生成部３３より与えられるＭＡＣと、既に与えられている他の全ての子ノード（ここでは「０２」のノードだけ）からの受信確認情報とを連結させたものに対してハッシュ関数を施したハッシュ値を、自身の受信確認情報として、ノードＩＤ付加部４０へ与え、ノードＩＤ付加部４０は、この受信確認情報（ハッシュ値）に、不達ノードＩＤ「０３」及び「０４」を連結させて、受信応答情報として送信部３８より親ノード（サーバ）に送信させる。
【００９３】
「第４段階Ｓ２０４（図１５）」
サーバ１Ｂは、受信確認情報検証部１４において、受信部１６より与えられる０以上の不達ノードＩＤが付加された受信確認情報から、受信確認情報と全ての不達ノードＩＤを分離する。
【００９４】
サーバ１Ｂは、受信確認情報検証部１４において、データ生成部１２より与えられるブロードキャストデータＸと、ノード情報管理部１３より与えられるノードＩＤ、ノード認証鍵、ルート情報と、抽出した不達ノードのＩＤより、隣接ノードから返信されるであろう受信確認情報を算出する。この際の受信確認情報の算出方法は、ツリー構造の各ノードが実行すると同様な処理を、エンドノード側からトップノードへかけて順次行うものである。
【００９５】
「第５段階Ｓ２０５（図１６）」
サーバ１Ｂは、受信確認情報検証部１４において、算出した受信確認情報と、受信部１６が受信した隣接ノードからの受信確認情報が一致するかどうかを検証する。
【００９６】
サーバ１Ｂは、検証結果が一致することで、不達ノードＩＤ管理部１７において不達ノードのＩＤを管理し、サーバ認証鍵管理部１１で管理するネットワーク内に認証鍵連鎖の未公開の次の鍵Ｋｉをネットワーク内に公開することを許可する。一方、検証結果が一致しないことで、鍵Ｋｉを公開することを許可しない。
【００９７】
「第６段階Ｓ２０６（図１６）」
サーバ１Ｂは、認証鍵連鎖の未公開の次の鍵Ｋｉを、送信部１５を介してネットワーク内に公開する。
【００９８】
「第７段階Ｓ２０７（図１７）」
ノード２Ｂは、受信部３７を介して受信した鍵をサーバ認証鍵検証部３６に与え、受信した鍵が、確かにサーバ１Ｂがネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを、受信した鍵に一方向性関数を施した結果が、既にサーバ認証鍵検証部３６にて保持するサーバ１Ｂが一番最近に公開した鍵と一致するかどうかを確かめることで検証する。
【００９９】
ノード２Ｂは、検証結果が一致することで、受信した鍵を、サーバ１Ｂがネットワーク内に未公開にしていた認証鍵連鎖の次の鍵であると認証し、受信データ保持部３１に保持するデータＸをサーバ１Ｂからの正しいデータであると認証する。また、認証した鍵を、サーバ１Ｂによって一番最近に公開された鍵としてサーバ認証鍵検証部３６に保持する。
【０１００】
（Ｂ−３）第２の実施形態の効果
第２の実施形態によれば、上述した第１の実施形態の効果に加え、以下の効果を奏することができる。
【０１０１】
第２の実施形態によれば、ノードの故障や、パケットロスなどの理由で、受信確認を応答しないノード２Ｂが存在する場合にも、サーバはそれらノードを、データが到達していない可能性のあるノードとして把握することができる。従って、例えば、サーバがネットワークに未公開の認証鍵連鎖の次の鍵を公開する前に、それらノードになんらかのアクションを起こすことが可能であるし、また、鍵を公開するとしても、それらノードにはなんらかの異常がある可能性があることをサーバは把握できる。
【０１０２】
（Ｃ）第３の実施形態
次に、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第３の実施形態を、図面を参照しながら説明する。
【０１０３】
第１及び第２の実施形態では、サーバにおける受信確認の検証が失敗したときには、サーバは認証鍵連鎖の次の未公開鍵を不用意に公開できない（公開すると攻撃者がサーバになりすますことが可能となる）ので、それ以降の動作が止まってしまう。
【０１０４】
そこで、例えば、サーバにおける受信確認の検証が失敗したときに、データを複数回再送して受信確認の検証結果が一致してから、鍵を公開するといったことをセキュアに実現したい。
【０１０５】
第３の実施形態では、サーバがブロードキャストするデータに、そのデータに対して、まだ公開していない認証鍵連鎖の次の鍵を用いて生成したＭＡＣを付加して発信する。そして、サーバが、（複数回）発信した情報に対するノードの受信確認を得た後に、ＭＡＣ生成に用いた鍵を公開し、ノードが既に受信したブロードキャストデータのうちでサーバからの正しいデータを認証することを特徴とする。
【０１０６】
（Ｃ−１）第３の実施形態の構成
図１８は、第３の実施形態のサーバ（ブロードキャストデータの送信装置）１Ｃの構成を示すブロック図であり、第１、第２の実施形態に係る図２、図１０との同一、対応部分には同一符号を付して示している。
【０１０７】
第３の実施形態のサーバ１Ｃは、サーバ認証鍵管理部１１、データ生成・保持部１８、ＭＡＣ生成・付加部１９、ノード情報管理部１３、受信確認情報検証部１４、不達ノードＩＤ管理部１７、送信部１５及び受信部１６を有する。第２の実施形態に比較すると、データ生成・保持部１８及びＭＡＣ生成・付加部１９が追加され、データ生成部１２が削除されており、サーバ認証鍵管理部１１、受信確認情報検証部１４、送信部１５の機能も多少異なっている。以下では、第２の実施形態と異なる構成要素について説明する。
【０１０８】
第３の実施形態のサーバ認証鍵管理部１１は、第２の実施形態のものと以下の点が異なっている。サーバ認証鍵管理部１１は、受信確認情報検証部１４より、検証結果一致のメッセージを受けて、ネットワーク内に未公開の次の認証鍵連鎖の鍵を送信部１５へ与え、管理下のノード２Ｃに公開する。そして、認証鍵連鎖の次の未公開の鍵をＭＡＣ生成・付加部１９へ与える。
【０１０９】
データ生成・保持部１８は、ブロードキャストするデータを生成・保持するものである。また、データ生成・保持部１８は、生成したブロードキャストデータを、ＭＡＣ生成・付加部１９へ与える。さらに、データ生成・保持部１８は、受信確認情報検証部１４より検証結果不一致のメッセージを受けて、保持するデータをＭＡＣ生成・付加部１９へ与える（データの再送）。但し、保持するデータの出力にあたり、データにはｎｏｎｃｅ（意味のないデータ）の付加などで以前に再送したデータと比べて新規性が確保されているものとする。
【０１１０】
ＭＡＣ生成・付加部１９は、サーバ認証鍵管理部１１より与えられる、認証鍵連鎖のネットワーク内に未公開の鍵を用いて、データ生成・保持部１８より与えられるブロードキャストデータに対するＭＡＣを生成・付加するものであり、ＭＡＣを付加したブロードキャストデータを、送信部１５と受信確認情報検証部１４へ与える。ＭＡＣ生成・付加部１９は、ＭＡＣ生成アルゴリズムを有し、例えば、ＡＥＳ暗号等のブロック暗号を用いたＣＢＣ−ＭＡＣである。
【０１１１】
第３の実施形態の受信確認情報検証部１４は、第２の実施形態に比較すると、ＭＡＣ生成・付加部１９よりＭＡＣを付加したブロードキャストデータを与えられ、そのデータに対する受信確認を行う点、受信確認の検証結果が一致しないことで、検証結果不一致のメッセージをデータ生成・保持部１８へ与える点などが異なっている。
【０１１２】
送信部１５は、ＭＡＣ生成・付加部１９より与えられるブロードキャストデータとＭＡＣを、管理下のノード２Ｃへブロードキャストするものである。また、送信部１５は、サーバ認証鍵管理部１１より与えられる、ネットワーク内に未公開の認証鍵連鎖の鍵を管理下のノード２Ｃへブロードキャストして公開するものである。
【０１１３】
図１９は、第３の実施形態のノード（ブロードキャストデータの受信装置）２Ｃの構成を示すブロック図であり、第１、第２の実施形態に係る図３、図１１との同一、対応部分には同一符号を付して示している。
【０１１４】
第３の実施形態のノード２Ｃは、受信データ保持部３１、自ノード認証鍵管理部３２、ＭＡＣ生成部３３、子ノード情報管理部３４、受信確認情報生成部３５、不達ノードＩＤ管理部３９、ノードＩＤ付加部４０、サーバ認証鍵検証部３６、受信データ認証部４１、受信部３７及び送信部３８を有する。
【０１１５】
第２の実施形態における構成（図１１）と異なる、受信データ保持部３１、ＭＡＣ生成部３３、サーバ認証鍵検証部３６、受信データ認証部４１、受信部３７についてのみ説明する。
【０１１６】
受信データ保持部３１は、受信部３７より与えられるサーバ１ＣのブロードキャストデータとＭＡＣを受信した順に保持しておくものである。また、受信データ保持部３１は、受信部３７より与えられたデータとＭＡＣをＭＡＣ生成部３３へ与える。さらに、受信データ保持部３１は、サーバ認証鍵検証部３６より検証成功メッセージを与えられて、保持するブロードキャストデータとそのＭＡＣを受信した順に受信データ認証部４１へ与える。
【０１１７】
ＭＡＣ生成部３３は、第２の実施形態のＭＡＣ生成部と異なる点は、受信データ保持部３１から、データとＭＡＣを与えられ、それらに対するＭＡＣを計算する点である。
【０１１８】
サーバ認証鍵検証部３６は、第２の実施形態のサーバ認証鍵検証部の機能に加え、受信した鍵をサーバ１Ｃが一番最近に公開した鍵であると認証することで、認証した鍵を受信データ認証部４１へ与える機能を有する。
【０１１９】
受信データ認証部４１は、受信したブロードキャストデータがサーバからの正しいデータであるかどうかを認証するものである。受信データ認証部４１は、ＭＡＣ生成アルゴリズムを有する。このＭＡＣ生成アルゴリズムは、サーバ１Ｃとの間で事前に決定されたものであり、サーバ１ＣがＭＡＣ生成・付加部１９に有するＭＡＣ生成アルゴリズムと同じものである。受信データ認証部４１は、受信データ保持部３１よりデータとそのＭＡＣを与えられ、そのデータに対して、サーバ認証鍵検証部３６より与えられたサーバの認証鍵を用いて生成したＭＡＣが、受信データ保持部３１より与えられたＭＡＣと等しいかどうかを検証する。また、受信データ認証部４１は、受信データ保持部３１より順番に与えられるデータのうち、一番初めにＭＡＣの検証結果が一致したデータを、サーバ１Ｃからの正しいデータであると認証し、それ以降のデータは破棄する。
【０１２０】
受信部３７は、サーバ１ＣからのブロードキャストデータとＭＡＣを受信データ保持部３１へ、子ノードからの０以上の不達ノードＩＤ付き受信確認情報を受信確認情報生成部３５へ、ネットワーク内に公開されたサーバ１Ｃの認証鍵をサーバ認証鍵検証部３６へ与えるものである。
【０１２１】
（Ｃ−２）第３の実施形態の動作
次に、第３の実施形態のメッセージ認証システムの動作（第３の実施形態のメッセージ認証方法）を、図２０〜図２３をも参照しながら説明する。ここで、第３の実施形態のメッセージ認証システムの動作は、大きくは、１０段階の動作（Ｓ３０１〜Ｓ３１０）でなっている。
【０１２２】
なお、以下では、説明の簡単化のために、ノードの故障やパケットロスなどによる受信確認を応答しないノード（不達ノード）が存在しない場合で説明する。そのような不達ノードが存在する場合は、下記の動作に、第２の実施形態の動作の項で示したような動作が追加される。
【０１２３】
「第１段階Ｓ３０１（図２０）」
サーバ１Ｃは、データ生成・保持部１８において、送信しようとするデータＤを生成・保持し、ＭＡＣ生成・付加部１９へ与える。ＭＡＣ生成・付加部１９において、サーバ認証鍵管理部１１より与えられるネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉ（サーバ１Ｃの認証鍵）を用いて、データＤに対するＭＡＣ（ＭＡＣＫｉ（Ｄ））を生成し、データＤに付加する。データＤにＭＡＣＫｉ（Ｄ）が付加されたものがブロードキャストデータＸとなる。
【０１２４】
「第２段階Ｓ３０２（図２０）」
サーバ１Ｃは、ブロードキャストデータＸを、送信部１５を介して管理下のノード２Ｃにブロードキャストする。
【０１２５】
「第３段階Ｓ３０３（図２０）」
ノード２Ｃは、受信部３７によって受信したブロードキャストデータＸを受信データ保持部３１に保持する。
【０１２６】
「第４段階Ｓ３０４（図２１）」
ノード２Ｃは、ＭＡＣ生成部３３において、受信データ保持部３１より与えられるブロードキャストデータＸと、自ノード認証鍵管理部３２により与えられる当該ノード２Ｃの認証鍵を入力して、受信データのＭＡＣを生成し、受信確認情報生成部３５へ与える。
【０１２７】
ノード２Ｃは、受信確認情報生成部３５において、子ノード情報管理部３４から与えられる情報より自身がエンドノードかルータノードかを判断する。エンドノードである場合には、ＭＡＣ生成部３３より与えられるＭＡＣに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報として送信部３８から親ノードに送信する。一方、ルータノードの場合には、受信部３７を通して全ての子ノードの受信確認情報が与えられることで、ＭＡＣ生成部３３より与えられるＭＡＣと全ての子ノードの受信確認情報とを連結させたものに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報として送信部３８から親ノードに送信する。
【０１２８】
「第５段階Ｓ３０５（図２１）」
サーバ１Ｃは、受信確認情報検証部１４において、ＭＡＣ生成・付加部１９より与えられるブロードキャストデータＸと、ノード情報管理部１３より与えられるノードＩＤ、ノード認証鍵、ルート情報から、隣接ノードから返信されるであろう受信確認情報を算出する。
【０１２９】
「第６段階Ｓ３０６（図２２）」
サーバ１Ｃは、受信確認情報検証部１４において、算出した受信確認情報と、受信部１６より受けた隣接ノードからの受信確認情報が一致するかどうかを検証する。サーバ１Ｃは、検証結果が一致することで、サーバ認証鍵管理部１１で管理するネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉをネットワーク内に公開することを許可する。一方、サーバ１Ｃは、検証結果が一致しないことで、第１段階の処理Ｓ３０１に戻り、データ生成・保持部１８において、保持するデータＤをＭＡＣ生成・付加部１９へ与える。但し、データＤの再送にあたり、データにはｎｏｎｃｅ（意味のないデータ）の付加などで新規性が確保されているものとする。
【０１３０】
「第７段階Ｓ３０７（図２２）」
サーバ１Ｃは、ネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを、送信部１５を通してネットワーク内に公開する。サーバ１Ｃは、鍵Ｋｉを公開することで、ネットワーク内に未公開の認証鍵連鎖の次の鍵Ｋｉ＋１をＭＡＣ生成・付加部１９に与える。
【０１３１】
「第８段階Ｓ３０８（図２３）」
ノード２Ｃは、受信部３７で受信した鍵Ｋｉをサーバ認証鍵検証部３６に与え、受信した鍵が、確かにサーバ１Ｃがネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを、受信した鍵に一方向性関数を施した結果が、既にサーバ認証鍵検証部３６にて保持するサーバが一番最近に公開した鍵Ｋｉ−１と一致するかどうかを確かめることで検証する。ノード２Ｃは、検証結果が一致することで、受信した鍵Ｋｉを、サーバがネットワーク内に未公開にしていた認証鍵連鎖の鍵であると認証し、その鍵をサーバによって一番最近に公開された鍵としてサーバ認証鍵検証部３６に保持する。
【０１３２】
「第９段階Ｓ３０９（図２３）」
ノード２Ｃは、受信データ認証部４１において、受信データ保持部３１から与えられたデータＤとＭＡＣＫｉ（Ｄ）を、サーバ認証鍵検証部３６より与えられた鍵Ｋｉを用いて、与えられた順に検証する。
【０１３３】
すなわち、受信データ保持部３１から与えられたデータＤに対し、今回受信した公開鍵Ｋｉを利用してＭＡＣを生成し、生成されたＭＡＣが、受信データ保持部３１から与えられたＭＡＣＫｉ（Ｄ）と一致するかを検証する。
【０１３４】
「第１０段階Ｓ３１０（図２３）」
ノード１Ｃは、最初に検証結果が一致したデータＤをサーバからの正しいデータであると認証する。それ以降のデータは破棄する。
【０１３５】
（Ｃ−３）第３の実施形態の効果
第３の実施形態によれば、既述した各実施形態の効果に加え、以下の効果を奏することができる。
【０１３６】
第３の実施形態によれば、サーバが受信確認の検証結果が一致するまでデータを複数回再送した場合でも、ノードが既に受信したデータのうちでサーバからの正しいデータを認証できる。
【０１３７】
ここで、第３の実施形態は、サーバが受信確認の検証に失敗した場合にだけブロードキャストデータを再送する場合に限定されず、受信確認の検証結果が一致した場合でも、サーバが、データが届いていない可能性があると把握しているノードに対して、データの再送を試みるときにも適用できる。
【０１３８】
（Ｄ）第４の実施形態
次に、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第４の実施形態を、図面を参照しながら説明する。
【０１３９】
第１〜第３の実施形態では、サーバによるブロードキャストデータの発信と、鍵の公開とを別に行うものであった。
【０１４０】
この第４の実施形態は、サーバからのブロードキャストデータの発信と、既に発信したデータをノードが認証するための認証鍵連鎖の鍵の公開を同時に行うことを特徴としている。
【０１４１】
（Ｄ−１）第４の実施形態の構成
図２４は、第４の実施形態のサーバ（ブロードキャストデータの送信装置）１Ｄの構成を示すブロック図であり、既述した実施形態に係る図面との同一、対応部分には同一符号を付して示している。
【０１４２】
第４の実施形態のサーバ１Ｄは、サーバ認証鍵管理部１１、データ生成・保持部１８、ＭＡＣ生成・付加部１９、鍵情報付加部２０、ノード情報管理部１３、受信確認情報検証部１４、サーバ認証鍵管理部１１、不達ノードＩＤ管理部１７、送信部１５及び受信部１６を有する。
【０１４３】
以下では、第３の実施形態における構成（図１８）と機能などが異なる、サーバ認証鍵管理部１１、ＭＡＣ生成・付加部１９、鍵情報付加部２０、受信確認情報検証部１４及び送信部１５について説明する。
【０１４４】
サーバ認証鍵管理部１１は、受信確認情報検証部１４より、検証結果一致のメッセージを受けて、ネットワーク内に未公開の次の認証鍵連鎖の鍵を公開することを決定し、その鍵を鍵情報付加部２０へ与え、この時点で公開することを決定していない認証鍵連鎖の次の未公開の鍵をＭＡＣ生成・付加部１９へ与える点が、第３の実施形態のものと異なっている。
【０１４５】
ＭＡＣ生成・付加部１９は、サーバ認証鍵管理部１１より与えられる、認証鍵連鎖のネットワーク内に未公開の鍵を用いて、データ生成・保持部１８より与えられるブロードキャストデータに対するＭＡＣを生成・付加するものであり、ＭＡＣを付加したブロードキャストデータを、鍵情報付加部２０へ与える点が、第３の実施形態のものと異なっている。
【０１４６】
鍵情報付加部２０は、ＭＡＣ生成・付加部１９より与えられる、ＭＡＣを付加したブロードキャストデータに、サーバ認証鍵管理部１１より与えられる管理下のノード２Ｄに公開することが決定した鍵情報を付加したものを、受信確認情報検証部１４と送信部１５へ与えるものである。
【０１４７】
受信確認情報検証部１４は、鍵情報付加部２０よりブロードキャストデータとそのＭＡＣと鍵情報を与えられ、そのデータに対する受信確認を行う点が、第３の実施形態のものと異なっている。
【０１４８】
送信部１５は、鍵情報付加部２０より与えられるブロードキャストデータとＭＡＣと鍵情報を、管理下のノード２Ｄへブロードキャストするものである。
【０１４９】
図２５は、第４の実施形態のノード２Ｄの詳細構成を示すブロック図を示しており、第３の実施形態に係る図１９との同一、対応部分には同一符号を付して示している。
【０１５０】
第４の実施形態のノード２Ｄも、構成要素は第３の実施形態のノード２Ｃと同様であるが、受信データ保持部３１、ＭＡＣ生成部３３、サーバ認証鍵検証部３６、受信部３７などの機能が第３の実施形態のものと異なっており、以下、これら要素について説明する。
【０１５１】
受信データ保持部３１は、以下の点が、第３の実施形態のものと異なっている。受信データ保持部３１は、サーバ認証鍵検証部３６よりブロードキャストデータとＭＡＣと鍵情報を与えられ、ブロードキャストデータとＭＡＣと鍵情報をＭＡＣ生成部３３へ与え、ブロードキャストデータとそのＭＡＣを与えられた順に保持しておくものである。また、受信データ保持部３１は、サーバ認証鍵検証部３６より検証結果一致のメッセージと、ブロードキャストデータとＭＡＣと鍵情報を与えられることで、それまでに保持していたブロードキャストデータとそのＭＡＣを受信した順に受信データ認証部４１へ与えて保持していたデータを消去し、サーバ認証鍵検証部３６より与えられたブロードキャストデータとＭＡＣと鍵情報をＭＡＣ生成部３３へ与え、ブロードキャストデータとそのＭＡＣを新規に保持しておくものである。
【０１５２】
ＭＡＣ生成部３３が、第３の実施形態のものと異なる点は、受信データ保持部３１から、データとＭＡＣと鍵情報を与えられ、それらに対するＭＡＣを計算する点である。
【０１５３】
サーバ認証鍵検証部３６は、以下の点が、第３の実施形態のものと異なっている。サーバ認証鍵検証部３６は、受信部３７よりブロードキャストデータとそのＭＡＣと鍵情報を与えられ、鍵情報を以下のように検証する。サーバ１Ｄが一番最近に公開した保持している鍵と、受信した鍵が同じであることをうけて、受信部３７より与えられたブロードキャストデータとそのＭＡＣと鍵情報を受信データ保持部３１へ与える。また、サーバ１Ｄが一番最近に公開した保持している鍵を用いて受信した鍵を検証し、受信した鍵が、サーバ１Ｄが一番最近に公開した鍵であると認証することで、検証結果一致のメッセージと、受信部３７より与えられたブロードキャストデータとそのＭＡＣと鍵情報を受信データ保持部３１へ与え、認証した鍵を受信データ認証部４１へ与える。受信した鍵が、上述した２つの場合に当てはまらないことで、受信部３７より与えられたブロードキャストデータとそのＭＡＣと鍵情報を破棄する。
【０１５４】
受信部３７は、サーバ１ＤからのブロードキャストデータとＭＡＣと鍵情報をサーバ認証鍵検証部３６へ、子ノードからの０以上の不達ノードＩＤ付き受信確認情報を受信確認情報生成部３５へ与えるものである。
【０１５５】
（Ｄ−２）第４の実施形態の動作
次に、第４の実施形態のメッセージ認証システムの動作（第４の実施形態のメッセージ認証方法）を、図２６〜図３０をも参照しながら説明する。ここで、第４の実施形態のメッセージ認証システムの動作は、大きくは、１０段階の動作（Ｓ４０１〜Ｓ４１０）でなっている。
【０１５６】
なお、以下では、説明の簡単化のために、ノードの故障やパケットロスなどによる受信確認を応答しないノード（不達ノード）が存在しない場合で説明する。そのような不達ノードが存在する場合は、下記の動作に、第２の実施形態の動作の項で示したような動作が追加される。
【０１５７】
「第１段階Ｓ４０１（図２６）」
サーバ１Ｄは、サーバ認証鍵管理部１１において認証鍵連鎖の次の未公開鍵Ｋｉを公開することを許可する。サーバ１Ｄは、データ生成・保持部１８においてデータＤｉ＋１を生成・保持し、ＭＡＣ生成・付加部１９へ与える。ＭＡＣ生成・付加部１９においては、サーバ認証鍵管理部１１より与えられるネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉ＋１（サーバの認証鍵）を用いて、データＤｉ＋１に対するＭＡＣ、すなわち、ＭＡＣＫｉ＋１（Ｄｉ＋１）を生成して付加し、鍵情報付加部２０へ与える。鍵情報付加部２０において、サーバ認証鍵管理部１１より与えられるネットワーク内に公開することが決定した認証鍵連鎖の鍵Ｋｉを付加する。
【０１５８】
以上のような処理により、ブロードキャストデータＸ＝Ｄｉ＋１‖ＭＡＣＫｉ＋１（Ｄｉ＋１）‖Ｋｉが生成されたことになる。
【０１５９】
「第２段階Ｓ４０２（図２６）」
サーバ１Ｄは、ブロードキャストデータＸを、送信部３８を通して管理下のノード２Ｄにブロードキャストする。
【０１６０】
「第３段階Ｓ４０３（図２７）
ノード２Ｄは、受信部３７によって受信したデータＸをサーバ認証鍵検証部３６に与え、データＸに含まれる公開鍵を抽出して検証する。
【０１６１】
ここで、サーバ認証鍵検証部３６で既に保持するサーバ１Ｄが一番最近に公開していた鍵Ｋｉ−１と、受信した鍵が同じである場合には、受信部３７より与えられたブロードキャストデータとそのＭＡＣと鍵情報を受信データ保持部３１へ与え、第６段階の処理Ｓ４０６へ進む。それ以外の場合には、第４段階の処理Ｓ４０４へ進む。
【０１６２】
「第４段階Ｓ４０４（図２７）」
ノード２Ｄは、受信した鍵が、確かにサーバ１Ｄがネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを、受信した鍵（正しい場合であればＫｉ）に一方向性関数Ｆ（・）を施した結果が、既にサーバ認証鍵検証部３６にて保持するサーバが一番最近に公開した鍵Ｋｉ−１と一致するかどうかを確かめることで検証する。
【０１６３】
受信した鍵が、サーバ１Ｄが一番最近に公開した鍵であると認証したことで、受信した鍵を、サーバ１Ｄがネットワーク内に未公開にしていた認証鍵連鎖の鍵であると認証できれば、その鍵をサーバによって一番最近に公開された鍵としてサーバ認証鍵検証部３６に更新保持する。また、検証結果一致のメッセージと、受信部３７より与えられたブロードキャストデータとそのＭＡＣと鍵情報を受信データ保持部３１へ与え、認証した鍵を受信データ認証部４１へ与える。
【０１６４】
受信した鍵が、サーバ１Ｄが一番最近に公開した鍵であると認証されないことで、受信部３７より与えられた、ブロードキャストデータとそのＭＡＣと鍵情報を破棄する。
【０１６５】
「第５段階Ｓ４０５（図２７）」
ノード２Ｄは、サーバ認証鍵検証部３６より検証結果一致のメッセージを受けることにより、受信データ保持部３１において、保持するデータを与えられた順に受信データ認証部４１に与え、受信データ認証部４１において、受信データ保持部３１から与えられたデータとＭＡＣを、サーバ認証鍵検証部３６より与えられた鍵Ｋｉを用いて、与えられた順に検証する。
【０１６６】
ノード２Ｄは、受信データ保持部３１において保持するデータを受信データ認証部４１に与えることで消去する。また、ノード２Ｄは、受信データ保持部３１から与えられたＭＡＣと、受信データ保持部３１から与えられたデータに対してサーバ認証鍵検証部３６より与えられた鍵を用いて生成したＭＡＣが一番初めに一致したデータをサーバからの正しいデータであると認証する。それ以降のデータは破棄する。
【０１６７】
「第６段階Ｓ４０６（図２７）」
ノード２Ｄは、サーバ認証鍵検証部３６より与えられたブロードキャストデータとそのＭＡＣと鍵情報とを新規に保持する。
【０１６８】
「第７段階Ｓ４０７（図２８）」
ノード２Ｄは、ＭＡＣ生成部３３において、受信データ保持部３１より与えられるブロードキャストデータＸと、自ノード認証鍵管理部３２により与えられる当該ノード２Ｄの認証鍵を入力して、受信データのＭＡＣを生成し、受信確認情報生成部３５へ与える。
【０１６９】
ノード２Ｄは、受信確認情報生成部３５において、子ノード情報管理部３４から与えられる情報より自身がエンドノードかルータノードかを判断する。エンドノードである場合には、ＭＡＣ生成部３３より与えられるＭＡＣに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報として送信部３８を通して親ノードに送信する。一方、ルータノードの場合には、受信部３７を通して全ての子ノードの受信確認情報が与えられることで、ＭＡＣ生成部３３より与えられるＭＡＣと全ての子ノードの受信確認情報とを連結させたものに対してハッシュ関数を施し、得られたハッシュ値を自身の受信確認情報として送信部３８を通して親ノードに送信する。
【０１７０】
「第８段階Ｓ４０８（図２８）」
サーバ１Ｄは、受信確認情報検証部１４において、ＭＡＣ生成・付加部１９より与えられるブロードキャストデータＸと、ノード情報管理部１３より与えられるノードＩＤ、ノード認証鍵、ルート情報から、隣接ノードから返信されるであろう受信確認情報を算出する。
【０１７１】
「第９段階Ｓ４０９（図２９）」
サーバ１Ｄは、受信確認情報検証部１４において、算出した受信確認情報と、受信部１６より受けた隣接ノードからの受信確認情報が一致するかどうかを検証する。
【０１７２】
サーバ１Ｄは、検証結果が一致することで、サーバ認証鍵管理部１１で管理するネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉをネットワーク内に公開することを許可する。この場合には、認証鍵連鎖の鍵Ｋｉを規定するパラメータｉを１インクリメントして、第１段階の処理Ｓ４０１へ戻る。
【０１７３】
サーバ１Ｄは、検証結果が一致しないことで、第１０段階の処理Ｓ４１０へ進む。
【０１７４】
「第１０段階Ｓ４１０（図３０）」
サーバ１Ｄは、データ生成・保持部１８において、保持するデータＤをＭＡＣ生成・付加部１９へ与える。但し、データＤの再送にあたり、データにはｎｏｎｃｅ（意味のないデータ）の付加などで新規性が確保されているものとする。
【０１７５】
ＭＡＣ生成・付加部１９において、サーバ認証鍵管理部１１より与えられるネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉ＋１（サーバの認証鍵）を用いて、データに対するＭＡＣ（＝ＭＡＣＫｉ＋１（Ｄｉ＋１））を生成して付加し、鍵情報付加部２０へ与える。
【０１７６】
鍵情報付加部２０において、サーバ認証鍵管理部１１より与えられるネットワーク内に一番最近に公開した認証鍵連鎖の鍵Ｋｉを付加する。そして、第２段階の処理Ｓ４０２へ戻る。
【０１７７】
（Ｄ−３）第４の実施形態の効果
第４の実施形態によれば、既述した各実施形態と同様な効果に加え、以下の効果を奏することができる。
【０１７８】
第４の実施形態によれば、サーバからのブロードキャストデータの発信と、既に発信したデータをノードが認証するための認証鍵連鎖の鍵の公開を同時に行うため、サーバからのデータ発信が連続しているような場合には、データ発信と鍵の公開を別々に行うよりも効率が良く実行できる。
【０１７９】
また、データと鍵の公開を同時に行い、それらに対する受信をサーバが確認することによって、サーバは現在自身が発信したデータが正しく届けられたことだけでなく、以前に届けた正しいデータを、ノードがサーバからの正しいデータであると認証したことも把握することができる。
【０１８０】
（Ｅ）第５の実施形態
次に、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第５の実施形態を、図面を参照しながら説明する。
【０１８１】
上述した第１〜第４の実施形態は、サーバが認証鍵連鎖の鍵を生成した順と逆順に１つずつ公開するのに対して、第５の実施形態は任意数おきに公開することを特徴とする。
【０１８２】
説明を簡単にするため、データのブロードキャストと鍵の公開は同時に行わない例（第３の実施形態に対して第５の実施形態の技術思想を追加適用した例）で説明する。また、サーバが認証鍵連鎖の鍵を一つおきに公開する例で説明する。
【０１８３】
（Ｅ−１）第５の実施形態の構成
第５の実施形態のサーバ１Ｅも、その内部構成を、第３の実施形態で説明した図１８で表すことができる。
【０１８４】
しかし、第５の実施形態のサーバ１Ｅは、サーバ認証鍵管理部１１、データ生成・保持部１８、ＭＡＣ生成・付加部１９、受信確認情報検証部１４、送信部１５及び受信部１６等の機能が第３の実施形態のものと多少異なっており、以下、これらの構成要素について説明する。
【０１８５】
サーバ認証鍵管理部１１は、以下の点が、第３の実施形態のものと異なっている。第５の実施形態のサーバ認証鍵管理部１１は、管理下のノード２Ｅに自身を証明するために、保持する認証鍵連鎖を生成した順と逆順で１つおきに公開する。サーバ認証鍵管理部１１は、受信確認情報検証部１４より、検証結果一致のメッセージを受けて、次に公開する認証鍵連鎖の鍵を送信部１６へ与え、管理下のノード２Ｅに公開する。そして、認証鍵連鎖上で次の未公開の鍵をＭＡＣ生成・付加部１９へ与える。
【０１８６】
データ生成・保持部１８は、以下の点が、第３の実施形態のものと異なっている。第５の実施形態のデータ生成・保持部１８は、ブロードキャストするデータと共にそのデータＩＤを生成・保持するものである。データＩＤはブロードキャストするデータの識別子であり、例えば、シーケンス番号などで表す。データ生成・保持部１８は、生成したブロードキャストデータとデータＩＤを、ＭＡＣ生成・付加部１９へ与える。また、データ生成・保持部１８は、受信確認情報検証部１４よりデータＩＤを受けて、保持するデータの中でそのデータＩＤに対応するデータとデータＩＤをＭＡＣ生成・付加部１９へ与える。
【０１８７】
ＭＡＣ生成・付加部１９には、以下の点が、第３の実施形態のものと異なっている。第５の実施形態のＭＡＣ生成・付加部１９は、サーバ認証鍵管理部１１より、認証鍵連鎖のネットワーク内に未公開の鍵を２つ与えられる。また、ＭＡＣ生成・付加部１９には、データ生成・保持部１８よりブロードキャストデータとデータＩＤを与えられる。さらに、ＭＡＣ生成・付加部１９は、送信部１５と受信確認情報検証部１４へ、ＭＡＣを付加したブロードキャストデータとデータＩＤを与える。さらにまた、ＭＡＣ生成・付加部１９は、サーバ認証鍵管理部１１より２個の鍵を与えられることで、データ生成・保持部１８より与えられる２つのブロードキャストデータに対して、それぞれＭＡＣを生成して付加する。
【０１８８】
受信確認情報検証部１４は、以下の点が、第３の実施形態のものと異なっている。第５の実施形態の受信確認情報検証部１４には、ＭＡＣ生成・付加部１９よりＭＡＣを付加したブロードキャストデータとデータＩＤを２組与えられ、受信部１６よりデータＩＤが付加された受信確認情報を与えられて、そのデータＩＤに対応するブロードキャストデータ（データＩＤ、データ、ＭＡＣ）に対する受信確認を行う。
【０１８９】
受信確認情報検証部１４は、受信確認情報に付加されているデータＩＤより、どのブロードキャストデータに対する受信確認情報であるかを判断する。受信確認の検証結果が一致しないことで、検証結果不一致のデータに対応するデータＩＤをデータ生成・保持部１８へ与える。
【０１９０】
送信部１５は、ＭＡＣ生成・付加部１９より与えられるデータＩＤとブロードキャストデータとＭＡＣを、管理下のノード２Ｅへブロードキャストする点が、第３の実施形態のものと異なっている。
【０１９１】
受信部１６は、受信確認情報と共にデータＩＤを受信確認情報検証部１４へ与える点が、  第３の実施形態のものと異なっている。
【０１９２】
第５の実施形態のノード２Ｅも、その内部構成を、第３の実施形態で説明した図１９で表すことができる。
【０１９３】
しかし、第５の実施形態のノード２Ｅは、受信データ保持部３１、ＭＡＣ生成部３３、受信確認情報生成部３５、ノードＩＤ付加部４０、サーバ認証鍵検証部３６、受信データ認証部４１、受信部３７及び送信部３８等の機能が第３の実施形態のものと多少異なっており、以下、これらの構成要素について説明する。
【０１９４】
受信データ保持部３１は、受信部３７より与えられたデータＩＤとデータとＭＡＣをＭＡＣ生成部３３へ与える点が、第３の実施形態のものと異なっている。
【０１９５】
ＭＡＣ生成部３３は、受信データ保持部３１から、データＩＤとデータとＭＡＣを与えられ、それらに対するＭＡＣを計算する点、データＩＤと生成したＭＡＣを受信確認情報生成部３５へ与える点が、第３の実施形態のものと異なっている。
【０１９６】
受信確認情報生成部３５は、以下の点が、第３の実施形態のものと異なっている。受信確認情報生成部３５は、ＭＡＣ生成部３３よりデータＩＤとＭＡＣの組を与えられ、それら情報を一時的に保持する。また、受信確認情報生成部３５は、受信確認情報に付加されているデータＩＤより、サーバ１Ｅから受信したどのデータに対する受信確認を生成する必要があるかを判断する。さらに、受信確認情報生成部３５は、受信部３７より与えられる子ノードの受信確認情報に付加されたデータＩＤに対応するＭＡＣを受信確認情報の生成に用いる。さらにまた、受信確認情報生成部３５は、データＩＤと生成した受信確認情報をノードＩＤ付加部４０へ与える。
【０１９７】
ノードＩＤ付加部４０は、以下の点が、第３の実施形態のものから異なっている。ノードＩＤ付加部４０には、受信確認情報生成部３５よりデータＩＤも与えられる。ノードＩＤ付加部４０は、与えられたデータＩＤを、０以上のノードＩＤを付加した受信確認情報に付加し、送信部３８へ与える。ノードＩＤ付加部４０によるデータＩＤの付加の仕方は、予めシステムによって決定されている。例えば、受信確認情報の先頭に任意長のデータＩＤビット配列を付加する形をとる。
【０１９８】
サーバ認証鍵検証部３６は、受信した鍵に対して２回一方向性関数を施し、その結果が既に保持する情報と等しいかどうかを確かめ、検証結果が一致することで、受信した鍵と、受信した鍵に対して１回一方向性関数を施した出力値を、受信データ認証部４１へ与える点が、第３の実施形態のものと異なっている。
【０１９９】
受信データ認証部４１は、サーバ認証鍵検証部３６より２つのサーバの認証鍵を与えられる点、受信データ保持部３１より順番に与えられるデータのうち、２つのサーバの認証鍵それぞれに対して、一番初めにＭＡＣの検証結果が一致したデータ２つを、サーバからの正しいデータであると認証し、それ以降のデータは破棄する点が、第３の実施形態のものと異なっている。
【０２００】
受信部３７は、サーバ１ＥからのデータＩＤとブロードキャストデータとＭＡＣを受信データ保持部３１へ、子ノードからのデータＩＤと０以上の不達ノードＩＤ付きの受信確認情報を受信確認情報生成部３５へ、ネットワーク内に公開されたサーバの認証鍵をサーバ認証鍵検証部３６へ与えるものである。
【０２０１】
送信部３８は、ノードＩＤ付加部４０より与えられるデータＩＤと０以上の不達ノードＩＤ付き受信確認情報を自身の親ノードに送信するものである。
【０２０２】
（Ｅ−２）第５の実施形態の動作
次に、第５の実施形態のメッセージ認証システムの動作（第５の実施形態のメッセージ認証方法）を、図３１〜図３４をも参照しながら説明する。ここで、第５の実施形態のメッセージ認証システムの動作は、大きくは、１０段階の動作（Ｓ５０１〜Ｓ５１０）でなっている。
【０２０３】
なお、以下では、説明の簡単化のために、ノードの故障やパケットロスなどによる受信確認を応答しないノード（不達ノード）が存在しない場合で説明する。そのような不達ノードが存在する場合は、下記の動作に、第２の実施形態の動作の項で示したような動作が追加される。また、以下の説明において、第３の実施形態と動作が同じところの説明をほぼ省略し、新しい動作の部分について重点的に説明する。
【０２０４】
「第１段階Ｓ５０１（図３１）」
サーバ１Ｅは、データ生成・保持部１８において、データＤｉ−１とデータ識別子ＩＤ（Ｄｉ−１）を生成・保持し、ＭＡＣ生成・付加部１９へ与える。ＭＡＣ生成・付加部１９において、サーバ認証鍵管理部１１より与えられるネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉ−１（サーバの認証鍵）を用いて、ＭＡＣＫｉ−１（Ｄｉ−１）を生成し、データＤｉ−１とデータ識別子ＩＤ（Ｄｉ−１）の組に付加する。これにより、ブロードキャストデータＸｉ−１＝ＩＤ（Ｄｉ−１）‖Ｄｉ−１‖ＭＡＣＫｉ−１（Ｄｉ−１）が生成されたことになる。
【０２０５】
同様にして、データＤｉとデータ識別子ＩＤ（Ｄｉ）についても、ネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを用いてＭＡＣＫｉ（Ｄｉ）が生成され、データＤｉとデータ識別子ＩＤ（Ｄｉ）の組に付加されて、ブロードキャストデータＸｉ＝ＩＤ（Ｄｉ）‖Ｄｉ‖ＭＡＣＫｉ（Ｄｉ）が生成される。
【０２０６】
「第２段階Ｓ５０２（図３１）」
サーバ１Ｅは、ブロードキャストデータＸｉ−１とブロードキャストデータＸｉとを、送信部１５を通して管理下のノード２Ｅにブロードキャストする。
【０２０７】
「第３段階Ｓ５０３（図３１）」
ノード２Ｅは、受信部３７によって受信したブロードキャストデータＸｉ−１とブロードキャストデータＸｉとを受信データ保持部３１に保持する。
【０２０８】
「第４段階Ｓ５０４（図３２）」
ノード２Ｅは、受信確認情報に、どのデータに対する受信確認情報であるかを示すためのデータＩＤ（ＩＤ（Ｄｉ−１）若しくはＩＤ（Ｄｉ））を付加する。ノード２Ｅは、付加されているデータＩＤに対応するＭＡＣを受信確認情報の生成に用いる。
【０２０９】
「第５段階Ｓ５０５（図３２）」
サーバ１Ｅは、返信された受信確認情報に付加されているデータＩＤより、どのデータに対する受信確認情報であるかを判断する。
【０２１０】
サーバ１Ｅは、発信した各データ（Ｄｉ−１、Ｄｉ）について返信されると想定される受信確認情報をそれぞれ算出する。
【０２１１】
「第６段階Ｓ５０６（図３３）」
発信した各データ（Ｄｉ−１、Ｄｉ）ともに検証結果が一致することで、サーバ認証鍵管理部１１で管理するネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを公開することを許可する。なお、検証結果が一致しないデータに関しては、第５段階の処理Ｓ５０１に戻り、再送を行う。
【０２１２】
「第７段階Ｓ５０７（図３３）」
サーバ１Ｅは、ネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを、送信部１５を通してネットワーク内に公開する。サーバ１Ｅは、鍵Ｋｉを公開することで、ネットワーク内に未公開の認証鍵連鎖の次の鍵Ｋｉ＋１とさらにその次の鍵Ｋｉ＋２をＭＡＣ生成・付加部１９に与える。
【０２１３】
「第８段階Ｓ５０８（図３４）」
ノード２Ｅは、受信した鍵をサーバ認証鍵検証部３６に与え、受信した鍵が、確かにサーバ１Ｅがネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを、受信した鍵に一方向性関数２回を施した結果が、既にサーバ認証鍵検証部３６にて保持するサーバ１Ｅが一番最近に公開した鍵Ｋｉ−２と一致するかどうかを確かめることで検証する。
【０２１４】
ノード２Ｅは、検証結果が一致することで、受信した鍵Ｋｉと受信した鍵に一方向性関数を１回施した出力値Ｋｉ−１を、サーバ１Ｅがネットワーク内に未公開にしていた認証鍵連鎖の鍵であると認証し、Ｋｉをサーバ１Ｅによって一番最近に公開された鍵としてサーバ認証鍵検証部３６に保持する。
【０２１５】
「第９段階Ｓ５０９（図３４）」
ノード２Ｅは、受信データ認証部４１において、受信データ保持部３１から与えられたデータとＭＡＣを、サーバ認証鍵検証部３６より与えられた鍵ＫｉとＫｉ−１を用いて、与えられた順に検証する。
【０２１６】
「第１０段階Ｓ５１０（図３４）」
ノード２Ｅは、鍵ＫｉとＫｉ−１それぞれに対して、一番最初に検証結果が一致したデータＤｉとＤｉ−１をサーバ１Ｅからの正しいデータであると認証する。それ以降のデータは破棄する。
【０２１７】
（Ｅ−３）第５の実施形態の効果
第５の実施形態によれば、既述した各実施形態と同様な効果に加え、以下の効果を奏することができる。
【０２１８】
第５の実施形態によれば、サーバは保持する認証鍵連鎖の鍵を生成した順と逆順に一つずつ公開するのではなく、予めシステムで決定した任意数ごとに公開し、ノードは鍵の公開を受けることで、複数のデータを認証する。その結果、サーバが１つの受信確認の検証が成功する毎に鍵を公開する場合に比べて、鍵を公開することで発生するネットワークの通信オーバヘッドを減少させることができる。
【０２１９】
また、第５の実施形態では、サーバが発信するデータと、ノードが返信する受信確認情報には、データＩＤが付加される。その結果、サーバが複数のデータを発信した場合でも、ノードはどのデータに対する受信確認を生成するかを判断でき、また、サーバが受信確認情報の返信を受けたときに、どのデータに対する受信確認を検証すれば良いかを把握できる。
【０２２０】
（Ｆ）第６の実施形態
次に、本発明によるメッセージ認証方法、通信端末装置及びメッセージ認証システムの第６の実施形態を、図面を参照しながら説明する。
【０２２１】
上述した第１〜第５の実施形態は、認証鍵連鎖の１つの鍵で１つのデータを認証するのに対して、第６の実施形態では認証鍵連鎖の１つの鍵で複数のデータを認証することを特徴とする。
【０２２２】
説明を簡単にするため、データのブロードキャストと鍵の公開は同時に行わない例で説明する。また、サーバが認証鍵連鎖の鍵を生成した順と逆順に一つずつ公開する例で説明する。
【０２２３】
（Ｆ−１）第６の実施形態の構成
図３５は、第６の実施形態のサーバ（ブロ一ドキャストデータの送信装置）１Ｇの構成を示すブロック図であり、既述した実施形態に係る図面との同一、対応部分には同一符号を付して示している。
【０２２４】
第６の実施形態のサーバ１Ｇは、サーバ認証健管理部１１、データ生成部１２、ＭＡＣ生成・付加部１９、送信済データ保持部２１、ノード情報管理部１３、受信確認情報検証部１４、不達ノードＩＤ管理部１７、送信部１５及び受信部１６を有する。
【０２２５】
以下では、第３の実施形態における構成（図１８）と機能などが異なる、サーバ認証鍵管理部１１、データ生成部１２、ＭＡＣ生成・付加部１９、送信済データ保持部２１、受信確認情報検証部１４、送信部１５及び受信部１６について説明する。
【０２２６】
サーバ認証鍵管理部１１は、第３の実施形態のものと比べて以下の点が異なっている。送信済データ保持部２１より、検証終了のメッセージを受けて、ネットワーク内に未公開の認証鍵連鎖の鍵を送信部１５へ与え、管理下のノード２Ｆに公開する。そして、この時点でネットワークに未公開の認証鍵連鎖の次の鍵をＭＡＣ生成・付加部１９へ与える。
【０２２７】
データ生成部１２は、ノード２Ｆに認証させたいデータを生成するものである。また、データ生成部１２は、認証鍵管理部１１で管理する認証鍵連鎖の各鍵で認証するデータの個数Ｚを決定するものである。データ生成部１２は、送信済データ保持部２１よりデータ検証終了のメッセージを受けることにより、次の認証鍵連鎖の鍵で認証するデータの個数Ｚを決定し、ＭＡＣ生成・付加部１９へ与える。また、データ生成部１２は、認証させたいデータをＺ個生成し、生成した各データとそのデータＩＤをＭＡＣ生成・付加部１９へ与える。データＩＤはデータを識別するものであり、例えばシーケンス番号を用いる。認証鍵連鎖の各鍵で認証するデータの個数Ｚは、認証鍵連鎖の各鍵ごとに決定して良く、システムによって予め決定しても良い。この第６の実施形態では、認証鍵連鎖の各鍵で認証するデータの個数Ｚを、認証鍵連鎖の各鍵ごとに決定する例で説明する。
【０２２８】
ＭＡＣ生成・付加部１９は、第３の実施形態のものと比べて以下の点が異なっている。第６の実施形態のＭＡＣ生成・付加部１９には、データ生成部１２より認証鍵連鎖の鍵を適用するデータの個数Ｚを与えられる。さらに、ＭＡＣ生成・付加部１９は、データ生成部１２より、データとそのデータＩＤを与えられることで、認証するデータの個数ＺとデータＩＤとデータに対してＭＡＣを生成・付加し、送信部１５と送信済みデータ保持部２１へ与える。
【０２２９】
送信済データ保持部２１は、ＭＡＣ生成・付加部１９より与えられた送信済データを保持するものである。送信済データは、認証するデータの個数ＺとデータＩＤとデータとＭＡＣから構成される。送信済データ保持部２１は、受信確認情報検証部１４よりデータＩＤを与えられることで、保持するデータの中でそのデータＩＤを含む送信済データを受信確認情報検証部１４へ返す。また、送信済データ保持部２１は、受信確認情報検証部１４より検証終了メッセージとデータＩＤを受けて、そのデータＩＤを含む送信済データを検証終了とする。さらに、送信済データ保持部２１は、受信確認情報検証部１４より再送要求メッセージとデータＩＤを受けて、そのデータＩＤを含む送信済データを送信部１５へ与える（再送）。さらに、送信済データ保持部２１は、ＭＡＣ生成・付加部１９より与えられたＺ個すべての送信済データに対して、検証終了メッセージを受けることで、検証終了のメッセージをデータ生成部１２とサーバ認証鍵管理部１１へ与える。
【０２３０】
受信確認情報検証部１４は、第３の実施形態のものと比べて以下の点が異なっている。第６の受信確認情報検証部１４は、受信部１６よりデータＩＤが付加された受信確認情報を与えられて、そのデータＩＤを送信済データ保持部２１へ与え、送信済データ保持部２１よりそのデータＩＤに対応する送信済データを得る。受信確認情報検証部１４は、送信済データ保持部２１より与えられた送信済データ（認証データ個数Ｚ、データＩＤ、データ）に対する受信確認を行う。受信確認情報検証部１４は、受信を確認できたノード２Ｆと受信を確認できなかったノード２Ｆを把握することにより、検証終了メッセージとデータＩＤ、又は、再送要求メッセージとデータＩＤを送信済データ保持部２１へ与える。検証終了メッセージを与えるか、再送要求メッセージを与えるかは、例えば、受信を確認できなかったノード２Ｆの個数（不達ノードの個数）に閾値を設けて判断する。また、受信確認の検証結果が不一致であることを受けて、再送要求メッセージとデータＩＤを送信済データ保持部２１へ与える。
【０２３１】
送信部１５は、ＭＡＣ生成・付加部１９若しくは送信済データ保持部２１より与えられる認証データ個数ＺとデータＩＤとデータとＭＡＣを管理下のノード２Ｆへ送信する点が、第３の実施形態のものと異なっている。
【０２３２】
受信部１６は、受信確認情報と共にデータＩＤを受信確認検証部１４へ与える点が、第３の実施形態のものと異なっている。
【０２３３】
第６の実施形態のノード２Ｆは、その内部構成を、第３の実施形態及び第５の実施形態で説明した図１９で表すことができる。
【０２３４】
しかし、第６の実施形態のノード２Ｆは、受信データ保持部３１、ＭＡＣ生成部３３、サーバ認証鍵検証部３６、受信データ認証部４１及び受信部３７等の機能が第５の実施形態のものと多少異なっており、以下、これらの構成要素について説明する。
【０２３５】
受信データ保持部３１は、以下の点が、第５の実施形態のものと異なっている。受信データ保持部３１は、受信部３７より与えられた認証データ個数ＺとデータＩＤとデータとＭＡＣを受信した順に保持し、ＭＡＣ生成部３３へ与える。また、受信データ保持部３１は、サーバ認証鍵検証部３６より検証成功メッセージを与えられて、保持する認証データ個数ＺとデータとＭＡＣを受信した順に受信データ認証部４１へ与える。
【０２３６】
ＭＡＣ生成部３３は、受信データ保持部３１から、認証データ個数ＺとデータＩＤとデータとＭＡＣを与えられ、それらに対するＭＡＣを計算する点が、第５の実施形態のものと異なっている。
【０２３７】
サーバ認証鍵検証部３６は、第３の実施形態のものと等しく、受信した鍵をサーバ１Ｆが一番最近に公開した鍵であると認証することで、認証した鍵を受信データ認証部４１へ与える。
【０２３８】
受信データ認証部４１は、以下の点が、第５の実施形態のものと異なっている。受信データ認証部４１には、受信データ保持部３１よりさらに認証するデータの個数Ｚが与えられる。受信データ認証部４１は、受信データ保持部３１より順番に与えられるデータのＭＡＣを検証し、検証結果が一致した最初のＺ個のデータを、サーバからの正しいデータであると認証し、それ以降のデータを破棄する。
【０２３９】
受信部３７は、サーバ１Ｆからの認証データ個数ＺとデータＩＤとデータとＭＡＣを受信データ保持部３１へ与える点が、第５の実施形態のものと異なっている。
【０２４０】
（Ｆ−２）第６の実施形態の動作
次に、第６の実施形態のメッセージ認証システムの動作（第６の実施形態のメッセージ認証方法）を、図３６〜図３９を参照しながら説明する。ここで、第６の実施形態のメッセージ認証システムの動作は、大きくは、１０段階の動作（Ｓ６０１〜Ｓ６１０）でなっている。
【０２４１】
なお、以下では、説明の簡単化のために、受信確認を応答しないノード（不達ノード）が存在しない場合で説明する。そのような不達ノードが存在する場合は、下記の動作に、第２の実施形態の動作の項で示したような動作が追加される。また、以下の説明において、第３の実施形態と動作が同じところの説明をほぼ省略し、新しい動作の部分について重点的に説明する。
【０２４２】
『第１段階Ｓ６０１（図３６）」
サーバ１Ｆは、データ生成部１２において、認証鍵連鎖の鍵Ｋｉを用いてノード２Ｆに認証させるデータの個数Ｚｉを決定する。また、データ生成部１２において、ノード２Ｆに認証させるＺｉ個のデータＤｉｍ（ｍ＝０，１，…，Ｚｉ−１）とそのデータ識別子ＩＤ（Ｄｉｍ）を生成し、決定した認証データの個数Ｚｉと共にＭＡＣ生成・付加部１９へ与える。ＭＡＣ生成・付加部１９において、サーバ認証鍵管理部１１より与えられるネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉ（サーバの認証鍵）を用いて、ＭＡＣＫｉ（Ｄｉｍ）を生成し、認証データの個数ＺｉとデータＤｉｍとデータ識別子ＩＤ（Ｄｉｍ）の組に付加する。これにより、ブロードキャストデータＸｉｍ＝Ｚｉ‖ＩＤ（Ｄｉｍ）‖Ｄｉｍ‖                            ＭＡＣＫｉ（Ｄｉｍ）が生成されたことになる。サーバ１Ｇは、生成したブロードキャストデータＸｉｍを送信部１５へ与えると共に、送信済データ保持部２１にて保持する。
【０２４３】
「第２段階Ｓ６０２（図３６）」
サーバ１Ｆは、ブロードキャストデータＸｉｍを送信部１５を通して管理下のノード２Ｆにブロードキャストする。
【０２４４】
「第３段階Ｓ６０３（図３６）」
ノード２Ｆは、受信部３７によって受信したブロードキャストデータＸｉｍを受信データ保持部３１に保持する。
【０２４５】
「第４段階Ｓ６０４（図３７）」
ノード２Ｆは、ブロードキャストデータＸｉｍに対する受信確認情報に、どのデータに対する受信確認情報であるかを示すためのデータ識別子ＩＤ（Ｄｉｍ）を付加する。また、ルータノード２Ｆは、子ノードから受信した受信確認情報に付加されているデータ識別子ＩＤ（Ｄｉｍ）に対応するＭＡＣを受信確認情報の生成に用いる。
【０２４６】
「第５段階Ｓ６０５（図３７）」
サーバ１Ｆは、返信された受信確認情報に付加されているデータ識別子ＩＤ（Ｄｉｍ）より、どのデータに対する受信確認情報であるかを判断し、送信済データ保持部２１より、そのデータ識別子ＩＤ（Ｄｉｍ）を含む送信済データを受けとる。サーバ１Ｆは、送信済データ保持部２１より受けたデータＸｉｍについて、返信されると想定する受信確認情報を算出する。
【０２４７】
「第６段階Ｓ６０６（図３８）」
サーバ１Ｆは、送信済データＸｉｍ（ｍ＝０，１，…，Ｚｉ−１）について受信を確認できたノードと受信を確認できなかったノードを把握することで、そのデータ識別子ＩＤ（Ｄｉｍ）と検証終了メッセージを送信済データ保持部２１へ与え、送信済データ保持部２１に保持するデータのうち与えられたデータ識別子ＩＤ（Ｄｉｍ）を含む送信済データＸｉｍを受信確認完了とする。サーバ１Ｆは、全ての送信済データＸｉｍについて受信を確認できたノードと受信を確認できなかったノードを把握することで、サーバ認証鍵管理部１１で管理するネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを公開することを許可し、また、データ生成部１２においてネットワーク内に未公開の認証鍵連鎖の次の鍵Ｋｉ＋１を用いて認証するデータの個数Ｚｉ＋１を決定することを許可する。なお、検証結果が一致しないデータと再送が必要と判断したデータに関しては、そのデータ識別子ＩＤ（Ｄｉｍ）と再送要求を送信済データ保持部２１に与え、再送を行う（第６段階の処理Ｓ６０２に戻る）。
【０２４８】
「第７段階Ｓ６０７（図３８）」
サーバ１Ｆは、ネットワーク内に未公開の認証鍵連鎖の鍵Ｋｉを、送信部１５を通してネットワーク内に公開する。サーバ１Ｆは、鍵Ｋｉを公開することで、ネットワーク内に未公開の認証鍵連鎖の次の鍵Ｋｉ＋１をＭＡＣ生成・付加部１９に与える。
【０２４９】
「第８段階Ｓ６０８（図３９）」
ノード２Ｆは、サーバ認証鍵検証部３６において、受信部３７で受信した鍵Ｋｉが確かにサーバ１Ｆがネットワーク内に未公開にしていた認証鍵連鎖の鍵であるかどうかを確かめる（第３の実施形態の動作例「第８段階Ｓ３０８」と等しいため省略する）。
【０２５０】
「第９段階Ｓ６０９（図３９）」
ノード２Ｆは、受信データ保持部３１に保持する認証データ個数ＺｉとデータＤｉｍとＭＡＣＫｉ（Ｄｉｍ）の組を、受信した順番に受信データ認証部４１に与え、受信データ認証部４１において、与えられたデータＤｉｍとＭＡＣＫｉ（Ｄｉｍ）を、サーバ認証鍵検証部３６に保持する鍵Ｋｉを用いて、与えられた順に検証する。
【０２５１】
「第１０段階Ｓ６１０（図３９）」
ノード２Ｆは、検証結果が一致したＺｉ個のデータをサーバ１Ｆからの正しいデータであると認証する。
【０２５２】
（Ｆ−３）第６の実施形態の効果
第６の実施形態によれば、既述した各実施形態と同様な効果に加え、以下の効果を奏することができる。
【０２５３】
第６の実施形態によれば、サーバ、又は、システムが認証鍵連鎖の各鍵で認証するデータの個数を規定し、ノードは認証鍵連鎖の１つの鍵で規定された複数のデータを認証する。その結果、サーバが認証鍵連鎖の１つの鍵で１つのデータを認証させる場合に比べて、認証鍵連鎖の使用効率が向上し、１つの認証鍵連鎖の使用期限をのばすことができる。
【０２５４】
（Ｇ）他の実施形態
上記各実施形態の説明においても、種々変形実施形態に言及したが、さらに以下に例示するような変形実施形態を挙げることができる。
【０２５５】
上記各実施形態では、説明の簡単化のため、サーバに隣接するノードが１つの場合で説明したが、この構成に限定されるものではない。サーバに複数のノードが隣接している場合でも、本発明を適用することができる。
【０２５６】
また、上記各実施形態では、説明の簡単化のため、サーバとノード間には直接のリンクがある例で説明したが、この構成に限定するものではない。センサネットワークの形態としては、図４０のようにサーバとノード間にゲートウェイとなるノードが存在するのが一般的である。図４０中のゲートウェイノードを、上記各実施形態でのサーバのように機能させても良く、図４０中のサーバがゲートウェイノードを経由してノードにデータを送信し、ゲートウェイノードを経由して受信確認情報を取り込むようにしても良い。
【０２５７】
データ発信者と受信確認情報検証者が互いに信頼できる関係であり、それらの間にセキュアなルートが構築されていれば、データ発信者と受信確認情報検証者は同じ端末でなくても良い。例えば、図４０中のゲートウェイノードがデータを送信し、受信した受信確認情報をサーバで検証してもらい結果の報告を受けるようにしても良い。
【０２５８】
上記各実施形態では、データをブロードキャストする場合を説明したが、マルチキャストする場合にも本発明を適用でき、この場合、第２の実施形態におけるような不達ノード情報が、送信先ノードでないものだけを含んでいることを妥当と捉えるようにすることもできる。また例えば、第３〜第５の実施形態で、サーバが、データが届いていないノードを把握できているときに、それらノードに対してデータを再送するときはマルチキャストするようにしても良い。
【０２５９】
また、上記各実施形態では、ノードが、受信した１データに対して受信確認を返信する場合で説明したが、複数のパケットに分割されたデータを全て受信した後で、受信確認を返信するようにしても良い。
【０２６０】
本発明におけるサーバでの受信確認方式は、上記実施形態のものに限定されるものではない。本発明は、データの受信確認方式（この方式は限定されない）と、認証鍵連鎖を用いたデータ認証を組み合わせて、サーバが発信したデータの受信を確認し、ノードが受信したデータをサーバからの正しいデータであると認証することを特徴の一つとしている。
【０２６１】
第３〜第５の実施形態では、認証鍵連鎖の鍵を用いてブロードキャストデータに対するＭＡＣを生成するものを示したが、認証鍵連鎖の鍵から派生した情報を用いてブロードキャストデータに対するＭＡＣを生成しても構わない。例えば、認証鍵連鎖の値に任意の暗号ハッシュ関数を施した出力値をＭＡＣ生成の鍵として用いることをシステムで予め決定していても良い。
【０２６２】
一般的に、ｏｎｅ−ｗａｙ  ｋｅｙ  ｃｈａｉｎの概念を利用したワンタイムパスワード方式では鍵切れの問題が存在するが、ｏｎｅ−ｗａｙ  ｋｅｙ  ｃｈａｉｎの概念をデータ認証に使用する上記各実施形態では、そのような問題は生じない。新たに別のｏｎｅ−ｗａｙ  ｋｅｙ  ｃｈａｉｎ（サーバの認証鍵連鎖）を生成し、ノードが、そのｏｎｅ−ｗａｙ  ｋｅｙ  ｃｈａｉｎを認証するのに用いる最初の鍵情報を、上記各実施形態で示したデータ認証方式でノードに認証させることで、上記鍵切れの問題を防止することができる。
【０２６３】
第５及び第６の実施形態では、ノードが受信した複数のデータそれぞれに対して受信確認を返信したが、この構成に限定するものではない。ノードは受信した複数のデータに対して受信確認をまとめて返す構成にしても良い。例えば、受信確認をまとめたデータの識別子全てを受信確認情報に付加することで容易に実現可能である。
【０２６４】
第５の実施形態では、サーバは保持する認証鍵連鎖の鍵を生成した順と逆順に、予めシステムで決定した任意数ごとに公開したが、この任意数はシステムによって予め決定されるものでなくても良い。例えば、認証鍵連鎖の各鍵に鍵連鎖番号を割り当て、ブロードキャストデータ送信時にはそのデータのＭＡＣ生成鍵の鍵連鎖番号を付加し、鍵の公開時には鍵と共にその鍵連鎖番号を付加することで、ノードは受信したデータが認証鍵連鎖の何番目の鍵でＭＡＣを付けられているか、また、公開された鍵は認証鍵連鎖の何番目の鍵かを容易に把握することができる。
【図面の簡単な説明】
【０２６５】
【図１】第１の実施形態のメッセージ認証システムに係るネットワークの構成例を示すと共に、サーバが管理するノード情報の説明図である。
【図２】第１の実施形態のサーバの詳細構成を示すブロック図である。
【図３】第１の実施形態のノードの詳細構成を示すブロック図である。
【図４】第１の実施形態のサーバの認証鍵（認証鍵連鎖）の概要を示す説明図である。
【図５】第１の実施形態のサーバの受信確認情報検証部での演算式の説明図である。
【図６】第１の実施形態のメッセージ認証システムの第１、第２段階の動作の説明図である。
【図７】第１の実施形態のメッセー認証システムの第３、第４段階の動作の説明図である。
【図８】第１の実施形態のメッセージ認証システムの第５、第６段階の動作の説明図である。
【図９】第１の実施形態のメッセージ認証システムの第７段階の動作の説明図である。
【図１０】第２の実施形態のサーバの詳細構成を示すブロック図である。
【図１１】第２の実施形態のノードの詳細構成を示すブロック図である。
【図１２】第２の実施形態のサーバの受信確認情報検証部での演算式の説明図である。
【図１３】第２の実施形態のメッセージ認証システムの第１、第２段階の動作の説明図である。
【図１４】第２の実施形態のメッセー認証システムの第３段階の動作の説明図である。
【図１５】第２の実施形態のメッセージ認証システムの第４段階の動作の説明図である。
【図１６】第２の実施形態のメッセージ認証システムの第５、第６段階の動作の説明図である。
【図１７】第２の実施形態のメッセージ認証システムの第７段階の動作の説明図である。
【図１８】第３の実施形態のサーバの詳細構成を示すブロック図である。
【図１９】第３の実施形態のノードの詳細構成を示すブロック図である。
【図２０】第３の実施形態のメッセージ認証システムの第１〜第３段階の動作の説明図である。
【図２１】第３の実施形態のメッセージ認証システムの第４、第５段階の動作の説明図である。
【図２２】第３の実施形態のメッセージ認証システムの第６、第７段階の動作の説明図である。
【図２３】第３の実施形態のメッセージ認証システムの第８〜第１０段階の動作の説明図である。
【図２４】第４の実施形態のサーバの詳細構成を示すブロック図である。
【図２５】第４の実施形態のノードの詳細構成を示すブロック図である。
【図２６】第４の実施形態のメッセージ認証システムの第１、第２段階の動作の説明図である。
【図２７】第４の実施形態のメッセージ認証システムの第３〜第６段階の動作の説明図である。
【図２８】第４の実施形態のメッセージ認証システムの第７、第８段階の動作の説明図である。
【図２９】第４の実施形態のメッセージ認証システムの第９段階の動作の説明図である。
【図３０】第４の実施形態のメッセージ認証システムの第１０段階の動作の説明図である。
【図３１】第５の実施形態のメッセージ認証システムの第１〜第３段階の動作の説明図である。
【図３２】第５の実施形態のメッセージ認証システムの第４、第５段階の動作の説明図である。
【図３３】第５の実施形態のメッセージ認証システムの第６、第７段階の動作の説明図である。
【図３４】第５の実施形態のメッセージ認証システムの第８〜第１０段階の動作の説明図である。
【図３５】第６の実施形態のサーバの詳細構成を示すブロック図である。
【図３６】第６の実施形態のメッセージ認証システムの第１〜第３段階の動作の説明図である。
【図３７】第６の実施形態のメッセージ認証システムの第４、第５段階の動作の説明図である。
【図３８】第６の実施形態のメッセージ認証システムの第６、第７段階の動作の説明図である。
【図３９】第６の実施形態のメッセージ認証システムの第８〜第１０段階の動作の説明図である。
【図４０】本発明のメッセージ認証システムを適用可能なネットワークの他の構成例を示す説明図である。
【符号の説明】
【０２６６】
１、１Ｂ、１Ｃ、１Ｆ…サーバ、２、２Ｂ、２Ｃ…ノード、１１…サーバ認証鍵管理部、１２…データ生成部、１３…ノード情報管理部、１４…受信確認情報検証部、１５…送信部、１６…受信部、１７…不達ノード管理部、１８…データ生成・保持部、１９…ＭＡＣ生成・付加部、２０…鍵情報付加部、２１…送信済データ保持部、３１…受信データ保持部、３２…自ノード認証鍵管理部、３３…ＭＡＣ生成部、３４…子ノード情報管理部、３５…受信確認情報生成部、３６…サーバ認証鍵検証部、３７…受信部、３８…送信部、３９…不達ノード管理部、４０…ノードＩＤ付加部、４１…受信データ認証部。
【図１】
2006157856.tif 000003
【図２】
2006157856.tif 000004
【図３】
2006157856.tif 000005
【図４】
2006157856.tif 000006
【図５】
2006157856.tif 000007
【図６】
2006157856.tif 000008
【図７】
2006157856.tif 000009
【図８】
2006157856.tif 000010
【図９】
2006157856.tif 000011
【図１０】
2006157856.tif 000012
【図１１】
2006157856.tif 000013
【図１２】
2006157856.tif 000014
【図１３】
2006157856.tif 000015
【図１４】
2006157856.tif 000016
【図１５】
2006157856.tif 000017
【図１６】
2006157856.tif 000018
【図１７】
2006157856.tif 000019
【図１８】
2006157856.tif 000020
【図１９】
2006157856.tif 000021
【図２０】
2006157856.tif 000022
【図２１】
2006157856.tif 000023
【図２２】
2006157856.tif 000024
【図２３】
2006157856.tif 000025
【図２４】
2006157856.tif 000026
【図２５】
2006157856.tif 000027
【図２６】
2006157856.tif 000028
【図２７】
2006157856.tif 000029
【図２８】
2006157856.tif 000030
【図２９】
2006157856.tif 000031
【図３０】
2006157856.tif 000032
【図３１】
2006157856.tif 000033
【図３２】
2006157856.tif 000034
【図３３】
2006157856.tif 000035
【図３４】
2006157856.tif 000036
【図３５】
2006157856.tif 000037
【図３６】
2006157856.tif 000038
【図３７】
2006157856.tif 000039
【図３８】
2006157856.tif 000040
【図３９】
2006157856.tif 000041
【図４０】
2006157856.tif 000042