(57)【特許請求の範囲】
【請求項１】
データネットワークを通じて、パスワードを共有する二つのコンピュータシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信方法において、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐ及びｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、本方法は、
一方のシステムが、少なくとも前記パスワードの関数の結果を計算し、少なくとも該パスワードの該関数の結果のうち少なくとも一部分についてランダム演算を実行し、そしてｇｘと、少なくとも前記パスワードの関数のランダム化された結果とに対する該群演算を実行することにより計算したパラメータｍを、他方のシステムに送信するステップを有し、ｍの少なくとも一部は、Ｇｐ，ｑの外部にあり、
これにより、他方のシステムは、ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行し、前記ｇｘを抽出し、前記共有秘密ｇｘｙを計算することが可能であることを特徴とする通信方法。
【請求項２】
少なくとも該パスワードの該関数のうちの少なくとも一部分の前記ランダム化は、前記群Ｚｐ＊からランダムに選択されるパラメータｈを計算し、前記パラメータｈを指数ｑ乗し、ｈｑと少なくとも該パスワードの該関数の該結果とに該群演算を実行することによって実行されることを特徴とする請求項１記載の方法。
【請求項３】
前記一方のシステムはクライアントであり、前記他方のシステムはサーバであることを特徴とする請求項１記載の方法。
【請求項４】
前記一方のシステムが、前記他方のシステムからｇｙを受信し、前記共有秘密ｇｘｙを生成するステップをさらに有することを特徴とする請求項１記載の方法。
【請求項５】
前記他方のシステムから受信されたパラメータを、前記パスワードと、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記共有秘密のうちの少なくとも１つとの関数と比較することによって、前記一方のシステムが前記他方のシステムを認証するステップをさらに有することを特徴とする請求項４記載の方法。
【請求項６】
前記一方のシステムが、前記パスワードと、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記共有秘密のうちの少なくとも１つとの関数を、前記他方のシステムに送信するステップをさらに有し、これにより、前記他方のシステムは、前記一方のシステムを認証することが可能であることを特徴とする請求項４記載の方法。
【請求項７】
前記一方のシステムが、前記共有秘密と、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記パスワードのうちの少なくとも１つとの関数としてセッション鍵を生成するステップをさらに有することを特徴とする請求項４記載の方法。
【請求項８】
データネットワークを通じて、パスワードを共有する二つのコンピュータシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信方法において、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐおよびｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、本方法は、
一方のシステムが少なくとも前記パスワードの関数の結果を計算し、前記結果のうち少なくとも一部分についてランダム演算を実行し、そしてｇｘと少なくとも前記パスワードの関数のランダム化された結果とに対する前記群演算を実行することにより計算したパラメータｍを、他方のシステムが一方のシステムから受信するステップを含み、ｍの少なくとも一部は、Ｇｐ，ｑの外部にあり、
他方のシステムが、ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行して、ｇｘを抽出して前記共有秘密ｇｘｙを計算するステップとを有することを特徴とする通信方法。
【請求項９】
少なくとも該パスワードの前記関数の該結果のうちの少なくとも一部分の前記ランダム化は、前記群Ｚｐ＊からランダムに選択されるパラメータｈを計算し、前記パラメータｈを指数ｑ乗し、ｈｑと少なくとも該パスワードの前記関数の前記結果とに該群演算を実行することによって実行されることを特徴とする請求項８記載の方法。
【請求項１０】
データネットワークを通じて、パスワードを共有する二つのシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信のためのプロトコルに従う装置であって、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐおよびｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、
本装置は前記一方のシステムに関連しており、本装置は少なくとも１つのプロセッサを有し、前記プロセッサは、
少なくとも前記パスワードの関数の結果を計算し、少なくとも該パスワードの該関数の前記結果のうち少なくも一部についてランダム演算を実行し、そしてｇｘと少なくとも前記パスワードの関数のランダム化された結果とに対する前記群演算を実行することにより一方のシステムが計算したパラメータｍを、他方のシステムに送信するように動作し、ｍの少なくとも一部は、Ｇｐ，ｑの外部にあり、
これにより、他方のシステムは、ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行して、ｇｘを抽出して前記共有秘密ｇｘｙを計算することが可能であることを特徴とする装置。
【請求項１１】
少なくとも該パスワードの前記関数の結果のうち一部分の前記ランダム化は、前記群Ｚｐ＊からランダムに選択されるパラメータｈを計算し、前記パラメータｈを指数ｑ乗し、ｈｑと少なくとも該パスワードの前記関数の前記結果とに該群演算を実行することによって実行されることを特徴とする請求項１０記載の装置。
【請求項１２】
前記一方のシステムはクライアントであり、前記他方のシステムはサーバであることを特徴とする請求項１０記載の装置。
【請求項１３】
前記一方のシステムに関連する前記少なくとも１つのプロセッサが、さらに、前記他方のシステムからｇｙを受信し、前記共有秘密ｇｘｙを生成するように動作することを特徴とする請求項１０記載の装置。
【請求項１４】
前記一方のシステムに関連する前記少なくとも１つのプロセッサが、さらに、前記他方のシステムから受信されるパラメータを、前記パスワードと、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記共有秘密のうちの少なくとも１つとの関数と比較することによって、前記他方のシステムを認証するように動作することを特徴とする請求項１３記載の装置。
【請求項１５】
前記一方のシステムに関連する前記少なくとも１つのプロセッサが、さらに、前記パスワードと、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記共有秘密のうちの少なくとも１つとの関数を、前記他方のシステムに送信するように動作し、これにより、前記他方のシステムは、前記一方のシステムを認証することが可能であることを特徴とする請求項１３記載の装置。
【請求項１６】
前記一方のシステムに関連する前記少なくとも１つのプロセッサが、さらに、前記共有秘密と、前記一方のシステムの識別子、前記他方のシステムの識別子、ｍ、ｇｙ、および前記パスワードのうちの少なくとも１つとの関数としてセッション鍵を生成するように動作することを特徴とする請求項１３記載の装置。
【請求項１７】
データネットワークを通じて通信を行って、パスワードを共有する二つのシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信プロトコルに従う装置であって、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐおよびｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、
本装置は前記他方のシステムに関連しており、本装置は少なくとも１つのプロセッサを有し、前記プロセッサは、
少なくとも前記パスワードの関数の結果を計算し、少なくとも該パスワードの関数の前記結果のうち少なくとも一部分についてランダム演算を実行し、そしてｇｘと少なくとも前記パスワードの関数のランダム化された結果とに対する前記群演算を実行することにより前記一方のシステムが計算したパラメータｍを、前記一方のシステムから受信し、ｍの少なくとも一部はＧｐ，ｑの外部にあり、そして、
ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行して、ｇｘを抽出して前記共有秘密ｇｘｙを計算する、
ように動作することを特徴とする装置。
【請求項１８】
少なくとも該パスワードの前記関数の結果のうち少なくとも一部分の前記ランダム化は、前記群Ｚｐ＊からランダムに選択されるパラメータｈを計算し、前記パラメータｈを指数ｑ乗し、ｈｑと前記関数に関する前記結果とに対して該群演算を実行することによって実行されることを特徴とする請求項１７記載の装置。
【請求項１９】
データネットワークを通じて、パスワードを共有する二つのシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信のための１つ又は複数のプログラムを含むコンピュータ読み取り可能な媒体において、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐおよびｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、
前記１つまたは複数のプログラムは、一方のシステムに関連するプロセッサにより実行される時に、
少なくとも前記パスワードの関数の結果を計算し、少なくとも該パスワードの該関数の前記結果のうち少なくとも一部分についてランダム演算を実行し、そしてｇｘと少なくとも前記パスワードの関数のランダム化された結果とに対する前記群演算を実行することにより前記一方のシステムが計算したパラメータｍを、前記一方のシステムから前記他方のシステムに送信するステップを実行し、ｍの少なくとも一部はＧｐ，ｑの外部にあり、
これにより、他方のシステムは、ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行して、ｇｘを抽出して前記共有秘密ｇｘｙを計算することが可能であることを特徴とするコンピュータ読み取り可能な媒体。
【請求項２０】
データネットワークを通じて、パスワードを共有する二つのシステム間で、群Ｇｐ，ｑに関するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ型鍵交換を用いて共有秘密ｇｘｙを生成する通信のための１つ又は複数のプログラムを含むコンピュータ読み取り可能な媒体において、
ｇは両システムに既知の群生成元であり、ｘは一方のシステムに既知の指数であり、ｙは他方のシステムに既知の指数であり、前記群は群演算および群逆演算を有し、Ｇｐ，ｑは、群Ｚｐ＊の部分群であり、ｐおよびｑは、ｑと互いに素である値ｒに対してｐがｒｑ＋１に等しいような素数であり、前記１つまたは複数のプログラムは、他方のシステムに関連するプロセッサにより実行される時に、
少なくとも前記パスワードの関数の結果を計算し、少なくとも該パスワードの該関数の前記結果のうち少なくとも一部分についてランダム演算を実行し、そしてｇｘと少なくとも前記パスワードの関数のランダム化された結果とに対する前記群演算を実行することにより前記一方のシステムが計算したパラメータｍを、前記一方のシステムから受信するステップを含み、ｍの少なくとも一部はＧｐ，ｑの外部にあり、
ｍと少なくとも前記パスワードの前記関数のランダム化された結果とに対して前記群逆演算を実行して、ｇｘを抽出して前記共有秘密ｇｘｙを計算するステップとを実行することを特徴とするコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク認証および鍵交換を提供する技術に関し、特に、そのようなネットワーク認証および鍵交換に関連する計算効率を改善する技術に関する。
【０００２】
【従来の技術】
ネットワークを通じての認証は、リモートクライアントがネットワークサーバにアクセスすることを可能にするシステムのセキュリティ（安全性）の重要な部分である。認証は一般に、次のうちの１つまたは複数のものを確認することにより実行される。
・ユーザが知っているもの。例えば、パスワード。
・ユーザ自体。すなわち、指紋のような生体計測情報。
・ユーザが持っているもの。すなわち、スマートカードのような何らかの識別トークン。
【０００３】
例えば、現金自動預入支払機（ＡＴＭ）は、これらのうちの２つ、すなわち、ユーザが持っているもの（ＡＴＭカード）と、ユーザが知っているもの（個人識別番号（暗証番号、ＰＩＮ））とを確認する。ＡＴＭ認証は、データネットワークを通じての認証よりもずっと容易である。その理由は、ＡＴＭ自体は信頼されたハードウェアとみなされ、ＡＴＭカードの存在を確認し正しい情報を安全に中央取引サーバに転送することが信用されているからである。
【０００４】
認証に加えて、鍵交換は、データネットワークを通じての通信の重要な部分である。クライアントとサーバが認証された後、安全な通信チャネルがそれらの間に設定されなければならない。これは一般に、クライアントとサーバが、認証に続く通信の間に用いるためのセッション鍵と呼ばれるある鍵を交換することによって実行される。
【０００５】
データネットワーク、特に、インターネットのような公衆データネットワークを通じての認証は困難である。その理由は、クライアントとサーバの間の通信は、多くの異なるタイプの攻撃を受けやすいからである。例えば、盗聴(eavesdropping)攻撃では、敵は、クライアントとサーバの間の通信を傍受することにより、秘密情報を知る可能性がある。敵は、パスワード情報を知った場合、その情報をサーバに対して再生（リプレイ）して正当なクライアントになりすますことが可能となる。これをリプレイ攻撃という。リプレイ攻撃は、クライアントから送られたパスワードが暗号化されている場合でも有効である。その理由は、敵は、実際のパスワードを知る必要はなく、代わりに、サーバが正当なクライアントから期待しているもの（この場合、暗号化されたパスワード）をサーバに提供すればよいからである。もう１つのタイプの攻撃は、スプーフィング攻撃である。これは、敵がサーバになりすますことにより、クライアントは、正当なサーバと通信していると信じるが、実際のところは敵と通信しているというものである。このような攻撃では、クライアントは、要注意(sensitive)情報を敵に提供してしまう可能性がある。
【０００６】
さらに、パスワードに基づく認証プロトコルでは、パスワードが辞書攻撃を受けるくらい弱くなる可能性が存在する。辞書攻撃は、必要なパスワードに関する何らかの既知情報に対して、多数のありそうなパスワード（例えば、英語辞書中の全単語）をテストすることによって実行される、パスワードに対する力ずくの攻撃である。この既知情報は、公に利用可能なこともあるし、上記の技術のうちの１つにより敵が入手したものであることもある。ユーザはしばしば、覚えやすい、したがって推測しやすいパスワードを選択するので、辞書攻撃はしばしば有効である。
【０００７】
ネットワーク認証にはさまざまな技術が知られている。これらの公知技術は２つに分類される。第１の分類には、クライアントシステム上に永続的記憶データを要求する技術が含まれる。第２の分類には、クライアントシステム上に永続的記憶データを要求しない技術が含まれる。
【０００８】
第１の分類に関して、永続的記憶データには、決して漏れてはならない秘密(secret)データ（例えば、認証サーバと共有される秘密鍵）も、改竄を防止しなければならない、秘密ではないが要注意の(sensitive)データ（例えば、認証サーバの公開鍵）も含まれる。いずれのタイプの永続的データでも、データを敵からの攻撃から守るには、追加のセキュリティ条件が必要である。さらに、パスワードおよび永続的記憶データの両方に依拠する認証プロトコルを用いるときには、一方の漏洩が他方の弱点となることがある。例えば、秘密鍵が漏洩すると、パスワードに対する辞書攻撃が可能となることがある。この第１のクラスのプロトコルでのもう１つの問題点は、永続的記憶データは、鍵の生成および配送を必要とするが、これは面倒なことがあり、一般にシステムの柔軟性が低下することである。
【０００９】
第２の分類は、クライアントにおける永続的記憶データを要求しないため、パスワードのみによる認証プロトコルと呼ばれる。クライアントは、正当なパスワードを提供することができればよい。潜在的に弱いパスワードを用いて強力なセキュリティおよび認証を提供するということは、矛盾しているように思われる。しかし、安全であるように設計されたパスワードのみによるユーザ認証および鍵交換のプロトコルがいくつか存在する。これらのプロトコルは、D. Jablon, "Strong Password-Only Authenticated Key Exchange", ACM Computer Communication Review, ACM SIGCOMM, 26(5):5-20, 1996、に記載されている。これらのパスワードのみによるプロトコルのうち注目すべきものには次のものがある。
・ＥＫＥ(Encrypted Key Exchange)（S. M. Bellovin and M. Merritt, "Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks", Proceedings of the IEEE Symposium on Research in Security and Privacy, pp.72-84、に記載）
・Ａ−ＥＫＥ(Augmented-EKE)（S. M. Bellovin and M. Merritt, "Augmented Encrypted Key Exchange: A Password-Based Protocol Secure Against Dictionary Attacks and Pasword File Compromise", Proceedings of the First Annual Conference on Computer and Communications Security, 1993, pp.244-250、に記載）
・Ｍ−ＥＫＥ(Modified EKE)（M. Steiner, G. Tsudik, and M. Waidner, "Refinement and Extension of Encrypted Key Exchange", ACM Operating System Review, 29:22-30, 1995、に記載）
・ＳＰＥＫＥ(Simple Password EKE)およびＤＨ−ＥＫＥ(Diffie-Hellman EKE)（いずれも、D. Jablon, "Strong Password-Only Authenticated Key Exchange", ACM Computer Communication Review, ACM SIGCOMM, 26(5):5-20, 1996、に記載）
・ＳＲＰ(Secure Remote Password Protocol)（T. Wu, "The Secure Remote Password Protocol", Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium, pp.97-111, 1998、に記載）
・ＯＫＥ(Open Key Exchange)（Stefan Lucks, "Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys", Security Protocol Workshop, Ecole Normale Superieure, April 7-9, 1997、に記載）
・ＡＫＥ(Authenticated Key Exchange)（M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated Key Exchange Secure Against Dictionary Attacks", Advances in Cryptology, pp.139-155, Eurocrypt 2000、に記載）
・米国特許出願第０９／３５３，４６８号（出願日：１９９９年７月１３日、発明者：P. D. MacKenzie et al.、発明の名称："Secure Mutual Network Authentication Protocol (SNAPI)"）
【００１０】
【発明が解決しようとする課題】
公知のパスワードのみによる認証プロトコルのほとんどでの問題点は、これらは安全であることが証明されていないことである。実際、S. Patel, "Number Theoretic Attacks on Secure Password Schemes", Proceedings of the IEEE Symposium on Research in Security and Privacy, pp.236-247, 1997、に記載されているように、ＥＫＥプロトコルは、いくつかの数論的攻撃を受ける可能性がある。ＡＫＥプロトコルは、安全であることが証明されているが、安全性を証明するために強い仮定を必要とする。さらに、ＳＮＡＰＩプロトコルも、安全であることが証明されているが、このプロトコルは、ディフィ・ヘルマン型のアルゴリズムではなくＲＳＡアルゴリズムに基づいている。
【００１１】
米国特許出願第０９／６３８，３２０号（出願日：２０００年８月１４日、発明者：V. V. Boyko et al.、発明の名称："Secure Mutual Network Authentication and Key Exchange Protocol"）には、安全であることが証明可能な、安全な、パスワードのみによる相互ネットワーク認証および鍵交換のプロトコルが開示されている。このプロトコルは、ディフィ・ヘルマン型の共有秘密を使用するが、二当事者が互いに共有パスワードを用いて認証することができるように変更されている。
【００１２】
【課題を解決するための手段】
本発明は、安全であることが証明可能な、安全な、パスワードのみによる相互ネットワーク認証プロトコルを提供する。本発明のプロトコルによれば、二当事者が、Diffie-Hellman型の鍵交換を用いて共有秘密を生成する。知られているように、Diffie-Hellman型の鍵交換によれば、特定の群に対する群生成元ｇと、一方当事者に既知の指数ｘと、他方当事者に既知の指数ｙと、共有秘密ｇｘｙがある。一方当事者がｇｘを生成し、他方当事者がｇｙを生成し、両者はこれらの値を交換して、それぞれが共有秘密ｇｘｙを生成することができるようにする。Diffie-Hellmanは鍵交換プロトコルを定義しているが、このプロトコルは認証の観点を有しない。
【００１３】
本発明によれば、Diffie-Hellman型の共有秘密を用いるが、二当事者が共有パスワードを用いて互いを認証することができるように修正されたプロトコルが実現される。さらに、本発明の発明者は、このプロトコルが安全であることを証明した。本発明によれば、一方当事者がDiffie-Hellman値ｇｘを生成し、これを、ある群演算を用いて少なくともパスワードの関数と結合する。関数の結果のうち群の外部にある部分はランダム化される。その結果得られる値は、他方当事者へ送信される。群演算は、用いられる特定の群に対して定義され、以下で詳細に説明する。今の目的のためには、あらゆる群は１つの群演算と、対応する群逆演算とを有することを認識すれば十分である。
【００１４】
他方当事者は、値を受信すると、受信した値と、少なくともパスワードの関数とに対して群逆演算を実行し、関数の結果のうち群の外部にある部分のランダム化を除去して、ｇｘを抽出する。これにより、他方当事者は、自己のｙの知識を用いて、共有秘密ｇｘｙを生成することができる。
【００１５】
ここに記載するように、群演算および群逆演算をDiffie-Hellman型の鍵交換プロトコルとともに用いることは、パスワードのみによる相互ネットワーク認証プロトコルに比べて利点がある。関数の結果のうち群の外部にある部分のランダム化は、一方当事者によって実行される演算に関連する計算量を低減する。本発明は、通信チャネルにアクセス可能な敵による攻撃に対して安全であることを証明することができるプロトコルを提供する。
【００１６】
上記のように、Diffie-Hellman値ｇｘは、少なくともパスワードの関数と結合される。「少なくとも」という用語を用いるのは、さまざまな実施例において、ｇｘは、パスワードのみの関数と結合されることもあるが、パスワードが特定の当事者のペアに対して一意的であることを保証するために、パスワードと、プロトコルに対する当事者の識別子との関数と結合されることもあるからである。
【００１７】
本発明の一実施例によれば、当事者は、少なくともいくつかのパラメータの関数を計算し、計算した値を他方当事者に送信し、受信された値を各当事者が自己の計算値に照らしてチェックすることによって、互いを認証することが可能である。この計算に用いられるパラメータは、少なくとも１つの当事者識別子、Diffie-Hellman値（ｇｘまたはｇｙ）、共有秘密、および共有パスワードとすることが可能である。これらの値のうちの少なくとも１つの関数を計算することにより、当事者は、他方当事者が共有パスワードを所有していることを認証することが可能である。
【００１８】
本発明の上記およびその他の特徴および利点は、添付の図面とともに、以下の実施例の詳細な説明から明らかとなる。
【００１９】
【発明の実施の形態】
暗号方式は、二当事者間に安全な通信を提供するための周知の技術である。本発明のさまざまな実施例について説明する前に、いくつかの背景的知識および基本的用語について説明する。
【００２０】
略式には、集合Ｓから集合Ｔへの関数ｆについて、Ｓに属するすべてのｘに対してはｆ（ｘ）は計算が容易であるが、Ｔに属するほとんどのｙに対しては、ｆ（ｘ）＝ｙとなるようなＳの元ｙを見つけるのが計算量的に実行不能である場合、ｆは一方向性関数であるという。一方向性関数の一例は、法指数演算である。ｐを大きい素数とし、ｇを、ｐを法とする乗法群（すなわち、１，...，ｐ−１の範囲の数）の生成元とする。この場合、ｆ（ｘ）＝ｇｘ  ｍｏｄ  ｐは一般に、一方向性関数であると仮定される。その逆関数（離散対数関数と呼ばれる）は、計算が困難である。離散対数関数の計算が困難な他の群もある。例えば、ある種の楕円曲線群である。
【００２１】
ｋおよびｌをセキュリティパラメータとする。ただし、ｋは、主セキュリティパラメータであり、ハッシュ関数および秘密鍵に対する一般的なセキュリティパラメータとみなされ（例えば、１６０ビット）、ｌ＞ｋは、離散対数に基づく公開鍵に対するセキュリティパラメータとみなされる（例えば、１０２４または２０４８ビット）。｛０，１｝＊を、有限二進数列の集合とし、｛０，１｝ｎを、長さｎの二進数列の集合とする。実数値関数ε（ｎ）は、任意のｃ＞０について、すべてのｎ＞ｎｃに対してε（ｎ）＜１／ｎｃとなるようなｎｃ＞０がある場合、無視しうるという。少なくともサイズｋのｑと、サイズｌのｐを、ある値ｒに対してｐ＝ｒｑ＋１がｑと互いに素であるような素数とする。ｇを、Ｚｐ＊の、サイズｑの部分群の生成元とする。この部分群をＧｐ，ｑと呼ぶことにする。
【００２２】
Diffie-Hellman鍵交換と呼ばれる鍵交換プロトコル（W. Diffie and M. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol.22, no.6, 644-654, 1976、に記載）は、法指数関数に基づいている。具体的には、二当事者ＡとＢが、図１に記載するプロトコルに従って、秘密鍵について合意する。ステップ１０２で、Ａは、群Ｚｑからランダムにｘを選ぶ（すなわち、ｘ∈ＲＺｑである）。ただし、Ｚｑ＝｛０，１，...，ｑ−１｝（あるいは単に、ｑを法とする整数）である。ステップ１０４で、Ａは、Ｘ＝ｇｘ  ｍｏｄ  ｐを計算する。ステップ１０６で、Ａは、ＸをＢへ送信する。ステップ１０８で、Ｂは、Ｚｑからランダムにｙを選ぶ（すなわち、ｙ∈ＲＺｑである）。Ｂは、ステップ１１０で、Ｙ＝ｇｙ  ｍｏｄ  ｐを計算し、ステップ１１２で、ＹをＡへ送信する。この時点で、共有秘密ｇｘｙ（すなわち、秘密鍵）が、ＡとＢの両者により計算可能となる。なお、以下、ｍｏｄ  ｐで考えていることが明らかである場合には、記法を簡単にするため、ｍｏｄ  ｐの記載を省略することがある。Ｘ＝ｇｘがステップ１０６でＡからＢへ送信されたため、ステップ１１６で、Ｂは、Ｘｙを計算することにより、共有秘密ｇｘｙを計算することができる。同様に、Ｙ＝ｇｙがステップ１１２でＢからＡへ送信されたため、ステップ１１４で、Ａは、Ｙｘを計算することにより、共有秘密ｇｘｙを計算することができる。こうして、共有秘密Ｓは、安全な通信のためのセッション鍵として、ＡとＢにより用いられることが可能となる。
【００２３】
Diffie-Hellman鍵交換は、ある種の楕円曲線群のような、離散対数関数の計算が困難な他の群の上でも実行可能である。群は当業者に周知であり、I. N. Herstein, "Topics in Algebra", 2nd edition, John Wiley and Sons, New York, 1975、には次のように記載されている。空でない元の集合Ｇにおいて、積と呼ばれ・で表される次のような二項演算が定義される場合、Ｇは群をなすという。
１．ａ，ｂ∈Ｇならば、ａ・ｂ∈Ｇ（閉じている）。
２．ａ，ｂ，ｃ∈Ｇならば、ａ・（ｂ・ｃ）＝（ａ・ｂ）・ｃ（結合律）
３．すべてのａ∈Ｇに対して、ａ・ｅ＝ｅ・ａ＝ａとなるような元ｅが存在する（Ｇにおける単位元の存在）。
４．任意のａ∈Ｇに対して、ａ・ａ−１＝ａ−１・ａ＝ｅとなるような元ａ−１が存在する（Ｇにおける逆元の存在）。
【００２４】
こうして、より一般的に、Diffie-Hellman鍵交換は、特定の群において作用する。ただし、秘密鍵ｘおよびｙは、群の元の指数である。そこで、ｇ∈Ｇを群生成元とする群Ｇ＝｛ｇ，ｇ・ｇ，ｇ・ｇ・ｇ，ｇ・ｇ・ｇ・ｇ，...｝を考える。ここで、・は群演算である。例として、Ｇの群演算が乗算である場合、Ｇ＝｛ｇ１，ｇ２，ｇ３，ｇ４，...｝である。Ｇの群演算が加算である場合、Ｇ＝｛１ｇ，２ｇ，３ｇ，４ｇ，...｝である。本発明は、さまざまな群を用いて実施可能であるため、以下の説明において、記法ｇｘは、群生成元ｇに対して群演算をｘ回作用させることを意味する。さらに、任意の群について、ここで／で表す群逆演算も存在する。以下の説明において、群逆演算は次のように定義される。すなわち、ｘおよびｙに対する群逆演算、すなわち、ｘ／ｙは、ｘ・ｙ−１として定義される。
【００２５】
図２に、両当事者が共有パスワードを所有する明示的認証アプローチによる相互認証および鍵交換プロトコルを示す。図２の通信プロトコルは、前掲の米国特許出願第０９／６３８，３２０号（出願日：２０００年８月１４日、発明者：V. V. Boyko et al.、発明の名称："Secure Mutual Network Authentication and Key Exchange Protocol"）に開示されている。一般に、この通信プロトコルは、ディフィ・ヘルマン型の共有秘密を使用するが、二当事者が互いに共有パスワードを用いて認証することができるように変更されている。さらに、このプロトコルは安全であることが証明されている。
【００２６】
図２において、図の左側に示すステップは第１当事者Ａによって実行され、図の右側に示すステップは第２当事者Ｂによって実行される。通常、Ａはクライアントマシン（コンピュータシステム）であり、Ｂはサーバマシン（コンピュータシステム）である。しかし、これは必ずしも必要ではなく、ＡおよびＢは、代表的な場合を示す例としてそれぞれクライアントおよびサーバと示されているだけである。したがって、理解されるように、図２に示したアプローチは、ＡおよびＢがクライアントおよびサーバである場合に限定されるものではなく、任意の二当事者ＡおよびＢに適用可能である。矢印は、当事者間の通信を表す。このプロトコルによれば、サーバは自分自身をクライアントに認証してもらい、クライアントは自分自身をサーバに認証してもらう。両者の認証が完了した後、それぞれが、後の安全な通信に使用可能なセッション鍵を生成する。
【００２７】
プロトコルを開始する前に、クライアントおよびサーバは、クライアントがサーバとの認証に用いるパスワードπを所有すると仮定する。
【００２８】
なお、以下のプロトコルは、サーバおよびクライアントの両方を認証する。したがって、サーバおよびクライアントのいずれも真正であるとは仮定されず、このため、サーバまたはクライアントのいずれかが敵である可能性がある。クライアントは、自分自身を認証してもらってサーバにアクセスしようとする敵である可能性がある。サーバは、疑いを持たないクライアントから要注意情報を得ようとして別の真正なサーバのふりをしようとする敵である可能性がある。
【００２９】
図２に戻り、ステップ２０２で、クライアントは、Ｚｑから指数ｘとしてランダムな値を選ぶ。次に、ステップ２０４で、クライアントは、ｍ＝ｇｘ・（Ｈ１（Ａ，Ｂ，π））ｒ  ｍｏｄ  ｐとして、パラメータｍを計算する。ただし、Ａはクライアントの一意的識別子であり、Ｂはサーバの一意的識別子であり、πは、この特定のサーバに対するクライアントのパスワードであり、Ｈ１はランダムハッシュ関数であり、・は群演算を表す。Ｈ１（Ａ，Ｂ，π）は、結果がＧ｛ｐ，ｑ｝内にあることを保証するために、ｒ乗される。略式には、集合Ｓから集合Ｔへの関数Ｈについて、Ｈの出力がランダムに見える場合、すなわち、少なくとも、Ｓに属する入力ｘで関数が計算されるまでは予測不能である場合、ランダムハッシュ関数と呼ばれる。Ｈ１は、Ｚｐ＊においてランダムに見えるものを出力しなければならないため、｜ｐ｜＋ｓｅｃビット（ただし、｜ｐ｜はｐのビット数であり、ｓｅｃはセキュリティパラメータである）を出力すべきである。セキュリティパラメータは、例えば、１６０とすることが可能である。一般にこのようにふるまう既知の関数には次のものがある。
・ＳＨＡ−１（FIPS 180-1, "Secure Hash Standard", Federal Information Processing Standards Publication 180-1, 1995、に記載）
・ＲＩＰＥＭＤ−１６０（H. Dobbertin, A. Bosselaers, B. Preneel, "RIPEMD-160: a strengthened version of RIPEMD", Fast Software Encryption, 3rd Intl. Workshop, 71-82, 1996、に記載）
【００３０】
各クライアント・サーバ対ごとに一意的であることを保証するために、パスワードのみではなく、組（タプル）（Ａ，Ｂ，π）を用いる。発見的セキュリティに要求されるのはパスワードのみであるが、以下で詳細に説明するように、セキュリティの形式的証明を保証するため、クライアントおよびサーバの名前が使用される。したがって、図２のプロトコルによれば、少なくともパスワードの関数と、Diffie-Hellman値ｇｘとに対して群演算を実行することにより、少なくともパスワードの関数をDiffie-Hellman値ｇｘと結合する。これは、パスワードの知識を有する者によってのみDiffie-Hellman値ｇｘがパラメータｍから抽出可能であることを保証するので、プロトコルの重要なステップである。このDiffie-Hellman値ｇｘの抽出については、ステップ２１４に関して以下で詳細に説明する。ステップ２０６で、クライアントは、パラメータｍをサーバへ送信する。
【００３１】
パラメータｍを受信すると、ステップ２０８で、サーバは、パラメータ値が０ｍｏｄ  ｐでないことを保証するために、パラメータ値をテストする。この値が０  ｍｏｄ  ｐである場合、サーバはプロトコルを終了する。０はＺｐ＊に属さないからである。この値が０  ｍｏｄ  ｐでない場合、ステップ２１０で、サーバは、Ｚｑから指数ｙとしてランダムな値を選ぶ。ステップ２１２で、サーバは、パラメータμに計算されたDiffie-Hellman値ｇｙを代入する。次に、ステップ２１４で、サーバは、受信したパラメータｍを用いて、次式のように、Diffie-Hellman共有秘密ｇｘｙ（このプロトコルではσで表す）を計算する。
σ＝（ｍ／（Ｈ１（Ａ，Ｂ，π））ｒ）ｙ  ｍｏｄ  ｐ
次に、このステップについて、さらに詳細に説明する（記法を簡単にするためｍｏｄ  ｐの記載を省略する）。まず、想起されるべき点であるが、上記のように、任意の群演算に対して、ｘおよびｙに対する群逆演算、すなわち、ｘ／ｙがｘ・ｙ−１として定義されるような群逆演算がある。そこで、当業者には認識されるように、ステップ２１４におけるｍ／（Ｈ１（Ａ，Ｂ，π））ｒの計算は、ｍと、少なくともパスワードの関数とに対する群逆演算を実行している。ステップ２０４からのｍの値を代入すると、ｇｘ・（Ｈ１（Ａ，Ｂ，π））ｒ／（Ｈ１（Ａ，Ｂ，π））ｒ＝ｇｘを得る。したがって、サーバは、正しいパスワードπを所有している場合、受信したパラメータｍの値からDiffie-Hellman値ｇｘを抽出することができる。こうして、ステップ２１４における計算の結果、サーバは、Diffie-Hellman共有秘密ｇｘｙを生成する。
【００３２】
次に、ステップ２１６で、サーバは、ｋ＝Ｈ２ａ（Ａ，Ｂ，ｍ，μ，σ，π）を計算する。ただし、Ｈ２ａは、ｓｅｃビット（ただしｓｅｃはセキュリティパラメータ）を出力しなければならないもう１つのランダムハッシュ関数である。パラメータｋは、以下で説明するように、サーバが正しいパスワードを所有していることを認証するために、クライアントＡにより使用されることになる。ステップ２１８で、サーバは、パラメータμおよびｋをクライアントへ送信する。
【００３３】
パラメータμおよびｋを受信すると、クライアントは、ステップ２２０で、σ＝μｘ  ｍｏｄ  ｐを計算する。μ＝ｇｙであるため、μｘ＝ｇｘｙはDiffie-Hellman共有秘密である。ステップ２２２で、クライアントは、自己のπの知識を用いてＨ２ａ（Ａ，Ｂ，ｍ，μ，σ，π）を計算し、その結果が、ステップ２１８でサーバから受信したパラメータｋに等しいかどうかをテストする。これらが等しい場合、クライアントはサーバを認証したことになる。これらが等しくない場合、サーバは認証されなかったので、クライアントはプロトコルを終了する。ステップ２２４で、クライアントはｋ′＝Ｈ２ｂ（Ａ，Ｂ，ｍ，μ，σ，π）を計算する。これは、以下で説明するように、サーバがクライアントを認証するために用いられることになる。ステップ２２６で、クライアントは、Ｋ＝Ｈ３（Ａ，Ｂ，ｍ，μ，σ，π）としてセッション鍵Ｋを生成する。ステップ２２８で、クライアントは、ｋ′をサーバへ送信する。今度も、Ｈ２ｂおよびＨ３は、ｓｅｃビット（ただしｓｅｃはセキュリティパラメータ）を出力しなければならないランダムハッシュ関数である。
【００３４】
ステップ２３０で、サーバは、自己のπの知識を用いてＨ２ｂ（Ａ，Ｂ，ｍ，μ，σ，π）を計算し、その結果が、ステップ２２８でサーバから受信したパラメータｋ′に等しいかどうかをテストする。これらが等しい場合、サーバはクライアントを認証したことになる。これらが等しくない場合、クライアントは認証されなかったので、サーバはプロトコルを終了する。ステップ２３２で、サーバは、Ｋ＝Ｈ３（Ａ，Ｂ，ｍ，μ，σ，π）としてセッション鍵Ｋを生成する。
【００３５】
この時点で、クライアントとサーバの両者は互いを認証したことになり、クライアントとサーバはいずれも同一の安全なセッション鍵Ｋを生成している。これは、クライアントとサーバの間の後の安全な通信に用いることが可能である。
【００３６】
このように、図２の通信プロトコルは、パスワードに基づく認証のある鍵交換の利点を提供するが、パラメータｍをｇｘ・（Ｈ１（Ａ，Ｂ，π））ｒ  ｍｏｄｐとして生成することは、計算量が膨大になる可能性がある。これは、クライアント装置がプロトコルのこの部分を十分に実行するだけの計算資源を有していないときに問題となる。これは、例えば、クライアントＡが、旧世代のパーソナルコンピュータ、スマートカード、あるいは携帯型個人情報端末（ＰＤＡ）のような、小型の遅い装置である場合に起こりうる。また、Ｂがサーバである場合には、クライアントよりも計算能力が高いと仮定されるが、このプロトコルは、２つのクライアント型の装置どうしの間で実行される可能性もあるため、計算効率は、プロトコルの両側で重要である。本発明によれば、図３を参照して説明するように、クライアント側の計算を少なくとも２分の１に低減することができる解決法が提供される。
【００３７】
次に、図３を参照して、本発明の実施例による、両当事者が共有パスワードを所有する、効率の改善された相互認証および鍵交換プロトコルについて説明する。この通信プロトコルは、安全なパスワード認証鍵交換プロトコルであり、Ｇｐ，ｑにおける決定ディフィ・ヘルマン問題（ＤＤＨ：Decision Diffie-Hellman problem）の困難さを仮定する。上記のようなＸ＝ｇｘおよびＹ＝ｇｙのディフィ・ヘルマン値ｇｘｙをＤＨ（Ｘ，Ｙ）で表す。１つの定式化は、Ｇｐ，ｑ内の与えられたｇ，Ｘ，Ｙ，Ｚに対して、Ｘ＝ｇｘおよびＹ＝ｇｙがランダムに選択され、Ｚは、それぞれ半々の確率でＤＨ（Ｘ，Ｙ）またはランダムのいずれかである場合、Ｚ＝ＤＨ（Ｘ，Ｙ）であるかどうかを決定せよ、というものである。ＤＤＨを解くことは、Ｚ＝ＤＨ（Ｘ，Ｙ）をランダムなＺから区別する、ランダム推測を超える無視できない有利さを有する多項式時間の敵を構成することを意味する。
【００３８】
さらに、ハッシュ関数Ｈ２ａ，Ｈ２ｂ，Ｈ３：｛０，１｝＊→｛０，１｝κおよびＨ１：｛０，１｝＊→｛０，１｝ηを定義する。ただし、η≧ｌ＋κである。また、Ｈ１、Ｈ２ａ、Ｈ２ｂ、およびＨ３は、上記の図２のアプローチで用いられたように、独立なランダム関数であると仮定する。なお、Ｈ１はビット列を返すように記載されているが、われわれはその出力に対してｐを法とする数として演算を行う。
【００３９】
図２の通信プロトコルによれば、注意すべき点であるが、クライアントは２つの｜ｑ｜ビット指数演算（ステップ２０４および２２０）と、１つの｜ｒ｜ビット指数演算（ステップ２０４）を実行する。図３に関連して以下で説明するように、本発明の通信プロトコルによれば、クライアントは、３つの｜ｑ｜ビット指数演算を実行するだけでよい。これは一般に、図２にプロトコルに比べてずっと少ない計算しか必要としない。本発明は、以下のようにして、このような利点を提供することができる。パラメータｍを生成するために使用されるハッシュ関数の結果が群Ｇｐ，ｑに属するように強制する代わりに、本発明では、ハッシュ関数の結果はＺｐ＊の任意の元であることを許容し、ハッシュ関数結果のＧｐ，ｑの外側の部分をランダム化する。これにより、ｍの値は、（Ｇｐ，ｑ内のランダム値ではなく）Ｚｐ＊内のランダム値と区別できなくなるが、依然として、ハッシュ値と追加のランダム化を抽出することが可能である。
【００４０】
この場合、追加のランダム化を抽出するために、ｐ＝ｒｑ＋１とする。ただし、ｇｃｄ（ｒ，ｑ）＝１である（ｇｃｄは、最大公約数を表す）。もちろん、（例えば、U. S. Department of Commerce/NIST, Springfield, VA, FIPS186, "Digital Signature Standard", Federal Information Processing Standards Publication 186, 1994、に記載されたＮＩＳＴ公認アルゴリズムを用いて）ランダムに選択されたｑおよびｐに対して、この関係は高い確率で満たされる。
【００４１】
図２と同様に、図３の左側に示すステップは第１当事者Ａによって実行され、図３の右側に示すステップは第２当事者Ｂによって実行される。同様に、代表的な場合を示す例として、Ａはクライアントマシン（コンピュータシステム）と呼ばれ、Ｂはサーバマシン（コンピュータシステム）と呼ばれる。したがって、理解されるように、図３に示したプロトコルは、任意の２つのエンティティあるいは当事者ＡおよびＢに適用可能である。また同様に、矢印は、当事者間の通信を表す。図３のプロトコルによれば、サーバは自分自身をクライアントに認証してもらい、クライアントは自分自身をサーバに認証してもらう。したがって、前に説明したように、サーバおよびクライアントのいずれも真正であるとは仮定されず、このため、サーバまたはクライアントのいずれかが敵である可能性がある。両者の認証が完了した後、それぞれが、後の安全な通信に使用可能な秘密セッション鍵を生成する。
【００４２】
図２のプロトコルと同様に、本発明による図３のプロトコルを開始する前に、クライアントおよびサーバは、クライアントがサーバとの認証に用いるパスワードπを所有すると仮定する。
【００４３】
図３において、ステップ３０２で、クライアントは、Ｚｑから指数ｘとしてランダムな値を選ぶ（すなわち、ｘ∈ＲＺｑである）。ステップ３０４で、クライアントは、群Ｚｐ＊からランダム値ｈを選ぶ（すなわち、ｈ∈ＲＺｐ＊である）。次に、ステップ３０６で、クライアントは、ｍ＝ｇｘ・ｈｑ・Ｈ１（Ａ，Ｂ，π）として、パラメータｍを計算する。ただし、Ａはクライアントの一意的識別子であり、Ｂはサーバの一意的識別子であり、πは、この特定のサーバに対するクライアントのパスワードであり、Ｈ１はランダムハッシュ関数であり、・は群演算を表し、ｈｑはランダム化演算である。想起すべき点であるが、図２のプロトコルでは、Ｈ１（Ａ，Ｂ，π）は、結果がＧｐ，ｑ内にあることを保証するために、ｒ乗される。これに対して、本発明によれば、パラメータｍを生成するために使用されるハッシュ関数の結果が群Ｇｐ，ｑに属するように強制する代わりに、図３のプロトコルでは、ハッシュ関数の結果はＺｐ＊の任意の元であることを許容し、ハッシュ関数結果のＧｐ，ｑの外側の部分をランダム化する。これは、ランダム化演算ｈｑによって実現される。これにより、ｍの値は、Ｇｐ，ｑ内のランダム値ではなくＺｐ＊内のランダム値から区別できなくなるが、依然としてサーバＢは、ハッシュ値と追加のランダム化を抽出することが可能である。ランダムパラメータｈを指数ｑ乗することによって、ハッシュ関数の結果において部分群Ｇｐ，ｑの外部にあるものはすべてランダム化される。
【００４４】
前に説明したように、集合Ｓから集合Ｔへの関数Ｈについて、Ｈの出力がランダムに見える場合、すなわち、少なくとも、Ｓに属する入力ｘで関数が計算されるまでは予測不能である場合、ランダムハッシュ関数と呼ばれる。したがって、Ｈ１は、Ｚｐ＊においてランダムに見えるものを出力しなければならないため、｜ｐ｜＋ｓｅｃビット（ただし、｜ｐ｜はｐのビット数であり、ｓｅｃはセキュリティパラメータである）を出力すべきである。セキュリティパラメータは、例えば、１６０とすることが可能である。今度も、ＳＨＡ−１またはＲＩＰＥＭＤ−１６０が、一般にこのようにふるまう既知の関数である。
【００４５】
図２のプロトコルの場合と同様に、各クライアント・サーバ対ごとに一意的であることを保証するために、パスワードのみではなく、組（タプル）（Ａ，Ｂ，π）を用いる。発見的セキュリティに要求されるのはパスワードのみであるが、セキュリティの形式的証明を保証するため、クライアントおよびサーバの名前が使用される。したがって、図３のプロトコルによれば、少なくともパスワードの関数と、Diffie-Hellman値ｇｘとに対して群演算を実行することにより、少なくともパスワードの関数をDiffie-Hellman値ｇｘと結合する。今度も、これは、パスワードの知識を有する者によってのみDiffie-Hellman値ｇｘがパラメータｍから抽出可能であることを保証するので、プロトコルの重要なステップである。ステップ３０８で、クライアントは、パラメータｍをサーバへ送信する。
【００４６】
パラメータｍを受信すると、ステップ３１０で、サーバは、パラメータ値が０ｍｏｄ  ｐでないことを保証するために、パラメータ値をテストする。この値が０  ｍｏｄ  ｐである場合、サーバはプロトコルを終了する。０はＺｐ＊に属さないからである。この値が０  ｍｏｄ  ｐでない場合、ステップ３１２で、サーバは、Ｚｑから指数ｙとしてランダムな値を選ぶ。ステップ３１４で、サーバは、パラメータμに計算されたDiffie-Hellman値ｇｙを代入する。次に、ステップ３１６で、サーバは、受信したパラメータｍを用いて、次式のように、Diffie-Hellman共有秘密ｇｘｙ（このプロトコルではσで表す）を計算する。
【数１】
0004237970.tif 000002
次に、このステップについて、さらに詳細に説明する。まず、想起されるべき点であるが、上記のように、任意の群演算に対して、ｘおよびｙに対する群逆演算、すなわち、ｘ／ｙがｘ・ｙ−１として定義されるような群逆演算がある。そこで、当業者には認識されるように、ステップ３１６における
【数２】
0004237970.tif 000003
の計算は、ｍと、少なくともパスワードの関数とに対する群逆演算を実行するとともに、クライアントのランダム演算ｈｑに関連するランダム化を抽出している。ステップ３０６からのｍの値を代入すると、ｇｘを得る。したがって、サーバは、正しいパスワードπを所有している場合、受信したパラメータｍの値からDiffie-Hellman値ｇｘを抽出することができる。こうして、ステップ３１６における計算の結果、サーバは、Diffie-Hellman共有秘密ｇｘｙを生成する。
【００４７】
次に、ステップ３１８で、サーバは、ｋ＝Ｈ２ａ（Ａ，Ｂ，ｍ，μ，σ，π）を計算する。ただし、Ｈ２ａは、ｓｅｃビット（ただしｓｅｃはセキュリティパラメータ）を出力しなければならないもう１つのランダムハッシュ関数である。パラメータｋは、以下で説明するように、サーバが正しいパスワードを所有していることを認証するために、クライアントＡにより使用されることになる。ステップ３２０で、サーバは、パラメータμおよびｋをクライアントへ送信する。
【００４８】
パラメータμおよびｋを受信すると、クライアントは、ステップ３２２で、σ＝μｘ  ｍｏｄ  ｐを計算する。μ＝ｇｙであるため、μｘ＝ｇｘｙはDiffie-Hellman共有秘密である。ステップ３２４で、クライアントは、自己のπの知識を用いてＨ２ａ（Ａ，Ｂ，ｍ，μ，σ，π）を計算し、その結果が、ステップ３２０でサーバから受信したパラメータｋに等しいかどうかをテストする。これらが等しい場合、クライアントはサーバを認証したことになる。これらが等しくない場合、サーバは認証されなかったので、クライアントはプロトコルを終了する。ステップ３２６で、クライアントはｋ′＝Ｈ２ｂ（Ａ，Ｂ，ｍ，μ，σ，π）を計算する。これは、以下で説明するように、サーバがクライアントを認証するために用いられることになる。ステップ３２８で、クライアントは、Ｋ＝Ｈ３（Ａ，Ｂ，ｍ，μ，σ，π）としてセッション鍵Ｋを生成する。ステップ３３０で、クライアントは、ｋ′をサーバへ送信する。今度も、Ｈ２ｂおよびＨ３は、ｓｅｃビット（ただしｓｅｃはセキュリティパラメータ）を出力しなければならないランダムハッシュ関数である。
【００４９】
ステップ３３２で、サーバは、自己のπの知識を用いてＨ２ｂ（Ａ，Ｂ，ｍ，μ，σ，π）を計算し、その結果が、ステップ３３０でサーバから受信したパラメータｋ′に等しいかどうかをテストする。これらが等しい場合、サーバはクライアントを認証したことになる。これらが等しくない場合、クライアントは認証されなかったので、サーバはプロトコルを終了する。ステップ３３４で、サーバは、Ｋ＝Ｈ３（Ａ，Ｂ，ｍ，μ，σ，π）としてセッション鍵Ｋを生成する。
【００５０】
この時点で、クライアントとサーバの両者は互いを認証したことになり、クライアントとサーバはいずれも同一の安全なセッション鍵Ｋを生成している。これは、クライアントとサーバの間の後の安全な通信に用いることが可能である。
【００５１】
前述のように、図３を参照して説明した本発明の通信プロトコルは、図２のプロトコルに比べて、クライアント側の計算を少なくとも２分の１に低減する。これは次の例から明らかである。ｐは１０２４ビットの素数であり、ｑは１６０ビットの素数であると仮定する。この場合、ｒは８６４ビットである。Ｚｐ＊におけるあらゆる指数演算は、その指数のビット数に比例する時間を要する。したがって、図２のプロトコルでは、２つのｑビット指数演算および１つのｒビット指数演算が実行されるため、その時間は２×１６０＋８６４＝１１８４に比例するのに対して、（図３で説明した）本発明のプロトコルでは、３つのｑビット指数演算が実行されるため、その時間は３×１６０＝４８０に比例する。このように、この値（４８０）は、図２のプロトコルの場合の値（１１８４）の半分より小さい。
【００５２】
図４に、本発明に従って、２つのエンティティＡとＢの間でパスワード認証鍵交換法を実現するのに適した、データネットワークおよびコンピュータシステムの一般化されたハードウェアアーキテクチャを示す。図示のように、エンティティＡはコンピュータシステム４０２からなり、エンティティＢはコンピュータシステム４０４からなる。２つのコンピュータシステム４０２と４０４は、データネットワーク４０６を通じて接続される。データネットワークは、それを通じてＡとＢが通信をしようとする任意のデータネットワーク（例えば、インターネット）であることが可能であり、本発明は、特定のタイプのネットワークに限定されない。一般に、図４においてラベルされているように、Ａはクライアントマシンであり、Ｂはサーバマシンである。しかし、これは必ずしも必要ではなく、ＡおよびＢは、代表的な場合を示す例としてそれぞれクライアントおよびサーバと示されているだけである。したがって、理解されるように、本発明の通信プロトコルは、ＡおよびＢがクライアントおよびサーバである場合に限定されるものではなく、ＡおよびＢを含む任意のコンピューティング装置に適用可能である。
【００５３】
当業者には直ちに明らかなように、サーバおよびクライアントは、コンピュータプログラムコードの制御下で動作するプログラムされたコンピュータとして実現可能である。コンピュータプログラムコードは、コンピュータ可読媒体（例えば、メモリ）に格納され、コードは、コンピュータのプロセッサによって実行される。本発明の明細書のこの開示が与えられれば、当業者は容易に、ここに記載されたプロトコルを実現するために、適当なコンピュータプログラムコードを作成することが可能である。
【００５４】
図４は、一般的に、ネットワークを通じて通信する各コンピュータシステムの例示的なアーキテクチャを示している。図示のように、クライアント装置は、入出力装置４０８−Ａ、プロセッサ４１０−Ａ、およびメモリ４１２−Ａを有する。サーバシステムは、入出力装置４０８−Ｂ、プロセッサ４１０−Ｂ、およびメモリ４１２−Ｂを有する。理解されるべき点であるが、ここで用いられる「プロセッサ」という用語は、中央処理装置（ＣＰＵ）あるいはその他の処理回路を含む、１つまたは複数の処理装置を含むことを意図している。また、ここで用いられる「メモリ」という用語は、ＲＡＭ、ＲＯＭ、固定記憶装置（例えば、ハードドライブ）、または取り外し可能記憶装置（例えば、ディスケットやＣＤＲＯＭ）のような、プロセッサあるいはＣＰＵに関連するメモリを含むことを意図している。さらに、ここで用いられる「入出力装置」という用語は、データを処理装置に入力するための１つまたは複数の入力装置（例えば、キーボード、マウス）と、処理装置の結果を出力する１つまたは複数の出力装置（例えば、ＣＲＴディスプレイ）とを含むことを意図している。したがって、ここに記載される、本発明の方法を実行するためのソフトウェア命令あるいはコードは、１つまたは複数の関連する記憶装置（例えば、ＲＯＭ、固定または取り外し可能メモリ）に格納され、利用可能なときに、ＲＡＭにロードされ、ＣＰＵによって実行されることが可能である。
【００５５】
以上、本発明の実施例について、添付図面を参照して説明したが、理解されるように、本発明は、上記の具体的実施例に限定されるものではなく、当業者であれば、本発明の技術的範囲あるいは技術思想を離れずに、他のさまざまな変更および修正をすることが可能である。例えば、本発明の技術思想について、上記の図２に記載された通信プロトコルより高い計算効率を提供する通信プロトコルとして説明したが、理解されるように、本発明は、他の通信プロトコルの場合にも適用可能である。例えば、本発明のランダム化演算は、上記の米国特許出願第０９／６３８，３２０号（出願日：２０００年８月１４日、発明者：V. V. Boyko et al.、発明の名称："Secure Mutual Network Authentication and Key Exchange Protocol"）に記載された、他のプロトコル実施例でも使用可能である。例えば、本発明は、前掲の米国特許出願の暗黙的(implicit)認証アプローチの場合にも使用可能である。さらに、本発明の通信プロトコルのハッシュ関数を評価する際にいくつかのパラメータが用いられているが、理解されるように、発見的セキュリティにとってすべてのパラメータが必要とされるわけではない。すなわち、プロトコルが形式的に安全であることを証明するために、追加的パラメータが使用されている。例えば、ステップ３１８、３２４、３２６、３２８、３３２、および３３４で用いられているハッシュ関数においては、関数内のパラメータσのみが、プロトコルを発見的に安全にするために必要とされる。
【００５６】
【発明の効果】
以上述べたごとく、本発明によれば、安全であることが証明可能な、安全な、パスワードのみによる相互ネットワーク認証プロトコルが提供される。
【００５７】
特許請求の範囲の発明の要件の後に括弧で記載した番号がある場合は、本発明の一実施例の対応関係を示すものであって、本発明の範囲を限定するものと解釈すべきではない。
【図面の簡単な説明】
【図１】  Diffie-Hellman鍵交換プロトコルを示す図である。
【図２】両当事者が共有パスワードを所有する、相互認証および鍵交換プロトコルを示す図である。
【図３】本発明の実施例による、両当事者が共有パスワードを所有する、効率の改善された相互認証および鍵交換プロトコルを示す図である。
【図４】本発明に従って１つまたは複数のパスワード認証鍵交換法を実現するのに適した、データネットワークおよびコンピュータシステムの一般化されたハードウェアアーキテクチャの図である。
【符号の説明】
４０２  コンピュータシステム
４０４  コンピュータシステム
４０６  データネットワーク
４０８  入出力装置
４１０  プロセッサ
４１２  メモリ
【図１】
0004237970.tif 000004
【図２】
0004237970.tif 000005
【図３】
0004237970.tif 000006
【図４】
0004237970.tif 000007