|
|
Boost : |
From: Mark Borgerding (mborgerding_at_[hidden])
Date: 2000-02-24 11:02:32
I did some more work on the entropy pool/ clock() timing rng.
I had about 3MB of data from the clock() method. I put it through a
entropy-pool churning process described in my earlier email. I used a
32 bit CRC to churn the pool.
For those that are just tuning in, the idea was to get a value from
clock(), count in a tight loop until clock() changes, and use the lsb
of the count as a random bit. Eight bits of entropy are gathered this
way and then mixed into an entropy pool via a CRC. A byte of the
entropy pool is then used as a true random byte.
The following is a program that writes random bytes to stdout.
I analyzed the results with diehard and they looked really good.
Granted, I could not run all the tests, because some of them require >
10MB of data.
The abbreviated diehard results are after the program listing. Note to
interpretation: p-values for random data should be uniformly
distributed on [0,1)
Of course, now that I've done all this, I'm having doubts about its
utility. I'm not sure this method would be strong enough in cases that
need cryptographic random numbers (i.e. key generation). And it is
probably too slow to be used in applications where a PRNG would
suffice. What does that leave?
.... but I put some serious time into this, so by golly -- I'm gonna
tell you about it.
/*
The CRC32 code is based upon work by Charles Michael Heard. He did
not affix any copyright to his original code. He should be contacted
before this is used for anything more than proof-of-concept.
*/
#include <stdlib.h>
#include <time.h>
#include <unistd.h> // this is needed for write(), not required by the
algo
unsigned char true_rand();
int main(int argc, char ** argv)
{
size_t num = ~0;
if (argc > 1)
num = atoi(argv[1]);
for (size_t i=0;i<num;++i){
unsigned char c = true_rand();
write(1,&c,1);
}
return 0;
}
const unsigned long polynomial = 0x04c11db7;
unsigned long crc_table[256];
void gen_crc_table()
{
int i, j;
unsigned long crc_accum;
for ( i = 0; i < 256; i++ ){
crc_accum = ( i << 24 );
for ( j = 0; j < 8; j++ ){
if ( crc_accum & 0x80000000L )
crc_accum = ( crc_accum << 1 ) ^
polynomial;
else
crc_accum = ( crc_accum << 1 );
}
crc_table[i] = crc_accum;
}
}
inline
unsigned long update_crc(unsigned long crc_accum,const void *
pData,unsigned long data_blk_size)
{
const char * data_blk_ptr = static_cast<const char *>(pData);
int i;
static bool init=false;
if (!init){
gen_crc_table();
init = true;
}
while (data_blk_size--){
i = (( crc_accum >> 24) ^ *data_blk_ptr++ ) & 0xff;
crc_accum = ( crc_accum << 8 ) ^ crc_table[i];
}
return crc_accum;
}
inline
unsigned char churn(const void * pData=0,size_t bytes=0) {
static unsigned long ent=0; //entropy pool
ent = update_crc(static_cast<unsigned long>(-1),&ent,sizeof(ent
));
if (bytes && pData)
ent = update_crc(ent,pData,bytes);
return (~ent)&0xff;
}
unsigned char true_rand()
{
unsigned char result = 0;
for (int i=0;i<8;++i)
{
unsigned int counter=0;
clock_t start = clock();
do
{
++counter;// keep counting until the clock
changes
}while (start == clock());
result <<= 1;
// left shift 1 bit
result |= (counter&1);
// put the LSB from the counter into the LSB of the
result
}
return churn(&result,1);
}
Here are the diehard test results for a 3MB file generated by the above
program on a linux box (Pentium 233, kernel 2.2.14,g++ 2.95.2,glibc
2.1.1).
If anyone is interested in getting the file or installing diehard (the
precompiled binaries didn't work for me), contact me (mborgerding @
acm.org) and I will help out.
Birthday spacings:
The 9 p-values were
.650702 .352101 .372355 .322484 .871127
.593715 .926910 .815100 .929238
A KSTEST for the 9 p-values yields .817223
BINARY RANK TEST for 6x8 matrices
TEST SUMMARY, 25 tests on 100,000 random 6x8 matrices
These should be 25 uniform [0,1] random variables:
.034846 .668624 .867341 .322676 .063906
.573906 .616073 .756396 .259063 .225803
.004042 .917611 .375742 .014019 .593909
.101089 .832640 .527469 .372356 .176146
.205358 .746577 .293803 .314605 .721505
brank test summary for rand.dat
The KS test for those 25 supposed UNI's yields
KS p-value= .723423
THE BITSTREAM TEST
BITSTREAM test results forrand.dat
tst no 1: 142557 missing words, 1.51 sigmas from mean, p-value=
.93489
tst no 2: 141747 missing words, -.38 sigmas from mean, p-value=
.35224
tst no 3: 142267 missing words, .84 sigmas from mean, p-value=
.79833
tst no 4: 142453 missing words, 1.27 sigmas from mean, p-value=
.89800
tst no 5: 142019 missing words, .26 sigmas from mean, p-value=
.60112
tst no 6: 141123 missing words, -1.84 sigmas from mean, p-value=
.03309
tst no 7: 142181 missing words, .63 sigmas from mean, p-value=
.73720
tst no 8: 141680 missing words, -.54 sigmas from mean, p-value=
.29604
tst no 9: 142044 missing words, .31 sigmas from mean, p-value=
.62349
tst no 10: 142355 missing words, 1.04 sigmas from mean, p-value=
.85113
tst no 11: 141741 missing words, -.39 sigmas from mean, p-value=
.34705
tst no 12: 141922 missing words, .03 sigmas from mean, p-value=
.51181
tst no 13: 142160 missing words, .59 sigmas from mean, p-value=
.72096
tst no 14: 141871 missing words, -.09 sigmas from mean, p-value=
.46432
tst no 15: 141482 missing words, -1.00 sigmas from mean, p-value=
.15904
Results for COUNT-THE-1's in successive bytes:
chisquare equiv normal p-value
byte stream for rand.dat 2566.34 .938 .825937
PARKING LOT TEST
DPARK: result of ten tests on file rand.dat
Of 12,000 tries, the average no. of successes
should be 3523 with sigma=21.9
Successes: 3518 z-score: -.228 p-value: .409702
Successes: 3522 z-score: -.046 p-value: .481790
Successes: 3508 z-score: -.685 p-value: .246694
Successes: 3520 z-score: -.137 p-value: .445521
Successes: 3510 z-score: -.594 p-value: .276387
Successes: 3525 z-score: .091 p-value: .536382
Successes: 3532 z-score: .411 p-value: .659449
Successes: 3515 z-score: -.365 p-value: .357445
Successes: 3529 z-score: .274 p-value: .607947
Successes: 3539 z-score: .731 p-value: .767486
square size avg. no. parked sample sigma
100. 3521.800 9.231
KSTEST for the above 10: p= .697954
This is the MINIMUM DISTANCE test
for random integers in the file rand.dat
Sample no. d^2 avg equiv uni
5 .5021 .2219 .396247
10 .8606 .4462 .578929
15 .0062 .4712 .006250
20 .0754 .5142 .072955
25 2.5621 .6595 .923843
30 .5615 .6905 .431277
35 1.9744 .7447 .862526
40 .9322 .7300 .608140
45 .0691 .7822 .067082
50 .3137 .7939 .270420
55 4.0357 .8903 .982682
60 .1584 .9124 .147175
3DSPHERES test for file rand.dat p-value= .598040
OVERLAPPING SUMS
Test no. 1 p-value .226889
Test no. 2 p-value .148903
Test no. 3 p-value .894253
Test no. 4 p-value .922038
Test no. 5 p-value .102995
Test no. 6 p-value .792611
Test no. 7 p-value .143711
Test no. 8 p-value .819030
Test no. 9 p-value .655024
Test no. 10 p-value .588361
Results of the OSUM test for rand.dat
KSTEST on the above 10 p-values: .307924
The RUNS test for file rand.dat
Up and down runs in a sample of 10000
_________________________________________________
Run test for rand.dat :
runs up; ks test for 10 p's: .575118
runs down; ks test for 10 p's: .444705
Run test for rand.dat :
runs up; ks test for 10 p's: .018677
runs down; ks test for 10 p's: .285316
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk