From: David Honig <honig@sprynet.com>
To: Mok-Kong Shen <cjh@osa.com.au>
Message Hash: 47fe540097b4aef561d55b8d1aa9d60b562ca5b29a004758eb6ae6d3a3de0a74
Message ID: <3.0.5.32.19981004135551.00888630@m7.sprynet.com>
Reply To: <m0zOxtY-0001eoC@magpie.osa.com.au>
UTC Datetime: 1998-10-04 08:09:42 UTC
Raw Date: Sun, 4 Oct 1998 16:09:42 +0800
From: David Honig <honig@sprynet.com>
Date: Sun, 4 Oct 1998 16:09:42 +0800
To: Mok-Kong Shen <cjh@osa.com.au>
Subject: Re: Randomness testing
In-Reply-To: <m0zOxtY-0001eoC@magpie.osa.com.au>
Message-ID: <3.0.5.32.19981004135551.00888630@m7.sprynet.com>
MIME-Version: 1.0
Content-Type: text/plain
At 11:13 AM 10/2/98 +0100, Mok-Kong Shen wrote:
>Clifford Heath wrote:
>>
>I suggest that you do at least Maurer's test which is described
>in A. J. Menezes et al. Handbook of Applied Cryptography. The
>test is not difficult to code. You could also look at my code in
>http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1 in Fortran.
>
>M. K. Shen
>
/*
UELI.c
1 Oct 98
This implements Ueli M Maurer's
"Universal Statistical Test for Random Bit Generators"
using L=16
Accepts a filename on the command line;
writes its results, with other info, to stdout.
Handles input file exhaustion gracefully.
Ref: J. Cryptology v 5 no 2, 1992 pp 89-105
also on the web somewhere, which is where I found it.
-David Honig
honig@sprynet.com
Built with Wedit 2.3, lcc-win32
http://www.cs.virginia.edu/~lcc-win32
26 Sept CP Release
Version Notes:
This version does L=16. It evolved from an L=8 prototype
which I ported from the Pascal in the above reference.
I made the memory usage reasonable
by replacing Maurer's "block" array
with the 'streaming' fgetc() call.
Usage:
UELI filename
outputs to stdout
*/
#define L 16 // bits per block
#define V (1<<L) // number of possible blocks
#define Q (10*V) // at LEAST 10 * V, to assure each block seen
#define K (100*Q) // at LEAST 100 * Q, as large as possible
#define MAXSAMP (Q + K)
#include <stdio.h>
#include <math.h>
int main( int argc, char **argv )
{
FILE *fptr;
int i;
int b, c;
int table[V];
float sum=0.0;
int run;
// Human Interface
printf("UELI 26 Sep 98\nL=%d %d %d \n", L, V, MAXSAMP);
if (argc <2)
{printf("Usage: UELI filename\n"); exit(-1); }
else
printf("Measuring file %s\n", argv[1]);
// FILE IO
fptr=fopen(argv[1],"rb");
if (fptr == NULL) {printf("Can't find %s\n", argv[1]); exit(-1); }
// INIT
for (i=0; i<V; i++) table[i]=0;
for (i=0; i<Q; i++) {
b= fgetc(fptr)<<8 | fgetc(fptr);
table[ b ]=i;
}
printf("Init done\n");
// COMPUTE
run=1;
for (i=Q; run && i<Q+K; i++)
{
// COMPOSE A 16-bit quantity
b=fgetc(fptr); if (b<0) run=0;
c=fgetc(fptr); if (c<0) run=0;
if (run) { b = b<<8 | c;
sum += log( (double) ( i-table[b] ) ) ;
table[ b ]=i;
}
}
if (!run) printf("Premature end of file; read %d blocks.\n", i-Q);
sum = (sum/( (double) (i-Q) ) ) / log(2.0); // i should be K if enough
samples
printf("%s fTU= %f\n\n", argv[1], sum);
printf("Expected value for L=16 is 15.167379 \n");
// Add further interpretation/thresholding of the number of sigmas from
expected,
// and include the fudge factors explained in the paper.
} // end
Return to October 1998
Return to “Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>”