ハードウェア乱数生成ルーチンhdrand.c  by とつげき東北  トップページに戻る





「ランダムな乱数」「良質な乱数」を得る

導入:

プログラミングをしていて、「真にランダムな乱数」を得ようとしたときに困ることがある。
どんなに優れた決定論的擬似乱数ルーチンも、真にランダムな乱数を作ってはくれない。
結果としてtime値などを乱数の種にすることになるわけだ。
ゲームなどならその程度でも充分だが、セキュリティの重要なソフトではそうはいかず、ユーザのマウス入力のタイミングなどを読み取る必要が出てくる。
そこでCPUがPentium以降・Windows下でハードディスクが使用されている環境で、ユーザに不可解な入力作業をさせることなく、良い性質の乱数を得るためのルーチンを作っておく。


方法:

テンポラリファイルフォルダにファイルを作成・削除し、その処理にかかった時間を高分解能パフォーマンスカウンタで計測して、処理時間を得る。
処理時間のビット列のうち、偏らないビットを乱数ビットとして利用する。
ハードディスクのシーク時間や物理的な書き込み速度は、キャッシュや温度や湿度やWindowsの処理順などによってばらつきがあるので、良質なランダムビットがとれる。
測定されるビットの変化を最初にテストしておくことで(100回のビット発生で、充分に変化が見られたビットだけを乱数に使用する)、処理速度の違いや、パフォーマンスカウンタの質の悪さ(例えば最下位ビットが必ず偶数や奇数になる可能性)も吸収できる。

当然、専用のハードウェアを用いるのと比較して動作速度は遅い(1000ビット/1秒・・・とつげき東北の環境で)が、「真の乱数」は普通は1000ビットもあればかなり充分だろう。
このルーチンが必要とする「Pentium以降・Windows・要ハードディスク」という敷居は、少なくとも専用ハードウェアよりはずっと低いものだ。
ユーザにマウスを振らせるよりずっと早く、ずっと良質な乱数が得られることだろう。
なお、この方式で生成した乱数列は、乱数評価の有名なテストDIEHARDテスト合格した(MTのDIEHARD結果はこちら)。
MTのような、周期の長い良質な擬似乱数の種としてこれを使えば、暗号ツールなどに実用的に応用できる。

より良い一様乱数を得る必要があるなどの目的に応じて、hdrand_test関数内のテストは各々調整すると良い。


関数:

int hdrand_init()

テンポラリファイルを用意するための関数。全ての動作の前にこれを1度だけ呼び出しておく。
ここでのエラーは特にチェックする必要はない。hdrand_test()での返り値だけをチェックすれば充分。
返り値
0 通常終了
-1 テンポラリファイルが作成できないのでhdrandはつかえない。


int hdrand_test()

実際にいくつかの乱数を発生させ、乱数として使用可能なビット情報をグローバル変数に格納する。
プログラムの最初で、initの後に1度だけ必ず呼び出し、エラーが出てさえいなければそれ以降は意識しなくて良い。
1度失敗しても(返り値-1でも)、その後成功する可能性もあるので何度かリトライした方が良い。

返り値
n nビットが乱数として使用可能。
0 使用可能な乱数ビットが存在しない。
-1 使用可能な乱数ビットが存在しない。その環境ではhdrandが使えない。

具体的な動作
hdrand_generate()で乱数ビットを100回生成する。
前回のビットと今回のビットが40〜60回変化していれば、そのビットは「合格」である。
合格になったビットが1ビット以上存在すれば、この関数は-1以外の値を返す。


int hdrand_generate()

実際に乱数を作るルーチン。内部でだけ使用する。


int hdrand32()

32ビットの信頼できる乱数ビット列を返す。
最初に初期化(initとtest)を行った後は、これを呼び出すだけで良質な乱数ビット列を取得できる。


int hdrandbit()

1ビットの信頼できる乱数ビットを返す。
hdrand_generateによって生成されるビット列の「有効な上位ビット」部分は少し偏る可能性があるので、より完全な乱数を得たい場合はこちらを利用する。
ただしある程度長い同じ長さのビット数を得る場合、hdrand32の方が高速である。


テストプログラム例(Borland C++ Builder)

#include"stdio.h"

