衛星Secure


衛星Secureへようこそ。

ここでは、Mobile ad hoc network において安全な通信を行うために使われている「証明書」の分散について研究を行っている。

 

Ad hoc network とは

パソコン、PDA、携帯電話など、無線で接続できる端末(ユーザ)のみで構成されたネットワーク。Ad hoc network ではユーザは常に移動し、自由にnetworkから離れたり、入ったりする。災害時、戦場、イベントなど、即席のnetworkを構成するときに使われる。

無線の届く範囲にいれば誰でもデータの盗聴・改ざんやなりすましが可能なので、安全に通信を行う技術が必要となる。そのために使われている技術のひとつが証明書分散システムと呼ばれるものである。

 

証明書分散システム

public-key(公開鍵)とprivate-key(秘密鍵)
 
各ユーザはpublic-keyとprivate-keyというものを持っている。ドナルドがミッキーにメッセージを送るときは
  1. ミッキーのpublic-keyを得、
  2. メッセージをロックして送り、
  3. ミッキーは自分のprivate-keyでロックを解除
という手順を踏む。



図1. 鍵のロックと解除

 

証明書(certificate)
 
で、メッセージをロックするためにpublic-keyが必要となるわけだが、誰彼かまわずpublic-keyを配るのは危険なので証明書というデータ構造を用いる。ドナルドからミッキーへの証明書とは、ミッキーのpublic-keyをドナルドのprivate-keyでロックしたものであり、ドナルドがミッキーを信用している証である。ドナルドのpublic-keyを知っている人はこのロックを解除しミッキーのpublic-keyを得ることができる。



図2. 証明書の構造

 

認証(Authentication)
 
証明書は、なりすましを防ぎ、正しい相手のpublic-keyを得るために用いる。自分からの証明書をたどっていく(信用の連鎖を作る)ことで相手のpublic-keyを得られる。
下図のように、ドナルドとミッキーが証明書を持っていたとする。それらを合わせドナルドからミッキーまでの信用の連鎖ができていれば、ミッキーのpublic-keyを得ることができ、そのpublic-keyが間違いなくミッキーのものであると信用できる。その後、そのpublic-keyを使ってドナルドはミッキーに安全にメッセージを送ることができる。


図3. 各ユーザの持っている証明書

↓ 証明書の連鎖ができていれば


図4. 証明書認証

 

(この辺りの公開鍵暗号方式や認証についての詳しい話は、他の専門のサイトに任せます)

 

証明書をどこにどれだけ配る?

ここまでで、ドナルドがミッキーにメッセージを送ろうとしたときにはお互いに持っている証明書からミッキーのpublic-keyを得られなければならないことがわかった。各ユーザの持つ証明書の数の合計はコストに相当し、先の条件を満足しつつコストを抑えるには、誰にどんな証明書を持たせるとよいのだろうか?

ここでの研究内容は、「発行される証明書を各ユーザに効率的に分散させる」 こと。

通信したい(通信できなければならない)ペアに対し、ちゃんと相手のpublic-keyが得られるように証明書を配布し、かつ配布された証明書の総数(コスト)が最小になるよう、日々研究中である。

 

グラフにすると

ユーザと証明書の関係はグラフで表され(点:ユーザ、辺:証明書)、


図5. 証明書グラフ

"パスが存在する任意の2点にはパス上にある辺(証明書)が保存されている"ように証明書を分散させかつコストを低くすること、が研究課題となる。

以下は今までの研究成果である。


研究結果

-"An Optimal Certificate Dispersal Algorithm for Mobile Ad Hoc Networks" (pdf) (ppt)
The 3rd International Symposium on Parallel and Distributed Computing(ISPDC 2004)
Special Section on Discrete Mathematics and Its Applications
of IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences(to appear)

グラフ惑星へ戻る