(57)【要約】【課題】グループ全員の端末識別子を知らない場合でも安全にグループ内共通鍵を生成と共有する。【解決手段】通信に使用する端末識別子と異なる端末識別子のアドレス帳を保持する端末から構成され、上記アドレス帳に互いの端末識別子が登録されている端末間は事前通信なしに暗号化通信が可能なネットワークにおいて、上記アドレス帳を使用し暗号化通信が可能な端末間を把握し、木構造で表したグループ内の暗号化通信経路を用いてグループ内共通鍵の生成、配布を行う。また暗号化通信が可能な端末間を信頼できるとし、ルーティングテーブルに信頼性を反映する。全員の端末識別子を知らない場合でも、グループ内共通鍵の生成と共有が可能となる。また、暗号化通信が可能なルートを選択することでより信頼性の高いルーティングが可能となる。【選択図】  図1
2005223773.tif 000002
【特許請求の範囲】
【請求項１】
複数の端末から構成され、前記複数の端末間で生成した共通鍵を用いて暗号化通信を行うネットワークにおいて、
いずれか二つの前記端末は、
他方の前記端末と知り合い関係であるか否かを判定するための、判定用端末識別子を記録するアドレス帳を保持し、
前記他方の端末と前記判定用識別子を送受し、
前記アドレス帳に互いの前記判定用端末識別子が登録されている場合には、他方の前記端末と知り合い関係であると判断し、
鍵情報の配信なしに共通鍵の生成と共有を行う、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項２】
請求項１に記載のグループ内共通鍵の生成と共有方法において、
いずれか二つの前記端末は、自端末識別子をハッシュ関数にかけたハッシュ値を前記判定用端末識別子として他方の前記端末に送信し、
他方の前記端末から送信されたハッシュ値を受け取った前記他の端末は、アドレス帳に登録されている端末識別子をハッシュ関数にかけ、
受信した前記ハッシュ値と同じ値が存在するかを確認することで前記知り合い関係であるかを判定する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項３】
請求項２に記載のグループ内共通鍵の生成と共有方法において、
前記各端末は、前記知り合い関係に基づき、暗号化通信可能な端末を示す自端末の知り合い関係表を生成し、
前記自端末の知り合い関係表を前記ネットワークに接続されている他の前記端末に送信し、
前記端末は、他の前記端末からそれぞれの端末の、自端末の知り合い関係表を受信し、
ネットワーク上の暗号化通信が可能な端末間関係を示すネットワーク上の知り合い関係表を生成する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項４】
請求項３に記載のグループ内共通鍵の生成と共有方法において、
前記グループを生成する際に、前記ネットワーク上の知り合い関係表を使用して、
グループのリーダとなる前記端末が、当該リーダとなる端末を頂点とし、親ノードとなる前記端末と子ノードとなる前記端末は前記暗号化通信が可能であるように前記グループを構成する前記端末を木構造のノードに設定する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項５】
請求項４に記載のグループ内共通鍵の生成と共有方法において、
前記各端末は、当該グループ内で用いる共通鍵を生成する際に、乱数を発生し、
前記木構造にもとづいて前記子ノードとなる前記端末から前記親ノードとなる前記端末への前記乱数の送信を繰り返し、
前記グループを構成する全ての前記端末の乱数を受信した前記リーダとなる端末は、グループ内共通鍵を生成し、
前記リーダとなる前記端末から順に、生成した前記グループ内共通鍵を前記木構造にもとづいて前記親ノードとなる前記端末から前記子ノードとなる前記端末へ配布する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項６】
請求項４に記載したグループ内共通鍵の生成と共有方法において、
前記各端末は、前記グループ内共通鍵を生成する際に、乱数を発生し、
前記木構造にもとづいて前記子ノードとなる前記端末から前記親ノードとなる前記端末へ前記乱数の送信を繰り返し、
前記グループを構成する全ての前記端末の乱数を受信した前記リーダとなる前記端末から順に、収集した前記乱数を前記木構造にもとづいて前記親ノードとなる前記端末から前記子ノードとなる前記端末へ配布し、
前記乱数を受信した前記各端末は前記グループの前記全端末共通の共通鍵生成関数を使用して前記グループ内共通鍵を生成する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項７】
請求項５に記載したグループ内共通鍵の生成と共有方法において、
前記リーダとなる前記端末から順に、生成した前記グループ内共通鍵を前記受信した乱数とともに、前記木構造にもとづいて、前記親ノードとなる前記端末から前記子ノードとなる前記端末へ配布し、
前記各端末は、
配布された前記乱数から前記グループ内共通鍵を生成し、
配布された前記グループ内共通鍵と比較することで配布されたグループ内共通鍵の正当性を検証する、
ことを特徴とするグループ内共通鍵の生成と共有方法。
【請求項８】
グループを構成する複数の端末から構成され、前記複数の端末間で生成した共通鍵を用いて暗号化通信を行うネットワークにおいて、
いずれかの前記端末は、宛先となる前記端末へのルートが複数存在する場合、
請求項１に記載の前記自端末の知り合い関係表を用いて、暗号化通信可能な端末間を把握し、
暗号化通信可能なルートを優先的に選択する、
ことを特徴とするルーティング方法。
【請求項９】
グループを構成する複数の端末から構成され、前記複数の端末間で生成した共通鍵を用いて暗号化通信を行うネットワークにおいて用いる、暗号化通信を行う端末であって、
他の前記端末と知り合い関係であるか否かを判定するための、判定用端末識別子を記録するアドレス帳を保持する手段と、
前記他方の端末と前記判定用識別子を送受する手段と、
前記アドレス帳に互いの前記判定用端末識別子が登録されている場合には、暗号化通信が可能と判断し、鍵情報の配信なしに共通鍵を生成と共有する手段と、を備える、
ことを特徴とする暗号化通信を行う端末。
【請求項１０】
請求項９に記載の暗号化通信を行う端末において、
自端末識別子をハッシュ関数にかけたハッシュ値を他方の前記端末に送信する手段と、
他の前記端末から送信されたハッシュ値を受け取る手段と、
前記アドレス帳に登録されている端末識別子をハッシュ関数にかけ、受信した前記ハッシュ値と同じ値が存在するかを確認することで前記暗号化通信が可能かを判定する手段と、を備える、
ことを特徴とする暗号化通信を行う端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に存在する端末の中で、特定のグループメンバによる暗号化通信を行うためのグループ内共通鍵の生成・共有方法と、宛先までのルートが複数存在する場合に信頼性の高いルートを選択するためのルーティング方法に関する。
【背景技術】
【０００２】
ノートパソコンや携帯電話など携帯可能な情報端末の普及により、その場に集まった人達の間で安全な通信を実現したいというニーズが増えると考えられる。例えば会議の場において、出席者間での資料などは会議出席者以外には秘匿したいと考えられる。また、例えば、グループ旅行中に携帯電話に搭載されているカメラで撮影した画像をその場で参加者全員に配布する場合には、プライバシー保護などの観点から部外者による盗聴を防止したいと考えられる。
【０００３】
上記のように通信内容を保護するためには通信内容の暗号化が行われる。暗号化には、共通鍵暗号方式の場合、あらかじめデータの送受信者が同じ共通鍵を保持する必要があるが、上述のようにその場で集まったメンバ間では、あらかじめ全員が鍵を共有しているとは限らないため、安全に鍵共有を実現する方法が必要である。
【０００４】
複数台の端末による暗号化通信を行う場合の共通鍵を共有する方法には、端末の固有情報をもとにした事前通信不要の共通鍵生成方法がある(例えば、特許文献1参照)。
【０００５】
また、鍵を共有していない端末間で暗号化通信を行う場合に、それぞれの端末と鍵を共有している端末に鍵を共有していない端末間の鍵を生成してもらい、それぞれ暗号化通信により生成した鍵を配布してもらう鍵交換方法がある(例えば、特許文献2参照)。
【０００６】
通常のルーティング制御方式では、距離などのコストが最小であることに重点を置いているため、データを盗聴される可能性がある。これに対し、コストは高くなる可能性があるが、最も安全なルートを選択するルーティング制御方法がある(例えば、特許文献3参照)。
【０００７】
【特許文献１】特開平9-181716号公報(請求項3、図4)
【０００８】
【特許文献２】特開2002-271309号公報(請求項1、図3)
【特許文献３】特開平5-153166号公報(請求項1、図1)
【発明の開示】
【発明が解決しようとする課題】
【０００９】
特許文献1の共通鍵生成方法を用いて、複数台からなるネットワークにおいて暗号化通信を行う場合に、あらかじめ各端末が固有情報を記載したリストを保持し、暗号化通信を行いたい端末の固有情報をもとに各端末が共通鍵を生成する。このため、暗号化通信を行うメンバ全員のメンバ名とアドレスをあらかじめ各自が知っておく必要がある。しかしながら、上記背景技術にて挙げた会議の場での例を考えた場合、各出席者が出席者全員の固有情報(例えばIPアドレスやメールアドレスなど)を知らない場合は容易に考えられる。
【００１０】
特許文献2の鍵共有方法を用いて、3台の端末A、B、Cが存在し、たとえば、端末Cは端末A、Bの2台と鍵共有しているが、端末A、Bの間では鍵を共有していない場合を考える。鍵を共有していない端末A、B間が暗号化通信を行う場合には、それぞれ鍵を共通している端末Cを利用する。端末Cは端末AB間の鍵ABを端末AC間の鍵ACで暗号化して端末Aに送信し、同様にして鍵ABを端末BC間の鍵BCで暗号化して端末Bに送信する。
【００１１】
したがって、4台以上の端末から構成される場合は自分以外の全端末との鍵をあらかじめ共有している端末が存在するか、上記方法を繰り返す必要がある。例えば、端末A、B、C、DにおいてAB間、BC間、CD間のみ鍵が共有されている場合にAD間で暗号化通信を行うためには、まず端末Bを使ってAC間の鍵共有を行い、その後に端末CをAD間の鍵共有を使って行う。上記会議場での例を考えると、全員の固有情報を知っている者が存在しない場合は容易に考えられる。また、特許文献2の鍵共有方法を繰り返す場合は、鍵を共有している端末同士、共有していない端末同士を把握する方法が問題となる。
【００１２】
また、特許文献3のルーティング制御方法では、各端末は自端末に接続された端末との安全性を他の端末に通知し、自端末は通知された各端末間の安全性情報にもとづいて最も安全なルートを選択する。この際に、ルーティングをするために自端末に接続されたリンクの安全度情報を他の端末に送信する必要がある上、安全度を測定する基準をあらかじめ決定しておく必要がある。
【課題を解決するための手段】
【００１３】
本発明は、上記課題を解決するために、暗号化通信を行いたいメンバ全員の固有情報を知らない場合でも、グループ内の共通鍵を生成し共有する技術を提供する。
【００１４】
本発明は、また、宛先端末までのルートが複数存在する場合に、できるだけ簡単な手順で信頼度の高いルートを選択する技術を提供する。
【００１５】
具体的な本発明の共通鍵生成方法は、特定のグループメンバによる暗号化通信を行う場合のグループ内共通鍵の生成方法方法であって、各端末は、通信に使用する端末識別子とは異なる、他の端末と知り合い関係であるか否かを判定するための、判定用端末識別子を記録したアドレス帳を保持し、互いの端末識別子がアドレス帳に登録されている端末間は事前通信を行うことなく、各端末が端末識別子にもとづいて端末間共通鍵を生成する。
【００１６】
以後、ネットワーク上で事前に鍵情報を配信する必要なく、暗号化通信が可能な端末間の関係を知り合い関係であると呼び、知り合い関係にある端末を記載した表を知り合い関係表と呼ぶ。
【００１７】
ネットワーク上のグループは、まず、知り合い関係にある端末を把握し、知り合い関係表を生成する。グループメンバのリーダを決定し、リーダとメンバ全員との通信を行う場合に、知り合い関係表にもとづいて、知り合い関係にある端末間のみを経由するリーダからメンバ全員への木構造のルートを作成し、作成した木構造のルートに従ってグループ内共通鍵の配信を行う。また、グループ内共通鍵を配信するとともに共通鍵生成に利用したデータを配信することでグループメンバ全員が配布された共通鍵の正当性を検証する。
【００１８】
以上の方法により、グループ内において、全員が互いの判定用端末識別子を知らない場合でも、端末識別子を知らないメンバに対して、判定用端末識別子を教えることなくグループ内共通鍵を生成することが可能となる。
【００１９】
さらに、宛先までの全ルートを各端末が把握し、本発明のグループ内共通鍵の生成機能を備えた端末からなるネットワークにおける端末間のルーティング方法として、上記知り合い関係表を用いて知り合い関係である端末間は信頼性が高いと判断し、より信頼性の高いルートを選択する。
【発明の効果】
【００２０】
本発明により、グループ内のメンバ全員の端末識別子を知らない場合においても、端末識別子を教える必要なく、グループ内共通鍵を生成し共有することが可能となる。
【００２１】
また、宛先へのルートが複数存在する場合に、ルーティング制御用に通信をする必要なく、信頼性の高いルーティング制御を行うことが可能となる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態を図面にもとづいて説明する。
【実施例１】
【００２３】
本実施例は、複数の端末間で共通鍵を共有し、グループ内の秘匿通信を実現する。具体的には端末としてアドホックネットワーク機能を備えた携帯電話を用い、IPアドレスを用いてアドホックネットワーク通信を行い、知り合い関係の判定用識別子として携帯電話番号を使用する。ただし、判定用識別子は共通鍵の生成に用いるため、通信路に流れるデータから第3者が取得できないように工夫する。
【００２４】
なお、アドホックネットワークとは、インフラを必要とせず、その場に集まった端末同士でネットワークを構築できる無線ネットワークである。また、通信が直接行えない端末同士も他の端末を介することにより通信が可能になるネットワークである。
【００２５】
図2は本実施例を適用する無線ネットワークの構成例である。携帯電話(110〜160、270、280)がアドホックネットワーク上に存在する。携帯電話(110〜160)のをメンバとしてグループを生成し、生成したグループ内での共通鍵を生成する。図2において、点線は知り合い関係を表し、実線は通信可能を表す。実線の中でも太線はグループ内の通信関係を表す。図2に示すとおり、各メンバは全員と知り合い関係ではない。
【００２６】
各携帯電話の構成について図3を用いて説明する。
【００２７】
各携帯電話にはメモリ(310)が備わっており、メモリ(310)には通信に使用するルーティングテーブル(311)、知り合い関係表生成に使用するアドレス帳(312)、自携帯電話の知り合いかどうかを表す、自端末の知り合い関係表（以下、知り合い関係表Aという）(313)、ネットワーク上に存在する各端末がそれぞれどの端末と知り合いを表す、ネットワーク上の知り合い関係表（以下、知り合い関係表Bという）(314)、グループ内共通鍵を生成して共有するためのグループ内通信経路を表す木構造(315)、グループ内共通鍵生成に使われる乱数(316)、知り合い関係にある端末との暗号化通信に使用する端末間共通鍵(317)、グループ内共通鍵(318)が格納されている。生成したい知り合い関係表は、知り合い関係表B(314)であり、知り合い関係表A(313)は知り合い関係表B(314)を生成する過程で必要である。
【００２８】
各携帯電話は、ルーティングテーブル(311)およびアドレス帳(312)を用いて知り合い関係表A(313)、B(314)を生成する知り合い関係表生成部(303)、生成した知り合い関係表(314)にもとづき木構造(315)を生成する木構造生成部(304)、木構造(315)にもとづき集めた乱数(316)から鍵を生成する鍵生成部(305)と鍵の正当性を検証する鍵検証部(306)、生成した鍵を使ってデータの暗号化および／または復号化を行う暗復号化部(307)、知り合い関係表などのデータを表示する表示部(302)、グループメンバの選択などを行うデータ入力部(301)、電話通信部(308)、無線LAN通信部(309)を備えている。各携帯電話は同じ知り合い関係生成関数、木構造生成関数、鍵生成関数、鍵検証関数、暗号化および／または復号化関数を共有する。
【００２９】
上記各処理部(301〜309)は、図示していないプロセッサが、メモリ(310)に格納されている図示していないプログラムを実行することにより、プロセスとして実現されるか、および／または、図示していない回路を制御することにより実現される。プログラムは、予めメモリ(310)に格納されていても良いし、必要なときに、当該携帯電話が利用可能な、着脱可能な記憶媒体または通信媒体（ネットワークまたはネットワーク上の搬送波）を介して、上記携帯電話に導入されてもよい。また、端末は携帯電話以外でも上記機能(301〜310)を保持できる端末ならば適用可能である。また通信は、電話、無線LANに限る必要はなく、知り合い判定に用いる端末識別子以外を用いた通信であればよい。
【００３０】
図4を用いてグループ内共通鍵を生成する流れを説明する。
はじめに無線LANによるアドホックネットワークを構築し、ルーティングテーブル(311)が生成される(ステップ401)
次に、各携帯電話の知り合い関係表生成部(303)が、メモリ(310)にあるアドレス帳(312)を用いてネットワーク上の知り合い関係表B(314)を生成し、メモリ(310)に格納する。知り合い関係表Bの生成によりネットワーク上の暗号化通信が可能となる場所が判明する(ステップ402)。
【００３１】
次に、グループのリーダとグループメンバを選択し(ステップ403)、
木構造生成部(304)が、知り合い関係表B(314)を用いて第i層の携帯電話と第i+1層の携帯電話が知り合い関係になるように木構造(315)を生成し、メモリ(310)に格納する(ステップ404)。ステップ404のグループメンバによる木構造生成によりグループ内共通鍵に必要なデータおよびグループ内共通鍵を送信するための暗号化通信経路が確定する。
【００３２】
木構造(315)を生成後、木構造の子ノードから親ノードへと暗号化通信を使って順に乱数を送信し(ステップ405)、
木構造の最上層に存在する携帯電話が、送信された乱数をもとにグループ内共通鍵(318)を生成し(ステップ406)、
生成したグループ内共通鍵(318)をメモリ(310)に格納する。収集した乱数とともにグループ内共通鍵(318)を木構造の最上層から順に子ノードへと配布する(ステップ407)。
【００３３】
グループ内共通鍵(318)および乱数を受信した携帯電話では、鍵検証部(306)が、送信されたグループ内共通鍵(318)が正しいか送信された乱数を使って検証する(ステップ408)し、
各携帯電話が配布されたグループ内共通鍵(318)が正しいことを検証するとグループ内共通鍵の生成と共有が終了したこととなる。
【００３４】
次に、上記に記述したグループ内共通鍵の生成と共有の流れにおける各処理の詳細を順に説明する。
【００３５】
まず、ステップ402の知り合い関係表生成の手順について図5、6、7を利用して説明した後、図8を用いて図2に示すネットワーク構成例における知り合い関係表生成の具体的な動作を説明する。
【００３６】
ステップ402の知り合い関係表生成について、携帯電話(110)に着目し、図5を用いて手順を説明する。
【００３７】
携帯電話(110)はネットワーク上に存在する他の携帯電話が自携帯電話(110)の知り合いかを確認する。知り合いであることは、互いのアドレス帳(312)に互いの電話番号が登録されているかどうかで判定する。携帯電話(110)の電話番号(Num110とする)をハッシュ関数にかけた値h(Num110)を求め、ルーティングテーブル(311)に存在する全携帯電話に対してh(Num110)を送信することで、ルーティングテーブル(311)に存在する全携帯電話に携帯電話(110)を知っているか判定を依頼する(ステップ501)。携帯電話(110)の電話番号Num110をハッシュ関数にかけたのは、端末(110)の電話番号Num110を知らない携帯電話が携帯電話(110)の電話番号Num110を知ることを防ぐためである。
【００３８】
携帯電話(110)は、ルーティングテーブル(311)に存在する各携帯電話から、それぞれが判定した知り合い判定結果を受信する(ステップ502)
携帯電話(110)を知っていると判定した他の携帯電話に対しては、当該携帯電話が後述する図6に従って行う処理に応答して、携帯電話(110)が送信元携帯電話を知っているか知り合い判定を行う(ステップ504)
携帯電話(110)も知っていると判定した場合のみ知り合い関係が成立する。他の携帯電話からの判定結果を知り合い関係表A(313)に反映する(ステップ505)
知り合い関係が成立した場合は知り合い関係表B(314)も更新する(ステップ506)。
【００３９】
他の携帯電話から判定結果を受信すると(ステップ507)、
携帯電話(110)は他の携帯電話に知り合い関係表A(313)を送信し(ステップ508)、
携帯電話(110)は他の各携帯電話から、それらが同様に作成した知り合い関係表A(313)を受信する(ステップ503)。
【００４０】
受信した知り合い関係表A(313)を携帯電話(110)の知り合い関係表B(314)に反映し(506)、ネットワーク上の知り合い関係表B(314)が完成する。
【００４１】
図6を用いて、図5のステップ501で携帯電話(110)が送信したh(Num110)を受信した、他の携帯電話の動作手順を説明する。
【００４２】
h(Num110)を受信した携帯電話(120)は、アドレス帳(312)を利用して携帯電話(110)を知っているか知り合い判定を行う(ステップ601)。知り合い判定処理の内容は図7で説明する。
【００４３】
知っていると判定された場合、携帯電話(120)の電話番号Num120をハッシュ関数にかけた値h(Num120)を求め(ステップ602)、
知っているという判定結果と一緒に携帯電話(110)に送信する(ステップ603)。
【００４４】
知らないと判定された場合は、その判定結果と携帯電話(120)のメンバ名を携帯電話(110)に送信する(ステップ604)。
【００４５】
図7を使ってステップ504、601における知り合い判定処理を説明する。
【００４６】
知り合い判定処理を実行する携帯電話(120)のアドレス帳に登録されている番号をそれぞれnum_0、num_1、…とする。携帯電話(110)より電話番号Num110のハッシュ値h(Num110)を受信した携帯電話(120)は、アドレス帳に登録されている各番号num_i(i=0,1,・・・)をハッシュ関数にかけた値h(num_i)を順に受信したハッシュ値h(Num110)と比較する(ステップ701)。
【００４７】
h(Num110)と等しい値が存在した場合、携帯電話(120)は携帯電話(110)を知っていると判断し(ステップ702)、
すべての番号のハッシュ値を比較して、h(Num)と一致するものが存在しない場合は携帯電話(110)を知らないと判断する(ステップ703)。
【００４８】
図8を用いて図2に示すネットワーク構成例の携帯電話(110)が知り合い関係表を生成する流れを説明する。
【００４９】
携帯電話(110)は各携帯電話が携帯電話(110)を知っているかを判定してもらうため、携帯電話(110)の電話番号Num110をハッシュ関数にかけた値h(Num110)を生成し(801)、
ルーティングテーブル(311)上に存在する携帯電話(120〜160、270、280)へ送信する(ステップ802)
各携帯電話は携帯電話(110)の知り合い判定を図7に示す手順で行う(ステップ803)
携帯電話(120、140、160、270、280)は知らないという結果と各メンバ名(319)を、携帯電話(130、150)は知っているという結果と携帯電話(130、150)の各電話番号をハッシュ関数にかけた値と各メンバ名(319)を携帯電話(110)へ送信する(804、805)。
【００５０】
携帯電話(110)は携帯電話(110)を知っていると判定した携帯電話(130、150)に対して図7に示す手順で携帯電話(110)の知り合いか知り合い判定を行い(ステップ806)、
その判定結果と残りの端末からの判定結果を携帯電話(110)の知り合い関係表A(313)およびネットワーク上の知り合い関係表B(314)に反映する(ステップ807)。
【００５１】
ルーティングテーブル上に存在する携帯電話(120〜160,270,280) と知り合い判定を行った結果を知り合い関係表A(313)に反映する(ステップ807)と、携帯電話(110)の知り合い関係表A(313)は完成する。
【００５２】
携帯電話(110)は、携帯電話(110)の知り合い関係表A(313)を他の携帯電話(120〜160、270、280)へ送信し(ステップ808)、
受信した各携帯電話は各自の知り合い関係表B(314)を更新する(ステップ809)。
【００５３】
各携帯電話は携帯電話(110)と同様に各携帯電話の知り合い関係表A(313)を生成する(ステップ810)。
【００５４】
携帯電話(110)はルーティングテーブル(311)上に存在する携帯電話から各携帯電話の知り合い関係表(313)を受信し(ステップ811)、
ネットワーク上の知り合い関係表B(314)を更新し(ステップ812)、図9に示すネットワーク上の知り合い関係表B(314)が完成する。
【００５５】
各携帯電話が携帯電話(110)と同様に動作し、図9と同じネットワーク上の知り合い関係を生成する。
【００５６】
次に、ステップ403の処理を説明する。リーダはあらかじめ決定しておく必要がある。本実施例では、図2に示すネットワーク構成例においてグループメンバを選択し、グループ内共通鍵の生成を要求した携帯電話(110)をリーダとする。リーダは表示部(302)に表示されたネットワーク上の知り合い関係表B(314)よりグループメンバを入力部(301)を用いて選択する。知り合い関係表B(314)を生成する際に取得した各携帯電話のメンバ名(319)を選択することによりメンバの選択がしやすくなる。
【００５７】
次に、ステップ404における、ネットワーク上の知り合い関係表B(314)を用いた木構造の生成手順を図10、12、13に基づいて説明する。本実施例では、木構造を図10に示すようなリスト構造で表すが、図11に示すようなテーブルで表しても良い。各携帯電話を表すListは木構造上の自分の階層(depth)、親ノードを示すポインタ(parent)、同じ階層の次の携帯電話を示すポインタ(next)、子ノード数(childNum)、先頭の子ノードへのポインタ(child)を保持する。
【００５８】
木構造生成の方針として、階層はできるだけ深くせず、また、1つの携帯電話から接続される子ノード数はできるだけ少なくする。前者の方針は共通鍵を共有するまでは木構造にもとづいて通信を行うため、少しでも通信の遅延を少なくすることを目的とし、後者の方針は1つの端末にかかる負担をできるだけ軽減することを目的とする。
【００５９】
リーダである自携帯電話を木構造の第1層としてリストに設定する。第i層(i=1,2,・・・)まで確定したとすると、ネットワーク上の知り合い関係表B(314)を使用して第i層の各携帯電話の知り合い関係にある携帯電話を求める(ステップ1201)
求めた携帯電話は木構造の第i+1層の候補となる。求めた第i+1層の候補である携帯電話が既に木構造に存在しないかを確認する(ステップ2101)
存在しない場合は、木構造の第i+1層としてリストに設定する(ステップ2102)。
【００６０】
存在する場合(ステップ2103)は、
存在する階層を調べ(ステップ2104)、
第i層以上に既に存在する場合(ステップ2104)は変更しない。
【００６１】
同じ層に存在する場合(ステップ2105)は、
親ノードである携帯電話の子ノード数を比較し(ステップ2106)、
現在の親ノード候補の子ノード数が既に設定されている親ノードの子ノード数より少ない場合は、親を変更する(ステップ2107)。第i+1層の候補である全携帯電話に対してこの操作を繰り返し、第i+1層が確定する。
【００６２】
第i+1層を第i層とし(ステップ12021)、上記処理を繰り返し、
メンバ全員が木構造に設定される(ステップ1203)まで繰り返す。
【００６３】
図2に示すネットワーク構成において、リーダである携帯電話(110)が、携帯電話(110〜160)をメンバとするグループを生成する場合の具体的な木構造生成の手順は、以下のようになる。
【００６４】
はじめにリーダである自携帯電話(110)を木構造の第1層に設定し、図9の知り合い関係表を使って携帯電話(110)と知り合い関係にある携帯電話(130、150)を求め、木構造の第2層に設定する。次に第2層の携帯電話(130)と知り合い関係にある携帯電話を図9の知り合い関係表より求め、携帯電話(140)を得る。携帯電話(140)はまだ木構造に設定されていないので、携帯電話(130)が親ノードである木構造の第3層として設定する。
【００６５】
同様に携帯電話(130)と同じ第2層の携帯電話(150)と知り合い関係である携帯電話を求め、携帯電話(120、140、160)を得る。携帯電話(140)は既に同じ第3層として木構造に存在するため、携帯電話(140)の親である携帯電話(130、150)が有する子ノード数を比較する。子ノード数を比較した結果、子ノード数は携帯電話(150)の方が多いため、携帯電話(140)の親ノードは携帯電話(130)とする。
【００６６】
携帯電話(120、160)はまだ木構造に存在しないので、第3層として木構造に設定する。全メンバが木構造に設定されたことが確認でき、図1に示す木構造が完成し、グループ内共通鍵を共有するまでの安全なルートが確定する。図10、11に、それぞれリスト形式とテーブル形式で表した木構造を示す。
【００６７】
上記木構造を生成した後で、リーダは木構造データをグループメンバ全員に配布する。具体的には、携帯電話(110)が木構造データを携帯電話(130、150)に送信する。携帯電話(130、150)はそれぞれ木構造上で自分の子ノードである携帯電話、携帯電話(130)の場合は携帯電話(140)、携帯電話(150)の携帯電話は携帯電話(160、120)に、木構造データを送信する。このとき、お互いの電話番号を知っていることを利用して暗号化通信を行う。
【００６８】
図14を用いて図1に示す携帯電話(110)と携帯電話(130)間での木構造データの暗号化通信を説明する。携帯電話(110)は自身の電話番号Num110及びデータ送信相手である携帯電話(130)の電話番号Num130をアドレス帳(312)より取得する(ステップ1301)。
【００６９】
取得した2つの電話番号をもとに鍵生成部(305)にて携帯電話(110、130)間の共通鍵(317)を生成する(ステップ1302)。鍵生成関数は、各データを同等に使用し、生成した共通鍵から各電話番号が推定できないものを使用する。例えば、携帯電話(110)の電話番号Num110と携帯電話(130)の電話番号Num130を小さい順に並べ、ハッシュ関数にかけた値を共通鍵とする。
【００７０】
暗復号化部(307)で携帯電話(110)は携帯電話(130)との共通鍵(317)で木構造データを暗号化し、送信する(ステップ1303、1304)。
【００７１】
携帯電話(130)は、携帯電話(110)から暗号化された木構造データを受信したことを確認すると(ステップ1305)、携帯電話(110)の電話番号Num110をアドレス帳(312)から取得し(ステップ1306)、
携帯電話(110)との共通鍵(317)を鍵生成部(305)で生成し(ステップ1307)、
暗復号化部(307)で暗号化された木構造データの復号化を行う(ステップ1308)。復号化した木構造(316)をメモリ(310)に格納する。
【００７２】
携帯電話(130)は、復号化した木構造(316)から次に携帯電話(140)に木構造データを送信することを確認し、上記と同様の手順で携帯電話(140)に暗号化された木構造データを送信する。この動作を順次行うと、木構造がグループメンバ全員に配布される。
【００７３】
本実施例では、リーダがグループメンバを選択し木構造の生成を行った後、生成した木構造をグループメンバ全員に配布したが、各携帯電話がリーダとグループメンバを選択し、各自で木構造を生成しても良い。各携帯電話が木構造を生成する場合は、木構造を配布する必要がないが、各携帯電話がリーダとメンバを選択する必要がある。
【００７４】
また、以後、グループ内共通鍵を生成するまで携帯電話同士間の通信は必ず上述した2者間暗号化通信を行っているものとする。本実施例では、2者間の暗号化通信にはアドレス帳(312)にある携帯電話番号を使用したが、あらかじめ2者間共通鍵を保持しておいてもよい。
【００７５】
次に、ステップ405、406に示したグループ内共通鍵生成の手順を図15、16にもとづいて説明する。
【００７６】
各携帯電話が乱数(316)を発生する(図15、ステップ1401)
自分が木構造上のどの階層にいるかを確認し(ステップ1402)、
最下層にいる場合は、親ノードである携帯電話に自分の乱数(316)を親ノードに送信する(ステップ1403)。
【００７７】
親ノードである携帯電話は、子ノードから乱数を受信すると(ステップ1404)、
受信した乱数と自分の乱数(316)を自分の親ノードに送信する(ステップ1405)。
【００７８】
第1層の端末、すなわちリーダは第2層の全携帯電話から乱数を受信する(ステップ1406)ことにより全メンバの乱数を取得し、
共通鍵生成部(305)にてグループ内共通鍵(318)を生成する(ステップ1407)。
【００７９】
このとき、使用される共通鍵生成関数は各端末の乱数が生成する共通鍵に反映され、生成された鍵から乱数が容易に推定できないものを使用する。例えば、全乱数を規則順に並べ替えた後(図16，ステップ1501)、
ハッシュ関数にかける(ステップ1502)。
【００８０】
次に、ステップ407、408に示した図17生成した共通鍵をグループメンバ全員に配布する手順及び配布された共通鍵が正当な共通鍵であることを検証する手順を、図17を使用して説明する。
【００８１】
第1層の端末、すなわちリーダは生成したグループ内共通鍵(318)と共通鍵生成に利用した全乱数を子ノードに送信する(ステップ1601)
ステップ1602でグループ内共通鍵(318)と共通鍵生成に利用した乱数を受け取った子ノードの鍵検証部(306)は、全乱数の中に自分が生成した乱数(316)が存在すること(ステップ1603)、
全乱数を鍵生成関数にかけた結果が受信したグループ内共通鍵(318)と同じ値であることを確認する。
【００８２】
自分が生成した乱数が存在しない場合(ステップ1605)、
または全乱数を共通鍵生成関数にかけた結果が受信した共通鍵と異なる場合は(ステップ1606)、
検証に失敗したとして検証結果を親ノードと子ノードに送信する(ステップ1607)。
【００８３】
検証に成功した場合は、自分の全子ノードへ全乱数とグループ内共通鍵(318)を送信し(ステップ1608)、
自分の検証が成功したことを配布されたグループ内共通鍵(318)を使って暗復号化部(307)が暗号化し、グループメンバ全員へ送信する(ステップ1609)。
【００８４】
暗復号化部(307)は、グループメンバ全員から検証の成功を知らせるメッセージを、自分が保持するグループ内共通鍵(318)を使って復号化できることにより、グループメンバ全員がグループ内共通鍵の検証・共有に成功したことを確認する(ステップ1610、1611)。
【００８５】
検証を行っている際に自分の親ノードまたは子ノードから検証に失敗したことを表すメッセージを受信した場合(ステップ1612)、または検証成功メッセージの復号化に失敗した場合は(ステップ1613)、共通鍵の生成と共有に失敗したこととなる。
【００８６】
図18を使って図2に示すネットワーク構成例の携帯電話(110〜160)が共通鍵の生成、共有および検証手順を説明する。各携帯電話が乱数を発生し(ステップ1701)、
携帯電話(140)は生成した乱数rand140を親ノードである携帯電話(130)に送信する(ステップ1702)。
【００８７】
携帯電話(130)はrand140 と携帯電話(130)の乱数rand130を親である携帯電話(110)に送信し(ステップ1703)、
同様に携帯電話(120、160)は親ノードである携帯電話(150)に各自生成した乱数rand120、rand160を送信し(ステップ1704、1705)、
携帯電話(150)は受信した乱数rand120、rand160とrand150を携帯電話(110)へ送信する(ステップ1706)。
【００８８】
携帯電話(110)は全乱数が集まったことを確認すると、グループ内共通鍵(318)を生成し(ステップ1707)、
共通鍵生成に利用した乱数とともに生成したグループ内共通鍵(318)を子ノードである携帯電話(130、150)に送信する(ステップ1708、1709)。
【００８９】
携帯電話(130)の鍵検証部(306)は、受信した乱数に自分が生成した乱数rand130が含まれていることと、受信した乱数からグループ内共通鍵を生成して受信したグループ内共通鍵(318)と同じ値になることを確認する(ステップ1710)。
【００９０】
確認後、子供である携帯電話(140)へ乱数とグループ内共通鍵を送信し(ステップ1711)、
グループメンバ全員に検証が成功したというメッセージをグループ内共通鍵で暗号化して送信する(ステップ1712)。
【００９１】
携帯電話(130)の暗復号化部(307)は、グループ内共通鍵(318)を使って他の携帯電話から暗号化された検証の成功を表すメッセージを復号化することにより、各端末が検証に成功したことを確認する(ステップ1713)
その他の携帯電話に関しても携帯電話(130)と同様の処理を行うことにより、メンバ全員がグループ内共通鍵の共有と検証に成功したことを確認できる。
【００９２】
本実施例ではリーダがグループ内共通鍵を生成しメンバに配布したが、リーダは共通鍵を生成せず、乱数のみを配布し各メンバがグループ内共通鍵を生成しても良い。
【実施例２】
【００９３】
本実施例では、図2で示すネットワーク構成例において、図5、6、7の手順に従って生成された知り合い関係表B(314)を利用して、安全な経路の選択を実現する方法を説明する。
【００９４】
具体的には、知り合い関係表B(314)を用いて、ルーティングテーブル(311)を更新する。本実施例におけるネットワークでは、各携帯電話が各宛先携帯電話へのルートをすべて把握しているものとし、各携帯電話は本発明による知り合い関係表を用いたグループ内共通鍵生成と共有機能を備えているものとする。ただし、携帯電話以外でも上記グループ内共通鍵の共有機能を備えている端末ならば適用可能である。
【００９５】
各携帯電話が、ネットワーク上の知り合い関係表B(314)を用いてルーティングテーブル(311)を更新する手順を図19にもとづいて説明する。
【００９６】
ルーティングテーブル(311)上の各宛先までのルートが複数存在する場合(ステップ1801)、
各ルートに対してホップ数、各ルートの端末間で知り合い関係である箇所を知り合い関係表B(314)より求め、ホップ数から知り合い関係箇所を引いた値をそのルートの信頼値とする(ステップ1802)
本実施例では、値が低いほど信頼度が高いものとし、信頼値がもっとも低いルートをその宛先へのルートとして選択する(ステップ1803、1804)。
【００９７】
信頼値は同じ場合はホップ数が少ないルートを選択する(ステップ1805、1806)
選択したルートを着目宛先までのルートとしてルーティングテーブルに載せる(ステップ1807)。
【００９８】
本実施例では、ホップ数から知り合い関係箇所を引いた値を信頼値として使用したが、知り合い関係箇所を考慮した計算による値ならば信頼値として利用可能である。
【００９９】
図2で示すネットワークにおいて携帯電話(110)から携帯電話(120)へのルートは図20に示す5通りである。各ルートのホップ数と図9に示す知り合い関係表から端末間の知り合い数を求めた結果を図21に示す。図21より信頼値がもっとも低い（信頼度がもっとも高い）ルートは、端末(150)を経由して端末(110)から端末(120)へデータを送信するルートとなり、このルートをルーティングテーブルに記載する。
【０１００】
上述のように、端末にあらかじめ備わっているアドレス帳と知り合い関係表を利用し、信頼性を判断するため、判定が容易である。
【図面の簡単な説明】
【０１０１】
【図１】グループメンバによる木構造を示す図である。
【図２】実施例のネットワーク構成例を示す図である。
【図３】携帯電話端末の構成を示す図である。
【図４】グループ内共通鍵生成の流れを示す図である。
【図５】知り合い関係表作成の手順を示す図である。
【図６】ハッシュ値を受信した端末の動作手順を示す図である。
【図７】知り合い判定の手順を示す図である。
【図８】実施例のネットワークにおける知り合い関係表生成の流れを示す図である。
【図９】実施例のネットワークにおける知り合い関係表を表す図である。
【図１０】木構造をリスト構造で表した図である。
【図１１】木構造をテーブルで表した図である。
【図１２】木構造生成の手順を表す図である。
【図１３】木構造生成の手順を表す図である。
【図１４】２者間暗号化通信の手順を表す図である。
【図１５】グループ内共通鍵生成の手順を表す図である。
【図１６】共通鍵生成関数例を表す図である。
【図１７】グループ内共通鍵共有と検証手順を表す図である。
【図１８】実施例のネットワークのグループ内共通鍵共有と検証の流れを表す図である。
【図１９】ルーティングテーブル更新の手順を表す図である。
【図２０】実施例のネットワークに存在する携帯電話(110)から携帯電話(120)へのルートを表す図である。
【図２１】実施例における各ルートのホップ数及び信頼数、コストを表す図である。
【符号の説明】
【０１０２】
110〜160：携帯電話、301：入力部、302：表示部、303：知り合い関係表生成部、304：木構造生成部、305：鍵生成部、306：鍵検証部、307：暗号化・復号化部、308：電話通信部、309：無線LAN通信部、310：メモリ、311：ルーティングテーブル、312：アドレス帳、313：自端末と各グループメンバとの知り合い関係表、314：グループ内における知り合い関係表、315：木構造、316：自端末及びグループ内メンバから収集した乱数、317：自端末と他の端末とで共有する端末間共有鍵、318：グループ内共有鍵、319：グループのメンバ名。
【図１】
2005223773.tif 000003
【図２】
2005223773.tif 000004
【図３】
2005223773.tif 000005
【図４】
2005223773.tif 000006
【図５】
2005223773.tif 000007
【図６】
2005223773.tif 000008
【図７】
2005223773.tif 000009
【図８】
2005223773.tif 000010
【図９】
2005223773.tif 000011
【図１０】
2005223773.tif 000012
【図１１】
2005223773.tif 000013
【図１２】
2005223773.tif 000014
【図１３】
2005223773.tif 000015
【図１４】
2005223773.tif 000016
【図１５】
2005223773.tif 000017
【図１６】
2005223773.tif 000018
【図１７】
2005223773.tif 000019
【図１８】
2005223773.tif 000020
【図１９】
2005223773.tif 000021
【図２０】
2005223773.tif 000022
【図２１】
2005223773.tif 000023