• 追加された行はこの色です。
  • 削除された行はこの色です。
  • 擬似乱数生成器 へ行く。

*目次 [#u7d3cad6]

#contents


*擬似乱数生成器 [#jb99e27c]

 暗号学的に安全な''擬似乱数生成器(psudo-random generator:PRG)''とは、次の性質を持たす乱数でなければならない。

-一様分布性:出力される乱数系列に0と1の偏りがないこと。
-予測不可能性:過去の乱数系列から将来の乱数系列を予測できないこと。


**擬似乱数生成器の仕組み [#d59ca046]

・擬似乱数生成器は内部状態を持ち、外部から与えられた種を元に擬似乱数列を生成する。 
-擬似乱数生成器は内部状態を持ち、外部から与えられた種を元に擬似乱数列を生成する。 
-擬似乱数を1個生成するという命令が出たとき、擬似乱数生成器はメモリの値(内部状態)を元に計算をして、その計算結果を擬似乱数として出力する。そして、次の擬似乱数の出力命令に備えて、自分の内部状態を変化させておくのである。つまり、内部状態から擬似乱数を計算する方法と内部状態を変化させる方法の2つが、擬似乱数生成器のアルゴリズムである。 
-疑似乱数生成器で[[疑似乱数]]を生成するためには、疑似乱数の種(seed)という情報が必要である。疑似乱数の値は、疑似乱数生成器の内部状態を初期化するために用いられる。つまり、メモリの値を種として使うのである。種はもちろんアタッカーに予測されてはなりません。例えば、現在の時刻といってものを種としてしまうと脆弱ということである。

・擬似乱数を1個生成するという命令が出たとき、擬似乱数生成器はメモリの値(内部状態)を元に計算をして、その計算結果を擬似乱数として出力する。そして、次の擬似乱数の出力命令に備えて、自分の内部状態を変化させておくのである。つまり、内部状態から擬似乱数を計算する方法と内部状態を変化させる方法の2つが、擬似乱数生成器のアルゴリズムである。 

・疑似乱数生成器で[[疑似乱数]]を生成するためには、疑似乱数の種(seed)という情報が必要である。疑似乱数の値は、疑似乱数生成器の内部状態を初期化するために用いられる。つまり、メモリの値を種として使うのである。種はもちろんアタッカーに予測されてはなりません。例えば、現在の時刻といってものを種としてしまうと脆弱ということである。


*各種プログラミング言語・スクリプト言語における擬似乱数生成 [#aa01a67e]

**C言語 [#db863abf]

***rand() [#q1a3a07f]

-stdlib.hに用意されているsrand()に擬似乱数の生成のためのseedを渡すことができる。
--seedとして、time関数で取得した現在時刻を指定することが多い。
---例:srand((unsigned) time(NULL));
---time関数は秒単位の値を返すため、ループ内でsrand()とrand()を使ってしまうと、1秒間は同じ乱数値が出力されてしまうことになる。よって、srand()はループの外で1回行えばよい。
-rand()で擬似乱数(整数)を取得することができる。
--擬似乱数の範囲は0以上32768未満である。
-範囲を絞り込んで擬似乱数を生成するときは%演算子を用いた剰余計算を利用する場合が多い。
--「擬似乱数値=rand() % 範囲の要素数 + 範囲の最小値」とする。

***OpenSSL付属のBIGNUMライブラリ [#h5142784]

 擬似乱数を持つBIGNUMオブジェクトを取得するにはBN_rand_range()関数を用いる。BN_rand_range()関数の書式は次の通り。

 int BN_rand_range(BIGNUM *result, BIGNUM *range);

 この関数の引数は次の通り。

-result
--初期化済みのBIGNUMオブジェクトのポインタ。
--生成された素数はこのオブジェクトに格納される。
-range
--0〜ここで指定した値までの擬似乱数を生成する。

 また、BN_generate_prime()関数を使えば、ランダムな素数を生成することができる。BN_generate_prime()関数の書式は次の通り。

 BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add, BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg);

 この関数の引数は次の通りである。

-ret
--割り当てられたBIGNUMオブジェクト。
---生成された擬似ランダムな素数はこのオブジェクトに格納される。
--成功した場合にもこのオブジェクトが返される。
--NULLを指定すると、新しいBIGNUMオブジェクトが返される。
-num
--生成される素数の持つべきビット数。
-safe
--安全な素数を返すかどうかの指定する。
---ここでいう安全な素数とは1を引いて、2で割っても素数である数のことである。
---例えば、[[DH鍵交換]]で使用する素数は安全な素数である必要がある。
-add
--非NULLが指定された場合、生成された素数をこの数で割ったときの余りはrem引数で与えられた値に一致する必要がある。
-rem
--add引数に非NULLが指定された場合、生成された素数をadd引数で割ったときの余りはこの値になる必要がある。
--NULLが指定された場合は、値として1が使用される。
-callback
--素数生成の際に、その進行状況を報告させたい場合に使用するコールバック関数へのポインタ。
--NULLを指定すればコールバックしない。
-cb_arg
--進行状況を監視するコールバック関数が指定された場合、この引数がコールバック関数に直接渡される。

***RANDLIB [#eeeaf894]

-http://www.mlab.ice.uec.ac.jp/~ej-sib/numerical/numerical_random.html

**C++ [#k96a83f2]

***rand() [#v7086ba4]

-C言語のrand()と同様。

**Ruby [#o64c25d1]

**Perl [#l6a4242b]

***rand [#oe2ac2c4]

-「rand EXPR」とすると0以上EXPR未満の擬似乱数を返す。
--EXPRを省略すると、0以上1未満の擬似乱数を返す。
-srandでseedを設定できる。

***Math::Random::MTモジュール [#acfe890f]

-Math::Random::MTモジュールを使うことで簡単にメルセンヌツイスターで生成した擬似乱数を取得することができる。
-「use Math::Random::MT qw(srand rand);」としておけば、後は標準のrandやsrandと同じように使える。

**PHP [#w92a4498]

***rand() [#r6c69632]

-rand()により0以上getrandmax()未満の擬似乱数を返す。・
--[[Windows]]などのではgetrandmax()の値は32768となっている。
---32768より大きい擬似乱数が欲しい場合は、引数ありのrand()を使った方が簡単である。
-rand(int $min, int $max)を使えば、範囲を設定できる。
--指定した最小値と最大値を含む。
-srand()を使えば、seedを設定できる。
-libcの擬似乱数生成器を利用する。

***mt_rand() [#fbfe8677]

-標準のrand()よりも4倍以上高速。
-メルセンヌツイスターを用いて擬似乱数を生成するため、高精度である。
-見た目上は標準のrand()の関数名に「mt_」という接頭語が付いているだけであり、使い方は同じである。
--ただし、引数なしのmt_rand()を使用した場合、0以上mt_getrandmax()未満の値となる。

**VB.NET [#ra805f31]

***Rnd [#rb45af9f]

-Rnd()関数により、0以上1未満の擬似乱数を得ることができる。
-Randomizeステートメントでseedを設定することができる。
-擬似乱数を生成するアルゴリズムは24ビット線形合同法である。

***Randomクラス [#h085031c]

-Randomクラスが用意されています。
-擬似乱数を生成するアルゴリズムはKnuthの減算法である。
-Randomクラスのコンストラクタにseedを設定できる。
--引数無しのコンストラクタを使うと、seedとしてEnvironment.TickCountが使用される。
-Random#Next()により擬似乱数値(Integer)を取得することができる。Next()には引数を持つものと持たないものがあり、持つものを使えば指定する範囲内の擬似乱数値を得ることができる。

例:

Dim rnd As New System.Random()
Dim r1 As Integer = rnd.Next(6)			'0以上6未満の擬似乱数を生成する。
MessageBox.Show(r1.ToString())
Dim r2 As Integer = rnd.Next(-10, 10)	'-10以上10未満の擬似乱数を生成する。
MessageBox.Show(r2.ToString())
Dim r3 As Integer = rnd.Next()			'0以上Int32.MaxValue未満の擬似乱数を生成する。
MessageBox.Show(r3.ToString())
 Dim rnd As New System.Random()
 Dim r1 As Integer = rnd.Next(6)			'0以上6未満の擬似乱数を生成する。
 MessageBox.Show(r1.ToString())
 Dim r2 As Integer = rnd.Next(-10, 10)	'-10以上10未満の擬似乱数を生成する。
 MessageBox.Show(r2.ToString())
 Dim r3 As Integer = rnd.Next()			'0以上Int32.MaxValue未満の擬似乱数を生成する。
 MessageBox.Show(r3.ToString())

-Integer以外の擬似乱数を得るために、NextBytes()やNextDouble()なども存在する。

***RNGCryptoServiceProviderクラス [#o20f3978]

-暗号用の擬似乱数を生成するクラス。

例:

Dim random() As Byte = New Byte(100) {}
Dim rng As New System.Security.Cryptography.RNGCryptoServiceProvider()
rng.GetBytes(random)	'ランダムな100バイト長の配列を作る。
 Dim random() As Byte = New Byte(100) {}
 Dim rng As New System.Security.Cryptography.RNGCryptoServiceProvider()
 rng.GetBytes(random)	'ランダムな100バイト長の配列を作る。

-0以外の擬似ランダムなByte値を得る場合は、GetNonZeroBytes()を使う。


**Java [#a81dec56]

***BigIntegerの乱数 [#cbcb64f9]

 BigIntegerのコンストラクタの第1引数に範囲(nを指定すると、0〜2SUP{n};ビットの範囲)、第2引数にRandamインスタンスを指定すると、BigInteger型の乱数を生成することができる。

 BingInteger int = new BigInteger(int bit , new Random());

 ランダムな素数を得る場合は次のようにする。ただし、probablePrime()の第1引数はMiller-Rabinの繰り返し数なので、例えば1を指定した場合は素数を生成する確率は1/2になる。

 BigInteger primeInt = BigInteger.probablePrime(1, new Random());

***Randomクラス [#d02d092c]

-[[Randomクラス:http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Random.html]]を利用して簡単に乱数を取得することできる。
-擬似乱数を生成するアルゴリズムは48ビット線形合同法である。
-nextInt()の引数でnを与えたときは、戻り値として0〜n-1の範囲の乱数値となる。
-問題点が『Effective Java』の項目47「ライブラリーを知り、ライブラリーを使う」のところに書いてある。 ★

 Random rand = new Random();
 System.out.println(rand.nextInt([数値]));

-nextInt()だと戻り値の型はintであるが、戻り値の型としてboolean,long,double,floatであるメソッドも用意されている。

|メソッド名|戻り値の型|引数を指定しないときの範囲|h
|nextBoolean()|boolean型|true or false|
|nextInt()|int型|-2147483648〜+2147483647|
|nextLong()|long型|-9223372036854775808〜+9223372036854775807|
|nextDouble()|double型|0.0以上1.0未満|
|nextFloat()|float型|0.0以上1.0未満|

-擬似乱数の種(long値)を与えるときはRandonクラスのコンストラクタで設定する。あるいはRandom#setSeed(long)で設定することもできる。

 Random rand = new Random(seed);

***Math.random() [#g43abced]

-0以上1未満のdouble型の擬似乱数を生成するためにはMath.random()を実行する。
-seedを設定する機能がない。

例:指定範囲の整数の擬似乱数を返すメソッド

/**
 * 指定範囲の整数の擬似乱数を返す.
 * <p>最大値、最小値共に擬似乱数の範囲に含まれる.
 * @param max 最大値
 * @param min 最小値
 * @return 擬似乱数
 */
private static int getRandom(final int max, final int min) {
	return (int) Math.floor(Math.random() * (max - min + 1)) + min;
}
 /**
  * 指定範囲の整数の擬似乱数を返す.
  * <p>最大値、最小値共に擬似乱数の範囲に含まれる.
  * @param max 最大値
  * @param min 最小値
  * @return 擬似乱数
  */
 private static int getRandom(final int max, final int min) {
 	return (int) Math.floor(Math.random() * (max - min + 1)) + min;
 }

**シェルスクリプト(bash) [#u0f4aed1]

 RANDOM変数を参照するだけで簡単に擬似乱数を取得することができる。

 $ echo $RANDOM

-この方法で取得できる乱数値は0〜32767の整数である。
-RANDOM変数に値0〜2SUP{32};-1を代入すると、'''擬似乱数列'''を初期化することができる。
-unsetコマンドでRANDOM変数を無効にすると、そのシェル内のRANDOM変数の効力は失う。

**PowerShell [#g7481086]

-Get-Randomコマンドレットが用意されている。
--例:「Get-Random 1000」とすれば、0以上1000未満の擬似乱数を取得できる。


**SQL [#fa622a5b]

***SQL Server [#sa8f2acd]

-RAND()により擬似乱数(0〜1)を取得できる。
-RAND()の引数にseedを指定できる。
-RAND()は呼び出されるごとに異なる擬似乱数を返す。
--ただし、1回のSELECT内で返されるRAND()の値は同じである。

例:fooテーブルに複数行があるとき、SELECTの結果はすべての行が同じ値になる。

 SELECT RAND() FROM foo;

***MySQL [#kd47a6cd]


-RAND()により擬似乱数を取得できる。
-RAND()の引数にseedを指定できる。
-引数を省略すると、呼び出されるごとに、異なる擬似乱数を返す。
--1回のSELECT内でも異なる擬似乱数を返す。

***PostgreSQL [#l1775f8b]

-RANDOM()により擬似乱数を取得できる。
-乱数のseedはSEED変数またはSETSEED関数により指定できる。
--seedは0〜1までの浮動小数点数である。
-1回のSELECT内でも異なる擬似乱数を返す。


*疑似乱数生成器の例 [#o4afd328]

**でたらめな方法 [#l9587f52]

・アルゴリズムを単純に複雑にしただけでは解決できない。
-アルゴリズムを単純に複雑にしただけでは解決できない。
-まず、周期が短くなってしまうという問題がある。複雑にしただけのアルゴリズムを使って数の列を生成させると、多くの場合は短い周期(短い数列の繰り返し)に陥ってしまう。暗号技術で使う乱数は予測不可能性でなければならないので、周期が短いというのはダメである。
-もうひとつの欠点として、プログラマーが詳細を理解できないようなアルゴリズムは古典暗号のようにアルゴリズム自身を秘匿しているだけであり、そのアルゴリズムが数学的に安全であるかどうか評価できないということである。

・まず、周期が短くなってしまうという問題がある。複雑にしただけのアルゴリズムを使って数の列を生成させると、多くの場合は短い周期(短い数列の繰り返し)に陥ってしまう。暗号技術で使う乱数は予測不可能性でなければならないので、周期が短いというのはダメである。

・もうひとつの欠点として、プログラマーが詳細を理解できないようなアルゴリズムは古典暗号のようにアルゴリズム自身を秘匿しているだけであり、そのアルゴリズムが数学的に安全であるかどうか評価できないということである。


**線形合同法 [#f633e883]

・よく使われている疑似乱数生成器だが、暗号技術に使うことはできない。 
-よく使われている疑似乱数生成器だが、暗号技術に使うことはできない。 
-今、RSUB{0};,RSUB{1};,…という疑似乱数の列を作るとする。まず、疑似乱数の種(seed)から、次の計算式を使って最初の疑似乱数RSUB{0};を作る。

・今、RSUB{0};,RSUB{1};,…という疑似乱数の列を作るとする。まず、疑似乱数の種(seed)から、次の計算式を使って最初の疑似乱数RSUB{0};を作る。

&mimetex("R_0 = ( A \times seed + C ) \, mod \, M");

 ここで、A,C,Mは「A<M,C<M」を満たす定数とする。

 次に、RSUB{0};から、次のようにして疑似乱数RSUB{1};を作る。

&mimetex("R_1 = ( A \times R_0 + C ) \, mod \, M");

 以降同様にして、RSUB{n};からRSUB{n+1};を作る。

&mimetex("R_{n+1} = ( A \times R_n + C ) \, mod \, M");

 つまり、現在の疑似乱数の値をA倍してCを加え、さらにMで割った余りを次の疑似乱数とするわけだ。線形合同法では、最後に生成した疑似乱数の値が内部状態になるといえる。

・A,C,Mの値を注意深く選択すれば、無作為性を持つ疑似乱数列を作ることができるが、予測不可能性は持たない。なぜならば、一旦同じ数が出てしまうと、次からは前に出たか数列が繰り返し出てきてしまうからである。これが乱数の周期となってしまう。mを大きい数にすれば周期は長くなるが、結局いつかは同じ数列が出てきてしまう。つまり、線形合同法は暗号技術に使えない。
-A,C,Mの値を注意深く選択すれば、無作為性を持つ疑似乱数列を作ることができるが、予測不可能性は持たない。なぜならば、一旦同じ数が出てしまうと、次からは前に出たか数列が繰り返し出てきてしまうからである。これが乱数の周期となってしまう。mを大きい数にすれば周期は長くなるが、結局いつかは同じ数列が出てきてしまう。つまり、線形合同法は暗号技術に使えない。
-プログラミング言語のライブラリ関数として用意されている疑似乱数生成器の多くが、線形合同法を用いている。例えば、C言語のrand関数、Javaのjava.util.Randomクラスなどがある。よってこうした関数を利用した暗号技術は脆弱といえる。

・プログラミング言語のライブラリ関数として用意されている疑似乱数生成器の多くが、線形合同法を用いている。例えば、C言語のrand関数、Javaのjava.util.Randomクラスなどがある。よってこうした関数を利用した暗号技術は脆弱といえる。


***線形合同法のプログラムによる実験 [#x70ca63c]

 線形合同法で使う各定数は次のように設定しておく。

-a:8で割って5余る数
-c:奇数
-m:2の累乗の数で、できるだけ大きなもの

 次にjavaで動作する線形合同法のプログラム(SenkeiGoudouHou.java)を示す。

#code(java){{
/*
 * 線形合同法による(擬似)乱数の生成
 * 入力:x,a,c,m
 * 出力:擬似乱数:x=(a*x+c) % mの結果
 */
public class SenkeiGoudouHou {

	public static void main(String[] args) {
		int x=0;	//最後に求めた乱数。初期値をセットする。
		int m=0;	//2の累乗の数
		int a=8*5+5;	//8で割って5余る数
		int c=123;	//奇数
		
		try{
			x=Integer.parseInt(args[0]);
			a=Integer.parseInt(args[1]);
			c=Integer.parseInt(args[2]);
			m=Integer.parseInt(args[3]);
		}catch(NumberFormatException e){
			System.out.println("線形合同法による擬似乱数生成");
			System.out.println("SenkeiGoudouHou <x> <a> <c> <m>");
			return;
		}
		
		for(int i=0;i<20;i++){
			x=(a*x+c)%m;
			System.out.println(x+",\t");
		}
	}
}
}}

 上記プログラムを利用して、線形合同法の実験をしてみる。

 >java SenkeiGoudouHou 1 45 123 8
 0,	3,	2,	5,	4,	7,	6,	1,
 0,	3,	2,	5,	4,	7,	6,	1,
 0,	3,	2,	5,

 m=8とすると、10個目に0が登場する。つまり周期が登場している。実際にそれ以降は同じ数列の繰り返しであることを確かめることができる。

 m=4にしてみる。

 >java SenkeiGoudouHou 1 45 123 4
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,

 このとき5個目に0が登場している。確かにmを小さくすると、周期が短くなったことがわかった。

 次のようにmを大きくしてみると、出力される値も大きくなると同時に周期も長くなる。少なくとも20個の出力の中に周期は存在していないことがわかる。

 >java SenkeiGoudouHou 1 45 123 65536
 168,	7683,	18178,	31701,	50412,
 40439,	50406,	40169,	38256,	17707,
 10506,	14141,	46644,	1951,	22382,
 24273,	43832,	6483,	29714,	26533,

 以上の考察より、「引数が同じならば何度でも同じ擬似乱数が生成されること」と「mは小さいといけないこと」がわかる。ところが、サイコロの目の1〜6の擬似乱数を出力したいとする。このためm=6としてしまうと、周期が短くなってしまうという問題が起こる。そこで、m=65,536(=2SUP{16};)のような大きな値で擬似乱数を作り、それを6で割った余りを求めればよいというアイデアが思いつく。

 まとめると、0からn-1までの範囲の乱数を作りたいときには、大きなmで擬似乱数を生成して、それをmod nで考えた出力を擬似乱数として使えばよいということである。これを考慮したJavaプログラム(SenkeiGoudouHou2.java)を次に示す。

#code(java){{
/*
 * 線形合同法による擬似乱数生成(0〜n-1の擬似乱数を求める)
 * 入力:n
 * 出力:0〜n-1の20個の乱数
 */
public class SenkeiGoudouHou2 {
	//クラス変数の定義
	static int x=1;	//最後に求めた乱数。初期値をセットする。
	
	//乱数を求める関数
	//n:n-1までの乱数を求める
	//戻り値:求めた乱数
	static int MyRandom(int n){
		int m=65536;
		int a=8*5+5;
		int c=123;
		x=(a*x+c)%m;
		int r=x%n;
		return r;
	}
	
	//main
	public static void main(String[] args) {
		int n=10000;	//乱数の範囲。引数が指定されなければ、これがデフォルト値に設定される。
		
		if(args.length==1){
			try{
				n=Integer.parseInt(args[0]);
			}catch(NumberFormatException e){
				System.out.println("線形合同法による擬似乱数表示(0からn-1の擬似乱数)");
				System.out.println("SenkeiGoudouHou2 <n> n:求める範囲");
				return;
			}
		}
		
		//乱数を20個作って表示
		for(int i=0;i<20;i++){
			int r=MyRandom(n);
			System.out.println(r+",\t");
		}
	}
}
}}

 引数に4と2を指定したときの場合は次のようになる。

 >java SenkeiGoudouHou2 2
 0,	1,	0,	1,
 0,	1,	0,	1,
 0,	1,	0,	1,
 0,	1,	0,	1,
 0,	1,	0,	1,
 
 >java SenkeiGoudouHou2 4
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,
 0,	3,	2,	1,

 mは65,536なので、周期は長いはずだが、2,4の場合はそれぞれ周期が2,4となってしまっている。なぜならば、線形合同法には、下位の桁がランダムではなくなるという問題が生じてしまうのである。ランダムでないものをさらにnで割った余りはもちろんランダムでなくなる。例えば、n=4で、6XXを割った余りを求めると、600は4で割り切れるから、XXだけが余りの計算に使われるのである。~
 この問題を修正するには、上位の桁に注目すればよい。なぜならば、上位の桁はランダムだからである。上位の桁を使うには、xを2で割っていき、nの2倍よりも小さくなったら、余りを求めるようにすればよい。上記プログラム(SenkeiGoudouHou2.java)内に登場したMyRandomメソッドを次のように変更すればよい。

 	static int MyRandom(int n){
 		int m=65536;
 		int a=8*5+5;
 		int c=123;
 		x=(a*x+c)%m;
 		int r=x;
 
 		//rがnの2倍より大きい間繰り返す
 		while(r >= n*2){
 			//rを2で割る
 			r /= 2;
 		}
 		//rをnで割った余りを考える
 		r %= n;
 
 		return r;
 	}

 この修正版MyRandomメソッドに変更したプログラム(SenkeiGoudouHou3.java)は次の通りである。

 >java SenkeiGoudouHou3 4
 1,	3,	0,	3,	2,	0,
 2,	0,	0,	0,	1,	2,
 1,	3,	1,	1,	1,	2,
 3,	2,

**一方向ハッシュ関数を使う方法 [#ob3907c7]

・一方向[[ハッシュ関数]]を使って、予測不可能性を持った疑似乱数列(強い疑似乱数)を生成する疑似乱数生成器が作れる。

#img(http://s-akademeia.sakura.ne.jp/main/image8/itihoukou_giji.jpg)
#img(,clear)

・アドバーサリーが次の疑似乱数を予測するためには、現在のカウンターの値を知る必要がある。カウンターの値を知るためには、一方向ハッシュ関数の一方向性を破らなければならないのである。これは極めて困難なので、アドバーサリーは次の疑似乱数を予測できない。つまり、この疑似乱数生成器は、一方向ハッシュ関数の一方向性が疑似乱数生成器の予測不可能性を支えている。


**メルセンヌ・ツイスターを使う方法 [#yf287d52]


**M系列乱数を使う方法 [#v966b6df]


**暗号を使う方法 [#l4534155]

・暗号を使い、強い疑似乱数を生成する疑似乱数生成器を作ることができる。 
-暗号を使い、強い疑似乱数を生成する疑似乱数生成器を作ることができる。 
-このときの暗号はAESのような対象暗号であっても、[[RSA暗号]]のような公開鍵暗号であってもよい。

・このときの暗号はAESのような対象暗号であっても、RSAのような公開鍵暗号であってもよい。

#img(http://s-akademeia.sakura.ne.jp/main/image8/angou_giji.jpg)
#img(,clear)

・アドバーサリーが次の疑似乱数を予測するためには、現在のカウンターの値を知る必要がある。しかし、これまでに出力された疑似乱数列は、暗号文に相当するので、カウンターの値を知るというのは、暗号を解読することに他ならない。これは極めて困難なので、アドバーサリーは次の疑似乱数を予測できない。つまり、この疑似乱数生成器では暗号の機密性が疑似ランダム生成器の予測不可能性を支えていることになる。 
-アドバーサリーが次の疑似乱数を予測するためには、現在のカウンターの値を知る必要がある。しかし、これまでに出力された疑似乱数列は、暗号文に相当するので、カウンターの値を知るというのは、暗号を解読することに他ならない。これは極めて困難なので、アドバーサリーは次の疑似乱数を予測できない。つまり、この疑似乱数生成器では暗号の機密性が疑似ランダム生成器の予測不可能性を支えていることになる。 

・暗号を使った疑似乱数生成器の具体的なものとして、ANSI X9.17およびANSI X9.31のAppendixに記述されている方法がある。これは暗号ソフトウェアの[[PGP]]でも使われている。
-暗号を使った疑似乱数生成器の具体的なものとして、ANSI X9.17およびANSI X9.31のAppendixに記述されている方法がある。これは暗号ソフトウェアの[[PGP]]でも使われている。


*疑似乱数生成器に対するアタック [#t81e12c2]

・一般には暗号に対するアタックの影に隠れて、疑似乱数生成器の存在はあまり意識されない。しかし、疑似乱数成績は鍵を作るという重要な役目を持っているので、アドバーサリーの攻撃対象となりやすい。 
-一般には暗号に対するアタックの影に隠れて、疑似乱数生成器の存在はあまり意識されない。しかし、疑似乱数成績は鍵を作るという重要な役目を持っているので、アドバーサリーの攻撃対象となりやすい。 

**種(seed) [#j44b09f0]

・疑似乱数の種は、暗号の鍵に匹敵する重要性を持つ。 
-[[疑似乱数]]の種は、暗号の鍵に匹敵する重要性を持つ。 
-疑似乱数の種がアドバーサリーに知られてしまえば、その疑似ランダム生成器が生成する疑似乱数列はすべてアアドバーサリーに知られたことになる(疑似ランダム生成器で使われているアルゴリズムは、攻撃者に知られていることを仮定する)。よって、疑似乱数の種はアドバーサリーに秘密にしなければならない。 
-種をアドバーサリーに知られないようにするためには、再現不可能性を持つ真の乱数自体を種にすることである。 

・疑似乱数の種がアドバーサリーに知られてしまえば、その疑似ランダム生成器が生成する疑似乱数列はすべてアアドバーサリーに知られたことになる(疑似ランダム生成器で使われているアルゴリズムは、攻撃者に知られていることを仮定する)。よって、疑似乱数の種はアドバーサリーに秘密にしなければならない。 

・種をアドバーサリーに知られないようにするためには、再現不可能性を持つ真の乱数自体を種にすることである。 


**ランダムプールに対するアタック [#xd4be8a9]

・必要になったときにその場で真の乱数を作り出すのではなく、ランダムプールと呼ばれるファイルにランダムなビット列を蓄えておく方法がある。暗号ソフトウェアが疑似乱数の種を必要とする時は、このランダムプールから必要なだけのランダムのビット列を取り出して使う。 
-必要になったときにその場で真の乱数を作り出すのではなく、[[ランダムプール]]と呼ばれるファイルにランダムなビット列を蓄えておく方法がある。暗号ソフトウェアが疑似乱数の種を必要とする時は、このランダムプールから必要なだけのランダムのビット列を取り出して使う。 
-もし、アドバーサリーにこのランダムプールの内容を知られてしまうと、疑似乱数の種を予測されてしまう可能性がある。

・もし、アドバーサリーにこのランダムプールの内容を知られてしまうと、疑似乱数の種を予測されてしまう可能性がある。


*PRGの数論的構築 [#l6b1e051]

**one-way functionからPRGを作る [#mcdf9de1]

[定理]~
「one-way functionが存在する」~
⇒「length-tripling pseudo random generator(PRG)が存在する」

[定義]~
「&mimetex("G= \{ G_k : \{ 0,1 \}^k \to \{ 0,1 \}^{3k} \}_{k \in \mathbb{N}}");:PRG」~
⇔SUP{def};「&mimetex("\forall D \( PPT \, distinguisher \) | Pr [ x \overset{$}{\leftarrow} \{ 0,1 \}^{3k} : D \( x \) =1 ] - Pr [ s \overset{$}{\leftarrow} \{ 0,1 \}^k ; x=G_k \( s \) : D \( x \) =1 ] |:neg");」

 言い換えると、次が成り立つ。

&mimetex("U_{3k} \approx G \( U_k \)");

 ここで、USUB{k};はkビットストリングの一様分布を意味する。


*擬似乱数生成器の応用例 [#b9fb0647]

 暗号の中では乱数が使われる。例えば、次の場面で使われる。

-共通鍵暗号系の秘密鍵の生成
-公開鍵暗号系やデジタル署名におけるデータ生成
-ストリーム暗号


*参考文献 [#gaeabe54]

-『最新暗号技術』
-『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』