(57)【特許請求の範囲】
【請求項１】
複数の通信装置からなる通信グループ内の全通信装置で暗号通信用の共通鍵を共有するための鍵共有方法であって、下記（ａ１）〜（ａ５）の手順を含むことを特徴とする鍵共有方法。
（ａ１）：最初に、前記通信グループを２つに分けた各サブグループ内の通信装置のうちの１つが、前記通信グループ内の全通信装置で共有する公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して公開データを生成し、当該装置が属するサブグループ内に、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が存在すれば、その通信装置のうちの１つを送信先としてこの公開データを送信する。
（ａ２）：前記サブグループ内の通信装置は、他の通信装置から公開データを受信すると、この公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して公開データを生成し、当該装置が属するサブグループ内に、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が存在すれば、その通信装置のうちの１つを送信先としてこの公開データを送信する。
（ａ３）：上記（ａ２）の手順は、生成した公開データの送信先が存在しなくなるまで繰り返される。
（ａ４）：上記（ａ１）又は（ａ２）で、自己が生成した公開データの送信先が存在しない通信装置は、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が前記通信グループ内に複数存在すれば、それらを２つのグループに分けた各グループ（以下、下位サブグループという）について、この下位サブグループ内の通信装置のうちの１つを送信先としてこの公開データを送信する。そして、この下位サブグループが上記（ａ２）のサブグループとなり、上記（ａ２）からの手順が行われる。
（ａ５）：上記（ａ１）又は（ａ２）で、自己が生成した公開データの送信先が存在しない通信装置は、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が前記通信グループ内に複数存在せず１つしか存在しなければ、この存在している通信装置を送信先としてこの公開データを送信する。そして、この公開データを受信した通信装置は、受信した公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して共通鍵を生成する。
【請求項２】
請求項１に記載の鍵共有方法において、
前記通信グループはｎ個の通信装置からなっていると共に、該ｎ個の通信装置で、素数ｑと、この素数ｑを法とするガロア体ＧＦ（ｑ）の原始元αとを公開データとして共有しており、更に、
上記（ａ１）の手順で生成される公開データＺaは、下記式（１）から算出され、
上記（ａ２）の手順で他の通信装置からの公開データＺbを受信した通信装置により生成される公開データＺcは、下記式（２）から算出され、
上記（ａ５）の手順で他の通信装置からの公開データＺdを受信した通信装置により生成される共通鍵Ｋは、下記式（３）から算出されること、
を特徴とする鍵共有方法。
【数１】
0003838926.tif 000005
【請求項３】
請求項１又は請求項２に記載の鍵共有方法において、
上記（ａ１）の手順で、前記２つのサブグループは、各サブグループ内の通信装置の数が同じ又は１つ違いとなるように分けられ、
上記（ａ４）の手順で、前記２つの下位サブグループは、各下位サブグループ内の通信装置の数が同じ又は１つ違いとなるように分けられること、
を特徴とする鍵共有方法
【請求項４】
請求項３に記載の鍵共有方法において、
前記通信グループが２k個の通信装置からなっていることを特徴とする鍵共有方法。
【請求項５】
請求項１ないし請求項４の何れか１項に記載の鍵共有方法により互いに暗号通信用の共通鍵を共有する通信装置であって、
前記鍵共有方法に基づき動作する手段として、
前記公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施す演算処理手段と、
他の通信装置との間で前記公開データの送受信を行う送受信手段と、
を備えたことを特徴とする通信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の通信装置で暗号通信用の共通鍵を安全に共有するための技術に関するものである。
【０００２】
【従来の技術】
従来より、２つの通信装置（ピア）で暗号通信用の共通鍵を共有するためのＩＫＡ（Initial Key Agreement）プロトコルとして、Diffie-Hellmanプロトコルが知られている。尚、暗号通信用の共通鍵を共有するためのプロトコルは、複数の通信装置で最初に共通鍵を共有する際に使われるＩＫＡプロトコルと、共通鍵を共有している複数の通信装置からなるグループが既に存在している場合に、そのグループへの新たな通信装置の追加や、そのグループからの通信装置の削除、また、共通鍵の更新といった操作を行う際に使われるＡＫＡ（Auxiliary Key Agreement）プロトコルとの２つに大別される。
【０００３】
ここで、Diffie-Hellmanプロトコルの内容について簡単に説明する。
図４に示すように、このプロトコルでは、前提条件として、２つの通信装置Ｐ1，Ｐ2が、１０２４ビット程度の大きな素数ｑと、この素数ｑを法とするガロア体ＧＦ（ｑ）の原始元αとを予め共有している。尚、これらのデータは、第三者に公開しても何ら問題がないため、例えば、２つの通信装置Ｐ1，Ｐ2間で通信により共有されるようにしてもよい。
【０００４】
そして、このプロトコルでは、まず、一方の通信装置Ｐ1が、乱数を発生させて、この値を当該装置Ｐ1のみが有する非公開の秘密鍵Ｎ1とし（即ち、秘密鍵Ｎ1を生成し）、下記式（４）から公開データＺ1を算出して、この算出した公開データＺ1を通信装置Ｐ2へユニキャストする。同様に、他方の通信装置Ｐ2も、当該装置Ｐ2のみが有する秘密鍵Ｎ2を生成し、下記式（５）から公開データＺ2を算出して、この算出した公開データＺ2を通信装置Ｐ1へユニキャストする。つまり、２つの通信装置Ｐ1，Ｐ2間で、それぞれの秘密鍵Ｎ1，Ｎ2を用いて生成した公開データＺ1，Ｚ2を交換するようになっている。
【０００５】
次に、通信装置Ｐ1は、通信装置Ｐ2から送られてきた公開データＺ2を用いて、下記式（６）から共通鍵Ｋを算出する。同様に、通信装置Ｐ2も、通信装置Ｐ1から送られてきた公開データＺ1を用いて、下記式（７）から共通鍵Ｋを算出する。ここで、各通信装置Ｐ1，Ｐ2にて算出された共通鍵Ｋは同じ値となるため、２つの通信装置Ｐ1，Ｐ2で共通鍵Ｋが共有されたことになる。また、素数ｑとして１０２４ビット程度の大きな値を用いていることで、第三者が公開データＺ1，Ｚ2から各通信装置Ｐ1，Ｐ2の秘密鍵Ｎ1，Ｎ2を求めることは計算量的に困難となるため、通信装置Ｐ1，Ｐ2間でのみ秘密の共通鍵Ｋを安全に共有することができる。
【０００６】
【数２】
0003838926.tif 000002
【０００７】
ところで、「M.Steiner,G.Tsudik,and M.Waidner,Key agreement in dynamic peer groups,IEEE Transactions on Parallel and Distributed Systems,11(08),August 2000.」には、上記Diffie-Hellmanプロトコルを応用したIKA.1プロトコルが開示されている。このIKA.1プロトコルは、３つ以上の通信装置で暗号通信用の共通鍵を共有することを可能とするものである。
【０００８】
ここで、このIKA.1プロトコルの内容について簡単に説明する。尚、このIKA.1プロトコルにおいても、前述したDiffie-Hellmanプロトコルの場合と同様に、前提条件として、暗号通信用の共通鍵を共有しようとする全ての通信装置が、素数ｑと、この素数ｑを法とするガロア体ＧＦ（ｑ）の原始元αとを共有している。
【０００９】
このプロトコルでは、下記の（ｂ１）〜（ｂ３）の手順に従い、ｎ個の通信装置で暗号通信用の共通鍵を共有する。
（ｂ１）：１〜（ｎ−１）番目の各通信装置Ｐ1〜Ｐn-1において、ｉ番目（ｉ＝１，２，…，ｎ−１）の通信装置Ｐiが、前述したDiffie-Hellmanプロトコルの場合と同様に当該装置Ｐiのみが有する秘密鍵Ｎiを生成し、下記式（８）から公開データＺiを算出して、この算出した公開データＺiを、（ｉ＋１）番目の通信装置Ｐi+1へユニキャストする。
【００１０】
（ｂ２）：ｎ番目の通信装置Ｐnが、当該装置Ｐnのみが有する秘密鍵Ｎnを生成し、下記式（９）から公開データＹiを算出して、この算出した公開データＹiを、他の通信装置Ｐ1〜Ｐn-1へブロードキャストする。
（ｂ３）：ｎ個の各通信装置において、ｉ番目の通信装置Ｐiが、下記式（１０）から共通鍵Ｋを求める。
【００１１】
こうした手順を踏むことにより、ｎ個の通信装置で共通鍵Ｋを共有することができる。
【００１２】
【数３】
0003838926.tif 000003
【００１３】
ここで、このIKA.1プロトコルに従った共通鍵の共有化の具体例として、通信装置の数ｎ＝４の場合について、図５を用いて簡単に説明する。 尚、以下の説明では、各公開データＺi，Ｙi及び共通鍵Ｋについて、上記式（８）〜式（１０）に示すモジュロの記載（「mod q」）を省略している。
【００１４】
図５に示すように、まず、通信装置Ｐ1が、当該装置Ｐ1の秘密鍵Ｎ1を用いて上記式（８）から算出した公開データＺ1（この場合、αN1）を、通信装置Ｐ2へ送信する。次に、通信装置Ｐ2が、通信装置Ｐ1から受信した公開データＺ1と当該装置Ｐ2の秘密鍵Ｎ2とを用いて上記式（８）から算出した公開データＺ2（この場合、αN1，αN2，αN1N2）を、通信装置Ｐ3へ送信する。更に、通信装置Ｐ3が、通信装置Ｐ2から受信した公開データＺ2と当該装置Ｐ3の秘密鍵Ｎ3とを用いて上記式（８）から算出した公開データＺ3（この場合、αN1N2，αN1N3，αN2N3，αN1N2N3）を、通信装置Ｐ4へ送信する。そして最後に、通信装置Ｐ4が、通信装置Ｐ3から受信した公開データＺ3と当該装置Ｐ4の秘密鍵Ｎ4とを用いて上記式（９）から算出した公開データＹ1〜Ｙ4（この場合、それぞれαN2N3N4，αN1N3N4，αN1N2N4，αN1N2N3）を、他の通信装置Ｐ1〜Ｐ3へブロードキャストする。これにより、各通信装置Ｐi（ｉ＝１，２，３，４）は、各自に対応する公開データＹiと、各自の有する秘密鍵Ｎiとを用いて、上記式（１０）から共通鍵Ｋ（この場合、Ｋ＝αN1N2N3N4）を求めることができる。
【００１５】
以上説明したIKA.1プロトコルは、共通鍵を共有するために必要な通信装置全体としての計算量を少なくする効果が高く、しかも、共通鍵Ｋの形により、ＩＫＡプロトコルのみならず、ＡＫＡプロトコルにも適している。
【００１６】
【発明が解決しようとする課題】
しかしながら、上記IKA.1プロトコルでは、共通鍵を共有しようとする各通信装置が順番に公開データの計算を行うようになっているため、全体としての計算時間が長くなってしまうといった問題があった。
【００１７】
即ち、公開データを１つ計算する処理を計算ステップの１単位とし、共通鍵を共有するために必要な全ての公開データを計算するのに要する計算時間を、この計算ステップを用いて表した場合、図５のように、通信装置Ｐ1での計算ステップ数ｔ1＝１、通信装置Ｐ2での計算ステップ数ｔ2＝２、通信装置Ｐ3での計算ステップ数ｔ3＝３、という具合に、計算ステップ数ｔiは通信装置Ｐiの順位ｉに比例した値となる。そして、各通信装置による公開データの計算は並行して行われず、順番に行われるようになっているため、全体として計算ステップ数が大きな値となり、共通鍵を共有するまでの計算時間が長くなってしまうのである。尚、通信グループがｎ個の通信装置からなっている場合、全ての公開データの計算に必要な全計算ステップ数は、「ｎ（ｎ＋１）／２」と表される。
【００１８】
本発明は、こうした問題に鑑みなされたものであり、複数の通信装置で暗号通信用の共通鍵を共有する際に必要な通信装置全体での計算時間を短くすることを目的としている。
【００１９】
【課題を解決するための手段及び発明の効果】
上記目的を達成するためになされた請求項１に記載の鍵共有方法は、複数の通信装置からなる通信グループ内の全通信装置で暗号通信用の共通鍵を共有するためのものであって、下記（ａ１）〜（ａ５）の手順を含むことを特徴としている。
【００２０】
（ａ１）：最初に、通信グループを２つに分けた各サブグループ内の通信装置のうちの１つが、通信グループ内の全通信装置で共有する公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して公開データを生成し、当該装置が属するサブグループ内に、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が存在すれば、その通信装置のうちの１つを送信先としてこの公開データを送信する。
【００２１】
（ａ２）：サブグループ内の通信装置は、他の通信装置から公開データを受信すると、この公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して公開データを生成し、当該装置が属するサブグループ内に、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が存在すれば、その通信装置のうちの１つを送信先としてこの公開データを送信する。
【００２２】
（ａ３）：上記（ａ２）の手順は、生成した公開データの送信先が存在しなくなるまで繰り返される。
（ａ４）：上記（ａ１）又は（ａ２）で、自己が生成した公開データの送信先が存在しない通信装置は、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が通信グループ内に複数存在すれば、それらを２つのグループに分けた各グループを下位サブグループとし、各下位サブグループ内の通信装置のうちの１つを送信先としてこの公開データを送信する。そして、この下位サブグループが上記（ａ２）のサブグループとなり、上記（ａ２）からの手順が行われる。
【００２３】
（ａ５）：上記（ａ１）又は（ａ２）で、自己が生成した公開データの送信先が存在しない通信装置は、この生成した公開データについて未だ秘密鍵を用いた演算処理を施していない通信装置が通信グループ内に複数存在せず１つしか存在しなければ、この存在している通信装置を送信先としてこの公開データを送信する。そして、この公開データを受信した通信装置は、受信した公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施して共通鍵を生成する。
【００２４】
尚、通信装置が公開データに対し当該装置の秘密鍵を用いた演算処理を施して公開データを生成することは、表現を変えれば、通信装置が当該装置の秘密鍵を基に公開データを加工すると言うこともできる。
ここで、このような請求項１の鍵共有方法に従い各通信装置が行う処理の具体例として、通信グループが８個の通信装置Ｐ1〜Ｐ8からなっていると共に、請求項２に記載のように、その８個の通信装置Ｐ1〜Ｐ8で、素数ｑと、この素数ｑを法とするガロア体ＧＦ（ｑ）の原始元αとを公開データとして共有している場合について、図１を用いて説明する。尚、以下の説明では、下記式（１）〜式（３）に示す各公開データＺa，Ｚc及び共通鍵Ｋについて、その各式に示すモジュロの記載（「mod q」）を省略している。
【００２５】
【数４】
0003838926.tif 000004
【００２６】
まず、上記（ａ１）の手順について説明する。尚、ここからの説明は、図１において「第１の段階」として示している部分に関するものである。
上記（ａ１）の手順では、最初に、８個の通信装置Ｐ1〜Ｐ8からなる通信グループが、通信装置Ｐ1〜Ｐ4からなる第１のサブグループと、通信装置Ｐ5〜Ｐ8からなる第２のサブグループとに分かれる。
【００２７】
そして、第１のサブグループ内の通信装置の１つである通信装置Ｐ1が、全通信装置Ｐ1〜Ｐ8で共有している原始元αに対し当該装置Ｐ1のみが有する秘密鍵Ｎ1を用いた演算処理を施して公開データＺa（この場合、αN1）を生成（具体的には、式（１）から算出）する。そして更に、当該装置Ｐ1が属する第１のサブグループ内の通信装置Ｐ1〜Ｐ4のうち、この生成した公開データＺaについて未だ秘密鍵を用いた演算処理を施していない通信装置Ｐ2〜Ｐ4の中の１つである通信装置Ｐ2を送信先として、この公開データＺaを送信する。
【００２８】
一方、第２のサブグループ内の通信装置の１つである通信装置Ｐ5も、同様に、当該装置Ｐ5のみが有する秘密鍵Ｎ5を用いて公開データＺa（この場合、αN5）を生成し、通信装置Ｐ6を送信先としてこの公開データＺaを送信する。
次に、上記（ａ２）の手順について説明する。尚、以下の説明では、第１のサブグループについてのみ説明するが、第２のサブグループにおいても同様のことが行われる。
【００２９】
上記（ａ２）の手順では、第１のサブグループにおいて、通信装置Ｐ2が、通信装置Ｐ1から公開データＺbを受信すると、この公開データＺbに対し当該装置Ｐ2のみが有する秘密鍵Ｎ2を用いた演算処理を施して公開データＺc（この場合、αN1N2）を生成（具体的には、式（２）から算出）する。尚、この場合の公開データＺbは、上記（ａ１）の手順で通信装置Ｐ1が生成した公開データＺaである。
【００３０】
そして更に、通信装置Ｐ2が、第１のサブグループ内の通信装置Ｐ1〜Ｐ4のうち、この生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していない通信装置Ｐ3，Ｐ4のうちの１つである通信装置Ｐ3を送信先として、この公開データＺcを送信する。
【００３１】
次に、上記（ａ３）の手順について説明する。
上記（ａ３）の手順では、上記（ａ２）の手順が、生成した公開データの送信先が存在しなくなるまで繰り返される。
即ち、第１のサブグループにおいて、通信装置Ｐ3が、通信装置Ｐ2から公開データＺbを受信すると、この公開データＺbに対し当該装置Ｐ3のみが有する秘密鍵Ｎ3を用いた演算処理を施して公開データＺc（この場合、αN1N2N3）を式（２）から算出する。尚、この場合の公開データＺbは、上記（ａ２）の手順で通信装置Ｐ2が生成した公開データＺcであり、上記（ａ２）の手順で通信装置Ｐ2が受信した公開データＺbではない。つまり、式（２）では、受信される公開データを単にＺbと表し、送信する公開データを単にＺcと表している。このことは、以下の説明においても同様である。
【００３２】
そして更に、通信装置Ｐ3が、第１のサブグループ内の通信装置Ｐ1〜Ｐ4のうち、この生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していない唯一の通信装置Ｐ4を送信先として、この公開データＺcを送信する。
そして、通信装置Ｐ4が、通信装置Ｐ3から公開データＺbを受信すると、この公開データＺbに対し当該装置Ｐ4のみが有する秘密鍵Ｎ2を用いた演算処理を施して公開データＺc（この場合、αN1N2…N4）を式（２）から算出する。
【００３３】
つまり、上記（ａ３）の手順では、サブグループ内の全ての通信装置が公開データに対し秘密鍵を用いた演算処理を施すまで、上記（ａ２）の手順が繰り返されるようになっている。
次に、上記（ａ４）の手順について説明する。尚、ここからの説明は、図１において「第２の段階」として示している部分に関するものである。
【００３４】
上記（ａ４）の手順では、通信グループ内の通信装置Ｐ1〜Ｐ8のうち、通信装置Ｐ4の生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していない通信装置（即ち、第２のサブグループ内の通信装置）Ｐ5〜Ｐ8が、通信装置Ｐ5，Ｐ6からなる第１の下位サブグループと、通信装置Ｐ7，Ｐ8からなる第２の下位サブグループとに分かれる。そして、通信装置Ｐ4が、各下位サブグループ内の通信装置のうちの１つである通信装置Ｐ5，Ｐ7を送信先として、当該装置Ｐ4が生成した公開データＺcを送信する。そして、この第１の下位サブグループが上記（ａ２）の第１のサブグループとなり、この第２の下位サブグループが上記（ａ２）の第２のサブグループとなって、上記（ａ２）からの手順が以下のように行われる。尚、以下の説明では、第１のサブグループについてのみ説明するが、第２のサブグループにおいても同様のことが行われる。
【００３５】
第１のサブグループの通信装置Ｐ5が、通信装置Ｐ4から公開データＺbを受信すると、公開データＺc（この場合、αN1N2…N5）を式（２）から算出する。そして、通信装置Ｐ5が、第１のサブグループ内の通信装置Ｐ5，Ｐ6のうち、この生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していない唯一の通信装置Ｐ6を送信先として、この公開データＺcを送信する。そして更に、通信装置Ｐ6が、通信装置Ｐ5から公開データＺbを受信すると、公開データＺc（この場合、αN1N2…N6）を式（２）から算出する。
【００３６】
そして、ここからの説明は、図１において「第３の段階」として示している部分に関するもので、通信グループ内の通信装置Ｐ1〜Ｐ8のうち、通信装置Ｐ6の生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していない通信装置（即ち、第２のサブグループ内の通信装置）Ｐ7，Ｐ8が、通信装置Ｐ7のみからなる第１の下位サブグループと、通信装置Ｐ8のみからなる第２の下位サブグループとに分かれる。そして、通信装置Ｐ6が、各下位サブグループの通信装置Ｐ7，Ｐ8を送信先として、当該装置Ｐ6が生成した公開データＺcを送信する。そして、この第１の下位サブグループが上記（ａ２）の第１のサブグループとなり、この第２の下位サブグループが上記（ａ２）の第２のサブグループとなって、上記（ａ２）からの手順が更に行われる。尚、以下の説明では、第１のサブグループについてのみ説明するが、第２のサブグループにおいても同様のことが行われる。
【００３７】
即ち、第１のサブグループの通信装置Ｐ7が、通信装置Ｐ6から公開データＺbを受信すると、公開データＺc（この場合、αN1N2…N7）を式（２）から算出する。これにより、通信グループ内の通信装置Ｐ1〜Ｐ8のうち、通信装置Ｐ7の生成した公開データＺcについて未だ秘密鍵を用いた演算処理を施していないのは通信装置Ｐ8のみとなる。
【００３８】
次に、上記（ａ５）の手順について説明する。尚、ここからの説明は、図１において「第４の段階」として示している部分に関するものである。
上記（ａ５）の手順では、通信装置Ｐ7が、通信装置Ｐ8を送信先として、当該装置Ｐ7の生成した公開データＺcを送信する。そして、公開データＺd（この場合、通信装置Ｐ7の生成した公開データＺc）を受信した通信装置Ｐ8が、この公開データＺdに対し当該装置Ｐ8のみが有する秘密鍵Ｎ8を用いた演算処理を施して共通鍵Ｋ（この場合、αN1N2…N8）を生成（具体的には、式（３）から算出）する。
【００３９】
このような請求項１の鍵共有方法によれば、複数の通信装置で共通鍵を共有する際に必要な通信装置全体での計算時間を短くすることができる。つまり、従来技術として示したIKA.1プロトコルでは、共通鍵を共有しようとする各通信装置が順番に公開データの計算を行うようになっているため、共通鍵が生成されるまでに必要な計算ステップ数が多くなってしまうが、請求項１の鍵共有方法では、複数の通信装置が並行して演算処理を行うようになっているため、計算ステップ数を少なくすることができるのである。
【００４０】
また、１つの公開データが２つのグループに分配されて利用されるようになっているため、通信装置全体としての計算量についても少なくすることができる。
また更に、公開データのブロードキャストを行う必要が無いため、ブロードキャストを行う機能を有していない通信装置であっても実施することができる。
【００４１】
加えて、共通鍵の形がIKA.1プロトコルと同じであるため、ＡＫＡにも適している。
尚、図１では、通信グループが８個の通信装置からなっている場合について説明したが、通信装置の数はこれに限らず、いくつであってもよい。ここで、通信グループを構成する通信装置の数ｎが２kの形で表せるものであれば、図１のように２つのグループを常に均等に分けていくことができるが、通信装置の数ｎが２kの形で表せない場合にも、「２k-1＜ｎ＜２k」の条件を満たすｋを用い、ｎ＝２kと仮定して図１のように表し、実際には存在しない通信装置については公開データを素通りさせる（言い換えれば、存在しない通信装置の秘密鍵を１とする）ようにすればよい。具体的に説明すると、通信グループが５個の通信装置からなっている場合には、「２k-1＜５＜２k」の条件を満たすｋ＝３であるため、図１のように８個の通信装置を仮定し、３つの通信装置（例えば、通信装置Ｐ6〜Ｐ8）については存在しないものとして、その部分は公開データを素通りさせるようにすれば、通信装置の数ｎがいくつであっても対応することができる。
【００４２】
そして特に、請求項３に記載のように、上記（ａ１）の手順で、２つのサブグループが、各サブグループ内の通信装置の数が同じ又は１つ違いとなるように分けられ、上記（ａ４）の手順で、２つの下位サブグループが、各下位サブグループ内の通信装置の数が同じ又は１つ違いとなるように分けられるようになっていることが好ましい。このように２つのグループ内の装置の数ができるだけ均等になるような条件で分けられるようになっていれば、計算ステップ数を最小限に抑えることができるからである。具体的に説明すると、前述したように通信グループが５個の通信装置からなっている場合には、例えば、図１において通信装置Ｐ4，Ｐ6，Ｐ7が存在しないものとすれば、この条件を満たし、通信装置の数に対する計算ステップを最小限に抑えることができる。
【００４３】
また、請求項３の鍵共有方法では、通信グループがｎ個の通信装置からなっている場合、公開データを生成する段階（図１に示した例では、「第１の段階」から「第３の段階」まで）の数は、「Ａ≧ｌｏｇ2ｎ」を満たす最小の整数Ａと表される。したがって、計算ステップと同様に公開データを１つ計算する処理を１単位とした場合、１つの通信装置で公開データを生成するために行われる最大計算量も上記整数Ａと表される。一方、前述したIKA.1プロトコルでは、ｉ番目の通信装置が行う公開データの計算量は「ｉ」であることから、通信グループがｎ個の通信装置からなっている場合、１つの通信装置で行われる最大計算量は「ｎ」と表される。つまり、請求項３の鍵共有方法では、IKA.1プロトコルに比べ、各通信装置に要求される計算量の上限についても小さくすることができる。また、通信グループ内の全通信装置で公開データを生成するために行う計算量は「ｎＡ」と表され、全体としての計算量を小さくすることができるという点でも優れている。
【００４４】
また更に、請求項４に記載のように、通信グループが２k個の通信装置からなっていれば、２つのサブグループ又は２つの下位サブグループについて、各グループ内の通信装置の数が常に同数となるように分けることができるため、各通信装置での計算量を均等にすることができる。即ち、従来技術として示したIKA.1プロトコルでは、公開データを受ける順番が遅い通信装置ほど計算量が多くなり、各通信装置での計算量が大きく偏ってしまうといった欠点があるが、請求項４の鍵共有方法では、各通信装置が共通鍵を生成するまでの各段階（図１に示した例では、「第１の段階」から「第４の段階」までの各段階）において、通信グループ内の全通信装置がそれぞれ１回ずつ演算処理を行うこととなり、各通信装置での計算量が偏らないからである。尚、通信グループが２k個の通信装置からなっていなくても、上記請求項３の方法によれば、IKA.1プロトコルに比べ、各通信装置での計算量の偏りを格段に小さくできることは言うまでもない。
【００４５】
そして、請求項４の鍵共有方法では、通信グループがｎ＝２k個の通信装置からなっている場合、公開データを生成する段階の数は、「ｌｏｇ2ｎ」と表される。したがって、通信グループ内の全通信装置で公開データを生成するために行う計算量は、「ｎｌｏｇ2ｎ」と表される。一方、前述したIKA.1プロトコルに従い通信グループ内の全通信装置で公開データを生成するために行う計算量は、全計算ステップ数と同様に「ｎ（ｎ＋１）／２」と表される。つまり、請求項４の鍵共有方法では、IKA.1プロトコルに比べ、全体のべき乗計算量のオーダが「Ｏ（ｎ2）→Ｏ（ｎｌｏｇ2ｎ）」に減少している。
【００４６】
また、請求項４の鍵共有方法では、通信グループを構成する通信装置の数ｎに対し、全ての公開データの計算に必要な全計算ステップ数は「ｔ＝ｎ−１」と表される。そして、この値は、前述したIKA.1プロトコルでの全計算ステップ数「ｎ（ｎ＋１）／２」に比べ、オーダが「Ｏ（ｎ2）→Ｏ（ｎ）」に減少しており、格段に小さい値であることが分かる。
【００４７】
次に、請求項５に記載の通信装置は、上記請求項１〜４の何れかの鍵共有方法により互いに暗号通信用の共通鍵を共有するものである。そして、本装置では、この鍵共有方法に基づき、演算処理手段が、公開データに対し当該装置のみが有する秘密鍵を用いた演算処理を施し、送受信手段が、他の通信装置との間で公開データの送受信を行う。このため、本装置を用いれば、当該装置と同様の機能を有する装置との間で、上記請求項１〜４の鍵共有方法を実施して共通鍵を共有することができる。
【００４８】
【発明の実施の形態】
以下、本発明が適用された実施形態の通信装置としての携帯電話装置について、図面を用いて説明する。
まず図２は、本実施形態の携帯電話装置１０の構成を表すブロック図である。
【００４９】
この携帯電話装置１０は、送受信部１２、ＣＰＵ１４、ＲＡＭ１６、ＲＯＭ１８及びデータの書き換えが可能な不揮発性メモリ２０を備えている。
送受信部１２は、他の携帯電話装置とデータを送受信するための無線通信を行う。
【００５０】
また、不揮発性メモリ２０には、複数の携帯電話装置で共通鍵を共有する鍵共有処理をＣＰＵ１４に行わせるためのプログラムが記憶されている。また、この鍵共有処理に用いられるパラメータとして、１０２４ビットの素数ｑと、この素数ｑを法とするガロア体ＧＦ（ｑ）の原始元αとが記憶されており、これらのデータは、共通鍵を共有しようとする全ての携帯電話装置で予め共有されている。尚、これらのデータは、第三者に公開しても何ら支障がないため、通信により共有するようにしてもよい。
【００５１】
ここで、上記プログラムに従いＣＰＵ１４が行う鍵共有処理について、図３のフローチャートを用いて説明する。尚、本鍵共有処理は、他の携帯電話装置との間で共通鍵の共有を行う旨の合意がされた場合に開始される。
この鍵共有処理が開始されると、まず、Ｓ１００にて、共通鍵を共有しようとする携帯電話装置の台数ｎと、そのｎ台の携帯電話装置からなる通信グループ内における当該装置１０の順位ｉ（ｉ＝１，２，…，ｎ）とを、送受信部１２を介して取得する。尚、この順位ｉは、通信グループ内で単に各携帯電話装置を識別するためのものであり、例えば、通信グループ内の携帯電話装置のうちの一つにより、他の全ての携帯電話装置に一括して付与されるようにすればよい。
【００５２】
そして、Ｓ１１０では、当該装置１０のみが有する非公開の秘密鍵Ｎiを生成する。具体的には、素数ｑの範囲内で乱数を発生させ、この値を秘密鍵Ｎiとして、不揮発性メモリ２０に記憶させる。
次に、Ｓ１２０では、Ｓ１００にて取得した台数ｎに基づきマップを作成する。ここで作成するマップは、前述した（ａ１）〜（ａ５）の手順に従う鍵共有方法で暗号通信用の共通鍵を共有する際に、通信グループ内の各携帯電話装置が行うべき処理の順序を表すものであり、例えば、通信グループ内の携帯電話装置の台数ｎ＝８の場合には、図１に示す内容のマップを作成する。尚、上記（ａ１）〜（ａ５）の手順に従い暗号通信用の共通鍵を共有するために通信グループ内の各携帯電話装置が行うべき処理の具体的な内容については、図１を用いて既に説明しているので、ここでは省略する。
【００５３】
また、本実施形態では、作成するマップの内容（言い換えれば、各携帯電話装置が行うべき処理の順序）が、通信グループを構成する携帯電話装置の台数ｎに対して一義的に決まるようにするため、上記（ａ１）〜（ａ５）の手順について、更に、下記の（ｃ１）〜（ｃ４）のような規則を定めている。
【００５４】
（ｃ１）：複数の携帯電話装置を２つのグループ（サブグループ又は下位サブグループ）に分ける場合には、順位ｉの値が小さい第１グループと、順位ｉの値が大きい第２グループとに分ける。
（ｃ２）：上記（ｃ１）において、２つのグループに分ける対象の複数の携帯電話装置の台数が偶数であれば、各グループ内の携帯電話装置の台数が同数となるように分ける。
【００５５】
（ｃ３）：上記（ｃ１）において、２つのグループに分ける対象の複数の携帯電話装置の台数が奇数であれば、第１グループ内の携帯電話装置の台数が、第２グループ内の携帯電話装置の台数よりも１台多くなるように分ける。
（ｃ４）：任意に選択可能な複数の携帯電話装置が存在するときは、順位ｉの値が最も小さいものを選択する。尚、ここでいう任意に選択可能な複数の携帯電話装置とは、例えば、上記（ａ１）の手順に関して言えば、公開データを生成する通信装置や、公開データの送信先となる通信装置のことである。
【００５６】
こうした規則に従うことで、携帯電話装置の台数ｎに対して各携帯電話装置が行うべき処理の順序が一義的に決まるため、通信グループ内の全ての携帯電話装置で同一内容のマップが作成されることとなる。尚、通信グループを構成する携帯電話装置の台数ｎ＝８の場合に、この規則に従い作成されたマップが、図１に示す内容となる。
【００５７】
こうして、Ｓ１２０の処理が行われた後は、Ｓ１３０へ移行し、Ｓ１２０で作成したマップに基づき、当該装置が一番最初に公開データを生成する装置（図１におけるＰ1又はＰ5に当たる装置）に該当しているか否かを判定する。
このＳ１３０で、当該装置が一番最初に公開データを生成する装置に該当していると判定した場合には、Ｓ１４０へ移行し、不揮発性メモリ２０に記憶されている原始元αに対し当該装置の秘密鍵Ｎiを用いた演算処理を施して公開データＺaを生成（具体的には、上記式（１）から算出）する。そして更に、Ｓ１５０へ移行して、マップに基づき送信先と判断した携帯電話装置へ、Ｓ１４０にて生成した公開データを送受信部１２を介して送信した後、Ｓ１６０へ移行する。
【００５８】
一方、Ｓ１３０で、当該装置が一番最初に公開データを生成する装置に該当していないと判定した場合には、Ｓ１４０及びＳ１５０の処理を行わずに、Ｓ１６０へ移行する。
Ｓ１６０では、送受信部１２により公開データが受信されたか否かを判定する。尚、この判定処理は、公開データが受信されたと判定するまで繰り返される。
【００５９】
そして、Ｓ１６０で、公開データが受信されたと判定すると、Ｓ１７０へ移行し、受信された公開データが、当該装置以外の全ての携帯電話装置により演算処理が行われた最終的なデータ（図１における第４段階で受信するデータ）であるか否かをマップに基づき判定する。尚、この場合には、受信された公開データがマップ上のどの部分の処理に関するものかを判断する必要があるが、このための方法としては、例えば、送信する公開データに識別データを付すようにしてもよく、また、各携帯電話装置で公開データを送信するタイミングを予め決めておき、そのタイミングに基づき判断するようにしてもよい。
【００６０】
このＳ１７０で、受信された公開データが最終的なデータではないと判定した場合には、Ｓ１８０へ移行し、受信された公開データＺbに対し当該装置の秘密鍵Ｎiを用いた演算処理を施して公開データＺcを生成（具体的には、上記式（２）から算出）する。そして更に、Ｓ１９０へ移行して、マップに基づき送信先と判断した携帯電話装置へ、Ｓ１８０にて生成した公開データを送受信部１２を介して送信した後、Ｓ１６０へ移行する。
【００６１】
一方、Ｓ１７０で、受信された公開データが最終的なデータであると判定した場合には、Ｓ２００へ移行し、受信された公開データＺdに対し当該装置の秘密鍵Ｎiを用いた演算処理を施して共通鍵Ｋを生成（具体的には、上記式（３）から算出）した後、本鍵共有処理を終了する。
【００６２】
次に、通信グループ内を構成する携帯電話装置の台数が８台の場合の本携帯電話装置１０の動作例について、図１を用いて説明する。
本携帯電話装置１０は、他の携帯電話装置との間で共通鍵の共有を行う旨の合意をすると、共通鍵を共有しようとする全ての携帯電話装置の台数（８台）と、その８台の携帯電話装置からなる通信グループ内における当該装置１０の順位ｉ（この例では、ｉ＝１）とを取得する（Ｓ１００）。そして、当該装置１０（この場合、携帯電話装置Ｐ1）のみが有する非公開の秘密鍵Ｎ1を生成する（Ｓ１１０）。また、この台数に基づき図１に示す内容のマップを作成し（Ｓ１２０）、このマップに基づき、当該装置Ｐ1が一番最初に公開データを生成する装置に該当していると判定する（Ｓ１３０：ＹＥＳ）。
【００６３】
そして、本携帯電話装置Ｐ1は、「第１の段階」で行う処理として、記憶している原始元αに対し当該装置Ｐ1の秘密鍵Ｎ1を用いた演算処理を施して公開データを生成し（Ｓ１４０）、この生成した公開データを、マップに基づき送信先と判断した携帯電話装置Ｐ2へ送信する（Ｓ１５０）。その後、公開データを受信するまで待機する（Ｓ１６０：ＮＯ）。
【００６４】
「第２の段階」へ移行すると、当該装置Ｐ1へ携帯電話装置Ｐ8から公開データが送信されてくる。この公開データを本携帯電話装置Ｐ1が受信すると（Ｓ１６０：ＹＥＳ）、マップに基づき、受信した公開データが最終的なデータではないと判定する（Ｓ１７０：ＮＯ）。このため、受信した公開データに対し当該装置Ｐ1の秘密鍵Ｎ1を用いた演算処理を施して公開データを生成し（Ｓ１８０）、この生成した公開データを、マップに基づき送信先と判断した携帯電話装置Ｐ2へ送信する（Ｓ１９０）。その後、公開データを受信するまで待機する（Ｓ１６０：ＮＯ）。
【００６５】
「第３の段階」へ移行すると、当該装置Ｐ1へ携帯電話装置Ｐ4から公開データが送信されてくる。この公開データを本携帯電話装置Ｐ1が受信すると（Ｓ１６０：ＹＥＳ）、マップに基づき、受信した公開データが最終的なデータではないと判定する（Ｓ１７０：ＮＯ）。このため、「第２の段階」と同様に、公開データを生成し（Ｓ１８０）、この公開データを、マップに基づき送信先と判断した携帯電話装置Ｐ2へ送信した後（Ｓ１９０）、公開データを受信するまで待機する（Ｓ１６０：ＮＯ）。
【００６６】
「第４の段階」へ移行すると、当該装置Ｐ1へ携帯電話装置Ｐ2から公開データが送信されてくる。この公開データを本携帯電話装置Ｐ1が受信すると（Ｓ１６０：ＹＥＳ）、マップに基づき、受信した公開データが最終的なデータであると判定する（Ｓ１７０：ＹＥＳ）。このため、受信した公開データに対し当該装置Ｐ1の秘密鍵Ｎ1を用いた演算処理を施して共通鍵を生成する（Ｓ２００）。
【００６７】
このような処理を、通信グループ内の全ての携帯電話装置がそれぞれ実行することで、通信グループ内の全ての携帯電話装置で共通鍵が共有される。
尚、本実施形態の携帯電話装置１０では、図３におけるＳ１４０，Ｓ１８０，Ｓ２００の処理が、演算処理手段に相当し、送受信部１２と、図３におけるＳ１５０，Ｓ１６０，Ｓ１９０の処理とが、送受信手段に相当している。
【００６８】
このような本実施形態の携帯電話装置１０により実施される共通鍵共有方法によれば、複数の携帯電話装置が並行して演算処理を同時進行するため、共通鍵を共有するために必要な計算ステップ数を少なくして、計算時間を短くすることができる。また、携帯電話装置全体としての計算量についても少なくすることができる。
【００６９】
更に、複数の携帯電話装置を２つのグループに分ける場合に、各グループ内の携帯電話装置の台数ができるだけ均等となるように分けるようになっているため、計算ステップ数及び計算量を最小限に抑えることができる。また、各携帯電話装置での計算量の偏りを小さくすることができる。そして特に、通信グループが２k台の携帯電話装置からなっていれば、各携帯電話装置での計算量を均等にすることができる。
【００７０】
また更に、公開データのブロードキャストを行う必要が無いため、ブロードキャストを行うことができない通信形態（例えば、電話回線による通信）にも適用することができる。
加えて、共通鍵の形がIKA.1プロトコルと同じであるため、ＡＫＡにも適している。
【００７１】
以上、本発明の一実施形態について説明したが、本発明は、種々の形態を採り得ることは言うまでもない。例えば、上記実施形態では、通信装置として携帯電話装置を例に挙げて説明したが、これ以外の通信装置であってもよい。
【図面の簡単な説明】
【図１】  本発明の鍵共有方法を説明するための説明図である。
【図２】  実施形態の携帯電話装置の構成を表すブロック図である。
【図３】  鍵共有処理を表すフローチャートである。
【図４】  Diffie-Hellmanプロトコルの内容を説明するための説明図である。
【図５】  IKA.1プロトコルの内容を説明するための説明図である。
【符号の説明】
１０…携帯電話装置、１２…送受信部、１４…ＣＰＵ、１６…ＲＡＭ、１８…ＲＯＭ、２０…不揮発性メモリ
【図１】
0003838926.tif 000006
【図２】
0003838926.tif 000007
【図３】
0003838926.tif 000008
【図４】
0003838926.tif 000009
【図５】
0003838926.tif 000010