Random Number Generator (RNG)について | kosh.dev

Random Number Generator (RNG)について

Aug 28, 2021

RNGについて調べてみました。

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


乱数の性質として無作為性予測不可能性が挙げられています。


また、無作為に値を抽出し、連続した値(乱数列)を生成します。

この時、連続した値を再現することができないため、性質として再現不可能性も含まれていると考えられます。

RNGは予測不可能な数値のソースです。上記で述べた"乱数"を理想的に生成することが可能です。

"純粋な運によって与えられる精度よりも高い精度で、結果を予測することが不可能なソース"と捉えられます。

例えば、コイントスです。


ただし、理論的に正しいとされるRNGを実際に"実装する"ことは不可能であり、結局実装はRNGの近似でしかありません。

RNGの近似的手法は、True Random Number Generator (TRNG)とPseudo Random Number Generators (PRNG)の2つに分けられます。

(コイントスのような理想的なRNGを"perfect RNG"と記述している例もありました。)

TRNGはランダムな物理現象(非決定論的な現象)を利用してランダムなビットを生成します。

つまり、無作為性・予測不可能性を限りなく満たす乱数を生成することができます。


TRNGは大きく分けて3つのブロックで構成されます。


Entropy Source (ES)

複雑な物理現象等で観測されるデータを回収する部分です。

生成方法(物理現象)は知られながらも、生成する値が非決定論的である必要があります。

一般的にはノイズなどが利用されます。(ex. Thermal noise[*1])


Entropy Harvester (EH)

ESによって生成された値を読み込み、ビット列に変換する部分です。


Post Processor (PP)

この部分は必須ではないです。

ESやEHによって生じた偏りなどを減らしていく部分です。[*2]

一般的な手法として、von Neumannによる手法[*3]やXORが挙げられます。

より堅牢な方法として暗号学的ハッシュ関数(MD5やSHAなど)を用いた方法もあります。

初期値(シード)を用いて、ランダムに見える長い乱数列を生成する方法(アルゴリズム)のことです。

シード値を用いて生成するため、再現不可能性を満たすことはありません

実際にはTRNGを用いることが望まれますが、生成コストを考慮しPRNGが代用される場合があります。

シミュレーション等でPRNGを用いる場合は無作為性を満たす[*4]ことで十分な場合が多いですが、暗号の分野においては予測不可能性を満たす必要があります。

暗号技術での利用に適した特性を持つPRNGをcryptographically secure PRNG (CSPRNG)と言います。

CSPRNGであるためには、まず無作為性を満たすこと(統計検定[*4]等に合格していること)です。

次に"next-bit test"[*5]に合格することと"state compromise extensions"[*6]に耐えることが求められています。

ここについてはもう少し調べたいと思います。

1. Thermal Noise

An integrated analog/digital random noise source | paper

Thermal Agitation of Electric Charge in Conductors | paper


2. Software whitening

Hardware random number generator #Software whitening | wiki


3. Various technique used in connection with random digits

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


4. Statistical Test

SP 800-22 : A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications

FIPS 140-2 : Security Requirements for Cryptographic Modules


5. Next-bit test

Next-bit test | wiki

Theory and application of trapdoor functions | paper


6. State Compromise Extension Attacks

Cryptanalytic Attacks on Pseudorandom Number Generators | paper


TRNG

Implementation and Testing of High-Speed CMOS True Random Number Generators Based on Chaotic Systems | paper

A TRNG using chaotic entropy pool as a post-processing technique: analysis, design and FPGA implementation | paper

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)


prev
next