|
1 /* |
|
2 * Portions Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 */ |
|
16 |
|
17 |
|
18 /* -------------------------------------------------------------------------- |
|
19 Title : The NIST Statistical Test Suite |
|
20 |
|
21 Date : December 1999 |
|
22 |
|
23 Programmer : Juan Soto |
|
24 |
|
25 Summary : For use in the evaluation of the randomness of bitstreams |
|
26 produced by cryptographic random number generators. |
|
27 |
|
28 Package : Version 1.0 |
|
29 |
|
30 Copyright : (c) 1999 by the National Institute Of Standards & Technology |
|
31 |
|
32 History : Version 1.0 by J. Soto, October 1999 |
|
33 Revised by J. Soto, November 1999 |
|
34 Revised by Larry Bassham, March 2008 |
|
35 |
|
36 Keywords : Pseudorandom Number Generator (PRNG), Randomness, Statistical |
|
37 Tests, Complementary Error functions, Incomplete Gamma |
|
38 Function, Random Walks, Rank, Fast Fourier Transform, |
|
39 Template, Cryptographically Secure PRNG (CSPRNG), |
|
40 Approximate Entropy (ApEn), Secure Hash Algorithm (SHA-1), |
|
41 Blum-Blum-Shub (BBS) CSPRNG, Micali-Schnorr (MS) CSPRNG, |
|
42 |
|
43 Source : David Banks, Elaine Barker, James Dray, Allen Heckert, |
|
44 Stefan Leigh, Mark Levenson, James Nechvatal, Andrew Rukhin, |
|
45 Miles Smid, Juan Soto, Mark Vangel, and San Vo. |
|
46 |
|
47 Technical |
|
48 Assistance : Larry Bassham, Ron Boisvert, James Filliben, Daniel Lozier, |
|
49 and Bert Rust. |
|
50 |
|
51 Warning : Portability Issues. |
|
52 |
|
53 Limitation : Amount of memory allocated for workspace. |
|
54 |
|
55 Restrictions: Permission to use, copy, and modify this software without |
|
56 fee is hereby granted, provided that this entire notice is |
|
57 included in all copies of any software which is or includes |
|
58 a copy or modification of this software and in all copies |
|
59 of the supporting documentation for such software. |
|
60 -------------------------------------------------------------------------- */ |
|
61 //system include |
|
62 #include <e32base.h> |
|
63 #include <e32std.h> |
|
64 #include <e32cons.h> |
|
65 |
|
66 // user include |
|
67 #include "openc.h" |
|
68 #include "../include/decls.h" |
|
69 #include "../include/cephes.h" |
|
70 #include "../include/utilities.h" |
|
71 #include "../include/generators.h" |
|
72 |
|
73 typedef int (*CompareFnType)(const void*, const void*); |
|
74 |
|
75 void partitionResultFile(int numOfFiles, int numOfSequences, int option, int testNameID); |
|
76 void postProcessResults(int option); |
|
77 int cmp(const double *a, const double *b); |
|
78 int computeMetrics(char *s, int test); |
|
79 |
|
80 int |
|
81 StartNISTTest() |
|
82 { |
|
83 int i; |
|
84 int option = 10; /* TEMPLATE LENGTH/STREAM LENGTH/GENERATOR*/ |
|
85 char *streamFile = NULL; /* STREAM FILENAME */ |
|
86 |
|
87 |
|
88 tp.n = 1000000; // length of the individual bit stream(s) to be processed |
|
89 tp.blockFrequencyBlockLength = 128; |
|
90 tp.nonOverlappingTemplateBlockLength = 9; |
|
91 tp.overlappingTemplateBlockLength = 9; |
|
92 tp.approximateEntropyBlockLength = 10; |
|
93 tp.serialBlockLength = 16; |
|
94 tp.linearComplexitySequenceLength = 500; |
|
95 tp.numOfBitStreams = 100; |
|
96 chooseTests(); |
|
97 fixParameters(); |
|
98 openOutputStreams(option); |
|
99 invokeTestSuite(option, streamFile); |
|
100 fclose(freqfp); |
|
101 for( i=1; i<=NUMOFTESTS; i++ ) { |
|
102 if ( stats[i] != NULL ) |
|
103 fclose(stats[i]); |
|
104 if ( results[i] != NULL ) |
|
105 fclose(results[i]); |
|
106 } |
|
107 if ( (testVector[0] == 1) || (testVector[TEST_CUSUM] == 1) ) |
|
108 partitionResultFile(2, tp.numOfBitStreams, option, TEST_CUSUM); |
|
109 if ( (testVector[0] == 1) || (testVector[TEST_NONPERIODIC] == 1) ) |
|
110 partitionResultFile(MAXNUMOFTEMPLATES, tp.numOfBitStreams, option, TEST_NONPERIODIC); |
|
111 if ( (testVector[0] == 1) || (testVector[TEST_RND_EXCURSION] == 1) ) |
|
112 partitionResultFile(8, tp.numOfBitStreams, option, TEST_RND_EXCURSION); |
|
113 if ( (testVector[0] == 1) || (testVector[TEST_RND_EXCURSION_VAR] == 1) ) |
|
114 partitionResultFile(18, tp.numOfBitStreams, option, TEST_RND_EXCURSION_VAR); |
|
115 if ( (testVector[0] == 1) || (testVector[TEST_SERIAL] == 1) ) |
|
116 partitionResultFile(2, tp.numOfBitStreams, option, TEST_SERIAL); |
|
117 fprintf(summary, "------------------------------------------------------------------------------\n"); |
|
118 fprintf(summary, "RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES\n"); |
|
119 fprintf(summary, "------------------------------------------------------------------------------\n"); |
|
120 fprintf(summary, " C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST\n"); |
|
121 fprintf(summary, "------------------------------------------------------------------------------\n"); |
|
122 postProcessResults(option); |
|
123 fclose(summary); |
|
124 |
|
125 return 1; |
|
126 } |
|
127 |
|
128 void |
|
129 partitionResultFile(int numOfFiles, int numOfSequences, int option, int testNameID) |
|
130 { |
|
131 int i, k, m, j, start, end, num, numread; |
|
132 float c; |
|
133 FILE **fp = (FILE **)calloc(numOfFiles+1, sizeof(FILE *)); |
|
134 int *results = (int *)calloc(numOfFiles, sizeof(int *)); |
|
135 char *s[MAXFILESPERMITTEDFORPARTITION]; |
|
136 char resultsDir[200]; |
|
137 |
|
138 for ( i=0; i<MAXFILESPERMITTEDFORPARTITION; i++ ) |
|
139 s[i] = (char*)calloc(200, sizeof(char)); |
|
140 |
|
141 sprintf(resultsDir, "%s\\experiments\\%s\\%s\\results", gLogFilePath.PtrZ(), generatorDir[option], testNames[testNameID]); |
|
142 |
|
143 if ( (fp[numOfFiles] = fopen(resultsDir, "r")) == NULL ) { |
|
144 printf("%s", resultsDir); |
|
145 printf(" -- file not found. Exiting program.\n"); |
|
146 exit(-1); |
|
147 } |
|
148 |
|
149 for ( i=0; i<numOfFiles; i++ ) |
|
150 { |
|
151 sprintf(s[i], "%s\\experiments\\%s\\%s\\data%d", gLogFilePath.PtrZ(), generatorDir[option], testNames[testNameID], i+1); |
|
152 } |
|
153 numread = 0; |
|
154 m = numOfFiles/20; |
|
155 if ( (numOfFiles%20) != 0 ) |
|
156 m++; |
|
157 for ( i=0; i<numOfFiles; i++ ) { |
|
158 if ( (fp[i] = fopen(s[i], "w")) == NULL ) { |
|
159 printf("%s", s[i]); |
|
160 printf(" -- file not found. Exiting program.\n"); |
|
161 exit(-1); |
|
162 } |
|
163 fclose(fp[i]); |
|
164 } |
|
165 for ( num=0; num<numOfSequences; num++ ) { |
|
166 for ( k=0; k<m; k++ ) { /* FOR EACH BATCH */ |
|
167 |
|
168 start = k*20; /* BOUNDARY SEGMENTS */ |
|
169 end = k*20+19; |
|
170 if ( k == (m-1) ) |
|
171 end = numOfFiles-1; |
|
172 |
|
173 for ( i=start; i<=end; i++ ) { /* OPEN FILE */ |
|
174 if ( (fp[i] = fopen(s[i], "a")) == NULL ) { |
|
175 printf("%s", s[i]); |
|
176 printf(" -- file not found. Exiting program.\n"); |
|
177 exit(-1); |
|
178 } |
|
179 } |
|
180 |
|
181 for ( j=start; j<=end; j++ ) { /* POPULATE FILE */ |
|
182 fscanf(fp[numOfFiles], "%f", &c); |
|
183 fprintf(fp[j], "%f\n", c); |
|
184 numread++; |
|
185 } |
|
186 |
|
187 for ( i=start; i<=end; i++ ) /* CLOSE FILE */ |
|
188 fclose(fp[i]); |
|
189 } |
|
190 } |
|
191 fclose(fp[numOfFiles]); |
|
192 for ( i=0; i<MAXFILESPERMITTEDFORPARTITION; i++ ) |
|
193 free(s[i]); |
|
194 |
|
195 free(fp); |
|
196 free(results); |
|
197 return; |
|
198 } |
|
199 |
|
200 int |
|
201 cmp(const double *a, const double *b) |
|
202 { |
|
203 if ( *a < *b ) |
|
204 return -1; |
|
205 if ( *a == *b ) |
|
206 return 0; |
|
207 return 1; |
|
208 } |
|
209 |
|
210 void |
|
211 postProcessResults(int option) |
|
212 { |
|
213 int i, k; |
|
214 int randomExcursionSampleSize = 0; |
|
215 int generalSampleSize = 0; |
|
216 int case1, case2, numOfFiles = 2; |
|
217 double passRate; |
|
218 char s[200]; |
|
219 |
|
220 for ( i=1; i<=NUMOFTESTS; i++ ) { // FOR EACH TEST |
|
221 if ( testVector[i] ) { |
|
222 // SPECIAL CASES -- HANDLING MULTIPLE FILES FOR A SINGLE TEST |
|
223 if ( ((i == TEST_CUSUM) && testVector[TEST_CUSUM] ) || |
|
224 ((i == TEST_NONPERIODIC) && testVector[TEST_NONPERIODIC] ) || |
|
225 ((i == TEST_RND_EXCURSION) && testVector[TEST_RND_EXCURSION]) || |
|
226 ((i == TEST_RND_EXCURSION_VAR) && testVector[TEST_RND_EXCURSION_VAR]) || |
|
227 ((i == TEST_SERIAL) && testVector[TEST_SERIAL]) ) { |
|
228 |
|
229 if ( (i == TEST_NONPERIODIC) && testVector[TEST_NONPERIODIC] ) |
|
230 numOfFiles = MAXNUMOFTEMPLATES; |
|
231 else if ( (i == TEST_RND_EXCURSION) && testVector[TEST_RND_EXCURSION] ) |
|
232 numOfFiles = 8; |
|
233 else if ( (i == TEST_RND_EXCURSION_VAR) && testVector[TEST_RND_EXCURSION_VAR] ) |
|
234 numOfFiles = 18; |
|
235 else |
|
236 numOfFiles = 2; |
|
237 for ( k=0; k<numOfFiles; k++ ) { |
|
238 if ( k < 10 ) |
|
239 sprintf(s, "%s\\experiments\\%s\\%s\\data%1d", gLogFilePath.PtrZ(), generatorDir[option], testNames[i], k+1); |
|
240 else if ( k < 100 ) |
|
241 sprintf(s, "%s\\experiments\\%s\\%s\\data%2d", gLogFilePath.PtrZ(), generatorDir[option], testNames[i], k+1); |
|
242 else |
|
243 sprintf(s, "%s\\experiments\\%s\\%s\\data%3d", gLogFilePath.PtrZ(), generatorDir[option], testNames[i], k+1); |
|
244 if ( (i == TEST_RND_EXCURSION) || (i == TEST_RND_EXCURSION_VAR) ) |
|
245 randomExcursionSampleSize = computeMetrics(s,i); |
|
246 else |
|
247 generalSampleSize = computeMetrics(s,i); |
|
248 } |
|
249 } |
|
250 else { |
|
251 sprintf(s, "%s\\experiments\\%s\\%s\\results", gLogFilePath.PtrZ(), generatorDir[option], testNames[i]); |
|
252 generalSampleSize = computeMetrics(s,i); |
|
253 } |
|
254 } |
|
255 } |
|
256 |
|
257 fprintf(summary, "\n\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"); |
|
258 case1 = 0; |
|
259 case2 = 0; |
|
260 if ( testVector[TEST_RND_EXCURSION] || testVector[TEST_RND_EXCURSION_VAR] ) |
|
261 case2 = 1; |
|
262 for ( i=1; i<=NUMOFTESTS; i++ ) { |
|
263 if ( testVector[i] && (i != TEST_RND_EXCURSION) && (i != TEST_RND_EXCURSION_VAR) ) { |
|
264 case1 = 1; |
|
265 break; |
|
266 } |
|
267 } |
|
268 if ( case1 ) { |
|
269 if ( generalSampleSize == 0 ) { |
|
270 fprintf(summary, "The minimum pass rate for each statistical test with the exception of the\n"); |
|
271 fprintf(summary, "random excursion (variant) test is undefined.\n\n"); |
|
272 } |
|
273 else { |
|
274 passRate = 0.99-3.0*sqrt(0.01*(1.0-ALPHA)/(double)generalSampleSize); |
|
275 fprintf(summary, "The minimum pass rate for each statistical test with the exception of the\n"); |
|
276 fprintf(summary, "random excursion (variant) test is approximately = %f for a\n", generalSampleSize ? passRate : 0.0); |
|
277 fprintf(summary, "sample size = %d binary sequences.\n\n", generalSampleSize); |
|
278 } |
|
279 } |
|
280 if ( case2 ) { |
|
281 if ( randomExcursionSampleSize == 0 ) |
|
282 fprintf(summary, "The minimum pass rate for the random excursion (variant) test is undefined.\n\n"); |
|
283 else { |
|
284 passRate = 0.99-3.0*sqrt(0.01*(1.0-ALPHA)/(double)randomExcursionSampleSize); |
|
285 fprintf(summary, "The minimum pass rate for the random excursion (variant) test\n"); |
|
286 fprintf(summary, "is approximately %f for a sample size = %d binary sequences.\n\n", passRate, randomExcursionSampleSize); |
|
287 } |
|
288 } |
|
289 fprintf(summary, "For further guidelines construct a probability table using the MAPLE program\n"); |
|
290 fprintf(summary, "provided in the addendum section of the documentation.\n"); |
|
291 fprintf(summary, "- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"); |
|
292 } |
|
293 |
|
294 int |
|
295 computeMetrics(char *s, int test) |
|
296 { |
|
297 int j, pos, count, sampleSize, expCount; |
|
298 int freqPerBin[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; |
|
299 double *A = NULL; |
|
300 double *T = NULL; |
|
301 double chi2, proportion, uniformity; |
|
302 float c; |
|
303 FILE *fp = NULL; |
|
304 |
|
305 if ( (fp = fopen(s, "r")) == NULL ) { |
|
306 printf("%s",s); |
|
307 printf(" -- file not found. Exiting program.\n"); |
|
308 exit(-1); |
|
309 } |
|
310 |
|
311 /* Compute Metric 1: Proportion of Passing Sequences */ |
|
312 |
|
313 count = 0; |
|
314 sampleSize = tp.numOfBitStreams; |
|
315 |
|
316 if ( (test == TEST_RND_EXCURSION) || (test == TEST_RND_EXCURSION_VAR) ) { /* Special Case: Random Excursion Tests */ |
|
317 if ( (T = (double *)calloc(tp.numOfBitStreams, sizeof(double))) == NULL ) { |
|
318 printf("Final Analysis Report aborted due to insufficient workspace\n"); |
|
319 // Perform cleanup before returning |
|
320 fclose(fp); |
|
321 return 0; |
|
322 } |
|
323 for ( j=0; j<sampleSize; j++ ) { |
|
324 fscanf(fp, "%f", &c); |
|
325 if ( c > 0.000000 ) |
|
326 T[count++] = c; |
|
327 } |
|
328 |
|
329 if ( (A = (double *)calloc(count, sizeof(double))) == NULL ) { |
|
330 printf("Final Analysis Report aborted due to insufficient workspace\n"); |
|
331 // Perform cleanup before returning |
|
332 fclose(fp); |
|
333 free(T); |
|
334 return 0; |
|
335 } |
|
336 |
|
337 for ( j=0; j<count; j++ ) |
|
338 A[j] = T[j]; |
|
339 |
|
340 sampleSize = count; |
|
341 count = 0; |
|
342 for ( j=0; j<sampleSize; j++ ) |
|
343 if ( A[j] < ALPHA ) |
|
344 count++; |
|
345 free(T); |
|
346 T = NULL; |
|
347 } |
|
348 else { |
|
349 if ( (A = (double *)calloc(sampleSize, sizeof(double))) == NULL ) { |
|
350 printf("Final Analysis Report aborted due to insufficient workspace\n"); |
|
351 // Perform cleanup before returning |
|
352 fclose(fp); |
|
353 return 0; |
|
354 } |
|
355 for ( j=0; j<sampleSize; j++ ) { |
|
356 fscanf(fp, "%f", &c); |
|
357 if ( c < ALPHA ) |
|
358 count++; |
|
359 A[j] = c; |
|
360 } |
|
361 } |
|
362 if ( sampleSize == 0 ) |
|
363 proportion = 0.0; |
|
364 else |
|
365 proportion = 1.0-(double)count/sampleSize; |
|
366 |
|
367 /* Compute Metric 2: Histogram */ |
|
368 |
|
369 qsort((void *)A, sampleSize, sizeof(double), (CompareFnType)cmp); |
|
370 |
|
371 for ( j=0; j<sampleSize; j++ ) { |
|
372 pos = (int)floor(A[j]*10); |
|
373 if ( pos == 10 ) |
|
374 pos--; |
|
375 freqPerBin[pos]++; |
|
376 } |
|
377 chi2 = 0.0; |
|
378 expCount = sampleSize/10; |
|
379 for ( j=0; j<10; j++ ) |
|
380 chi2 += pow(freqPerBin[j]-expCount, 2)/expCount; |
|
381 uniformity = cephes_igamc(9.0/2.0, chi2/2.0); |
|
382 |
|
383 for ( j=0; j<10; j++ ) /* DISPLAY RESULTS */ |
|
384 fprintf(summary, "%3d ", freqPerBin[j]); |
|
385 |
|
386 if ( expCount == 0 ) |
|
387 fprintf(summary, " ---- "); |
|
388 else if ( uniformity < 0.0001 ) |
|
389 fprintf(summary, " %8.6f * ", uniformity); |
|
390 else |
|
391 fprintf(summary, " %8.6f ", uniformity); |
|
392 |
|
393 if ( sampleSize == 0 ) |
|
394 fprintf(summary, " ---- %s\n", testNames[test]); |
|
395 else if ( proportion < 0.96 ) |
|
396 fprintf(summary, "%6.4f * %s\n", proportion, testNames[test]); |
|
397 else |
|
398 fprintf(summary, "%6.4f %s\n", proportion, testNames[test]); |
|
399 |
|
400 fclose(fp); |
|
401 free(A); |
|
402 |
|
403 return sampleSize; |
|
404 } |
|
405 |
|
406 /* |
|
407 Gobal Entry Function |
|
408 */ |
|
409 GLDEF_C TInt E32Main() |
|
410 { |
|
411 __UHEAP_MARK; |
|
412 TInt ret = StartNISTTest(); |
|
413 __UHEAP_MARKEND; |
|
414 |
|
415 return ret; |
|
416 } |
|
417 |
|
418 |
|
419 |