1998-08-01 - MAKE ENTROPY CHEAP!!!
Header Data
From: David Honig <honig@m7.sprynet.com>
To: cypherpunks@toad.com
Message Hash: a79a7a87037c50c035a90e3bbf7e5065671dd5801ef895dd86d298513373e900
Message ID: <3.0.5.32.19980801163906.007bc7d0@m7.sprynet.com>
Reply To: N/A
UTC Datetime: 1998-08-01 23:39:39 UTC
Raw Date: Sat, 1 Aug 1998 16:39:39 -0700 (PDT)
Raw message
From: David Honig <honig@m7.sprynet.com>
Date: Sat, 1 Aug 1998 16:39:39 -0700 (PDT)
To: cypherpunks@toad.com
Subject: MAKE ENTROPY CHEAP!!!
Message-ID: <3.0.5.32.19980801163906.007bc7d0@m7.sprynet.com>
MIME-Version: 1.0
Content-Type: text/plain
Producing True Random Numbers at 44Kbits/sec on a common PC
I found that FM radio hiss can be digitized and processed to yield true,
quality random numbers which pass the Diehard randomness tests.
A cheap FM radio was tuned to hiss at the high end of the FM band.
The radio's earphone-out signal was fed into ordinary computer soundcard and
digitized at 16bits/sample at 22Ksamples/sec.
Various spectral-analysis programs showed that the FM hiss was fairly white
analog noise, however the raw data did not pass Diehard tests.
I then processed the raw data: The parity of each raw byte
was shifted into a register until a byte accumulated, which was then output.
The resulting data, 1/8 the size of the raw data, passes Diehard randomness
tests with
no additional processing.
Diehard output:
BIRTHDAY SPACINGS TEST, M= 512 N=2**24 LAMBDA= 2.0000
bigsimple.bin using bits 1 to 24 p-value= .215128
bigsimple.bin using bits 2 to 25 p-value= .749499
bigsimple.bin using bits 3 to 26 p-value= .096196
bigsimple.bin using bits 4 to 27 p-value= .658912
bigsimple.bin using bits 5 to 28 p-value= .017458
bigsimple.bin using bits 6 to 29 p-value= .574795
bigsimple.bin using bits 7 to 30 p-value= .057843
bigsimple.bin using bits 8 to 31 p-value= .755589
bigsimple.bin using bits 9 to 32 p-value= .088504
The 9 p-values were
.215128 .749499 .096196 .658912 .017458
.574795 .057843 .755589 .088504
A KSTEST for the 9 p-values yields .896831
----------------------------------------------------------------------------
----
OPERM5 test for file bigsimple.bin
chisquare for 99 degrees of freedom= 87.229; p-value= .204786
OPERM5 test for file bigsimple.bin
chisquare for 99 degrees of freedom=159.365; p-value= .999882
----------------------------------------------------------------------------
----
Binary rank test for bigsimple.bin
Rank test for 31x31 binary matrices:
rows from leftmost 31 bits of each 32-bit integer
rank observed expected (o-e)^2/e sum
28 199 211.4 .729394 .729
29 5138 5134.0 .003101 .732
30 23023 23103.0 .277344 1.010
31 11640 11551.5 .677653 1.687
chisquare= 1.687 for 3 d. of f.; p-value= .457248
Binary rank test for bigsimple.bin
Rank test for 32x32 binary matrices:
rows from leftmost 32 bits of each 32-bit integer
rank observed expected (o-e)^2/e sum
29 206 211.4 .138848 .139
30 5156 5134.0 .094185 .233
31 23196 23103.0 .373989 .607
32 11442 11551.5 1.038443 1.645
chisquare= 1.645 for 3 d. of f.; p-value= .450664
----------------------------------------------------------------------------
----
b-rank test for bits 1 to 8 p=1-exp(-SUM/2)= .14013
b-rank test for bits 2 to 9 p=1-exp(-SUM/2)= .95786
b-rank test for bits 3 to 10 p=1-exp(-SUM/2)= .23685
b-rank test for bits 4 to 11 p=1-exp(-SUM/2)= .54937
b-rank test for bits 5 to 12 p=1-exp(-SUM/2)= .60969
b-rank test for bits 6 to 13 p=1-exp(-SUM/2)= .62964
b-rank test for bits 7 to 14 p=1-exp(-SUM/2)= .89250
b-rank test for bits 8 to 15 p=1-exp(-SUM/2)= .78444
b-rank test for bits 9 to 16 p=1-exp(-SUM/2)= .55013
b-rank test for bits 10 to 17 p=1-exp(-SUM/2)= .23741
b-rank test for bits 11 to 18 p=1-exp(-SUM/2)= .03669
b-rank test for bits 12 to 19 p=1-exp(-SUM/2)= .04415
b-rank test for bits 13 to 20 p=1-exp(-SUM/2)= .62760
b-rank test for bits 14 to 21 p=1-exp(-SUM/2)= .61393
b-rank test for bits 15 to 22 p=1-exp(-SUM/2)= .96515
b-rank test for bits 16 to 23 p=1-exp(-SUM/2)= .08958
b-rank test for bits 17 to 24 p=1-exp(-SUM/2)= .41657
b-rank test for bits 18 to 25 p=1-exp(-SUM/2)= .57191
b-rank test for bits 19 to 26 p=1-exp(-SUM/2)= .88550
b-rank test for bits 20 to 27 p=1-exp(-SUM/2)= .08824
b-rank test for bits 21 to 28 p=1-exp(-SUM/2)= .71721
b-rank test for bits 22 to 29 p=1-exp(-SUM/2)= .54291
b-rank test for bits 23 to 30 p=1-exp(-SUM/2)= .67989
b-rank test for bits 24 to 31 p=1-exp(-SUM/2)= .53742
b-rank test for bits 25 to 32 p=1-exp(-SUM/2)= .17990
TEST SUMMARY, 25 tests on 100,000 random 6x8 matrices
These should be 25 uniform [0,1] random variables:
.140129 .957865 .236846 .549372 .609694
.629638 .892499 .784442 .550129 .237412
.036688 .044150 .627598 .613930 .965150
.089578 .416568 .571912 .885501 .088241
.717215 .542912 .679889 .537418 .179904
brank test summary for bigsimple.bin
The KS test for those 25 supposed UNI's yields
KS p-value= .206759
----------------------------------------------------------------------------
----
No. missing words should average 141909. with sigma=428.
tst no 1: 142384 missing words, 1.11 sigmas from mean, p-value= .86629
tst no 2: 142777 missing words, 2.03 sigmas from mean, p-value= .97868
tst no 3: 143026 missing words, 2.61 sigmas from mean, p-value= .99546
tst no 4: 142308 missing words, .93 sigmas from mean, p-value= .82420
tst no 5: 142173 missing words, .62 sigmas from mean, p-value= .73107
tst no 6: 142022 missing words, .26 sigmas from mean, p-value= .60382
tst no 7: 141931 missing words, .05 sigmas from mean, p-value= .52019
tst no 8: 142314 missing words, .95 sigmas from mean, p-value= .82780
tst no 9: 141482 missing words, -1.00 sigmas from mean, p-value= .15904
tst no 10: 141443 missing words, -1.09 sigmas from mean, p-value= .13796
tst no 11: 141796 missing words, -.26 sigmas from mean, p-value= .39559
tst no 12: 142268 missing words, .84 sigmas from mean, p-value= .79899
tst no 13: 141365 missing words, -1.27 sigmas from mean, p-value= .10172
tst no 14: 142147 missing words, .56 sigmas from mean, p-value= .71066
tst no 15: 141423 missing words, -1.14 sigmas from mean, p-value= .12792
tst no 16: 142599 missing words, 1.61 sigmas from mean, p-value= .94645
tst no 17: 142520 missing words, 1.43 sigmas from mean, p-value= .92318
tst no 18: 141225 missing words, -1.60 sigmas from mean, p-value= .05492
tst no 19: 141413 missing words, -1.16 sigmas from mean, p-value= .12310
tst no 20: 141194 missing words, -1.67 sigmas from mean, p-value= .04733
----------------------------------------------------------------------------
----
OPSO for bigsimple.bin using bits 23 to 32 141802 -.370 .3557
OPSO for bigsimple.bin using bits 22 to 31 141789 -.415 .3391
OPSO for bigsimple.bin using bits 21 to 30 141377 -1.836 .0332
OPSO for bigsimple.bin using bits 20 to 29 142196 .989 .8386
OPSO for bigsimple.bin using bits 19 to 28 142155 .847 .8015
OPSO for bigsimple.bin using bits 18 to 27 142171 .902 .8166
OPSO for bigsimple.bin using bits 17 to 26 141331 -1.994 .0231
OPSO for bigsimple.bin using bits 16 to 25 141565 -1.187 .1175
OPSO for bigsimple.bin using bits 15 to 24 141550 -1.239 .1077
OPSO for bigsimple.bin using bits 14 to 23 142197 .992 .8394
OPSO for bigsimple.bin using bits 13 to 22 141930 .071 .5284
OPSO for bigsimple.bin using bits 12 to 21 141593 -1.091 .1377
OPSO for bigsimple.bin using bits 11 to 20 141585 -1.118 .1317
OPSO for bigsimple.bin using bits 10 to 19 141418 -1.694 .0451
OPSO for bigsimple.bin using bits 9 to 18 141044 -2.984 .0014
OPSO for bigsimple.bin using bits 8 to 17 141908 -.005 .4982
OPSO for bigsimple.bin using bits 7 to 16 141648 -.901 .1838
OPSO for bigsimple.bin using bits 6 to 15 141884 -.087 .4652
OPSO for bigsimple.bin using bits 5 to 14 142362 1.561 .9407
OPSO for bigsimple.bin using bits 4 to 13 141924 .051 .5202
OPSO for bigsimple.bin using bits 3 to 12 141289 -2.139 .0162
OPSO for bigsimple.bin using bits 2 to 11 142145 .813 .7918
OPSO for bigsimple.bin using bits 1 to 10 141728 -.625 .2659
OQSO for bigsimple.bin using bits 28 to 32 142157 .840 .7994
OQSO for bigsimple.bin using bits 27 to 31 141539 -1.255 .1047
OQSO for bigsimple.bin using bits 26 to 30 141511 -1.350 .0885
OQSO for bigsimple.bin using bits 25 to 29 141902 -.025 .4901
OQSO for bigsimple.bin using bits 24 to 28 141674 -.798 .2125
OQSO for bigsimple.bin using bits 23 to 27 141837 -.245 .4032
OQSO for bigsimple.bin using bits 22 to 26 142276 1.243 .8931
OQSO for bigsimple.bin using bits 21 to 25 142511 2.040 .9793
OQSO for bigsimple.bin using bits 20 to 24 142223 1.063 .8562
OQSO for bigsimple.bin using bits 19 to 23 141683 -.767 .2215
OQSO for bigsimple.bin using bits 18 to 22 141936 .090 .5360
OQSO for bigsimple.bin using bits 17 to 21 141337 -1.940 .0262
OQSO for bigsimple.bin using bits 16 to 20 141959 .168 .5669
OQSO for bigsimple.bin using bits 15 to 19 141975 .223 .5881
OQSO for bigsimple.bin using bits 14 to 18 142166 .870 .8079
OQSO for bigsimple.bin using bits 13 to 17 141738 -.581 .2807
OQSO for bigsimple.bin using bits 12 to 16 141628 -.954 .1701
OQSO for bigsimple.bin using bits 11 to 15 141781 -.435 .3318
OQSO for bigsimple.bin using bits 10 to 14 142112 .687 .7540
OQSO for bigsimple.bin using bits 9 to 13 141920 .036 .5144
OQSO for bigsimple.bin using bits 8 to 12 141668 -.818 .2067
OQSO for bigsimple.bin using bits 7 to 11 141655 -.862 .1943
OQSO for bigsimple.bin using bits 6 to 10 141984 .253 .5999
OQSO for bigsimple.bin using bits 5 to 9 141585 -1.099 .1358
OQSO for bigsimple.bin using bits 4 to 8 142013 .351 .6374
OQSO for bigsimple.bin using bits 3 to 7 141833 -.259 .3979
OQSO for bigsimple.bin using bits 2 to 6 141671 -.808 .2096
OQSO for bigsimple.bin using bits 1 to 5 142007 .331 .6297
DNA for bigsimple.bin using bits 31 to 32 142254 1.017 .8454
DNA for bigsimple.bin using bits 30 to 31 142326 1.229 .8905
DNA for bigsimple.bin using bits 29 to 30 142408 1.471 .9294
DNA for bigsimple.bin using bits 28 to 29 142186 .816 .7928
DNA for bigsimple.bin using bits 27 to 28 141882 -.081 .4679
DNA for bigsimple.bin using bits 26 to 27 142132 .657 .7444
DNA for bigsimple.bin using bits 25 to 26 141958 .144 .5571
DNA for bigsimple.bin using bits 24 to 25 141857 -.154 .4387
DNA for bigsimple.bin using bits 23 to 24 141521 -1.146 .1260
DNA for bigsimple.bin using bits 22 to 23 142664 2.226 .9870
DNA for bigsimple.bin using bits 21 to 22 141448 -1.361 .0868
DNA for bigsimple.bin using bits 20 to 21 142090 .533 .7030
DNA for bigsimple.bin using bits 19 to 20 141867 -.125 .4503
DNA for bigsimple.bin using bits 18 to 19 141894 -.045 .4820
DNA for bigsimple.bin using bits 17 to 18 141463 -1.317 .0940
DNA for bigsimple.bin using bits 16 to 17 141587 -.951 .1708
DNA for bigsimple.bin using bits 15 to 16 142088 .527 .7009
DNA for bigsimple.bin using bits 14 to 15 141372 -1.585 .0565
DNA for bigsimple.bin using bits 13 to 14 141896 -.039 .4843
DNA for bigsimple.bin using bits 12 to 13 142256 1.023 .8468
DNA for bigsimple.bin using bits 11 to 12 141172 -2.175 .0148
DNA for bigsimple.bin using bits 10 to 11 141524 -1.137 .1278
DNA for bigsimple.bin using bits 9 to 10 141700 -.617 .2685
DNA for bigsimple.bin using bits 8 to 9 142180 .798 .7877
DNA for bigsimple.bin using bits 7 to 8 141782 -.376 .3536
DNA for bigsimple.bin using bits 6 to 7 142054 .427 .6652
DNA for bigsimple.bin using bits 5 to 6 142370 1.359 .9129
DNA for bigsimple.bin using bits 4 to 5 142032 .362 .6413
DNA for bigsimple.bin using bits 3 to 4 141471 -1.293 .0980
DNA for bigsimple.bin using bits 2 to 3 142013 .306 .6201
DNA for bigsimple.bin using bits 1 to 2 141754 -.458 .3234
----------------------------------------------------------------------------
----
Test results for bigsimple.bin
Chi-square with 5^5-5^4=2500 d.of f. for sample size:2560000
chisquare equiv normal p-value
Results fo COUNT-THE-1's in successive bytes:
byte stream for bigsimple.bin 2480.79 -.272 .392963
byte stream for bigsimple.bin 2544.61 .631 .735960
----------------------------------------------------------------------------
----
Chi-square with 5^5-5^4=2500 d.of f. for sample size: 256000
chisquare equiv normal p value
Results for COUNT-THE-1's in specified bytes:
bits 1 to 8 2539.84 .563 .713407
bits 2 to 9 2462.74 -.527 .299128
bits 3 to 10 2475.45 -.347 .364216
bits 4 to 11 2352.58 -2.085 .018545
bits 5 to 12 2486.65 -.189 .425128
bits 6 to 13 2473.02 -.382 .351384
bits 7 to 14 2655.21 2.195 .985918
bits 8 to 15 2536.20 .512 .695677
bits 9 to 16 2532.48 .459 .677002
bits 10 to 17 2314.27 -2.627 .004311
bits 11 to 18 2605.76 1.496 .932629
bits 12 to 19 2588.76 1.255 .895302
bits 13 to 20 2486.16 -.196 .422396
bits 14 to 21 2496.38 -.051 .479582
bits 15 to 22 2425.24 -1.057 .145196
bits 16 to 23 2490.05 -.141 .444052
bits 17 to 24 2373.30 -1.792 .036578
bits 18 to 25 2356.86 -2.024 .021470
bits 19 to 26 2557.84 .818 .793310
bits 20 to 27 2590.32 1.277 .899259
bits 21 to 28 2467.57 -.459 .323273
bits 22 to 29 2496.07 -.056 .477834
bits 23 to 30 2530.74 .435 .668114
bits 24 to 31 2474.58 -.360 .359599
bits 25 to 32 2580.29 1.135 .871906
----------------------------------------------------------------------------
----
CDPARK: result of ten tests on file bigsimple.bin
Of 12,000 tries, the average no. of successes
should be 3523 with sigma=21.9
Successes: 3529 z-score: .274 p-value: .607947
Successes: 3521 z-score: -.091 p-value: .463618
Successes: 3526 z-score: .137 p-value: .554479
Successes: 3536 z-score: .594 p-value: .723613
Successes: 3517 z-score: -.274 p-value: .392053
Successes: 3539 z-score: .731 p-value: .767486
Successes: 3524 z-score: .046 p-value: .518210
Successes: 3513 z-score: -.457 p-value: .323972
Successes: 3541 z-score: .822 p-value: .794438
Successes: 3527 z-score: .183 p-value: .572463
square size avg. no. parked sample sigma
100. 3527.300 8.736
KSTEST for the above 10: p= .804330
----------------------------------------------------------------------------
----
This is the MINIMUM DISTANCE test
for random integers in the file bigsimple.bin
Sample no. d^2 avg equiv uni
5 .1930 1.0055 .176285
10 .5596 .9379 .430160
15 1.1844 1.0280 .695890
20 .5422 .8555 .420105
25 .9861 .9044 .628811
30 .2861 .8935 .249863
35 .1485 .9897 .138682
40 .2950 .9306 .256592
45 .6921 .8989 .501193
50 .1139 .9307 .108141
55 1.0898 .9325 .665562
60 .0072 .9084 .007231
65 .6066 .8989 .456462
70 .7895 .9008 .547730
75 .3097 .8698 .267450
80 .4391 .8918 .356821
85 .8823 .8699 .588018
90 .2776 .9121 .243421
95 1.3020 .9192 .729777
100 2.3327 .9325 .904094
MINIMUM DISTANCE TEST for bigsimple.bin
Result of KS test on 20 transformed mindist^2's:
p-value= .157745
----------------------------------------------------------------------------
----
The 3DSPHERES test for file bigsimple.bin
sample no: 1 r^3= 61.647 p-value= .87189
sample no: 2 r^3= 61.307 p-value= .87043
sample no: 3 r^3= 21.447 p-value= .51076
sample no: 4 r^3= 2.684 p-value= .08559
sample no: 5 r^3= 1.207 p-value= .03942
sample no: 6 r^3= 12.684 p-value= .34479
sample no: 7 r^3= 24.098 p-value= .55214
sample no: 8 r^3= .287 p-value= .00951
sample no: 9 r^3= 68.533 p-value= .89817
sample no: 10 r^3= 15.201 p-value= .39751
sample no: 11 r^3= 37.780 p-value= .71616
sample no: 12 r^3= 48.397 p-value= .80076
sample no: 13 r^3= 26.584 p-value= .58775
sample no: 14 r^3= 29.700 p-value= .62842
sample no: 15 r^3= 8.969 p-value= .25841
sample no: 16 r^3= 43.698 p-value= .76697
sample no: 17 r^3= 61.285 p-value= .87034
sample no: 18 r^3= 30.428 p-value= .63733
sample no: 19 r^3= 54.608 p-value= .83802
sample no: 20 r^3= 19.998 p-value= .48655
3DSPHERES test for file bigsimple.bin p-value= .595668
----------------------------------------------------------------------------
----
RESULTS OF SQUEEZE TEST FOR bigsimple.bin
Table of standardized frequency counts
( (obs-exp)/sqrt(exp) )^2
for j taking values <=6,7,8,...,47,>=48:
2.0 .1 1.3 1.6 .8 -1.0
.0 -.1 -2.2 -1.0 -1.9 .7
.5 -.3 .9 -.4 .6 -1.3
.5 -.8 .4 -.2 1.6 -.5
.5 1.6 -.1 .0 -1.1 1.2
.8 .6 .2 -1.0 -.1 2.2
.3 1.1 .5 -1.8 -.6 .0
-1.1
Chi-square with 42 degrees of freedom: 45.808
z-score= .415 p-value= .683048
______________________________________________________________
----------------------------------------------------------------------------
----
Test no. 1 p-value .130689
Test no. 2 p-value .697905
Test no. 3 p-value .312460
Test no. 4 p-value .031315
Test no. 5 p-value .961343
Test no. 6 p-value .483192
Test no. 7 p-value .554386
Test no. 8 p-value .960960
Test no. 9 p-value .767135
Test no. 10 p-value .146497
Results of the OSUM test for bigsimple.bin
KSTEST on the above 10 p-values: .135933
----------------------------------------------------------------------------
----
The RUNS test for file bigsimple.bin
Up and down runs in a sample of 10000
_________________________________________________
Run test for bigsimple.bin :
runs up; ks test for 10 p's: .368663
runs down; ks test for 10 p's: .177188
Run test for bigsimple.bin :
runs up; ks test for 10 p's: .199189
runs down; ks test for 10 p's: .860525
----------------------------------------------------------------------------
----
Results of craps test for bigsimple.bin
No. of wins: Observed Expected
98315 98585.86
Chisq= 26.08 for 20 degrees of freedom, p= .83666
Throws Observed Expected Chisq Sum
SUMMARY FOR bigsimple.bin
p-value for no. of wins: .112863
p-value for throws/game: .836658
Test completed. File bigsimple.bin
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::
honig@alum.mit.edu
"Speech is not protected simply because it is written in a language"
Federal Misjudge Gwin on the Bernstein Case
Thread
Return to August 1998
Return to “David Honig <honig@m7.sprynet.com>”
1998-08-01 (Sat, 1 Aug 1998 16:39:39 -0700 (PDT)) - MAKE ENTROPY CHEAP!!! - David Honig <honig@m7.sprynet.com>