FLAGS

筆者おかあつ 大きな区分 記事の区分 記事の一覧 検索 ツイート

2009年5月19日火曜日

IDとは(アルゴリズムネタ) (mixi05-u459989-200905191735)

ミクシ内で書かれた旧おかあつ日記を紹介します。
IDとは(アルゴリズムネタ)
2009年05月19日17:35
今デジタル証明書の設計をしていて、すごく時間がかかっている。 正直こんなに難しいと思っていなかった。

デジタル証明書の設計が難しい理由はいくつかある。 その理由は非常に根源的で理解がとても難しい。 デジタル証明書とはデジタル署名された証明書と呼ばれるファイルのことだ。 ここでデジタル署名というものが重要な役割を果たす。 だからデジタル署名というものの性質について深く考える必要がある。

======================================

署名と証明書とは

デジタル署名というのは、しばしば、紙とサイン(署名)になぞらえる。 ある文が書かれている紙にある人がサラサラと署名すると、確かにその人がその紙を見た、ということをあらわすことが出来る。 一般的には、署名には一定の意味が持たされている。 例えば 「その契約書に『同意』した」とか「確かにこの手紙は自分が書いた」とかそういう意味が含まれている。

しかし署名自体にその署名の意味は書かれていない。 署名があるからといって、その紙の内容に同意したのかまではわからない。 ひょっとしたら、「その紙を確かに私が書きましたが、内容については私は同意していません」 という意味かもしれない。

そこで、一般的にその署名の意味は紙に明記されている物だ。紙自体に「ここに署名した者はこの内容に同意したとみなす」というようなことが書かれており、署名に対してはっきりした意味がつけられる。 このように署名に対して意味を持たせるような紙のことを「証明書」と呼ぶ。

本来サインをするということは「確かにその人=サインの持ち主がその紙と出会い、そして署名をした」ということのみをあらわすものだ。 逆に見ると、署名がないということは、その人はその紙と出会っていたのだが署名しなかったのかもしれない。 その人はその紙と出会っていなかったのかもしれない。 署名があるということは、少なくともその両方=その紙と出会って、かつ署名をしたということが言える。

これが署名と証明書の概略だ。 そしてデジタル証明書の場合、問題はさらに複雑になる。 デジタルの世界では、紙、署名、というような存在する実体がないため、 紙の内容・署名の内容はいくらでも複製できてしまうからだ。 署名するということの本質的な意味が根本的に変化する。

======================================

現実とデジタルの違い

現実の世界では、肉体と魂は常に共にに存在している。 ところがデジタルの世界では、奇妙なことに肉体と魂は別な存在だ。 例えば、あるPDFファイルをもらったとすると、このPDFファイルはまるで魂のような存在だ。 魂は実体のない存在である以上、インターネットを通じて誰にでも複製を送ることが出来る。 しかも、プリンターを使えば、いつでもどこでも肉体を与える=実体化することが出来る。 ファイルというのは実に不思議な存在だ。

そうすると、非常に困ったことが起こる。 「名前」という概念が持っている機能が、ある物の存在を説明するにあたって、不足してしまう。 例えば生活上、「田中一郎」と呼べば、田中一郎はひとりしかいないので、田中一郎氏が返事をするだろう。 ところが、もしこの「田中一郎」がデジタル上の情報で、インターネットで自由にやり取りすることが出来て、プリンターを使っていつでも実体化できるようなファイルだったらどのようにして呼べばいいのだろうか。 通常「名前」 というものは、ある「実体」に対してつけるものだ。 ところが、デジタルの世界では、その情報(魂)に対して「実体」が無数に存在するため、名前がつけられない。

そこで、デジタルの世界では、実体(インスタンス)と抽象的な実体(タイプ)と、はっきりと分けて扱い、それぞれに違う名前をつける習慣がある。

======================================

デジタル署名とは

デジタル署名をするということは、実体(インスタンス)に署名をするのではない。 抽象的な実体(タイプ)に署名をすることになる。 署名自体も抽象的な実体(タイプ)である以上、無数に複製が作られることになる。

======================================

デジタル署名する際のファイルフォーマットの重要性

ファイルというものは、単純な数値の羅列でしかない。 これはこのままでは人間にとって意味を成さない。 だからそこに必ず解釈が必要になる。 このことをファイルフォーマットと呼ぶ。

Aというファイルがあったとき、その内容が16進数で CA FE BA BE だったとする。 これはビッグエンディアンという方式によれば 3405691582 という10進数の整数である。 または、リトルエンディアンという方式を使えば 3199925962 という風に認識することも出来る。 あるいは、プログラム言語 JAVA用の実行ファイルとしても認識することが出来る。(JAVA用の実行ファイルの先頭には必ず CA FE BA BE というキーワードが振られる約束になっている。) このようにあるファイルの内容がどのような意味を表しているのかは、解釈(ファイルフォーマット)による。

