このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 乱数 へ行く。

*目次 [#i2d74234]

#contents


*乱数 [#db9f5300]

 直観的にいうと、''乱数(ランダム値)''とはでたらめな数の列のことである。


**乱数の定義 [#p6f45e80]

 乱数には次の3つの性質を考えることができ、それを何個満たすかどうかで乱数のランクが異なる。

|無作為性|統計的な偏りがなく、でたらめな数列になっているという性質。|
|予測不可能性|過去の数列から次の数を予測できないという性質。|
|再現不可能性|同じ数列を再現できないという性質。再現するためには、数列そのものを保存しておくしかない。|

 例えば、無作為性の性質を持っていたとしても、再現不可能性を必ず持ってい
るとは限らない。このように下の性質にいくほど厳しい制限、即ち完全なラン
ダムに近くなる。
 例えば、無作為性の性質を持っていたとしても、再現不可能性を必ず持っているとは限らない。このように下の性質にいくほど厳しい制限、即ち完全なランダムに近くなる。


**無作為性 [#r5eafbb4]

 無作為性とは、でたらめに見える性質のことである。擬似乱数列の統計的な性質を調べて偏りがないなら、その擬似乱数列は無作為であると考えられる。この調べる方法を乱数の検定と呼ぶ。乱数の検定にはたくさんの種類がある。 

 例えば、ゲームやシミュレーションで使う乱数は、乱数の検定を行う必要があるが、無作為性を持てば十分である。しかし、暗号技術で使う乱数は無作為性を持っているだけでは不十分なのだ。暗号技術で重要なのはアタッカーに見破られないことである。鍵がでたらめであったとしても、必ずしも見破られないとは限らないのである。例えば、線形合同法で作り出す擬似乱数は見破ることができてしまう。 

 このように、無作為性だけの性質を持つ擬似乱数を弱い擬似乱数と呼ぶ。

**予測不可能性 [#sdbf6054]

 予測不可能性とは、過去に出力した擬似乱数列をアタッカーに知られたとしても、次に出力する擬似乱数をアタッカーは言い当てることができないという性質のことである。 

 擬似乱数生成器のアルゴリズムはアタッカーに知られているものと仮定する。一般的な現代暗号は暗号化・復号化アルゴリズムは公開されているので、同時に擬似乱数生成器のアルゴリズムも知られているはずだ。また、暗号の鍵がアタッカーに秘密であるのと同様に、擬似乱数の種はアタッカーに秘密であるものとする。つまり、予測不可能性を厳密に言い換えると、擬似乱数生成器のアルゴリズムは公開するが、擬似乱数の種は秘密という仮定の下で、過去の擬似乱数列がアタッカーに知られたとしても、次に出力する擬似乱数は予測できないということである。 

 予測不可能性を持つ擬似乱数生成器を作るには、他の暗号技術を使って実現する。例えば、一方向性ハッシュ関数の一方向性、暗号の機密性などがそうである。 

 無作為性と予測不可能性を持つ擬似乱数を強い擬似乱数と呼ぶ。

**再現不可能性 [#t7997252]

 再現不可能性とは、ある乱数列と同じ数列を再現することはできないということである。その数列を再現するためには、その乱数列そのものを保存しておく以外に方法がないときに、その乱数列は再現不可能性を持つという。 

 ソフトウェアは擬似乱数列しか作れないので、再現不可能性を実現するにはソフトウェア以外の情報を使わなければならない。その情報は再現不可能な物理現象から得れば実現できる。現在では熱の変化をセンターで検知して、その変化をもとに、再現不可能性を持つ乱数列を生成するハードウェアが開発されている。 

 この再現不可能性も持っている乱数を真の乱数と呼ぶ。


*理想的な擬似乱数 [#f8c399d6]

|弱い擬似乱数|無作為性しか持たない|
|強い擬似乱数|無作為性、予測不可能性を持つ|
|真の乱数|3つすべての性質を持つ|

 弱い擬似乱数は暗号技術に使えない。一方、残りの2つが暗号技術で使える。

 よって、この3つの性質を満たすものが完全なランダム値(真のランダム値)である。しかし、このような真のランダム値は、コンピュータのソフトウェアでは作り出すことは不可能である。もしそうしたランダム値を作るとしたらハードウェアの助けが必要となる。しかも、かなり複雑でよいアイデアでなければ、偏りが出てしまうので、現実的には真のランダム値は使われない。そこで、普通の暗号では、無作為性と予測不可能性の2つの性質のみを持つランダム値を使われる。これは真のランダムではないので、''疑似ランダム''と呼ばれる。そうした疑似ランダムを生成する機構のことを''[[擬似乱数生成器]]''と呼ぶ。


*乱数生成器 vs 擬似乱数生成器 [#ffe2c524]

 乱数はハードウェアで生成する場合とソフトウェアで生成する場合がある。 

 真の乱数を生成するハードウェアを''[[乱数生成器]](Random Number Generator:RNG)''と呼ぶ。

 乱数を生成するソフトウェアを''[[擬似乱数生成器]](Pseduo Random Number Generator:PRNG、PRG)''と呼ぶ。ソフトウェアだけでは真の乱数は生成することができないので、擬似がつくわけである。


*暗号において乱数が使われる場面 [#se08555c]

-鍵の生成
--対称暗号やメッセージ認証コード(MAC)で使う。
-鍵ペアの生成
--公開鍵暗号やデジタル署名で使う。
-初期化ベクトル(IV)の生成
--ブロック暗号のCBC、CFB、OFBの各モードで使う。 
-ノンスの生成
--再生攻撃防止や簿ロック暗号のCTRモードなどで使う。
-ソルトの生成
--パスワードをもとにした暗号化([[PBE]])などで使う。 

 いずれも大切な役割であるが、とても重要なのは鍵の生成と鍵ペアの作成である。どんなに強力な暗号アルゴリズムを使っていても、鍵がアタッカーに知られてしまっては意味がない。鍵を見破られない(=予測不可能)ように乱数を使うのである。


*参考文献 [#o7610699]

-『暗号技術入門』