(57)【要約】【課題】予備通信を行うことなく共通キーを生成する方式において、センタを必要とすることなく、且つセキュアでない通信環境にて、共通キーを生成する。【解決手段】第１のエンティティにて群Ｇの部分集合ＸＡから固有キーａを生成し、ａ＊ＸＢ＊ａ−１を生成し、それを第２のエンティティに送信する。第２のエンティティにて群Ｇの部分集合ＸＢから固有キーｂを生成し、ｂ＊ＸＡ＊ｂ−１を生成し、それを第１のエンティティに送信する。第１のエンティティにて、第２のエンティティより送信されたｂ＊ＸＡ＊ｂ−１を使用して、ｂ＊ａ＊ｂ−１を生成し、共通キーとして、（ｂ＊ａ＊ｂ−１）＊ａ−１を生成する。第２のエンティティにて、第１のエンティティより送信されたａ＊ＸＢ＊ａ−１を使用して、ａ＊ｂ＊ａ−１を生成し、共通キーとして、ｂ＊（ａ＊ｂ＊ａ−１）−１を生成する。【選択図】　図１
2004032574.tif 000002
【特許請求の範囲】
【請求項１】
群Ｇを保存するための群Ｇ保存装置と上記群Ｇの部分集合ＸＡを保存するための部分集合ＸＡ保存装置と上記群Ｇの部分集合ＸＢを保存するための部分集合ＸＢ保存装置と固有キーａを保存するための固有キーａ保存装置とを有する第１のエンティティと、群Ｇを保存するための群Ｇ保存装置と上記群Ｇの部分集合ＸＢを保存するための部分集合ＸＢ保存装置と上記群Ｇの部分集合ＸＡを保存するための部分集合ＸＡ保存装置と固有キーｂを保存するための固有キーｂ保存装置とを有する第２のエンティティと、を有し、上記第１のエンティティは、上記部分集合ＸＡから固有キーａを生成し、演算結果ａ＊ＸＢ＊ａ−１を生成し、それを上記第２のエンティティに送信し、上記第２のエンティティは、上記部分集合ＸＢから固有キーｂを生成し、演算結果ｂ＊ＸＡ＊ｂ−１を生成し、それを上記第２のエンティティに送信し、上記第１のエンティティは、上記第２のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して共通キー（ｂ＊ａ＊ｂ−１）＊ａ−１を生成し、上記第２のエンティティは、上記第１のエンティティより送信された演算結果ａ＊ＸＢ＊ａ−１を使用して共通キーｂ＊（ａ＊ｂ＊ａ−１）−１を生成するように構成されている共通キーの生成装置。
【請求項２】
上記群ＧはＢｒａｉｄ群であることを特徴とする請求項１記載の共通キーの生成装置。
【請求項３】
第１及び第２のエンティティに対して群Ｇと該群Ｇの部分集合ＸＡ、ＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が付与されているとき、
上記第１のエンティティにて上記部分集合ＸＡから固有キーａを生成することと、
上記第２のエンティティにて上記部分集合ＸＢから固有キーｂを生成することと、
上記第１のエンティティにて演算結果ａ＊ＸＢ＊ａ−１を生成し、それを上記第２のエンティティに送信することと、
上記第２のエンティティにて演算結果ｂ＊ＸＡ＊ｂ−１を生成し、それを上記第１のエンティティに送信することと、
上記第１のエンティティにて、上記第２のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して、演算結果ｂ＊ａ＊ｂ−１を生成し、両エンティティ間の共通キーとして、（ｂ＊ａ＊ｂ−１）＊ａ−１を生成することと、
上記第２のエンティティにて、上記第１のエンティティより送信された演算結果ａ＊ＸＢ＊ａ−１を使用して、演算結果ａ＊ｂ＊ａ−１を生成し、両エンティティ間の共通キーとして、ｂ＊（ａ＊ｂ＊ａ−１）−１を生成することと、
を含む共通キーの生成方法。
【請求項４】
上記群ＧはＢｒａｉｄ群であることを特徴とする請求項３記載の共通キーの生成方法。
【請求項５】
群Ｇと該群Ｇの部分集合ＸＡ、ＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が付与されているとき、
上記部分集合ＸＡから固有キーａを生成する過程と、
演算結果ａ＊ＸＢ＊ａ−１を生成し、それを他のエンティティに送信する過程と、
他のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して、演算結果ｂ＊ａ＊ｂ−１を生成し、自分及び他のエンティティ間の共通キーとして、（ｂ＊ａ＊ｂ−１）＊ａ−１を生成する過程と、
を含む共通キーの生成プログラム。
【請求項６】
上記群ＧはＢｒａｉｄ群であることを特徴とする請求項５記載の共通キーの生成プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、予備通信を行うことなく共通キーを生成するための共通キーの生成装置、生成方法及び生成プログラムに関する。
【０００２】
【従来の技術】
共通キー方式では、送信者と受信者が同一の暗号化及び復号化キーを有する。送信者側と受信者側が共通のキーを保持する方法として、予備通信によって送信者と受信者に共通キーを付与する第１の方式と、予備通信を行うことなく送信者と受信者に共通キーを付与する方式とがある。予備通信を行うことなく暗号化及び復号化キーを共有する方法には、予め暗号通信を行う可能性がある相手のキーを秘密保管しておく第２の方式と、送信者と受信者が独立に同一キーを生成する第３の方式がある。第３の方式として、例えば、ＩＤ−ＮＩＫＥＳ（ＩＤ−Ｂａｓｅｄ　Ｎｏｎ−Ｉｎｔｅｒａｃｔｉｖｅ　　Ｋｅｙ　Ｓｈａｒｉｎｇ　　Ｓｃｈｅｍｅｓ）が知られている。
【０００３】
ＩＤ−ＮＩＫＥＳでは、エンティティ（通信者）を管理するセンタの存在が必要であり、センタは秘密情報［ＳＣｊ］（ｊ＝１，２，…ｎ）、公開情報［ＰＣｊ］（ｊ＝１，２，…ｎ）及び全てのエンティティのＩＤ情報を有する。２つのエンティティＸ、Ｙ間で暗号通信を行う場合、センタは、先ず、送信者であるエンティティＸに次の秘密情報ＳＸを秘密裏に送信する。
【０００４】
【数１】
ＳＸ＝Ｆ（［ＳＣｊ］，［ＰＣｊ］，ＩＤＸ）
Ｆは関数を表す。［ＳＣｊ］は秘密情報、［ＰＣｊ］は公開情報、ＩＤＸはエンティティＸのＩＤ情報より生成された情報を表し、これらは関数Ｆの独立変数である。
【０００５】
エンティティＸは、次の式によって、受信者であるエンティティＹに対する共通キーを生成する。
【０００６】
【数２】
ＫＸＹ＝ｆ（ＳＸ，［ＰＣｊ］，ＩＤＹ）
ｆは関数を表す。ＩＤＹはエンティティＹのＩＤ情報より生成された情報を表す。受信者であるエンティティＹは、同様に、次の式によって、送信者であるエンティティＸに対する共通キーを生成する。
【０００７】
【数３】
ＫＹＸ＝ｆ（ＳＹ，［ＰＣｊ］，ＩＤＸ）
ここで、センタは、ＫＸＹ＝ＫＹＸとなるように、関数Ｆを決め、それを各エンティティＸ、Ｙに送信する。各エンティティはセンタより送信された関数Ｆを使用して関数ｆを決める。こうして関数ｆが得られると、各エンティティは数２又は数３の式より共通キー、ＫＸＹ＝ＫＹＸを求めることができる。
【０００８】
【発明が解決しようとする課題】
上述の方法では、（１）エンティティを管理する信頼性あるセンタが必要である、（２）センタはエンティティＸ、Ｙに秘密情報ＳＸ及びＳＹを秘密裏に送信しなければならない、（３）センタは、ＫＸＹ＝ＫＹＸとなるように、関数Ｆを決定する必要がある、等の欠点を有する。
【０００９】
先ず、（１）の問題では、センタは全てのエンティティの秘密情報を保持するため、センタが所謂Ｂｉｇ　　Ｂｒｏｔｈｅｒとなる可能性がある。即ち、センタがＫｅｙ　　Ｅｓｃｒｏｗ　　Ｓｙｓｔｅｍになる可能性がある。また、幾つかのエンティティが結託してセンタの有する秘密を解読する結託問題がある。（２）の問題では、センタは秘密情報ＳＸ及びＳＹを各エンティティに秘密裏の送信しなければならないため、インターネット等のセキュアでない公衆通信網を利用することができない。（３）の問題では、関数ｆは各エンティティが計算するが、関数Ｆはセンタが計算するため、関数ｆもセンタに知られることとなる。
【００１０】
本発明の目的は、予備通信を行うことなく共通キーを生成する方式において、センタを必要とすることなく、共通キーを生成するための装置及び方法を提供することにある。
【００１１】
本発明の目的は、更に、予備通信を行うことなく共通キーを生成する方式において、インターネット等のセキュアでない通信環境を利用して、共通キーを生成するための装置及び方法を提供することにある。
【００１２】
【課題を解決するための手段】
本発明によると、共通キーの生成装置は、群Ｇを保存するための群Ｇ保存装置と上記群Ｇの部分集合ＸＡを保存するための部分集合ＸＡ保存装置と上記群Ｇの部分集合ＸＢを保存するための部分集合ＸＢ保存装置と固有キーａを保存するための固有キーａ保存装置とを有する第１のエンティティと、群Ｇを保存するための群Ｇ保存装置と上記群Ｇの部分集合ＸＢを保存するための部分集合ＸＢ保存装置と上記群Ｇの部分集合ＸＡを保存するための部分集合ＸＡ保存装置と固有キーｂを保存するための固有キーｂ保存装置とを有する第２のエンティティと、を有し、上記第１のエンティティは、上記部分集合ＸＡから固有キーａを生成し、演算結果ａ＊ＸＢ＊ａ−１を生成し、それを上記第２のエンティティに送信し、上記第２のエンティティは、上記部分集合ＸＢから固有キーｂを生成し、演算結果ｂ＊ＸＡ＊ｂ−１を生成し、それを上記第２のエンティティに送信し、上記第１のエンティティは、上記第２のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して共通キー（ｂ＊ａ＊ｂ−１）＊ａ−１を生成し、上記第２のエンティティは、上記第１のエンティティより送信された演算結果ａ＊ＸＢ＊ａ−１を使用して共通キーｂ＊（ａ＊ｂ＊ａ−１）−１を生成するように構成されている。
【００１３】
本発明によると、上記群ＧはＢｒａｉｄ群である。
本発明によると、共通キーの生成方法は、第１及び第２のエンティティに対して群Ｇと該群Ｇの部分集合ＸＡ、ＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が付与されているとき、
上記第１のエンティティにて上記部分集合ＸＡから固有キーａを生成することと、
上記第２のエンティティにて上記部分集合ＸＢから固有キーｂを生成することと、
上記第１のエンティティにて演算結果ａ＊ＸＢ＊ａ−１を生成し、それを上記第２のエンティティに送信することと、
上記第２のエンティティにて演算結果ｂ＊ＸＡ＊ｂ−１を生成し、それを上記第１のエンティティに送信することと、
上記第１のエンティティにて、上記第２のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して、演算結果ｂ＊ａ＊ｂ−１を生成し、両エンティティ間の共通キーとして、（ｂ＊ａ＊ｂ−１）＊ａ−１を生成することと、
上記第２のエンティティにて、上記第１のエンティティより送信された演算結果ａ＊ＸＢ＊ａ−１を使用して、演算結果ａ＊ｂ＊ａ−１を生成し、両エンティティ間の共通キーとして、ｂ＊（ａ＊ｂ＊ａ−１）−１を生成することと、
を含む。更に、本発明によると、上記群ＧはＢｒａｉｄ群である。
【００１４】
本発明によると、共通キーの生成プログラムは、群Ｇと該群Ｇの部分集合ＸＡ、ＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が付与されているとき、
上記部分集合ＸＡから固有キーａを生成する過程と、
演算結果ａ＊ＸＢ＊ａ−１を生成し、それを他のエンティティに送信する過程と、
他のエンティティより送信された演算結果ｂ＊ＸＡ＊ｂ−１を使用して、演算結果ｂ＊ａ＊ｂ−１を生成し、自分及び他のエンティティ間の共通キーとして、（ｂ＊ａ＊ｂ−１）＊ａ−１を生成する過程と、
を含む。更に、本発明によると、上記群ＧはＢｒａｉｄ群である。
【００１５】
従って、本発明によると、２つのエンティティ間にて、それぞれ共通キーを生成するから、エンティティを管理するセンタを必要としない利点がある。
【００１６】
本発明によると、２つのエンティティ間にて、演算結果ｂ＊ＸＡ＊ｂ−１及びｂ＊ＸＡ＊ｂ−１を送信するが、固有キーａ、ｂを送信することはないから、インターネットのようにセキュアでない通信環境を利用して共通キーを生成することができる利点がある。
【００１７】
【発明の実施の形態】
図１を参照して本発明の共通キーの生成システムの例を説明する。本例の共通キーの生成システムは、第１及び第２のエンティティ１０、２０を有し、両者は通信回線３０によって接続されている。通信回線３０は、必ずしもセキュアである必要はなく、インターネット等のような公衆通信網であってよい。
【００１８】
第１のエンティティ１０は、群Ｇ保存装置１１と第１の部分集合ＸＡ保存装置１２と第２の部分集合ＸＢ保存装置１３と固定キーａ保存装置１４と演算装置１５と送受信装置１６とを有する。第２のエンティティ２０は、群Ｇ保存装置２１と第１の部分集合ＸＢ保存装置２２と第２の部分集合ＸＡ保存装置２３と固定キーｂ保存装置２４と演算装置２５と送受信装置２６とを有する。
【００１９】
尚、第１及び第２のエンティティ１０、２０は、コンピュータ装置であってよく、それぞれ、ディスプレイ部、入力装置等を有するが、図示は省略する。保存装置１１、２１、１２、２２、１３、２３及び１４、２４は、コンピュータ装置に設けられた外部又は内部記憶装置であってよい。
【００２０】
群Ｇ保存装置１１、２１は、群Ｇの定義情報を保存する。群Ｇが一般の群の場合には、定義情報は、生成元の個数と生成元間の制約を含む。群ＧがＢｒａｉｄ群の場合には、位数、即ち、整数を指定するだけで群Ｇが完全に特定されるから、定義情報は、位数のみを含む。群Ｇ保存装置１１、２１の内部構成は後に図５を参照して説明する。
【００２１】
第１及び第２の部分集合ＸＡ保存装置１２、２３は群Ｇの部分集合ＸＡを保存する。第２及び第１の部分集合ＸＢ保存装置１３、２２は群Ｇの部分集合ＸＢを保存する。部分集合ＸＡ、ＸＢの元には順番が付されており、この順番は、２つのエンティティ１０、２０において同一である。一般に、部分集合の元は、生成元からなる語で記述される。これらの部分集合ＸＡ保存装置１２、２３及び部分集合ＸＢ保存装置１３、２２の内部構成は後に図７を参照して説明する。
【００２２】
固定キーａ保存装置１４及び固定キーｂ保存装置２４は、部分集合ＸＡ、ＸＢから生成された群Ｇの元ａ、ｂを固定キーとして保存する。固定キーａ保存装置１４及び固定キーｂ保存装置２４には、部分集合ＸＡ、ＸＢから固有キーａ、ｂを生成する方法の情報、即ち、どのような順番によってＸＡ、ＸＢの元が掛け合わされたかという情報も格納されている。固定キーａ保存装置１４及び固定キーｂ保存装置２４の内部構成の例は、後に図９を参照して説明する。固定キーの例、生成方法等に関しては、後に、図１０、図１１及び図１２を参照して説明する。
【００２３】
固定キーａ、ｂは、各エンティティ１０、２０によって生成されるが、共通キーの計算に際して、他のエンティティ又は外部に送信されることはない。従って、第三者が固有キーを知ることは困難である。
【００２４】
本例によると、先ず、サーバ等（図示なし）により、群Ｇ及び群Ｇの２つの部分集合ＸＡ及びＸＢからなる組（Ｇ，ＸＡ，ＸＢ）が生成され、第１及び第２のエンティティ１０、２０に付与される。第三者が、３つの群の組（Ｇ，ＸＡ，ＸＢ）を傍受しても、それから共通キーを求めることは困難である。従って、群の組（Ｇ，ＸＡ，ＸＢ）は、インターネット等のセキュアでない公衆網を経由して、２つのエンティティ１０、２０に送信される。
【００２５】
図２を参照して、本発明による共通キーの生成方法の予備的処理を説明する。本例の処理では、第１のエンティティ１０は、演算ａ＊ＸＡ＊ａ−１を行い、それを第２のエンティティ２０に送信する。尚、第２のエンティティ２０も、演算ｂ＊ＸＡ＊ｂ−１を行い、それを第１のエンティティ１に送信するが、この処理は、第１のエンティティ１０における処理と同様であり、その説明は省略する。
【００２６】
先ずステップＳ２０にて、固有キーａ保存装置１４に格納されている固有キーａを取り出す。固有キーａは、部分集合ＸＡより生成され、固有キーａ保存装置１４に既に格納されているものとする。ステップＳ２１にて、第２のエンティティ２０へ送信する演算結果ａ＊ＸＡ＊ａ−１を格納するためのリストＬを初期化する。ステップＳ２２にて、第２の部分集合ＸＢ保存装置１３より、元に付された順番に従って、未処理の最初の元を取り出し、それをｘとする。例えば、部分集合がＸＢ＝［ｂ１、ｂ２、ｂ３］である場合、その元はｘ＝ｂ１、ｂ２又はｂ３である。
【００２７】
ステップＳ２３では、演算ａ＊ｘ＊ａ−１を行い、それをリストＬの最後に追加する。例えば、部分集合がＸＢ＝［ｂ１、ｂ２、ｂ３］である場合、その元はｘ＝ｂ１、ｂ２又はｂ３であり、ａ＊ｘ＊ａ−１＝ａ＊ｂ１＊ａ−１、ａ＊ｂ２＊ａ−１又はａ＊ｂ３＊ａ−１である。リストＬが初期化された直後では、リストの先頭になる。尚、演算結果ａ＊ｘ＊ａ−１は第三者が、固有キーａを容易に類推することができないように、適当な表現方法により表現される。
【００２８】
ステップＳ２４にて、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘが処理されたか否かを判定する。全ての元が処理されていなければステップＳ２２に戻り、全ての元が処理されているならステップＳ２５に進む。
【００２９】
ステップＳ２５では、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘに対する演算結果ａ＊ｘ＊ａ−１から構成されるリストＬを第２のエンティティ２０に送信する。リストＬには、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘに対する演算結果ａ＊ｘ＊ａ−１が第２の部分集合ＸＢ保存装置１３における元の順番と同一の順番にて、格納されている。例えば、部分集合がＸＢ＝［ｂ１、ｂ２、ｂ３］である場合、リストＬには、第２の部分集合ＸＢ保存装置１３に保存された全ての元ｘ＝ｂ１、ｂ２又はｂ３に対する演算結果ａ＊ｘ＊ａ−１＝ａ＊ｂ１＊ａ−１、ａ＊ｂ２＊ａ−１、又はａ＊ｂ３＊ａ−１が第２の部分集合ＸＢ保存装置１３における元の順番（ｂ１、ｂ２、ｂ３）と同一の順番にて、格納されている。
【００３０】
図３を参照して、本発明による共通キーの生成方法の本処理を説明する。本例の処理では、第１のエンティティ１０において、共通キーとして（ｂ＊ａ＊ｂ−１）＊ａ−１を計算する。この計算は、図２に示した予備的処理と並行して実行されてよい。
【００３１】
先ずステップＳ３０にて群の元である変数Ｙを初期化する。即ち、変数Ｙに中立元Ｅを代入する。ステップＳ３１にて、第２のエンティティ２０より送信される演算結果ｂ＊ＸＡ＊ｂ−１を格納するためのリストＬを初期化する。ステップＳ３２にて、第２のエンティティ２０より送信された演算結果ｂ＊ＸＡ＊ｂ−１を、部分集合ＸＡの元ｘの順番にしたがって、リストＬに格納する。
【００３２】
例えば、部分集合をＸＡ＝｛ａ１，ａ２，ａ３｝とすると、その元ｘの順番はａ１、ａ２、ａ３である。演算結果はｂ＊ＸＡ＊ｂ−１＝｛ｂ＊ａ１＊ｂ−１，ｂ＊ａ２＊ｂ−１，ｂ＊ａ３＊ｂ−１｝である。演算結果ｂ＊ＸＡ＊ｂ−１は、その元ｙ＝ｂ＊ｘ＊ｂ−１の順番が、ｂ＊ａ１＊ｂ−１、ｂ＊ａ２＊ｂ−１、ｂ＊ａ３＊ｂ−１となるように格納される。
【００３３】
ここで第１のエンティティ１０は、第２のエンティティ２０の固有キーｂそのものを入手する必要はなく、演算結果ｂ＊ｘ＊ｂ−１のみを入手すればよいことに留意されたい。
【００３４】
ステップＳ３３にて、固有キーａ保存装置１４に格納されている固有キーａを取り出す。固有キーａは、以下に図１２を参照して説明するが、部分集合ＸＡの元ｘに符号を付して順番に積を演算することにより生成される。固有キーａにはその生成過程を示す情報が含まれる。ステップＳ３４にて、固有キーａより部分集合ＸＡの元ｘとその指数ｎ（０以外の整数）を取り出す。ステップＳ３５にて、リストＬより部分集合ＸＡの元ｘに対応する演算結果ｂ＊ＸＡ＊ｂ−１の元ｙ＝ｂ＊ｘ＊ｂ−１を取り出す。ステップＳ３６にて、元ｙのｎ乗、即ちｙｎを演算する。ステップＳ３７にて、変数Ｙとｙｎの積を演算する。ｙｎを変数Ｙに右から掛けるか左から掛けるかは、固有キーａの構成法に順ずる。ステップＳ３８にて、固有キーａの全ての元に対して処理がされたかを判定する。全ての元に対して処理がなされていない場合には、ステップＳ３４に戻り、未処理の元に対して、上述の処理がなされる。
【００３５】
固有キーａの全ての元に対して処理がなされている場合には、ステップＳ３９に進む。ステップＳ３９では、Ｙ＊ａ−１を演算する。ステップＳ３９に到達したときには、Ｙ＝ｂ＊ａ＊ｂ−１となっている。従って、Ｙ＊ａ−１＝（ｂ＊ａ＊ｂ−１）ａ−１である。これが共通キーとなる。
【００３６】
図４を参照して、第２のエンティティ２０における共通キーの計算手順を説明する。ステップＳ３８までは、図３の例と同様であり、上述の説明において、ａをｂとし、ＸＡをＸＢとすればよい。
【００３７】
ステップＳ３９１の差分処理にて、ｂ＊Ｙ−１＝ｂ＊（ａ＊ｂ＊ａ−１）−１を演算する。ステップＳ３９１に到達したときには、Ｙ＝ａ＊ｂ＊ａ−１である。従って共通キーはｂ＊（ａ＊ｂ＊ａ−１）−１である。
【００３８】
尚、恒等式（ｂ＊ａ＊ｂ−１）ａ−１＝ｂ＊（ａ＊ｂ＊ａ−１）−１が成り立つことに留意されたい。したがって、２つのエンティティ１０、２０にて同一の共通キーが得られる。
【００３９】
図５を参照して群Ｇ保存装置１１、２１の内部構成を説明する。群Ｇ保存装置１１、２１は群Ｇの定義５０を含む。群Ｇの定義５０は、生成元の個数５１と生成元間の制約５２を含む。本例では、生成元の個数はｎ個である。制約５２は複数の制約条件からなり、群Ｇは指定された全ての制約条件を満足する必要がある。各制約条件５３は、生成元を表すｉ、ｊと指数を表すｍ、ｎからなる１対の数字を含む。生成元ｉ、ｊは１からｎまでの整数であり、指数ｍ、ｎは０以外の整数である。群ＧがＢｒａｉｄ群の場合には、制約条件は、群の位数のみである。
【００４０】
図６を参照して制約条件の意味を説明する。参照符号６１は、群Ｇの生成元の個数ｎが９以上のとき、群Ｇ保存装置１１、２１に格納された制約条件の１例を示す。参照符号６２は、群Ｇの生成元をＸ１，Ｘ２，Ｘ３，…Ｘｎと表したとき、制約条件６１を具体的に表したものである。
【００４１】
図７を参照して部分集合ＸＡ保存装置１２、２３の内部構成の例を説明する。尚、部分集合ＸＢ保存装置１３、２２は部分集合ＸＡ保存装置１２、２３と同様である。部分集合ＸＡ保存装置１２、２３は部分集合ＸＡの定義７０を含む。本例では、部分集合ＸＡの元の個数はｐ個である。部分集合ＸＡの定義７０はｐ個の定義からなる。参照符号７１は１つの元の定義を表す。定義７１は、複数の対を含み、各対は生成元ｉとその指数ｍからなる。
【００４２】
図８を参照して、部分集合ＸＡの定義を説明する。尚、部分集合ＸＢは部分集合ＸＡと同様である。本例では、群の生成元の個数ｎは３以上であり、部分集合ＸＡの元の個数は２個である。参照符号８０は２個の元の定義を示し、参照符号８１は群Ｇの生成元をＸ１，Ｘ２，Ｘ３，…Ｘｎと表したとき、２個の元を具体的に表したものである。
【００４３】
図９を参照して固有キーａ保存装置の内部構成を説明する。尚、固有キーｂ保存装置は固有キーａ保存装置と同様である。参照符号９０は、固有キーａ保存装置１４に保存された固有キーａの定義の例を示す。各定義は、複数の対を含み、各対は部分集合ＸＡの元ｉとその指数ｍからなる。
【００４４】
図１０を参照して、固有キーａの具体例を説明する。本例では、部分集合ＸＡの元の個数は２個である。参照符号１００は固有キーａの定義の例を示し、参照符号１０１は、部分集合ＸＡの元をｘａ１，ｘａ２，ｘａ３，…ｘａｎと表したとき、固有キーａの元を具体的に表したものである。
【００４５】
図１１を参照して、固有キーａの具体例を説明する。本例では、生成元の個数は３以上であり、部分集合ＸＡの元の個数は２個である。参照符号１１０は、固有キーａ保存装置１４に保存された固有キーの定義の例を示し、２つの定義１１６、１１７の例が示されている。参照符号１１１は、固有キーａ保存装置１４にて格納された状態の固有キーａを表示したものである。参照符号１１２は、固有キーａを生成元によって表示したものであり、３つの固有キー１１３、１１４、１１５の例が示されている。元を生成元によって表示すると、２つの元の積の結果は２つの元を表すリストを繋げ合わせたものとなる。また、逆元は、リストの順番を逆にして且つ指数の符号を変えたものである。
【００４６】
第１の固有キー１１３は、固有キー１１１の最初の元（２，１）によって生成されたものである。この元（２，１）の生成元は２、指数は１である。従って、第１の固有キー１１３は、固有キー１１０の２番目の元１１７がそのまま記述されている。
【００４７】
第２の固有キー１１４は、固有キー１１１の２番目の元（１，−２）によって生成されたものである。この元（１，−２）の生成元は１、指数は−２である。従って、第２の固有キー１１４は、先ず、固有キー１１０の１番目の元１１６の順番を逆にし、その符号を反転させることにより、（３，６）（２，−３）（１，−２）を生成し、次に、それを二乗したものである。
【００４８】
固有キー１１５は、固有キー１１１の３番目の元（２，３）によって生成されたものである。この元（２，３）の生成元は２、指数は３である。従って、固有キー１１５は、固有キー１１０の２番目の元１１７を３乗することによって得られる。
【００４９】
上述の方法は、エンティティ内部にて群Ｇの元を処理する場合には、十分である。しかしながら、演算結果ｂ＊ＸＡ＊ｂ−１又はａ＊ＸＢ＊ａ−１をエンティティ間にて交信する場合には、適当に同値な表現に変えたほうがよい。特に、群ＧがＢｒａｉｄ群の場合には、元ｘの生成元を用いた冗長な表現を生成元を用いた簡単な表現に変えるアルゴリズムが知られている。従って、このようなアルゴリズムを適用して、演算結果ｂ＊ＸＡ＊ｂ−１又はａ＊ＸＢ＊ａ−１の各要素を簡単な表現に変えることができる。それによって、第三者は、演算結果ｂ＊ＸＡ＊ｂ−１又はａ＊ＸＢ＊ａ−１を見ても、固有キーａ、ｂを容易に類推することができない。
【００５０】
図１２を参照して、固有キーの生成方法を説明する。ステップＳ１２０にて、部分集合ＸＡに含まれる要素の数をｎに代入する。ステップＳ１２１にて、部分集合ＸＡの元により、固有キーａを生成したときの長さを＋ＲＡＮＤＡＭ関数によって決定する。この固有キーａの長さをＮに代入する。＋ＲＡＮＤＡＭ関数は自然数をランダムに返す関数である。ステップＳ１２２にて、リストに投入した要素数をカウントするためのカウンタＫを初期化する。ステップＳ１２３にて、リストＬを初期化する。これは一時的に固有キーａを保持するためのワーク領域である。ステップＳ１２４にて、部分集合ＸＡの元を決定するために、ＭＯＤ−ＲＡＮＤＡＭ（ｎ）の結果をＩに代入する。ＭＯＤ−ＲＡＮＤＡＭ（ｎ）は１からｎまでの値をランダムに返す関数である。
【００５１】
ステップＳ１２５にて、指数の絶対値を決定するために、＋ＲＡＮＤＡＭの結果をＭに代入する。＋ＲＡＮＤＡＭは＋１をランダムに返す関数である。ステップＳ１２６にて、指数の絶対値を決定するために、ＳＩＧＮ−ＲＡＮＤＡＭ（ｎ）の結果をＳに代入する。ＳＩＧＮ−ＲＡＮＤＡＭ（ｎ）は＋１、−１をランダムに返す関数である。
【００５２】
ステップＳ１２７にて、指数を計算するために、Ｓ＊ＭをＭに代入する。ステップＳ１２８にて、リストＬの最後であるＫ番目に、ペア（Ｉ，Ｍ）を代入する。ステップＳ１２９にて、終了判定のためにカウンタＫのインデックスを１つ増加する。ステップＳ１２０１にて、終了判定を行う。カウンタＫがＮ回より大きいかを判定し、リストＬに対してＮ回処理が行われたかを確認する。カウンタＫがＮ回より小さいか又は等しい場合には、ステップＳ１２４に戻る。カウンタＫがＮ回より大きい場合には、ステップＳ１２０２に進み、リストＬを固有キーａ保存装置１４に格納する。ステップＳ１２０２に到達したときには、既にリストＬには、Ｎエントリが入っている。
【００５３】
図１２の固定キーの生成方法において、部分集合ＸＡの代わりにＸＢを使用することにより、固定キーｂを生成することができる。本例では、固定キーａ、ｂの生成方法を、エンティティの中だけで決定することができるので、第三者が傍受することはできない。
【００５４】
以上、本発明の実施の態様について説明したが、本発明は、上述の実施の態様に限定されるものではなく、特許請求の範囲に記載された発明の範囲にて、様々な変更が可能であることは当業者にとって理解されよう。
【００５５】
【発明の効果】
本発明によると、予備通信を用いることなく共通キーを生成する場合に、エンティティを管理するセンタを必要としない利点がある。
【００５６】
本発明によると、予備通信を用いることなく共通キーを生成する場合に、エンティティ間にて、固有キーではなく、演算結果ａ＊ＸＡ＊ａ−１又はｂ＊ＸＢ＊ｂ−１を送信するから、第三者に固有キーが傍受されることはない利点がある。
【００５７】
本発明によると、予備通信を用いることなく共通キーを生成する場合に、エンティティ内にて、固有キーの生成するから、第三者に固有キーが傍受されることはない利点がある。
【図面の簡単な説明】
【図１】本発明による共通キーの生成装置の概略構成を示す図である。
【図２】本発明による第１のエンティティにおける共通キーの生成処理の予備的処理を示す流れ図である。
【図３】本発明による第１のエンティティにおける共通キーの本処理を示す流れ図である。
【図４】本発明による第２のエンティティにおける共通キーの生成処理の差分工程を示す図である。
【図５】本発明による群Ｇ保存装置の内部構成の概略を示す図である。
【図６】本発明による群Ｇ保存装置に保存された群の生成元の制約の例を示す図である。
【図７】本発明による部分集合ＸＡ保存装置の内部構成の概略を示す図である。
【図８】本発明による部分集合ＸＡ保存装置に保存された部分集合ＸＡの例とその意味を示す図である。
【図９】本発明による固有キーａ保存装置の内部構成の概略を示す図である。
【図１０】本発明による固有キーａ保存装置に保存された固有キーａの例とその意味を示す図である。
【図１１】本発明による固有キーａ保存装置に保存された固有キーａを生成元によって表現した例とその意味を示す図である。
【図１２】本発明による固有キーａの生成処理を示す流れ図である。
【符号の説明】
１０…エンティティ、　１１…群Ｇ保存装置、　１２…部分集合ＸＡ保存装置、　１３…部分集合ＸＢ保存装置、　１４…固有キーａ保存装置、　１５…演算装置、　１６…送受信装置、　２０…エンティティ、　２１…群Ｇ保存装置、　２３…部分集合ＸＡ保存装置、　２２…部分集合ＸＢ保存装置、　２４…固有キーｂ保存装置、　２５…演算装置、　２６…送受信装置、　３０…通信回線
【図１】
2004032574.tif 000003
【図２】
2004032574.tif 000004
【図３】
2004032574.tif 000005
【図４】
2004032574.tif 000006
【図５】
2004032574.tif 000007
【図６】
2004032574.tif 000008
【図７】
2004032574.tif 000009
【図８】
2004032574.tif 000010
【図９】
2004032574.tif 000011
【図１０】
2004032574.tif 000012
【図１１】
2004032574.tif 000013
【図１２】
2004032574.tif 000014