(57)【要約】【課題】方法及びシステムが、対称秘密鍵を有する第１のデバイスと非対称公開鍵及び私有鍵を有する第２のデバイスとの間でメッセージを暗号化及び復号化するためのリンク鍵を確立する。【解決手段】第１のデバイスは、秘密鍵を公開鍵で暗号化するとともに第１の乱数を秘密鍵で暗号化する。第２のデバイスは、秘密鍵を私有鍵で復号化するとともに第１の乱数を秘密鍵で復号化する。次に、第２のデバイスが第２の乱数を秘密鍵で暗号化し、第１のデバイスにおいてこの第２の乱数が秘密鍵で復号化される。次に、第１及び第２のデバイスは、第１及び第２の乱数を組み合わせて、当該第１及び第２のデバイス間でメッセージを暗号化及び復号化するためのリンク鍵を確立することができる。【選択図】図５
2004364303.tif 000002
【特許請求の範囲】
【請求項１】
対称秘密鍵を有する第１のデバイスと非対称公開及び私有鍵を有する第２のデバイスとの間でメッセージを暗号化及び復号化するためのリンク鍵を確立する方法であって、
前記第１のデバイスにおいて前記秘密鍵を前記公開鍵で暗号化することと、
前記第１のデバイスにおいて第１の乱数を前記秘密鍵で暗号化することと、
前記第２のデバイスにおいて前記秘密鍵を前記私有鍵で復号化することと、
前記第２のデバイスにおいて前記第１の乱数を前記秘密鍵で復号化することと、
前記第２のデバイスにおいて第２の乱数を前記秘密鍵で暗号化することと、
前記第１のデバイスにおいて前記第２の乱数を前記秘密鍵で復号化することと、
前記第１及び第２のデバイスの間でメッセージを暗号化及び復号化するための前記リンク鍵を確立するために、前記第１及び第２のデバイスにおいて前記第１及び第２の乱数を組み合わせることと
を含む方法。
【請求項２】
前記第１のデバイスは低減機能デバイスであり、前記第２のデバイスは全機能デバイスである請求項１に記載の方法。
【請求項３】
第１の証明書により前記公開鍵を認証することと、
前記第１のデバイスにおいて前記第１の証明書を検証することと
をさらに含む請求項１に記載の方法。
【請求項４】
第２の証明書により前記暗号化した秘密鍵及び前記第１の乱数を認証することと、
前記第２のデバイスにおいて前記第２の証明書を検証することと
をさらに含む請求項３に記載の方法。
【請求項５】
第１の証明書により前記公開鍵を認証することと、
前記第１のデバイスにおいて前記第１の証明書を検証することと、
第２の証明書により前記暗号化した秘密鍵及び前記第１の乱数を認証することと、
前記第２のデバイスにおいて前記第２の証明書を検証することと
をさらに含む請求項１に記載の方法。
【請求項６】
前記第１の証明書は、前記第１のデバイスの第１の識別番号を含み、前記第２の証明書は、前記第２のデバイスの第２の識別番号を含む請求項５に記載の方法。
【請求項７】
前記第１のデバイスは、第１の識別番号を有し、前記第２のデバイスは、第２の識別番号を有し、
前記第１及び第２の識別番号を連結することと、
前記第１及び第２の乱数の組み合わせをハッシュ鍵として有するハッシュ関数に従って前記リンク鍵を作成することと
をさらに含む請求項１に記載の方法。
【請求項８】
対称秘密鍵を有する第１のデバイスと、
前記ネットワークを介して前記第１のデバイスに接続された、非対称公開鍵及び私有鍵を有する第２のデバイスと
を備えたデバイスネットワークにおいて、メッセージを暗号化及び復号化するためのリンク鍵を確立するシステムであって、
前記第１のデバイスにおいて前記秘密鍵を前記公開鍵で暗号化するとともに第１の乱数を前記秘密鍵で暗号化する手段と、
前記第２のデバイスにおいて前記秘密鍵を前記私有鍵で復号化するとともに前記第１の乱数を前記秘密鍵で復号化し、かつ第２の乱数を前記秘密鍵で暗号化する手段と、
前記第１のデバイスにおいて前記第２の乱数を前記秘密鍵で復号化する手段と、
前記第１及び第２のデバイスにおいて前記第１及び第２の乱数を組み合わせて、前記第１及び第２のデバイスの間でメッセージを暗号化及び復号化するための前記リンク鍵を確立する手段と
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には暗号化に関し、特に暗号鍵の確立に関する。
【背景技術】
【０００２】
暗号化システムは、データの安全な送信及び格納を必要とする様々な用途で用いられている。安全な送信は、コンピュータ、電話、ファクシミリ装置、及び他のデバイス間で必要である。安全な格納は、メモリ、ディスク、スマートカード、及びポータブルデバイスに格納されるデータに必要である。暗号化の主な目標は、全ての場合に、通信及び格納されるデータを不正な盗聴及びアクセスに対して安全にすることである。
【０００３】
暗号化では現在までに、２つの相互に排他的な種類の鍵及びプロトコル、すなわち対称暗号化及び非対称（公開鍵）暗号化が知られている。
【０００４】
対称暗号化では、暗号化と復号化に同一の秘密鍵が用いられる。この場合、双方が秘密鍵を知っている必要がある。対称プロトコルの安全性は、暗号化と復号化に単一の秘密鍵を用いる安全性を上回ることはできない。対称鍵は、主に鍵の機密性に頼っているため、秘密鍵は、それほど大きくなくともよい（例えば１２８ビット）。対称プロトコルは、比較的高速で実施が容易である。対称鍵方式の計算の複雑性及び電力消費量は、公開鍵演算に比べると取るに足りない。しかしながら、対称プロトコルにおける鍵交換は、複雑になる可能性があり、攻撃者による攻撃に常にさらされている。
【０００５】
対称プロトコルでは、鍵の管理に関して３つの問題が認識されている。第１に、秘密鍵は、危殆化する可能性がある。この問題を解決する唯一の方法は、秘密鍵を頻繁に変更することである。第２に、対称暗号化は、１つのグループ内の個人の一意のペアが異なる秘密鍵を用いて通信を行う場合、多数の秘密鍵を必要とする。第３に、秘密鍵は、それが暗号化するメッセージよりも価値が高い。したがって、秘密鍵は、公開鍵暗号化プロトコルのような安全なプロトコルによって確立されなければならない。
【０００６】
非対称すなわち公開鍵暗号化では、２つの異なる鍵が用いられる。誰もがアクセスできる公開鍵は、暗号化に用いられ、受信者のみが知っている私有鍵は、復号化に用いられる。公開鍵プロトコルの安全性は、公開鍵を解析して私有鍵を割り出すことの難しさに頼っている。公開鍵を用いれば、多数の別個の鍵セットを維持する必要がなく、双方の間で秘密鍵を交換するための初期化プロセスが必要ない。また、公開鍵は、同報通信の複雑性も低い。しかしながら、公開鍵は、非常に大きくなければならない（例えば１０２４ビット）。これにより、計算及び通信の複雑性ならびに電力消費が増す。
【０００７】
これは、小型の低電力デバイス、例えば、ポータブルＰＤＡ、携帯電話、及びセンサで問題となる。公開鍵暗号化方法の複雑性は、対称暗号化方法の約１０００倍である。さらに、公開鍵は、一般に入手可能であるため、詐欺師に用いられる可能性がある。このことにより、認証が問題となる。
【０００８】
公開鍵管理における認証問題の１つの可能な解決策は、認証されたユーザに秘密鍵を発行する鍵配布センタ（ＫＤＣ）を用いることである。このセンタは、送信メッセージのアイデンティティ認証の基礎を提供する。問題は、秘密鍵のレポジトリとなる中心施設を設けねばならず、この施設は、何らかの信用機関によって運営されなければならないことである。用途によっては、この問題を克服することはほぼ不可能である。
【０００９】
暗号鍵の管理は、対称及び非対称鍵暗号化の両方において最も難しい安全性の問題である。安全な鍵及びプロトコルを開発することは容易ではないが、そのようなプロトコルに用いられる鍵を確実に秘密にしておくことはさらに困難なタスクである。対称及び公開鍵システムの両方で最も一般的な攻撃点は鍵管理である（Schneier著「暗号化の応用（Applied Cryptography）（John Wiley & Sons, Inc., p.140, 1994）」を参照）。
【００１０】
鍵の確立には様々な交換プロトコルが既知であり、Shamirのスリーパスプロトコル（米国特許４，７４８，６６８号）、ＣＯＭＳＥＴプロトコル、Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ及びＡｄｌｅｍａｎ（ＲＳＡ）公開鍵プロトコル（米国特許第４，４０５，８２９号）、Ｅｌ  Ｇａｍａｌ公開鍵プロトコル、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ公開鍵プロトコルなどがある（米国特許第４，２００，７７０号、同第４，２１８，５８２号、同第４，４２４，４１４号、及びSchneier（pp.376-381）（全て参照により本明細書中に援用）を参照）。対称鍵の交換に公開鍵プロトコルを使用することは依然として、スモールフォームファクタデバイスにとって問題である。
【００１１】
図１は、従来技術の、新しいリンク鍵σを確立するための対称認証鍵交換を示す（Beller他著「ポータブル通信システム上でのプライバシー及び認証（Privacy and Authentication on a Portable Communications System）」（IEEE Journal on Selected Areas in Communications, Vol. 11, No. 6, Aug. 1993）（Ｂｅｌｌｅｒ−Ｃｈａｎｇ−Ｙａｃｏｂｉ）（参照により本明細書に援用）を参照）。鍵交換は、デバイスＡとデバイスＢとの間で鍵配布センタ（ＫＤＣ）を用いて行われる。
【００１２】
図２は、初期化プロセスを示し、図３は、チャレンジ−応答機構を用いた認証プロセスを示す。最初に、デバイスＡとデバイスＢの両方が、プロトコルの開始前に永続性のある共通秘密鍵ＫＡＢを知っていなければならない。これは、ＫＤＣがデバイスの秘密鍵すべての大きなデータベースを維持しなければならないことを意味する。このデータベースは、保護や維持が難しい。この要件は、複数のサービスプロバイダが関わる場合に、特に問題となる。これらのサービスプロバイダがデータベースを共有する場合を除き、デバイスＡはプロバイダ毎に別個の秘密鍵を必要とする。秘密鍵プロトコルを用いない場合、デバイスＢは、Ｎ個のデバイスへ同報通信するメッセージに対してＮ個の異なる認証タグを計算して付加しなければならない。
【００１３】
図４は、従来技術の公開鍵に基づく認証鍵交換方式を示す（Aziz他著「不正アクセスを防ぐための安全な通信プロトコル−無線ローカルエリアネットワークのプライバシーと認証（A secure communications protocol to prevent unauthorized access-privacy and authentication for wireless local area networks）」（IEEE Personal Communications, First Quarter 1994）（Ａｚｉｚ−Ｄｉｆｆｉｅ）（参照により本明細書中に援用）を参照）。
【００１４】
対称交換とは対照的に、公開鍵に基づく認証鍵交換は、多数の別個の秘密鍵セットを維持する必要がなく、二者間で永続的な秘密鍵を共有するための初期化プロセスがない。しかしながら、共有の共通鍵を用いない場合、より多くの認証情報が必要となる。さらに、公開鍵は、より複雑なモジュラ乗算、べき乗、または楕円曲線上の点の乗算を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
したがって、鍵を格納するための大きなデータベースを必要とせず、鍵の同期問題がない認証鍵の確立方法が必要とされている。
【課題を解決するための手段】
【００１６】
方法及びシステムが、対称秘密鍵を有する第１のデバイスと非対称公開鍵及び私有鍵を有する第２のデバイスとの間でメッセージを暗号化及び復号化するためのリンク鍵を確立する。
【００１７】
第１のデバイスは、秘密鍵を公開鍵で暗号化するとともに、第１の乱数を秘密鍵で暗号化する。第２のデバイスは、秘密鍵を私有鍵で復号化するとともに、第１の乱数を秘密鍵で復号化する。
【００１８】
次に、第２のデバイスが第２の乱数を秘密鍵で暗号化し、第１のデバイスにおいてこの第２の乱数が秘密鍵で復号化される。
【００１９】
次に、第１及び第２のデバイスは、第１及び第２の乱数を組み合わせて、当該第１及び第２のデバイス間でメッセージを暗号化及び復号化するためのリンク鍵を確立することができる。
【００２０】
さらに、検証可能な証明書によりデバイス間の鍵及び乱数の交換を認証することが可能である。
【発明の効果】
【００２１】
デバイスの処理能力、パラメータ記憶容量及び符号空間が限られている場合、本発明によるハイブリッド認証鍵プロトコルは、集約的な公開鍵暗号化演算をなくすことができる。必要となるのは３つの対称鍵演算のみであり、２つの比較的単純な公開鍵演算は、オフラインで行うことができる。本ハイブリッド法は、Ａｚｉｚ−Ｄｉｆｆｉｅ及びＢｅｌｌｅｒ−Ｃｈａｎｇ−Ｙａｃｏｂｉ公開鍵に基づくプロトコルと比べて、帯域幅、ＲＦＤ側の計算及び記憶要件の性能がよい。本発明は、対称プロトコルによく見られる鍵の配布及び格納問題も解決する。
【発明を実施するための最良の形態】
【００２２】
システム構造
図９は、ネットワーク１００を介して１つまたは複数の全機能デバイス（ＦＦＤ）１０２につながった低減機能デバイス（ＲＦＤ）１０１を示す。本発明は、ハイブリッドな認証鍵交換方法を用いて、デバイス１０１及び１０２の暗号鍵を確立する。ネットワークは、認証局（ＣＡ）１１０にも接続することができる。
【００２３】
ＲＦＤデバイス１０１は、関連する対称秘密鍵を有し、ＦＦＤ１０２は、関連する非対称公開及び秘密鍵を有する。
【００２４】
システム動作
図１０は、ＲＦＤデバイスとＦＦＤデバイスが両者間でメッセージを暗号化及び復号化するために用いることができるリンク鍵の確立方法の基本動作を示す。
【００２５】
ＦＦＤデバイス１０２は、公開鍵ＰＫＢ１００１を同報通信する。
【００２６】
ＲＦＤデバイス１０１は、秘密鍵ＳＫＡ１０１１を公開鍵で暗号化する（１０１０）とともに第１の乱数ＲＡ１０１２を秘密鍵で暗号化し（１０２０）、両方の暗号化した値１０１３及び１０１４をＦＦＤデバイスに送る。
【００２７】
ＦＦＤデバイスは、秘密鍵を私有鍵ｐＫＢ１０３１で復号化し（１０３０）第１の乱数を秘密鍵で復号化する（１０４０）。
【００２８】
次に、ＦＦＤは、第２の乱数ＣＢ１０５１を秘密鍵で暗号化し（１０５０）、暗号化した値１０５２をＲＦＤに送る。
【００２９】
ＲＦＤは、第２の乱数を復号化する（１０６０）。
【００３０】
すると、ＲＦＤとＦＦＤの両方が第１及び第２の乱数を組み合わせて（１０７０）下式により、メッセージ１０８１を暗号化及び復号化する（１０８０）ためのリンク鍵λ１０７１を確立することができる。
【００３１】
【数１】
2004364303.tif 000003
【００３２】
図５は、本発明によるハイブリッドな認証鍵の確立方法のよりロバスト性のある変形を示す。上記のように、鍵交換は、低減機能デバイス（ＲＦＤ）Ａ１０１（例えば、小型のポータブルデバイス）のうちの１つと、全機能デバイス（ＦＦＤ）Ｂ１０２（例えば、ネットワークのサーバコンピュータ、サービスプロバイダ、または「マスタ」システム）との間で、リンク鍵σ５００を確立するためになされる。ここで、ＲＦＤ  Ａは、第１の識別番号ＩＤＡを有し、ＦＦＤは、第２の識別番号ＩＤＢを有する。
【００３３】
本方法は、ＲＦＤがバッテリー駆動であり、計算力及び記憶容量が限られている用途（例えば、ポータブルコンピューティングデバイス、携帯電話、またはセンサ）に特に有用である。全機能デバイスＢには、電力や処理の制限がない。全てのデバイスは、図９に示すようなネットワーク１００（例えば、パーソナルエリアネットワーク（ＰＡＮ）またはローカルエリアネットワーク（ＬＡＮ））により互いに接続される。他のネットワークも用いることができ、ネットワークは、複数のデバイスを互いに、また他のデバイスネットワークに接続できることを理解されたい。
【００３４】
本発明によるハイブリッドな認証鍵交換方法により、ＲＦＤにおける費用の高い公開鍵による暗号化及び署名作成がなくなる。これらの動作は、可能な場合、効率的な対称鍵に基づく動作と置き換えられる。
【００３５】
初めに、プロトコルは、ＲＦＤのみが、プレインストールされた永続性のある秘密鍵ＳＫＡを有しているものと仮定する。利点として、従来技術の対称プロトコルと異なり、ＦＦＤが秘密鍵を知っている必要はない。ＦＦＤ１０１は、公開鍵ＰＫＢをネットワーク１００内の全てのＲＦＤ１０１に同報通信または他の方法で配布する。
【００３６】
このロバスト性のある変形において、公開鍵ＰＫＢは、認証局（ＣＡ）から取得した証明書ＣｅｒｔＢにより認証される。この証明書は、ＣＡの公開検証プロセスを実行することによって確認される。
【００３７】
ＲＦＤ  Ａは、認証されたＰＫＢのコピーを用いて、次のようにＣＡから証明書ＣｅｒｔＡを取得する（５１０）。
ＣｅｒｔＡ＝＜ＩＤＡ、ＥＰＫＢ（ＫＡ）、ＳｉｇＣＡ（ＩＤＡ、ＥＰＫＢ（ＫＡ））＞
ここで、秘密鍵ＳＫＡは、公開鍵ＰＫＢで暗号化される（Ｅ）。このプロセス中、ＲＦＤ  Ａは、２つの単純な公開鍵演算すなわち小さなモジュラべき乗を行う。これらの演算は、オフラインで予め計算しておくことができる。これによりＲＦＤ  Ａは、ＦＦＤ  Ｂと通信するための証明書ＣｅｒｔＡを得る。
【００３８】
演算Ｒａｎｄ（ｋ）により、プロトコルは、ＲＦＤ  ＡがＦＦＤ  Ｂの認証に対するチャレンジとして、第１の乱数ＣＡを生成すると開始する。この乱数は、秘密鍵ＳＫＡによりＥＳＫＡ（ＣＡ）に暗号化される。次にＲＦＤ  Ａは、これらを、証明書とともにメッセージβとしてＦＦＤ  Ｂに送る（５２０）。ＦＦＤ  Ｂは、このメッセージをＲＦＤ  Ａから受け取ると、ＣＡの公開検証を用いて証明書を確認する。証明書が有効である場合、プロトコルは続行する。
【００３９】
ＲＦＤ  Ｂは、私有鍵ｐＫＢを用いて復号化、すなわちＥ−１（ＥｐＫＢ（ＳＫＡ））を行い、秘密鍵ＳＫＡを得る。すると、秘密鍵ＳＫＡは、ＲＦＤ  Ａ及びＦＦＤ  Ｂが共有する対称秘密鍵となる。ＦＦＤ  Ｂは、第２の乱数ｃＢを生成する。秘密鍵ＳＫＡを用いて、暗号化したメッセージＥＳＫＡ（ｃＡ、ＩＤＢ，ｃＢ）をＲＦＤ  Ａに送り返す（５３０）。ＲＦＤ  Ａは、このメッセージを復号化して、ｃＡ、ＩＤＢ、及びｃＢを求める。ＲＦＤ  Ａ以外に秘密鍵ＳＫＡを知っているのはＦＦＤ  Ｂだけなので、ＲＦＤ  Ａは、メッセージがＦＦＤ  Ｂからのものであることを知る。これにより、ＦＦＤ  Ｂの認証プロセスが完了する。
【００４０】
次に、ＲＦＤ  Ａは、第２の乱数ｃＢを秘密鍵ＳＫＡで暗号化し、それをメッセージαとしてＦＦＤ  Ｂに送り返す（５４０）。ＦＦＤ  Ｂは、メッセージを受け取ると、復号化して、それが第２の乱数ｃＢを含むかどうかを判定する。含む場合、ＲＦＤ  Ａの認証は完了し、ＲＦＤ  ＡとＦＦＤ  Ｂの両方が、次の組み合わせによりリンク鍵σ５００を求めることができる。
σ＝ＨＭＡＣＫ（ＩＤＡ｜ＩＤＢ）
ここで、ＨＭＡＣは、一方向の安全なハッシュメッセージ認証コード関数であり、記号「｜」は、連結を示し、Ｋは下式であり、ＨＭＡＣ関数の鍵として用いられる。
【００４１】
【数２】
2004364303.tif 000004
【００４２】
認証
ＲＦＤ  ＡとＦＦＤ  Ｂの識別番号は、ＣＡが発行した証明書によって認証される。この証明書は、デバイスＡ及びＢがサービスに初めて加入したときに取得される。証明書は、必要に応じて、安全なチャネル１１１を介してＣＡ  １１０に対し更新することができる。これがほぼ全ての認証プロトコルに共通する仮定である。
【００４３】
証明書を受け取るために、デバイスは、公開鍵を識別番号とともに、安全なチャネル１１１を介してＣＡ１１０へ送る。するとＣＡは、私有鍵を用いて、連結したメッセージのハッシュ値に署名し、署名した証明書と公開鍵を、安全なチャネルを介してデバイスへ送り返す。
【００４４】
ＲＦＤ−ＦＦＤ認証は、次のチャレンジペアによって実現する。
（ＥＫＡ（ｃＡ）、ＥＫＡ（ｃＡ、ＩＤＢ、ｃＢ））
及び
（ＥＫＡ（ｃＡ、ＩＤＢ、ｃＢ）、ＥＫＡ（ｃＢ））
【００４５】
攻撃者が秘密鍵ＫＡを知らずに応答を発見することは不可能である。したがってＲＦＤ  Ａは、ＦＦＤ  Ｂのみが応答を作成できることを確信している。さらに、攻撃者は、２つの暗号化された乱数ｃＡ及びｃＢについて何ら情報を得ることができない。したがって、それぞれの側のリンク鍵への寄与は、他方の側に安全に転送される。
【００４６】
ＲＦＤとＦＦＤの両方が、組み合わされてリンク鍵５００を形成する乱数ｃＡ及びｃＢに寄与するため、いずれの側もリンク鍵の選択を完全に制御することはできず、ＲＦＤ  ＡとＦＦＤ  Ｂの両方がリンク鍵の新しさを保障できる。
【００４７】
本発明の利点として、ＣＡにおいて全てのデバイスの秘密鍵の大きなデータベースを保護及び維持する必要がない。さらに、対称的な従来技術の方法と同様に、秘密鍵の同期問題がない。ＲＦＤ  Ａはいつでも、ＦＦＤ  Ｂに事前に通知せずとも、秘密鍵ＫＡを変更して新しい証明書を取得することができる。また、ＦＦＤ  ＢもＣＡにアクセスする必要がある。ＲＦＤ  Ａが新しい秘密鍵を新しい証明書とともにＦＦＤ  Ｂに送ると、ＦＦＤ  Ｂは、単に古い鍵を新しい秘密鍵と置き換える。
【００４８】
計算の複雑性
本発明によるハイブリッド方式は、ＲＦＤとＦＦＤの両方で対称鍵及び公開鍵暗号化演算の両方を伴う。ＣＡ１１０は通常、電力消費を心配する必要がないため、安全に有線接続される（１１１）。対称鍵演算の計算の複雑性は、公開鍵演算の計算の複雑性に比べると取るに足りない。システムではＦＦＤ１０２よりも遥かに多くのＲＦＤ１０１があり、ＲＦＤの電力には制限があるため、主な問題は、ＲＦＤ側での公開鍵演算（すなわち検証（Ｖｅｒ）演算）を減らすことである。
【００４９】
図６に示すように、２００ＭＨｚ  Ｐｅｎｔｉｕｍ（登録商標）  ＰｒｏにおけるＲＳＡ−１０２４、ＤＳＡ−１０２４及びＥＣＤＳＡ−１６８（楕円曲線デジタル署名アルゴリズム）の検証タイミングは、それぞれ０．６、２７及び１９ミリ秒である。したがって、好ましい実施形態は、ＲＳＡ−１０２４を用いて本発明のハイブリッド認証方式の公開鍵演算を行う。これは、ＦＦＤ側に大きなべき乗演算をもたらすが、ＦＦＤの数に対してＦＦＤの数の比率が大きいことを考慮すれば、依然として複雑性の高い利得を達成する。さらに、ＦＦＤにおいて暗号コプロセッサを用いて、これらの費用のかかる演算を容易にすることもできる。今日使われているスマートカードの多くは、高速な標準ＲＳＡプロセスを可能にする暗号コプロセッサを内蔵する（例えばSiemens社のＳＬＥ−６６ファミリー、及びPhilips Semiconductors社のＰ８ＷＥ５０３２ファミリーなど）。
【００５０】
図７は、ＥＣＣの場合の他の公開鍵及び対称鍵に基づくプロトコルと比較したハイブリッド方式の計算の複雑性を示す（Aydos他著「ワイヤレス通信のための楕円曲線暗号化に基づく認証及び鍵合意アルゴリズム（An Elliptic Curve Cryptography-based Authentication and Key Agreement Protocol for Wireless Communication）」（2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications Symposium on Information Theory, Oct. 1998）を参照）。
【００５１】
本発明のハイブリッド方式では、公開鍵の計算費用に比べると取るに足りない３つの単純な対称鍵演算があり、ＲＦＤ側には、１回かつオフラインで前処理ステップ中に行うことができる小さなモジュラべき乗演算が２つあるだけである。より複雑な大きなモジュラべき乗は、ＦＦＤ側で行われる。これは、中国人剰余定理（ＣＲＴ）を用いて高速化することができる。
【００５２】
図７から、本発明のハイブリッド方式の計算の複雑性はＡｚｉｚ−ＤｉｆｆｉｅまたはＢｅｌｌｅｒ−Ｃｈａｎｇ−Ｙａｃｏｂｉの公開鍵に基づく鍵交換プロトコルよりも遥かに小さいことが認められる。明らかに、計算の複雑性が最も低いのは対称鍵に基づくプロトコルであるが、上述したように鍵の管理が問題となる。
【００５３】
ＥＣＣに基づく公開鍵の鍵確立方式では、ＲＦＤ側とＦＦＤ側の両方に１つの署名及び１つの検証演算が必要となる。図６の演算要件に基づき、ＥＣＣに基づく方式に対するハイブリッド方式のリンク鍵確立プロセス毎の全ての計算の複雑性の比率は、次の通りである。
Ｔｈｙｂｒｉｄ−ｔｏｔａｌ／ＴＥＣＣ−ｔｏｔａｌ
＝｛０．６×３＋４３｝／｛２×（５＋１９）｝
＝０．９３３
【００５４】
リンク鍵の確立プロセス毎のＲＦＤ側の計算の複雑性の比率は、次の通りである。
Ｔｈｙｂｒｉｄ−ＲＦＤ／ＴＥＣＣ−ＲＦＤ
＝（０．６×２）／（５＋１９）
＝０．０５
【００５５】
図８は、ＲＦＤ対ＦＦＤについて、ＲＳＡを用いるデバイス毎の計算の複雑性の平均を、ＥＣＣを用いるデバイスと比べた比率を示す。図８から、本発明によるハイブリッドプロトコルは、従来技術のＥＣＣに基づくプロトコルに比べて良好な計算の複雑性を達成することが明らかである。
【００５６】
通信の複雑性
ＲＳＡに基づく公開鍵プロトコルは、認証及び鍵に寄与する情報を８６４バイト用いるのに対し、対称鍵プロトコルは、９６バイトしか必要としない。本発明によるハイブリッド方式では、ＲＦＤが短期間で２つ以上のリンク鍵の確立に同一の鍵ＫＡを用いている限り、ＦＦＤ  Ｂは、秘密鍵ＳＡをキャッシュして複数のセッションの通信の複雑性を抑えることができる。したがって、新しい鍵ＫＡを用いる１回目のセッションでは、２４０バイトの情報が送信され（すなわち２０Ｋｂ／ｓのデータレートで１２ｍｓ）、その後、ＦＦＤ  Ｂが秘密鍵ＫＡをキャッシュしている場合、必要とされるのは９６バイト（すなわち２０Ｋｂ／ｓのデータレートで４．８ｍｓ）のみである。
【００５７】
データ及びコードのためのメモリ要件
実際には、ＫＡ、ＩＤＡ、ＩＤＢ、ｃＡ及びｃＢがそれぞれ１２８ビット長であり、公開鍵暗号化演算に１０２４ビットのＲＳＡが用いられる場合、ＦＦＤがパラメータを格納するために４１６バイトの永続メモリ（すなわち、それ自体の私有鍵とＲＳＡモジュラの２０４８ビットに加えて証明書の１２８０ビット）が必要である。ＲＦＤ側では、３０４バイトのメモリが１２８ビットの秘密鍵と、１２８０ビットの証明書と、１０２４ビットのＲＳＡモジュラとを格納する。
【００５８】
さらに、ＲＦＤには、公開鍵の計算を行うために十分なランダムアクセスメモリ（ＲＡＭ）が必要である。公開鍵ｅ＝３を有する１０２４ビットのＲＳＡの場合、符号には４００バイトのＲＡＭが必要である。全ＲＳＡ及び対称鍵暗号化アルゴリズムの符号要件は、約５Ｋバイトとなる。
【００５９】
本発明を好ましい実施形態の例として記載してきたが、本発明の精神及び範囲内で様々な他の適応形態及び変更形態を実施できることが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入る変形及び変更形態をすべて網羅することである。
【図面の簡単な説明】
【００６０】
【図１】従来技術における認証対称鍵の交換のブロック図である。
【図２】図１の交換の初期化のブロック図である。
【図３】図１の交換のチャレンジ及び応答のブロック図である。
【図４】従来技術における認証公開鍵の交換のブロック図である。
【図５】本発明によるハイブリッドな認証鍵交換のブロック図である。
【図６】公開鍵を用いて行われる検証動作の表である。
【図７】本発明の対称及び非対称方法の動作をハイブリッドな方法と比較した表である。
【図８】デバイスの比率の関数としての計算の複雑性のグラフである。
【図９】本発明を用いたネットワークを示す図である。
【図１０】本発明によるリンク鍵の確立方法のフロー図である。
【図１】
2004364303.tif 000005
【図２】
2004364303.tif 000006
【図３】
2004364303.tif 000007
【図４】
2004364303.tif 000008
【図５】
2004364303.tif 000009
【図６】
2004364303.tif 000010
【図７】
2004364303.tif 000011
【図８】
2004364303.tif 000012
【図９】
2004364303.tif 000013
【図１０】
2004364303.tif 000014
【外国語明細書】
2004364303.tif 000015
2004364303.tif 000016
2004364303.tif 000017
2004364303.tif 000018
2004364303.tif 000019
2004364303.tif 000020
2004364303.tif 000021
2004364303.tif 000022
2004364303.tif 000023
2004364303.tif 000024
2004364303.tif 000025
2004364303.tif 000026
2004364303.tif 000027
2004364303.tif 000028
2004364303.tif 000029
2004364303.tif 000030
2004364303.tif 000031
2004364303.tif 000032
2004364303.tif 000033
2004364303.tif 000034
2004364303.tif 000035
2004364303.tif 000036
2004364303.tif 000037
2004364303.tif 000038
2004364303.tif 000039
2004364303.tif 000040
2004364303.tif 000041
2004364303.tif 000042
2004364303.tif 000043