乱数のタネの新しい生成法：Programing Bible

コンピュータだけでは真の乱数を発生させることはできない。従って、暗号処理など「乱数」を使うアプリケーションは、一般に考えられているほど安全ではない。だが、こうしたコンピュータによる乱数発生の限界を超える試みがある。

[Sam-'RavidgeMole'-Bisbee，japan.linux.com]

　広く知られているように、コンピュータだけでは真の乱数を発生させることはできない。そのため、ソフトウェアで乱数が必要なときは、代わりに疑似乱数を使うのが一般的だ。従って、暗号処理など「乱数」を使うアプリケーションは、一般に考えられているほど安全ではない。だが、こうしたコンピュータによる乱数発生の限界を超える試みがある。よく使われるのはシステムクロックを使う方法だ。こうした人間が直接かかわらない方法のほかに、人間の入力操作を直接的に利用する方法もある。

　面白いことに、Googleを利用すると、人間が直接かかわらない方法で乱数を発生させることができる。インターネットではWebページやドメインがひっきりなしに作られ変更され削除されており、絶え間なく無作為に動いている。従って、Googleのデータベースのような巨大なデータの集まりから、乱数のタネを取ることができるのである。このタネ（種）というのは、乱数を発生させるアルゴリズムの初期値となる数のことだ（このタネを初期値としてある種の計算を繰り返し行って乱数を発生させる。従って、この乱数列には規則性――疑似乱数――があり、同じタネからは同じ乱数列が発生する）。

　乱数のタネはデータの持つさまざまな特性を利用して生成できるが、真の乱数を発生させ得るだけのバラツキが必要である。その一方で、生成の処理は容易でなければならない。GoogleのGUIは一様すぎるためタネには使えないが（バラツキが小さい）、検索されたページからはタネが取れるだろう。

　Googleは類似のページを除いているため検索されたページは互いに異なっており、検索結果は異なる要素から成る集まりである。だから、そのほとんどのページに含まれているテキストはページごとに異なり、従ってGoogleで検索されたページはタネを取る良質の材料になるはずだ（バラツキが大きい）。これが、Googleからタネを取る方法の論拠である。テキストの持つ数的特性の一つに語数があるが、理論的には、Googleが検索したページのテキストに含まれる語数を数えることでタネを生成できる（生成処理が容易）。

　しかし、Googleは検索したページを無作為に示すわけではない。それどころか、ページランクに基づいて検索結果を順序づけている。そのため、同じ照会を2回繰り返せば同じページが同じ順序で表示される可能性が極めて高く、そこから取ったタネは予測される可能性が高い。従って、検索結果の中で最もランクの低いページを使うか、毎回、検索語を変えた方がよいだろう。

　予測可能性をさらに低くするには、検索語を毎回変えなければならない。つまり、検索語のリストを作る必要がある。例えば、検索されたページから1語抽出して加えていくようにすれば、検索語リストは容易に実現できる（生成処理が容易）。

　しかし、この方法には欠点がある。第一に、頻出語が多く追加されることになり、関連のある語が多くなってくるだろう。第二に、リストをコンピュータ上に置くため、次のタネの予測が容易になるだろう（実装上の大きな障害）。第三に、インターネットを利用しているため、ネットワークに接続されていなければ乱数を発生できず、一方、ネットワークに接続されていても接続速度が遅ければ乱数の発生も遅くなる（ページの取得に時間がかかる場合に備えて、タイムアウト機能を用意する必要があるだろう）。

　こうした欠点から、この方法は実現可能な方法というよりも、着想の面白さとして意味がある。拙文Google Random Number Generatorに、この方法で乱数を発生させる簡単な例がある。

ユーザー入力を直接利用してタネを取る

　コンピュータは、大概、キーボードから操作される。従って、その打鍵間隔からタネを取って保存しておくことにすれば、タネを取る材料に困ることはない。ユーザーはシステムにログインしなければならないから、ログイン時の打鍵はタネを取るにはうってつけである。

　ログインがあるたびにタネを変えるのも容易だし（新たに得た数をタネにする、古いタネに加算するなど）、ログインは最初の処理だから事前にタネを用意しておくことにもなる。システムクロックなどの疑似乱数のタネと合わせて使われることが多いが、類似のシステムはすでに使われている。

タネが取れても――

　手段はともあれタネが取れたら、乱数発生器に使えるようシステムのどこかに保管しておく（乱数が必要になったときにタネを取るのではない）。取り外し可能な媒体を含め、タネをデータ・ストレージ・デバイスに保管するのは好ましいことではない。誰かがタネにアクセスする可能性があるからだ。タネが手に入ればそれから発生される乱数を予測できてしまう。従って、保護されたメモリ上に保管すべきだ。

　保護されたメモリにタネを書き込むにはシステム権限で動作する必要があるが、システムがLinuxやBSDであれば、カーネルモジュールを書くのは難しいことではない。カーネルがタネを保管するように仕組んでおけば、クライアントプログラムがカーネルにタネを要求し、それを使って乱数発生器を呼び出すのは簡単なことだ。そして、乱数発生器が、与えられたタネを出発点として乱数発生アルゴリズムによって乱数を発生させる。

　システム権限がないか、あるいは、プログラムが書けないためにこうしたカーネルモジュールが使えない場合は、サーバのように動作するプロセス（サービス）を常時動作させておき、同様の処理を行うようにすればよい。このプロセスは、ほかのプログラムから呼ばれタネを保管したり取り出したりする。UID 0で動作することになるが、クライアントはプロセス間通信を使ってタネを要求すればよい。このサービスは、initを使ってシステムの起動時に立ち上げることになるだろう。

おわりに

　疑似乱数でも十分なことはある。しかし、SSHやGnuPGなどのように、安全にかかわるアプリケーションの場合は本当にデタラメなタネでなければならない。

　ここに述べたアルゴリズムのいずれか、あるいはほかのものでもよい。それを採用して、オペレーティングシステムが本当にデタラメなタネを生成するようにするのは簡単なことだろう。乱数発生用の標準ハードウェア機器を確立してもよい。今使われている疑似乱数発生器よりもましだ。ハードウェア方式はコンピュータメーカーにとってもユーザーにとっても割高になるだろうが、コンピュータをよく知るユーザーなら出費をいとわないだろう。

原文へのリンク