Linuxの擬似乱数解析について
7829 ワード
rand関数
関数の説明:rand()は、0～RAND_の範囲のランダムな数値を返します.MAX間.この関数を呼び出して乱数を生成する前に、srand()を使用して乱数シードを設定する必要があります.乱数シードを設定していない場合、rand()は呼び出し時に自動的に乱数シードを1に設定します.乱数シードについてはsrand()の戻り値を参照してください.0からRAND_に戻ります.MAX間の乱数、RAND_MAXはstdlibで定義.h,その値は2147483647
srand関数
関数の説明:srand()はrand()が乱数を生成するときの乱数シードを設定するために使用されます.パラメータseedは整数でなければなりません.通常、geypid()またはtime(0)の戻り値をseedとして使用できます.seedのたびに同じ値を設定すると、rand()によって生成されるランダムな数値は毎回同じになります.
Linux乱数解析
最も一般的な乱数過程,すなわちsrand−>randの過程は,得られた乱数に基づいて種子を逆方向に放出することを目的とする.
unsafe_state:
srand関数:
srandの具体的な実装は__ですsrandom_r,パラメータseedがシード,bufが上のunsafe_state. ここでは主にseedをベースにstate[0]と表記し、state[i]=(16807*state[i-1])%2147483647を実現する.
rand関数:
randの具体的な実装は_random_r,パラメータbufは依然として上のunsafe_state,resultは私たちが返したランダム数です.
疑似コード:
以上の解析により,後続seedに基づいて乱数と対応するstateを得ることができるようになった.
コードの簡略化:
予測:上に&0 x 7 fffffffが存在し、かつ2で割ることも存在することが分かるので、予測に成功する場合はr[i-31]とr[i-3]ともに&0 x 7 fffffffは存在しない.これはr[i]=((r[i-31]<<1)+(r[i-3]<<1))に対応する乱数か(r[i]>>1)&0 x 7 fffffffffffかであるが、実際にはさらに簡単であり、我々が得たのは乱数であるため、このようなものである.
rand[i]=(r[i]>>1)&0 x 7 fffffff r[i]=(r[i−31]<<1)+(r[i−3]<<1))rand[i−3]=(r[i−3]>>1)&0 x 7 fffffffffffffff rand[i−31]=(r[i−31]>>1)&0 x 7 fffffffffffffffff総合:rand[i]=((r[i−31]<<1)+(r[i−31]<<1)&0 x 7 fffffffffffffffffffff発売rand[i]=(rand[i](rand[i](rand[i]-3]+(rand[i]+(r[i rand[i-31]&0 x 7 fffffffしかし2で割った原因があるため、1の誤差がある可能性がある
関数の説明:rand()は、0～RAND_の範囲のランダムな数値を返します.MAX間.この関数を呼び出して乱数を生成する前に、srand()を使用して乱数シードを設定する必要があります.乱数シードを設定していない場合、rand()は呼び出し時に自動的に乱数シードを1に設定します.乱数シードについてはsrand()の戻り値を参照してください.0からRAND_に戻ります.MAX間の乱数、RAND_MAXはstdlibで定義.h,その値は2147483647
srand関数
関数の説明:srand()はrand()が乱数を生成するときの乱数シードを設定するために使用されます.パラメータseedは整数でなければなりません.通常、geypid()またはtime(0)の戻り値をseedとして使用できます.seedのたびに同じ値を設定すると、rand()によって生成されるランダムな数値は毎回同じになります.
Linux乱数解析
最も一般的な乱数過程,すなわちsrand−>randの過程は,得られた乱数に基づいて種子を逆方向に放出することを目的とする.
unsafe_state:
146 static int32_t randtbl[DEG_3 + 1] =
147 {
148 TYPE_3,
149
150 -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
151 1627687941, -179304937, -2073333483, 1780058412, -1989503057,
152 -615974602, 344556628, 939512070, -1249116260, 1507946756,
153 -812545463, 154635395, 1388815473, -1926676823, 525320961,
154 -1009028674, 968117788, -123449607, 1284210865, 435012392,
155 -2017506339, -911064859, -370259173, 1132637927, 1398500161,
156 -205601318,
157 };
160 static struct random_data unsafe_state =
161 {
162 /* FPTR and RPTR are two pointers into the state info, a front and a rear
163 pointer. These two pointers are always rand_sep places apart, as they
164 cycle through the state information. (Yes, this does mean we could get
165 away with just one pointer, but the code for random is more efficient
166 this way). The pointers are left positioned as they would be from the call:
167 initstate(1, randtbl, 128);
168 (The position of the rear pointer, rptr, is really 0 (as explained above
169 in the initialization of randtbl) because the state table pointer is set
170 to point to randtbl[1] (as explained below).) */
171
172 .fptr = &randtbl[SEP_3 + 1], //
173 .rptr = &randtbl[1], //
174
175 /* The following things are the pointer to the state information table,
176 the type of the current generator, the degree of the current polynomial
177 being used, and the separation between the two pointers.
178 Note that for efficiency of random, we remember the first location of
179 the state information, not the zeroth. Hence it is valid to access
180 state[-1], which is used to store the type of the R.N.G.
181 Also, we remember the last location, since this is more efficient than
182 indexing every time to find the address of the last element to see if
183 the front and rear pointers have wrapped. */
184
185 .state = &randtbl[1], // randtbl ，state srand ，
186
187 .rand_type = TYPE_3, // 3
188 .rand_deg = DEG_3, // state 31， state randtbl[1] ，randtbl[0] TYPE_3
189 .rand_sep = SEP_3, // 3
190
191 .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])] // randtbl
192 };
srand関数:
srandの具体的な実装は__ですsrandom_r,パラメータseedがシード,bufが上のunsafe_state. ここでは主にseedをベースにstate[0]と表記し、state[i]=(16807*state[i-1])%2147483647を実現する.
161 __srandom_r (unsigned int seed, struct random_data *buf)
162 {
163 int type;
164 int32_t *state;
165 long int i;
166 int32_t word;
167 int32_t *dst;
168 int kc;
169
170 if (buf == NULL)
171 goto fail;
172 type = buf->rand_type; // type 3
173 if ((unsigned int) type >= MAX_TYPES)
174 goto fail;
175
176 state = buf->state; // state randtbl[1]
177 /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
178 if (seed == 0) // seed 0 1
179 seed = 1;
180 state[0] = seed; // state[0] seed， TYPE_3
181 if (type == TYPE_0)
182 goto done;
183 // state[1] ， state[i] = (16807 * state[i - 1]) % 2147483647
184 dst = state; // dst state[i]
185 word = seed; // word state[i-1]
186 kc = buf->rand_deg; // kc=31， table
187 for (i = 1; i < kc; ++i) // 30
188 {
189 /* This does:
190 state[i] = (16807 * state[i - 1]) % 2147483647;
191 but avoids overflowing 31 bits. */
192 long int hi = word / 127773;
193 long int lo = word % 127773;
194 word = 16807 * lo - 2836 * hi;
195 if (word < 0)
196 word += 2147483647;
197 *++dst = word;
198 }
199
200 buf->fptr = &state[buf->rand_sep]; // fptr state[3]
201 buf->rptr = &state[0]; // rptr state[0]
202 kc *= 10; // 310
203 while (--kc >= 0) // __random_r 310
204 {
205 int32_t discard;
206 (void) __random_r (buf, &discard);
207 }
208
209 done:
210 return 0;
211
212 fail:
213 return -1;
214 }
rand関数:
randの具体的な実装は_random_r,パラメータbufは依然として上のunsafe_state,resultは私たちが返したランダム数です.
352 int
353 __random_r (struct random_data *buf, int32_t *result)
354 {
355 int32_t *state;
356
357 if (buf == NULL || result == NULL)
358 goto fail;
359
360 state = buf->state;
361
362 if (buf->rand_type == TYPE_0)
363 {
364 int32_t val = state[0];
365 val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
366 state[0] = val;
367 *result = val;
368 }
369 else // type=3，
370 {
371 int32_t *fptr = buf->fptr;
372 int32_t *rptr = buf->rptr;
373 int32_t *end_ptr = buf->end_ptr;
374 int32_t val;
375
376 val = *fptr += *rptr;
377 /* Chucking least random bit. */
378 *result = (val >> 1) & 0x7fffffff;
379 ++fptr;
380 if (fptr >= end_ptr)
381 {
382 fptr = state;
383 ++rptr;
384 }
385 else
386 {
387 ++rptr;
388 if (rptr >= end_ptr)
389 rptr = state;
390 }
391 buf->fptr = fptr;
392 buf->rptr = rptr;
393 }
394 return 0;
395
396 fail:
397 __set_errno (EINVAL);
398 return -1;
399 }
疑似コード:
以上の解析により,後続seedに基づいて乱数と対応するstateを得ることができるようになった.
#include
#define MAX 1000
#define seed 1
#int main() {
int r[MAX],i,j;
int state[31];
state[0] = seed;
for (i=1; i<31; i++){
state[i] = (16807LL * state[i-1]) % 2147483647;
if (state[i] < 0) {
state[i] += 2147483647;
}
}
for (i=31; i<341;i++){
state[(i+3)%31] = (state[(i+3)%31]+state[i%31]);
}
for (i=341;i>1)&0x7fffffff;
printf("%d : %x
",i-340,r[i-340]);
}
return 0;
}
コードの簡略化:
#include
#define MAX 1000
#define seed 1
int main() {
int r[MAX],i;
r[0] = seed;
for (i=1; i<31; i++){
r[i] = (16807LL * r[i-1])%0x7fffffff;
if (r[i] < 0) {
r[i] += 0x7fffffff;
}
}
for (i=31; i<34; i++){
r[i] = r[i-31];
}
for (i=34; i<344;i++){
r[i] = r[i-31] + r[i-3];
}
for (i=344;i<350;i++){
r[i] = r[i-31] + r[i-3];
printf("%d %#x
", i-343, (r[i]>>1)&0x7fffffff);
}
return 0;
}
予測:上に&0 x 7 fffffffが存在し、かつ2で割ることも存在することが分かるので、予測に成功する場合はr[i-31]とr[i-3]ともに&0 x 7 fffffffは存在しない.これはr[i]=((r[i-31]<<1)+(r[i-3]<<1))に対応する乱数か(r[i]>>1)&0 x 7 fffffffffffかであるが、実際にはさらに簡単であり、我々が得たのは乱数であるため、このようなものである.
rand[i]=(r[i]>>1)&0 x 7 fffffff r[i]=(r[i−31]<<1)+(r[i−3]<<1))rand[i−3]=(r[i−3]>>1)&0 x 7 fffffffffffffff rand[i−31]=(r[i−31]>>1)&0 x 7 fffffffffffffffff総合:rand[i]=((r[i−31]<<1)+(r[i−31]<<1)&0 x 7 fffffffffffffffffffff発売rand[i]=(rand[i](rand[i](rand[i]-3]+(rand[i]+(r[i rand[i-31]&0 x 7 fffffffしかし2で割った原因があるため、1の誤差がある可能性がある