【手続補正書】
【提出日】平成18年9月20日(2006.9.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】明細書
【発明の名称】中央局と加入者のグループの間に共通キーを確立するための方法
【特許請求の範囲】
【請求項１】
中央局Ｚと加入者のグループＴ１乃至Ｔｎの間で共通キーｋを確立する方法であって、グループＧおよび要素ｇに関して離散対数の計算が実質的に不可能であるような、公に知られた数学的なグループＧおよびグループＧ内の高いオーダの要素ｇ∈Ｇを含み、一般に知られた閾値方法を用いて、
ａ）乱数ｉが各加入者Ｔｉによって生成され、そして、値ｇｉが、知られた要素ｇ∈Ｇおよび問題の該乱数ｉから各加入者Ｔｉによって計算され、そして該中央局Ｚに送信され、
ｂ）乱数ｚが該中央局Ｚ内で生成され、該乱数ｚおよび該受信された値ｇｉからＧ内の値（ｇｉ）ｚが計算され、これらの値から閾値方法のｎ個のシェア（ｓｉ…ｓｎ）が導出され、そして、シェア（ｓｉ…ｓｎ）から（ｎ、２ｎ−１）閾値方法が構築され、この方法によって暗黙的に与えられる秘密は確立されるべきキーｋであり、該シェア（ｓ１…ｓｎ）とは異なる(ｎ−１)個のさらなるシェア（ｓｎ＋１…ｓ２ｎ−１）が、該中央局Ｚ内でＧ内の値ｇｚと共に計算され、そして加入者Ｔ１−Ｔｎに送信され、
ｃ）各加入者Ｔｉに関して、確立されるべき該キーｋが再構築され、該再構築は、
該中央局Ｚによって送信された該値ｇｚおよび問題の該加入者Ｔｉの該乱数ｉからＧにおける（ｇｚ）ｉに関する値が計算され、結果として生じる値から閾値方法を適用してシェアｓｉが導出され、該シェアｓｉおよび該中央局Ｚによって送信されるシェア（ｓｎ＋１…ｓ２ｎ−１）に基づいて、（ｎ、２ｎ−１）閾値方法の助けによって該キーｋが再構築される方法。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、独立請求項で特定されたものに従った、中央局と加入者のグループの間で共通の暗号キーを確立する方法に関する。関連技術分野には多くの異なった暗号化方法があり、これらの方法は商業的な重要性が増している。これらは一般にアクセス可能な送信媒体上で情報を送信するために使用される。しかし、暗号キーの所有者のみがこの情報をプレーンテキスト（符号化されていないテキスト）で読むことができる。安全ではない通信チャネルを介して共通キーを確立するための知られた方法は、たとえば、W.DiffieおよびW.Hellmanの方法である（ＤＨ方法に関しては、W.DiffieおよびM.Hellmannの「New Directions in Cryptography」（1976年11月、ＩＥＥＥ  Transactions on Information Theory IT-22(6)，第644乃至第654頁）を参照のこと）。Diffie-Hellmannキー交換（ＤＨ７６）は、大きな素数ｐを法として対数を計算することは事実上不可能であるという事実に基づいている。下に説明した例では、アリスとボブは、たがいに秘密にｐよりも小さい（かつｐ−１と互いに素の）数ｘおよびｙをそれぞれ選択することによってこの事実を利用している。次に、彼らは互いに（連続的または同時に）公に知られた数αのｘ（およびそれぞれ、ｙ）べき乗を送信する。彼らはそれぞれ受信されたべき乗から、再びｘおよびｙで累乗を実行することによって共通キーＫ：＝αｘｙを計算することができる。αｘおよびαｙしか見えない攻撃者は、そこからＫを計算することはできない（今日知られている唯一の計算方法は、たとえば基本のｐを法とする底αに対するαｘの対数をまず計算し、ついでαｙをそのべきまで上げることである）。
2002527993.tif 000001
【０００２】
ＤＨキー交換の場合に存在する問題は、アリスは、彼女が実際にボブと通信しているのか、または偽のボブと通信しているのかが分からないことである。ＩＰＳｅｃにおいては、加入者の同一性が信頼できる権限（entity)によってパブリック・キーにリンクされているパブリック・キー認証を使用することによってこの問題が解決される。このようにして会話のパートナの同一性が確認できる。
【０００３】
ＤＨキー交換はまた、有限体ＧＦ（２ｎ）または楕円カーブなどの他の数学的構造を使用しても実装できる。このような代替の方法では、性能を向上することができる。しかしこの方法は２人の加入者の間のキーの一致に関してしか適していない。ＤＨ方法を３人またはそれ以上の加入者（ＤＨグループ）に拡張する種々の試みが行われてきた。M.Steiner、G.Tsudik、およびM.Waidnerは、インドのニューデリーで1996年３月に行われた第３回ＡＣＭ  Conference on Computer and Communications Securityの会報の「Diffie-Hellman Key Distribution Extended to Group Communication」で当技術分野の状態の概要を提供している。
【０００４】
次の表はＤＨ方法がＡ、ＢおよびＣの３人の加入者に拡張された例を示す（どの場合でも計算は法ｐである）。
【表１】
2002527993.tif 000002
【０００５】
２つのラウンドが実行されると、加入者の各々は秘密キーｇａｂｃ ｍｏｄ ｐを計算できる。
【０００６】
これらの拡張のすべてにおいて、次の問題のうち少なくとも１つが発生する。
加入者は所定の方法で構成されなければならず、たとえば上の例では円形に構成されなければならない。
加入者は中央局に対して選択に影響を有しない。
ラウンドの数は加入者の数に依存している。
概して、これらの方法は実装するのが困難であり相当な計算の経費が必要である。
【０００７】
共通キーを確立するための別の方法は、ドイツ特許第195 38 385.0号から知られる。しかしこの方法では、中央局は加入者の秘密キーを知っていなければならない。
【０００８】
また、１９９４年にベルリンで行われたSpringer LNCS EUROCRYPT '94  の会報で、Burmester、Desmedtによる「A Secure and Efficient Conference Key Distribution System」の手法が知られており、ここではキーを生成するために２つのラウンドが必要であり、第２のラウンドで、ｎ人の加入者に関して中央局を通して長さがｐ＝約1000ビットのｎ個の通信を送信することが必要となる。（ｎ、ｔ）閾値方法((n,t) threshold method))と説明される暗号方法も知られている。（ｎ、ｔ）閾値方法では、キーｋは、キーｋが任意のｎ個のｔシャドウから再構築できるように、ｔ部分（シャドウと呼ばれる）に分解できる(Beutelspacher,Schwenk,Wolfenstetterによる「Moderne Verfahren Der kryptographie (Modern Cryptographic Method)(第二版、Vieweg Publishers, Wiesbaden,1998年)」を参照のこと）。
「On the Design of Conference Key Distribution Systems for the Broadcasting Networks」(IEEE Infocom '93、The Conference on Computer Communications Proceedings, Twelth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking: Foundation for the Future (cat. no. 93CH3264-9) (3/28/1993), vol．３の第1406頁乃至第1413頁）で、中央局（議長）およびｎ人の加入者のグループの間で共通キーを確立するための方法が説明されており、ここで閾値方法が使用されている。この手法では、中央局（議長）が共通キーを選択する。この方法は議長と加入者の間で安全なチャネルをあらかじめ想定している。この種の安全なチャネルはたとえば、上記のＤＨ方法（ＤＨ７６）またはその変形例を使用して確立できる。しかしこのために、ｎ人の加入者と中央局（議長）の間で共通キーを相談し、「公共シャドウ(public shadows)」に関して通信を送信するために、各加入者について２つの通信（メッセージ）が必要である。したがって、共通キーを確立するために全部で（２ｎ＋１）個の通信が必要である。
【０００９】
中央局と少なくとも３人の加入者の間の共通キーを生成するための本方法は、ＤＨ方法と同じセキュリティ標準規格を有することが目的とされている。しかしこのコンテキストでは、本方法は容易に実装でき、必要な計算の経費は最小にすべきである。
【００１０】
本発明による方法はこのタスク(task)に等しい。本発明の方法はＤＨ方法と同じ数学的な構造に基づいているため、匹敵するセキュリティ機能を有する。これまで知られた方法内で提案されたグループＤＨ方法と比較すると、本方法は計算の経費および通信の要件の点で大幅に効率的である。
【００１１】
本発明による方法の動作の原理は、次のように説明される。この例では、中央局はＺによって示され、この方法内で定義された加入者はＴ１乃至Ｔｎによって示され、具体的に名付けられていない各単一の加入者はＴｉによって示される。この方法の公に知られた構成要素は、好ましくは大きな素数ｐを法とするすべての整数のグループの倍数である公に知られた数学的グループＧ、および好ましくは高い倍数オーダを有する数０＜ｇ＜ｐであるグループＧの要素ｇを含む。しかしグループＧに関しては、たとえば有限体の倍数グループ、または楕円カーブのポイントのグループなど別の適した数学的構造も使用できる。
【００１２】
この方法は３つの作業ステップで実行できる。第１のステップでは、形態（Ｔｉ、ｇｉ ｍｏｄ ｐ）の通信（メッセージ）が各加入者Ｔｉによって中央局に送信され、加入者Ｔｉのｉは乱数生成器によって選択された乱数である。
【００１３】
第２の作業ステップでは、中央局Ｚにおいて
乱数ｚが生成され、数（ｇｉ）ｚ ｍｏｄ  ｐが各加入者Ｔｉに関して計算される。
これらのｎ個の数から、一般に知られた（ｎ、２ｎ−１）閾値方法を使用して中央局Ｚにおいてｎ人の加入者に関してｎ個のシェアが微分される（導出される）。
（ｎ−１）個のさらなるシェアｓ１−ｓｎ−１が、数ｇｚ ｍｏｄ  ｐと共に中央局ｚ内で選択され、すべての加入者Ｔ１〜Ｔｎに送信される。
【００１４】
第３の作業ステップでは、共通キーｋが各加入者Ｔｉに関して計算される。
（ｇｚ）ｉ ｍｏｄ ｐ＝（ｇｉ）ｚ ｍｏｄ ｐが計算され、
ここから、閾値方法のシェアが微分され、
このシェアおよびｓ１…ｓｎ−１に基づいて、共通キーｋが秘密として決定される。
【００１５】
実際の例に基づいて、本発明による方法はＡ、Ｂ、およびＣの３人の加入者および中央局Ｚに関して以下のように説明される。しかし、加入者の数は任意の所望の数に増加できる。この例では、数ｐの長さは１０２４ビットであり、ｇは少なくとも２１６０の倍数オーダを有する。
【００１６】
本発明による方法は次の方法ステップに従って実行される。
１  加入者Ａ、Ｂ、およびＣは、ｇａ ｍｏｄ ｐ、ｇｂ ｍｏｄ ｐ、およびｇｃ ｍｏｄ ｐを中央局Ｚに送信（送信）する。
２  ｇａｚｍｏｄ  ｐ、ｇｂｚｍｏｄ  ｐおよびｇｃｚｍｏｄ  ｐが中央局において計算され、どの場合でもその１２８の最下位ビットがそれぞれシェアｓＡ、ｓＢおよびｓＣとして使用される。中央局Ｚでは（ｎ、２、−１）閾値方法を適用して、ポイント（１、ｓＡ）、（２、ｓＢ）および（３、ｓＣ）を通過し、これらのポイントによって一意的に定義される二次多項式Ｐ（ｘ）が有限体ＧＦ（２１２３）に関して計算される。共通キーｋはこの多項式とｙ軸の交差のポイント、すなわち、ｋｊ＝Ｐ（０）である。中央局Ｚはｇｚ ｍｏｄ  ｐおよびｓ１ｊ＝Ｐ（４）およびｓ２ｊ＝Ｐ（５）を加入者Ａ、ＢおよびＣに送信する。
３  加入者Ａに関しては、（ｇｚ）ａ ｍｏｄ  ｐが計算される。この結果、この値の１２８の最下位ビットを有する加入者ＡはシェアｓＡを受信し、これはｓ１およびｓ２と共に十分に多項式Ｐ'（ｘ）を決定し、したがってまたキーｋも決定する。加入者ＢおよびＣに関しても同様のステップが行われる。
【００１７】
上記の方法は加入者Ｔ１乃至Ｔｎと中央局Ｚの間で最小の２ラウンドを行う。BurmesterおよびDesmedtの手法とは異なり、中央局によってｎ人の加入者に送信されるべき文字列に関する経費は第２のラウンドで加入者あたり１２８ビットの長さにまで削減できる。