main(void)
{
//準備とエラーチェック
int noerr=0;
hdrand_init();
for(int retry=0;retry<16;retry++)if(hdrand_test()!=-1){noerr=1;break;}
if(noerr==0){ShowMessage("乱数が使えません");exit(0);}
//実際に乱数を生成する
for(int r=0;r<10;r++)ShowMessage(hdrand32());
}



実装:

ヘッダ部(グローバル):(必要ならstaticにすること。関数のプロトタイプ宣言も必要ならすること)

_LARGE_INTEGER hdrand_PC; //高分解能パフォーマンスカウンタのカウント値参照用
DWORD hdrand_value; //ジェネレータが返す真の値
int hdrand_Rshift; //hdrandのジェネレータが返す値の右何ビットが使えないか
int hdrand_Lshift; //hdrandのジェネレータが返す値の何ビットが使用可能か
char hdrand_buf[MAX_PATH]; //ファイルネーム保持用
FILE * hdrand_str; //ファイル入出力用

関数部:

int hdrand_init()
{
if(GetTempPath(MAX_PATH,hdrand_buf)==0)return -1; //テンポラリファイルフォルダを取得
strcat(hdrand_buf,"temprnd.tmp\0"); //仮のテンポラリファイル。ちゃんとやるならGetTempFileNameで。
return 0;
}

int hdrand_generate()
{
QueryPerformanceCounter(&hdrand_PC);
hdrand_value=hdrand_PC.LowPart;

hdrand_str=fopen(hdrand_buf,"wb");
if(hdrand_str==NULL)return -1;
fwrite(hdrand_str,1,1,hdrand_str);
fclose(hdrand_str);
DeleteFile(hdrand_buf);

QueryPerformanceCounter(&hdrand_PC);
hdrand_value=(hdrand_PC.LowPart^hdrand_value);
}


int hdrand_test()
{
bool bits[64];
bool lastbits[64];
int henka[64];
int h_b;

memset(henka,0,sizeof(int)*8);

for(int j=0;j<100;j++)
{
hdrand_generate();
h_b=hdrand_value;
for(int i=0;i<sizeof(int)*8-1;i++)
{
bits[i]=(h_b & 1);
h_b = h_b >> 1;
henka[i]+=bits[i]!=lastbits[i];
lastbits[i]=bits[i];
}
}

hdrand_Rshift=255;
hdrand_Lshift=-1;
for(int i=0;i<sizeof(int)*8-1;i++)
{
if((henka[i]>=40)&&(henka[i]<=60))
{
if(i<hdrand_Rshift)hdrand_Rshift=i;
if(i>=hdrand_Lshift)hdrand_Lshift=i-hdrand_Rshift+1;
}
else break;
}
if(hdrand_Rshift==255)return -1;
if(hdrand_Lshift<=0)return -1;
return hdrand_Lshift;
}


//ランダムな32ビットの乱数を返す。
int hdrand32()
{
unsigned int tmp=0;
unsigned int h_v;
int totalbit=0;
while(1)
{
VNhdrand_generate();
h_v=hdrand_value >> hdrand_Rshift;
for(int j=0;j<hdrand_Lshift;j++)
{
tmp+=h_v & 1;
h_v=h_v >> 1;
totalbit++;
if(totalbit>=32)return tmp;
tmp=tmp<<1;
}
}

}


//ランダムな1ビットの乱数を返す。
int hdrandbit()
{
hdrand_generate();
return (hdrand_value >> hdrand_Rshift ) &1 ;
}


注意

hdrand32()は、書き込みにかかった時間の上位の方のビットも利用する(その変化が充分に大きい限り)。
そのため、より良い乱数を得るためには、hdrand_generateによる返り値hdrand_valueの下位ビットの方を利用するようにした方が良いかもしれない。
実用上充分だと思うが、そのあたりの調整をする場合各自でソースをいじるように。

このプログラムを利用して発生したいかなる損害にも、作者とつげき東北は責任を負わない。各自の責任の下に使用すること。
改良、自作ソフトへの組み込み等は全て自由。このページの内容を著作権だけを変更して、そのまま自分のHPに書くようなことはしないように(著作権法に違反する)。
このページは2002/04/21に公開された。