diehard and ent results quesion
rex dickens
ent test
Entropy = 7.752289 bits per byte.
Optimum compression would reduce the size
of this 11534336 byte file by 3 percent.
Chi square distribution for 11534336 samples is 3559641.13, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
Monte Carlo value for Pi is 3.223218610 (error 2.60 percent).
Serial correlation coefficient is 0.006276 (totally uncorrelated = 0.0).
diehard test
BIRTHDAY SPACINGS TEST
blankenc using bits 1 to 24 286.428
duplicate number number
spacings observed expected
0 499. 67.668
1 1. 135.335
2 0. 135.335
3 0. 90.224
4 0. 45.112
5 0. 18.045
6 to INF 0. 8.282
Chisquare with 6 d.o.f. = 3179.77 p-value= 1.000000
BINARY RANK TEST
28 713 211.4********** 1189.986
29 6251 5134.0243.019800 1433.006
30 20182 23103.0369.324200 1802.330
31 12854 11551.5146.858800 1949.189
chisquare=****** for 3 d. of f.; p-value=1.000000
b-rank test for bits 1 to 8
OBSERVED EXPECTED (O-E)^2/E SUM
r<=4 1785 944.3 748.463 748.463
r =5 20541 21743.9 66.546 815.009
r =6 77674 77311.8 1.697 816.706
p=1-exp(-SUM/2)=1.00000
THE BITSTREAM TEST
all are
tst no 1: 1031925 missing words, 2079.48 sigmas from mean, p-value=1.00000
tst no 2: 1041436 missing words, 2101.70 sigmas from mean, p-value=1.00000
OPSO, OQSO and DNA test
all are
OPSO for blankenc using bits 23 to 32 1048052******* 1.0000
COUNT-THE-1's TEST
bits 1 to 8********* 35276.380 1.000000
rest are within a range 34000-41000
PARKING LOT TEST
Successes: 245 z-score:******* p-value: .000000
Successes: 108 z-score:******* p-value: .000000
rest are 108
MINIMUM DISTANCE TEST
all 0
3dsphere test
sample no: 1 r^3= 89.164 p-value= .94881
rest close to that 87-91
squeeze test
-1.5 -2.4 -4.2 -6.8 -10.5 -15.4
269.6 -28.7 -36.9 90.7 115.7 34.0
57.8 -39.8 62.4 -18.3 -90.6 13.1
17.3 -84.9 -40.9 10.5 -20.8 -8.1
6.2 -45.9 -39.2 61.4 -27.5 -22.6
-18.4 -14.8 -11.7 -9.2 -7.2 -5.5
-4.2 -3.2 -2.4 -1.8 -1.3 -1.0
-1.1
CRAPS TEST
No. of wins: Observed Expected
84207 98585.86
84207= No. of wins, z-score=****** pvalue= .00000
Analysis of Throws-per-Game:
Chisq=******* for 20 degrees of freedom, p=********
Throws Observed Expected Chisq Sum
1 73678 66666.7 737.381 737.381
2 36841 37654.3 17.568 754.948
3 31578 26954.7 792.982 1547.931
4 15790 19313.5 642.804 2190.735
5 10528 13851.4 797.399 2988.135
6 10529 9943.5 34.471 3022.605
7 5263 7145.0 495.732 3518.337
8 10528 5139.15650.934 9169.271
9 5263 3699.9 660.401 9829.672
10 0 2666.32666.29712495.970
11 1 1923.31921.32914417.300
12 0 1388.71388.74015806.040
13 1 1003.71001.71616807.750
14 0 726.1 726.14117533.890
15 0 525.8 525.83618059.730
16-21 are 0
SUMMARY FOR blankenc
p-value for no. of wins: .000000
p-value for throws/game:********
Tom St Denis
"rex dickens" <rdic...@cox.net> wrote in message
news:Oyq4a.36188$K71....@news1.central.cox.net...
> could someone try to explain the following
Means the source ain't none random.
Tom
Paul Pires
Different from the explainations provided with these
two test packages? What don't you understand?
That the results indicate a really bad PRNG or random
source? Or do you suspect some other problem?
I am familiar with both packages.
>
> ent test
> Entropy = 7.752289 bits per byte.
Not a result reflecting a good random source.
should be more like 7.99xxxxx
>
> Optimum compression would reduce the size
> of this 11534336 byte file by 3 percent.
Not a result reflecting a good random source.
Should be more like .00125
>
> Chi square distribution for 11534336 samples is 3559641.13, and randomly
> would exceed this value 0.01 percent of the times.
Note: This test is "Locked" with the entropy test. Basically just
two different looks at the same result.
>
> Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
> Monte Carlo value for Pi is 3.223218610 (error 2.60 percent).
> Serial correlation coefficient is 0.006276 (totally uncorrelated = 0.0).
Not a result reflecting a good random source.
>
>
> diehard test
All of the DieHard results demonstrate a rather putrid PRNG.
Far worse than something like rand() (A really poorly performing
PRNG)
Are you sure you supplied the random bits to the tests in the form
and the quantity that they need? Results this bad should be evident
by looking at the raw data by eye.
Paul
Cristiano
>> Entropy = 7.752289 bits per byte.
>
> Not a result reflecting a good random source.
> should be more like 7.99xxxxx
It depend on how many bits (or bytes) you supply: few bits, small
'entropy'; many bits, high 'entropy' (that 'entropy' it's only an
estimate).
>> Optimum compression would reduce the size
>> of this 11534336 byte file by 3 percent.
>
> Not a result reflecting a good random source.
> Should be more like .00125
Same as above.
>> Chi square distribution for 11534336 samples is 3559641.13, and
>> randomly
>> would exceed this value 0.01 percent of the times.
>
> Note: This test is "Locked" with the entropy test. Basically just
> two different looks at the same result.
Perhaps you're right. But the chi-square test seems more useful. Do you
agree?
>> Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
>> Monte Carlo value for Pi is 3.223218610 (error 2.60 percent).
>> Serial correlation coefficient is 0.006276 (totally uncorrelated =
>> 0.0).
>
> Not a result reflecting a good random source.
The first seems not bad. You can get 127.3 even with a good generator.
> Are you sure you supplied the random bits to the tests in the form
> and the quantity that they need? Results this bad should be evident
> by looking at the raw data by eye.
You're right! I'd like to see what kind of generator he used.
Cristiano
[Paul, have you got my mail on Feb, 15?]
Paul Pires
Cristiano <cristi...@nsquipo.it> wrote in message news:qbz4a.200146$0v.55...@news1.tin.it...
> Paul Pires wrote:
> > rex dickens <rdic...@cox.net> wrote in message
> >
> >> ent test
> >> Entropy = 7.752289 bits per byte.
> >
> > Not a result reflecting a good random source.
> > should be more like 7.99xxxxx
>
> It depend on how many bits (or bytes) you supply: few bits, small
> 'entropy'; many bits, high 'entropy' (that 'entropy' it's only an
> estimate).
>
> >> Optimum compression would reduce the size
> >> of this 11534336 byte file by 3 percent.
> >
> > Not a result reflecting a good random source.
> > Should be more like .00125
>
> Same as above.
>
> >> Chi square distribution for 11534336 samples is 3559641.13, and
> >> randomly
> >> would exceed this value 0.01 percent of the times.
> >
> > Note: This test is "Locked" with the entropy test. Basically just
> > two different looks at the same result.
>
> Perhaps you're right. But the chi-square test seems more useful. Do you
> agree?
You mis-understand (I think). In the ENT package, these two tests
are actually two different reports on a single analysis. Invert, scale and
the results fall on top of each other, always. There are really only three
different tests in the ENT package. Throw out the entropy test as it
is not as precise in it's reporting and you loose nothing.
Paul
Cyber Vagrant
> could someone try to explain the following
>
> ent test
> Entropy = 7.752289 bits per byte.
>
> Optimum compression would reduce the size
> of this 11534336 byte file by 3 percent.
>
> Chi square distribution for 11534336 samples is 3559641.13, and randomly
> would exceed this value 0.01 percent of the times.
>
> Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
> Monte Carlo value for Pi is 3.223218610 (error 2.60 percent).
> Serial correlation coefficient is 0.006276 (totally uncorrelated = 0.0).
I use Ent to test a varity combination generators I've been working on
lately. Entropy is synonomous with randomness, more is better. A
text file has about 4 bits of entropy per byte. Your figure here
leaves room for improvement.
Entropy is also a measure of data density. Again, more is better.
Your figure here mean that the data density of the file is 99.98%.
That good.
The chi square I know little about other than a result between 0%-5%
or 95%-100% is downright bad, a result between 5%-10% or 90%-95% is
poor and a result between 90%-10% is accepted as having passed the
test. Your figue here is about as bad as it can get.
The arithmetic mean is self-explanatory. Your figure is OK.
The Monte Carlo test is neat. They mark off a square 6 bytes x
6bytes, scribe a circle inside it then plot points 6 bytes for x and 6
bytes for y. At the end the ratio of points inside the circle to
points outside the circle is the result. For a good random number
source the ratio should approximate the value of pi. The better the
source, the better the approximation. Yours has room for improvement.
Serial correlation I understand poorly at the moment. It has to do
with how much one value is affected by the previous value. Here less
is better. Your value could be improved.
Here are Ent results for one of my latest creations:
Entropy = 7.999985 bits per byte.
Optimum compression would reduce the size
of this 11468800 byte file by 0 percent.
Chi square distribution for 11468800 samples is 241.81, and randomly
would exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 127.4558 (127.5 = random).
Monte Carlo value for Pi is 3.141800063 (error 0.01 percent).
Serial correlation coefficient is -0.000377 (totally uncorrelated =
0.0).
I have been banging my head against the walls tring to get better than
this, and after a couple weeks of testing different combination
variations and seed values, this seems to be about as good as it gets.
ISAAC tested about the same.
As far as Die Hard goes. You want a "Uniform Distrobution Between 0
and 1".
That means if you see five or six 1s or 0s all in a line, then you
generator failed the test.
Cyber Vagrant
seems to have failed one OPSO test. The results, as these are execpt
one, should be evenly distrobuted over the interval (0,1). Before I
meant five or six 1s or 9s all in a row.
BIRTHDAY SPACINGS TEST, M= 512 N=2**24 LAMBDA= 2.0000
x.bin using bits 1 to 24 p-value= .800910
x.bin using bits 2 to 25 p-value= .159594
x.bin using bits 3 to 26 p-value= .977341
x.bin using bits 4 to 27 p-value= .383329
x.bin using bits 5 to 28 p-value= .032909
x.bin using bits 6 to 29 p-value= .049932
x.bin using bits 7 to 30 p-value= .397622
x.bin using bits 8 to 31 p-value= .250844
x.bin using bits 9 to 32 p-value= .765404
The 9 p-values were
.800910 .159594 .977341 .383329 .032909
.049932 .397622 .250844 .765404
A KSTEST for the 9 p-values yields .484428
--------------------------------------------------------------------------------
OPERM5 test for file x.bin
chisquare for 99 degrees of freedom= 62.451; p-value= .001551
OPERM5 test for file x.bin
chisquare for 99 degrees of freedom=117.393; p-value= .899907
--------------------------------------------------------------------------------
Binary rank test for x.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 212 211.4 .001602 .002
29 5186 5134.0 .526476 .528
30 22982 23103.0 .634217 1.162
31 11620 11551.5 .405912 1.568
chisquare= 1.568 for 3 d. of f.; p-value= .438614
Binary rank test for x.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 225 211.4 .872538 .873
30 5213 5134.0 1.215303 2.088
31 23107 23103.0 .000676 2.089
32 11455 11551.5 .806557 2.895
chisquare= 2.895 for 3 d. of f.; p-value= .636339
--------------------------------------------------------------------------------
b-rank test for bits 1 to 8 p=1-exp(-SUM/2)= .58031
b-rank test for bits 2 to 9 p=1-exp(-SUM/2)= .97681
b-rank test for bits 3 to 10 p=1-exp(-SUM/2)= .58525
b-rank test for bits 4 to 11 p=1-exp(-SUM/2)= .82136
b-rank test for bits 5 to 12 p=1-exp(-SUM/2)= .56544
b-rank test for bits 6 to 13 p=1-exp(-SUM/2)= .69794
b-rank test for bits 7 to 14 p=1-exp(-SUM/2)= .50961
b-rank test for bits 8 to 15 p=1-exp(-SUM/2)= .12056
b-rank test for bits 9 to 16 p=1-exp(-SUM/2)= .50483
b-rank test for bits 10 to 17 p=1-exp(-SUM/2)= .01746
b-rank test for bits 11 to 18 p=1-exp(-SUM/2)= .01516
b-rank test for bits 12 to 19 p=1-exp(-SUM/2)= .78465
b-rank test for bits 13 to 20 p=1-exp(-SUM/2)= .69148
b-rank test for bits 14 to 21 p=1-exp(-SUM/2)= .69889
b-rank test for bits 15 to 22 p=1-exp(-SUM/2)= .89104
b-rank test for bits 16 to 23 p=1-exp(-SUM/2)= .60796
b-rank test for bits 17 to 24 p=1-exp(-SUM/2)= .05970
b-rank test for bits 18 to 25 p=1-exp(-SUM/2)= .79798
b-rank test for bits 19 to 26 p=1-exp(-SUM/2)= .02867
b-rank test for bits 20 to 27 p=1-exp(-SUM/2)= .17388
b-rank test for bits 21 to 28 p=1-exp(-SUM/2)= .52713
b-rank test for bits 22 to 29 p=1-exp(-SUM/2)= .58135
b-rank test for bits 23 to 30 p=1-exp(-SUM/2)= .22838
b-rank test for bits 24 to 31 p=1-exp(-SUM/2)= .10657
b-rank test for bits 25 to 32 p=1-exp(-SUM/2)= .32764
TEST SUMMARY, 25 tests on 100,000 random 6x8 matrices
These should be 25 uniform [0,1] random variables:
.580310 .976814 .585246 .821358 .565437
.697936 .509612 .120565 .504831 .017461
.015160 .784653 .691477 .698885 .891041
.607956 .059701 .797980 .028672 .173875
.527127 .581348 .228378 .106571 .327638
brank test summary for x.bin
The KS test for those 25 supposed UNI's yields
KS p-value= .524853
--------------------------------------------------------------------------------
No. missing words should average 141909. with sigma=428.
tst no 1: 141566 missing words, -.80 sigmas from mean, p-value=
.21123
tst no 2: 142142 missing words, .54 sigmas from mean, p-value=
.70665
tst no 3: 141273 missing words, -1.49 sigmas from mean, p-value=
.06854
tst no 4: 142025 missing words, .27 sigmas from mean, p-value=
.60652
tst no 5: 141787 missing words, -.29 sigmas from mean, p-value=
.38751
tst no 6: 142586 missing words, 1.58 sigmas from mean, p-value=
.94306
tst no 7: 142050 missing words, .33 sigmas from mean, p-value=
.62880
tst no 8: 142270 missing words, .84 sigmas from mean, p-value=
.80030
tst no 9: 142127 missing words, .51 sigmas from mean, p-value=
.69448
tst no 10: 142428 missing words, 1.21 sigmas from mean, p-value=
.88722
tst no 11: 141864 missing words, -.11 sigmas from mean, p-value=
.45783
tst no 12: 142008 missing words, .23 sigmas from mean, p-value=
.59116
tst no 13: 142005 missing words, .22 sigmas from mean, p-value=
.58844
tst no 14: 142294 missing words, .90 sigmas from mean, p-value=
.81561
tst no 15: 141882 missing words, -.06 sigmas from mean, p-value=
.47454
tst no 16: 142303 missing words, .92 sigmas from mean, p-value=
.82116
tst no 17: 141629 missing words, -.65 sigmas from mean, p-value=
.25624
tst no 18: 142945 missing words, 2.42 sigmas from mean, p-value=
.99224
tst no 19: 141408 missing words, -1.17 sigmas from mean, p-value=
.12073
tst no 20: 141452 missing words, -1.07 sigmas from mean, p-value=
.14264
--------------------------------------------------------------------------------
OPSO for x.bin using bits 23 to 32 142118 .720
.7641
OPSO for x.bin using bits 22 to 31 141742 -.577
.2820
OPSO for x.bin using bits 21 to 30 142351 1.523
.9361
OPSO for x.bin using bits 20 to 29 142207 1.026
.8477
OPSO for x.bin using bits 19 to 28 141948 .133
.5530
OPSO for x.bin using bits 18 to 27 141465 -1.532
.0627
OPSO for x.bin using bits 17 to 26 141883 -.091
.4638
OPSO for x.bin using bits 16 to 25 141878 -.108
.4570
OPSO for x.bin using bits 15 to 24 141440 -1.618
.0528
OPSO for x.bin using bits 14 to 23 141633 -.953
.1703
OPSO for x.bin using bits 13 to 22 142064 .533
.7031
// I wonder what happened here //
OPSO for x.bin using bits 12 to 21 140751 -3.994
.0000
OPSO for x.bin using bits 11 to 20 142085 .606
.7277
OPSO for x.bin using bits 10 to 19 141895 -.049
.4803
OPSO for x.bin using bits 9 to 18 141844 -.225
.4109
OPSO for x.bin using bits 8 to 17 141984 .257
.6016
OPSO for x.bin using bits 7 to 16 141499 -1.415
.0785
OPSO for x.bin using bits 6 to 15 141997 .302
.6188
OPSO for x.bin using bits 5 to 14 141780 -.446
.3278
OPSO for x.bin using bits 4 to 13 141768 -.487
.3130
OPSO for x.bin using bits 3 to 12 141765 -.498
.3094
OPSO for x.bin using bits 2 to 11 141757 -.525
.2997
OPSO for x.bin using bits 1 to 10 141621 -.994
.1601
OQSO for x.bin using bits 28 to 32 142638 2.470
.9932
OQSO for x.bin using bits 27 to 31 141864 -.154
.4389
OQSO for x.bin using bits 26 to 30 142053 .487
.6869
OQSO for x.bin using bits 25 to 29 141650 -.879
.1897
OQSO for x.bin using bits 24 to 28 142006 .328
.6284
OQSO for x.bin using bits 23 to 27 142271 1.226
.8899
OQSO for x.bin using bits 22 to 26 141896 -.045
.4820
OQSO for x.bin using bits 21 to 25 141793 -.394
.3467
OQSO for x.bin using bits 20 to 24 142199 .982
.8369
OQSO for x.bin using bits 19 to 23 141853 -.191
.4243
OQSO for x.bin using bits 18 to 22 142304 1.338
.9095
OQSO for x.bin using bits 17 to 21 141894 -.052
.4793
OQSO for x.bin using bits 16 to 20 142190 .951
.8293
OQSO for x.bin using bits 15 to 19 142080 .579
.7186
OQSO for x.bin using bits 14 to 18 141535 -1.269
.1022
OQSO for x.bin using bits 13 to 17 141281 -2.130
.0166
OQSO for x.bin using bits 12 to 16 141605 -1.032
.1511
OQSO for x.bin using bits 11 to 15 141979 .236
.5934
OQSO for x.bin using bits 10 to 14 142508 2.029
.9788
OQSO for x.bin using bits 9 to 13 141604 -1.035
.1503
OQSO for x.bin using bits 8 to 12 142042 .450
.6735
OQSO for x.bin using bits 7 to 11 141322 -1.991
.0232
OQSO for x.bin using bits 6 to 10 141957 .162
.5642
OQSO for x.bin using bits 5 to 9 142021 .379
.6475
OQSO for x.bin using bits 4 to 8 141770 -.472
.3184
OQSO for x.bin using bits 3 to 7 141947 .128
.5508
OQSO for x.bin using bits 2 to 6 142510 2.036
.9791
OQSO for x.bin using bits 1 to 5 142321 1.395
.9186
DNA for x.bin using bits 31 to 32 141878 -.092
.4632
DNA for x.bin using bits 30 to 31 141735 -.514
.3035
DNA for x.bin using bits 29 to 30 141778 -.387
.3492
DNA for x.bin using bits 28 to 29 141774 -.399
.3449
DNA for x.bin using bits 27 to 28 141720 -.558
.2883
DNA for x.bin using bits 26 to 27 142461 1.627
.9482
DNA for x.bin using bits 25 to 26 141398 -1.508
.0657
DNA for x.bin using bits 24 to 25 142133 .660
.7453
DNA for x.bin using bits 23 to 24 141696 -.629
.2646
DNA for x.bin using bits 22 to 23 142561 1.922
.9727
DNA for x.bin using bits 21 to 22 141873 -.107
.4573
DNA for x.bin using bits 20 to 21 142091 .536
.7040
DNA for x.bin using bits 19 to 20 141760 -.440
.3298
DNA for x.bin using bits 18 to 19 141596 -.924
.1777
DNA for x.bin using bits 17 to 18 141529 -1.122
.1309
DNA for x.bin using bits 16 to 17 141948 .114
.5454
DNA for x.bin using bits 15 to 16 141440 -1.384
.0831
DNA for x.bin using bits 14 to 15 142432 1.542
.9384
DNA for x.bin using bits 13 to 14 142393 1.427
.9232
DNA for x.bin using bits 12 to 13 141961 .152
.5606
DNA for x.bin using bits 11 to 12 141913 .011
.5043
DNA for x.bin using bits 10 to 11 142230 .946
.8279
DNA for x.bin using bits 9 to 10 141845 -.190
.4247
DNA for x.bin using bits 8 to 9 141732 -.523
.3005
DNA for x.bin using bits 7 to 8 141756 -.452
.3255
DNA for x.bin using bits 6 to 7 141455 -1.340
.0901
DNA for x.bin using bits 5 to 6 141824 -.252
.4006
DNA for x.bin using bits 4 to 5 141868 -.122
.4515
DNA for x.bin using bits 3 to 4 141769 -.414
.3395
DNA for x.bin using bits 2 to 3 142202 .863
.8060
DNA for x.bin using bits 1 to 2 141032 -2.588
.0048
--------------------------------------------------------------------------------
Test results for x.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 x.bin 2568.59 .970 .833977
byte stream for x.bin 2462.91 -.525 .299960
--------------------------------------------------------------------------------
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 2482.32 -.250 .401278
bits 2 to 9 2610.31 1.560 .940625
bits 3 to 10 2451.90 -.680 .248173
bits 4 to 11 2481.71 -.259 .397921
bits 5 to 12 2525.09 .355 .638650
bits 6 to 13 2471.92 -.397 .345660
bits 7 to 14 2491.38 -.122 .451498
bits 8 to 15 2406.38 -1.324 .092748
bits 9 to 16 2445.56 -.770 .220667
bits 10 to 17 2574.36 1.052 .853518
bits 11 to 18 2543.38 .613 .730214
bits 12 to 19 2533.67 .476 .682996
bits 13 to 20 2471.52 -.403 .343549
bits 14 to 21 2427.97 -1.019 .154196
bits 15 to 22 2492.28 -.109 .456535
bits 16 to 23 2449.60 -.713 .237985
bits 17 to 24 2510.93 .155 .561425
bits 18 to 25 2397.49 -1.450 .073561
bits 19 to 26 2509.17 .130 .551591
bits 20 to 27 2479.58 -.289 .386392
bits 21 to 28 2500.83 .012 .504688
bits 22 to 29 2399.47 -1.422 .077559
bits 23 to 30 2485.62 -.203 .419424
bits 24 to 31 2493.47 -.092 .463199
bits 25 to 32 2503.61 .051 .520360
--------------------------------------------------------------------------------
CDPARK: result of ten tests on file x.bin
Of 12,000 tries, the average no. of successes
should be 3523 with sigma=21.9
Successes: 3489 z-score: -1.553 p-value: .060270
Successes: 3549 z-score: 1.187 p-value: .882429
Successes: 3535 z-score: .548 p-value: .708135
Successes: 3540 z-score: .776 p-value: .781201
Successes: 3552 z-score: 1.324 p-value: .907282
Successes: 3486 z-score: -1.689 p-value: .045562
Successes: 3503 z-score: -.913 p-value: .180558
Successes: 3567 z-score: 2.009 p-value: .977738
Successes: 3534 z-score: .502 p-value: .692266
Successes: 3522 z-score: -.046 p-value: .481790
square size avg. no. parked sample sigma
100. 3527.700 25.890
KSTEST for the above 10: p= .601719
--------------------------------------------------------------------------------
This is the MINIMUM DISTANCE test
for random integers in the file x.bin
Sample no. d^2 avg equiv uni
5 4.8736 1.4396 .992539
10 .5743 1.0346 .438517
15 .0240 .7956 .023864
20 .2070 .7401 .187859
25 .6987 .8709 .504496
30 1.4461 .8816 .766220
35 .4365 .9259 .355105
40 .4192 .8827 .343841
45 .4173 .8605 .342574
50 .3512 .8033 .297412
55 1.6349 .8762 .806617
60 1.8349 .8663 .841835
65 .6874 .9863 .498855
70 2.4023 .9729 .910574
75 .2816 .9982 .246483
80 .6624 .9967 .486076
85 .9017 .9857 .595941
90 .4408 .9721 .357885
95 1.9831 .9694 .863725
100 .0700 .9508 .067893
MINIMUM DISTANCE TEST for x.bin
Result of KS test on 20 transformed mindist^2's:
p-value= .497781
--------------------------------------------------------------------------------
The 3DSPHERES test for file x.bin
sample no: 1 r^3= 10.814 p-value= .30265
sample no: 2 r^3= 13.414 p-value= .36053
sample no: 3 r^3= 6.790 p-value= .20256
sample no: 4 r^3= 13.009 p-value= .35185
sample no: 5 r^3= 12.646 p-value= .34397
sample no: 6 r^3= 8.084 p-value= .23621
sample no: 7 r^3= 4.439 p-value= .13754
sample no: 8 r^3= 99.261 p-value= .96344
sample no: 9 r^3= 8.012 p-value= .23439
sample no: 10 r^3= 3.213 p-value= .10157
sample no: 11 r^3= 46.610 p-value= .78853
sample no: 12 r^3= 25.837 p-value= .57735
sample no: 13 r^3= 11.549 p-value= .31952
sample no: 14 r^3= 37.033 p-value= .70900
sample no: 15 r^3= 3.666 p-value= .11504
sample no: 16 r^3= 2.223 p-value= .07141
sample no: 17 r^3= 19.398 p-value= .47617
sample no: 18 r^3= 31.504 p-value= .65011
sample no: 19 r^3= 15.237 p-value= .39824
sample no: 20 r^3= 4.003 p-value= .12490
3DSPHERES test for file x.bin p-value= .939378
--------------------------------------------------------------------------------
RESULTS OF SQUEEZE TEST FOR x.bin
Table of standardized frequency counts
( (obs-exp)/sqrt(exp) )^2
for j taking values <=6,7,8,...,47,>=48:
.6 -.7 .3 3.0 .0 -1.0
-.5 -.2 -.7 -.9 -.4 1.2
-1.4 1.1 -1.4 1.3 .3 .3
-.6 .9 .0 -.5 .2 1.1
-1.6 1.0 .1 -.6 -1.6 2.5
.3 -.5 -.1 -1.5 -1.6 .4
.5 -.4 .9 -1.3 -1.3 -1.0
-.1
Chi-square with 42 degrees of freedom: 47.212
z-score= .569 p-value= .732183
______________________________________________________________
--------------------------------------------------------------------------------
Test no. 1 p-value .998119
Test no. 2 p-value .303507
Test no. 3 p-value .641075
Test no. 4 p-value .389275
Test no. 5 p-value .488078
Test no. 6 p-value .885272
Test no. 7 p-value .718623
Test no. 8 p-value .842957
Test no. 9 p-value .682483
Test no. 10 p-value .349455
Results of the OSUM test for x.bin
KSTEST on the above 10 p-values: .798854
--------------------------------------------------------------------------------
The RUNS test for file x.bin
Up and down runs in a sample of 10000
_________________________________________________
Run test for x.bin :
runs up; ks test for 10 p's: .298913
runs down; ks test for 10 p's: .242557
Run test for x.bin :
runs up; ks test for 10 p's: .157246
runs down; ks test for 10 p's: .022188
--------------------------------------------------------------------------------
Results of craps test for x.bin
No. of wins: Observed Expected
98155 98585.86
Chisq= 21.05 for 20 degrees of freedom, p= .60565
Throws Observed Expected Chisq Sum
SUMMARY FOR x.bin
p-value for no. of wins: .026986
p-value for throws/game: .605653
Test completed. File x.bin
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Douglas A. Gwyn
> Paul Pires wrote:
>>>Entropy = 7.752289 bits per byte.
> 'entropy'; many bits, high 'entropy'
No. The number is entropy *density*.
> (that 'entropy' it's only an estimate).
It should be an exact entropy computation relative to
the no-a-priori-information model.
>>>Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
>>Not a result reflecting a good random source.
> The first seems not bad. You can get 127.3 even with a good generator.
Out of a sample of 11534336 bytes? The expected s.d.m.
is 0.02176, so the observed s.e.m. is 6.47 times greater,
which would occur by pure chance (if the data really came
from a uniform random source) about 1 time in 1,000,000,000.
rex dickens
I'll try to answer them.
First let me say, I wrote this generator using vb6, I'm a complete novice to
realy any programing lanuage lessthan 1 month.
I'm trying to create a good random variation but needs to be repeatable.
I'm makeing a a simple stream encryption method I don't know alot about
using random function but found enough for this simple task, I could
defenitly use a better generator
I got the test sample by running a 11mb file of nothing(hex 00)
through the encryption program.
prety much it does this
x=some number
rnd -1
loop
randomize x
x = Int(2147483647 * Rnd)
random number byte= int(255*rnd)
loop
in the x= statement that number is just a few(i think) of a max long
variable, would it be better to find a way to do higher?
in the random number byte
should I use a higher value of 255
for a first try random number generator are the values in the test results
decent
Cristiano
> Cristiano wrote:
>> Paul Pires wrote:
>>> rex dickens <rdic...@cox.net> wrote ...
>>>> Entropy = 7.752289 bits per byte.
>> It depend on how many bits (or bytes) you supply: few bits, small
>> 'entropy'; many bits, high 'entropy'
>
> No. The number is entropy *density*.
I just wanna say that when I test many bits I get Entropy = 7.9999871,
but when I test few bits (of the same generator) I get 7.817234.
What does 'entropy density' mean?
> > (that 'entropy' it's only an estimate).
>
> It should be an exact entropy computation relative to
> the no-a-priori-information model.
I agree (I seen the code).
Some time ago, I seen in this ng something like this:
unsigned long counts[2][1024],state;
double entropy_bit(const int bit,const int update)
{
double p;
if(update) { counts[0][state]+=bit; ++counts[1][state]; }
else {
p=counts[0][state]/double(counts[1][state]);
if(!bit) p = 1.0 - p;
p = -(log(p) / M_LN2);
}
state <<= 1; state |= bit; state &= 1023;
return p;
}
The sender told me: "If this is correct, it should give you the 10-th
order prediction of the output.".
Can that code be related to the entropy relative to the
no-a-priori-information model?
>>>> Arithmetic mean value of data bytes is 127.3592 (127.5 = random).
>>> Not a result reflecting a good random source.
>> The first seems not bad. You can get 127.3 even with a good
>> generator.
>
> Out of a sample of 11534336 bytes?
No. Some time I get 127.3... when I test 20,000 bits of a good
generator.
> The expected s.d.m.
> is 0.02176, so the observed s.e.m. is 6.47 times greater,
> which would occur by pure chance (if the data really came
> from a uniform random source) about 1 time in 1,000,000,000.
Please, could you post the formulas?
Cristiano
Cristiano
>>> two different looks at the same result.
>>
>> Perhaps you're right. But the chi-square test seems more useful. Do
>> you agree?
>
> You mis-understand (I think). In the ENT package, these two tests
> are actually two different reports on a single analysis. Invert,
> scale and the results fall on top of each other, always.
I meant that the chi-square report seems useful (to me).
> There are really only
> three different tests in the ENT package. Throw out the entropy test
as it
> is not as precise in it's reporting and you loose nothing.
Usually I throw out the whole ENT package without lose nothing :-)
Cristiano
Tom St Denis
"Cyber Vagrant" <cyberv...@yahoo.com> wrote in message
news:9f8a576b.03021...@posting.google.com...
> I use Ent to test a varity combination generators I've been working on
> lately. Entropy is synonomous with randomness, more is better.
Not quite. Entropy is the measure of uncertainty. That is how many bits
does it require in a decision graph to distinguish this message from all
other messages. E.g. if you had only "yes" or "no" then only one bit would
be required.
The actual amount of "entropy" per message is not a fixed number. Say you
compress a text with deflate you might hit 3bpb which would indicate each
char has 3 bits of entropy. However, that same message through
BWT+RLE+MTF+Huffman [aka BZIP2] may hit 1.5bpb.
Tom
Cyber Vagrant
> I'm makeing a a simple stream encryption method I don't know alot about
> using random function but found enough for this simple task, I could
> defenitly use a better generator
I just started studing pseudo (repeatable) random number generators.
There seems to be two gereral catagories:
Linear Congruential types with a structural variation of:
x(s) = ( a * x(s-1) + b ) % m
where, s is the sequence number and b and m are constants. For the
'with carry' or 'with borrow' types b is the carry or borrow. for me
m is usually 2^32.
Lagged Fibonacci types with a structal variation of:
x(s) = ( x(s-p) @ x(s-q) ) % m
where p and q are the lag constants, and again for me m is usually 32.
The '@' can be any of +, -, *, xor. I prefer xor because it looks at
x(n) as a bunch of bits rather than as a number. With a number there
is a least significant end and a most significant end. and the digits
in between are treated with varing degrees of importance. This is
order, just what is tring to be avoided. Hence, my preference for
xor.
Generators I am currently working on are combinations of the Lagged
Fibonacci type using xor and lags between 1000 and 2000. I then
combine and alter the seperate outputs to isolate them from individual
analysis.
I have made similar combos with simple Multiply With Carry types that
appear to function just as well and without have to maintain the lag
tables, however I still prefer to aviod the use of arithemetic
operators.
Paul Pires
> for a first try random number generator are the values in the test results
> decent
Here is a direct answer for a direct question:
No, not even a little.
Paul
>
>
Cyber Vagrant
> does it require in a decision graph to distinguish this message from all
> other messages. E.g. if you had only "yes" or "no" then only one bit would
> be required.
Ok, so that is how you define entropy.
How do you define randomness as to distinguish it from uncertainy?
Douglas A. Gwyn
> Douglas A. Gwyn wrote:
>>Cristiano wrote:
>>>Paul Pires wrote:
>>>>rex dickens <rdic...@cox.net> wrote ...
>>>>Not a result reflecting a good random source.
>>>The first seems not bad. You can get 127.3 even with a good
>>>generator.
>>Out of a sample of 11534336 bytes?
> No. Some time I get 127.3... when I test 20,000 bits of a good
> generator.
But the actual amount of data used is crucial in
assessing the goodness of fit of the data to the model.
>>The expected s.d.m.
>>is 0.02176, so the observed s.e.m. is 6.47 times greater,
>>which would occur by pure chance (if the data really came
>>from a uniform random source) about 1 time in 1,000,000,000.
> Please, could you post the formulas?
This is standard statistics. The expectation value of the
variable, a.k.a. the mean, is the sum over possible values
of the value times the probability for the value. The use
of "probability" indicates that I am talking about the
hypothesis, which is of a uniform uncorrelated generator,
for which the probability of any particular value is 1/(k+1),
where the possible values are 0,1,2,...,k. For the example
at hand, k=255. One can readily compute directly from the
foregoing that the expectation value is k/2, or 127.5 in
this case. (You need to know that the sum for j = 0 through
k of j is k(k+1)/2, which can be proved by induction.) The
expected variance is the sum over possible values of the
square of the difference of the value from the mean times
the probability for that value. A bit of algebraic
manipulation reduces this, for the uniform model, to
k(k+2)/12. (You also need to know that the sum for j = 0
through k of j squared is k(k+1)(2k+1)/6, also provable by
induction.) The expected variance for the mean is the
variance for the value, divided by the sample size N; in
this case that's k(k+2)/(12N). The standard deviation is
the square root of the variance. Finally, you can use
inverse look up of the "sigmage" in a standard table of the
normal distribution to get an estimate of the probability
for a sample deviation from the mean to be as large as the
observed deviation (divide the deviation by the standard
deviation to get the "sigmage", usually denoted by z). You
most likely will have to subtract the table value, which is
for the logically complementary condition, from 1. The
particular table I used did not cover sigmages beyond 5.5,
so I used an approximate extrapolation. (There is a fairly
simple formula for tail values, but I didn't bother, for
the same reason that the table didn't cover such sigmages:
the probability of such deviation is so low that we are
utterly safe in rejecting the hypothesis that the data was
generated in accordance with the model.)
Douglas A. Gwyn
> "Cyber Vagrant" <cyberv...@yahoo.com> wrote ...
>> Entropy is synonomous with randomness, more is better.
> Not quite. Entropy is the measure of uncertainty. That is how many bits
> does it require in a decision graph to distinguish this message from all
> other messages. E.g. if you had only "yes" or "no" then only one bit would
> be required.
Cyber Vagrant was close enough at the level of understanding
needed for the job at hand. Entropy, like all measures of
information, is relative to context. The simple computation
performed by a program like "ent" uses a context in which
nothing is assumed about the data source; thus the source
probabilities are estimated from the observed data and that
is used to estimate the entropy; to do this correctly there
must be an adjustment for the loss of d.f. due to constraints.
An alternative is to assume the uniform-uncorrelated model (so
the probabilities are known a priori).
What is actually desired for cryptographic applications is
that the actual entropy (relative to complete knowledge of
the source) density be as close as possible to 1.0 bit per bit.
> The actual amount of "entropy" per message is not a fixed number. Say you
> compress a text with deflate you might hit 3bpb which would indicate each
> char has 3 bits of entropy. However, that same message through
> BWT+RLE+MTF+Huffman [aka BZIP2] may hit 1.5bpb.
Wrong. The entropy of a data sample (relative to a fixed
set of a priori information) is a constant, although you
might not know what the constant is. Different compressors
model the data in different ways, and if you naively use
them in an attempt to measure entropy you in effect merely
approximate the entropy (very imprecisely) relative to
the particular assumed model. Data with high entropy
density is nearly uncompressible.
Bryan Olson
> Cristiano wrote:
>> It depend on how many bits (or bytes) you supply: few bits, small
>> 'entropy'; many bits, high 'entropy'
>> (that 'entropy' it's only an estimate).
> No. The number is entropy *density*.
I think he's talking about a different issue. The formula ent
uses is what statisticians call a "biased estimator". It tends
to give too low a value. As the number of bytes increases, the
expected value of the estimate gets closer and closer to the
true value.
>
> It should be an exact entropy computation relative to
> the no-a-priori-information model.
No, there's a specific a-priori model: each octet independently
drawn with the same sample space probabilities.
--
--Bryan
Cristiano
>
>>> The expected s.d.m.
>>> is 0.02176, so the observed s.e.m. is 6.47 times greater,
>>> which would occur by pure chance (if the data really came
>>> from a uniform random source) about 1 time in 1,000,000,000.
>> Please, could you post the formulas?
>
> The particular table I used did not cover sigmages beyond 5.5,
I calculate the exact integral (using Simpson rule) to 15 digits. I get
an even less probability: 1 time in 10.24 billion.
That generator is really bad :-)
Cristiano
Cristiano
> Douglas A. Gwyn wrote:
> > Cristiano wrote:
>
> >> It depend on how many bits (or bytes) you supply: few bits, small
> >> 'entropy'; many bits, high 'entropy'
> >> (that 'entropy' it's only an estimate).
>
> > No. The number is entropy *density*.
>
> I think he's talking about a different issue. The formula ent
> uses is what statisticians call a "biased estimator". It tends
> to give too low a value. As the number of bytes increases, the
> expected value of the estimate gets closer and closer to the
> true value.
But using that formula any generator seems to have 8 bit per byte,
because if I test 20,000 bit say I get 7.8, with 1 Mb I can get 7.99,
with 1 Gb 7.99999.
This mean that asymptotically (which is what you call "true value") I
get 8 bit per byte for any generator (using ENT formula). It seems very
strange.
Cristiano
Bryan Olson
> Bryan Olson wrote:
>> The formula ent
>>uses is what statisticians call a "biased estimator". It tends
>>to give too low a value. As the number of bytes increases, the
>>expected value of the estimate gets closer and closer to the
>>true value.
>
> But using that formula any generator seems to have 8 bit per byte,
> because if I test 20,000 bit say I get 7.8, with 1 Mb I can get 7.99,
> with 1 Gb 7.99999.
>
> This mean that asymptotically (which is what you call "true value") I
> get 8 bit per byte for any generator (using ENT formula). It seems very
> strange.
Well, that agrees with what I've been saying, other than that
Cristiano says it seems strange. I don't think it's strange --
biased estimators are common. The best-known example is
probably the biased version of "sample variance". As the number
of samples grows, its expected value gets arbitrarily close to
the true variance, but for finite values, it's expected value is
lower than the variance.
The obvious question, open at least in this thread: is there a
simple computation for entropy, under the same assumptions, that
is unbiased? The assumptions are that each byte is
independently drawn from the same sample space with the same
probabilities. Note that there is a simple unbiased version of
sample variance: just use n-1 in the denominator in place of n,
where n is the number of samples. Could unbiased sample entropy
be so simple? I do not know.
--
--Bryan
Douglas A. Gwyn
> The obvious question, open at least in this thread: is there a
> simple computation for entropy, under the same assumptions, that
> is unbiased?
Usually for small samples (where this matters) I instead use
Kullback's information statistic to discriminate between
hypotheses. So long as one correctly identifies the degrees
of freedom, it is unbiased and has maximal power.
Cristiano
I'll do a web search for it. But do you know a link for that statistic?
Or can you give me a simple explanation?
Thanks
Cristiano
Cristiano
>
> The obvious question, open at least in this thread: is there a
> simple computation for entropy, under the same assumptions, that
Your question is interesting, but I prefer a more direct one: is there a
computation for entropy (even extremely complicated) which is useful for
something?
What I'm trying to say is that the entropy given by ENT seems to me
useless because almost all generators seem to have 8 bpb (if you test
many samples).
Cristiano
Mok-Kong Shen
Since you have apparently had quite some computational
experience in this, could you try AES in CTR mode
and see what entropy value you would get? Thanks.
M. K. Shen
Bryan Olson
> Your question is interesting, but I prefer a more direct one: is there a
> computation for entropy (even extremely complicated) which is useful for
> something?
You mean given the samples, estimate the entropy of the source?
No, there's no such computation.
> What I'm trying to say is that the entropy given by ENT seems to me
> useless because almost all generators seem to have 8 bpb (if you test
> many samples).
Right. It's just testing whether each of the 256 byte values
appears with near-equal frequency.
--
--Bryan
Mok-Kong Shen
Bryan Olson wrote:
>
> Cristiano wrote:
>
> > What I'm trying to say is that the entropy given by ENT seems to me
> > useless because almost all generators seem to have 8 bpb (if you test
> > many samples).
>
> Right. It's just testing whether each of the 256 byte values
> appears with near-equal frequency.
Thus the name ENT (plus the use of the term 'entropy'
in the software web page) is very misleading, I suppose.
M. K. Shen
Mok-Kong Shen
Bryan Olson wrote:
>
> Cristiano wrote:
>
> > Your question is interesting, but I prefer a more direct one: is there a
> > computation for entropy (even extremely complicated) which is useful for
> > something?
>
> You mean given the samples, estimate the entropy of the source?
> No, there's no such computation.
Very dumb question: How should one understand
nonetheless the estimate of 1.3 bits/character of
normal English (see AC)? Thanks.
M. K. Shen
Cristiano
> Cristiano wrote:
>
> > Your question is interesting, but I prefer a more direct one: is
> there a > computation for entropy (even extremely complicated) which
> is useful for > something?
>
> You mean given the samples, estimate the entropy of the source?
> No, there's no such computation.
I know :-(
I meant exactly what I wrote: "useful for something". When you see:
"Entropy= 7.98273" or "Entropy= 7.999283" (calculated by ENT), what does
it mean (for practical purposes)?
> > What I'm trying to say is that the entropy given by ENT seems to me
> > useless because almost all generators seem to have 8 bpb (if you
> test > many samples).
>
> Right. It's just testing whether each of the 256 byte values
> appears with near-equal frequency.
And is not the chi-square test better? At least you get a p-value, not a
raw value (like 7.91872) which tell me nothing.
Cristiano
Cristiano
From my point of view, you are perfectly right.
Cristiano
Cristiano
>
> Since you have apparently had quite some computational
> experience in this, could you try AES in CTR mode
> and see what entropy value you would get? Thanks.
If you really want this, I can do it. But if I test AES in CTR mode,
lcg, MT19937, MWC, and whatever you want I'll get very similar results.
I'm quite confident that we are wasting our time, because the "entropy"
value is really useless (at least for me).
Cristiano
Bryan Olson
>
> Bryan Olson wrote:
>>No, there's no such computation.
>
> Very dumb question: How should one understand
> nonetheless the estimate of 1.3 bits/character of
> normal English (see AC)? Thanks.
I don't know what the difficulty is in interpreting it, but
reading that paper by Shannon would probably help.
--
--Bryan
Mok-Kong Shen
My question is simple: You said that there can be
no computation that gives an 'estimate' of the entropy
of a source from given samples. AC cites a reference
giving an estimate of entropy of normal English.
These normal English sentences are 'samples' from
a source, namely utterances from English speaking
people. So, if one accepts what AC cites, then there
is a contradiction to what you stated (exsitence
vs non-existence of estimate). Could you clear up
this point? Thanks.
M. K. Shen
M. K. Shen
Mok-Kong Shen
I agree. I suggested trying AES only in case there
remained some opinions of entropy being measurable by
ENT (which is not the case). MT is said to have
excellent statistical properties. Thus with 'practical'
tests one should hardly be able to find indications
of its deviations from 'randomness'. But assigning
full entropy to MT is obviously not o.k. This suffices
to show in my view that it's infeasible to have any
concrete device/algorithm that is capable in practice
to universally 'measure' the entropy of a source. (See
also Olson's previous post.)
M. K. Shen
Bryan Olson
> Bryan Olson wrote:
>
>>The obvious question, open at least in this thread: is there a
>>simple computation for entropy, under the same assumptions, that
>>is unbiased?
>
> Usually for small samples (where this matters) I instead use
> Kullback's information statistic to discriminate between
> hypotheses.
That's not the situation here. If we knew of a statistic that
should differ between a given generator and a random source,
then we'd be in the market for likelihood estimation.
Here, we're given the stream and asked if it's random. We may
be able to find a statistic that lets us confidently reject the
hypothesis that it's random, but no matter how many tests we
run, we can never reject that it's non-random.
That said, there's every reason to ignore ent's so-called
"entropy" statistic. It's labeling in the output has misguided
many people. It's computed solely from the frequency counts,
and as Cristiano pointed out, the Chi-square test does a much
better job of that. The fact that it's biased is just one more
defect.
--
--Bryan
Bryan Olson
>
> Cristiano wrote:
>>What I'm trying to say is that the entropy given by ENT seems to me
>>useless because almost all generators seem to have 8 bpb (if you test
>>many samples).
>
> Since you have apparently had quite some computational
> experience in this, could you try AES in CTR mode
> and see what entropy value you would get? Thanks.
He tells you it's a bad test, so you want him to use it?
--
--Bryan
Mok-Kong Shen
See my recent reply to him.
M. K. Shen
John A. Malley
>
> Bryan Olson wrote:
>
>>Mok-Kong Shen wrote:
>> >
>> > Bryan Olson wrote:
>> >>You mean given the samples, estimate the entropy of the source?
>> >>No, there's no such computation.
>> >
>> > Very dumb question: How should one understand
>> > nonetheless the estimate of 1.3 bits/character of
>> > normal English (see AC)? Thanks.
>>
>>I don't know what the difficulty is in interpreting it, but
>>reading that paper by Shannon would probably help.
>>
>
> My question is simple: You said that there can be
> no computation that gives an 'estimate' of the entropy
> of a source from given samples. AC cites a reference
> giving an estimate of entropy of normal English.
No. He's discussing the estimated rate of the source (entropy per
symbol.)On page 234 of the second edition of Applied Cryptography we find:
"For a given language, the rate of the language is
r = H(M)/N
in which N is the length of the message. The rate of normal English
takes various values between 1.0 bits/letter and 1.5 bits/letter, for
large values of N. Shannon, in [1434], said that the entropy depends on
the length of text. Specifically he indicated a rate of 2.3 bits/letter
for 8-letter chunks, but the rate drops to between 1.3 and 1.5 for
16-letter chunks."
Reference [1434] in AC 2nd Ed. is
C.E. Shannon, "Predication and Entropy in Printed English," Bell System
Technical Journal, v. 30, n. 1, 1951, pp. 50-64.
The rate is related to the redundancy of the source. Source redundancy
affects key equivocation and message equivocation. Bryan Olson pointed
to the Shannon paper explaining this.
HTH,
John A. Malley
10266...@compuserve.com
Mok-Kong Shen
Sorry for my ignorance, for I don't yet understand.
Substitute 'estimated rate (entropy per symbol)'
for 'estimated entropy of source', doesn't one
still have a contradiction? I guess that Cristiano
would be satisfied if he could get such a 'rate'.
M. K. Shen
Douglas A. Gwyn
> What I'm trying to say is that the entropy given by ENT seems to me
> useless because almost all generators seem to have 8 bpb (if you test
> many samples).
That's because uniform-random-bit generators have that
*as a design goal*. The fact is that the one we were
discussing fails to meet this goal, badly enough that a
relatively simple statistical test detects the failure.
Douglas A. Gwyn
> I'll do a web search for it. But do you know a link for that statistic?
> Or can you give me a simple explanation?
If you can locate the source code that I published long ago,
which was included on Bruce Schneier's Applied Cryptography
disks under the name "i-hat", it includes Unix manual pages
(which are ASCII text files meant to be formatted but which
can be read with only moderate difficulty in themselves).
One link I found quickly through a Web search is:
http://tirnanog.ls.fi.upm.es/Servicios/Software/ap_crypt/disk1/i-hat.zip
I also posted formatted plain-ASCII versions of the manual
pages to this newsgroup a couple of months ago in response to
a long thread in which MKS kept going on about the absence of
proof-by-testing for randomness.
Mok-Kong Shen
I like to cite what Olson posted previously:
Here, we're given the stream and asked if it's random.
We may be able to find a statistic that lets us confidently
reject the hypothesis that it's random, but no matter how
many tests we run, we can never reject that it's non-random.
In my view, one could under circumstances be very
'confident' that one's source is of such a good quality
that the opponent can't discern any deviations from
'randomness', but that's certainly different from a
'proof' of randomness in the rigorous sensce of the word,
if I don't err.
M. K. Shen
Douglas A. Gwyn
> Could you clear up this point?
The estimation is not made on the basis of the data,
but rather on the basis of the use English speakers
can make of the data. If you just measured the 1st
order "entropy" of the data itself relative to a
flat-random model, you'd find a higher value than
when you give the same data to English speakers and
test how much redundancy they actually find in it.
The difference is primarily due to the differing
context (knowledge of English usage vs. assumption
of white noise).
What Bryan was referring to is the intractibility
of the problem of determining the minimum encoding
of a given (lengthy) data string. The source's
"absolute" entropy would be related to the length
of the minimal encoding, where by "absolute" I mean
without reference to any assumed model. But it is
a result of Chaitin (also Church & Goedel) that
there is no effective algorithm for computing the
length of the minimal encoding. Therefore, given
*arbitrary* data, in most cases we cannot compute
the "absolute" entropy. However, it is easy enough
to compute a close estimate of entropy relative to
various assumed models, such as the uniform-random
model.
Douglas A. Gwyn
> And is not the chi-square test better? At least you get a p-value,
> not a raw value (like 7.91872) which tell me nothing.
There is not "the" chi-square test; Pearson's chi-square is a
measure of the difference between two distributions (actual
or hyptothetical). It can be applied in a variety of contexts.
One could, with some effort, determine what the probability
is for a computed "entropy" measure to vary from the ideal by
as much is as actually observed. All such determinations
have to take into account the number of samples involved.
In this case it would be redundant, since we already know
(with practical certainty) from the excessive depression of
the observed mean value that there is bias in the sampled data.
Tom St Denis
> > Not quite. Entropy is the measure of uncertainty. That is how many bits
> > does it require in a decision graph to distinguish this message from all
> > other messages. E.g. if you had only "yes" or "no" then only one bit would
> > be required.
>
> Ok, so that is how you define entropy.
>
> How do you define randomness as to distinguish it from uncertainy?
Basically yes. A generator is "random" if you are uncertain about the
next output with uniform probability. That is you need the whole bit
of output to know what the next output will be.
Wierd, well consider a PRNG that emits 8 bits at a time. If you could
tell what the whole output was with only say 2 of the 8 bits then
there is only 2 bits of entropy in the output.
the "entropy" of the output would be how many bits you need to know
what the next output will be. A perfect PRNG will require you to grab
all of the bits. Other PRNGs [e.g. a LFSR for instance] will only
need a small fraction of the bits to determine the output.
Tom
Douglas A. Gwyn
> I like to cite what Olson posted previously:
> Here, we're given the stream and asked if it's random.
> We may be able to find a statistic that lets us confidently
> reject the hypothesis that it's random, but no matter how
> many tests we run, we can never reject that it's non-random.
> In my view, one could under circumstances be very
> 'confident' that one's source is of such a good quality
> that the opponent can't discern any deviations from
> 'randomness', but that's certainly different from a
> 'proof' of randomness in the rigorous sensce of the word,
> if I don't err.
It's strange that you "like to cite what Olson posted"
but then immediately contradict it in your own view.
In fact one can *never* gain confidence in the randomness
of a source merely by testing a finite stretch of its
output. (The source could be designed to switch to an
all-0 stream this coming midnight.) There are two
related alternatives, however: (1) one *can*, in some
instances, merely by testing a long run of output gain
confidence that a source is *not* following a specific
random model; or (2) one can gain confidence in a true
random source's randomness by inspection and analysis of
its design and construction.
Douglas A. Gwyn
> Basically yes. A generator is "random" if you are uncertain about the
> next output with uniform probability. That is you need the whole bit
> of output to know what the next output will be.
> Wierd, well consider a PRNG that emits 8 bits at a time. If you could
> tell what the whole output was with only say 2 of the 8 bits then
> there is only 2 bits of entropy in the output.
> the "entropy" of the output would be how many bits you need to know
> what the next output will be. A perfect PRNG will require you to grab
> all of the bits. Other PRNGs [e.g. a LFSR for instance] will only
> need a small fraction of the bits to determine the output.
The above is nearly entirely wrong, and the most likely result
of posting it will be to confuse novices and stretch out the
discussion much longer than was necessary while we correct the
new misunderstandings.
Cristiano
>
> the "entropy" of the output would be how many bits you need to know
> what the next output will be.
I think this is totally wrong.
> A perfect PRNG will require you to grab all of the bits. Other PRNGs
[e.g. a LFSR for instance] will only need a small fraction of the bits
to determine the output.
You say that a LFSR is not a "perfect PRNG", but this is true also for
MT19937, TT800, LFSR113, MWC, LCG, ... In other words all the PRNG are
not "perfect PRNG".
Cristiano
Cristiano
>
> [...]. MT is said to have
> excellent statistical properties. Thus with 'practical'
> tests one should hardly be able to find indications
> of its deviations from 'randomness'.
AFAIK there is no test able to find some weakness of MT (NIST, Maurer
and diehard find nothing).
> But assigning full entropy to MT is obviously not o.k.
But perhaps it can be useful to compare a "unknown" generator with a
good one.
I should try to see what happen, although iirc using that entropy value
any generator has the same "entropy".
> This suffices
> to show in my view that it's infeasible to have any
> concrete device/algorithm that is capable in practice
> to universally 'measure' the entropy of a source. (See
> also Olson's previous post.)
Agreed. Or we can say that the entropy measured in this way:
ent += prob[i] * log(1 / prob[i])
where prob[i] = count[i] / total_count
is useless when we test a prng (perhaps it is useful for other stuff).
Also the NIST test uses that formula, but, at least, it gives a p-value
and you can change the block size (for example 5 or 8 bits).
Cristiano
Cristiano
>
> [...]
> I guess that Cristiano would be satisfied if he could get such a
'rate'.
I don't know. I think the Pearson's chi-square is enough.
Cristiano
Mok-Kong Shen
I understand that the essential problem here is one
of (pedantic) theory vs (realistic) practice. One
has besides always errors (measurement, computer
roundings etc.). So a 'close estimate' is what
one actually should strive at and not any 'exact'
values (according to some theoretical models that
have themselves to be 'assumed' to be true). But
Cristiano has a 'practical' problem. He has sources
which are (let's say of unknown) nature having
statistical qualities that are comparable to the
good common PRNGs. Is it possible/sensible to
construct a good model and correspondingly compute
the 'entropy' of the source? I rather doubt that,
in view of the fact that MT and presumably also AES
in CTR mode etc. deliver sequences of excellent
statistical qualities and (at least intuitively)
these shouldn't contain very much entropy (rate in
bits per bit of the output sequence). Further,
is there a way to assess the 'goodness' of one's
model 'in general'? Could you say something on
these questions? Thanks in advance.
M. K. Shen
Mok-Kong Shen
A chi-square statistics is applied in diverse situations,
e.g. in the frequency test and the serial test etc. etc.
Like all statistics, it always gives something about the
confidence to reject a hypothesis computed on the data
being used in the test. (Subsequent sample data sets may
yield somewhat different values.) It never 'proves'
anything but in my view only 'helps' you to more or less
(but not entirely) objectively build up your 'belief'
in the goodness of the random source being tested.
(See another follow-up concerning PRNGs.)
M. K. Shen
Mok-Kong Shen
The NIST test suite has apparently been done with
some serious effort and hence should presumably
always be preferred in testing random sequences,
I suppose. Concerning diehard I am under the
impression (I have never used the package) that
its result may be rather difficult to interpret
concisely. As someone noted recently, the foundations
of some its tests are also not very well explained
in the documents. What's your opinion of diehard
from your experiences todate?
I could err, but in my view it is in any case not
very sensible to assign an entropy to sources that
are PRNGs. My thought goes as follows: Suppose
one flips a fair coin and gets 128 bits and uses
that as a key to AES in CTR mode. This is a PRNG
with a period of 2^128. So from 128 'genuine' bits
one derives 2^128*128 bits. Now how much 'entropy'
(rate in bits per bit of the sequence generated)
would you expect to get for that 'source'?
BTW, I have a related problem. Hashing is generally
considered as a good means to condense the entropy
of a sequence from a source not having full entropy,
if I don't err. How about the reverse process of
'dilution' of entropy. In the above example, from
128 bits a huge quantity of bits are generated.
This is an extreme dilution. What if one wants
only a 'moderate dilution', say generating m*128
bits sufficiently well randomly, with m of the
order of say 100? Are there any methods of doing
that?
Thanks.
M. K. Shen
Mok-Kong Shen
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > I like to cite what Olson posted previously:
> > Here, we're given the stream and asked if it's random.
> > We may be able to find a statistic that lets us confidently
> > reject the hypothesis that it's random, but no matter how
> > many tests we run, we can never reject that it's non-random.
> > In my view, one could under circumstances be very
> > 'confident' that one's source is of such a good quality
> > that the opponent can't discern any deviations from
> > 'randomness', but that's certainly different from a
> > 'proof' of randomness in the rigorous sensce of the word,
> > if I don't err.
>
> It's strange that you "like to cite what Olson posted"
> but then immediately contradict it in your own view.
No. I did't contradict the quote from Olson but in
fact agreed with him that it is 'impossible 'to 'verify'
randomness (rigorously) with any (practical) tests.
In my view, any claim of good approximation of
randomness must contain more or less subjectivity.
If I conducted all statistical tests known in the
public community and obtain satisfactory statistics
(at high confidence levels), then I personally would
have sufficient confidence (i.e. well 'believe')
that the source is well random (a good approximation
of randomness), if the generation is done in hardware.
But that is evidently not entirely objective. For
PRNG, the 'P' recalls that 'nothing' is 'really'
random but that it's only something that 'looks like'
random, i.e. something that only serves for 'deception'.
>
> In fact one can *never* gain confidence in the randomness
> of a source merely by testing a finite stretch of its
> output. (The source could be designed to switch to an
> all-0 stream this coming midnight.) There are two
> related alternatives, however: (1) one *can*, in some
> instances, merely by testing a long run of output gain
> confidence that a source is *not* following a specific
> random model; or (2) one can gain confidence in a true
> random source's randomness by inspection and analysis of
> its design and construction.
I suppose that you confirm here what I said about
'subjectivity' above. To repeat: In crypto one
generally desires random sequences of a uniform
distribution. One can apply tests to detect (possible)
deviations from randomness of such a model but never
'prove' randomness (see the quote from Olson). The
practical evaluation of 'entropy' of a source is
at best (in case of hardware generation) an
approximation. I consider it to be not sensible
to assign any entropy value to PRNG sources.
M. K. Shen
Cyber Vagrant
> I meant exactly what I wrote: "useful for something". When you see:
> "Entropy= 7.98273" or "Entropy= 7.999283" (calculated by ENT), what does
> it mean (for practical purposes)?
>
> > > What I'm trying to say is that the entropy given by ENT seems to me
> > > useless because almost all generators seem to have 8 bpb (if you
> > test > many samples).
> >
> > appears with near-equal frequency.
>
> raw value (like 7.91872) which tell me nothing.
>
I tried to explain that the figure here for practal purposes is a
measure of randomness(uncertainty if you like), in this case the
opposite of order(I also suppose you could certainty).
You can turn it in to a percent. Just divide the result by the bit
lenght of the samples. Then one could say the the measured sample is
XX% random or has ( 100 - XX% ) residue order.
The Ent result for entropy is a crude measure.
In this case it tells me if I get it close to 8.0 that is 7.9 with
three or four 9s following that the generator is faily uniform in
producing all the different combinations of 8 bit patterns.
I'd like it, if Ent would allow selection of different sample widths
like 16, 32 or 64. Guess I'll have to tweak the code for that :)
Cristiano
>
> I tried to explain that the figure here for practal purposes is a
> measure of randomness(uncertainty if you like), in this case the
> opposite of order(I also suppose you could certainty).
>
> You can turn it in to a percent. Just divide the result by the bit
> lenght of the samples. Then one could say the the measured sample is
> XX% random or has ( 100 - XX% ) residue order.
>
> The Ent result for entropy is a crude measure.
Yes, crude and useless :-)
I done what your said.
I tested 3 prng: MT19937, a 32-bit LCG and a maximal length 32-bit LFSR.
I calculated (using ent algorithm) the entropy for 20 sets of length N
bytes and I used the average for the followig calculations.
For sample size N = 2,000,000 bytes I got:
ENTROPY ENTROPY / N
MT: 7,9999102439 3,999955122e-6
LCG: 7,9999562949 3,999978147e-6
LFSR: 7,9999053902 3,999952695e-6
For sample size N = 500,000 bytes I got:
ENTROPY ENTROPY / N
MT: 7,999633448 1,599926690e-5
LCG: 7,999812335 1,599962467e-5
LFSR: 7,999638273 1,599927655e-5
Using your definition MT19937 has about 99.999996% of "residue order"
(!?) when I test 2e6 bytes and 99.999984% when I test 5e5 bytes.
Do you think these values are somehow useful?
> In this case it tells me if I get it close to 8.0 that is 7.9 with
> three or four 9s following that the generator is faily uniform in
> producing all the different combinations of 8 bit patterns.
>
> I'd like it, if Ent would allow selection of different sample widths
> like 16, 32 or 64. Guess I'll have to tweak the code for that :)
You can bet! But this is a simple task. Just use short, long and long
long types for ccount, but the memory request will be extremely high.
Cristiano
Cristiano
Agreed. That p-value is much more useful than the raw value of the
"entropy".
If I understand correctly, the ratio r = H(M)/N should be about the same
to which Cyber Vagrant is referring to when he says: "You can turn it in
to a percent. Just divide the result [the entropy] by the bit lenght of
the samples.".
But in my reply you can see the uselessness of this ratio (for our
purposes).
Cristiano
Cristiano
I tried to compile your code, but it's to hard for me. Also I read the
post on Dec 2002 but I have found nothing.
In your code I haven't seen a function called Kullback. Instead I seen
many functions and the line
Print( "2info = %5.2f\tdf = %2d\tq = %7.4f\n",
info, infodf, QChiSq( info, infodf ) );
in the main function.
I guess the p-value QChiSq( info, infodf ) is gotten from the Kullback
statistic. Am I right?
Cristiano
Cristiano
>
> The NIST test suite has apparently been done with
> some serious effort and hence should presumably
> always be preferred in testing random sequences,
> I suppose.
Preferred to ent.
> Concerning diehard I am under the
> impression (I have never used the package) that
> its result may be rather difficult to interpret
> concisely.
Very difficult (at least for me).
Right now I'm testing my new (p-)rng and it seems good. But in my P2 450
MHz it fail opso, oqso and dna tests, but I'm not able to find the
weakness.
> As someone noted recently, the foundations
> of some its tests are also not very well explained
> in the documents.
I guess you meant "is not explained" :-)
> What's your opinion of diehard from your experiences todate?
In the new diehard, the Birthday Spacings test seems bad, so I replaced
it with the old version.
The operm5 test (which was a bit "strange") now seems good.
The real bad thing in diehard is that the author doesn't give any
technical support. The posts in this ng about diehard show what I say.
Cristiano
Cyber Vagrant
I meant to say "residual order". Those results good, you got 9s for
three and four orders of magnitude. I think for practical purposes
that's as good as it gets. I have to look into how the figure rises
with more samples. Still, it is a standard statistical measure,
right?
With the GFSRs I've been playing with I can get four or five orders of
nines of raw entropy. I just use the figure as a measure of
improvement or degradation when I tweak the structure and parameters
of the generator.
I've noticed that an improvement can usually be made over a single
generator by combination and some sort of jitterizing, but I can get
only so much improvement before futher elaboration on the design
causes a decline in performance or simply fails to produce any futher
improvement.
So, to answer your question is it useful? Yes, in this limited way:
Did the change in the design make it better or worse from the
perspective of entropy?
Douglas A. Gwyn
> I tried to compile your code, but it's to hard for me.
? It should compile under any standard-conforming C
implementation. If not, I'd appreciate hearing exactly
what diagnostics were produced.
> Also I read the post on Dec 2002 but I have found nothing.
In Google groups, tot_info's manual page is in my posting of
2002-12-04 11:14:04 PST; chi_sq and gamma manual pages are
in my posting of 2002-12-13 09:45:00 PST.
> In your code I haven't seen a function called Kullback.
Kullback's I-hat statistic is computed by InfoTbl.
> Print( "2info = %5.2f\tdf = %2d\tq = %7.4f\n",
> info, infodf, QChiSq( info, infodf ) );
> I guess the p-value QChiSq( info, infodf ) is gotten from
> the Kullback statistic. Am I right?
Yes, actually from twice Kullback's I-hat, which has an
asymptotic chi-square distribution.
Douglas A. Gwyn
> Cristiano has a 'practical' problem. He has sources
> which are (let's say of unknown) nature having
> statistical qualities that are comparable to the
> good common PRNGs. Is it possible/sensible to
> construct a good model and correspondingly compute
> the 'entropy' of the source?
It is *easy* to compute the entropy density for some
simple random source model. The real question is how
well it really models the given data. Even though one
might start out with no a priori knowledge about an
actual source, one can sometimes figure out enough
about how the source operates to come up with a good
model for it. We call that procedure "cryptanalysis".
Sometimes fitting an HMM to the data is revealing.
> is there a way to assess the 'goodness' of one's
> model 'in general'?
Sure. How well does it agree with the observed data?
Bryan Olson
> I'd like it, if Ent would allow selection of different sample widths
> like 16, 32 or 64. Guess I'll have to tweak the code for that :)
How many samples do you think you'd need in order to test if
64-bit values are generated with approximately equal frequency?
--
--Bryan
Mok-Kong Shen
"Douglas A. Gwyn" wrote:
>
> It is *easy* to compute the entropy density for some
> simple random source model.
Could you please elaborate a little bit through giving
a tiny example? (I suppose one doesn't in modelling e.g.
simply 'assume' that the bits are 'random', i.e. of full
entropy.) Thanks.
M. K. Shen
Cristiano
>
> I meant to say "residual order". Those results good, you got 9s for
> three and four orders of magnitude. I think for practical purposes
> that's as good as it gets. I have to look into how the figure rises
> with more samples. Still, it is a standard statistical measure,
> right?
What should "a standard statistical measure" be?
> With the GFSRs I've been playing with I can get four or five orders of
> nines of raw entropy. I just use the figure as a measure of
> improvement or degradation when I tweak the structure and parameters
> of the generator.
Uh? Are you using that "entropy" to tweak a generator!?
What do you hope to see with that "entropy"?
You'd better to use a real test. Even fips-140 is better!
> I've noticed that an improvement can usually be made over a single
> generator by combination and some sort of jitterizing, but I can get
> only so much improvement before futher elaboration on the design
> causes a decline in performance or simply fails to produce any futher
> improvement.
>
> So, to answer your question is it useful? Yes, in this limited way:
> Did the change in the design make it better or worse from the
> perspective of entropy?
You already know my answer: the entropy used in ent is totally useless,
from my point of view, to test a generator.
Look at the code:
prob[i] = (double) ccount[i] / totalc;
entropy = f( prob[i] );
and you get a meaningless raw value or a value very hard to interpret.
There is also the line: chisq = chisq + (a * a) / cexp.
With chisq, ent calculates a p-value relative to the same analysis (like
Paul Pires also told). If you use this p-value instead of "entropy" you
have a much more readable report.
My suggestion: forget "entropy" and use chi-square.
An even better suggestion: forget "ent" and use a better test :-)
Cristiano
Cristiano
> Cristiano wrote:
>> I tried to compile your code, but it's to hard for me.
>
> ? It should compile under any standard-conforming C
> implementation. If not, I'd appreciate hearing exactly
> what diagnostics were produced.
I'm using Borland C++ Builder which should be the most out-of-standard
compiler in the world :-)
One thing seem strange (for a windows programmer): there is #include
"std.h" but this file there isn't in i-hat.zip. It is included in info.c
and I guess the lines:
END OF info.c
echo 'std.h' 1>&2
cat >'std.h' <<'END OF std.h'
should do something of useful... I simply created a new file called
std.h.
> > Also I read the post on Dec 2002 but I have found nothing.
>
> In Google groups, tot_info's manual page is in my posting of
> 2002-12-04 11:14:04 PST; chi_sq and gamma manual pages are
> in my posting of 2002-12-13 09:45:00 PST.
Thank you I'll see those posts.
>> Print( "2info = %5.2f\tdf = %2d\tq = %7.4f\n",
>> info, infodf, QChiSq( info, infodf ) );
>> I guess the p-value QChiSq( info, infodf ) is gotten from
> > the Kullback statistic. Am I right?
>
> Yes, actually from twice Kullback's I-hat, which has an
> asymptotic chi-square distribution.
This mean that for small infodf there is an error, I guess. Can you tell
me how big (or small) is that error?
Thanks
Cristiano
Cristiano
> Cristiano wrote:
>> I tried to compile your code, but it's to hard for me.
>
> ? It should compile under any standard-conforming C
> implementation. If not, I'd appreciate hearing exactly
> what diagnostics were produced.
I compiled your code and I compared it with your results: it works.
> > Also I read the post on Dec 2002 but I have found nothing.
>
> In Google groups, tot_info's manual page is in my posting of
> 2002-12-04 11:14:04 PST; chi_sq and gamma manual pages are
> in my posting of 2002-12-13 09:45:00 PST.
I read the manuals, but I really don't know how to use the Kullback
statistic in our test.
Please, could you show me an example?
Thank you
Cristiano
Cristiano
> Cristiano wrote:
>> I tried to compile your code, but it's to hard for me.
>
> ? It should compile under any standard-conforming C
> implementation. If not, I'd appreciate hearing exactly
> what diagnostics were produced.
Now your code is working and I'm comparing it with the p-values gotten
from Pearson's chi-square test.
I generate 256*4 pseudo-random bytes and I use 255 dof.
For 3 test, I got these p-values:
Pearson's Kullback
1) 0.106181968397376 0.999995537266834
2) 0.954981072869181 0.99999999998646
3) 0.497057423527765 0.999999998693001
Pearson's test seems more sensitive. Do you think it's the worth to use
Kullback?
Cristiano
Cyber Vagrant
> What do you hope to see with that "entropy"?
> You'd better to use a real test. Even fips-140 is better!
>
> My suggestion: forget "entropy" and use chi-square.
> An even better suggestion: forget "ent" and use a better test :-)
>
> Cristiano
The entropy value, as has been mentioned before, tops out easily, so
when that happenes I move on to...
The more meaningfull tests:
The Chi-Square, although in this implementaion it seem to jump between
25% 50% and 75% in single steps. In over a hundred runs I have yet to
see any value between these figures appear, so if I get it to say 50%
I'm happy.
The Monte Carlo test is my favorite, its a neat one, hard to get
better than 0.02%.
The Arithemetic average is of limited helpfullness.
The serial correlation is interesting, but seems little affected by
the changes I make, and even presents similar values for different
types of generators???
I'll have to have a look at Fips-140
Cristiano
>
> The more meaningfull tests:
>
> The Chi-Square, although in this implementaion it seem to jump between
> 25% 50% and 75% in single steps. In over a hundred runs I have yet to
> see any value between these figures appear, so if I get it to say 50%
> I'm happy.
25% is also good.
You should include in the code a function to calculate a more precise
p-value from the chi-square (there are many of such functions).
> The Monte Carlo test is my favorite, its a neat one, hard to get
> better than 0.02%.
You like only "strange" tests! :-)
> The Arithemetic average is of limited helpfullness.
Agreed.
But if you add some statistic to this test (as Douglas said) that test
could be a bit better.
> The serial correlation is interesting, but seems little affected by
> the changes I make, and even presents similar values for different
> types of generators???
My thought about that test is the same as for entropy test.
> I'll have to have a look at Fips-140
You have had an excellent idea! :-)
But do the next step: check out NIST test and Maurer too.
Cristiano
Douglas A. Gwyn
> "Douglas A. Gwyn" wrote:
>>It is *easy* to compute the entropy density for some
>>simple random source model.
> Could you please elaborate a little bit through giving
> a tiny example?
Shannon already did that.
> (I suppose one doesn't in modelling e.g.
> simply 'assume' that the bits are 'random', i.e. of full
> entropy.)
There is an important difference between random and
uniformly distributed. Of course we already know
the answer for a uniform-random bit generator.
Douglas A. Gwyn
> One thing seem strange (for a windows programmer): there is #include
> "std.h" but this file there isn't in i-hat.zip.
That was a local header that did such simple things as
typedef int bool;
#define false 0
#define true 1
I'm surprised the archive didn't include it, but it's
easy enough to just leave it out and then fix any errors
that result from such things not being defined.
> This mean that for small infodf there is an error, I guess.
> Can you tell me how big (or small) is that error?
The information computation is exact, so for example the
results of a batch of independent tests can be combined
by simply adding the infos and the dfs then looking up
the aggregate values in the inverse chi-square function.
One of the great features of this approach is that the
contributions to the total information can come from a
variety of sources, and conflicting information is taken
into account automatically (opposite signs on the info
part). This provides a general framework for choosing
among competing hypotheses in potentially confusing
environments, such as in intelligence assessment.
The inexactness is in the use of the inverse chi-square
"p" values for small d.f. However, they're close enough
for practical purposes, even for d.f. as small as 4 or 5.
Douglas A. Gwyn
> I read the manuals, but I really don't know how to use the Kullback
> statistic in our test.
> Please, could you show me an example?
The info_tbl manual page should have included an example
of its application in a cryptanalytic example.
Douglas A. Gwyn
> Now your code is working and I'm comparing it with the p-values gotten
> from Pearson's chi-square test.
Make sure you're using it appropriately.
The idea is to set up two or more categories that come
from potentially different distributions, then test
the likelihood that they all come from the same
distribution. With only one column, the d.f. is 0
so the result isn't interesting.
> Pearson's test seems more sensitive.
Actually the two tests have similar properties, but
Pearson's breaks down badly when some cells in the
table have too few (typically less than 5) entries,
whereas the discriminating-information measure works
all the way down to 0 entries. The discriminating
"power" of the information statistic is maximal
(over all statistics meeting the same conditions).
Cyber Vagrant
> > I'll have to have a look at Fips-140
>
> You have had an excellent idea! :-)
> But do the next step: check out NIST test and Maurer too.
>
I got Greg Rose's fip 140 source and ran it it only tests 20k bits
though. I have to write a shell for it to grab more samples.
I got the NIST suite too. Its just making me fustrated. The
documentation kinda skips over the basics. Like when you enter the
stream size on the command line calling assess, then some functions
asks you for a block size and then how many streams, its hard to
figure out how the stream gets chopped up.
I'm still pouring over the manual.
What I need is an algorithm to factor mersennes into primitives, or to
build them up from trinomials. I went out and looks at Knuth's set.
If I could only spare a yard and half :)
Cristiano
>
> I got Greg Rose's fip 140 source and ran it it only tests 20k bits
> though. I have to write a shell for it to grab more samples.
If you have the source just change it!
> I got the NIST suite too. Its just making me fustrated. The
> documentation kinda skips over the basics. Like when you enter the
> stream size on the command line calling assess, then some functions
> asks you for a block size and then how many streams, its hard to
> figure out how the stream gets chopped up.
>
> I'm still pouring over the manual.
If you don't have time to waste, I can send you my implementation. You
only need to fill a vector of bits and then call the test you like.
Cristiano
Cristiano
> Cristiano wrote:
>> Now your code is working and I'm comparing it with the p-values
>> gotten from Pearson's chi-square test.
>
> Make sure you're using it appropriately.
> The idea is to set up two or more categories that come
> from potentially different distributions, then test
> the likelihood that they all come from the same
> distribution. With only one column, the d.f. is 0
> so the result isn't interesting.
I generate 256*N bytes and I put them into 256 bins. This is the first
row (the first half of your vector f in the code).
Then I fill the second half of the vector with the expected frequency N
(an integer number). This is the second row.
There are 256 columns and 2 rows, so I have 255 d.f. like in Pearson's.
I'm wrong?
Thanks
Cristiano
Mok-Kong Shen
Perhaps I had not expressed myself properly. In doing
modelling for any phenomenon one assumes or hypothesize
something to pertain to the 'reality'. In most (or all)
cases a model discards many details and makes
'idealizations' to simplify the matter such that
some simple computations could be done. As discussed
previously, the goodness of a model could be checked
by comparing the results of the computation with
the reality. But such comparisons are in my view
more sensibly doable in engineering applications
and the like than in the present case of having
a source (of by assumption unknown nature) and
attempting to investigate its (inherent) randomness
or 'entropy'. What could one assume in constructing
a model? Assume independence, assume a frequency
distribution? What else? Alas, as discussed long ago,
no 'practical' test for independence is known. As to
distribution, one uses some sufficient amount of
samples and fits in a distribution. So now the model
gives quite good agreement (by construction) with
the distribution of frequency. But is that 'all'?
Does that tell us 'really' anything about 'randomness'
that is the goal of investigation? Consider the case
of a blackbox containing a very good PRNG, e.g. MT,
and one would see the questionability of such
approachs, I suppose.
M. K. Shen
Gregory G Rose
Cyber Vagrant <cyberv...@yahoo.com> wrote:
>I got Greg Rose's fip 140 source and ran it it only tests 20k bits
>though. I have to write a shell for it to grab more samples.
FIPS-140 is a *standard* and it specifies 20k
bits. By all means extend it, but by the time you
do that, you might as well write your own...
you'll need to recalculate all the statistical
bounds.
You might look on my page for "bias.c", which
will do basic balance/bias tests on truly huge
datasets. One day I'll probably implement large
file versions of the other tests that FIPS-140
does, but don't wait for me.
Greg.
--
Greg Rose INTERNET: g...@qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Cristiano
> In article <9f8a576b.03022...@posting.google.com>,
> Cyber Vagrant <cyberv...@yahoo.com> wrote:
>> I got Greg Rose's fip 140 source and ran it it only tests 20k bits
>> though. I have to write a shell for it to grab more samples.
>
> FIPS-140 is a *standard* and it specifies 20k
> bits. By all means extend it, but by the time you
> do that, you might as well write your own...
> you'll need to recalculate all the statistical
> bounds.
But you can also use the p-value instead of the bounds. In this way you
can test how many bits you want without any change.
For example, consider the poker test with m-bit blocks. Calculate its
statistic. HAC says that it follows a chi-square distribution with 2^m-1
d.f. so you just need to calculate the p-value (there are many functions
for this). If it fall outside your significance level the sequence (not
the generator) is bad.
Cristiano
Cyber Vagrant
> If you don't have time to waste, I can send you my implementation. You
> only need to fill a vector of bits and then call the test you like.
>
Sure, you got my address, if you need more than a 1MB I'll give you an
FTP account. I was considering seperating each test from the suite.
Cyber Vagrant
> 64-bit values are generated with approximately equal frequency?
I run as many as I could, 1,000,000 64bit value should give you a good idea.
Michael Amling
Hmm... If you find no duplicates among the one million values, how
close to uniform have you established that the distribution is?
--Mike Amling
David Wagner
Nope. Sorry, that's utterly wrong. Time to learn some more statistics...
Cyber Vagrant
> bits. By all means extend it, but by the time you
> do that, you might as well write your own...
> you'll need to recalculate all the statistical
> bounds.
>
I noticed would be more involved than I wanted to get :)
> You might look on my page for "bias.c", which
> will do basic balance/bias tests on truly huge
> datasets. One day I'll probably implement large
> file versions of the other tests that FIPS-140
> does, but don't wait for me.
I did, just have yet to look at it. Went to the store and looked for
something like numerical algorithms in C but everything is C++ on the
shelves.
Cyber Vagrant
Cristiano
>> If you don't have time to waste, I can send you my implementation.
>> You only need to fill a vector of bits and then call the test you
>> like.
>>
>
> Sure, you got my address, if you need more than a 1MB I'll give you an
> FTP account.
The zipped package is only 16K.
> I was considering seperating each test from the suite.
Good! Then I have what you need.
Cristiano
Cristiano
For Pearson's chi-square test you need *at least* 5*2^64 64-bit numbers.
Do you have this ram? :-)
Cristiano
Douglas A. Gwyn
> I generate 256*N bytes and I put them into 256 bins. This is the first
> row (the first half of your vector f in the code).
> Then I fill the second half of the vector with the expected frequency N
> (an integer number). This is the second row.
> There are 256 columns and 2 rows, so I have 255 d.f. like in Pearson's.
That is okay for Pearson's chi-square, but I suspect it's
problematic for the information statistic, because in fact
the two rows do *not* come from the same distribution; the
second row is not at all random. If we saw an actual
distribution come out exactly uniform like that we'd be
highly suspicious and would not likely believe that it had
been obtained by a random draw from the model source.
Stephen Avis
"Douglas A. Gwyn" <DAG...@null.net> ha scritto nel messaggio
news:3E5A141C...@null.net...
The information statistic that Cristiano is using measures the "closeness"
of two samples from each other without making any assumptions regarding
their underlying models. Since as Gwyn says the constant row is a very
long way from random it is not surprising that the statistic doesn't work as
expected.
Kullback in his book "Information Theory and Statistics" gives another
statistic that can be used for measuring the "distance" of a given sample
from a given model.
Taking the reference model to be random bytes this statistic becomes:
2 * Sum_over_i xi * log( xi * 256 / N )
where the xi correspond to the number of occurences of
byte i and
N = Sum_over_i xi.
For large N this statistic is again Chi Square.
With N = 1024 (which was Cristiano's original sample size) there is some
difference between the statistic as calculated (which has a mean of about
271) and the asymptotic chi square (which has a mean of 255).
Cyber Vagrant
>
> Nope. Sorry, that's utterly wrong. Time to learn some more statistics...
OK, statistic are a little foriegn to me. But, it some one ran a few
million through Ent I'd figure they'd get a basic idea.
Say, are you at UC Berkley? I was there once, I liked the double
helical stairs in the genetic research building :)
Cristiano
>
> Kullback in his book "Information Theory and Statistics" gives another
> statistic that can be used for measuring the "distance" of a given
> sample from a given model.
> Taking the reference model to be random bytes this statistic becomes:
> 2 * Sum_over_i xi * log( xi * 256 / N )
> where the xi correspond to the number of
> occurences of byte i and
> N = Sum_over_i xi.
> For large N this statistic is again Chi Square.
... with 255 d.f., I suppose. Also, I guess log is base 2.
That formula looks like the one used in ent:
ent += prob[i] * log(1 / prob[i])
where prob[i] = xi / N
and we seen that it is totally useless for our purpose.
I tried anyway your formula with 2048 samples and I get a very big
chi-square (2 * Sum_over_i... is about 28000) so the p-value= chi(2 *
Sum_over_i... ,255) = 1.
Do I have misundertood something?
> With N = 1024 (which was Cristiano's original sample size) there is
> some difference between the statistic as calculated (which has a mean
> of about 271) and the asymptotic chi square (which has a mean of 255).
I can generate many billion of samples. How many samples do you think
are needed?
Cristiano
Paul Crowley
> > >I run as many as I could, 1,000,000 64bit value should give you a good idea.
> >
> > Nope. Sorry, that's utterly wrong. Time to learn some more statistics...
>
> OK, statistic are a little foriegn to me. But, it some one ran a few
> million through Ent I'd figure they'd get a basic idea.
Well, that just means that you need to familiarise yourself with
statistics to make progress here. There's not a lot of point
subsituting wild guesses for knowledge.
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
Cristiano
>
> [...]. But, it some one ran a few
> million through Ent I'd figure they'd get a basic idea.
Sure, you'd get that ent is useless :-)
Cristiano
Douglas A. Gwyn
> The information statistic that Cristiano is using
> measures the "closeness" of two samples from each other
> without making any assumptions regarding their underlying
> models.
Thanks for stating that so clearly. I tried to make
that point back in December in response to MKS but I
guess I didn't make it clearly enough.
> Kullback in his book "Information Theory and Statistics"
[available as a Dover reprint]
> gives another statistic that can be used for measuring
> the "distance" of a given sample from a given model.
> Taking the reference model to be random bytes this
> statistic becomes:
> 2 * Sum_over_i xi * log( xi * 256 / N )
Since 256 and N are constant factors they can be pulled
out of the summation:
2 * {N * log 256 - N log N + Sum [xi * log(xi)]}.
If the statistic is being used merely to choose the most
likely of several alternatives, the constants can be
dropped, so one is just looking at the sum of x*log(x)
terms. (It needs to be understood that when x=0, x*log(x)
is to be evaluated as precisely 0, regardless of what
your math teacher tells you; another way of looking at it
is that those cases are omitted from the sum.) For use
in computing a "p value" via inverse chi-square lookup,
all the constant terms must be retained. This formula is
very close to the one used for I-hat, and probably there
is a way of looking at them that shows the equivalence.
The general use of x*log(x) as "weight of evidence" was
first applied to cryptologic problems by Alan Turing
(although there is some mention in passing by early
workers in statistics), and I.J. Good promoted this
methodology in many of his writings and lectures,
although I haven't seen widespread use of it by the
statistical mainstream. Of course, in the rather
specialized form of "Kullback-Liebler distance" the
idea is put to use by quite a few workers in pattern
recognition etc. (I think I had something to do with
this through my participation in an information fusion
workshop several years ago.)
Douglas A. Gwyn
> ... with 255 d.f., I suppose.
I'd have to think more about it. It's either that
or N - 1. I'm inclined to think the latter, since
the value computed by the formula Stephen gave is
roughly proportional to N.
> Also, I guess log is base 2.
It only matters for comparison chi-square values;
for that comparison, however, the *natural log*
must be used.
> That formula looks like the one used in ent:
> ent += prob[i] * log(1 / prob[i])
> where prob[i] = xi / N
It's not surprising, since that is proportional
to the sum of -x*log(x). Information is "negentropy".
> and we seen that it is totally useless for our purpose.
I'm not sure what your purpose is, but I find
information statistics very useful for cryptanalytic
purposes, especially when I don't have any obvious
model.
> I tried anyway your formula with 2048 samples and I get
> a very big chi-square ...
I'm not sure you should get such a large value, but
surely that would be *good*, since it lets you reject
the model with near certainty. Large chi-square means
poor fit of data to model.
What happens if df = N-1 is used?
> I can generate many billion of samples. How many samples
> do you think are needed?
Needed for what? If you find a significant discrepancy
between the data and the model, that's enough. Otherwise,
perhaps with more data you can find a discrepancy. It
does depend on the reality of the situation.
Stephen Avis
> Cristiano wrote:
> > ... with 255 d.f., I suppose.
>
> I'd have to think more about it. It's either that
> or N - 1. I'm inclined to think the latter, since
> the value computed by the formula Stephen gave is
> roughly proportional to N.
Actually, the formula that I quoted from Kullback is asymptotically
chi-square with 255 degrees of freedom and hence its mean value is also 255
thus, in
general, its value is not proportional to N.
I doesnt seem to be easy to make use of Kullback's mdi for small N (say from
5 to about 10 * df ) since
I cant find an easy way of converting the info_value into a reliable p value
(say correct to within 5% or so).
Asymptotically it is chi square and so the chi square function can be used
for large N.
For smaller values of N the chi square is not a good approximation to the
info_value's probability diistribution.
To see what I mean look at the N=1024 with df=255 example of Cristiano.
The mean of the correct distribution is about 271 whilst the mean of the chi
square is 255.
Indeed, the 'correct' p-value for an info_value of 255 is 0.27 (ish) whilst
the chi square gives 0.51.
Stephen Avis
"Cristiano" <cristi...@nsquipo.it> ha scritto nel messaggio
news:K7v6a.227556$0v.64...@news1.tin.it...
> Stephen Avis wrote:
> I tried anyway your formula with 2048 samples and I get a very big
> chi-square (2 * Sum_over_i... is about 28000) so the p-value= chi(2 *
> Sum_over_i... ,255) = 1.
Thats strange: 28000 doesnt seem reasonable (assuming the sample is random).
The mean value for a sample size of 2048 is about 261.
Just to be clear here is an example of how that formula is used.
df=255 as before
N= 10 ( ie a sample with 10 byte values)
and suppose that the we have just got the following sample of byte values
( 110, 112, 128, 125, 124, 130, 125, 125, 128, 113)
The occurences are:
125: 3
128: 2
110,112,113,124,130 1 each
others 0
thus for this sample the statistic has the value:
2*( 3*log( 3*256/10) + 2*log( 2 * 256 / 10 ) + 5*1*log( 1 * 256 / 10 ) )
= 74.2.
The mean value for this statistic (with df=255 and N=10) is about 65.
The correct calculated p-value for 74.2 turns out to be about 0.99 (which
just shows that the above sample was not very random).
Cyber Vagrant
> statistics to make progress here. There's not a lot of point
> subsituting wild guesses for knowledge.
Actually, I have quite a bit of homework to do now: Factoring
Primpolys, building orthogonal squares and Statistics. That ought to
keep me busy for the foreseeable future :)
Douglas A. Gwyn
> I cant find an easy way of converting the info_value into a
> reliable p value (say correct to within 5% or so).
Of course in principle one could prepare inverse-MDI tables.
However, the normal use of such statistics is either to
choose among alternatives, in which case the monotonicity
is all that matters, or to estimate the likelihood of some
observed event, which for small samples is inherently very
crude anyway. It might matter if one then took the "p
values" and used them in a Bayesian formula, etc., but if
one is taking an information-statistical approach it is more
useful to accrue all relevant information toward deciding
the hypothesis and evaluate the aggregate as the final step.