linux glibcのrand関数のソースコードを読んでみましょう。
どうやって乱数を生成しているのか調べてみましょう。全く怖くありません。
まず乱数についてですが、真性乱数と擬似乱数に分類されます。glibcの乱数は周期性があるため擬似乱数となります。優秀な擬似乱数としてはメルセンヌ・ツイスタ乱数があります。暗号に使われるのは真性乱数の方ですね。難しそうな説明はここまで。w
glibc ダウンロードディレクトリ glibc-2.22.tar.gz
rand関数は解凍してstdlibディレクトリのrandom.cとrandom_r.cに書かれています。
ソースコードを読む、というよりパクって実装して動かしてみると理解できます。
まず今は使われていない昔のrand関数を書いていきます。
oldrand.c
#include <stdio.h>
#include <stdlib.h>
/* x**31 + x**3 + 1. */
#define TYPE_3 3
#define BREAK_3 128
#define DEG_3 31
#define SEP_3 3
//実はこの乱数テーブルをいじっているだけ 昔の乱数は2番目の-1726662223しか使っていない
static int32_t randtbl[DEG_3 + 1] =
{
TYPE_3,
-1726662223, 379960547, 1735697613, 1040273694, 1313901226,
1627687941, -179304937, -2073333483, 1780058412, -1989503057,
-615974602, 344556628, 939512070, -1249116260, 1507946756,
-812545463, 154635395, 1388815473, -1926676823, 525320961,
-1009028674, 968117788, -123449607, 1284210865, 435012392,
-2017506339, -911064859, -370259173, 1132637927, 1398500161,
-205601318,
};
static struct random_data unsafe_state =
{
.fptr = &randtbl[SEP_3 + 1],
.rptr = &randtbl[1],
.state = &randtbl[1],
.rand_type = TYPE_3,
.rand_deg = DEG_3,
.rand_sep = SEP_3,
.end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};
void oldrand(struct random_data *buf, int *result)
{
int *state;
state = buf->state;
int val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; //randtbl[1]をごちゃごちゃいじっているだけ
state[0] = val;
*result = val;
}
int main()
{
int i, result;
for (i = 0; i < 10; i++) {
oldrand(&unsafe_state, &result);
printf("oldrand = %d\n", result);
}
return 0;
}
$ gcc oldrand.c -o oldrand
./oldrand
oldrand = 897822358
oldrand = 105331223
oldrand = 617672196
oldrand = 1888665581
oldrand = 1128537634
oldrand = 1434149043
oldrand = 980477552
oldrand = 1927835113
oldrand = 1772747374
oldrand = 1723946255
これが昔のrand関数です。randtblという乱数テーブルを用意していますが、たった一つしか使っていません。
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
ここで数字をいじっているだけです。
次は現在使われている乱数
myrand.c
#include <stdio.h>
#include <stdlib.h>
/* x**31 + x**3 + 1. */
#define TYPE_0 0
#define TYPE_3 3
#define BREAK_3 128
#define DEG_3 31
#define SEP_3 3
//実はこの乱数テーブルをいじっているだけ ポインタを使って順送りしているだけ。最後まで行ったら最初に戻る
static int32_t randtbl[DEG_3 + 1] =
{
TYPE_3,
-1726662223, 379960547, 1735697613, 1040273694, 1313901226,
1627687941, -179304937, -2073333483, 1780058412, -1989503057,
-615974602, 344556628, 939512070, -1249116260, 1507946756,
-812545463, 154635395, 1388815473, -1926676823, 525320961,
-1009028674, 968117788, -123449607, 1284210865, 435012392,
-2017506339, -911064859, -370259173, 1132637927, 1398500161,
-205601318,
};
static struct random_data unsafe_state =
{
.fptr = &randtbl[SEP_3 + 1],
.rptr = &randtbl[1],
.state = &randtbl[1],
.rand_type = TYPE_3,
.rand_deg = DEG_3,
.rand_sep = SEP_3,
.end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};
void myrand(struct random_data *buf, int *result)
{
int *state;
int32_t *fptr = buf->fptr;
int32_t *rptr = buf->rptr;
int32_t *end_ptr = buf->end_ptr;
int32_t val;
val = *fptr += *rptr;
/* Chucking least random bit. */
*result = (val >> 1) & 0x7fffffff; //ここで数字をいじる。他はポインタの書き換えでしかない
++fptr;
if (fptr >= end_ptr) {
fptr = state;
++rptr;
} else {
++rptr;
if (rptr >= end_ptr)
rptr = state;
}
buf->fptr = fptr;
buf->rptr = rptr;
}
int main()
{
int i, result;
for (i = 0; i < 10; i++) {
myrand(&unsafe_state, &result);
printf("oldrand = %d\n", result);
}
return 0;
}
$ gcc myrand.c -o myrand
$ ./myrand
oldrand = 1804289383
oldrand = 846930886
oldrand = 1681692777
oldrand = 1714636915
oldrand = 1957747793
oldrand = 424238335
oldrand = 719885386
oldrand = 1649760492
oldrand = 596516649
oldrand = 1189641421
難しそうですがやっていることはポインタを使って読み込むrandtblのアドレスを書き換えているだけです。
もちろん、これだけだと毎回同じ乱数が生成されます。
srandは与えられた種を元にrandtblのデータを書き換えているだけです。
それで毎回異なる乱数を生成することができるようになります。
仕組みは恐ろしく簡単です。
それよりも注意が必要なのは関数の実態がわかりづらいことです。
random.cの中でsrandが関連付けられています。
weak_alias (__srandom, srand) とあります。
srandを呼び出すと__srandomに変換されますよ、という意味。
さらに__srandom_r関数へと変換されて、random_r.cファイルの中で定義されています。
つまりsrand 関数は内部では __srandom_r 関数になります。
仕組みはこんなもんです。この調子でglibcのソースコードを読んでいきましょう。
どうやって乱数を生成しているのか調べてみましょう。全く怖くありません。
まず乱数についてですが、真性乱数と擬似乱数に分類されます。glibcの乱数は周期性があるため擬似乱数となります。優秀な擬似乱数としてはメルセンヌ・ツイスタ乱数があります。暗号に使われるのは真性乱数の方ですね。難しそうな説明はここまで。w
glibc ダウンロードディレクトリ glibc-2.22.tar.gz
rand関数は解凍してstdlibディレクトリのrandom.cとrandom_r.cに書かれています。
ソースコードを読む、というよりパクって実装して動かしてみると理解できます。
まず今は使われていない昔のrand関数を書いていきます。
oldrand.c
#include <stdio.h>
#include <stdlib.h>
/* x**31 + x**3 + 1. */
#define TYPE_3 3
#define BREAK_3 128
#define DEG_3 31
#define SEP_3 3
//実はこの乱数テーブルをいじっているだけ 昔の乱数は2番目の-1726662223しか使っていない
static int32_t randtbl[DEG_3 + 1] =
{
TYPE_3,
-1726662223, 379960547, 1735697613, 1040273694, 1313901226,
1627687941, -179304937, -2073333483, 1780058412, -1989503057,
-615974602, 344556628, 939512070, -1249116260, 1507946756,
-812545463, 154635395, 1388815473, -1926676823, 525320961,
-1009028674, 968117788, -123449607, 1284210865, 435012392,
-2017506339, -911064859, -370259173, 1132637927, 1398500161,
-205601318,
};
static struct random_data unsafe_state =
{
.fptr = &randtbl[SEP_3 + 1],
.rptr = &randtbl[1],
.state = &randtbl[1],
.rand_type = TYPE_3,
.rand_deg = DEG_3,
.rand_sep = SEP_3,
.end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};
void oldrand(struct random_data *buf, int *result)
{
int *state;
state = buf->state;
int val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; //randtbl[1]をごちゃごちゃいじっているだけ
state[0] = val;
*result = val;
}
int main()
{
int i, result;
for (i = 0; i < 10; i++) {
oldrand(&unsafe_state, &result);
printf("oldrand = %d\n", result);
}
return 0;
}
$ gcc oldrand.c -o oldrand
./oldrand
oldrand = 897822358
oldrand = 105331223
oldrand = 617672196
oldrand = 1888665581
oldrand = 1128537634
oldrand = 1434149043
oldrand = 980477552
oldrand = 1927835113
oldrand = 1772747374
oldrand = 1723946255
これが昔のrand関数です。randtblという乱数テーブルを用意していますが、たった一つしか使っていません。
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
ここで数字をいじっているだけです。
次は現在使われている乱数
myrand.c
#include <stdio.h>
#include <stdlib.h>
/* x**31 + x**3 + 1. */
#define TYPE_0 0
#define TYPE_3 3
#define BREAK_3 128
#define DEG_3 31
#define SEP_3 3
//実はこの乱数テーブルをいじっているだけ ポインタを使って順送りしているだけ。最後まで行ったら最初に戻る
static int32_t randtbl[DEG_3 + 1] =
{
TYPE_3,
-1726662223, 379960547, 1735697613, 1040273694, 1313901226,
1627687941, -179304937, -2073333483, 1780058412, -1989503057,
-615974602, 344556628, 939512070, -1249116260, 1507946756,
-812545463, 154635395, 1388815473, -1926676823, 525320961,
-1009028674, 968117788, -123449607, 1284210865, 435012392,
-2017506339, -911064859, -370259173, 1132637927, 1398500161,
-205601318,
};
static struct random_data unsafe_state =
{
.fptr = &randtbl[SEP_3 + 1],
.rptr = &randtbl[1],
.state = &randtbl[1],
.rand_type = TYPE_3,
.rand_deg = DEG_3,
.rand_sep = SEP_3,
.end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};
void myrand(struct random_data *buf, int *result)
{
int *state;
int32_t *fptr = buf->fptr;
int32_t *rptr = buf->rptr;
int32_t *end_ptr = buf->end_ptr;
int32_t val;
val = *fptr += *rptr;
/* Chucking least random bit. */
*result = (val >> 1) & 0x7fffffff; //ここで数字をいじる。他はポインタの書き換えでしかない
++fptr;
if (fptr >= end_ptr) {
fptr = state;
++rptr;
} else {
++rptr;
if (rptr >= end_ptr)
rptr = state;
}
buf->fptr = fptr;
buf->rptr = rptr;
}
int main()
{
int i, result;
for (i = 0; i < 10; i++) {
myrand(&unsafe_state, &result);
printf("oldrand = %d\n", result);
}
return 0;
}
$ gcc myrand.c -o myrand
$ ./myrand
oldrand = 1804289383
oldrand = 846930886
oldrand = 1681692777
oldrand = 1714636915
oldrand = 1957747793
oldrand = 424238335
oldrand = 719885386
oldrand = 1649760492
oldrand = 596516649
oldrand = 1189641421
難しそうですがやっていることはポインタを使って読み込むrandtblのアドレスを書き換えているだけです。
もちろん、これだけだと毎回同じ乱数が生成されます。
srandは与えられた種を元にrandtblのデータを書き換えているだけです。
それで毎回異なる乱数を生成することができるようになります。
仕組みは恐ろしく簡単です。
それよりも注意が必要なのは関数の実態がわかりづらいことです。
random.cの中でsrandが関連付けられています。
weak_alias (__srandom, srand) とあります。
srandを呼び出すと__srandomに変換されますよ、という意味。
さらに__srandom_r関数へと変換されて、random_r.cファイルの中で定義されています。
つまりsrand 関数は内部では __srandom_r 関数になります。
仕組みはこんなもんです。この調子でglibcのソースコードを読んでいきましょう。