(57)【特許請求の範囲】
【請求項１】
通信装置におけるデータ通信の機密性を提供する方法であって、
・前記通信装置の乱数生成手段が乱数を生成し、または前記通信装置の乱数受信手段が乱数を受信するステップ、
・前記通信装置の関数生成手段が、認証暗号化オフセット（ACO）を少なくとも鍵値および前記乱数の関数として生成するステップ、
・前記通信装置の暗号化鍵生成手段が、暗号化鍵を前記鍵値および前記ACOの関数として生成するステップ、
・前記通信装置の暗号化データ送受信手段が、前記暗号化鍵による暗号化データを送受信するステップ、
を有し、
前記ACOの初期値は、前記データ通信の相手先通信装置との間で同一の値に設定され、該初期値が設定された後は、前記ACOは、１または２以上のパラメータの関数として生成されるものであって、当該１または２以上のパラメータのうちの少なくとも１つは、過去のACOから導出されることを特徴とする方法。
【請求項２】
前記ACOを１または２以上のパラメータの関数として生成する前記ステップは、
前記１または２以上のパラメータの中から、ｋ番目の値Xkを生成するステップと、
Xkと過去の値ACOk-1との間で交換律を満たすバイナリ演算を行うステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ACOを１または２以上のパラメータの関数として生成する前記ステップは、次式に従う実行時加算（running sum）としてACOのｋ番目の値を生成するステップを含むことを特徴とする請求項１に記載の方法。
0004694751.tif 000004
ただし、Xiは、前記少なくとも１つの過去に演算されたACOの値から導出されたパラメータを除いた前記１または２以上のパラメータの関数として生成される。
【請求項４】
前記加算は、ビット単位の２を法とする加算（bitwise modulo-2 sum）であることを特徴とする請求項３に記載の方法。
【請求項５】
前記ビット単位の２を法とする加算は、ビット単位の排他的論理和（XOR）演算によって実行されることを特徴とする請求項４に記載の方法。
【請求項６】
データ通信の機密性を提供するように構成された通信装置であって、
・乱数を生成し、または受信するように論理構成された手段、
・認証暗号化オフセット（ACO）を少なくとも鍵値および前記乱数の関数として生成するように論理構成された手段、
・暗号化鍵を前記鍵値および前記ACOの関数として生成するように論理構成された手段、
・前記暗号化鍵による暗号化データを送受信するように論理構成された手段、
を備えるとともに、
前記ACOの初期値は、前記データ通信の相手先通信装置との間で同一の値に設定され、該初期値が設定された後は、前記ACOは、１または２以上のパラメータの関数として生成され、当該１または２以上のパラメータのうちの少なくとも１つは、過去のACOから導出されることを特徴とする通信装置。
【請求項７】
前記ACOを１または２以上のパラメータの関数として生成するように論理構成された前記手段は、
前記１または２以上のパラメータの中から、ｋ番目の値Xkを生成するように論理構成された手段と、
Xkと過去の値ACOk-1との間で交換律を満たすバイナリ演算を行うように論理構成された手段と、
を含むことを特徴とする請求項６に記載の装置。
【請求項８】
前記ACOを１または２以上のパラメータの関数として生成するように論理構成された前記手段は、次式に従う実行時加算（running sum）としてACOのｋ番目の値を生成するように論理構成された手段を含むことを特徴とする請求項６に記載の装置。
0004694751.tif 000005
ただし、Xiは、前記少なくとも１つの過去に演算されたACOの値から導出されたパラメータを除いた前記１または２以上のパラメータの関数として生成される。
【請求項９】
前記ACOのｋ番目の値を生成するように論理構成された前記手段は、ビット単位の２を法とする加算（bitwise modulo-2 sum）を行うように論理構成された手段を含むことを特徴とする請求項８に記載の装置。
【請求項１０】
前記ビット単位の２を法とする加算を行うように論理構成された前記手段は、ビット単位の排他的論理和（XOR）演算を行うように論理構成された手段を含むことを特徴とする請求項９に記載の装置。
【請求項１１】
リアルタイム装置を含むことを特徴とする請求項６に記載の装置。
【請求項１２】
非リアルタイム装置を含むことを特徴とする請求項６に記載の装置。
【発明の詳細な説明】
【０００１】
（背景）
本発明は通信システムに関し、特に、リアルタイム・レイヤと非リアルタイム・レイヤとのインタフェースにおいて制御不能な遅延を伴う通信エンティティ間の同期に関する。
【０００２】
コンピュータ化された携帯型装置（デバイス）が一般的に使用される数が増えるにつれ、これらのデバイス間の通信の必要性が高まっている。その結果、多くのデータ共有方式や通信システムにおいて、このような各種デバイス間の通信を提供するための標準規格が制定されている。
【０００３】
かかるシステムの一例として、Bluetoothとよばれるものがある。これは、特に移動電話機、ラップトップ・コンピュータ、携帯情報端末（ＰＤＡ）といった移動型の携帯デバイス間の相互接続性を普及させるべく近年導入されたものである。ただし、Bluetoothは、本発明が適用される多くのシステムのうちの１つにすぎない。つまり、本発明によって解決すべき課題のいくつかの例はBluetoothを用いたシステムによって説明していくことにはなるが、これらの例はあくまで説明としての位置づけであって、本発明は他の類似のシステムに同様の課題を解決するために適用することができる。
【０００４】
Bluetoothシステムは、周波数ホッピングを使用して、低電力、低コスト、かつ小型の構成を可能にしている。このシステムは、データと音声の両方をサポートする。後者は高速周波数ホッピング（ＦＨ）をロバストな音声符号化と組み合わせて使用することによって最適化される。高速周波数ホッピングは、80MHz幅の2.4GHz ISM帯全体にわたり各方向で800hop/sに対応して１秒あたり1,600ホップ（1,600hop/s）の、通常のレートを有する。
【０００５】
Bluetoothシステムのコンセプトに基づくデバイスは、マスタ・デバイスと１または２以上のスレーブ・デバイスとがＦＨピコネットチャネルを介して接続されたピコネットとよばれる構成をつくることができる。ピコネットチャネルに対して用いられるＦＨシーケンスは、マスタとして動作するデバイスのアドレスまたはＩＤでもって完全に求められる。マスタ・デバイスのシステムクロックは、ホッピング・シーケンスにおける位相（すなわち、そのシーケンスにおいて想定されるホッピングのいずれかの指定が、“現在の”のホッピングである）を求める。Bluetoothシステムでは、各デバイスは自走システムクロックを有する。各スレーブ・デバイスは、対応する時間オフセットをそのクロックに加算することでマスタ・デバイスのクロックと整合をとることを可能にする。マスタ・アドレスを用いて適当なホッピング・シーケンスを選択すること、および、時間オフセットを用いてマスタ・デバイスのクロックと整合をとることによって、各スレーブ・デバイスはマスタ・デバイスへのホッピング同期を維持する。つまり、マスタ・デバイスとスレーブ・デバイスとは、同一のホッピング周波数またはホッピング搬送波に同調したホッピングによってコンタクトを維持する。
【０００６】
詳細は、1997年９月18日に出願された米国特許出願第08/932,911号（発明の名称："Frequency Hopping Piconets in an Uncoordinated Wireless Multi-user System,"）、および、Bluetoothシステム仕様書ver.1.0A（Specification of the Bluetooth System version 1.0A）に開示されている。この仕様書はインターネットで、次のＵＲＬから入手可能である。
http://www.bluetooth.com
【０００７】
Bluetoothシステム仕様書に開示されているように、低レベルのセキュリティ機能である認証（authentication）および暗号化（encryption）を容易にする２つの方式が含まれている。Bluetooth無線コネクションを有する１のユニット（以下「ユニットＡ」）が他のユニット（以下「ユニットＢ」）で主張されたＩＤの証明を要求するたびに、認証手順が起動される。
【０００８】
関与する両ユニットの主張されたＩＤがいったん（一方向に、または、リンクを介して動作しているアプリケーションが要求する場合には双方向に）照合されると、両ユニットはトラヒックのためのリンクの使用を開始することができる。両方のユニットが共有秘密、すなわちリンク鍵を知っていることが認証成功の前提となる。
【０００９】
Bluetoothにおける認証手順は、チャレンジ＆レスポンス方式に従う。簡単にいうと、認証側（verifier）が乱数によってチャレンジ（challenge、以下「AU_RAND」ともいう。）を生成し、これを要求側（claimant）に送信する。要求側は、このチャレンジを受信すると、署名付応答（signed response、これを「SRES」とする。）を演算し、これを認証側に返送する。認証側でも別途、与えたチャレンジと２つのBluetoothユニットで用いられる共有秘密リンク鍵（shared secret link key）とから予期される応答（これを「SRES'」とする。）を演算することができる。受信したSRESが演算したSRES'と等しければ、認証が成功したとみなされる。他方、２つの値が異なれば、そのＩＤによる要求側の認証は失敗に終わる。このチャレンジ＆レスポンス方式はBluetoothシステムに限定されるものではなく、認証を要する多くの通信システムに適用が可能である。このようなシステムでは、チャレンジ＆レスポンスのフォーマットは、システムの各ユニット間で通信されうる同一もしくは類似の値で使用することができる。
【００１０】
ある時点でデータの機密保護が必要である場合に、ユニットは暗号化を作動させる（オンする）ことができる。この処理には、共通の秘密（secret）、すなわち、暗号化鍵（encryption key）も必要である。暗号化鍵はリンク鍵とは異なるが、リンク鍵から導出されるものである。認証は通常、コネクション設定時に行われる。後で認証処理を繰り返すことが可能であるとしても、それは必須ではない。したがって、認証が行われて暗号化が作動してから長時間が経過する場合もある。そのため、（認証処理を頻繁に繰り返さないかぎり）この時間帯に悪意のあるユーザによってユニットが交換されてしまうことはないという確実な保証はない。
【００１１】
望ましくは、暗号化がオンされしだい、不正なユニットは直ちに突き止められる。このような不正ユニットはすべて、リンクにもともと関与しているデバイスによって用いられる秘密リンク鍵を所持すべきではないからである。よって、ユニットは暗号化鍵を導出することもできない。不正ユニットのために困難性をさらに増すべく、暗号化鍵は、リンク鍵だけでなく「認証暗号化オフセット（Authentication Ciphering Offset : ACO）」とよばれる数値にも依存して生成される。ACOは、SRESを生成する関数の各コールに対して生成される数値である。２つのユニットが異なるACOで暗号化をオンにする場合には、それら２つのユニットが同じリンク鍵を使用したとしても、それぞれ生成される暗号化鍵は異なることになる。
【００１２】
SRESおよびACOの演算はE1で示されるアルゴリズムで定義される。すなわち、
【００１３】
0004694751.tif 000002
【００１４】
ただし、{0, 1}iの表記は長さｉの２進数、Ｋは128bitのリンク鍵、AU_RANDは認証側で発行された128bitのチャレンジ、BD_ADDRは要求側の48bitのBluetoothデバイスアドレス、SRESは32bitの署名付応答、ＸはSRESと同時に演算される96bitの数値を表す。演算子“×”は必ずしも乗算を意味するものではなく、むしろ、矢印の左辺のパラメータが共に、その矢印の右辺に供給されて２つのパラメータを生成する演算が行われることを表すのに用いられていることに留意。この関数は、Bluetoothシステム仕様書の第14章（Chapter 14）で定義されている。ただし、Bluetoothシステムまたは他の通信システムにおいて、別の好適なアルゴリズムを適用してもよいことは理解されよう。
【００１５】
現在、E1の各コール毎に、各デバイスはACOの値を更新する。よって、従来のシステムにおいては、次式のとおりとみなせる。
【００１６】
ＡＣＯ＝Ｘ.                  （２）
【００１７】
ところで、現在の認証方式では、ACO値を一致（シンクロナイズ）させることの困難性の点で問題がある。例えば、現在のBluetoothベースバンド仕様書によれば、生成したACOの最新のものを常に使用すべしということになっているが、その確認は困難であるという事実から問題が生じることになる。この問題に関して、論点が２つある。第１に、ユニット間の通信において生じる遅延はおそらく未知であるということ。第２に、同時伝送もしくはそれに近い伝送であるために送信が最新のものであるかどうかの判断は困難であることである。
【００１８】
図１は、２つのユニット間で認証および／または暗号化が必要な通信方式の一例を示す図である。図１は、認証および／または暗号化が必要なBluetoothシステムまたは別の好適な通信システムに関するものである。図１に示すように、各ユニットにおいてリンクマネージャ（Link Manager : ＬＭ）１０１がＬＭメッセージを生成し、ベースバンド（ＢＢ）送信機１０３がメッセージを符号化して他のユニット内のＢＢ受信機１０５に送信する。同様に、各ユニット内のＢＢ受信機１０５は、受信したビットストリームを復号化し、これらを上層レイヤのリンクマネージャ１０１に渡す。リンクマネージャ１０１はメッセージを解釈する。
【００１９】
不都合なことに、上記の処理の実現のために、リンクマネージャ１０１がメッセージを生成した時からＢＢ送信機１０３がそのメッセージを送信する時までの間に未知の遅延を生じる場合がある。受信機側でも同様である。ＢＢ受信機１０５がメッセージを受信し、そのメッセージがリンクマネージャ１０１で解釈され処理されるのに、予測不能な遅延を生じる。上記のような事態を生じるのは、各種認証方式における認証要求を含むあらゆる種類のＬＭメッセージの場合にも当てはまる。
【００２０】
遅延が生じる理由はいくつか考えられる。明らかなのは、内部のハードウェア設計（例えばバッファ）および生起トラヒック負荷がこの遅延に影響を及ぼすことである。さらに、無線チャネルの特性（干渉状況やＳＮＲなど）も影響を与える。例えば、無線チャネルの状態が悪いためにユニットＡがユニットＢにまだ配信していない未処理メッセージを抱えている場合がある。ユニットＡのリンクマネージャ１０１が新たなメッセージを生成するとそのメッセージは送信キューに置かれることになるが、未処理メッセージがすべて送信されるまで送信されない。
【００２１】
問題は、２つのユニットが同時に（正確にいうと、実際の遅延に依存した「短い」時間インターバル内に）相手側に認証要求を発行したときに生じる。これは、一方の側でイベントが生じた時点からそのイベントが他端側に登録される時点までの遅延の長さを知る術がないからである。明らかに、この状況においてはそれぞれの側では暗号化鍵生成アルゴリズムE1を２回コールする必要がある。１回目のコールは自身のユニットが生成した要求のために、２回目のコールは相手側から受信した要求に対する応答を生成するためである。後述するように、遅延が異なるために、Ａ側での最後のコールがＢ側での最後のコールと異なる場合がある。そのため、ユニットＡ，Ｂは暗号化をオンしたときに異なる暗号化鍵を生成してしまい、互いに明瞭に通信することができない結果となる。
【００２２】
図２は、両方の側が最終的に同じACOになり、暗号化がオンした後にも互いに通信が可能になったケースを示している。垂直線はユニットＡ，Ｂそれぞれのリンクマネージャ１０１の時間軸であり、下に向かって時間が進んでいく。step201で、ユニットＡはユニットＢのＩＤの確認を要求すべく、チャレンジAU_RANDAを生成する。このチャレンジがユニットＢに送信される。step203で、ユニットＢはユニットＡからチャレンジを受信し、E1をコールして２つのパラメータSRESA，ACOAを生成し、応答する（各パラメータの添字ＡはユニットＡのチャレンジに係るものであることを表す。）。そして、ユニットＢで生成された応答パラメータSRESAがユニットＡに返送される。
【００２３】
次にstep205で、ユニットＡはユニットＢの応答パラメータSRESAを受信し、それに応答してE1をコールして予期される応答パラメータSRES'A，ACOAを演算する。そして、ユニットＡは予期される署名付応答SRES'Aを実際の署名付応答SRESAと比較してユニットＢが真正かどうかを判断することができる。
【００２４】
step207で、ユニットＢはユニットＡのＩＤの確認を要求すべく、チャレンジAU_RANDBを生成する。このチャレンジがユニットＡに送信される。step209で、ユニットＡはユニットＢからチャレンジを受信し、E1をコールして２つのパラメータSRESB，ACOBを生成し、応答する（各パラメータの添字ＢはユニットＢのチャレンジに係るものであることを表す。）。そして、ユニットＡで生成された応答パラメータSRESBがユニットＢに返送される。
【００２５】
次にstep211で、ユニットＢはユニットＡの応答パラメータSRESBを受信し、それに応答してE1をコールして予期される応答パラメータSRES'B，ACOBを演算する。そして、ユニットＢは予期される署名付応答SRES'Bを実際の署名付応答SRESBと比較してユニットＡが真正かどうかを判断することができる。
【００２６】
その後、両ユニットは互いの通信に暗号化を使用することを決定する。そこで、step213で、ユニットＡは最後に生成されたACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。同様に、step215で、ユニットＢも最後に生成したACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。このケースでは、ユニットＡとユニットＢの両方で最後に生成したACOの値はACOBである。つまり、両ユニットは同一の暗号化鍵を生成し、相互に通信を継続することが可能になる。
【００２７】
続いて図３を参照されたい。これは、伝送の遅延によって２つのユニットＡ，Ｂがそれぞれ最終的に異なる値のACOを生成してしまい、暗号化をオンにした後に通信不能になってしまうケースを示している。具体的には、step301で、ユニットＡはユニットＢのＩＤの確認を要求すべく、チャレンジAU_RANDAを生成する。このチャレンジがユニットＢに送信される。ところがstep303で、ユニットＡからチャレンジを受信する前に、ユニットＢもユニットＡのＩＤを確認すべく自身のチャレンジAU_RANDBを生成する。
【００２８】
step305で、ユニットＡはユニットＢのチャレンジを受信し、E1をコールして２つのパラメータSRESB，ACOBを生成し、応答する（各パラメータの添字ＢはユニットＢのチャレンジに係るものであることを表す。）。そして、ユニットＡで生成された応答パラメータSRESBがユニットＢに返送される。
【００２９】
同様に、step307で、ユニットＢは（step301で送信された）ユニットＡのチャレンジを受信し、E1をコールして２つのパラメータSRESA，ACOAを生成し、応答する（各パラメータの添字ＡはユニットＡのチャレンジに係るものであることを表す。）。そして、ユニットＢで生成された応答パラメータSRESAがユニットＡに返送される。
【００３０】
次にstep309で、ユニットＢはユニットＡの応答パラメータSRESBを受信し、それに応答してE1をコールして予期される応答パラメータSRES'B，ACOBを演算する。そして、ユニットＢは予期される署名付応答SRES'Bを実際の署名付応答SRESBと比較してユニットＡが真正かどうかを判断することができる。
【００３１】
同様にstep311で、ユニットＡはユニットＢの応答パラメータSRESAを受信し、それに応答してE1をコールして予期される応答パラメータSRES'A，ACOAを演算する。そして、ユニットＡは予期される署名付応答SRES'Aを実際の署名付応答SRESAと比較してユニットＢが真正かどうかを判断することができる。
【００３２】
その後、両ユニットは互いの通信に暗号化を使用することを決定する。そこで、step313で、ユニットＡは最後に生成されたACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。同様に、step315で、ユニットＢも最後に生成したACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。このケースでは、ユニットＡで最後に生成したACOの値はACOAであり、ユニットＢで最後に生成したACOの値はACOBである。つまり、ユニットＡとＢは異なる暗号化鍵を生成してしまい、これによって相互に通信を継続することが不可能になってしまう。
【００３３】
図３に示した問題は、特別なルールを用いて回避することができる。例えば、Bluetoothベースバンド仕様書の現行バージョンによれば、次のルールを用いることで問題を解決している。
【００３４】
『相互認証の場合には、第２の認証で得られたACO値を保持する。しかし、両方のデバイスで認証イベントが同時に生じる場合がある。この場合には、どちらが第１のイベントでどちらが第２のイベントなのかが分からない。そこで、両方のユニットは、マスタユニットから発行されたチャレンジに応答して生成されたACOを用いることとする。』
【００３５】
第２のユニット（ユニットＢ）は、以前にユニットＢから送信したチャレンジに対する応答が来ると予想されるところに第１のユニット（ユニットＡ）からのチャレンジを受信したときに、ユニットＡで認証イベントが同時またはほぼ同時に生成されたと判断することができる。このケースでは、ユニットＢから発信された認証イベントはオープンであるとみなされる。応答を受信するまでは発信側による認証イベントはオープンであるとみなされるのである。発信側でその応答を受信し処理すると、そのイベントはクローズされる。したがって、図３のようなケースで、上記したBluetoothルールを用いると、ユニットＢは、step303で送信した過去のチャレンジに対して予期される応答ではなくてstep307での認証要求を受信したことを監視する。そうすると、step303でユニットＢから発信した認証要求はオープンであるとみなされ、ユニットＢで使用されるのはACOBではなく、step301でマスタ・ユニットＡによって生成されたチャレンジから得られたACOAとなる。同様にユニットＡも上記のルールに従い、認証要求を受信したときは（step305）、step301で発信した認証イベントがオープンであるとみなされ、ACOAを使用することになる。したがって、このルールを使用することで、Bluetoothシステムにおいて通信するデバイスは図３に示した問題を回避することができる。
【００３６】
続いて図４を参照されたい。これは、Bluetoothシステムにおける伝送遅延または処理遅延によって、２つのユニットＡ，Ｂがそれぞれ最終的に異なる値のACOを生成してしまい、暗号化をオンにした後に通信不能になってしまうケースを示している。図３に示したケースでは上記ルールによって通信を継続させることができたが、この図４のケースで同じルールを適用しても、遅延によってBluetoothシステムにおける通信は困難になってしまう。具体的に説明すると、step401で、ユニットＡはユニットＢのＩＤの確認を要求すべく、チャレンジAU_RANDAを生成する。このチャレンジがユニットＢに送信される。ところがstep403で、ユニットＡからチャレンジを受信する前に、ユニットＢもユニットＡのＩＤを確認すべく自身のチャレンジAU_RANDBを生成する。
【００３７】
step405で、ユニットＢは（step401で送信された）ユニットＡのチャレンジを受信し、E1をコールして２つのパラメータSRESA，ACOAを生成し、応答する（各パラメータの添字ＡはユニットＡのチャレンジに係るものであることを表す。）。そして、ユニットＢで生成された応答パラメータSRESAがユニットＡに返送される。Bluetooth仕様ルールに従えば、ユニットＢは、その認証要求はオープンであることを知ってこの応答を生成し、そして、マスタ・ユニットＡで生成されたACOの値を用いる。
【００３８】
step407で、ユニットＡは時刻tAにユニットＢの応答パラメータSRESAを受信し、それに応答してE1をコールして予期される応答パラメータSRES'A，ACOAを演算する。そして、ユニットＡは予期される署名付応答SRES'Aを実際の署名付応答SRESAと比較してユニットＢが真正かどうかを判断することができる。そしてユニットＡは、ほぼ同時に認証イベントが生じたことを知らないでこの演算を実行する。このケースではユニットＡの要求に対する応答によってユニットＡの認証イベントがクローズされた後に、ユニットＢの要求が受信されるからである。
【００３９】
step409で、ユニットＡはユニットＢのチャレンジを受信し、E1をコールして２つのパラメータSRESB，ACOBを生成し、応答する（各パラメータの添字ＢはユニットＢのチャレンジに係るものであることを表す。）。そして、ユニットＡで生成された応答パラメータSRESBがユニットＢに返送される。
【００４０】
step411で、ユニットＢは時刻tBにユニットＡの応答パラメータSRESBを受信する。しかし、ユニットＢは、E1をコールして予期される応答パラメータSRES'B，ACOBを演算するのではなく、SRES'Bを算出するものの、Bluetooth仕様書のルールに従いマスタ・ユニットＡで生成されたチャレンジから得られたACOAを保持する。
【００４１】
step403でユニットＢによって生成されたユニットＢの認証要求AU_RANDBがユニットＡによって受信されるのが（step409）、step405でユニットＢによって生成された署名付応答SRESAがstep407でユニットＡによって時刻tAで受信された後であることから、図４のケースで問題が生じる。つまり、ユニットＢによって生成された認証要求を受信する前の時刻tAでユニットＡの認証要求イベントがクローズされてしまうので、ユニットＡは、ほぼ同時に２つの認証要求が生じたことを知らない。そのため、ユニットＡは、両ユニットにACOBではなくマスタ・ユニットのACO値を用いるよう要求するBluetooth仕様ルールを適用しない。しかし、ユニットＢは、step401でユニットＡによって生成されたユニットＡの認証要求を、step403でユニットＢが認証要求を生成した後のstep405で受信する。ユニットＡによって生成された認証要求を受信したのは、ユニットＢによって生成された認証要求の後、step411でユニットＡからの応答を受信する前であるから、ユニットＢは、２つの認証要求がほぼ同時にあったと認識し、ユニットＢにマスタ・ユニットのACO値またはACOAを用いるよう要求するBluetooth仕様ルールを適用する。
【００４２】
このユニットＢの認証要求の時間遅延の結果、２つのデバイスが後に暗号化をオンにしたときは、step413に示すようにユニットＡはACOBを使用し、step415に示すようにユニットＢはACOAを使用する。結果、相異なるACO値を用いる２つのユニットによっていったん暗号化がオンされると、通信不能となってしまう。
【００４３】
上記した例では、他のユニットからの実際の署名付応答を受信した後にだけ、各ユニットが予期される署名付応答SRES'Bを生成すると仮定した。しかし、これは要求事項ではなく、例えば、ユニットがチャレンジAU_RANDを生成すると同時に、予期される署名付応答（SRES'B）を生成するようにしてもよい。SRES'をいつ生成するかは、それを実現するシステムに依存して決定してよい。例えば、Bluetoothシステム仕様書は、その設計を開発者に委ねている。また、それは一方向についてなのか、そうではないのかということも要求されていないので、あるメーカーで製造された１のユニットはチャレンジの生成と同時にSRES'を生成するのに対し、違うメーカーで製造された別のユニットは相手側から署名付応答を受信した後にのみSRES'を生成するということも可能になっている。このようなケースでもまた、最後に生成されたACOの値が２つのユニットで相違し、暗号化がオンされたときに互いに同一の暗号化鍵を生成させることができない事態が起こりうる。
【００４４】
米国特許第5 148 007号は、上述したチャレンジ＆レスポンス方式による方法を開示する。ここには、乱数が、過去に演算された乱数を含む複数のパラメータの関数として生成されることが記載されている。
よって、上述のようにACO値が相違して矛盾した暗号化を使用する場合があるという従来技術の問題を回避したシステムを実現する必要がある。
【００４５】
（発明の概要）
「備える、有する（comprises, comprising）」の用語は、本明細書で用いる場合には、明示した機能、数値、工程、要素が存在することを意味するものであるが、これらの用語は、１または２以上の他の機能、数値、工程、要素、もしくはそれらのグループが存在し、またはそれらを付加することを除外するものではないことを強調しておく。
【００４６】
通信システムに使用される本発明によって前述の目的およびその他の目的が達成される。このようなシステムの１つにBluetoothシステムがある。本発明の一側面によれば、認証暗号化オフセット（Authentication Ciphering Offset : ACO）は、１または２以上のパラメータの関数として生成されるものであり、ここで、上記１または２以上のパラメータのうちの少なくとも１つは、過去に演算されたACOの値から導出されることを特徴とする。これは、各デバイスに、他の通信デバイスで生成された相手側ACO値と一致しないACOを生成してしまうことを回避させ、それによって例えば、制御不能な遅延によって生じる従来システムの問題を解決することを可能にする。
【００４７】
（詳細な説明）
以下、図面を参照しながら、いくつかの実施形態により、本発明をさまざまな側面から詳細に説明する。図中、同様の構成要素には同一の参照符号を付してある。発明の理解の助けとなるように、コンピュータシステムの構成要素によって実行される動作シーケンスにより発明の多くの側面を説明する。各実施形態において、各種動作は、専用回路（例えば、特化した機能を実行するように接続されたディスクリート論理ゲート）によって、または、１もしくは２以上のプロセッサで実行されるプログラム命令によって、あるいは、両者の組み合わせによって、実行される。さらに、以下で説明する方法をプロセッサに実行させる好適なコンピュータ命令セットが格納された、コンピュータによって読出し可能なあらゆる形式の記憶媒体も、本発明を実現するものである。したがって、本発明の多くの側面が違った形態で実現され、これらすべての形態が本発明の範囲に含まれることを意図している。本発明の各側面において、すべての実施形態の構成は、記述した動作について「〜するように論理構成された手段（logic configured to）」と表現することができる。
【００４８】
過去に演算したすべてのACOの値およびその他のパラメータの関数として認証暗号化オフセット（Authentication Ciphering Offset : ACO）を生成する新たな関数を使用することによって、従来技術に係る問題が解消する。
【００４９】
図５に示すように、トリガ・イベント（step501）によって、特定のデバイスもしくは通信ユニットにACOを所定のパラメータの関数として演算させる（step503）。所定のパラメータのうちの少なくとも１つは過去に演算されたACOの値である。トリガ・イベント501は、各種の内部トリガ・イベント、外部トリガ・イベントのいずれでもよい。外部トリガ・イベントとしては例えば、他のデバイスから受信した認証要求または署名付応答がある。内部トリガ・イベントとしては例えば、一定の時間経過イベントなどが考えられる。新たなACO値を生成する場合、順序に依存しない交換律を満たすバイナリ関数であれば過去のACO値に基づいてACO値を生成するのに十分である。
【００５０】
実施形態において、各ユニットは、ACO値の実行時加算（running sum）（ビット単位の２を法とする（bitwise modulo-2）加算）を保持し、最後に生成したACOの値と現在生成したＸ（E1をコールすることで生成される）の値とを結合する。ゆえに、E1をｋ回コールした後のACOは、次式で表される。
【００５１】
0004694751.tif 000003
【００５２】
ただし、本実施形態において、加算はビット単位の２を法とする（bitwise modulo-2）加算である。この加算値は望ましくは排他的論理和（XOR）関数を使用することで生成される。Xkの値は従来どおりE1で示される関数を用いて計算することができる。
【００５３】
加算における要素の順序は重要ではないので、次の結果が満足されるかぎり、２つのユニットＡ，Ｂは同一のACO値を有する。
{xi(A)|i=1...k} = {xi(B)|i=1...k}
その結果、図３および図４で説明した例と同様のケースでは、暗号化がオンになってもまったく問題は生じない。
【００５４】
XOR演算を用いてACO値のすべてを加算するものとは異なる別の技術を使用することもできる。例えば、過去のACOの値を用いた何種類かの関数を使用して、選択された単数もしくは複数の関数が交換律を満足するかぎり、両ユニットにおけるACOを同一のまま維持する。論理演算のAND, NAND, OR, NORのような単純なブール関数に加え、減算関数および乗算関数を使用することもできる。例えば、式（３）に示したようなXkとACOk-1との間で交換律を満たすバイナリ演算を使用することができる。さらに、コンボリューション加算等のようなより複雑な関数を使用することもできる。
【００５５】
ただし、XOR関数以外の単純なバイナリ関数は、数多く処理を繰り返すと生成するACOが特定の結果になる傾向があり、予測がつくACOを生成してしまうので、望ましいとはいえないことに注意。さらに、より複雑な関数も、計算量を著しく増やしてしまうため望ましいものではない。しかし、より複雑なアルゴリズムまたは複数のアルゴリズムの組み合わせのほうが、より予測が難しいACO値を生成することができるので、処理速度が速くなれば望ましいものになる。
【００５６】
図６は、図３で示した問題を解決するために、通信システムにおいて本発明がどのように適用されるかを説明する図である。図３においては、Ａ，Ｂ両方のユニットでほぼ同時にチャレンジが生成されたことで両方のユニットで最終的にACO値が相異なり、暗号化がオンされた後に通信不能になってしまっていた。しかし、図６では、本発明により、新たなACOの値それぞれが過去のACOの値を用いて演算され、両方のユニットでACOの値を一致させることが可能になり、暗号化がオンになっても通信を維持することができる。図６に示したケースにおいて、ユニットＡとユニットＢとで初めは同じACO値にする。具体的には、ユニットＡは初めにACOmを生成し、ユニットＢは初めにACOn（ACOmと等しい値）を生成する。
【００５７】
step601で、ユニットＡはユニットＢのＩＤの確認を要求すべく、チャレンジAU_RANDAを生成する。このチャレンジがユニットＢに送信される。ところがstep603で、ユニットＡからチャレンジを受信する前に、ユニットＢもユニットＡのＩＤを確認すべく自身のチャレンジAU_RANDBを生成してしまう。
【００５８】
step605で、ユニットＡは（step603で送信された）ユニットＢのチャレンジを受信し、E1をコールして２つのパラメータSRESB，ACOm+1を生成し、応答する。このケースでは、ACOm+1は、AU_RANDBおよび過去のACO値の関数として導出される。ACOm+1は、式（３）に記した方法で演算することができる。あるいは交換律を満たす適当な別のバイナリ関数を用いて演算してもよい。そして、ユニットＡで生成された応答パラメータSRESBがユニットＢに返送される。
【００５９】
同様に、step607で、ユニットＢは（step601で送信された）ユニットＡのチャレンジを受信し、E1をコールして２つのパラメータSRESA，ACOn+1を生成し、応答する。ACOn+1は、AU_RANDAおよび過去のACO値の関数として導出される。ACOn+1は、例えば式（３）に示したような交換律を満たすバイナリアルゴリズムを用いて生成される。そして、ユニットＢで生成された応答パラメータSRESAがユニットＡに返送される。
【００６０】
次にstep609で、ユニットＢはユニットＡの応答パラメータSRESBを受信し、それに応答してE1をコールして予期される応答パラメータSRES'B，ACOn+2を演算する。ここで、ACOn+2は、AU_RANDB，ACOn+1の関数である。そして、ユニットＢは予期される署名付応答SRES'Bを実際の署名付応答SRESBと比較してユニットＡが真正かどうかを判断することができる。
【００６１】
同様にstep611で、ユニットＡはユニットＢの応答パラメータSRESAを受信し、それに応答してE1をコールして予期される応答パラメータSRES'A，ACOm+2を演算する。ここで、ACOm+2は、AU_RANDA，ACOm+1の関数である。そして、ユニットＡは予期される署名付応答SRES'Aを実際の署名付応答SRESAと比較してユニットＢが真正かどうかを判断することができる。
【００６２】
その後、所定の時刻で、または暗号化要求によって、両ユニットは互いの通信に暗号化を使用することを決定する。そこで、step613で、ユニットＡは最後に生成されたACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。同様に、step615で、ユニットＢも最後に生成したACOの値を用いて暗号化をオンにし、使用する暗号化鍵を生成する。このケースでは、ユニットＡで最後に生成したACOの値はACOm+2であり、ユニットＢで最後に生成したACOの値はACOn+2である。しかし、２つのユニットが等しい値（すなわち、ACOm＝ACOn）で処理を開始しており、また、例えば式（３）に示したような交換律を満たす関数のように、ACO値をそれぞれ生成するときに実行される演算が交換律を満たし、演算の順序によって演算結果が変わらないのであれば、これらの値は等しいことになる。したがって、ユニットＡとユニットＢは共に等しいACO値で終わることになり、暗号化がオンされたとしても通信を維持することができるようになる。くわえて、未知の遅延や同時の認証要求があったとしても、両方のユニットでACO値が等しい状態に保つことができる。よって、図３で示したような問題は、本発明によって解消される。
【００６３】
続いて図７を参照されたい。これは、本発明により図４で説明した問題が解消される例を示している。図４のケースでは、Bluetoothシステムにおけるチャレンジの伝送遅延または処理遅延によって、２つのユニットのACO値が異なる結果となり、いったん暗号化がオンされると通信不能になってしまっていた。２つのユニットは、等しいACO値（すなわち、ACOm＝ACOn）を用いて、図７に示すケースを開始する。図７において、step701で、ユニットＡは認証要求またはチャレンジAU_RANDAを生成し、それをユニットＢに送信する。同様に、step703で、ユニットＢも認証要求またはチャレンジAU_RANDBを生成し、それをユニットＡに送信する。step705で、ユニットＢは、step701でユニットＡによって生成されたチャレンジを受信し、署名付応答SRESAおよびACOn+1を生成する。ACOn+1は、AU_RANDAおよび過去のACO値（すなわちACOn）の関数として演算される。そして、署名付応答SRESAがユニットＡに送信される。これはstep707で、時刻tAに受信される。その後、ユニットＡは、AU_RANDAおよび過去のACO値ACOmの関数であるACOm+1を生成することができる。ユニットＡはまた、このステップで、ユニットＢが真正かどうかを検証できるように、予期される署名付応答SRES'Aも生成することもできる。step709で、ユニットＡはstep703でユニットＢによって生成されたチャレンジを受信し、これに応答して、署名付応答SRESBを生成するとともに、AU_RANDB，ACOm+1の関数であるACOm+2を演算する。この各ACO値の演算は、例えば式（３）に示したような交換律を満たすバイナリ演算を用いて実行することができる。そして、ユニットＡは署名付応答をユニットＢに送信し、これはstep711で、時刻tBに受信される。Bluetooth仕様書のルールの下では、２つの認容要求がほぼ同時に生成されたとき、ユニットＢは、（step703で生成されたチャレンジで開始した）オープンイベントの間にユニットＡからチャレンジを受信したという事実を認識し、将来の使用のためにACOn+1を保持することになる。しかし、本発明によれば、step711の時刻tBで、新たな値ACOn+2がAU_RANDB，ACOn+1の関数として演算されることになる。この演算は、例えば式（３）に示したような交換律を満たすバイナリ演算で実現できる。
【００６４】
本発明の適用によって、ユニットＡ，ユニットＢがそれぞれstep713，step715で暗号化をオンすることを決定した時点で、両ユニットにおける暗号化鍵を求めるための最新のACO値は互いに等しく、そのため暗号化がオンになったとしても通信を維持することができる。なお、図７では、あるユニットによってイベントが生じ、そのイベントがクローズされるまで、そのユニットによって各ACO値が演算され利用されなかったが、これは必須事項ではない。そのユニットに係るACO値は、そのユニットによってチャレンジが発行された時点やその他適当な時点で演算するようにしてもよい。ただし、あるチャレンジイベントに係るACO値が、そのイベントがクローズされる前に利用される場合には、例えばイベントが消失した、イベントが戻らない、イベントがタイムアウトした等のケースを考えると問題が残る。
【００６５】
本発明は、多くの特長を有し、従来手法に関する問題を解決する。これにより保証応答時間にリアルタイムを要求することが不要になる。ACOの演算の順序も問題にならない。レイヤ間での異なる遅延によるリアルタイムの問題も軽減される。したがって、本発明は、受信の順序に関係なくACO値を演算するので、同一の通信システムにおいてリアルタイム装置と非リアルタイム装置とを混在させることが可能になる。ACO値は、伝送、受信、処理におけるあらゆる遅延とも関係なく演算される。さらに、本発明の計算量も無視しうるものである。従来手法に比して余分な記憶容量も必要とならない。
【００６６】
以上、特定の実施形態を参照して本発明について説明したが、上述の好適な実施形態とは異なる態様で本発明を実現できることは明らかであろう。
【００６７】
また、以上では特定の実施形態を参照して、本発明によって、通信における遅延によってACOパラメータが２つのユニット間で一致しなくなるという問題が解決されることを説明した。しかし、少なくとも一部で過去の値を用いる関数のパラメータを生成するという原理は、遅延によってかかるパラメータを一致させることに問題を生じるあらゆるシステムに適用することができるものである。このようなシステムには、例えば、予測不能な遅延を生じ問題を起こす可能性のあるあらゆるリアルタイムシステムが含まれる。このようなシステムの例としては、移動電話システム、無線ページングシステム、無線インターネットシステム等の無線システム、ならびに、インターネット、陸上有線電話システム、ダイヤルアップ・ネットワークシステム、ＬＡＮ、ＷＡＮ等の有線システムがある。通信リンクの両端でデータ交換を行うアプリケーションを有するあらゆるシステムにおいて、予測不能な遅延による問題が生じる場合に、本発明を適用するすることが有益となろう。
【００６８】
よって、好適な実施形態は単なる説明に過ぎず、いかようにも限定的な解釈をすべきではない。本発明の技術的範囲は、前述の説明からではなく「請求の範囲（claims）」によって与えられ、この請求の範囲内に包含される改変、均等物はすべて本発明の技術的範囲に含まれることを意図するものである。
【図面の簡単な説明】
【図１】  それぞれリンクマネージャ、ベースバンド送信機、ベースバンド受信機を備える２つのユニットのブロック図である。
【図２】  ２つのユニットが最終的に同一のACO値を有することになるケースを示す認証シグナリングのタイミングチャートである。
【図３】  ２つのユニットが最終的に相異なるACO値を有することになるケースを示す従来技術の認証シグナリングのタイミングチャートである。
【図４】  信号遅延のために２つのユニットが相異なるACO値を有することになるケースを示す従来技術の認証シグナリングのタイミングチャートである。
【図５】  本発明の実施形態に係るACO値の演算のフローチャートである。
【図６】  通信システムにおいて本発明がどのように実現されるかを説明するタイミングチャートである。
【図７】  所定のルールを適用する通信システムにおいて本発明がどのように実現されるかを説明するタイミングチャートである。
【図１】
0004694751.tif 000006
【図２】
0004694751.tif 000007
【図３】
0004694751.tif 000008
【図４】
0004694751.tif 000009
【図５】
0004694751.tif 000010
【図６】
0004694751.tif 000011
【図７】
0004694751.tif 000012