前のページ 1/1 次のページ

擬似乱数(ぎじらんすう、)とは、乱数列(乱数)のように見えるが、実際には確定的な計算によって求めている数列に含まれる数を指す。擬似乱数を生成する機器を擬似乱数生成器、生成アルゴリズムを擬似乱数生成法と呼ぶ。

乱数は本来規則性も再現性も無いために予測は不可能だが(例:サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能)、擬似乱数は計算によって作るので、作り方が分かれば理論的には予測可能であり、また内部の初期値(シード)が分かれば、先に計算しておくこともできる。

何をもって擬似乱数と呼ぶのかは議論があるところだが、暗号理論では擬似乱数(生成器)に明確な定義がある。すなわち、多項式時間の計算機が乱数と識別不能な列を出力する機器のことを、擬似乱数生成器と呼び、この列に含まれる数を(暗号論的)擬似乱数という。

いかなる数列であれば乱数列であるかも議論のあるところではあるが、一様分布であることと過去の数から次の数が予測不能であることは同値であることが示されている(Yao)。そこで過去の数から次の数が予測不能であるかで、(暗号論的)擬似乱数か否かを区別する。

◆用途

シミュレーション実験や、暗号などに利用されている。

物理乱数よりも手軽に扱え、また、シード値を元に戻すことで、まったく同じ乱数列を生成できるため、実験の再現ができるというメリットがある。

逆に、再現性を利用して、シード値の選択を意図的(不正に)に行う可能性を排除することが必要な場合もある(楕円曲線暗号のパラメータ生成など)。

◆主な擬似乱数生成法

様々な擬似乱数生成法が知られている。

・予測可能、再現性あり

  ・古典的生成法 - 平方採中法、線形合同法、混合合同法、線形帰還シフトレジスタ

  ・新しい生成法 - メルセンヌ・ツイスタ、カオス乱数

・予測不能、再現性あり

  ・暗号学的に安全な生成法 - BBS(Blum Blum Shub)、Fortuna

・予測不能、再現性なし

  ・ハードウェア乱数生成器 - サイコロ、熱雑音、宇宙線などを利用する物理的暗号

◇ 混合合同法(mixed congruential method)

下の式に適当な a、p、q を代入する(必要な桁数が採れれば何でも良い)。求まった a' の中間あたりの必要な桁数を乱数として採用し、それを新たな a として、再び下の式に代入する。

:ap + q = a'

(例)5 桁の擬似乱数を作ってみる。ただし、最初は a = 14992、p = 673、q = 944とし、求まった a' の、十の位から十万の位までを採用することとする。

:14992×673+944 = 10090560 → 09056

:09056×673+944 = 06095632 → 09563

:09563×673+944 = 06436843 → 43684

:43684×673+944 = 29400276 → 40027

:40027×673+944 = 26939115 → 93911

:…

こうして、擬似乱数列 を得る。

+ b \mod m

として、$X$ を乱数列とする。

-->

◇ 平方採中法(middle-square method)

1946年頃、ノイマンが提案

初期値に適当な a をきめ、それを 2 乗する。求まった値の中央にある、必要な桁数を採って乱数とし、それを 2 乗して求まった値の中央にある必要な桁数を採って次の乱数とする。これを繰り返して乱数列とする方法。ここで「中央」とは、求まった値を必要な桁数の 2 倍の桁数として見た時の中央とする。たとえば、4 桁を必要としていて、求まった値が 7 桁の時は、最上位の前の位(千万の位)に「0」を付け足して 8 桁とする(下の例を参照)。

(例)4 桁の擬似乱数を作ってみる。ただし、最初は a = 1763とする。

:1763² = 03108169 → 1081

:1081² = 01168561 → 1685

:1685² = 02839225 → 8392

:8392² = 70425664 → 4256

:4256² = 18113536 → 1135

:…

こうして、擬似乱数列 を得る

一般的には、平方採中法は偶数桁を採る時にしか使えないことと、周期が短い、つまり、どちらも、ずっと繰り返していればいつかは最初の数字に一致する数値が現れるが、それが平方採中法の方が早いことから、混合合同法を使うことの方が多いようである。

◇ 線形帰還シフトレジスタ

擬似乱数の生成方式として、線形帰還シフトレジスタ (LFSR; Linear Feedback Shift Register) を用いた方法が知られている。LFSRはデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保障される。しかし、LFSRは数学的に容易に解析可能であるため、そのまま暗号に使用することは推奨されない。

◆ 新しい擬似乱数生成アルゴリズム

上記のような古典的擬似乱数生成法の欠点を改良するため、新しい擬似乱数生成法がいくつか考案されている。

◇ メルセンヌ・ツイスタ

◇ カオス乱数

非線形微分方程式の解はカオスと呼ばれ、初期値敏感性等の性質を持つ。

漸化式の形で記述することによりカオス的な関数を得ることができるとされている。

よく使われる関数にロジスティック関数やテント写像がある。

厳密には有理式でなければランダムな関数とはならないため、コンピュータで実装した場合は必ずしも乱数性の優れた擬似乱数とはならない。

カオス乱数の出力をそのままストリーム暗号の鍵ストリームとして用いる手法は安全とは言えない。

◆ 暗号論的擬似乱数

暗号理論では擬似乱数に厳密な定義が与えられている。Σ = とする。自然数 k に対し、Σ^k 上の一様分布を U_k と表す。確率変数の族 _k∈N が、一様分布の族 _k∈N と計算量的識別不能な時、族 _k∈N は(暗号論的)擬似乱数であるという。

前述の混合合同法や平方採中法で作った乱数列は、簡単に真の乱数と識別可能なので暗号論的な意味では擬似乱数ではない。

次に擬似乱数生成器の厳密な定義をする。l(k) を l(k) > k を満たす多項式とする。G を多項式時間アルゴリズムで、G に k ビットのビット列を入力をすると l(k) ビットの出力を返すものとする。すると G(U_k) は Σ^l(k) 上の確率分布である。確率分布の族 _k∈N が擬似乱数である時、多項式時間アルゴリズム G を擬似乱数生成機という。

一方向性関数が存在すれば擬似乱数生成機が存在する事が知られている。

前のページ 1/1 次のページ

・擬似乱数 page1