(57)【要約】【課題】  本発明の目的は、インターネットを始めとするセキュアでない環境において、共通キーをセキュアに生成する技術を提供する。【課題を解決する手段】  第１のエンティティは、固有キーａより交換情報ａ＊ＸＢ＊ａ−１を演算し、それをグラフ表現にエンコードし、２のエンティティに送信する。第２のエンティティのデコーダは、第１のエンティティより送信されたグラフ表現された交換情報ａ＊ＸＢ＊ａ−１をもとの交換情報にデコードし、デコードされた交換情報ａ＊ＸＢ＊ａ−１から固有キーｂを使用して共通キーｂ＊（ａ＊ｂ＊ａ−１）−１を生成する。【選択図】  図１
2005086778.tif 000002
【特許請求の範囲】
【請求項１】
群Ｇ、群Ｇの部分集合ＸＡ、ＸＢ及び固有キーａを保存するための保存装置と、通信相手から送信されたグラフ表現された交換情報ｂ＊ＸＡ＊ｂ−１をもとの交換情報ｂ＊ＸＡ＊ｂ−１にデコードするデコーダと、該デコードした交換情報より共通キー（ｂ＊ａ＊ｂ−１）＊ａ−１を演算する演算部と、を有する共通キー生成装置。
【請求項２】
請求項１記載の共通キー生成装置において、更に交換情報をグラフ表現にエンコードするエンコーダを設け、上記演算部は、上記部分集合ＸＢと上記固有キーａより交換情報ａ＊ＸＢ＊ａ−１を演算し、上記エンコーダは、該交換情報ａ＊ＸＢ＊ａ−１をグラフ表現にエンコードし、通信相手に、上記グラフ表現した交換情報ａ＊ＸＢ＊ａ−１を送信することを特徴とする共通キー生成装置。
【請求項３】
請求項２記載の共通キー生成装置において、上記群Ｇはブレード群であり、上記エンコーダは、上記交換情報ａ＊ＸＢ＊ａ−１をブレード群の忠実な作用によるグラフ表現にすることを特徴とする共通キー生成装置。
【請求項４】
群Ｇ、群Ｇの部分集合ＸＡ、ＸＢ及び固有キーａを保存するための保存装置と、上記固有キーａより交換情報ａ＊ＸＢ＊ａ−１を演算する演算部と、該交換情報ａ＊ＸＢ＊ａ−１をグラフ表現にエンコードするエンコーダと、グラフ表現にエンコードされた交換情報をもとの交換情報にデコードするデコーダとを有する第１のエンティティと、群Ｇ、群Ｇの部分集合ＸＡ、ＸＢ及び固有キーｂを保存するための保存装置と、上記固有キーｂより交換情報ｂ＊ＸＡ＊ｂ−１を演算する演算部と、該交換情報ｂ＊ＸＡ＊ｂ−１をブレード群の忠実な作用によるグラフ表現にエンコードするエンコーダと、グラフ表現にエンコードされた交換情報をもとの交換情報にデコードするデコーダとを有する第２のエンティティと、を有し、
上記第１のエンティティの演算部は、上記固有キーａより交換情報ａ＊ＸＢ＊ａ−１を演算し、上記第１のエンティティのエンコーダは、該交換情報をグラフ表現にエンコードし、上記第１のエンティティは該エンコードした交換情報を上記第２のエンティティに送信し、上記第２のエンティティのデコーダは、上記第１のエンティティより送信されたグラフ表現された交換情報ａ＊ＸＢ＊ａ−１をもとの交換情報にデコードし、上記第２のエンティティの演算部は、デコードされた交換情報ａ＊ＸＢ＊ａ−１から上記固有キーｂを使用して共通キーｂ＊（ａ＊ｂ＊ａ−１）−１を生成するように構成されている共通キーの生成システム。
【請求項５】
請求項４記載の共通キー生成システムにおいて、
上記第２のエンティティの演算部は、上記固有キーｂより交換情報ｂ＊ＸＡ＊ｂ−１を演算し、上記第２のエンティティのエンコーダは、該交換情報をグラフ表現にエンコードし、上記第２のエンティティは該エンコードした交換情報を上記第１のエンティティに送信し、上記第１のエンティティのデコーダは、上記第２のエンティティより送信されたグラフ表現された交換情報ｂ＊ＸＡ＊ｂ−１をもとの交換情報にデコードし、上記第１のエンティティの演算部は、デコードされた交換情報ｂ＊ＸＡ＊ｂ−１から上記固有キーａを使用して共通キー（ｂ＊ａ＊ｂ−１）＊ａ−１を生成するように構成されている共通キーの生成システム。
【請求項６】
請求項４記載の共通キーの生成システムにおいて、上記群Ｇはブレード群であり、上記第１のエンティティのエンコーダは、上記交換情報ａ＊ＸＢ＊ａ−１をブレード群の忠実な作用によるグラフ表現にすることを特徴とする共通キーの生成システム。
【請求項７】
群Ｇと該群Ｇの部分集合ＸＡ、ＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が付与されているとき、上記部分集合ＸＡから固有キーａを生成する固有キーａ生成ステップと、
通信相手から送信されたグラフ表現された交換情報ｂ＊ＸＡ＊ｂ−１をもとの交換情報にデコードするデコードステップと、
上記デコードされた交換情報ｂ＊ＸＡ＊ｂ−１から上記固有キーａを使用してｂ＊ａ＊ｂ−１を演算する演算ステップと、
上記演算結果ｂ＊ａ＊ｂ−１より共通キー（ｂ＊ａ＊ｂ−１）＊ａ−１を演算する共通キー演算ステップと、
を含む共通キーの生成方法。
【請求項８】
請求項７記載の共通キーの生成方法において、
上記固有キーａと部分集合ＸＢから交換情報ａ＊ＸＢ＊ａ−１を演算する交換情報演算ステップと、
上記交換情報ａ＊ＸＢ＊ａ−１をグラフ表現にエンコードするエンコードステップと、
上記エンコードした交換情報ａ＊ＸＢ＊ａ−１を通信相手に送信する送信ステップと、
を含む共通キーの生成方法。
【請求項９】
請求項７記載の共通キーの生成方法において、上記群Ｇはブレード群であり、上記デコードステップは、ブレード群の忠実な作用によりグラフ表現された上記交換情報ａ＊ＸＢ＊ａ−１をもとの交換情報にデコードすることを特徴とする共通キーの生成方法。
【請求項１０】
請求項８記載の共通キーの生成方法において、上記群Ｇはブレード群であり、上記エンコードステップは、上記交換情報ａ＊ＸＢ＊ａ−１をブレード群の忠実な作用によるグラフ表現にすることを特徴とする共通キーの生成方法。
【請求項１１】
請求項７、８、９又は１０記載の共通キーの生成方法をコンピュータに実行させるためのコンピュータによって読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予備通信を用いることなく共通キーを生成する共通キーの生成技術に関し、特に、セキュアでない環境において、共通キーをセキュアに生成する装置及び方法に関する。
【背景技術】
【０００２】
近年、非可換群を用いた、共通キー生成方式が用いられている。それによると、まずエンティティＡ、Ｂに与えられる群Ｇと群Ｇの部分集合ＸＡ、ＸＢの組（Ｇ、ＸＡ、ＸＢ）より、エンティティＡの中で部分集合ＸＡから外部とは全く独立な手段により適当な固有キーａを生成し、エンティティＢの中で部分集合ＸＢから外部とは全く独立な手段により適当な固有キーｂを生成する。次に、エンティティＡからエンティティＢに交換情報ａ＊ＸＢ＊ａ−１を送信し、エンティティＢからエンティティＡに交換情報ｂ＊ＸＡ＊ｂ−１を送信する。
【０００３】
エンティティＡは、受信した交換情報ｂ＊ＸＡ＊ｂ−１からｂ＊ａ＊ｂ−１を計算することができる。これは、部分集合ＸＡより固有キーａを生成したので、同様に、交換情報ｂ＊ＸＡ＊ｂ−１からｂ＊ａ＊ｂ−１を計算することができるからである。エンティティＡは、固有キーａを用いて、ｂ＊ａ＊ｂ−１から（ｂ＊ａ＊ｂ−１）＊ａ−１を計算することによって、共通キーｂ＊ａ＊ｂ−１＊ａ−１を得る。
【０００４】
同様に、エンティティＢは、受信した交換情報ａ＊ＸＢ＊ａ−１からａ＊ｂ＊ａ−１を計算し、ａ＊ｂ＊ａ−１からｂ＊（ａ＊ｂ＊ａ−１）−１を計算することによって、共通キーｂ＊ａ＊ｂ−１＊ａ−１を得る。
【０００５】
尚、このような共通キーの生成方法の詳細については、本願出願人と同一の出願人による特願２００２−１８８９１７号を参照されたい。尚、本発明に関連する技術が本願出願人と同一の出願人による特願２００２−２７１４１４号に記載されている。
【０００６】
特表２００２−５０５５５０号には、暗号法上安全な代数キー設定プロトコル、代数キー一致プロトコル、代数キー輸送プロトコル等を生成する方法及び装置が記載されている。
【０００７】
【特許文献１】特表２００２−５０５５５０号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述の共通キー生成方式にて、エンティティＡ、Ｂ間の通信で、交換情報ａ＊ＸＢ＊ａ−１あるいは、ｂ＊ＸＡ＊ｂ−１を受け渡す。この過程にて、第３者に、エンティティの固有キーであるａまたはｂを知られないようにする必要がある。一般的には、群の積はシンボリックに計算されるが、そのままだと、第３者が、固有キーを類推する可能性がある。
【０００９】
本発明の目的は、第３者が、固有キーを類推することができない共通キーの生成方法及び装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明によると、エンティティＡ、Ｂ間の通信で、交換情報ａ＊ＸＢ＊ａ−１あるいは、ｂ＊ＸＡ＊ｂ−１を受け渡すとき、交換情報ａ＊ＸＢ＊ａ−１あるいは、ｂ＊ＸＡ＊ｂ−１をグラフにエンコードしてから、受け渡す。特に、群Gがブレード群の場合、ブレード群に対応したグラフにエンコードしてから受け渡す。
【発明の効果】
【００１１】
本発明によると、第三者が固有キーを知ること又は類推することが極めて困難である。
【発明を実施するための最良の形態】
【００１２】
図１を参照して本発明の共通キーの生成システムの例を説明する。本例の共通キーの生成システムは、第１及び第２のエンティティ１０、２０を有し、両者は通信回線３０によって接続されている。通信回線３０は、必ずしもセキュアである必要はなく、インターネット等のような公衆通信網であってよい。
【００１３】
第１のエンティティ１０は、群Ｇ保存装置１１と第１の部分集合ＸＡ保存装置１２と第２の部分集合ＸＢ保存装置１３と固有キーａ保存装置１４と演算装置１５とエンコーダ１６とデコーダ１７と送受信装置１８とを有する。第２のエンティティ２０は、群Ｇ保存装置２１と第１の部分集合ＸＢ保存装置２２と第２の部分集合ＸＡ保存装置２３と固有キーｂ保存装置２４と演算装置２５とエンコーダ２６とデコーダ２７と送受信装置２８とを有する。
【００１４】
尚、第１及び第２のエンティティ１０、２０は、それぞれコンピュータ装置であってよく、それぞれ、ディスプレイ部、入力装置等を有するが、図示は省略する。保存装置１１、２１、１２、２２、１３、２３及び１４、２４は、コンピュータ装置に設けられた外部又は内部記憶装置であってよい。演算装置１５とエンコーダ１６とデコーダ１７は１つの演算装置によって構成されてよい。演算装置２５とエンコーダ２６とデコーダ２７は１つの演算装置によって構成されてよい。
【００１５】
群Ｇ保存装置１１、２１は、群Ｇの定義情報を保存する。群Ｇが一般の群の場合には、定義情報は、生成元の個数と生成元間の制約を含む。群Ｇがブレード（Braid）群の場合には、位数、即ち、整数を指定するだけで群Ｇが完全に特定されるから、定義情報は、位数のみを含む。以下に、群Ｇがブレード群であるとして説明する。
【００１６】
第１のエンティティ１０の第１の部分集合ＸＡ保存装置１２は群Ｇの部分集合ＸＡを保存し、第２の部分集合ＸＢ保存装置１３は群Ｇの部分集合ＸＢを保存する。第２のエンティティ２０の第１の部分集合ＸＢ保存装置２２は群Ｇの部分集合ＸＢを保存し、第２の部分集合ＸＡ保存装置２３は群Ｇの部分集合ＸＡを保存する。部分集合ＸＡ、ＸＢの元には順番が付されており、この順番は、２つのエンティティ１０、２０において同一である。一般に、部分集合の元は、生成元からなる語で記述される。
【００１７】
固有キーａ保存装置１４及び固有キーｂ保存装置２４は、部分集合ＸＡ、ＸＢから生成された群Ｇの元ａ、ｂを固有キーとして保存する。固有キーａ保存装置１４及び固有キーｂ保存装置２４には、部分集合ＸＡ、ＸＢから固有キーａ、ｂを生成する方法の情報、即ち、どのような順番によってＸＡ、ＸＢの元が掛け合わされたかという情報も格納されている。
【００１８】
第１のエンティティ１０の演算装置１５は、固有キーａと部分集合ＸＢを用いて交換情報ａ＊ＸＢ＊ａ−１を演算する。エンコーダ１６は、交換情報ａ＊ＸＢ＊ａ−１をブレード群のグラフ表現にエンコードする。送受信装置１８は、グラフ表現化した交換情報ａ＊ＸＢ＊ａ−１を第２のエンティティ２０に送信する。
【００１９】
第２のエンティティ２０の送受信装置２８は、第１のエンティティ１０から送信された、グラフ表現化した交換情報ａ＊ＸＢ＊ａ−１を受信する。デコーダ２７は、グラフ表現化した交換情報をもとの交換情報にデコードする。演算装置２５は、デコードした交換情報ａ＊ＸＢ＊ａ−１からａ＊ｂ＊ａ−１を演算する。更に、固有キーｂを用いて、ａ＊ｂ＊ａ−１からｂ＊（ａ＊ｂ＊ａ−１）−１を計算することによって、共通キーｂ＊ａ＊ｂ−１＊ａ−１を得る。
【００２０】
同様に、第２のエンティティ２０は、グラフ表現にエンコードした交換情報ｂ＊ＸＡ＊ｂ−１を第１のエンティティ１０に送信する。第１のエンティティ１０は、グラフ表現化した交換情報ｂ＊ＸＡ＊ｂ−１をもとの交換情報にデコードし、デコードした交換情報ｂ＊ＸＡ＊ｂ−１からｂ＊ａ＊ｂ−１を演算する。更に、第２のエンティティ２０は、固有キーａを用いて、ｂ＊ａ＊ｂ−１から（ｂ＊ａ＊ｂ−１）＊ａ−１を計算することによって、共通キーｂ＊ａ＊ｂ−１＊ａ−１を得る。
【００２１】
固有キーａ、ｂは、各エンティティ１０、２０によって生成されるが、共通キーの計算に際して、他のエンティティ又は外部に送信されることはない。従って、第三者が固有キーを知ることは困難である。
【００２２】
本例によると、先ず、サーバ等（図示なし）により、群Ｇ及び群Ｇの２つの部分集合ＸＡ及びＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が生成され、第１及び第２のエンティティ１０、２０に付与される。第三者が、３つの群の組（Ｇ，ＸＡ，ＸＢ）を傍受しても、それから共通キーを求めることは困難である。従って、群の組（Ｇ，ＸＡ，ＸＢ）は、インターネット等のセキュアでない公衆網を経由して、２つのエンティティ１０、２０に送信される。
【００２３】
図２を参照して、本発明による共通キーの生成方法の予備的処理を説明する。本例の処理にて、第１のエンティティ１０は、交換情報ａ＊ＸＢ＊ａ−１の演算を行い、それを第２のエンティティ２０に送信する。尚、第２のエンティティ２０も、交換情報ｂ＊ＸＡ＊ｂ−１の演算を行い、それを第１のエンティティ１に送信するが、この処理は、第１のエンティティ１０における処理と同様であり、その説明は省略する。
【００２４】
先ずステップ２０１にて、固有キーａ保存装置１４に格納されている固有キーａを取り出す。固有キーａは、部分集合ＸＡより生成され、固有キーａ保存装置１４に既に格納されているものとする。ステップ２０２にて、第２のエンティティ２０へ送信する交換情報ａ＊ＸＢ＊ａ−１を格納するためのリストＬを初期化する。ステップ２０３にて、第２の部分集合ＸＢ保存装置１３より、元に付された順番に従って、未処理の最初の元を取り出し、それをｘとする。例えば、部分集合がＸＢ＝{ｂ１、ｂ２、ｂ３}である場合、その元はｘ＝ｂ１、ｂ２又はｂ３である。
【００２５】
ステップ２０４にて、演算装置１５は、交換情報ａ＊ｘ＊ａ−１の演算を行い、エンコーダ１６は、交換情報ａ＊ｘ＊ａ−１をエンコードし、その結果をＥNＣｘに入れる。ステップ２０５にて、ＥNＣｘをリストＬの最後に追加する。例えば、部分集合がＸＢ＝{ｂ１、ｂ２、ｂ３}である場合、その元はｘ＝ｂ１、ｂ２又はｂ３であり、ａ＊ｘ＊ａ−１＝ａ＊ｂ１＊ａ−１、ａ＊ｂ２＊ａ−１又はａ＊ｂ３＊ａ−１である。リストＬが初期化された直後では、リストの先頭になる。尚、交換情報ａ＊ｘ＊ａ−１は第三者が、固有キーａを容易に類推することができないように、適当な表現方法により表現される。
【００２６】
ステップ２０６にて、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘが処理されたか否かを判定する。全ての元が処理されていなければステップ２０３に戻り、全ての元が処理されているならステップ２０７に進む。
【００２７】
ステップ２０７にて、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘに対する交換情報ａ＊ｘ＊ａ−１から構成されるリストＬを第２のエンティティ２０に送信する。リストＬには、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘに対するエンコードされた交換情報ａ＊ｘ＊ａ−１が第２の部分集合ＸＢ保存装置１３における元の順番と同一の順番にて、格納されている。例えば、部分集合がＸＢ＝{ｂ１、ｂ２、ｂ３}である場合、リストＬには、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘ＝ｂ１、ｂ２又はｂ３に対するエンコードされた交換情報ａ＊ｘ＊ａ−１＝ａ＊ｂ１＊ａ−１、ａ＊ｂ２＊ａ−１、又はａ＊ｂ３＊ａ−１が第２の部分集合ＸＢ保存装置１３における元の順番（ｂ１、ｂ２、ｂ３）と同一の順番にて、格納されている。
【００２８】
図３を参照して、本発明による共通キーの生成方法の本処理を説明する。本例の処理にて、第１のエンティティ１０において、共通キーとして（ｂ＊ａ＊ｂ−１）＊ａ−１を計算する。この計算は、図２に示した予備的処理と並行して実行されてよい。
【００２９】
先ずステップ３０１にて群の元である変数Ｙを初期化する。即ち、変数Ｙに中立元Ｅを代入する。ステップ３０２にて、第２のエンティティ２０より送信される交換情報ｂ＊ＸＡ＊ｂ−１を格納するためのリストＬを初期化する。
【００３０】
ステップ３０３にて、第２のエンティティ２０より送信されたエンコード化された交換情報をもとの交換情報ｂ＊ＸＡ＊ｂ−１にデコードし、それを、部分集合ＸＡの元ｘの順番にしたがって、リストＬに格納する。
【００３１】
例えば、部分集合をＸＡ＝｛ａ１，ａ２，ａ３｝とすると、その元ｘの順番はａ１、ａ２、ａ３である。交換情報はｂ＊ＸＡ＊ｂ−１＝｛ｂ＊ａ１＊ｂ−１，ｂ＊ａ２＊ｂ−１，ｂ＊ａ３＊ｂ−１｝である。交換情報ｂ＊ＸＡ＊ｂ−１は、その元ｙ＝ｂ＊ｘ＊ｂ−１の順番が、ｂ＊ａ１＊ｂ−１、ｂ＊ａ２＊ｂ−１、ｂ＊ａ３＊ｂ−１となるように格納される。
【００３２】
ここで第１のエンティティ１０は、第２のエンティティ２０の固有キーｂそのものを入手する必要はなく、交換情報ｂ＊ＸＡ＊ｂ−１のみを入手すればよいことに留意されたい。
【００３３】
ステップ３０４にて、固有キーａ保存装置１４に格納されている固有キーａを取り出す。固有キーａは、部分集合ＸＡの元ｘに符号を付して順番に積を演算することにより生成されるが、詳細は上述の特願２００２−１８８９１７号を参照されたい。固有キーａにはその生成過程を示す情報が含まれる。ステップ３０５にて、固有キーａより部分集合ＸＡの元ｘとその指数ｎ（０以外の整数）を取り出す。ステップ３０６にて、リストＬより部分集合ＸＡの元ｘに対応する交換情報ｂ＊ＸＡ＊ｂ−１の元ｙ＝ｂ＊ｘ＊ｂ−１を取り出す。ステップ３０７にて、元ｙのｎ乗、即ちｙｎを演算する。ステップ３０８にて、変数Ｙとｙｎの積を演算する。ｙｎを変数Ｙに右から掛けるか左から掛けるかは、固有キーａの構成法に順ずる。ステップ３０９にて、固有キーａの全ての元に対して処理がされたかを判定する。全ての元に対して処理がなされていない場合には、ステップ３０５に戻り、未処理の元に対して、上述の処理がなされる。
【００３４】
固有キーａの全ての元に対して処理がなされている場合には、ステップ３１０に進む。ステップ３１０にて、Ｙ＊ａ−１を演算する。ステップ３１０に到達したときには、Ｙ＝ｂ＊ａ＊ｂ−１となっている。従って、Ｙ＊ａ−１＝（ｂ＊ａ＊ｂ−１）ａ−１である。これが共通キーとなる。
【００３５】
図４を参照して、図３のステップ３０３のデコード処理を説明する。ステップ４０１にて、デコードした交換情報を格納するためのリストLを初期化する。ステップ４０２にて、第２のエンティティ２０より送信されたリストの未処理の元のうち、最初の元を取り上げて変数Ｙとする。ステップ４０３にて、ステップ４０２で取り上げた変数ＹをデコードしてＤＥＣｙとする。ステップ４０４にて、ＤＥＣｙをリストLの最後に追加する。これによって順番が保障されるものである。ステップ４０５にて、終了判定を行う。即ち、第２のエンティティ２０から送信された交換情報が全て処理されたかを判定する。
【００３６】
ところで、本例では、エンコーダ１６、２６は、交換情報ａ＊ＸＢ＊ａ−１、ｂ＊ＸＡ＊ｂ−１をブレード群に対応したグラフ表現にエンコードする。実際のエンコード処理にて、冗長性を排して表現を行うことが、容易に固有元を類推させないようにするのに重要である。ここで、ブレード群に対応したグラフ表現について述べる。ここで述べるブレード群のグラフ表現とは、パスの集まりである。
【００３７】
図５及び図６を参照して、先ず、パス（曲線又は折線）の記法を説明する。平面上に、始点X0と、その上側に略水平に並んでいるN+1個の点X1,…，XN+1を取る。このような点の取り方は、以下に説明する記法を単純化するためであり、本質的でない。始点X0を出発し、点X1,….XN+1を終端とするN+1個のパスp1,…，pN+1を作る。各パスpiは、自身及び他の点Xj(j≠i)と交わらないものとする。パスは直線、折線又は曲線であってよく、図面にて便宜上、直線又は折線にて表現されている。
【００３８】
すると、自然にＮ個のカノ二カルな生成元が与えられる。次に、パスに対するカノニカルな生成元σiの作用を説明する。カノニカルな生成元σiの作用は、平面上の２点Xi, Xi+1の近辺に限られる。２点の近辺にて、パスの反時計周りの回転と２点の入れ替えが起きる。
【００３９】
図５に示す例にて、第１のパスｐ1にカノニカルな生成元σ１を作用させると、２点Ｘ1、Ｘ2の近辺にて、第１のパスｐ1の回転と２点Ｘ1、Ｘ2の入れ替えが起きる。同様に、第２のパスｐ2にカノニカルな生成元σ２を作用させると、２点Ｘ2、Ｘ3の近辺にて、回転と入れ替えが起きる。第３のパスｐ3にカノニカルな生成元σ３を作用させると、２点Ｘ3、Ｘ4の近辺にて、回転と入れ替えが起きる。
【００４０】
結局、N+1個のパスp1,…，pN+1に対して、順次、カノニカルな生成元σiを作用させると、Ｎ組の隣接する２点の近辺にて回転と入れ替えが起きる。
【００４１】
図５は、３個のカノニカルな生成元σ1、σ2、σ3が与えられた例を示す。平面上に４個の点Ｘ1、Ｘ2、Ｘ3、Ｘ4をとり、４個のパスｐ1、ｐ2、p3、ｐ4を生成する。パスｐ2に、カノニカルな生成元σiを作用させると、パスの回転と隣接した２点の入れ替えが起きる。これを繰返すと、図６に示すように、複雑なパスｐ2が生成される。このような、カノニカルな生成元σiの作用の詳細は後に説明する。
【００４２】
次にパスの記法を説明する。始点X0を出発し、ｉ番目の点Xi(1≦i≦N+1)を終点とするパスpiを考える。このパスpiは、次のようなリストＬによって完全に記述することができる。
[数１]
（X0,0）（Xj１,＋）（Xj２, ±）…，…(Xjｎ, ±)…(Xi,0)
リストＬは要素からなり、各要素は、（Ｘｊ，sign）の形式となっている。ここで、Ｘｊを点、signを符号と呼ぶ。点Ｘｊは、パスpiが点Ｘｊの近辺を通過することを意味する。符号は、点Ｘｊに対するパスpiの位置を示す。符号＋である場合には、パスpiは、点Ｘｊの上側を通り、符号が−である場合には、パスpiは、点Ｘｊの下側を通ることを意味する。符号が０である場合には、パスpiは、点Ｘｊを始端又は終端とすることを意味する。
【００４３】
従って、最初の要素（X0,0）はパスpiの始点を表し、最後の要素(Xi,0)はパスpiの終点を表す。要素(Xj, ＋)は、パスpiが点Xjの上側を通過し、要素(Xj, −)は、パスpiが点Xjの下側を通過することを意味している。
【００４４】
図６のパスp2は、上述の記法によると次のリストによって表される。
[数２]  
（X0,0）（X2,＋）（X3, −）（X4,＋）（X4,−）（X3, −）(X2, 0)
ここで、記法の冗長性を避ける手法が使用されている。それによると、始点X0を出発したパスp2が、始点の次の点X1の下側を通る場合には、要素(X1, −)の記載を省略する。従って、始点の次の要素（X2,＋）はパスp2が最初に上側を通る点を表す。
【００４５】
ここでブレード群の任意の元Σは、次のようなリストの形で表される。
[数３]    
（σj１、sign１）（σj２、sign２）…（σjｍ、signm）
σｊｋはカノ二カルな生成元であって、signｋは符号を表す、signkがプラスの時は、（σjｋ、＋）はカノ二カルな生成元σjｋそのものを表し、signkがマイナスととき（σjｋ、−）はカノ二カルな生成元σjｋの逆元を表す。
【００４６】
図７を参照して、図２のステップ２０４のエンコード処理を説明する。尚、随時、図５及び図６を参照する。数３の式によって表されるN個のカノニカルな生成元Σが与えられているものとし、図５に示すように、平面上に、始点X0を出発し、点X1,….XN+1を終端とするN+1個のパスp1,…，pN+1を作る。これらのパスｐ1、…ｐn全体をパスの集合Ｐとする。
【００４７】
ステップ701にて、パスの集合Ｐを初期化する。即ち、N+1個のパスp1,…，pN+1を、図５で表されるような最も簡単な直線状のパスとする。上述に記法によると初期化したパスは(X0,0)(Xj,0)となる。尚、図５のパスの集合Ｐを具体的に表現すると、(X0,0)(X1,0)、(X0,0)(X2,0)、(X0,0)(X3,0)、(X0,0)(X4,0)となる。
【００４８】
次に、ステップ702にて、N個のカノニカルな生成元Σより、１個のカノ二カルな生成元σｊとその符号±をランダムに選ぶ。これをここでは（σｊ，±）と表現する。（σｊ，±）は、（σｊ，＋）又は（σｊ，−）の意味である。
【００４９】
ステップ703にて、平面上のN+1個のパスp1,…，pN+1に対して、順次、カノ二カルな生成元（σｊ，±）を作用させる。各パスpｉにカノ二カルな生成元（σｊ，±）を作用させる方法は、以下に、図８を参照して詳細に説明する。こうして、作用の結果としてN+1個のパスｐ1,…，ｐN+1が得られる。このN+1個のパスｐ1,…，ｐN+1は、数２の式のようなリストとして得られる。
【００５０】
ステップ704にて、ステップ703で得られたN+1個のパスｐ1,…，ｐN+1より、順次、冗長性を除去する。冗長性を除去する方法の例は本願の出願人と同一の出願人による特願２００２−２７１４１４号に記載されており、詳細は同出願を参照されたい。ステップ704にて、冗長性が除去されたN+1個のパスｐ1,…，ｐN+1のリストが得られる。
ステップ705にて、カノ二カルな生成元の集合Σの処理がすべて終了したかを判定する。
【００５１】
図８を参照して、図７のステップ７０３のカノ二カルな生成元をパスに作用させる処理を説明する。始点X0から始まるパスｐｉが要素からなるリストＬｉとして与えられているものとする。このパスｐｉに対してカノニカルな生成元σｉを作用させたとき結果リストＬを得るための処理を説明する。パスｐｉを表すリストＬｉの各要素は、上述のように、（Ｘｊ,sign）と表され、Ｘｊを点、signを符号と呼ぶことにする。
【００５２】
まずステップ801にて、パスｐｉに対してカノニカルな生成元σｊを作用させた結果を格納するための結果リストＬを初期化する。即ち、結果リストＬの最初の要素として、始点X0を表す要素(X0,0)を入れる。ここで、パスｐｉを表すリストＬｉにおける処理中の要素の位置を表すインデックスＩを０番目から数えることとする。ステップ802にて、リストＬｉにおける処理中の要素の位置を表すインデックスＩを初期化する。即ち、インデックスＩを０から１にする。
【００５３】
ステップ803にて、リストＬｉにおけるＩ番目の要素を取り出し、それをCurrentとする。ステップ804にて、Currentの点がXｊであるか否かを判定する。Currentの点がXiであれば、ステップ805に進む。ステップ805の処理の詳細は後に図１４及び図１５を参照して説明する。Currentの点がXｊでなければ、ステップ806に進む。ステップ806にて、Currentの点がXｊ+1であるか否かを判定する。Currentの点がXｊ+1であればステップ807に進む。ステップ807の処理は、ステップ805の処理と同様である。ステップ806にて、Currentの点がXｊ+1でなければ、ステップ808に進み、インデックスＩを１インクメントし、リストＬｉにおける次の要素に進む。ステップ809にて、結果リストＬの最後に、Currentを追加する。
【００５４】
ステップ805、807、809の実行後は、ステップ810にて、リストＬｉの全ての要素について、処理が完了したか否かを判定する。即ち、処理中の要素の位置を示すインデックスＩが、リストＬｉの全要素数より真に大であるか否かを判定する。ステップ810にて、処理が完了していないと判定された場合には、ステップ803に戻り、処理が完了していると判定された場合には、本例のフローを終了する。
【００５５】
図９を参照して、図４のステップ４０３のデコード処理を説明する。ステップ９０１にて、本例のデコード処理によって生成する逆元のリストΣを初期化する。ステップ９０２にて、処理中のパスを表すインデックスIを初期化する。即ち、インデックスＩを１とする。
【００５６】
ステップ９０３にて、パスのリストＬIの処理結果をリストΣ’に入れる。パスPIは要素からなるリストＬIとして与えられているものとする。処理結果Σ’の求め方については、図１０で詳細に述べる。
【００５７】
ステップ９０４にて、処理結果Σ’を処理結果のリストΣに追加する。これは、単純なリストの結合であるので詳しく述べない。ステップ９０５にて、インデックスIを１増やし、次に処理するパスを示す。ステップ９０６にて、全てのパスが処理されたか否かを判定する。処理中のパスを表すインデックスIがパスの個数Nよりも大きくないときは、未処理のパスが存在し、ステップ９０８に進む。
【００５８】
ステップ９０８にて、処理結果であるカノ二カルな生成元Σ’をパスＰｊ（ｊ＞Ｉ）に作用させる。作用させた結果のパスをＰｊ（ｊ＞Ｉ）とする。この処理の詳細は、図８で述べた。
【００５９】
もし、インデックスIがパスの個数Nより大きいときは、全てのパスが処理済みであり、ステップ９０７に進む。ステップ９０７にて、処理結果のリストであるカノ二カルな生成元Σの逆元を求める。カノ二カルな生成元Σの逆元は、「（１）リストΣの順番を逆にする。（２）リストΣの符号を変える。」ことによって得られる。例えば、カノ二カルな生成元Σが数４の式によって表される場合、その逆元は、数５の式によって表される。
[数４]
（σj１、sign１）（σj２、sign２）…（σjｍ、signm）
[数５]
（σjｍ、ＣH（signm））…（σj２、ＣH（sign２））（σj１、ＣH（sign１））
ここでＣHは符号の変更、すなわち＋なら−、−なら＋にすることを意味している。
【００６０】
図１０を参照してステップ９０３の処理、即ち、パスのリストPIからカノ二カルな生成元Σ´を生成する処理を説明する。始点Ｘ０から始まるパスPIが要素からなるリストＬIとして与えられているものとする。ステップ１００１にて、本例の処理によって生成するカノ二カルな生成元のリストΣ´を初期化する。
【００６１】
ステップ１００２にて、処理対象であるパスのリストLIの最後の要素（Ｘn、０）を求める。ステップ１００３にて、パスのリストLIの最後から２番目の要素が、（Ｘ０、−１）であるか否かを判定する。（Ｘ０、−１）の時は、ステップ１００４に進み、位置Ｘ０の処理を行う。最後から２番目の要素が、（Ｘ０、−１）でない時は、ステップ１００５に進む。
【００６２】
ステップ１００５にて、パスのリストLIの最後から２番目の要素の位置がＸn−１か否かを判定する。これは、最後の点（Ｘn、０）に左側から到達したか否かを判定することを意味し、ＹＥＳならば、ステップ１００６にて最後から２番目の要素の位置Ｘn−１の処理を行う。Noならばステップ１００７にて位置Ｘn+１の処理を行う。ステップ１００４、ステップ１００６及びステップ１００７の処理の詳細は図１１〜図１３を参照して説明する。
【００６３】
図１１を参照してステップ１００４の処理の詳細を説明する。ステップ１１０１にてエラーを判定する。つまり、パスLIの作業中には、ＸIよりも左側にある点は絶対に出現しない。もし存在するときには、ステップ１１０２のエラー処理に飛ぶ。一方NOであれば、ステップ１１０３に飛ぶ。
【００６４】
ステップ１１０３は、さらに処理が必要か否かを判定する。NOならばなにもせず戻る。ＹＥSならば、ステップ１１０４に進み、対応する元をΣ’にかける。具体的には、数６の式によって表されるリストをΣ’の左に追加する。
[数６]  
（σI、−）（σI+１、−）…（σn−１、−１）
【００６５】
図１２を参照してステップ１００６の処理の詳細を説明する。ステップ１２０１にて、先ず入力であるパスのリストLIから最後の２つの要素をとり省いて、LI’とする。ここで最後の２つの要素とは、（Ｘn−１、±）（Ｘn、０）のことである。
【００６６】
ステップ１２０２にて、エラーを判定している。つまり、パスLIの作業中には、ＸIよりも左側にある点は絶対に出現しない。もし存在するときには、ステップ１２０３のエラー処理に飛ぶ。
【００６７】
ステップ１２０４はＸn−１の符号が正であるか負であるかを判定する。（Ｘn−１、＋）の時は、ステップ１２０５に進み、（Ｘn−１、−）の時は、ステップ１２０６に進む。
【００６８】
ステップ１２０５にて、Σ’に左からσn−１をかけΣ１とする。すなわち、Σ’の左側に、（σn−１、＋）を追加する。ステップ１２０６にて、Σ’に左から（σn−１）−１をかけΣ１とする。すなわち、Σ´の左側に、（σn−１、−）を追加する。
【００６９】
ステップ１２０７にて、ステップ１２０１で作成されたLI’に対して、（Ｘn−１、０）を追加し、LIとする。ステップ１２０８にて、図１０の処理を呼び出す。即ち、ステップ１２０７で作成されたLIに対するΣ’を返す。ステップ１２０９は、ステップ１２０８で得られたΣ’をステップ１２０５又はステップ１２０６で得られたΣ１に左から乗算する。
【００７０】
図１３を参照してステップ１００７の処理の詳細を説明する。ステップ１３０１にて、先ず入力であるパスのリストLIから最後の２つの要素をとり省いて、LI´とする。ここで最後の２つの要素とは、（Ｘn+１、±）（Ｘn、０）のことである。
【００７１】
ステップ１３０２にて、エラーを判定する。即ち、パスLIの作業中には、ＸIよりも左側にある点は絶対に出現しない。もし存在するときには、ステップ１３０３のエラー処理に進む。
【００７２】
ステップ１３０４はＸn+１のサインを判定している。即ち、（Ｘn+１、＋）の時は、ステップ１３０５に進み、（Ｘn+１、−）の時は、ステップ１３０６に進む。ステップ１３０５は、Σ’に左から（σn）−１をかけΣ１とする。すなわち、Σ´の左側に、（σn、−）を追加する。ステップ１３０６は、Σ´に左からσnをかけΣ１とする。すなわち、Σ’の左側に、（σn、＋）を追加する。
【００７３】
ステップ１３０７は、ステップ１３０１で作成されたLI’に対して、（Ｘn+１、０）を追加しLIとしている。ステップ１３０８は、図１０の処理を呼び出すもので、ステップ１３０７で作成されたLIに対するΣ’を返す。
【００７４】
ステップ１３０９は、ステップ１３０８で得られたΣ’をステップ１３０５あるいは１３０６で得られたΣ１に左から乗算する。
【００７５】
図１４及び図１５を参照して図８のステップ805を詳細に説明する。まず、ステップ1401にて、Currentが終点を表しているか否かを判定する。即ち、Currentの符号が０であるか否かを判定する。Currentが終点を表しているならば、ステップ1402にて、結果リストＬに２つの要素(Xｊ,−) (Xｊ+1,0)を追加して、終了ステップ1417に飛ぶ。Currentが終点を表していない場合には、ステップ1403にて、Currentの次の要素を取り出し、それをNextとする。
【００７６】
ステップ1404は、Nextの点がXｊであるか否かを判定する。Nextの点がXｊである場合には、ステップ1405に進む。ステップ1405にて、パスｐｉが時計周りか反時計周りかを判定する。ステップ1404にて、Nextの点がXiでない場合、即ち、Xｊ+1の場合には、ステップ1408（図１５）に進む。
【００７７】
ステップ1405にて、Currentの符号が正であるか否かを判定する。Currentの符号が正であるならば、パスｐｉが時計周りであることを意味し、ステップ1406に進む。Currentの符号が負ならば、パスｐｉが反時計周りであることを意味し、ステップ1407に進む。
【００７８】
ステップ1406は、パスｐｉが時計周りである場合の処理で、結果リストＬに(Xｊ,−) (Xｊ+1,＋) (Xｊ+1,-) (Xｊ,−)を追加して終了ステップ1417に飛ぶ。
【００７９】
ステップ1407は、パスｐｉが反時計周りである場合の処理で、結果リストＬに(Xｊ,−) (Xｊ+1,-) (Xｊ+1,＋) (Xｊ,−)を追加して終了ステップ1417に飛ぶ。終了ステップ1417は、インデックスＩを２インクリメントする。
【００８０】
図１５を参照する。ステップ1408にて、Nextが終点であるか否かを判定する。尚、ステップ1408にて、Nextの点はXｊ+1である。Nextが終点であるか否かは、符号が０であるか否かを判定すればよい。Nextが終点である場合には、ステップ1409に進み、パスｐｉが、点Xｊ+1に到達する途中に、点Xｊの上側を通ったか否か判定する。Currentの符号が正の場合には、パスｐｉが、上側を通ったことになり、ステップ1410にて、結果リストＬに(Xｊ,0)を追加して、終了ステップ1417に飛ぶ。
【００８１】
パスｐｉが、点Xｊ+1に到達する途中に、点Xｊの下側を通った場合には、ステップ1411に進む。ステップ1411にて、結果リストＬに（Xｊ,-）（Xｊ+1,-）（Xｊ+1,+）（Xｊ,0）を追加して終了ステップ1417に飛ぶ。
【００８２】
ステップ1408にて、Nextが終点でない場合、即ち、CurrentとNextが共に終点でない場合には、ステップ1412に進む。ステップ1412にて、CurrentとNextの符号が等しいか否か判定する。両者の符号が等しい場合には、ステップ1413に進み、結果リストＬにCurrentとNextを追加する。これは、パスｐｉのこの部分については、なんら変更を加えないことを意味する。
【００８３】
ステップ1412にて、CurrentとNextの符号が等しくない場合には、ステップ1414に進み、Nextの符号が正であるか否かを判定する。即ち、パスｐｉが右上がりか否かを判定する。ステップ1414にて、Nextの符号が正である場合には、パスｐｉが右上がりであるから、ステップ1415に進み、結果リストＬに（Xｊ,-）（Xｊ+1,-）（Xｊ+1,-）（Xｊ+1,+）（Xｊ,-）（Xｊ,+）（Xｊ+1,+）を追加して、終了ステップ1417に飛ぶ。
【００８４】
ステップ1414にて、Nextの符号が負の場合には、パスｐｉが左上がりであるから、ステップ1416に進み、結果リストＬに（Xｊ+1,-）（Xｊ+1,+）を追加して、終了ステップ1417に飛ぶ。
【００８５】
以上、ステップ805の処理、即ち、Currentの点がXｊの場合の処理を詳細に説明したが、ステップ807の処理、即ち、Currentの点がXｊ+1の場合の処理も同様であり、その説明は省略する。
こうして、パスｐｉに対して、カノ二カルな生成元σｉを順次に作用させると、最終的には、作用させた結果パスに対応する結果リストＬが生成される。
【００８６】
上述の例では、群Ｇがブレード群である場合を説明したが群Ｇはブレード群でなくてもよい。また、上述の方法はコンピュータによって実行されるが、本発明は、コンピュータによって読み取り可能なプログラム又はそのようなプログラムを格納した媒体も含まれるものである。
【００８７】
以上、本発明の例を説明したが、本発明は上述の例に限定されるものにてなく、特許請求の範囲に記載された発明の範囲にて様々な変更が可能であることは当業者に理解されよう。
【図面の簡単な説明】
【００８８】
【図１】本発明による共通キーの生成システムの概略構成を示す図である。
【図２】本発明による共通キーの生成処理の予備的処理を示す流れ図である。
【図３】本発明による共通キーの本処理を示す流れ図である。
【図４】本発明によるデコード処理（図３のステップ３０３）を示す流れ図である。
【図５】カノニカルな生成元(N=3)を作用させる前のパスを示す図である。
【図６】カノニカルな生成元(N=3)を作用させた後のパスを示す図である。
【図７】本発明によるエンコード処理（図２のステップ２０４）を示す流れ図である。
【図８】本発明によるパスに対してカノニカルな生成元を作用させる処理（図７のステップ７０３）を説明するための流れ図である。
【図９】本発明によるデコード処理（図４のステップ４０３）を示す流れ図である。
【図１０】パスPIから対応する群の元Σ´を生成する処理（図９のステップ９０３）を示す流れ図である。
【図１１】図１０のステップ１００４の（Ｘ０、−１）の時の処理を示す流れ図である。
【図１２】図１０のステップ１００６のＸn−１の時の処理を示す流れ図である。
【図１３】図１０のステップ１００７のＸn+１の時の処理を示す流れ図である。
【図１４】図８のステップ８０５の処理を示す流れ図である。
【図１５】図８のステップ８０５の処理を示す流れ図である。
【符号の説明】
【００８９】
１０…エンティティ、  １１…群Ｇ保存装置、  １２…部分集合ＸＡ保存装置、  １３…部分集合ＸＢ保存装置、  １４…固有キーａ保存装置、  １５…演算装置、  １６…エンコーダ、  １７…デコーダ、  １８…送受信装置、  ２０…エンティティ、  ２１…群Ｇ保存装置、  ２２…部分集合ＸＢ保存装置、  ２３…部分集合ＸＡ保存装置、  ２４…固有キーｂ保存装置、  ２５…演算装置、  ２６…エンコーダ、  ２７…デコーダ、  ２８…送受信装置、  ３０…通信回線
【図１】
2005086778.tif 000003
【図２】
2005086778.tif 000004
【図３】
2005086778.tif 000005
【図４】
2005086778.tif 000006
【図５】
2005086778.tif 000007
【図６】
2005086778.tif 000008
【図７】
2005086778.tif 000009
【図８】
2005086778.tif 000010
【図９】
2005086778.tif 000011
【図１０】
2005086778.tif 000012
【図１１】
2005086778.tif 000013
【図１２】
2005086778.tif 000014
【図１３】
2005086778.tif 000015
【図１４】
2005086778.tif 000016
【図１５】
2005086778.tif 000017