3. 乱数生成器の技術

3.1. 乱数生成器の分類

乱数生成器は、決定性乱数生成器と非決定性乱数生成器に分かれます。前者は疑似乱数生成器、後者は真性乱数生成器と呼ばれることもあります。

3.2. 非決定性乱数生成器の技術

非決定性乱数生成器の技術は、大きく二つに分けられます。

  • システムに内在するエントロピーを(なんとか)かき集める
  • 外部からエントロピーを得る

以下では、この二つについて述べ、また、実装の関する規格について紹介します。

最後に、CPU/MCU組み込みの乱数生成器の実装について言及します。

3.3. 内在するエントロピーを集める実装

システムに内在するエントロピーを集める実装は、最近では、HAVEGE[1]が有名です。同様な試みで、カーネル内での実装の提案もあります[2]

以前では EGD[3]が使われることもありました。

歴史的には、1993年のCryptolibでtruerandと名付けられたアルゴリズムがあります。このアルゴリズムの実装については、Perl のモジュール Math-TrulyRandom-1.0[4]で見ることができます。このモジュール自身は歴史的なコードとしての意義以上の状態ではありません。使うには、Crypt-Random-TESHA2-0.01[5]でしょうか。

[1]

HAVEGE: HArdware Volatile Entropy Gathering and Expansion

[2]

CPU Time Jitter Based Non-Physical True Random Number Generator

[3]

EGD: The Entropy Gathering Daemon

[4]

Perl module: Math-TrulyRandom-1.0

[5]

Perl module: Crypt-Random-TESHA2-0.01

3.4. 外部からエントロピーを得る実装

実装として

  • リングオシレータ
  • メタスタビリティ
  • カオスの現象
  • サウンドボード
  • (蓋をした)CCDカメラ

3.5. その他

3.6. 実装関連の規格など

乱数生成器については、「これだ!」というものが定まっていて業界の実装がそれに則っている、という状況には、まだ、ありません(2013年現在)。

古くからあるものとしてはドイツBSIの文書 AIS31 がとても参考になるもので、英文のものもあります[8]。ISOの規格 18031 もあります[7]

AIS31 や ISO18031 は、乱数生成器の実装のおおまかな指針としては役に立ちますが、どのように実装するかについては、規定されていない部分が残されます。また、実装上、現実的に難しいことまで言及されていると思います。

まだドラフト段階ですが、NIST の文書 SP 800-90B[6]は、関連文書としては、もっとも新しいもので、(関連製品の検証まで視野に入れて)細かく規定されており、また、実装上、現実的な方策が示されていると思います。

[6]NIST SP 800-90B (draft)
[7]ISO/IEC 18031: Information technology — Security techniques — Random bit generation
[8]Wolfgang Killmann and Werner Schindler, A proposal for: Functionality classes and evaluation methodology for true (physical) random number generators, Version 3.1, 2001-09-25

3.7. CPU/MCU組み込みの乱数生成器の実装

周辺機器として追加する形式、命令を追加する形式があります。

1999年、Intel のチップセットの一部 82802 Firmware Hubに追加された例があります[9]

CPUコアに導入する試みとしては、x86アーキテクチャでは、VIA C3 の Nehemiah コアで導入されました(2003年)。最近では、Intel Ivy Bridge で RDRAND 命令が導入されました(2012年4月発表)。2014年発売が予定されているBroadwellでは、RDSEED命令が導入されます。

また、近年、MCUでも利用可能となってきており、一例をあげると、(NeuGの対象としているMCUより上のグレードの)STM32F2 や STM32F4 ではチップに組み込まれた乱数生成器が利用可能です。

Ivy Bridgeは最終段の疑似乱数生成器を含めて出来上がって構成されています。RDRAND命令は最終段の決定性(疑似)乱数生成器からの出力を得ます。この設計は、「とても親切」と言うこともできますが、ここまで組み込まれてしまうと果たして(それを信頼して)使えるのか、という疑問となってもやむを得ないでしょう。

一方、RDSEED命令は、(段の途中で)疑似乱数生成器の前の乱数を得ます。さて、こちらを(信頼して)使えるには、どのような状況となれば良いでしょうか。

VIA C3やMCU組み込みの機能は、DRAFT SP 800-90B の観点を吟味すると、厳しい用途では、ここから得たエントロピーを、ソフトウェアで実装されたconditioning component に入れて使う、ということになるでしょう。

このようにハードウェアによる乱数生成の役割の切り分けは難しい問題です。

[9]

The Intel Random Number Generator