出張版インターネット・トリビア: コンピュータと乱数

【IIJ 2019 TECHアドベントカレンダー 12/23（月）の記事です】

IIJでは、広報誌 IIJ.newsを定期的に発行しています。IIJ.newsではIIJのサービスの紹介と言うより、その時々に注目を集めているIT動向についてIIJスタッフが中心になって記事を書いています。

IIJ.newsには特集記事以外にもいくつか連載コラムがあります。その中の一つ「インターネット・トリビア」をこの記事の筆者(堂前)が担当しています。インターネット・トリビアでは、名前の通り、インターネット(や、コンピュータ)に関するトリビア的なネタを毎号とりとめも無く紹介するコラムで、2012年から続いています。

今回はアドベントカレンダーに合わせて、「出張版インターネット・トリビア」ということで、エンジニアブログ書き下ろしの記事をお届けしたいと思います。

IIJ.news (冊子)を毎号無料でお届けします

広報誌 IIJ.news、および、技術レポート誌 Internet Infrastructure Review (IIR)は、ご登録いただきました皆様に毎号無料でお届けしています。IIJ.news および IIR 送付の申し込みより送付先住所をお送りください。(会社名の欄は、学生の方がご所属の学校名、個人の方は「個人」と記入ください。

※バックナンバーはPDFで配布しています。

インターネット・トリビア: コンピュータと乱数

コンピュータ業界で乱数(列)と言えば、予測できない順番で出てくる数値の列のことを指します。乱数はコンピュータや通信の中で極めて重要な役目を果たしています。たとえば、皆さんのパソコンをつなげているネットワーク(EthernetやWi-Fi)では、複数の端末が同時にデータ送信して衝突が発生したときは、乱数で決めた「適当な時間」待ってからデータを再送するようになっています。なぜなら、待ち時間を一定にしてしまうと、複数の端末が同じ時間だけ待ってしまって、衝突を繰り返す可能性があるからです。

その重要性とは裏腹に、コンピュータにとって乱数を作り出すのは苦手なことの一つです。ご存じの通り、コンピュータはプログラムされた指示通りの処理を何度も何度も繰り返し同じ結果を出すことはできますが、その指示を外れて動くことはできません。本質的にコンピュータは乱数を生み出すことができないのです。

コンピュータが生成できる乱数のことを疑似乱数と呼びます。最初に決められた数値(初期値)を元に繰り返し一定の計算を行い、乱数のように”見える”数列を得ています。あくまで乱数のように見えるだけであり、真の意味では乱数ではありません。そのため、同じ初期値を使うと常に同じ順序の数列が生成されます。また、乱数の生成を繰り返していると、いつかは同じパターンに戻ってしまう(周期性がある)という特徴があります。疑似乱数を得るための計算手法については様々なものが提案されており、数値の偏りが少ないもの、同じパターンに戻ってくるまでの周期が長いものが良い計算手法であると言われています。

どれだけ良い計算手法であっても、疑似乱数は初期値が決まると必ず同じ数列が繰り返されます。そのため、真の乱数を得るために、何らかの形でコンピュータの外から「乱数の元」を持ってくる場合があります。この乱数の元をエントロピーと呼びます。例えば、キーボードやマウスの操作は予測が不可能で、細かなタイミングまで含めれば再現も困難ですので、良いエントロピー源として利用することができます。他にもハードディスクのアクセスの待ち時間などもエントロピー源として利用できます。

また、CPUの中には、半導体内の電子の不規則な運動によるノイズ(熱雑音)を用いて乱数を発生させる機構を持っているものもあります。こうした計算手法によらない乱数のことを「物理乱数」と呼びます。

乱数はコンピュータ内のあらゆるところで利用されていますが、中には乱数を生成する仕組みがいまいちだったため大きな問題が起こることもあります。

一つの例は、暗号鍵の生成にまつわる問題です。コンピュータ内で暗号を扱う際には「鍵」に相当する情報をあらかじめ用意する必要があります。通常、この鍵の生成は乱数を用いて行われ、生成された情報は暗号を使う本人のみが厳重に保管することになっています。しかし、一部のソフトウェアにおいて、疑似乱数を生成する計算方法に誤りがあったために、どのような鍵が生成されたかを他人が予測可能な状態になっていたことがありました。これでは鍵を秘密にしていても意味がなく、他人に暗号を解読される恐れがあります。

別の例では、乱数の使いすぎが原因でシステムが一時停止してしまったこともありました。先ほど書いたとおり、乱数のエントロピー源としてキーボードやマウスの操作が使われることが多いのですが、サーバとして利用しているコンピュータの場合キーボードもマウスも接続されておらず、十分なエントロピーが集められません。一方で、サーバは暗号通信などで乱数を大量に消費します。この結果、エントロピー不足で新しい乱数が生成できなくなり、システムが一時停止状態に陥ってしまったのです。

コンピュータに予測不可能な仕事をさせるのは、なかなか難しいのです。