ある人が、あるファイルAに署名したとする。 そのとき、もしもファイルの解釈が一定でなかったとしたらどうなるだろう。 ある人Aがある人Bに対して契約書の署名をさせ、その後そのファイルのファイルフォーマットを変更することで、契約の意味を変更することが可能になってしまう。 つまり、ファイルに署名するときには、そのファイルだけでなく、必ずそのファイルのファイルフォーマットを含めて署名する必要がある。

======================================

IDENTIFIER と LOCATOR とは

IDというのは、ある物に対して識別するための名前のような物だ。 たとえば住所などはIDのよい例だ。 もちろん人の名前もIDのひとつだ。

一口にIDと言ってもいくつか種類がある。 まず、IDENTIFIER と LOCATOR という区別があげられる。 IDENTIFIERというのは識別するものという意味で、LOCATOR というのは場所を示すという意味だ。

例えば、住所はLOCATORである。 つまり 住所は、物事を識別するためのしるしとして役割を果たすと同時に、その物理的な場所をも示す。 一方、人の名前「田中一郎」というような名前はIDENTIFIERである。 「田中一郎」という名前を聞いただけでは「田中一郎」がどこにいるのかまでは知ることが出来ない。

ネットの世界では、URI や URL と呼ばれる物が有名だ。 URI とは Uniform Resource Identifier の略で、ネット上の場所まではあらわさない。 一方 URLは、Uniform Resource Locator の略で、ネット上の具体的な場所まではっきり表すことができる。 URLというのは URIに含まれる。

また IDは一意性という属性を持っている。 住所は100%絶対に重複がない一意な存在だが、「田中一郎」という名前は、重複が多い。 「田中一郎」と言っても、じゃぁ3丁目の田中一郎氏なのか、隣町の田中一郎氏なのかは、判別がつかない。 「田中一郎」という名前は一意性が低いといえる。 一方住所は一意性が高い。


======================================
HASH値

あるファイル内容にほぼ一意になる数値を算出するという方法があり、これのことをHASH値・DIGEST値と呼ぶ。 これを使えばファイルの内容をほぼ一意に特定できる。

======================================

で、僕が言いたかったことは、次のことだ。

一般的に、デジタル証明書は、中にHASH値を内部に持つことができるようになっており、これにより間接的に別なファイルに署名することが出来るようになっている。

このとき、HASH値というのは、IDENTIFIERであって LOCATOR ではない。

ところが、デジタル証明書を設計するだんになると、どうしても、証明書、証明書の証明書、証明書の証明書の証明書、というように証明書を数珠繋ぎする必要が出てくる。そうすると、ファイルの管理が指数関数的に複雑になっていく。

何故ファイルの管理が複雑になるのかをよく考えてみると、HASH値がIDENTIFIERであって LOCATOR ではない、ということがボトルネックとなるからだ、ということが(僕には)おぼろげに見えてくる。

HASH値を応用したシステムを作ることで、HASH値をIDENTIFIERではなく LOCATOR として利用することは 技術的に可能で、 これが無いからこそ、証明書の普及に足かせとなっているのではないか、という気がする。



また、同時に、証明書には「有効期限」という要素が必要になるケースが多い。 「有効期限」は非常にオーバーヘッドが大きいアルゴリズムだが、今のところこれを手動で管理する以外方法がない。 これはシステム管理者にとって大変な重荷になっている。 この問題と、HASH値のIDENTIFIER性問題が積算されると、実用的な運用が不可能といえる作業の複雑さのレベルに達する。 これがボトルネックとなって証明書の普及の足かせとなっているのではないだろうか。


======================================

解決策

僕はこれの解決策として 非階層型ファイルシステムを作っている。 これは多分この問題の解決策として応用できるだろう。

僕としての問題は、「タマゴが先か・ニワトリが先か」というものだ。 非階層型ファイルシステムの実装には、柔軟なデジタル証明書のシステムが必要で、柔軟なデジタル証明書の実装には非階層型ファイルシステムが必要だ。

どちらから実装すればいいのか。 これが今日の課題だ。

簡易的なファイルを取りまとめるファイルフォーマット(ここではコンテナと呼ぼう)があれば解決するのではないだろうか。 コンテナを実装するなら、ごくシンプルなTARファイルのような物を作ってもかまわないしあるいは ZIPファイルをそのまま使ってもよいかもしれない。



コメント一覧
 
出展 2009年05月19日17:35 『IDとは(アルゴリズムネタ)』