Random Number Generator (RNG)について
RNGについて調べてみました。
Random Number (RN)
NISTのCSRCでは以下のように定義されていました。
Definition(s):
A value in a set of numbers that has an equal probability of being selected from the total population of possibilities and, in that sense, is unpredictable. A random number is an instance of an unbiased random variable, that is, the output produced by a uniformly distributed random process.
NIST SP 800-107 Rev.1 under Random number
乱数の性質として無作為性と予測不可能性が挙げられています。
また、無作為に値を抽出し、連続した値(乱数列)を生成します。
この時、連続した値を再現することができないため、性質として再現不可能性も含まれていると考えられます。
Random Number Generator (RNG)
RNGは予測不可能な数値のソースです。上記で述べた"乱数"を理想的に生成することが可能です。
"純粋な運によって与えられる精度よりも高い精度で、結果を予測することが不可能なソース"と捉えられます。
例えば、コイントスです。
ただし、理論的に正しいとされるRNGを実際に"実装する"ことは不可能であり、結局実装はRNGの近似でしかありません。
RNGの近似的手法は、True Random Number Generator (TRNG)とPseudo Random Number Generators (PRNG)の2つに分けられます。
(コイントスのような理想的なRNGを"perfect RNG"と記述している例もありました。)
True Random Number Generator (TRNG)
TRNGはランダムな物理現象(非決定論的な現象)を利用してランダムなビットを生成します。
つまり、無作為性・予測不可能性を限りなく満たす乱数を生成することができます。
TRNGは大きく分けて３つのブロックで構成されます。
Entropy Source (ES)
複雑な物理現象等で観測されるデータを回収する部分です。
生成方法(物理現象)は知られながらも、生成する値が非決定論的である必要があります。
一般的にはノイズなどが利用されます。(ex. Thermal noise1)
Entropy Harvester (EH)
ESによって生成された値を読み込み、ビット列に変換する部分です。
Post Processor (PP)
この部分は必須ではないです。
ESやEHによって生じた偏りなどを減らしていく部分です。2
一般的な手法として、von Neumannによる手法3やXORが挙げられます。
より堅牢な方法として暗号学的ハッシュ関数(MD5やSHAなど)を用いた方法もあります。
Pseudo Random Number Generators (PRNG)
初期値(シード)を用いて、ランダムに見える長い乱数列を生成する方法(アルゴリズム)のことです。
シード値を用いて生成するため、再現不可能性を満たすことはありません。
実際にはTRNGを用いることが望まれますが、生成コストを考慮しPRNGが代用される場合があります。
シミュレーション等でPRNGを用いる場合は無作為性を満たす4ことで十分な場合が多いですが、暗号の分野においては予測不可能性を満たす必要があります。
暗号技術での利用に適した特性を持つPRNGをcryptographically secure PRNG (CSPRNG)と言います。
Cryptographically Secure PRNG (CSPRNG)
CSPRNGであるためには、まず無作為性を満たすこと(統計検定4等に合格していること)です。
次に"next-bit test"5に合格することと"state compromise extensions"6に耐えることが求められています。
ここについてはもう少し調べたいと思います。
参考文献
An integrated analog/digital random noise source | paper Thermal Agitation of Electric Charge in Conductors | paper
Software whitening Hardware random number generator #Software whitening | wiki
John von Neumann / Collected works. volume Ⅴ : Design of computers, theory of automata and numerical analysis / p 768-770. 書籍の情報がわからなかったのですが、偶然同じような人がいたのですぐ判明しました。Finding a paper by John von Neumann written in 1951 | stackExchange
SP 800-22 : A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / FIPS 140-2 : Security Requirements for Cryptographic Modules
TRNG
Robust entropy harvester for analogue noise sources in TRNG | paper
Random number generation #"True" vs. pseudo-random numbers | wiki
PRNG
List of random number generators | wiki
暗号理論
暗号理論入門 原書第3版 (978-4-621-06186-2)
暗号と乱数―乱数の統計的検定 (978-4-320-11258-2)
暗号技術の全て (978-4-7981-4881-6)