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