(57)【特許請求の範囲】
【請求項１】
メッセージと、メッセージ認証コードに従うキーからタグ値を判定するために前記メッセージを通信デバイスが処理する方法であって、
前記通信デバイスの処理ユニットが、複数のシンボルの１つを選択するステップであって、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定する、ステップと、
前記通信デバイスの処理ユニットが、前記選択されたシンボルとなる前記タグ値を判定するステップと、
前記通信デバイスの処理ユニットが、第１通信チャネルを介して受信側の通信デバイスへ、少なくともメッセージへの寄与を通信するステップと、
前記通信デバイスの処理ユニットが、前記第１通信チャネルとは異なる第２通信チャネルを介して、前記受信側の通信デバイスへ、前記タグ値及び前記キーの少なくとも一方を通信するステップとを備え、
前記タグ値は、前記キーによって判定される時点で前記誤り訂正コードを定義する多項式を評価することによって判定される
ことを特徴とする方法。
【請求項２】
前記メッセージから導出される前記データ要素は、前記メッセージを構成する
ことを特徴とする請求項１に記載の方法。
【請求項３】
更に、前記通信デバイスの処理ユニットが、前記メッセージから算出される一方向ハッシュ関数のハッシュ値となる前記データ要素を判定するステップを備える
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記キーは、ユーザ対話を介在して通信するのに十分に短い
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記タグ値は、有限フィールド内の要素である
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記第２通信チャネルは、ユーザ対話を含んでいる
ことを特徴とする請求項１に記載の方法。
【請求項７】
データメッセージを通信するための通信デバイスであって、前記通信デバイスは、メッセージと、メッセージ認証コードに従うキーからタグ値を判定するように適合されている処理手段を備え、前記処理手段は、以下のように
複数のシンボルの１つを選択し、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定し、
前記選択されたシンボルとなる前記タグ値を判定し、
第１通信チャネルを介して受信側の通信デバイスへ、少なくともメッセージへの寄与を通信し、
前記第１通信チャネルとは異なる第２通信チャネルを介して、前記受信側の通信デバイスへ、前記タグ値及び前記キーの少なくとも一方を通信する
ように適合されていて、
前記タグ値は、前記キーによって判定される時点で前記誤り訂正コードを定義する多項式を評価することによって判定される
ことを特徴とする通信デバイス。
【請求項８】
メッセージと、メッセージ認証コードに従うキーからタグ値を判定するために前記メッセージを通信デバイスが処理する方法であって、
前記通信デバイスの処理ユニットが、複数のシンボルの１つを選択するステップであって、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定する、ステップと、
前記通信デバイスの処理ユニットが、前記選択されたシンボルとなる前記タグ値を判定するステップと、
前記通信デバイスの処理ユニットが、第１通信チャネルを介して受信側の通信デバイスへ、少なくともメッセージへの寄与を通信するステップと、
前記通信デバイスの処理ユニットが、前記第１通信チャネルとは異なる第２通信チャネルを介して、前記受信側の通信デバイスへ、前記タグ値及び前記キーの少なくとも一方を通信するステップとを備え、
前記誤り訂正コードは、リード−ソロモンコードであり、前記タグ値は、前記キーによって判定される時点でリード−ソロモンエンコーディング多項式を評価することによって判定される
ことを特徴とする方法。
【請求項９】
データメッセージを通信するための通信デバイスであって、前記通信デバイスは、メッセージと、メッセージ認証コードに従うキーからタグ値を判定するように適合されている処理手段を備え、前記処理手段は、以下のように
複数のシンボルの１つを選択し、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定し、
前記選択されたシンボルとなる前記タグ値を判定し、
第１通信チャネルを介して受信側の通信デバイスへ、少なくともメッセージへの寄与を通信し、
前記第１通信チャネルとは異なる第２通信チャネルを介して、前記受信側の通信デバイスへ、前記タグ値及び前記キーの少なくとも一方を通信する
ように適合されていて、
前記タグ値は、前記キーによって判定される時点で前記誤り訂正コードを定義する多項式を評価することによって判定される
ことを特徴とする通信デバイス。
【請求項１０】
請求項１、３及び８のいずれか１項に記載のステップのすべてをコンピュータに実行させるためのコンピュータプログラム。
【請求項１１】
請求項１、３及び８のいずれか１項に記載のステップのすべてをコンピュータに実行させるためのプログラムを記憶したコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野
本発明は、メッセージ認証コード（message authentication code）に従うタグ値を判定するためのメッセージの処理に関するものである。
【０００２】
本発明の背景
データ保全性（integrity）及び信頼性は、任意のセキュアデータ通信システムにおいて基本的に期待されるものであり、このシステムは、変更することが許可されていない何者かによって情報が変更されないことを補償する。無線通信環境においては、通信データの敵対的な傍受及び、かつ変更の可能性に対して、取り分けて高いリスクがある、つまり、保全性保護及び認証に対する要求が取り分けて存在する。
【０００３】
データ保全性は、メッセージ認証コード（ＭＡＣ）によって提供される。ＭＡＣは、データ通信ペイロードの保全性保護に対して使用される、これは、大量のデータでさえコンピュータで効率的に保護する方法を提供する。
【０００４】
ＭＡＣは、送信側（送信機：sender）と受信側（受信機:receiver）との間での対称（共通：symmetric）共有シークレットに基づいている。このシークレット値は、キーと呼ばれる。このシークレットキーは、ＭＡＣ算出への１つの入力変数であり、また、保護対象のメッセージは別の入力である。ＭＡＣ算出は、タグ値として参照される保全性チェック値を出力する。正しいシークレットキーを処理するものだけが、与えられるメッセージに対するタグ値を算出することができる。従来の自動保全性保護環境においては、算出されたタグ値は、メッセージとタグ値を通信チャネルを介して受信先へ送信する前に、そのメッセージに付加される。ＭＡＣによって保護されているメッセージの受信においては、受信側は、受信データと共有シークレットキーに基づいて、対応するタグ値を算出する。算出されたタグ値が、受信タグ値と等しい場合、メッセージは認証されたものとして受け入れられる。周知のＭＡＣの例には、いわゆる、メッセージ認証用キー化ハッシング（ＨＭＡＣ）アルゴリズムがあり、これは、暗号技術における一方向性ハッシュ関数に基づいていて、これには、セキュアハッシュアルゴリズムＳＨＡ−１及びメッセージダイジェストアルゴリズムＭＤ５がある。
【０００５】
手動の認証スキームでは、算出されたタグ値は、送信メッセージに付加される必要はない。このようなスキームでは、そのタグ値は、そのメッセージを送信するデバイスによって、かつそのメッセージを受信するデバイスによって算出することができる。次に、ユーザは、算出されたタグ値を比較する、あるいは算出されたタグ値を、比較のために、あるデバイスから他のデバイスへ手動で送信する。同様にして、いくつかのアプリケーションでは、ＭＡＣは、データ要素の保全性チェックを実行するために使用することができ、このデータ要素は、２つの異なるデバイスによって別々に生成されたものである。従って、この状況では、データ要素は、送信側から受信側へは送信されない、つまり、タグ値は、送信前にデータに付加される必要はない。
【０００６】
シー．  ゲールマン及びケイ．  ネイバーグによる、論文「ブルートゥース帯域幅セキュリティへの拡張」、ノルディックサイエンス議事録  ２００１、コペンハーゲン  ２００１年１１月（C. Gehrmann and K. Nyberg, "Enhancements to the Bluetooth baseband security", Proceedings of the Nordsec 2001, Copenhagen, November 2001）では、ディフィ−ヘルマン（Diffie-Hellman）共有シークレットによる手動認証スキームの一例を記載している、これは、通信リンクを介して共有シークレットを通信することなく、２つのデバイスによって事前に生成されたものである。この方法は、中間者（man-in-the-middle）は、ディフィ−ヘルマンキー交換が存在している場合に、確立されたデフィ−ヘルマンキーが正当なデバイス内で異なって存在しているという前提に基づいている。この方法に従えば、生成された共有シークレットは、シークレットキーを手動で交換し、生成された共有シークレットとシークレットキーからメッセージ認証コードのタグ値を算出し、かつ生成されたタグ値を手動で比較することによって、生成された共有シークレットが認証される。
【０００７】
ユーザ対話が介在する、このような状況では、タグ値長を短く維持することが要望されている、これは、ユーザ実用性によるタグ値の比較あるいは転送を行うためである、即ち、このような手動の比較を必要とする時間を削減し、かつ誤りのリスクを削減するためである。
【０００８】
ジー．  カバチアンスキ、ビー．  スミーツ及びティー  ヨハンソンによる、「誤り訂正コードを介する体系的Ａコードの濃度」  ＩＥＥＥ  会報  情報理論、ＩＴ−４２、ページ５６６−５７８、１９９６年（On the cardinality of systematic A-codes via error correcting codes", IEEE Transaction on Information theory, vol. IT-42, pp. 566-578,1996）では、メッセージ認証コードと誤り訂正コード間の関係を記載していて、また、誤り訂正コードに基づくＭＡＣ構造を開示していて、ここで、このコードは、等価のクラスに分類される、そうすることで、一定でないコードワード（codeword）のすべてが単一のコードワードに置き換えられる、これによって、新規のコード、いわゆる、ファクタコードを生成する。そして、タグ値が、２つのキーに基づいて、そのファクタコードのシンボルから算出される。
【０００９】
本発明の要約
本発明の目的は、メッセージ認証コードのタグ値を提供することであり、このメッセージ認証コードは、小さいタグサイズで、かつ小さいキーサイズに対する、高レベルの偽装保護を提供する。
【００１０】
上述及び他の目的は、メッセージと、メッセージ認証コードに従うキーからタグ値を判定するためにメッセージを処理する方法によって達成され、この方法は、、
−複数のシンボルの１つを選択し、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定し、
−前記選択されたシンボルとなる前記タグ値を判定する。
【００１１】
上述の方法は、小さいタグサイズ及び小さいキーサイズに対してさえ、高レベルの偽装セキュリティを提供することが、本発明者によって実現されている。
【００１２】
更なる効果は、誤り訂正コードのコードワードのシンボルとしてタグ値を直接選択することによって、効率的にコンピュータによって算出される（computationally）ＭＡＣ構成が提供されることである。
【００１３】
一実施形態では、メッセージから導出されるデータ要素は、メッセージ自身である。従って、一実施形態では、メッセージは、誤り訂正コードへの入力として直接使用される。
【００１４】
別の実施形態では、メッセージから導出されるデータ要素は、メッセージから算出される一方向ハッシュ関数のハッシュ値である、これによって、メッセージサイズを削減し、かつ、同一レベルのセキュリティを維持しながら、キーのサイズ及びタグ値のサイズの少なくとも一方の更なる削減を可能にする。
【００１５】
更なる効果は、セキュリティが、ＭＡＣ関数として、ロングハッシュコードでのハッシュ関数が使用される場合にコンピュータで算出されるセキュリティに依存するのではなく、ＭＡＣ関数の絶対的なセキュリティに基づいていることである。
【００１６】
特に、上述及び後述のＭＡＣ構成は、ショートタグ値及びショートキー、即ち、１０〜１５の桁、文字及び他のシンボル、例えば、４〜６の１６進文字の少なくともいずれかの長さより小さい長さを有するタグ及びキーに対してさえも偽装確率を十分に低くする、これによって、ユーザは、タグ値の通信及び比較の少なくとも一方を実行することができる。
【００１７】
本説明のために、メッセージという用語は、任意のデジタルデータ要素を備えることを意図し、これは、その保全性及び信頼性の少なくとも一方が検証されるものである。メッセージの例には、例えば、無線通信リンクを介して、送信側から受信側へ送信されるデータ要素や、異なるデバイスによって別々に生成されるあるいは協働して生成されるデータ要素及びその類を含んでいる。
【００１８】
一実施形態では、少なくともメッセージに対する寄与は、第１通信チャネルを介して送信側から受信側へ通信され、タグ値と、オプションとして、キーが第１チャネルとは別の第２通信チャネルを介して通信される。一実施形態では、第２通信チャネルはユーザ対話が介在する。
【００１９】
例えば、メッセージ全体が通信されても良く、あるいは、いくつかの実施形態では、通信に関与する各デバイスが、最終メッセージに対する寄与を生成し、かつその寄与をそれぞれの他のデバイスへ送信することができる。両方のデバイスが最終メッセージを生成する。この場合、１つ以上の送信された寄与及び最終メッセージの少なくとも一方は、上述及び以下の方法によって検証することができる。
【００２０】
更なる実施形態が、従属請求項で開示される。
【００２１】
上述及び以下の方法の特徴は、ソフトウェアで実現されても良く、また、データ処理システムあるいは、コンピュータ実行可能命令の実行によって生じる他の処理手段で実現されても良い。この命令は、記憶媒体あるいはコンピュータネットワークを介する別のコンピュータから、ＲＡＭのようなメモリにロードされるプログラムコード手段であっても良い。選択的には、上述の特徴は、ソフトウェアに代える固定配線回路、あるいはそれをソフトウェアとの組合わせによって実現されても良い。
【００２２】
本発明は、様々な方法で実現することができ、これには、上述及び以下の方法、通信デバイス及び更なる製造手段があり、これらは、最初に説明される方法とともに説明される１つ以上の利益及び効果をもたらす、また、これらはそれぞれ、最初に説明される方法とともに説明され、かつ従属請求項で開示される実施形態に対応する１つ以上の実施形態を持っている。
【００２３】
本発明は、更に、データメッセージを通信するための通信デバイスに関するものであり、この通信デバイスは、メッセージと、メッセージ認証コードに従うキーからタグ値を判定するために適合されている処理手段を備え、この処理手段は、以下のように
−複数のシンボルの１つを選択し、前記複数のシンボルは、前記メッセージから導出されるデータ要素をエンコーディングするコードワードを生成し、前記コードワードは、誤り訂正コードに従って前記データ要素をエンコーディングし、前記キーは、前記複数のシンボルの内の１つのどれが選択されるかを判定し、
−前記選択されたシンボルとなる前記タグ値を判定する
ように適合されている。
【００２４】
通信デバイスという用語は、例えば、無線通信信号のような通信信号の受信及び送信の少なくとも一方を実行するための適切な回路を備える任意のデバイスを意味するものであり、これは、データ通信を容易にする。このようなデバイスの例は、ポータブル無線通信機器及び他のハンドヘルドあるいはポータブルデバイスを含んでいる。ポータブル無線通信機器には、移動電話、ページャー、コミュニケータ、即ち、電子オーガナイザー、スマート電話、パーソナルデジタルアシスタント（ＰＤＡ）、ハンドヘルドコンピュータあるいはその類のようなあらゆる機器が含まれる。
【００２５】
通信デバイスの更なる例には、ステーショナリー通信機器が含まれ、これには、例えば、ステーショナリーコンピュータあるいは、無線通信インタフェースを含む他の電子機器がある。一実施形態では、この通信デバイスの１つとしては、ネットワークデバイス、例えば、コンピュータネットワーク、例えば、ＬＡＮへの無線アクセスを提供するコンピュータネットワークのアクセスポイントであっても良い。
【００２６】
ここで、処理手段という用語は、上述の機能を実行するように適切に適合されている任意の回路及びデバイスの少なくとも一方を意味するものである。特に、上述の用語は、汎用あるいは専用プログラマブルマイクロプロセッサ、デジタル信号処理（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、プログラマブル論理アレイ（ＰＬＡ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、専用電子回路等、あるいはそれらの組み合わせを意味するものである。
【００２７】
実施形態の詳細説明
図１は、ユーザ対話が介在するメッセージ認証環境の例のフロー図を示している。このメッセージ認証環境は、通常は、Ａ及びＢで示される２つのデバイスが関与する。参照番号１０１で示される左側のフロー図は、デバイスＡによって実行され、一方、参照番号１０２で示される右側のフロー図は、デバイスＢによって実行される。
【００２８】
図１の例では、両方のデバイスは、それぞれボックス１０３及び１０９によって示されるメッセージｄを記憶している。例えば、メッセージｄは、一方のデバイスによって生成して、他方のデバイスに送信することができる、選択的には、両方のデバイスは、１つ以上の他のデバイスからメッセージｄを受信することができる、あるいはそれらは、互いに協働して、及び／あるいは、第３のデバイスと協働してメッセージを生成することができる。
【００２９】
両方のデバイスが同一のメッセージを記憶していることを検証するために、初期ステップ１０４では、デバイスＡは、例えば、適切なシークレットストリング長で、適切なキー空間から選択される、キーｋを生成する。ステップ１０５では、デバイスＡは、生成されたキーを、例えば、無線通信リンクあるいは、２つのデバイス間での適切な別のデータ接続を介して、デバイスＢへ送信する。ステップ１１０では、デバイスＢは、そのキーを受信する。以下では、デバイスＢで受信されたキーを、ｋ’として参照する。
【００３０】
ステップ１０６では、デバイスＡは、デバイスＡによって記憶されているメッセージｄと、入力としてデバイスＡによって生成されるキーｋを使用するＭＡＣ関数のタグ値ｔを算出する。同様に、ステップ１１１では、デバイスＢは、デバイスＡと同一のＭＡＣ関数に対応するタグ値ｔ’を、受信したキーｋと、入力としてデバイスＢに記憶されるメッセージｄを使用して算出する。
【００３１】
ステップ１０７では、デバイスＡは、算出されたタグ値ｔと、生成されたキーｋを、デバイスＡのユーザに対して表示する。同様に、ステップ１１２では、デバイスＢは、デバイスＢによって算出されたタグ値ｔ’と、受信したキーｋ’を、デバイスＢのユーザに対して表示する。ユーザ（群）は、表示されたタグ値が等しいかどうか、即ち、ｔ＝ｔ’であるかどうかを判定するために、それらを比較する。例えば、デバイス同士が互いに近接している状態にある場合は、ユーザは、表示されたタグ値を直接比較することができる。デバイス同士が互いに離れて存在している場合には、デバイスＡのユーザは、デバイスＡからタグ値ｔとキーｋを読み出し、例えば、電話あるいは他の通信手段によって、そのタグ値とキーをデバイスＢのユーザに対して通信することができる、そうすることで、デバイスＢのユーザは、デバイスＢによって表示されたタグ値ｔ’とキーｋ’との比較を実行することができる。
【００３２】
ステップ１０８及び１１４では、デバイスＡ及びＢのユーザ（群）はそれぞれ、上述の比較結果を、タグ値とキーが等しい場合には、例えば、ＯＫボタンを押下することによって入力する、また、これらの値が等しくない場合は、ＣＡＮＣＥＬボタンを押下することによって入力する。
【００３３】
認証の結果のユーザ入力には、別の様々な実施形態が実現できることが理解される。例えば、ユーザには、デバイスの一方だけに結果を入力することを要求することができる。更にまた別の実施形態では、ユーザが所定時間期間内にＯＫボタンを押下しない場合には、デバイスは、認証が成功しなかったと見なしてもよい。
【００３４】
タグ値とキーが等しい場合、２つのデバイスに記憶されているメッセージｄが正常に認証され、かつデバイスＡとＢは、自身それぞれのメッセージの処理を継続することができる。このように、図１の認証環境は、破線矢印１１４によって示されるユーザ対話が介在する、これは、ユーザが、表示された値を比較し、かつデバイスの比較結果を示すからである。
【００３５】
図２は、ユーザ対話が介在するメッセージ認証環境の別の例のフロー図を示している。ここでは、このメッセージ認証環境は、２つのデバイスＡ及びＢが関与し、参照番号２０１で示される左側のフロー図のステップは、デバイスＡによって実行され、一方、参照番号２０２で示される右側のフロー図のステップは、デバイスＢによって実行される。
【００３６】
上述の例のように、両方のデバイスは、それぞれボックス１０３及び１０９によって示されるメッセージｄを記憶している。両方のデバイスが同一のメッセージが記憶しているかを検証するために、初期ステップ１０４では、デバイスＡは、キーｋを生成する。
【００３７】
ステップ２０５では、デバイスＡは、デバイスＡによって記憶されているメッセージｄと、入力としてデバイスＡによって生成されるキーｋを使用するＭＡＣ関数のタグ値ｔを算出する。
【００３８】
ステップ２０６では、デバイスＡは、生成されたキーｋと、算出されたタグ値ｔを、デバイスＡのユーザに対して表示する。例えば、これらの値は、２つの異なる値として表示されても良い、あるいは１つのストリングに連結されて表示されても良い。
【００３９】
デバイスＡのユーザは、表示された値（群）を読み出し、デバイスＢへ入力する（ステップ２０８）。例えば、ユーザは、デバイスＢのキーボードあるいはキーパッド、あるいは任意の他の適切な入力デバイスを介してその値を入力することができる。例えば、デバイス同士が、互いに離れて存在している場合、デバイスＡのユーザは、例えば、電話あるいは他の通信手段によって、それらの値（群）をデバイスＢのユーザに対して通信することができる、そうすることで、デバイスＢのユーザは、デバイスＢにそれら値をデバイスＢに入力することができる。
【００４０】
次のステップ２０９では、デバイスＢは、デバイスＡと同一のＭＡＣ関数に対応するタグ値ｔ’を、入力したキーｋと、入力としてデバイスＢに記憶されるメッセージｄを使用して算出する。
【００４１】
ステップ２１０では、デバイスＢは、算出されたタグ値ｔ’と、デバイスＢのユーザによって入力されたタグ値ｔとを比較する。タグ値が等しい場合、メッセージｄは正常に認証される（ステップ２１１）、そうでない場合、メッセージｄは破壊されているものとして拒否される（ステップ２１２）。一実施形態では、デバイスＢは、ユーザのデバイスへ対応するメッセージを表示することができる、これは、認証結果を示すものである。選択的には、あるいはこれに加えて、デバイスＢは、対応するメッセージをデバイスＡに送信することができる。
【００４２】
ここでも、図２の認証環境は、破線矢印２１３で示されるユーザ対話が介在する。
【００４３】
このように、上述では、ユーザ対話が介在する認証環境の２つの例が説明される。上述の環境では、ＭＡＣ関数に入力される少なくとも１つのキーｋと、ＭＡＣ関数によって算出されるタグ値ｔは読み出される、及び／あるいはユーザによって入力される。ユーザは、例えば、電話を介して、別のユーザへ値を通信することが更に必要とされる場合がある。従って、上述及び同様の環境では、認証スキームによって提供されるセキュリティを低下させることなく、タグ値のサイズとキー長を維持することが要求される。
【００４４】
更に、上述の環境は、単なる例示を示していて、また、ユーザ対話が介在するいくつかの他の認証スキームが存在することが理解される。例えば、一実施形態では、キーｋは、第３のデバイスによって生成され、デバイスＡ及びＢに通信されても良い、あるいはキーは、ユーザ、例えば、ＰＩＮ番号によって生成されて、両方のデバイスに入力されても良い、あるいは、キーは、２つのデバイスに対してハードコード化されていても良いし、あるいはその類がなされても良い。また、キーと、可能であれば、タグ値は、実際の認証に先立ってデバイスＡによって算出されても良い。例えば、デバイスＡは、デバイスＡによるメッセージｄの生成とともに、キー及びタグ値を生成しても良い。更に別の実施形態では、通信されるパラメータ、即ち、図１のキーｋあるいは図２のキー及びタグは、デバイスＡから第３のデバイスに通信されても良い、ここで、この第３のデバイスは、デバイスＢからアクセス可能である。例えば、デバイスＢがコンピュータネットワークのネットワークデバイスである場合、上述のパラメータは、そのコンピュータネットワークの別のコンピュータに通信することができる、ここで、これらのパラメータは、デバイスＢに記憶されておて、連続して検索することができる。
【００４５】
図３は、誤り訂正コードに基づくメッセージ認証コードを算出する方法のフロー図を示している。図３の例では、データ空間Ｄからのデータ要素ｄは、メッセージ認証コード（ＭＡＣ）を使用する認証対象であると想定し、このメッセージ認証コードは、例えば、図１のステップ１０６及び１１１、あるいは図２のステップ２０５及び２０９で示されるものである。この例のために、データ要素ｄは、メッセージとしても参照する。
【００４６】
一般的に、ＭＡＣは、データ空間Ｄとキー空間Ｋからタグ空間Ｃへのマッピングｆである、即ち、ｆ：Ｄ×Ｋ→Ｃである、ここで、メッセージｄ∈Ｄとキーｋ∈Ｋは、タグｔ∈Ｃへマッピングされる、即ち、（ｄ，ｋ）→ｔである。
【００４７】
ＭＡＣは、メッセージの保全性を保護するために使用される、即ち、例えば、メッセージの送信側からメッセージの受信側への送信中に、データが変更されないことを補償するために使用される。手動認証では、ショートＭＡＣ値が使用される、即ち、１０〜１５の桁、文字、他のシンボルの少なくともいずれかより小さい長さのタグが使用される、これによって、ユーザに、タグ値を通信すること及び比較することの少なくとも一方を可能にする。このような手動認証スキームでは、セキュリティは、コンピュータ的なセキュリティではなく、ＭＡＣ関数の絶対的な（unconditional）セキュリティに基づいている。例えば、ロングハッシュコードを備えるハッシュ関数がＭＡＣ関数として使用される場合、セキュリティは、コンピュータ的なセキュリティに基づいている。
【００４８】
ＭＡＣ関数の絶対的なセキュリティは、異なるタイプの可能性のある攻撃を考慮することによって判定される。２つの主なタイプは、偽装（impersonation）攻撃と置換（substitution）攻撃がある。以下の説明の理解を容易にするために、これらのタイプの攻撃について、本明細書において簡単に説明する。より詳細な説明は、ジー．  カバチアンスキ、ビー．  スミーツ及びティー  ヨハンソンによる、「誤り訂正コードを介する体系的Ａコードの濃度」  ＩＥＥＥ  会報  情報理論、ＩＴ−４２、ページ５６６−５７８、１９９６年（On the cardinality of systematic A-codes via error correcting codes", IEEE Transaction on Information theory, vol. IT-42, pp. 566-578,1996,）を参照されたい、これは、そのすべてを参照することによって本明細書に組み込まれる。
【００４９】
偽装攻撃では、攻撃者は、正当な送信側と受信側間のデータ交換を事前に観測することなく、データが正当な送信側から送信されていることを受信側に信用させる試行を行う。一方、置換攻撃においては、攻撃者は、いくつかのデータｄを観測し、次に、その観測したデータをいくつかの他のデータｄ’≠ｄに置き換える。偽装攻撃及び置換攻撃を成功させるための攻撃者の確率は、それぞれＰIとＰSで示され、これは、以下のように表現することができる。
【００５０】
0004664206.tif 000002
【００５１】
例えば、以下の図７で説明されるキー交換プロトコルの構成では、観測されたデータｄを他のデータｄ’へ置換するための攻撃者の確率は、キー交換方法のセキュリティに関連する測定値である、即ち、キー交換中に送信されるパブリックキーを別のパブリックキーに置換するための確率である。この状況では、ｄ’が受信側に有効データとして受け入れられる場合に、攻撃者は成功する。短距離無線通信環境、例えば、ブルートゥースでは、両方のデバイスは、物理的に互いに近接していて、かつ、データの受信だけに制限されている、これは、両方のデバイスが、レディ状態にあることを示す信号を発信している場合である。ここで、このような状況では、偽装攻撃は容易に回避することができるので、置換攻撃の確率は、セキュリティにより関連する測定値に関係するものとして見なしても良い。また、多くの手動認証環境では、ＭＡＣ関数によって算出されるタグ値は、データが送信される通信リンクとは異なる別の通信チャネルを介して通信される。これは、標準的なＭＡＣ環境とは対照的である、ここで、データ及びタグ値の両方が一緒に送信され、かつこれらは、攻撃者によって観測される可能性がある。これらを前提とすると、置換攻撃の成功確率は、以下のように表現することができる。
【００５２】
0004664206.tif 000003
【００５３】
ここで、キーがキー空間Ｋからランダムで一律に選択されるとすると、上述の確率は、次のように表現することができる。
【００５４】
0004664206.tif 000004
【００５５】
ここで、｜・｜は、濃度セット、即ち、｜Ｋ｜は、Ｋの濃度であり、上述の式の分子は、ｄ及びｄ’に対して同一のＭＡＣ関数を生成するキー空間Ｋ内のすべてのキーのセットの濃度である。従って、上述の式から、高いセキュリティを提供するために、ＭＡＣ関数ｆの衝突確率は低くするべきである。
【００５６】
ＭＡＣ構成の以下の例は、誤り訂正コードに基づいている。この説明のために、有限フィールドＦqに渡る誤り訂正コードを想定する。特に、Ｆqに渡るコードワード長ｎのｑ−元コード（q-ary code）を想定し、これをＶで示す。一般的には、このコードは、メッセージからコードワードへのマッピングであり、そうすることで、各メッセージは固有のコードワードに対応し、かつそれぞれのコードワードはいくつかのシンボルを構成する。従って、コードＶは、ベクトルｖ∈Ｖ＝｛ｖ(d)：ｄ∈Ｄ｝のすべてを構成し、ここで、ｖ(d)＝（ｖ1(d)，ｖ2(d)，．．．，ｖn(d)、即ち、ｖi(d)＝Ｆqは、コードワードｖ(d)のシンボルである。
【００５７】
２つのｑ−元のｎ組（タプル：tuple）のｘ及びｙ間のハミング距離ｄH（ｘ，ｙ）は、同一ではないｎ組のコンポーネント数である、即ち、ｄH（ｘ，ｙ）＝｜｛ｉ∈｛１，．．．，ｎ｝：ｘi≠ｙi｝｜である。コードＶの最小距離は、
【００５８】
0004664206.tif 000005
【００５９】
である。即ち、コードＶのすべてのコードワード間の最小距離である。
【００６０】
図３を参照すると、誤り訂正コードに基づくＭＡＣ構成の実施形態が説明される、即ち、図３は、図１、図２及び図７それぞれのサブプロセス１０６、１１１、２０５、２０９、７１４の任意のものの実施形態のフロー図である。
【００６１】
初期ステップ３０１では、ＭＡＣ構成に対する入力データが提供される、即ち、認証対象のメッセージｄとＭＡＣ関数の入力として使用されるキーｋが提供される。一実施形態では、キーは、シンボル、桁（digit）、文字あるいはその類のストリングあっても良い。好ましくは、キーは、１０〜１５未満のシンボルから構成され、より好ましくは、７シンボル未満、例えば、４〜６の１６進文字を構成する。
【００６２】
ステップ３０２では、インデックスｉ∈｛１，．．．，ｎ｝が、キーｋの関数ｇ、即ち、ｉ＝ｇ（ｋ）として選択される。特に、キー空間Ｋがｎ要素である場合、即ち、｜Ｋ｜＝ｎである場合、各ｋは固有にシンボルインデックスの１つにマッピングされる、各インデックスは、１つのキーに対応する。一実施形態では、キーは直接インデックス、即ち、ｉ＝ｋとして使用される。
【００６３】
ステップ３０３では、タグ値ｔは、コードＶのコードワードＶ(d)のｉ番目のシンボルとして判定される、このコードＶは、メッセージｄに対応する、即ち、
【００６４】
0004664206.tif 000006
【００６５】
に対応する。
【００６６】
ここで、タグ値は、誤り訂正コードのコードワードの選択されるシンボルとして判定され、コードワードはメッセージに対応するコードワードであり、また、シンボルは、キーによって特定される。その結果、上述の例では、ＭＡＣは、ｎに等しいキー空間サイズと、コーディング空間サイズに等しいメッセージ空間を用いて取得される。また、上述の置換攻撃に対する確率Ｐsは、次のように与えられる。
【００６７】
0004664206.tif 000007
【００６８】
図４ａ〜ｂは、リード−ソロモンコードに基づいてメッセージ認証コードを算出する方法の例のフロー図である。
【００６９】
リード−ソロモン（ＲＳ）コードという用語は、誤り訂正コードのタイプを示しており、ここで、コードワードは、生成多項式を用いる多項式除算を介して定義される、これは、アイ．エス．  リード及びジー．  ソロモンによる、「有限フィールド上の多項式コード」、応用数理学会、８号、ページ３００〜３０４、１９６０年（l. S. Reed and G. Solomon,"Polynomial Codes over Certain Finite Fields", journal of Soc. Ind. Appl. Math. , vol. 8, pp. 300- 304,1960）を参照されたい、これは、参照することによって、その全体が本明細書に組み込まれる。リード−ソロモンコードという用語は、更に、リード−ソロモンコード、例えば、いわゆる、規格化リード−ソロモンコードを構成することも意図されるものである。
【００７０】
図４ａの構成では、初期ステップ４０１では、ＭＡＣ構成に対する入力データが提供される、即ち、図３で上述したように、認証対象のメッセージｄとＭＡＣ関数の入力として使用されるキーｋが提供される。
【００７１】
ステップ４０２では、メッセージは、Ｆq上のｑ−元のτ組（タプル）として表現される、即ち、ｄ＝ｄ0、ｄ1，．．．，ｄτ-1として表現され、ここで、ｄi∈Ｆqである。従って、メッセージに対応するリード−ソロモン（ＲＳ）エンコーディング（符号化）多項式は、以下のように定義される。
【００７２】
0004664206.tif 000008
【００７３】
ステップ４０３では、ＭＡＣのタグ値は、キーｋで特定される点での多項式を評価することによって算出される、即ち、
【００７４】
0004664206.tif 000009
【００７５】
となる。
【００７６】
ここで、キーｋは、リード−ソロモンコードのシンボルを特定し、これは、タグ値として使用される。上述のように、シンボルは、キーの適切な関数によって特定されても良いことが理解される。
【００７７】
更に、この構成では、キーは、有限フィールドＦq、即ち、ｋ∈Ｆqから選択されることに注意する。その結果、この構成は、以下の属性を持っている、ｎ＝ｑ＝｜Ｋ｜及び｜Ｄ｜＝ｑτ＝ｎτとなる。上述のコードの最小距離は、ｄH（Ｖ）＝ｎ−τ＋１である、つまり、置換攻撃の成功確率は、ＰS＝（τ−１）／ｎである。リード−ソロモンコードの利点は、これらが、最小距離が大きいロングコードであることである、これによって、高いセキュリティを提供する。
【００７８】
上述の内容は、更に、確率ＰSが、メッセージ空間Ｄのサイズが大きくなることを意味するものである。
【００７９】
図４ｂは、リード−ソロモンコードに基づくＭＡＣ構成の別の実施形態のフロー図を示している。
【００８０】
ここで、この構成に従えば、初期ステップ４０４では、ＭＡＣ構成に対する入力データが提供される、即ち、認証対象のメッセージｄとＭＡＣ関数の入力として使用されるキーｋが提供される。
【００８１】
ステップ４０５では、一方向ハッシュ関数ｈがメッセージに適用される。この説明のために、一方向ハッシュ関数という用語は、データ要素、例えば、ストリングを入力として取得し、かつ固定長バイナリ値（ハッシュ）を出力として生成するアルゴリズムを意味するものである。特に、このプロセスは不可逆である、即ち、生成されているデータ要素を検出時には、与えられるハッシュ値は、コンピュータで実行できないようにされるべきである。同様に、同一のハッシュ値を生成する２つの任意のデータ要素を検出することも、コンピュータで実行できないようにされるべきである。適切なハッシュ関数の例には、標準セキュアハッシュアルゴリズムＳＨＡ−１がある。このＳＨＡ−１アルゴリズムは、２６４ビット長未満のメッセージを取得して、１６０−ビットのメッセージダイジェストを生成する。一方向ハッシュ関数の他の例には、ＭＤ４、ＭＤ５及びその類が含まれる。ハッシュ関数δ＝ｈ（ｄ）の出力は、リード−ソロモンコードへの入力として使用される。一実施形態では、ハッシュ関数の出力は、メッセージサイズを更に効果的に削減するために切り捨てられる。
【００８２】
従って、ステップ４０６では、ハッシュ値δは、Ｆq上のｑ−元のτ組（タプル）として表現される、即ち、δ＝δ0，δ1，．．．，δτ-1であり、ここで、δi∈Ｆqである。
【００８３】
ステップ４０７では、ＭＡＣのタグ値ｔは、キーｋによって特定される点の、対応するリード−ソロモンエンコーディング多項式を評価することによって算出される、即ち、
【００８４】
0004664206.tif 000010
【００８５】
である。
【００８６】
ここで、ＳＨＡ−１のような一方向ハッシュ関数をメッセージにまず適用することによって、メッセージ空間のサイズが削減される、これによって、キー長あるいはＭＡＣの出力長、即ち、タグ長を著しく大きくすることなく、置換攻撃の成功確率ＰSを低下させる。その結果、ショートキー及びショートメッセージタグに対してさえ安全な認証が提供される、これによって、人間の対話が介在するキー及びメッセージタグの通信を可能にする。
【００８７】
図５は、図４ａ〜ｂのＭＡＣ構成のいくつかの構成例に対する置換攻撃の成功確率を示すテーブルを示している。ｌｏｇ2｜Ｄ｜で示される第１列は、ビット数で示されるメッセージのサイズである、ｌｏｇ2（ｎ）で示される第２列はビット数によるキーサイズを示している、一方、最後の列は、対応する置換攻撃の成功確率を示している。例えば、４桁の１６進数のコード長と、４桁のキーサイズ（ｎ＝ｑ＝１６4）からなるコードは、１２８ビット長のメッセージに対して、２-13〜２-16の間の偽装確率となる。従って、１２８ビットに切り捨てられるＳＨＡ−１出力と、１６進数で４ビットのキーサイズとコードサイズは、十分に高いセキュリティをもたらす。キーサイズを５桁（ｌｏｇ2（ｎ）＝２０）に増やす場合、この偽装確率は、２-17あるいはそれ未満に更に低下する。
【００８８】
図６は、Ａ及びＢで示される２つの通信デバイスを含む通信システムのブロック図を示している。通信デバイスＡと通信デバイスＢは、通信リンク６０５を介して互いに通信する。
【００８９】
通信デバイスＡは、処理ユニット６０２、その処理ユニットに接続されている無線通信ユニット６０３、その処理ユニットに接続されている記憶媒体６０４、その処理ユニットに接続されているユーザインタフェース６０６を備えている。
【００９０】
無線通信ユニット６０３は、処理ユニット６０２から受信したデータを、無線リンク６０５を介して通信デバイス６０７へ送信し、その通信デバイス６０７は、無線リンクからデータを受信し、それらを処理ユニットへ転送する。例えば、無線通信ユニット６０３は、ブルートゥース技術に基づいていても良く、また、２．４５ＧＨｚのＩＳＭ帯で送信／受信することができる。
【００９１】
処理ユニット６０２、例えば、適切なプログラム化マイクロプロセッサは、通信デバイスＡによって実現される機能に従って、他のデバイスから受信したデータを処理し、また、他のデバイスへの送信対象のデータを処理する。特に、処理ユニット６０２は、上述のセキュリティ機能、特に、上述のキー及び対応するＭＡＣ関数のタグ値の生成を実行するために適切にプログラムされている。
【００９２】
記憶媒体６０４は、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリあるいはその類であり、これは、キーｋを記憶するとともに、上述のメッセージ認証で必要なパラメータを記憶するように適合されている。
【００９３】
ユーザインタフェース６０６は、生成されたキーＫ及び対応するタグ値ｔを表示するためのディスプレイを備え、そうすることで、ユーザは、生成された値を読み取り、かつそれらを通信デバイスＢへ送信することができる。加えて、ユーザインタフェース６０６は、データ入力手段を備えていても良く、これには、例えば、キーボード、キーパッド、ポインティングデバイス、タッチスクリーンあるいはその類がある。
【００９４】
通信デバイスＢは、処理ユニット６０９、その処理ユニットに接続されている無線通信ユニット６０８、その処理ユニットに接続されている記憶媒体６１０、その処理ユニットに接続されているユーザインタフェース６１１を備えている。
【００９５】
無線通信ユニット６０９は、通信装置Ａの無線通信ユニット６０３に対応する、これによって、無線通信デバイスＡとＢ間の無線通信を可能にする。
【００９６】
処理ユニット６０９は、通信デバイスによって実現される機能に従って、他のデバイスから受信したデータを処理し、また、他のデバイスへの送信対象のデータを処理する。特に、処理ユニットは、上述のセキュリティ機能、特に、上述の認証方法及び対応するデバイスＡによって実現される認証メカニズムを実行するために適切にプログラムされている。
【００９７】
同様に、記憶媒体６０４は、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリあるいはその類であり、これは、キーｋとタグ値ｔを記憶するように適合されている。
【００９８】
ユーザインタフェース６１１は、入力デバイスを備え、これには、例えば、キーパッド、キーボード、タッチスクリーンあるいはその類があり、これは、ユーザに、キーｋと、通信デバイスＡによって生成される、キーｋと対応するタグ値ｔを入力することを可能にする。加えて、ユーザインタフェースは、ディスプレイ、ポインティングデバイス、及びその類の少なくとも１つを備えていても良い。
【００９９】
このように、図６の通信システムは、２つの通信デバイス、例えば、２つのポータブル通信デバイスを備えていて、これには、例えば、２つの移動電話、移動電話とポータブルコンピュータ、２つのポータブルコンピュータ、あるいは、上述の方法に従ってメッセージ認証を実行するように適合されている同様の電子機器の任意の組み合わせがある。
【０１００】
一実施形態では、処理ユニット及び記憶媒体の少なくとも一方は、対応する通信デバイスに着脱可能に装着されても良い、これによって、実際のデバイスとは独立して確立されるセキュリティアソシエーション（security association：セキュリティ協定）を可能にする。例えば、記憶媒体及び処理ユニットの少なくとも一方は、スマートカード、例えば、ＳＩＭカードによって構成されても良い。
【０１０１】
また、通信デバイスは、更に、図６のブロック図で省略されているコンポーネントを備えていても良いことに注意する。例えば、認証スキームの実環境に依存して、デバイスは、認証方法のパラメータの入力及び出力の少なくとも一方を実行するための入力及び出力の一方の手段を更に備えていても良い。例えば、デバイスの１つには、通信インタフェース、例えば、ネットワークカードを備えていても良く、これは、ネットワークサーバあるいはその類からキー及びタグ値の少なくとも一方を検索するためのものである。
【０１０２】
図７は、生成された共有シークレットへの寄与（contribution）が、無線通信リンクを介して通信され、かつ上述のメッセージ認証によって認証される、セキュアキー交換メカニズムの実施形態を示している。ここで、この実施形態では、メッセージが、共有シークレットへの寄与である。Ａ及びＢで示される２つのデバイスが、共有シークレットキーを確立するために、セキュアキー交換を実行しようとする場合、これらは、以下のステップを実行する、ここで、参照番号７０１で示される左側のフロー図は、デバイスＡによって実行され、一方、参照番号７０２で示される右側のフロー図は、デバイスＢによって実行される。
【０１０３】
以下のキー交換は、いわゆる、キーアグリーメント（key agreement：鍵確立（鍵共有））用の「ディフィ−ヘルマン」方法に基づいている。以下の説明の理解を容易にするために、ディフィ−ヘルマンキーアグリーメントを簡単に説明する。より詳細な説明は、米国特許４，２００，７７０で参照され、これは、参照することによってその全体が本明細書に組み込まれる。
【０１０４】
２つのデバイスＡ及びＢが共有シークレットキーを確立したい場合、これは、素数Ｐ＞２と基底ｇについて同意する（agree）、これは、基本（原始）ｍｏｄ  ｐ（primitie mod p）である。パラメータｐとｇは、両方のデバイスにハードコード化されても良い、これは、一方のデバイスによって生成され、もう一方のデバイスに通信されても良い、また、これらは、サードパーティから検索されても良い、あるいはその類がなされても良い。例えば、ｐ及びｇを生成するために、例えば、１０００ビット以上からなる大きな乱数としてｐの値が選択されても良い、また、既知の素数テスト（プライムテスト：prime test）が、ｐが素数であるかをテストするために実行されても良い。そうでない場合、素数が検出されるまでテストを実行して、新規のｐを選択しても良い。続いて、乱数ｇが選択され、これは、ｇが生成元（ジェネレータ：generator）であるかかテストされ、そうでない場合、生成元が検出されるまで、テストを実行して、新規のｇを選択しても良い。
【０１０５】
各デバイスは、ｐ−１未満のシークレット番号を生成する。以下では、デバイスＡによって生成されるシークレット番号をｘと称し、デバイスＢによって生成されるシークレット番号をｙと称する。次に、各デバイスは、シークレット値と上述のパラメータに基づいてパブリックキーを生成する、デバイスＡは、Ｘ＝ｇx  ｍｏｄ  ｐ  を生成し、ここで、ｍｏｄは、モジュラス（modulus）関数を示している、即ち、整数剰余である。同様に、デバイスＢは、Ｙ＝ｇy  ｍｏｄ  ｐを生成する。
【０１０６】
デバイスは、自身のパブリックキーを交換し、かつそれぞれのデバイスは、共通シークレット値Ｓを、以下に従って算出する：
デバイスＡ：Ｓ＝（Ｙ）x  ｍｏｄ  ｐ
デバイスＢ：Ｓ＝（Ｘ）y  ｍｏｄ  ｐ
従って、この結果として、デバイスＡ及びＢは、シークレット値ｘ及びｙを通信することなく、共通シークレットキーＳを設定する、これは、（ｇy  ｍｏｄ  ｐ）x  ｍｏｄ  ｐ＝（ｇx  ｍｏｄ  ｐ）y  ｍｏｄ  ｐであるからである。
【０１０７】
ここで、図７を参照すると、キー交換の初期ステップ７０３では、デバイスＡは、乱数ｘ、対応するディフィ−ヘルマンパブリックキーＸ及びショートシークレットストリングＫを生成する。ディフィ−ヘルマンパブリックキーＸは、上述のように、対応するパラメータｇ及びｐに基づいて算出される、これは、デバイスＡ及びＢによって同意されているものである。好ましくは、シークレットストリングＫは、適切なキー空間、例えば、４〜６桁の１６進ストリングからランダムに判定される。
【０１０８】
次のステップ７０４では、デバイスＡは、上述のメッセージ認証コード（ＭＡＣ）を使用して、キーとしてシークレットストリングＫを使用するパブリックキーＸからタグ値ｔを算出する。キー設定中に追加のデータが通信される、いくつかの実施形態では、タグ値は、パブリックキーＸと追加のデータを含むメッセージから算出されても良く、これによって、追加のデータに対しても保全性保護を提供することが理解される。
【０１０９】
ステップ７０５では、生成されたシークレットストリングＫと算出されたタグ値ｔが、図７の破線矢印７０６で示されるように、適切な通信チャネルを介してデバイスＢへ通信される。例えば、Ｋとｔの値は、ユーザ対話によって、例えば、デバイスＡのディスプレイからその値を読み上げ、デバイスＢにその値をキー入力することによって、デバイスＡからデバイスＢへ転送されても良い。別の実施形態では、値はいくつかの他の手段によって転送されても良く、これには、例えば、電気通信ネットワークを介して、暗号化されたメッセージ、例えば、電子メール、ＳＭＳあるいはその類として値を送信することによるものがある、あるいは、他の適切な通信チャネル、好ましくは、セキュア通信が確立されている通信チャネルとは異なる通信チャネルを介するものがある。デバイスＡとＢは、互いに確立されている通信リンクを持つ必要がないという利点があり、これらは、互いに近接している必要ですらない。例えば、デバイスＡのユーザは、シークレットストリングとタグ値を、電話、メールあるいは他の適切な手段によって、デバイスＢのユーザへ通信することができる。また、Ｋとｔの生成された値の通信は、例えば、登録処理の一部として、共有シークレットキーが実際にデバイス間で確立する時より前に実行されても良い。一実施形態では、識別子ＩＤがＫ及びｔとともに通信される、これは次回のＫ及びｔの検索を容易にするためである。
【０１１０】
ステップ７０７では、デバイスＢは、Ｋ及びｔの値を受信し、ステップ７１０では、それらをデバイスＢの記憶媒体７１１、例えば、ポータブルデバイスのＥＰＲＯＭあるいはＥＥＰＲＯＭに記憶する、あるいは、スマートカード、ハードディスク、あるいはその他の適切なデータ記憶装置上に記憶する。値Ｋ及びｔが識別子ＩＤに関連付けられている場合、値Ｋ及びｔは、例えば、その識別子をインデックスとして使用して、その識別子と関連付けて記憶される。
【０１１１】
同様に、ステップ７０８では、デバイスＡは、シークレットストリングＫをデバイスＡの記憶媒体７０９に記憶し、オプションとしては、識別子ＩＤと関連付けて記憶する。また、デバイスＡは、シークレット値ｘを記憶する、パブリックキーＸの算出は、これに基づいている。
【０１１２】
これで、初期登録プロセスが終了となる。実際のキー交換を含む続くステップは、デバイスＡ及びＢが実際に通信リンクを介して接続される場合に実行される。これは、図７の線分７２７で示されるように、上述の初期登録後あるいはそれより後の時点に、直ちに発生する場合がある。
【０１１３】
ステップ７１２では、デバイスＡは、無線通信リンクを介して、パブリックキーＸをデバイスＢへ送信することによって、実際のキー交換を初期化する。シークレットストリングＫが識別子ＩＤに関連付けられている実施形態では、デバイスＡもその識別子を送信する。同様に、ステップ７０４で、タグ値ｔがパブリックキーといくつかの追加のデータに対して算出される場合、この追加のデータもデバイスＡからデバイスＢへ送信される。
【０１１４】
デバイスＢがデバイスＡからパブリックキーＸを受信する場合（ステップ７１３）、ステップ７１４で、デバイスＢは、識別子ＩＤに基づく実施形態では、記憶媒体７１１からシークレットストリングＫを検索する。デバイスＢは、シークレットストリングＫに基づいて、受信したパブリックキーＸのＭＡＣタグ値ｔ’を算出する。
【０１１５】
ステップ７１５では、デバイスＢは、算出されたタグ値ｔ’と予め記憶されているタグ値ｔとを比較する。タグ値が異なる場合、受信したパブリックキーは拒否される（ステップ７１６）。例えば、デバイスＢは、対応するメッセージをデバイスＡに送信することによって、また／あるいは、その拒否についてをユーザに通知することによって、例えば、可視あるいは可聴指示を提供することによって、キー交換を中止することができる。そうでない場合、即ち、タグ値が等しい場合、パブリックキーＸは受け入れられ、かつプロセスはステップ７１７に継続する。
【０１１６】
ステップ７１７で、デバイスＢは、上述のように、シークレット値ｙと対応するディフィ−ヘルマンパブリックキーＹを生成する。
【０１１７】
ステップ７１８では、デバイスＢは、対応するディフィ−ヘルマン共有シークレットキーＳ＝（Ｘ）y  ｍｏｄ  ｐを生成する。
【０１１８】
ステップ７１９では、デバイスＢは、生成された共有シークレットキーＳを使用して、記憶媒体７１１から検索されるシークレットストリングＫを暗号化し、暗号化シークレットストリングＫ*を得る。この暗号化は、対称シークレットキーに基づく任意の適切な暗号化方法に基づいていても良い。
【０１１９】
ステップ７２０では、デバイスＢは、暗号化ストリングＫ*とディフィ−ヘルマンパブリックキーＹをデバイスＡへ送信する。そして、一実施形態では、デバイスＢは、更に、対応する識別子ＩＤを送信する。
【０１２０】
ステップ７２１では、デバイスＡは、暗号化ストリングＫ*とディフィ−ヘルマンパブリックキーＹを受信する。
【０１２１】
ステップ７２２では、デバイスＡは、記憶媒体７０９に記憶されているシークレット値ｘを使用して、ディフィ−ヘルマン共有シークレットキーＳ＝（Ｙ）x  ｍｏｄ  ｐを生成する。
【０１２２】
ステップ７２３では、デバイスＡは、生成された共有シークレットキーＳを使用して、受信した暗号化シークレットストリングＫ*を解読して、解読されたシークレットストリングＫ’を取得する。
【０１２３】
ステップ７２４では、デバイスＡは、受信し、解読したシークレットストリングＫ’と、デバイスＡによって生成され、かつ記憶媒体７０９に記憶されているシークレットストリングＫとを比較する。シークレットストリングが等しくない場合、受信したパブリックキーＹが拒否される、即ち、生成された共有シークレットキーＳは破棄される（ステップ７２５）。そうでない場合、プロセスはステップ７２６に継続する。
【０１２４】
ステップ７２６では、受信したパブリックキーＹが受け入れられる、即ち、算出された共有シークレットキーＳが、共有シークレットとして受け入れられる。一実施形態では、対応するメッセージがデバイスへ送信される、これによって、キー交換が完了する。生成された共有シークレットキーは、例えば、デバイス間で送信されるメッセージを暗号化することによって、また／あるいは保全性保護を実行することによって、デバイスＡとＢ間の連続通信を保護するために使用することができる。
【０１２５】
別の実施形態では、デバイスＢからデバイスＡへ通信されるパブリックキーＹは、別の方法、例えば、上述の方法に従ってＭＡＣを算出することによって、認証されても良いことが理解される。
【０１２６】
本明細書で説明される認証方法は、事前に生成された共有シークレット、例えば、匿名のディフィ−ヘルマンキーアグリーメントによって生成される共有シークレットを認証するために使用しても良いことが理解される。従って、この実施形態では、メッセージは、２つのデバイスによって協働して生成される共有シークレットとなる。
【０１２７】
本明細書で使用される場合の「構成する／構成している」という用語は、上述の特徴、整数値（integers）、ステップあるいはコンポーネントの存在を特定するために採用されているが、これは、他の特徴、整数値、ステップ、コンポーネントあるいはそれらのグループの存在あるいは追加を除外するものではないことが重視されるべきである。
【０１２８】
本発明の実施形態が説明され、かつ図示されているが、本発明はこれに制約されるものではなく、請求項で定義される対象の範囲内で、他の方法で実施されても良い。
【０１２９】
ある数値（測定値）（measurement）が従属請求項と互いに異なって引用されていることは、これらの数値の組み合わせが効果として使用できないことを示しているものではない。
【図面の簡単な説明】
【０１３０】
【図１】ユーザ対話が介在するメッセージ認証環境の例のフロー図である。
【図２】ユーザ対話が介在するメッセージ認証環境の別の例のフロー図である。
【図３】誤り訂正コードに基づくメッセージ認証コードを算出する方法のフロー図である。
【図４ａ】リード−ソロモンコードに基づくメッセージ認証コードを算出する方法の例のフロー図である。
【図４ｂ】リード−ソロモンコードに基づくメッセージ認証コードを算出する方法の例のフロー図である。
【図５】図４ａ〜ｂのＭＡＣ構成のいくつかの構成例に対する置換攻撃の成功確率を示すテーブルである。
【図６】２つの通信デバイスのブロック図である。
【図７】生成された共有シークレットへの寄与が、無線通信リンクを介して通信され、かつ図３及び図４ａ〜ｂで説明されるメッセージ認証によって認証される、セキュアキー交換メカニズムの実施形態を示す図である。
【図１】
0004664206.tif 000011
【図２】
0004664206.tif 000012
【図３】
0004664206.tif 000013
【図４ａ】
0004664206.tif 000014
【図４ｂ】
0004664206.tif 000015
【図５】
0004664206.tif 000016
【図６】
0004664206.tif 000017
【図７】
0004664206.tif 000018