Archived NIST Technical Series Publication 

The attached publication has been archived (withdrawn), and is provided solely for historical purposes. 

It may have been superseded by another publication (indicated below). 

Archived Publication 

Series/Number: 

Title: 

Publication Date(s): 

Withdrawal Date: 

Withdrawal Note: 

Superseding Publication(s) 

The attached publication has been superseded by the following publication(s): 

Series/Number: 

Title: 

Author(s): 

Publication Date(s): 

URL/DOI: 

Additional Information (if applicable) 

Contact:

Latest revision of the 

attached publication: 

Related information: 

Withdrawal 

announcement (link): 

Date updated: ƵŐƵƐƚϭϮ, 2015 

NIST Special Publication 800-22

A Statistical Test Suite for Random and Pseudorandom Number

Generators for Cryptographic Applications

May 15, 2001

August 2008

SP 800-22 is superseded in its entirety by the publication of

SP 800-22 Revision 1 (August 2008).

NIST Special Publication 800-22 Revision 1

A Statistical Test Suite for Random and Pseudorandom Number

Generators for Cryptographic Applications

August 2008

Computer Security Division (Information Technology Lab)

SP 800-22 Revision 1a (as of August 12, 2015)

http://csrc.nist.gov/groups/ST/

N/A
NATX INST. OF STAND & TECH R I.C,

AlllQS fib5D23

I

N!ST

PUBLICATIONS

NIST Special Publication 800-22

Nisr

National Institute of Standards

and Technology

Technology Administration

U.S. Department of Commerce

A Statistical Test Suite for

Random and Pseudorandom

Number Generators for

Cryptographic Applications

Andrew Rukhin, Juan Soto, James Nechvatal,

Miles Smid, Elaine Barker, Stefan Leigh, Mark

Levenson, Mark Vangel, David Banks, Alan

Heckert, James Dray, San Vo

COMPUTER SECURITY
rhe National Institute of Standards and Technology was established in 1988 by Congress to "assist industry in the development of technology . . . needed to improve product quality, to modernize manufacturing processes,

to ensure product reliability . . . and to facilitate rapid commercialization ... of products based on new scientific discoveries." NIST, originally founded as the National Bureau of Standards in 1901, works to strengthen U.S. industry's

competitiveness; advance science and engineering; and improve public health, safety, and the environment. One

of the agency's basic functions is to develop, maintain, and retain custody of the national standards of

measurement, and provide the means and methods for comparing standards used in science, engineering,

manufacturing, commerce, industry, and education with the standards adopted or recognized by the Federal Government.

As an agency of the U.S. Commerce Department's Technology Administration, NIST conducts basic and

applied research in the physical sciences and engineering, and develops measurement techniques, test methods, standards, and related services. The Institute does generic and precompetitive work on new and

advanced technologies. NIST's research facilities are located at Gaithersburg, MD 20899, and at Boulder, CO 80303.

Major technical operating units and their principal activities are listed below. For more information contact the Publications and Program Inquiries Desk, 301-975-3058.

Office of the Director

• National Quality Program

• International and Academic Affairs

Technology Services

• Standards Services

• Technology Partnerships

• Measurement Services

• Information Services

Advanced Technology Program

• Economic Assessment

• Information Technology and Applications

• Chemistry and Life Sciences

• Materials and Manufacturing Technology

• Electronics and Photonics Technology

Manufacturing Extension Partnership

Program

• Regional Programs

• National Programs

• Program Development

Electronics and Electrical Engineering

Laboratory

• Microelectronics

• Law Enforcement Standards

• Electricity

• Semiconductor Electronics

• Radio-Frequency Technology'

• Electromagnetic Technology'

• Optoelectronics'

Materials Science and Engineering

Laboratory

• Intelligent Processing of Materials

• Ceramics

• Materials Reliability'

• Polymers

• Metallurgy

• NIST Center for Neutron Research

Chemical Science and Technology

Laboratory

• Biotechnology

• Physical and Chemical Properties^

• Analytical Chemistry

• Process Measurements

• Surface and Microanalysis Science

Physics Laboratory

• Electron and Optical Physics

• Atomic Physics

• Optical Technology

• Ionizing Radiation

• Time and Frequency'

• Quantum Physics'

Manufacturing Engineering

Laboratory

• Precision Engineering

• Automated Production Technology

• Intelligent Systems

• Fabrication Technology

• Manufacturing Systems Integration

Building and Fire Research

Laboratory

• Applied Economics

• Structures

• Building Materials

• Building Environment

• Fire Safety Engineering

• Fire Science Information Technology Laboratory

• Mathematical and Computational Sciences^

• Advanced Network Technologies

• Computer Security

• Information Access and User Interfaces

• High Performance Systems and Services

• Distributed Computing and Information Services

• Software Diagnostics and Conformance Testing

• Statistical Engineering

'At Boulder, CO 80303. ^Some elements at Boulder, CO.
NisT Special Publication 800-22 A Statistical Tcst Suitc for

Random and Pseudorandom

Number Generators for

Cryptographic Applications

Andrew Rukhin', Juan Soto^, James Nechvatal^,

Miles Smid^, Elaine Barker^, Stefan Leigh', Mark

Levenson', Mark Vangel', David Banks', Alan

Heckert', James Dray^, San Vo^

COMPUTER SECURITY

'statistical Engineering Division

^Computer Security Division

Information Technology Laboratory

National Institute of Standards and Technology

Gaithersburg, MD 20899-8930

October 2000

U.S. Department of Commerce

Norman Y. Mineta, Secretary

Technology Administration

Dr. Cheryl L. Shavers, Under Secretary of Commerce for Technology

National Institute of Standards and Technology

Raymond G. Kammer, Director
Reports on Computer Systems Technology

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST)

promotes the U.S. economy and public welfare by providing technical leadership for the Nation's measurement

and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept

implementations, and technical analyses to advance the development and productive use of information

technology. ITL's responsibilities include the development of technical, physical, administrative, and

management standards and guidelines for the cost-effective security and privacy of sensitive unclassified

information in Federal computer systems. This Special Publication 800-series reports on ITL's research,

guidance, and outreach efforts in computer security, and its collaborative activities with industry, government,

and academic organizations.

National Institute of Standards and Technology Special Publication 800-22

Natl. Inst. Stand. Technol. Spec. Publ. 800-22, 161 pages (Oct. 2000)

CODEN: NSPUE2

U.S. GOVERNMENT PRINTING OFFICE

WASHINGTON: 2000

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, DC 20402-9325
I j
ABSTRACT

This paper discusses some aspects of selecting and testing random and pseudorandom

number generators. The outputs of such generators may be used in many cryptographic

apphcations, such as the generation of key material. Generators suitable for use in

cryptographic applications may need to meet stronger requirements than for other

applications. In particular, their outputs must be unpredictable in the absence of

knowledge of the inputs. Some criteria for characterizing and selecting appropriate

generators are discussed in this document. The subject of statistical testing and its relation to cryptanalysis is also discussed, and some recommended statistical tests are provided. These tests may be useful as a first step in determining whether or not a

generator is suitable for a particular cryptographic application. However, no set of

statistical tests can absolutely certify a generator as appropriate for usage in a particular

application, i.e., statistical testing cannot serve as a substitute for cryptanalysis. The

design and cryptanalysis of generators is outside the scope of this paper.

Key words: random number generator, hypothesis test, P-value

Certain commercial equipment and materials were used in the development of this test suite. Such identification does not imply recommendation or endorsement by the National

Institute of Standards and Technology, nor does it imply that the materials or equipment

identified are necessarily the best available for the purpose.

iv
TABLE OF CONTENTS

1 INTRODUCTION TO RANDOM NUMBER TESTING 1

1.1 General Discussion 1 1.1.1 Randomness 1 1.1.2 Unpredictability 2

1.1.3 Random Number Generators (RNGs) 2

1.1.4 Pseudorandom Number Generators (PRNGs) 3

1.1.5 Testing 3

1.1.6 Considerations for Randomness, Unpredictability and Testing 6

1.2 Definitions and Abbreviations 6

1.3 Mathematical Symbols 11

2 RANDOM NUMBER GENERATION TESTS 13

2.1 Frequency (Monobit) Test 14

2.1.1 Test Purpose 14

2.1.2 Function Call 14

2.1.3 Test Statistic and Reference Distribution 15

2. 1 .4 Test Description 15

2.1.5 Decision Rule (at the 1 % Level) 15

2.1.6 Conclusion and Interpretation of Test Results 15

2.1.7 Input Size Recommendations 16

2.1.8 Example 16

2.2 Frequency Test within a Block 16

2.2.1 Test Purpose 16

2.2.2 Function Call 16

2.2.3 Test Statistic 17

2.2.4 Test Description 17

2.2.5 Decision Rule (at the 1 % Level) 18

2.2.6 Conclusion and Interpretation of Test Results 18

2.2.7 Input Size Recommendations 18

2.2.8 Example 18

2.3 Runs Test 18

2.3.1 Test Purpose 18

2.3.2 Function Call 19

2.3.3 Test Statistic and Reference Distribution 19

2.3.4 Test Description 19

2.3.5 Decision Rule (at the 1 % Level) 20

2.3.6 Conclusion and Interpretation of Test Results 20

2.3.7 Input Size Recommendations 20

2.3.8 Example 21

2.4 Test for the Longest Run of Ones in a Block 21

2.4.1 Test Purpose 21

2.4.2 Function Call 21

2.4.3 Test Statistic and Reference Distribution 22

V
2.4.4 Test Description 22

2.4.5 Decision Rule (at the 1 % Level) 23

2.4.6 Conclusion and Interpretation of Test Results 23

2.4.7 Input Size Recommendations 23

2.4.8 Example 23

2.5 Binary Matrix Rank Test 24

2.5.1 Test Purpose 24

2.5.2 Function Call 24

2.5.3 Test Statistic and Reference Distribution 25

2.5.4 Test Description 25

2.5.5 Decision Rule (at the 1 % Level) 26

2.5.6 Conclusion and Interpretation of Test Results 26

2.5.7 Input Size Recommendations 26

2.5.8 Example 26

2.6 Discrete Fourier Transform (Spectral) Test 27

2.6.1 Test Purpose 27

2.6.2 Function Call 27

2.6.3 Test Statistic and Reference Distribution 27

2.6.4 Test Description 27

2.6.5 Decision Rule (at the 1 % Level) 28

2.6.6 Conclusion and Interpretation of Test Results 28

2.6.7 Input Size Recommendations 29

2.6.8 Example 29

2.7 Non-overlapping Template Matching Test 29

2.7.1 Test Purpose 29

2.7.2 Function Call 29

2.7.3 Test Statistic and Reference Distribution 30

2.7.4 Test Description 30

2.7.5 Decision Rule (at the 1 % Level) 31

2.7.6 Conclusion and Interpretation of Test Results 31

2.7.7 Input Size Recommendations 32

2.7.8 Example 32

2.8 Overlapping Template Matching Test 32

2.8.1 Test Purpose 32

2.8.2 Function Call 33

2.8.3 Test Statistic and Reference Distribution 33

2.8.4 Test Description 33

2.8.5 Decision Rule (at the 1 % Level) 35

2.8.6 Conclusion and Interpretation of Test Results 35

2.8.7 Input Size Recommendations 35

2.8.8 Example 36

2.9 Maurer's "Universal Statistical" Test 36

2.9.1 Test Purpose 36

2.9.2 Function Call 36

2.9.3 Test Statistic and Reference Distribution 36

2.9.4 Test Description 37

2.9.5 Decision Rule (at the 1 % Level) 39

2.9.6 Conclusion and Interpretation of Test Results 40

2.9.7 Input Size Recommendations 40

2.9.8 Example 40

vi
2.10 Lempel-Ziv Compression Test 41

2.10.1 Test Purpose 41

2.10.2 Function Call 41

2. 1 0.3 Test Statistic and Reference Distribution 41

2.10.4 Test Description 41

2. 1 0.5 Decision Rule (at the 1 % Level) 42

2.10.6 Conclusion and Interpretation of Test Results 42

2.10.7 Input Size Recommendations 43

2.10.8 Example 43

2.11 Linear Complexity Test 43

2.11.1 Test Purpose 43

2.11.2 Function Call 43

2.11.3 Test Statistic and Reference Distribution 44

2 . 1 1 .4 Test Description 44

2.1 1.5 Decision Rule (at the 1 % Level) 45

2. 1 1 .6 Conclusion and Interpretation of Test Results 45

2. 1 1 .7 Input Size recommendations 46

2.11.8 Example 46

2.12 Serial Test 46

2.12.1 Test Purpose 46

2.12.2 Function Call 46

2. 12.3 Test Statistics and Reference Distribution 47

2 . 1 2 .4 Test Description 47

2. 12.5 Decision Rule (at the 1 % Level) 48

2.12.6 Conclusion and Interpretation of Test Results 48

2. 12.7 Input Size Recommendations 48

2.12.8 Example 48

2.13 Approximate Entropy Test 49

2.13.1 Test Purpose 49

2.13.2 Function Call 49

2. 13.3 Test Statistic and Reference Distribution 49

2.13.4 Test Description 50

2.13.5 Decision Rule (at the 1 % Level) 51

2.13.6 Conclusion and Interpretation of Test Results 51

2. 13.7 Input Size Recommendations 51

2.13.8 Example 51

2.14 Cumulative Sums (Cusum) Test 52

2.14.1 Test Purpose 52

2.14.2 Function Call 52

2. 14.3 Test Statistic and Reference Distribution 52

2.14.4 Test Description 52

2.14.5 Decision Rule (at the 1 % Level) 54

2. 14.6 Conclusion and Interpretation of Test Results 54

2. 14.7 Input Size Recommendations 54

2.14.8 Example 54

2.15 Random Excursions Test 55

2.15.1 Test Purpose 55

2.15.2 Function Call 55

2. 1 5.3 Test Statistic and Reference Distribution 55

2.15.4 Test Description 55

2. 15.5 Decision Rule (at the 1 % Level) 59

vii
2.15.6 Conclusion and Interpretation of Test Results 59

2.15.7 Input Size Recommendations 59

2.15.8 Example 59

2.16 Random Excursions Variant Test 60

2.16.1 Test Purpose 60

2.16.2 Function Call 60

2. 1 6.3 Test Statistic and Reference Distribution 60

2.16.4 Test Description 60

2. 16.5 Decision Rule (at the 1 % Level) 62

2.16.6 Conclusion and Interpretation of Test Results 62

2. 16.7 Input Size Recommendations 62

2.16.8 Example 62

3 TECHNICAL DESCRIPTION OF TESTS 64

3.1 Frequency (Monobit) Test 64

3.2 Frequency Test within a Block 65

3.3 Runs Test 66

3.4 Test for the Longest Run of Ones in a Block 67

3.5 Binary Matrix Rank Test 69

3.6 Discrete Fourier Transform (Spectral) Test 71

3.7 Non-overlapping Template Matching Test 74

3.8 Overlapping Template Matching Test 77

3.9 Maurer's "Universal Statistical" Test 78

3.10 Lempel-Ziv Compression Test 81

3.11 Linear Complexity Test 84

3.12 Serial Test 87

3.13 Approximate Entropy Test 89

3.14 Cumulative Sums (Cusum) Test 91

3.15 Random Excursions Test 93

3.16 Random Excursions Variant Test 96

4. TESTING STRATEGY AND RESULT INTERPRETATION 98

4.1 Strategies for the Statistical Analysis of an RNG * 98

4.2 The Interpretation of Empirical Results 100

viii
4.2. 1 Proportion of Sequences Passing a Test 1 00

4.2.2 Uniform Distribution of P-values 101

4.3 General Recommendations and Guidelines 101

4.4 Application of Multiple Tests 104

5. USER'S GUIDE 106

5.1 About the Package 106

5.2 System Requirements 107

5.3 How to Get Started 107

5.4 Data Input and Output of Empirical Results 109

5.4.1 Data Input 109

5.4.2 Output of Empirical Results 109

5.4.3 Test Data Files 109

5.5 Program Layout 109

5.5.1 General Program 110

5.5.2 Implementation Details 110

5.5.3 Description of the Test Code Ill

5.6 Running the Test Code 1 13

5.7 Interpretation of Results 115

APPENDIX A: RANK COMPUTATION FOR BINARY MATRICES 117

APPENDIX B: SOURCE CODE 121

APPENDIX C: EMPIRICAL RESULTS FOR SAMPLE DATA 124

APPENDIX D: CONSTRUCTION OF APERIODIC TEMPLATES 127

APPENDIX E: GENERATION OF THE BINARY EXPANSION OF IRRATIONAL

NUMBERS 129

APPENDIX F: NUMERIC ALGORITHM ISSUES 130

APPENDIX G: HIERARCHICAL DIRECTORY STRUCTURE 132

APPENDIX H: VISUALIZATION APPROACHES 136

ix
APPENDIX I: INSTRUCTIONS FOR INCORPORATING ADDITIONAL

STATISTICAL TESTS 139

APPENDIX J: INSTRUCTIONS FOR INCORPORATING ADDITIONAL PRNGS

141

APPENDIX K: GRAPHICAL USER INTERFACE (GUI) 143

APPENDIX L: DESCRIPTION OF THE REFERENCE PSEUDO RANDOM

NUMBER GENERATORS 146

APPENDIX M: REFERENCES 151
1 INTRODUCTION TO RANDOM NUMBER TESTING

The need for random and pseudorandom numbers arises in many cryptographic appHcations. For

example, common cryptosystems employ keys that must be generated in a random fashion.

Many cryptographic protocols also require random or pseudorandom inputs at various points,

e.g., for auxiliary quantities used in generating digital signatures, or for generating challenges in

authentication protocols.

This document discusses the randomness testing of random number and pseudorandom number

generators that may be used for many purposes including cryptographic, modeling and

simulation applications. The focus of this document is on those applications where randomness is required for cryptographic purposes. A set of statistical tests for randomness is described in this

document. The National Institute of Standards and Technology (NIST) believes that these

procedures are useful in detecting deviations of a binary sequence from randomness. However, a

tester should note that apparent deviations from randomness may be due to either a poorly

designed generator or to anomalies that appear in the binary sequence that is tested (i.e., a

certain number of failures is expected in random sequences produced by a particular generator).

It is up to the tester to determine the correct interpretation of the test results. Refer to Section 4

for a discussion of testing strategy and the interpretation of test results.

1.1 General Discussion

There are two basic types of generators used to produce random sequences: random number

generators (RNGs - see Section 1.1.3) and pseudorandom number generators (PRNGs - see Section 1 . 1 .4). For cryptographic applications, both of these generator types produce a stream of

zeros and ones that may be divided into substreams or blocks of random numbers.

1.1.1 Randomness

A random bit sequence could be interpreted as the result of the flips of an unbiased "fair" coin

with sides that are labeled "0" and "1," with each flip having a probability of exactly Vi of

producing a "0" or "1 ." Furthermore, the flips are independent of each other: the result of any

previous coin flip does not affect friture coin flips. The unbiased "fair" coin is thus the perfect

random bit stream generator, since the "0" and "1" values will be randomly distributed (and

[0,1] uniformly distributed). All elements of the sequence are generated independently of each

other, and the value of the next element in the sequence cannot be predicted, regardless of how

many elements have already been produced.

Obviously, the use of unbiased coins for cryptographic purposes is impractical. Nonetheless,

the hypothetical output of such an idealized generator of a true random sequence serves as a benchmark for the evaluation of random and pseudorandom number generators.

1
1.1.2 Unpredictability

Random and pseudorandom numbers generated for cryptographic applications should be

unpredictable. In the case of PRNGs, if the seed is unknown, the next output number in the

sequence should be unpredictable in spite of any knowledge of previous random numbers in the

sequence. This property is known as forward unpredictability. It should also not be feasible to determine the seed from knowledge of any generated values (i.e., backward unpredictability is also required). No correlation between a seed and any value generated from that seed should be

evident; each element of the sequence should appear to be the outcome of an independent

random event whose probability is 1/2.

To ensure forward unpredictability, care must be exercised in obtaining seeds. The values

produced by a PRNG are completely predictable if the seed and generation algorithm are known.

Since in many cases the generation algorithm is publicly available, the seed must be kept secret and should not be derivable from the pseudorandom sequence that it produces. In addition, the

seed itself must be unpredictable.

1 .1 .3 Random Number Generators (RNGs)

The first type of sequence generator is a random number generator (RNG). An RNG uses a nondeterministic source (i.e., the entropy source), along with some processing function (i.e., the

entropy distillation process) to produce randomness. The use of a distillation process is needed to overcome any weakness in the entropy source that results in the production of non-random

numbers (e.g., the occurrence of long strings of zeros or ones). The entropy source typically

consists of some physical quantity, such as the noise in an electrical circuit, the timing of user processes (e.g., key strokes or mouse movements), or the quantum effects in a semiconductor.

Various combinations of these inputs may be used.

The outputs of an RNG may be used directly as a random number or may be fed into a pseudorandom number generator (PRNG). To be used directly (i.e., without further processing),

the output of any RNG needs to satisfy strict randomness criteria as measured by statistical tests in order to determine that the physical sources of the RNG inputs appear random. For example,

a physical source such as electronic noise may contain a superposition of regular structures, such

as waves or other periodic phenomena, which may appear to be random, yet are determined to be

non-random using statistical tests.

For cryptographic purposes, the output of RNGs needs to be unpredictable. However, some

physical sources (e.g., date/time vectors) are quite predictable. These problems may be

mitigated by combining outputs from different types of sources to use as the inputs for an RNG.

However, the resulting outputs from the RNG may still be deficient when evaluated by statistical

tests. In addition, the production of high-quality random numbers may be too time consuming,

making such production undesirable when a large quantity of random numbers is needed. To

produce large quantities of random numbers, pseudorandom number generators may be

preferable.

2
1 .1 .4 Pseudorandom Number Generators (PRNGs)

The second generator type is a pseudorandom number generator (PRNG). A PRNG uses one or more inputs and generates multiple "pseudorandom" numbers. Inputs to PRNGs are called

seeds. In contexts in which unpredictability is needed, the seed itself must be random and

unpredictable. Hence, by default, a PRNG should obtain its seeds from the outputs of an RNG;

i.e., a PRNG requires a RNG as a companion.

The outputs of a PRNG are typically deterministic functions of the seed; i.e., all true randomness

is confined to seed generation. The deterministic nature of the process leads to the term

"pseudorandom." Since each element of a pseudorandom sequence is reproducible from its seed,

only the seed needs to be saved if reproduction or validation of the pseudorandom sequence is required.

Ironically, pseudorandom numbers often appear to be more random than random numbers

obtained from physical sources. If a pseudorandom sequence is properly constructed, each value

in the sequence is produced from the previous value via transformations which appear to introduce additional randomness. A series of such transformations can eliminate statistical autocorrelations between input and output. Thus, the outputs of a PRNG may have better statistical

properties and be produced faster than an RNG.

1.1.5 Testing

Various statistical tests can be applied to a sequence to attempt to compare and evaluate the

sequence to a truly random sequence. Randomness is a probabilistic property; that is, the

properties of a random sequence can be characterized and described in terms of probability. The

likely outcome of statistical tests, when applied to a truly random sequence, is known a priori

and can be described in probabilistic terms. There are an infinite number of possible stadstical

tests, each assessing the presence or absence of a "pattern" which, if detected, would indicate

that the sequence is nonrandom. Because there are so many tests forjudging whether a sequence

is random or not, no specific finite set of tests is deemed "complete." In addition, the results of

statistical testing must be interpreted with some care and caution to avoid incorrect conclusions

about a specific generator (see Section 4).

A statistical test is formulated to test a specific null hypothesis (Ho). For the purpose of this

document, the null hypothesis under test is that the sequence being tested is random. Associated

with this null hypothesis is the alternative hypothesis (Ha) which, for this document, is that the

sequence is not random. For each applied test, a decision or conclusion is derived that accepts or

rejects the null hypothesis, i.e., whether the generator is (or is not) producing random values,

based on the sequence that was produced.

For each test, a relevant randomness statistic must be chosen and used to determine the

acceptance or rejection of the null hypothesis. Under an assumption of randomness, such a

stafisdc has a distribufion of possible values. A theoretical reference distribufion of this statistic

3
under the null hypothesis is determined by mathematical methods. From this reference

distribution, a critical value is determined (typically, this value is "far out" in the tails of the

distribution, say out at the 99 % point). During a test, a test statistic value is computed on the

data (the sequence being tested). This test statistic value is compared to the critical value. If the

test statistic value exceeds the critical value, the null hypothesis for randomness is rejected.

Otherwise, the null hypothesis (the randomness hypothesis) is not rejected (i.e., the hypothesis is accepted).

In practice, the reason that statistical hypothesis testing works is that the reference distribution

and the critical value are dependent on and generated under a tentative assumption of

randomness. If the randomness assumption is, in fact, true for the data at hand, then the resulting

calculated test statistic value on the data will have a very low probability (e.g., 0.01 %) of

exceeding the critical value.

On the other hand, if the calculated test statistic value does exceed the critical value (i.e., if the

low probability event does in fact occur), then from a statistical hypothesis testing point of view,

the low probability event should not occur naturally. Therefore, when the calculated test statistic value exceeds the critical value, the conclusion is made that the original assumption of

randomness is suspect or faulty. In this case, statistical hypothesis testing yields the following

conclusions: reject Ho (randomness) and accept Ha (non-randomness).

Statistical hypothesis testing is a conclusion-generation procedure that has two possible

outcomes, either accept Hq (the data is random) or accept Ha (the data is non-random). The

following 2 by 2 table relates the true (unknown) status of the data at hand to the conclusion

arrived at using the testing procedure.

TRUE SITUATION

CONCLUSION

Accept Ho Accept Ha (reject Ho)

Data is random (Ho is true) No error Type I error Data is not random (Ha is true) Type II error No error

If the data is, in truth, random, then a conclusion to reject the null hypothesis (i.e., conclude that

the data is non-random) will occur a small percentage of the time. This conclusion is called a Type I error. If the data is, in truth, non-random, then a conclusion to accept the null hypothesis

(i.e., conclude that the data is actually random) is called a Type II error. The conclusions to accept Ho when the data is really random, and to reject Ho when the data is non-random, are

correct.

The probability of a Type I error is often called the level ofsignificance of the test. This

probability can be set prior to a test and is denoted as a. For the test, a is the probability that the

test will indicate that the sequence is not random when it really is random. That is, a sequence

appears to have non-random properties even when a "good" generator produced the sequence.

Common values of a in cryptography are about 0.01

.

The probability of a Type II error is denoted as p. For the test, p is the probability that the test will indicate that the sequence is random when it is not; that is, a "bad" generator produced a

4
sequence that appears to have random properties. UnHke a, (3 is not a fixed value. (3 can take on many different values because there are an infinite number of ways that a data stream can be

non-random, and each different way yields a different (3. The calculation of the Type II error p is more difficult than the calculation of a because of the many possible types of non-randomness.

One of the primary goals of the following tests is to minimize the probability of a Type II error,

i.e., to minimize the probability of accepting a sequence being produced by a good generator

when the generator was actually bad. The probabilities a and P

are related to each other and to the size n of the tested sequence in such a way that if two of them are specified, the third value is automafically determined. Practitioners usually select a sample size n and a value for a (the

probability of a Type I error - the level of significance). Then a critical point for a given statistic

is selected that will produce the smallest P (the probability of a Type II error). That is, a suitable

sample size is selected along with an acceptable probability of deciding that a bad generator has

produced the sequence when it really is random. Then the cutoff point for acceptability is chosen such that the probability of falsely accepting a sequence as random has the smallest

possible value.

Each test is based on a calculated test statistic value, which is a fiinction of the data. If the test

statistic value is S and the cridcal value is ?, then the Type I error probability is P(S > t\\Ho is true) = P(reject Ho \ Ho is true), and the Type II error probability is P{S <t\\Ho is false) =

/•(accept Ho \ Ho is false). The test statistic is used to calculate a P-value that summarizes the

strength of the evidence against the null hypothesis. For these tests, each P-value is the

probability that a perfect random number generator would have produced a sequence less

random than the sequence that was tested, given the kind of non-randomness assessed by the test. If a P-value for a test is determined to be equal to 1 , then the sequence appears to have perfect

randomness. A P-value of zero indicates that the sequence appears to be completely non- random. A significance level (a) can be chosen for the tests. If P-value > a, then the null

hypothesis is accepted; i.e., the sequence appears to be random. If P-value < a, then the null

hypothesis is rejected; i.e., the sequence appears to be non-random. The parameter a denotes the

probability of the Type I error. Typically, a is chosen in the range [0.001, 0.01].

• An a of 0.001 indicates that one would expect one sequence in 1000 sequences to be rejected

by the test if the sequence was random. For a P-value > 0. 001, a sequence would be

considered to be random with a confidence of 99.9 %. For a P-value < 0.001, a sequence

would be considered to be non-random with a confidence of 99.9 %.

• An a of 0.01 indicates that one would expect 1 sequence in 100 sequences to be rejected. A

P-value > 0.01 would mean that the sequence would be considered to be random with a confidence of 99 %. A P-value < 0.01 would mean that the conclusion was that the sequence

is non-random with a confidence of 99 %.

For the examples in this document, a has been chosen to be 0.01. Note that, in many cases, the

parameters in the examples do not conform to the recommended values; the exainples are for

illustrative purposes only.

5
1 .1 .6 Considerations for Randomness, Unpredictability and Testing

The following assumptions are made with respect to random binary sequences to be tested:

1 . Uniformity: At any point in the generation of a sequence of random or pseudorandom

bits, the occurrence of a zero or one is equally likely, i.e., the probability of each is exactly 1/2. The expected number of zeros (or ones) is n/2, where n = the sequence

length.

2. Scalability: Any test applicable to a sequence can also be applied to subsequences

extracted at random. If a sequence is random, then any such extracted subsequence

should also be random. Hence, any extracted subsequence should pass any test for

randomness.

3. Consistency: The behavior of a generator must be consistent across starting values

(seeds). It is inadequate to test a PRNG based on the output from a single seed, or an RNG on the basis of an output produced from a single physical output.

1.2 Definitions and Abbreviations

Term Definition

Asymptotic Analysis A statistical technique that derives limiting approximations

for functions of interest.

Asymptotic Distribution The limiting distribution of a test statistic arising when n approaches infinity.

Bernoulli Random

Variable

A random variable that takes on the value of one with

probability p and the value of zero with probability l-p.

Binary Sequence A sequence of zeroes and ones.

Binomial Distribution A random variable is binomially distributed if there is an

integer n and a probability p such that the random variable is the number of successes in n Bernoulli experiments, where the

probability of success in a single experiment is p. In a Bernoulli experiment, there are only two possible outcomes.

Bit String A sequence of bits.

Block A subset of a bit string. A block has a predetermined length.

Central Limit Theorem For a random sample of size n from a population with mean }i

and variance or', the distribution of the sample means is

6
approximately normal with mean |j, and variance o^/n as the

sample size increases.

Complementary Error

Function

See Erfc.

Confluent

Hypergeometric

Function

The confluent hypergeometric function is defined as

r(fl)r(c»-fl) •'o

Critical Value The value that is exceeded by the test statistic with a small

probability (significance level). A "look-up" or calculated

value of a test stafisdc (i.e., a test statistic value) that, by

construction, has a small probability of occurring (e.g., 5 %)

when the null hypothesis of randomness is true.

Cumulative Distribution

Function (CDF) F(x)

A function giving the probability that the random variable Xis less than or equal to x, for every value x. That is, F{x) = P(X<x).

Entropy A measure of the disorder or randomness in a closed system.

The entropy of uncertainty of a random variable Xwith

n probabilities p,, ...,p„ is defined to be H(X) = -Y.Pi log

i=l

Entropy Source A physical source of information whose output either appears

to be random in itself or by applying some filtering/disfillation

process. This output is used as input to either a RNG or PRNG.

Erfc The complementary error function erfc{z) is defined in

Secfion 5.5.3. This function is related to the normal cdf

igamc The incomplete gamma function Q{a^) is defined in Section

5.5.3.

Geometric Random

Variable

A random variable that takes the value k, a non-negafive

integer with probability p^(l-p). The random variable x is the

number of successes before a failure in an indefinite series of

Bemoulh trials.

Global Structure/Global

Value

A structure/value that is available by all routines in the test code.

GUI Graphical User Interface.
Incomplete Gamma

Function

See the definition for igamc.

Hypothesis (Alternative) A statement Ha that an analyst will consider as true (e.g., Ha'. the sequence is non-random) if and when the null hypothesis

is determined to be false.

Hypothesis (Null) A statement Ho about the assumed default condition/property

of the observed sequence. For the purposes of this document,

the null hypothesis Ho is that the sequence is random. If Ho is in fact true, then the reference distribution and critical values

of the test statistic may be derived.

KolmogoroV- Smimov

Test

A statistical test that may be used to determine if a set of data

comes from a particular probability distribution.

Level of Significance

(a)

The probability of falsely rejecting the null hypothesis, i.e., the probability of concluding that the null hypothesis is false

when the hypothesis is, in fact, true. The tester usually

chooses this value; typical values are 0.05, 0.01 or 0.001;

occasionally, smaller values such as 0.0001 are used. The

level of significance is the probability of concluding that a sequence is non-random when it is in fact random. Synonyms:

Type I error, a error.

Linear Dependence In the context of the binary rank matrix test, linear

dependence refers to m-bit vectors that may be expressed as a

linear combination of the linearly independent m-bit vectors.

Maple An interactive computer algebra system that provides a complete mathematical environment for the manipulation and

simplification of symbolic algebraic expressions, arbitrary

extended precision mathematics, two- and three-dimensional

graphics, and programming.

MATLAB An integrated, technical computer environment that combines

numeric computation, advanced graphics and visualization,

and a high level programming language. MATLAB includes

functions for data analysis and visualization; numeric and

symbolic computation; engineering and scientific graphics;

modeling, simulation and prototyping; and programming,

application development and a GUI design.

Normal (Gaussian)

Distribution

A continuous distribution whose density function is given by

8
1 --[—

/(x; |Li;a ) = , e

^ ^

, where p. and a are location and

V27i;a^

scale parameters.

P-value The probability (under the null hypothesis of randomness)

that the chosen test statistic will assume values that are equal

to or worse than the observed test statistic value when

considering the null hypothesis. The P-value is frequently

called the "tail probability."

Poisson Distribution - §3.8Poisson distributions model (some) discrete random variables.

Typically, a Poisson random variable is a count of the number

of rare events that occur in a certain time interval.

Probability Density

Function (PDF)

A function that provides the "local" probability distribution of

a test statistic. From a finite sample size «, a probability

density function will be approximated by a histogram.

Probability Distribution The assignment of a probability to the possible outcomes

(realizations) of a random variable.

Pseudorandom Number

Generator (PRNG)

A deterministic algorithm which, given a truly random binary

sequence of length k, outputs a binary sequence of length /

k which appears to be random. The input to the generator is called the seed, while the output is called a pseudorandom bit

sequence.

Random Number

Generator (RNG)

A mechanism that purports to generate truly random data.

Random Binary

Sequence

A sequence of bits for which the probability of each bit being

a "0" or "1" is ^2. The value of each bit is independent of any

other bit in the sequence, i.e., each bit is unpredictable.

Random Variable Random variables differ from the usual deterministic

variables (of science and engineering) in that random

variables allow the systematic distributional assignment of

probability values to each possible outcome.

Rank (of a matrix) Refers to the rank of a matrix in linear algebra over GF(2).

Having reduced a matrix into row-echelon form via

elementary row operations, the number of nonzero rows, if

any, are counted in order to determine the number of linearly

independent rows or colunms in the matrix.

9
Run An uninterrupted sequence of like bits (i.e., either all zeroes or

all ones).

Seed The input to a pseudorandom number generator. Different

seeds generate different pseudorandom sequences.

SHA-1 The Secure Hash Algorithm defined in Federal Information

Processing Standard 180-1.

Standard Normal

Cumulative Distribution

Function

See the definition in Section 5.5.3. This is the normal function

for mean = 0 and variance = 1

.

Statistically Independent

(Events)

Two events are independent if the occurrence of one event

does not affect the chances of the occurrence of the other

event. The mathematical lormulation oi the independence oi

events A and B is the probability of the occurrence of both A

and B being equal to the product of the probabilities of A and

B (i.e., P(A andB) = P(A)P(B)).

Statistical Test (of a Hypothesis)

A function of the data (binary stream) which is computed and

used to decide whether or not to reject the null hypothesis. A

systematic statistical rule whose purpose is to generate a conclusion regarding whether the experimenter should accept

• jil 111 i1 'TT

or reject the null hypothesis Hq.

Word A predefined substnng consisting of a fixed pattern/template

(e.g., 010, 01 10).

Abbreviation Definition

ANSI American National Standards Institute

FIPS Federal Informadon Processing Standard

NIST National Institute of Standards and Technology

RNG Random Number Generator

SHA-1 Secure Hash Algorithm

10
1.3 Mathematical Symbols

In general, the following notation is used throughout this document. However, the tests in this

document have been designed and described by multiple authors who may have used slightly

different notation. The reader is advised to consider the notation used for each test separate from

that notation used in other tests.

Symbol Meaning

UJ The floor function of x; for a given real positive jc, LjcJ = x-g, where \_x\

is a non-negative integer, and 0<g< 1

a The significance level.

d The normalized difference between the observed and expected number of

frequency components. See Sections 2.6 and 3.6.

V\\r'jobs); A measure of how well the observed values match the expected value. See

Sections 2.12 and 3.12.

E[] The expected value of a random variable.

8 The original input string of zero and one bits to be tested.

£/ The i"^ bit in the original sequence e.

Ho The null hypothesis; i.e., the statement that the sequence is random.

log(x) The natural logarithm of x: log(x) = loge(x) = ln(x).

log2(x)

Defined as ^^^^^

, where In is the natural logarithm.

ln(2)'

M The number of bits in a substring (block) being tested.

N The number of A/-bit blocks to be tested.

n The number of bits in the stream being tested.

fn The sum of the log2 distances between matching I-bit templates, i.e., the sum of

the number of digits in the distance between Z-bit templates. See Sections 2.9

and 3.9. n 3.14159... unless defined otherwise for a specific test.

The average number of ones in a string of n bits.

11
a The standard deviation of a random variable = ^i{x-\if f(x)dx .

The variance of a random variable = (standard deviation) .

^obs The observed value which is used as a statistic in the Frequency test.

s„

. . The n partial sum for values Xi = {- 1

, + 1 } ; i.e., the sum of the first n values of

X,

I The summation symbol.

Standard Normal Cumulative Distribution Function (see Section 5.5.3).

^ The total number of times that a given state occurs in the identified cycles. See

Section 2.16 and 3.16.

The elements of the string consisting of ±1 that is to be tested for randomness,

where Xi = 28,- 1

.

The [theoretical] chi-square distribution; used as a test statistic; also, a test

statistic that follows the distribution.

X (obs) The chi-square statistic computed on the observed values. See Sections 2.2,

2.4, 2.5, 2.7, 2.8, 2.1 1, 2.13, 2.15, and the corresponding sections of Section 3.

Vn The expected number of runs that would occur in a sequence of length n under

an assumption of randomness See Sections 2.3 and 3.3. Vn(0bs) The observed number of runs in a sequence of length n. See Sections 2.3 and

3.3. W The expected number of words in a bitstring being tested. ^

Wobs The number of disjoint words in a sequence. See Sections 2.10 and 3.10.

12
2 RANDOM NUMBER GENERATION TESTS

The NIST Test Suite is a statistical package consisting of 1 6 tests that were developed to test the

randomness of (arbitrarily long) binary sequences produced by either hardware or software

based cryptographic random or pseudorandom number generators. These tests focus on a

variety of different types of non-randomness that could exist in a sequence. Some tests are decomposable into a variety of subtests. The 1 6 tests are:

1 . The Frequency (Monobit) Test,

2. Frequency Test within a Block,

3. The Runs Test,

4. Test for the Longest-Run-of-Ones in a Block,

5. The Binary Matrix Rank Test,

6. The Discrete Fourier Transform (Spectral) Test,

7. The Non-overlapping Template Matching Test,

8. The Overlapping Template Matching Test,

9. Maurer's "Universal Statistical" Test,

10. The Lempel-Ziv Compression Test,

1 1 . The Linear Complexity Test,

12. The Serial Test,

13. The Approximate Entropy Test,

14.The Cumulative Sums (Cusums) Test,

15. The Random Excursions Test, and

16. The Random Excursions Variant Test.

This section (Section 2) consists of 16 subsections, one subsection for each test. Each

subsection provides a high level description of the particular test. The corresponding

subsections in Section 3 provide the technical details for each test.

Section 4 provides a discussion of testing strategy and the interpretation of test results. The

order of the application of the tests in the test suite is arbitrary. However, it is recommended

that the Frequency test be run first, since this supplies the most basic evidence for the existence

of non-randomness in a sequence, specifically, non-uniformity. If this test fails, the likelihood

of other tests failing is high. (Note: The most time-consuming statistical test is the Linear

Complexity test; see Sections 2.1 1 and 3.1 1).

Section 5 provides a user's guide for setting up and running the tests, and a discussion on program layout. The statistical package includes source code and sample data sets. The test code

was developed in ANSI C. Some inputs are assumed to be global values rather than calling

parameters.

A number of tests in the test suite have the standard normal and the chi-square (X^

)

reference distributions. If the sequence under test is in fact non-random, the calculated test

statistic will fall in extreme regions of the reference distribution. The standard normal

13
distribution (i.e., the bell-shaped curve) is used to compare the value of the test statistic obtained

from the RNG with the expected value of the statistic under the assumption of randomness. The

test statistic for the standard normal distribution is of the form z = (x - [ij/c, where x is the

sample test statistic value, and |J. and are the expected value and the variance of the test

statistic. The distribution (i.e., a left skewed curve) is used to compare the goodness-of-fit of

the observed frequencies of a sample measure to the corresponding expected frequencies of the

hypothesized distribution. The test statistic is of the form - ~^i)V^i)' where and

Bi are the observed and expected frequencies of occurrence of the measure, respectively.

For many of the tests in this test suite, the assumption has been made that the size of the

sequence length, n, is large (of the order 10^ to 10''). For such large sample sizes of «, asymptotic reference distributions have been derived and applied to carry out the tests. Most of

the tests are applicable for smaller values of n. However, if used for smaller values of n, the

asymptotic reference distributions would be inappropriate and would need to be replaced by

exact distributions that would commonly be difficult to compute.

Note: For many of the examples throughout Section 2, small sample sizes are used for

illustrative purposes only, e.g., « = 10. The normal approximation is not really applicable for

these examples.

2.1 Frequency (Monobit) Test

2.1.1 Test Purpose

The focus of the test is the proportion of zeroes and ones for the entire sequence. The purpose

of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence. The test assesses

the closeness of the fraction of ones to Vi, that is, the number of ones and zeroes in a sequence

should be about the same. All subsequent tests depend on the passing of this test; there is no

evidence to indicate that the tested sequence is non-random.

2.1.2 Function Call

Frequency(A2), where:

n The length of the bit string.

Additional input used by the fiinction, but supplied by the testing code:

£ The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; 8 = 8/, 82, ... , 8;,.

14
2.1 .3 Test Statistic and Reference Distribution

Sobs: The absolute value of the sum of the Xj (where, ^= 2£ - 1 = ±1) in the sequence divided

by the square root of the length of the sequence.

The reference distribution for the test statistic is half normal (for large «). (Note: If z (where

z = s^i^Jyfl ; see Section 3.1) is distributed as normal, then |z| is distributed as half normal.) If

the sequence is random, then the plus and minus ones will tend to cancel one another out so that

the test statistic will be about 0. If there are too many ones or too many zeroes, then the test

statistic will tend to be larger than zero.

2.1 .4 Test Description

(1) Conversion to ±1 : The zeros and ones of the input sequence (e) are converted to values

of -1 and +1 and are added together to produce S„ = X, + X2 +• • •+Xn , where Xi = 28/ -

1.

For example, if e = 1011010101, then «=10 and S„ = 1 + (-1) + 1 + 1 + (-1) + 1 + (-1) + 1 + (-1) + 1 = 2.

(2) Compute the test statistic Sobs 4n

\2\ For the example in this section, Sobs -1== 632455532.

yfjO

(3) Compute P-value = erfc

defined in Section 5.5.3.3

f \ ^obs

, where erfc is the complementary error function as

For the example in this section, P-value = erfc

.632455532 = 0.527089.

2.1 .5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.1 .6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 3 of Section 2.1.4 is > 0.01 (i.e., P-value = 0.527089), the

conclusion is that the sequence is random.

15
Note that if the P-value were small (< 0.01), then this would be caused by l^-^l or being

large. Large positive values of Sn are indicative of too many ones, and large negative values of

Sn are indicative of too many zeros.

2.1 .7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n >

100).

2.1.8 Example

(input) £= 11001001000011111101101010100010001000010110100011

000010001 101001 10001001 10001 1001 1000101000101 1 1000

(input) 100

(processing) Sjoo = -16

(processing) Sots = 1-6

(output) P-value = 0.109599

(conclusion) Since P-value >0.01, accept the sequence as random.

2.2 Frequency Test within a Block

2.2.1 Test Purpose

The focus of the test is the proportion of ones within M-bit blocks. The purpose of this test is to determine whether the frequency of ones in an M-bit block is approximately M/2, as would be

expected under an assumption of randomness. For block size M=\, this test degenerates to test

1 , the Frequency (Monobit) test.

2.2.2 Function Call

BlockFi!'equency(M,rt), where:

M The length of each block.

n The length of the bit string.

16
Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; £ = ey, 82, ... , e«.

2.2.3 Test Statistic

X (obs): A measure of how well the observed proportion of ones within a given M-bit

block match the expected proportion (1/2).

The reference distribution for the test statistic is a distribution.

2.2.4 Test Description

( 1 ) Partition the input sequence into

bits. M

non-overlapping blocks. Discard any unused

For example, if n = JO. M ^ 3 and e ^ 0110011010,3 blocks (N = 3) would be created,

consisting of Oil, 001 and 101. The final 0 would be discarded.

(2) Determine the proportion 71, of ones in each M-bit block using the equation

M

K: = ^ , for 1 < / < N. M

For the example in this section, 7t; = 2/3, K2 = 1/3, and Tij = 2/3.

N

(3) Compute the statistic: X^(obs) = 4 ( 71/ - Vif.

For the example in this section, y[^(obs) = 4 x3 xii^/^-j/^ ^iy^-j/^ ^i^^-j/JYl.

(4) Compute P-value = igamc {N/2, y^(obs)/2) , where igamc is the incomplete gamma

function for Q{a,x) as defined in Section 5.5.3.3.

Note: When comparing this section against the technical description in Section 3.2, note

that Q(a,x) = 1-P(a,x).

For the example in this section, P-value = igamc ^3_ 1^ = 0.801252.

17
2.2.5 Decision Rule (at tine 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.2.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 4 of Section 2.2.4 is > 0.01 (i.e., P-value = 0.801252), the

conclusion is that the sequence is random.

Note that small P-values (< 0.01) would have indicated a large deviation from the equal

proportion of ones and zeros in at least one of the blocks.

2.2.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n >

100). Note that n > MN. The block size Mshould be selected such that M> 20, M> .01 n and

N<100.

2.2.8 Example

(input) E= 11001001000011111101101010100010001000010110100011

000010001 101001 lOOOlOOl 10001 1001 1000101000101 1 1000

(input) n = 100

(input) M=10

(processing) N= 10

(processing) = 7.2

(output) P-value - 0. 706438

(conclusion) Since P-value > 0.0, accept the sequence as random.

2.3 Runs Test

2.3.1 Test Purpose

18
The focus of this test is the total number of runs in the sequence, where a run is an uninterrupted

sequence of identical bits. A run of length k consists of exactly k identical bits and is bounded

before and after with a bit of the opposite value. The purpose of the runs test is to determine

whether the number of runs of ones and zeros of various lengths is as expected for a random

sequence. In particular, this test determines whether the oscillation between such zeros and

ones is too fast or too slow.

2.3.2 Function Call

Runs(«), where:

n The length of the bit string.

Additional inputs for the ftinction, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £/, 82,

2.3.3 Test Statistic and Reference Distribution

V„(obs): The total number of runs (i.e., the total number of zero runs + the total number of

one-runs) across all n bits.

The reference distribution for the test statistic is a X distribution.

2.3.4 Test Description

Note: The Runs test carries out a Frequency test as a prerequisite.

(1) Compute the pre-test proportion 71 of ones in the input sequence: k = —-—

For example, {{£ = 1001101011, then n=lO and k = 6/10 = 3/5.

(2) Determine if the prerequisite Frequency test is passed: If it can be shown that 1 71 - ^ | > ^•

then the Runs test need not be performed (i.e., the test should not have been run because

of a failure to pass test 1, the Frequency (Monobit) test). If the test is not applicable, then

the P-value is set to 0.0000. Note that for this test, x has been pre-defined in the test

code.

19
(3)

For the example in this section, since x = 2/^^0.63246 , then \n- 1/2\ ^ \ 3/5 - 1/2 \ =0.1

< T, and the test is not run.

Since the observed value n is within the selected bounds, the runs test is applicable.

Compute the test statistic v„(obs) = "j!r(k)+j , where r(k)=0 if Ek^ek+i, and r(k)=l otherwise.

k=l

Since e = 1 00 11 0 1 0 11, then

Vio(obsMl+0+l+0+l+l+l+l+0)+l=7.

^|F„(ofo)-2«7l(l-Jl)|^

(4) Compute P-value = erfc

ly/lrmil-K)

For the example, P-value = erfc

7- r 3 f 2»10»- 1- 3^

5

\ 5.

2*V2»10«-«

5

= 0.147232.

2.3.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.3.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 4 of Section 2.3.4 is > 0.01 (i.e., P-value = 0.147232), the

conclusion is that the sequence is random.

Note that a large value for V„(obs) would have indicated an oscillation in the string which is too

fast; a small value would have indicated that the oscillation is too slow. (An oscillation is considered to be a change from a one to a zero or vice versa.) A fast oscillation occurs when

there are a lot of changes, e.g., 010101010 oscillates with every bit. A stream with a slow

oscillation has fewer runs than would be expected in a random sequence, e.g., a sequence

containing 100 ones, followed by 73 zeroes, followed by 127 ones (a total of 300 bits) would

have only three runs, whereas 150 runs would be expected.

2.3.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n >

100).

20
2.3.8 Example

(input) e- 11001001000011111101101010100010001000010110100011

000010001 101001 10001001 10001 1001 1000101000101 1 1000

(input) «=100

(input) X = 0.02

(processing) 7C = 0.42

(processing) V„(obs) = 52

(output) P-value = 0.500798

(conclusion) Since P-value >0.01, accept the sequence as random.

2.4 Test for the Longest Run of Ones in a Block

2.4.1 Test Purpose

The focus of the test is the longest run of ones within M-bit blocks. The purpose of this test is to determine whether the length of the longest run of ones within the tested sequence is consistent

with the length of the longest run of ones that would be expected in a random sequence. Note

that an irregularity in the expected length of the longest run of ones implies that there is also an

irregularity in the expected length of the longest run of zeroes. Therefore, only a test for ones is necessary. See Section 4.4.

2.4.2 Function Call

LongestRunOfOnes(«), where:

n The length of the bit string.

Additional input for the function supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £/, £2, ••• . £«• M The length of each block. The test code has been pre-set to accommodate three

values fovM: M = 8, M = 128 and M = 70"^ in accordance with the following

table.
Minimum n M

128 8

6272 128

750,000 10^

N The number of blocks; selected in accordance with the value ofM.

2.4.3 Test Statistic and Reference Distribution

X^(obs): A measure of how well the observed longest run length within M-bit blocks

matches the expected longest length within M-bit blocks.

The reference distribution for the test statistic is a % distribution.

2.4.4 Test Description

( 1 ) Divide the sequence into M-bit blocks.

(2) Tabulate the frequencies V/ of the longest runs of ones in each block into categories,

where each cell contains the number of runs of ones of a given length.

For the values of Msupported by the test code, the v, cells will hold the following

counts:

M = 8 M = 128 M = 10'*

Vo < 1 <4 < 10

Vl 2 5 11

V2 3 6 12

V3 >4 7 13

V4 8 14

V5 >9 15

V6 > 16

For an example, see Section 2.4.8.

(3) Compute x (obs ) = X

' —, where the values for Tt, are provided in Section 3.4.

i=0 ^T^i The values of K and N are determined by the value of M in accordance with the

following table:

M K N

8 3 16

22
128 5 49

10^ 6 75

For the example of 2.4.8,

2.^._ (4-16(.2148))'

^ (9-16(.3672))' ^ (3 - 16(.2305))'

^ (0 - 16(.1875))' _ ^ ^^^^^^

16(.2148) 16(.3672) 16(.2305 16(.1875)

(4) Compute P-value = igamc

K r(obs)

2' 2

For the example, P-value = igamc

5 4.882605

2' 2 = 0.180598.

2.4.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.4.6 Conclusion and Interpretation of Test Results

For the example in Section 2.4.8, since the P-value > 0.01 {P-value = 0.180609), the conclusion

is that the sequence is random. Note that large values of y^(obs) indicate that the tested

sequence has clusters of ones.

2.4.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum ofbits as specified in

the table in Section 2.4.2.

2.4.8 Example

For the case where K=3> and M= 8:

(input) e= 11001100000101010110110001001100111000000000001001

00110101010001000100111101011010000000110101111100

1100111001101101100010110010

(input) « = 128

23
(processing)

(processing)

(output)

Subblock Max-Run Subblock Max-Run

11001100 (2) 00010101 (1)

01101100 (2) 01001100 (2)

11100000 (3) 00000010 (1)

01001101 (2) 01010001 (1)

00010011 (2) 11010110 (2)

10000000 (1) 11010111 (3)

11001100 (2) 11100110 (3)

11011000 (2) 10110010 (2)

\'o = 4;Vj=9;V2 = 3; V4 = 0; % = 4.882457

P-value = 0.180609

(conclusion) Since the P-value is > 0.0 1 , accept the sequence as random.

2.5 Binary Matrix Rank Test

2.5.1 Test Purpose

The focus of the test is the rank of disjoint sub-matrices of the entire sequence. The purpose of

this test is to check for linear dependence among fixed length substrings of the original

sequence. Note that this test also appears in the DIEHARD battery of tests [7].

2.5.2 Function Call

Rank(«), where:

n The length of the bit string.

Additional input used by the function supplied by the testing code:

£ The sequence of bits as generated by the RNG or PRNG being tested; this exists as a

global structure at the time of the function call; e = £;, £2, ... , £«• M The number of rows in each matrix. For the test suite, Mhas been set to 32. If other

values of Mare used, new approximations need to be computed.

Q The number of columns in each matrix. For the test suite, Q has been set to 32. If other

values of Q are used, new approximations need to be computed.

24

i
2.5.3 Test Statistic and Reference Distribution

y^(obs)\ A measure of how well the observed number of ranks of various orders match

the expected number of ranks under an assumption of randomness.

The reference distribution for the test statistic is a distribution.

2.5.4

(1)

(2)

(3)

Test Description

Sequentially divide the sequence into M»Q-h\X disjoint blocks; there will exist

such blocks. Discarded bits will be reported as not being used in the

MQ

computation within each block. Collect the M»Q bit segments into Mhy Q matrices.

Each row of the matrix is filled with successive ^-bit blocks of the original sequence e.

For example, if « = 20, M= g = 5, and e = 01011001001010101101, then partition the

stream into A'' = —^ = 2 matrices of cardinality M»Q (3.3 = 9). Note that the last two

3»3

bits (0 and 1) will be discarded. The two matrices are

0 1 0 0 1 0

1 1 0 and I 0 I 0 1 0 0 1 J

. Note that

the first matrix consists of the first three bits in row 1 , the second set of three bits in row

2, and the third set of three bits in row 3. The second matrix is similarly constructed

using the next nine bits in the sequence.

Determine the binary rank (R^)of each matrix, where i = \,...,N . The method for

determining the rank is described in Appendix A.

For the example in this section, the rank of the first matrix is 2 (/?/ = 2), and the rank of

the second matrix is 3 {R2 = 3).

Let Fm - the number of matrices with R( = M(ftill rank),

Fm-1 = the number of matrices with R^ = M-1 (full rank - 1),

N-Fm - Fm-1 ^ the number of matrices remaining.

For the example in this section, Fm = Fj^ 1 {R2 has the full rank of 2>), Fm-i = F2^ 1 (Ri

has rank 2), and no matrix has any lower rank.

(4) Compute

xHobs) = {F^-0.2SSSNy , (F^_,-0.5776A^)^ (N - Fj^-F^-0A336N)

0.28887V

• +

0.5176N

+

0A336N

25
For the example in this section,

2,,, (l-0.2888»2y (l-0.5776«2f (2-l-l-0.1336«2y ^ r..r.r. X iobs) = ^ ^- + ^ ^- + ^ ^ =0.596953.

0.2888 •2 0.5776 •2 0.1336 •2

(5) Compute P - value = e'^^^°'''^'^ . Since M= 3 in the example, the P-value is equal to ^3 x\obsy

igamc

0.596953/

For the example in this section, P-value = e = 0.741948.

2.5.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.5.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 5 of Section 2.5.4 is > 0.01 {P-value = 0.741948), the

conclusion is that the sequence is random.

Note that large values of x

^ (obs ) (and hence, small P-values) would have indicated a deviation

of the rank distribution from that corresponding to a random sequence.

2.5.7 Input Size Recommendations

The probabilities for M = ^ = 52 have been calculated and inserted into the test code. Other

choices of Mand Q may be selected, but the probabilities would need to be calculated. The

minimum number of bits to be tested must be such that n > 38MQ (i.e., at least 38 matrices are

created). For M = Q = 32, each sequence to be tested should consist of a minimum of 38,912

bits.

2.5.8 Example

(input) E = the first 100,000 binary digits in the expansion of e

(input) n - 100000, M=Q = 32 (NOTE: 672 BITS WERE DISCARDED.)

(processing) N=97

(processing) Fm= 23, Fm-j = 60, N - Fm - Fm-i= 14

26
(processing) = 1 .26 1 9656

(output) P-value = 0.532069

(conclusion) Since P-value >0.01, accept the sequence as random.

2.6 Discrete Fourier Transform (Spectral) Test

2.6.1 Test Purpose

The focus of this test is the peak heights in the Discrete Fourier Transform of the sequence. The

purpose of this test is to detect periodic features (i.e., repetitive patterns that are near each other)

in the tested sequence that would indicate a deviation from the assumption of randomness. The

intention is to detect whether the number of peaks exceeding the 95 % threshold is significantly

different than 5 %.

2.6.2 Function Call

DiscreteFourierTransform(«), where:

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

£ The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; 8 = £y, £2, ... , £«.

2.6.3 Test Statistic and Reference Distribution

d: The normalized difference between the observed and the expected number of frequency

components that are beyond the 95 % threshold.

The reference distribution for the test statistic is the normal distribution.

2.6.4 Test Description

(1) The zeros and ones of the input sequence (£) are converted to values of-1 and +1 to create the sequence X = xi,X2, x„, where x,- = 2£/ - 7.

For example, if « = 10 and £ = 1001010011, thenX= 7, -1, -1, 1, -1, 1, -1, -1, 1, 1.

27
(2) Apply a Discrete Fourier transform (DFT) on X to produce: 5 = DFT(X). A sequence

of complex variables is produced which represents periodic components of the sequence

of bits at different frequencies (see Section 3.6 for a sample diagram of a DFT result).

(3) Calculate M = modulus(S') = \S'\, where 5" is the substring consisting of the first n/2

elements in S, and the modulus function produces a sequence of peak heights.

(4) Compute r= V3n = the 95 % peak height threshold value. Under an assumption of

randomness, 95 % of the values obtained from the test should not exceed T.

(5) Compute No = .95n/2. No is the expected theoretical (95 %) number of peaks (under the

assumption of randomness) that are less than T.

For the example in this section, A'o = 4.75.

(6) Compute Nj = the actual observed number of peaks in Mthat are less than T.

For the example in this section, Ni = 4.

(7) Compute d =

V«(.95)(.05)/2

(4 - 4 75)

For the example in this section, d = , \ , , ; = -1.538968.

yllO{.95X.05)/2

(8) Compute P-value = erfc

[y/2 ^

, 1-1. • ^ , 1.538968^

For the example m this section, P-value = erfc

[ V2 J

= 0.123812.

2.6.5 Decision Rule (at tlie 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.6.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 8 of Section 2.6.4 is > 0.01 (P-value = 0.123812), the

conclusion is that the sequence is random.

28
A d value that is too low would indicate that there were too few peaks (< 95 %) below T, and

too many peaks (more than 5 %) above T.

2.6.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 1000 bits (i.e., n >

1000).

2.6.8 Example

(input) £= 11001001000011111101101010100010001000010110100011

000010001 101001 10001001 10001 1001 1000101000101 1 1000

(input) « = 100

(processing) Ni = 46

(processing) No = 47.5

(processing) -0.973329

(output) P-value = 0.330390

(conclusion) Since P-value > 0.01, accept the sequence as random.

2.7 Non-overlapping Template Matching Test

2.7.1 Test Purpose

The focus of this test is the number of occurrences of pre-specified target strings. The purpose

of this test is to detect generators that produce too many occurrences of a given non-periodic

(aperiodic) pattern. For this test and for the Overlapping Template Matching test of Section 2.8, an Aw-bit window is used to search for a specific m-bit pattern. If the pattern is not found, the

window slides one bit position. If the pattern is found, the window is reset to the bit after the

found pattern, and the search resumes.

2.7.2 Function Call

NonOverlappingTemplateMatching(m,«)

m The length in bits of each template. The template is the target string.

29
n The length of the entire bit string under test.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = 8/, £2, ...,£«.

B The m-bit template to be matched; 5 is a string of ones and zeros (of length m)

which is defined in a template library of non-periodic patterns contained within

the test code.

M The length in bits of the substring of e to be tested. Mhas been set to 1 3 1 ,072

(i.e., 2'^) in the test code.

N The number of independent blocks. Nhas been fixed at 8 in the test code.

2.7.3 Test Statistic and Reference Distribution

X^(obs): A measure of how well the observed number of template "hits" matches the

expected number of template "hits" (under an assumption of randomness).

The reference distribution for the test statistic is the distribution.

2.7.4 Test Description

( 1 ) Partition the sequence into Nindependent blocks of length M.

For example, if 8 = 10100100101110010110, then n = 20. If 2 andM = 10, then the

two blocks would be 1010010010 and 1 1 100101 10.

(2) Lot Wj (J = \, N) be the number of times that B (the template) occurs within the

block j. Note that j = 1,...,N. The search for matches proceeds by creating an m-bit

window on the sequence, comparing the bits within that window against the template. If

there is no match, the window slides over one bit , e.g., if w = i and the current window

contains bits 3 to 5, then the next window will contain bits 4 to 6. If there is a match, the

window slides over m bits, e.g., if the current (successful) window contains bits 3 to 5,

then the next window will contain bits 6 to 8.

For the above example, if m = 3 and the template 5 = 001, then the examination

proceeds as follows:

Bit Positions

Block 1 Block 2

Bits Wi Bits W2

1-3 101 0 111 0

30
2-4 010 0 110 0

3-5 100 0 100 0

4-6 001 (hit) Increment to 1 001 (hit) Increment to 1 5-7 Not examined Not examined

6-8 Not examined Not examined

7-9 001 Increment to 2 Oil 1 8-10 010 (hit) 2 110 1

Thus, Wi = 2, and W2 = 1.

(3) Under an assumption of randomness, compute the theoretical mean \x and variance o^:

Li = (M-m+l)/2'" a' =M —

For the example in this section, |X = (10-3+ 1)/2^ = 1, and

a' =10*

^ 1 2*3-1^

(2' 2

2*3 = 0.46875^

N

(4) Compute % (obs ; = X

For the example in this section, % (obs) =_{2-\y+{\-\y _ 1+0

0.46875 0.46875 = 2.133333

(5) Compute P-value = igamc . Note that multiple P-values will be

computed, i.e., one P-value will be computed for each template. For m = 9, up to 148 Pvalues may be computed; for w = /O, up to 284 P-values may be computed.

For the example in this section, P-value = igamc (2_ 2.133333 ^ 2' 2 = 0.344154.

2.7.5 Decision Rule (at tiie 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.7.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 5 of Section 2.7.4 is > 0.01 (P-value = 0.344154), the

conclusion is that the sequence is random.

31
If the P-value is very small (< 0.01), then the sequence has irregular occurrences of the possible

template patterns.

2.7.7 Input Size Recommendations

The test code has been written to provide templates for m = 2, S,..., 10. It is recommended that

m ^ 9 or m ^ lOhQ specified to obtain meaningful results. Although N = 8 has been specified

in the test code, the code may be altered to other sizes. However, Nshould be chosen such that

N< 100 tobQ assured that the P-values are valid. The test code has been written to assume a sequence length of « = 10^ (entered via a calling parameter) and M = 131072 (hard coded). If

values other than these are desired, be sure that M> 0.01 • n and A'^ = \_n/Mj..

2.7.8 Example

For a template B = 000000001 whose size is m = 9:

(input) e = 2^^ bits produced by the G-SHA-1 generator*

(input) n = 2^\ B = 000000001

(processing) |i = 255.984375 and cy^= 247.499999

(processing) W, = 259; W2 = 229; W3 = 271; W4 = 245; W5 = 272; We = 262;

W7 = 259; and Ws = 246

(processing) X^(obs) = 5.999377

(output) P-value = 0. 64 7302

(conclusion) Since the P-value >0.01, accept the sequence as random.

2.8 Overlapping Template Matching Test

2.8.1 Test Purpose

The focus of the Overlapping Template Matching test is the number of occurrences of prespecified target strings. Both this test and the Non-overlapping Template Matching test of

Section 2.7 use an m-bit window to search for a specific m-bit pattern. As with the test in

Section 2.7, if the pattern is not found, the window slides one bit position. The difference

between this test and the test in Section 2.7 is that when the pattern is found, the window slides

only one bit before resuming the search.

' Defined in Federal Information Processing Standard (FIPS) 186-2.

32
2.8.2 Function Call

OverlappingTemplateMatching(m, n)

m The length in bits of the template - in this case, the length of the run of ones.

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

8 The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; £ = £/, 82, ... , 8„.

B The w-bit template to be matched.

K The number of degrees of freedom. K has been fixed at 5 in the test code.

M The length in bits of a substring of 8 to be tested. Mhas been set to 1032 in the

test code.

N The number of independent blocks of n. AAhas been set to 968 in the test code.

2.8.3 Test Statistic and Reference Distribution

y^(obs)'. A measure of how well the observed number of template "hits" matches the

expected number of template "hits" (under an assumption of randomness).

The reference distribution for the test statistic is the distribution.

2.8.4 Test Description

( 1 ) Partition the sequence into Nindependent blocks of length M.

For example, if 8 = 10111011110010110100011100101110111110000101101001, then

n = 50AfK = 2,M= 10 and N^5, then the five blocks are 101 1101 111, 0010110100,

0111001011, 1011111000, and 0101101001 .

(2) Calculate the number of occurrences of B in each of the blocks. The search for

matches proceeds by creating an m-bit window on the sequence, comparing the bits

within that window against B and incrementing a counter when there is a match. The

window shdes over one bit after each examination, e.g., if m = and the first window

contams bits 42 to 45, the next window consists of bits 43 to 46. Record the number of

33
occurrences of B in each block by incrementing an array v, (where i = 0, ...5), such that vo is incremented when there are no occurrences of 5 in a substring, v/ is incremented

for one occurrence ofB,.. .and vj is incremented for 5 or more occurrences of B.

For the above example, if m = 2 and 5=11, then the examination of the first block

{1011101111) proceeds as follows:

Bit Positions Bits No. of occurrences ofB =

11

1-2 10 0

2-3 01 0

3-4 1 1 (hit) Increment to 1 4-5 1 1 (hit) Increment to 2

5-6 10 2

6-7 01 2

7-8 1 1 (hit) Increment to 3

8-9 1 1 (hit) Increment to 4

9-10 1 1 (hit) Increment to 5

Thus, after block 1 , there are five occurrences of 1 1 , vs is incremented, and vo = 0, vi =

0, V2 = 0, V3 = 0, V4 = 0, and vs = 1

.

In a like manner, blocks 2-5 are examined. In block 2, there are 2 occurrences of 1 1 ; V2

is incremented. In block 3, there are 3 occurrences of 1 1; V3 is incremented. In block 4,

there are 4 occurrences of 1 1 ; V4 is incremented. In block 5, there is one occurrence of

1 1 ; vi is incremented.

Therefore, vq = 0, v/ = 7, v2 =/, = 1, v^^ 1, vj = 1 after all blocks have been

examined.

Compute values for A, and rj that will be used to compute the theoretical probabilities n

corresponding to the classes of vq-. X = (M-m+l)/2'" X] = X/2.

For the example in this section, X, = (10-2+ 1)/2^ = 2.25, and r| = }J2=1.125.

, s (v -Nk Y

Compute X (obs)= I,— '— ,whQTQ no = 0.367879, nj ^ 0.1 83940, n2 =

i=o Nn^

0.137955, %3 ^ 0.099634, K4 = 0.069935 and TCj = 0.140657 as computed by the

equations specified in Section 3.8.

For the example in this section, the values of tc, were recomputed, since the example

doesn't fit the requirements stated in Section 3.8.5. The example is intended only for

illustration. The values of 71/ are: Kq = 0.324652, Uj = 0.182617, K2 = 0.142670, K3 =

0.106645, K4 = 0.077147, and Ttj = 0.166269.

34
2^^^^._ {0-5»0.324652y

^ (l - 5 •0.182617y ^ (1 - 5 •0.142670)^

^ ^ ^ 5 •0.324652 5 •0.182617 5^ 0.142670

{l-5^ 0.106645y {l-5^0.077147y (l-5^0J66269y

"I" I 3. 5 • 0.106645

(5) Compute P-value = igamc

5^0.077147

5 x'(obs)

5^ 0.166269

167729.

2 2

For the example in this section, P-value = igamc

5 3.167729 = 0.274932.

2.8.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.8.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 4 of Section 2.8.4 is > 0.01 {P-value = 0.274932), the

conclusion is that the sequence is random.

Note that for the 2-bit template {B= 1 1), if the entire sequence had too many 2-bit runs of ones,

then: 1) Vs would have been too large, 2) the test statistic would be too large, 3) the P-value

would have been small (< 0.01) and 4) a conclusion of non-randomness would have resulted.

2.8.7 Input Size Recommendations

The values ofK, Mand Nhave been chosen such that each sequence to be tested consists of a minimum of 10^ bits (i.e., n > 10^). Various values of m may be selected, but for the time being,

NIST recommends m = 9 or m = 10. If other values are desired, please choose these values as follows:

• n>MN.

• Nshould be chosen so that A'^ • (min Tti) > 5. • X = (M-m+l)/2'" = 2

• m should be chosen so that m ~ log2 M

• Choose K so that K = 2X. Note that the tc, values would need to be

recalculated for values of K other than 5.

35
2.8.8 Example

(input) e the binary expansion of e up to 1,000,000 bits

(input) n = 1000000, B = 111111111

(processing) Vo = S29\ V] = 164; V2 = 150; V3= 1H;V4= 78; and Vj = 136

(processing) X^(obs) = 8.965859

(output) P-value = 0.110434

(conclusion) Since the P-value > 0.01, accept the sequence as random.

2.9 Maurer's "Universal Statistical" Test

2.9.1 Test Purpose

The focus of this test is the number of bits between matching patterns (a measure that is related

to the length of a compressed sequence). The purpose of the test is to detect whether or not the

sequence can be significantly compressed without loss of information. A significantly

compressible sequence is considered to be non-random.

2.9.2 Function Call

Universal(Z, Q, n), where

L The length of each block. Note: the use of L as the block size is not consistent

with the block size notation {M) used for the other tests. However, the use of L as the block size was specified in the original source of Maurer's test.

Q The number of blocks in the initialization sequence.

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

8 The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; 8 = £/, £2, ... , 8«.

,

2.9.3 Test Statistic and Reference Distribution

36
fn : The sum of the log2 distances between matching Z-bit templates, i.e., the sum of the

number of digits in the distance between Z-bit templates.

The reference distribution for the test statistic is the half-normal distribution (a one-sided

variant of the normal distribution) as is also the case for the Frequency test in Section 2.1.

2.9.4 Test Description

(1) The «-bit sequence (e) is partitioned into two segments: an initialization segment

consisting of Q Z-bit non-overlapping blocks, and a test segment consisting of A^I-bit

non-overlapping blocks. Bits remaining at the end of the sequence that do not form a complete Z-bit block are discarded.

Initialization Segment Test Segment

< QxL bits X KxL bits ^-Discard

I Z-bits I Z-bits I ...I i-bits I Z,-bits | Z-bits | i-bits |

. . .

| i-bits | i-bits | < n bits >

< eBlocks X A^Hocks >

The first Q blocks are used to initialize the test. The remaining K blocks are the test blocks {K = \_n/L\ - Q).

For example, if e = 01011010011101010111, then n = 20. If I = 2 and g = 4, then/: = In/Li - Q = I2O/2} - 4 = 6.ThQ initialization segment is 0101 101001; the test segment is 1 1010101 1 1. The Z-bit blocks are shown in the following table:

Block Type Contents

1 01

2 Initialization 01

3 Segment 10

4 10

5 01

6 Test Segment 11 7 01

8 01

9 01

10 11

(2) Using the initialization segment, a table is created for each possible I-bit value (i.e., the

L-bit value is used as an index into the table). The block number of the last occurrence of each Z-bit block is noted in the table (i.e.. For / from 1 to Q, Tj= i, wherej is the

decimal representation of the contents of the i* I-bit block).

37
For the example in this section, the following table is created using the 4 initialization

blocks.

Possible £-bit Value

00 01 10 11

(saved in To) (saved in Ti) (saved in Ti) (saved in T3)

Initialization 0 2 4 0

Examine each of the AT blocks in the test segment and determine the number of blocks

since the last occurrence of the same L-bit block (i.e., / - 7}). Replace the value in the

table with the location of the current block (i.e., 7}= /). Add the calculated distance

between re-occurrences of the same Z-bit block to an accumulating log2 sum of all the

differences detected in the K blocks (i.e., sum = sum + log2(1 - Tj)).

For the example in this section, the table and the cumulative sum are developed as follows:

For block 5 (the 1'* test block): 5 is placed in the "01" row of the table (i.e., T]),

and sum=log2(5-2) ^ 1.584962501.

For block 6: 6 is placed in the "1 1" row of the table (i.e., T3), and sum =

1.584962501 + log2(6-0) = 1.584962501 + 2.584962501 = 4.169925002.

For block 7: 7 is placed in the "01" row of the table (i.e., T]), and sum - 4.169925002 + log2(7-5) = 4.169925002 + 1 = 5.169925002.

For block 8: 8 is placed in the "01" row of the table (i.e., Ti), and sum =

5.169925002 + log2(8-7) = 5.169925002 + 0= 5.169925002.

For block 9: 9 is placed in the "01" row of the table (i.e., Tj), and sum =

5.169925002 + log2(9-8) = 5.169925002 + 0 = 5.169925002.

For block 10: 10 is placed in the "11" row of the table (i.e., T3), and sum =

5.169925002 + log2(10-6) = 5.169925002 + 2 = 7.169925002.

The states of the table are:

Iteration Possible X-bit

Block Value

00 01 10 11

4 0 2 4 0

5 0 5 4 0

6 0 5 4 6

7 0 7 4 6

8 0 8 4 6

9 0 9 4 6

10 0 9 4 10

38
7 (4) Compute the test statistic: /„ = — S log2(i -Tj), where Tj is the table entry

i=Q+l

corresponding to the decimal representation of the contents of the /* Z-bit block

1

• *t.- r 7.169925002 , ,^^^o^c For the example m this section, = = 1.1949875.

(5) Compute P-value = erfc

/„ - expectedValuefL) Via

where erfc is defined in Section

5.5.3.3, and expectedValue(L) and a are taken from a table of precomputed values (see

the table below). Under an assumption of randomness, the sample mean,

expectedValue(L), is the theoretical expected value of the computed statistic for the

given Z-bit length. The theoretical standard deviation is given by o =

var iance(L)

where c = 0.7-—+

L

A ^2

4+ —

L

K

-3/L

15

L expectedValue variance

6 5.2177052 2.954

7 6.1962507 3.125

8 7.1836656 3.238

9 8.1764248 3.311

10 9.1723243 3.356

11 10.170032 3.384

L expectedValue variance

12 11.168765 3.401

13 12.168070 3.410

14 13.167693 3.416

15 14.167488 3.419

16 15.167379 3.421

For the example in this section, P-value ^ erfc

1.1949875-1.5374383 = 0.767189.

^^2^Jl.338

Note that the expected value and variance for L = 2 are not provided in the above table,

since a block of length two is not recommended for testing. However, this value for L is easy to use in an example. The value for the expected value and variance for the case where 1 = 2, although not shown in the above table, were taken from the indicated

reference^.

2.9.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

^ From the ''Handbook ofApplied Cryptography.

^ From the ''Handbook ofApplied Cryptography. "

39
2.9.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 5 of Section 2.9.4 is > 0.01 (P-value = 0.767189), the

conclusion is that the sequence is random.

Theoretical expected values for (p have been computed as shown in the table in step (5) of

Section 2.9.4. If/, differs significantly fi*om expectedValue(L), then the sequence is significantly compressible.

2.9.7 Input Size Recommendations

This test requires a long sequence of bits {n>(Q + K)L) which are divided into two segments

of Z-bit blocks, where L should be chosen so that 6<L< 16. The first segment consists of Q

initialization blocks, where Q should be chosen so that Q = 10 • 2^. The second segment

consists of K test blocks, where K = [n/l] - Q~ 1000 • 2^. The values ofL, Q and n should be

chosen as follows:

n L Q = 10»2^

> 387,840 6 640 > 904,960 7 1280 > 2,068,480 8 2560 > 4,654,080 9 5120 > 1,342,400 10 10240 > 22,753,280 11 20480 > 49,643,520 12 40960 > 107,560,960 13 81920 > 231,669,760 14 163840

> 496,435,200 15 327680 > 1,059,061,760 16 655360

2.9.8 Example

(input) £ = A binary string constructed using G-SHA-l"^

(input) n = 1048576, Z = 7, g = 1280

(note) Note: 4 bits are discarded.

(processing) c =0.591311, a = 0.002703, K = 148516, sum = 919924.038020

" Defined in FIPS 186-2.

40
(processing)

(output)

(conclusion)

fn = 6.194107, expectedValue = 6.196251, a = 3.125

P-value - 0.427733

Since P-value > 0.01, accept the sequence as random.

2.10 Lempel-Ziv Compression Test

2.10.1 Test Purpose

The focus of this test is the number of cumulatively distinct patterns (words) in the sequence.

The purpose of the test is to determine how far the tested sequence can be compressed. The

sequence is considered to be non-random if it can be significantly compressed. A random

sequence will have a characteristic number of distinct patterns.

2.10.2 Function Call

LempelZivCompression(«), where:

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

8 The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £i, £2, ... , £«.

2.10.3 Test Statistic and Reference Distribution

Wobs' The number of disjoint and cumulatively distinct words in the sequence.

The reference distribution for the test statistic is the normal distribution.

2.10.4 Test Description

(1) Parse the sequence into consecutive, disjoint and distinct words that will form a

"dictionary" of words in the sequence. This is accomplished by creating substrings from

consecutive bits of the sequence until a substring is created that has not been found

previously in the sequence. The resulting substring is a new word in the dictionary.

Let Wobs = the number of cumulatively distinct words.

For example, if e = 010110010, then the examination proceeds as follows:

41
Bit Position Bit New Word? The Word is: 1 0 Yes 0 (Bit 1)

2 1 Yes 1 (Bit 2)

3 0 No

4 1 Yes 01 (Bits 3-4)

5 1 No

6 0 Yes 10 (Bits (5-6)

7 0 No

8 1 No

9 0 Yes 010 (Bits 7-9)

There are five words in the "dictionary": 0, 1,01, 10, 010. Hence, Wobs = 5.

(2) Compute P-value = y2 erfc

42^

, where |Li = 69586.25 and a = 470A48718 when

n = 10^. For other values of n, the values of \x. and a would need to be calculated. Note

that since no known theory is available to determine the exact values of \x. and a, these

values were computed (under an assumption of randomness) using SHA-1 . The BlumBlum-Shub generator will give similar results for |li and a^.

Because the example in this section is much shorter than the recommended length, the

values for |li and are not valid. Instead, suppose that the test was conducted on a sequence of a million bits, and the value Wobs = 69600 was obtained, then

P-value = V2 erfc

69586.25-69600

^2 • 70.448718 = 0.949310.

2.10.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.1 0.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 2 of Section 2.10.4 is > 0.01 {P-value = 0.949310), the

conclusion is that the sequence is random.

Note that for n = 106, if Wobs had fallen below 69,561, then the conclusion would have been that

the sequence is significantly compressible and, therefore, not random.

42
2.1 0.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 1,000,000 bits (i.e., n > 10%

2.10.8 Example

(processing) Wots = 69559

(output) P-value = 0.000584

(conclusion) Since P-value < 0.01, reject the sequence as being random.

2.1 1 Linear Complexity Test

2.11.1 Test Purpose

The focus of this test is the length of a linear feedback shiftregister (LFSR). The purpose of this

test is to determine whether or not the sequence is complex enough to be considered random.

Random sequences are characterized by longer LFSRs. An LFSR that is too short implies non- randomness.

2.11.2 Function Call

LinearComplexity(Af, «), where:

M The length in bits of a block.

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £/, 82, ...,£«•

K The number of degrees of freedom; AT = d has been hard coded into the test.

(input) e = the first 1 ,000,000 digits in the binary expansion of e

(input) «= 1,000,000

43
2. 11 .3 Test Statistic and Reference Distribution

y^(ohs)\ A measure of how well the observed number of occurrences of fixed length

LFSRs matches the expected number of occurrences under an assumption of

randomness.

The reference distribution for the test statistic is the distribution.

2.1 1 .4 Test Description

( 1 ) Partition the «-bit sequence into Nindependent blocks of Mbits, where n = MN.

(2) Using the Berlekamp-Massey algorithm^, determine the linear complexity Li of each of

the A'^ blocks (/ = 1, ...,N). Li is the length of the shortest linear feedback shift register

sequence that generates all bits in the block /. Within any Z/-bit sequence, some

combination of the bits, when added together modulo 2, produces the next bit in the

sequence (bit Z,, + 7).

For example, if M= 13 and the block to be tested is 1101011110001, then = 4, and

the sequence is produced by adding the and 2"'^ bits within a 4-bit subsequence to produce the next bit (the 5^ bit). The examination proceeded as follows:

The first 4 bits and the resulting 5*^ bit

Bits 2-5 and the resulting 6* bit

Bits 3-6 and the resulting bit

Bits 9-12 and the resulting IS^"" bit:

Bitl Bitl Bit 3 Bit 4 Bits

1 1 0 1 0

1 0 1 0 1 0 1 0 1 1

1 0 1 1 1 0 1 1 1 1

1 1 1 1 0

1 1 1 0 0

1 1 0 0 0

1 0 0 0 1

(3)

For this block, the trial feedback algorithm works. If this were not the case, other

feedback algorithms would be attempted for the block (e.g., adding bits 1 and 3 to produce bit 5, or adding bits 1, 2 and 3 to produce bit 6, etc.).

Under an assumption of randomness, calculate the theoretical mean |x:

36

^ Defined in The Handbook ofApplied Cryptography; A. Menezes, P. Van Oorschot and S. Vanstone; CRC Press, 1997.

44
(4)

For the example, = (- i/^ {4 - 6. 777222)+ %= 2.999444.

(5) Record the T/ values in vo, as follows:

If: Ti<-2.5 Increment Vo by one

Increment v; by one

Increment V2 by one

Increment vj by one

Increment V4 by one

Increment vj by one

Increment by one

-2.5 <Ti< -1.5

-1.5 < Ti<-0.5

-0.5 <Ti< 0.5

0.5 <Ti< 1.5

1.5 <Ti< 2.5

Ti > 2.5

(6) Compute x^(obs)=

^, where no = 0.01047, m = 0.03125, K2 = 0.125, K3 =

0.5, K4 = 0.25, Ks = 0.0625, Ks = 0.02078 are the probabilities computed by the

equations in Section 3.11.

2. 11 .5 Decision Rule (at tlie 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.1 1 .6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 7 of Section 2.10.4 is > 0.01 (P-value = 0.949310), the

conclusion is that the sequence is random.

Note that if the P-value were <0.01, this would have indicated that the observed frequency

counts of Ti stored in the V/bins varied from the expected values; it is expected that the

distribution of the frequency of the Ti (in the V/ bins) should be proportional to the computed 71, as shown in step (6) of Section 2. 1 1 .5.

K_ X^(obs)

2

' 2

(7) Compute P-value = igame

45
2.1 1 .7 Input Size recommendations

Choose n > 10\ The value of Mmust be in the range 500<M< 5000, and A^> 200 for the %^

result to be valid (see Section 3.11 for a discussion).

2.11.8 Example

(input) 8 = "the first 1 ,000,000 binary digits in the expansion of e

"

(input) n - 1000000 = 10\M^ 1000

(processing) vq ^ 11; V] = 31; V2 = 116; vs = 501; V4 = 258; V5 = 57; vs = 26

(processing) X^(obs) = 2. 700348

(output) P-value = 0.845406

(conclusion) Since the P-value >0.01, accept the sequence as random.

2.12 Serial Test

2.12.1 Test Purpose

The focus of this test is the fi"equency of all possible overlapping m-bit patterns across the entire

sequence. The purpose of this test is to determine whether the number of occurrences of the 2'" w-bit overlapping patterns is approximately the same as would be expected for a random

sequence. Random sequences have uniformity; that is, every m-bit pattern has the same chance

of appearing as every other m-bit pattern. Note that for m = 1 , the Serial test is equivalent to the

Frequency test of Section 2.1.

2.12.2 Function Call

SQna\(m,n), where:

m The length in bits of each block.

n The length in bits of the bit string.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; 8 = 8y, 82, ... , 8„.

46
2.12.3 Test Statistics and Reference Distribution

V\i/m(obs) andV ^\^„,(obs)\ A measure of how well the observed frequencies of m-bit patterns

match the expected frequencies of the m-bit patterns.

The reference distribution for the test statistic is the distribution.

2.12.4 Test Description

(1) Form an augmented sequence e': Extend the sequence by appending the first m-1 bits to the end of the sequence for distinct values of n.

For example, given « = 70 and 8 = 0011011101. \im=3, then e ' = 001101110100. If

m = 2, then £' = 00110111010. If w = 1, then e' = the original sequence 0011011101.

(2) Determine the frequency of all possible overlapping w-bit blocks, all possible

overlapping {m-l)-h\\. blocks and all possible overlapping (m-2)-h\X blocks. Let

V, denote the frequency of the w-bit pattern ii...im: let v, ^ denote the frequency of

the {m-l)-h\i pattern ii...im-i: and let v,

, ^ denote the frequency of the {m-2)~hit pattern

il —im-2-

For the example in this section, when m = 3, then (m-7) = 2, and {m-2) = 1 . The

frequency of all 3-bit blocks is: vqoo - 0, vqoi = 1, vqw - 1, von - 2, vjoo = 1, vjoi = 2_ vuo = 2, vjjj = 0. The frequency of all possible (m-7)-bit blocks is: vqo = 1. voi ' 3, vjo = 3_ V]j = 3. The frequency of all (w-2)-bit blocks is: vq = 4, vj = 6.

2 2'" (3) Compute: \|/; = — I

2 2

'/••'m m-]

n

2'"

2

n

,m-l

2 2

¥.-2 = -

m-2

,m-2

tm-l

tm-2

2 v,t...,-"

-n

For the example in this section,

Vi= —(0 + l + l + 4 + l + 4 + 4 + l)-10 = 12.8-10 = 2.8 ^10

92

\\f^2= —(l + 9 + 9 + 9)-10 = 11.2-10 = 1.2

\)//= —(16 + 36)-10 = 10.4-10 = 0.4

10

47
m—2 '

For the example in this section,

Vvl=¥i-¥L, = %' -^2 =2.8-1.2 = 1.6

V =y\fi - 2vL +¥1-2 = ^3 - + = 2.8 - 2(1 .2)+ 0.4 = 0.8

(5) Compute: P-valuel = igamc (2'" ^,V\|f^ )and

P-value2 = igamc f2'"~^V^

For the example in this section,

P-valuel = igamc(2,1.6)= 0.808792

P-value2 = igamc (/,a<§)= 0.670320.

2.12.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.12.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 5 of Section 2.12.4 is > 0.01 (P-valuel = 0.808792 and Pvalue2 = 0.670320), the conclusion is that the sequence is random.

Note that if V^y^m or had been large, then non-uniformity of the w-bit blocks is impUed.

2.12.7 Input Size Recommendations

Choose m and n such that m < [.log: n\ -2.

2.12.8 Example

(input) e = 1,000,000 bits from the binary expansion of e

(input) m = 2; n = 1000000 - 10^

(processing) #0s = 499971; #ls = 500029

48
WOs = 250116: #01s = #10s = 249855; mis = 250174

(processing) x/^ = 0.343128; \\f^j = 0.003364; m/o = 0.000000

(processing) Vi/i = 0.339764; VV^ = 0.336400

(output) P-valuei = 0. 843 764; P-value2 = 0.561915

(conclusion) Since both P-value1 and P-value2 were >0.01, accept the sequences as random

for both tests.

2.13 Approximate Entropy Test

2.13.1 Test Purpose

As with the Serial test of Section 2.12, the focus of this test is the frequency of all possible

overlapping m-bit patterns across the entire sequence. The purpose of the test is to compare the

frequency of overlapping blocks of two consecutive/adjacent lengths (w and m+1) against the

expected result for a random sequence.

2.13.2 Function Call

ApproximateEntropy(m,«), where:

m The length of each block - in this case, the first block length used in the test. m+1 is the second block length used.

n The length of the entire bit sequence.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the frinction call; e = £/, £2, ••• , £«•

2.13.3 Test Statistic and Reference Distribution

X^(obs): A measure of how well the observed value ofApEn(m) (see step 6 in Section

2.13.4) matches the expected value.

The reference distribution for the test statistic is the distribution.

49
2.13.4 Test Description

(1) Augment the «-bit sequence to create n overlapping m-bit sequences by appending m-1

bits from the beginning of the sequence to the end of the sequence.

For example, if e = 0100110101 and m = 3, then n ^ 10. Append the 0 and 1 at the

beginning of the sequence to the end of the sequence. The sequence to be tested

becomes 010011010101. (Note: This is done for each value of m.)

(2) A frequency count is made of the n overlapping blocks (e.g., if a block containing 8y to

£j+m-i is examined at timej, then the block containing £j+ 1 to £y +m is examined at time

j+1). Let the count of the possible m-bit ((/w+l)-bit) values be represented as cT j where / is the w-bit value.

For the example in this section, the overlapping w-bit blocks (where w = 3) become 010,

100, 001, Oil, 110, 101, 010, 101, 010, and 101. The calculated counts for the 2'" = 2^ =

8 possible m-bit strings are:

#000 = 0, #001 = #010 = 3, #01 1 = i, #100 = /, #101 = i, #i lo = /, #i 1 1 - o

(3) Compute Cl" = — for each value of z. n For example in this section, C^ooo = 0, C^ooi = 0.1, Cfoio ^ 0.3, Cfoii =0.1, Cfjoo = 0.1,

dio] = 0.3,diw=0.1,djij = 0.

(4) Compute (p " '"^ = J^Kilogn; , where tt,- = Cj , andj=log2 i. i=0

For the example in this section, (p^^^ = 0{log 0) + 0.1{log 0.1) + 0.3{log 0.3) + 0.1 (log

0. 1) + 0.1 (log 0.1) + 0.3{log 0.3) + 0.1 (log 0.1) + 0{log 0) = -1.64341772.

(5) Repeat steps 1-4, replacing m by m+7.

Step 1 : For the example in this section, m is now 4, the sequence to be tested becomes

0100110101010.

Step 2: The overlapping blocks become 0100, 1001,0011,0110, 1101, 1010,0101,

1010,0101, 1010. The calculated values are: #0011 = 1, #0100 = 1, #0101 = 2, #0110 =

1, #1001 = 1, #1010 = 3, #1101 = 1, and all other patterns are zero.

Step 3: Cfoou = C^owo = C^oiio = C^woj = iioi = 0.1, Cfoioi = 0.2, Cfjoio = 0:3, and all other values are zero.

Step 4: (p^^^ = 0 + 0 + 0 + O.\(log 0.01) + 0.1 (/og 0.01) + 0.2{log 0.02) + O.\(log 0.01) +

0 + 0 + O.l{log 0.01) + 0.3(/og 0.03) + 0 + 0 + 0.1(/og 0.01) + 0 + 0) = -1.83437197.

50
(6) Compute the test statistic : x

= 2n[log 2 - ApEn(m)] , where ApEn{m) = cp

^""^ - 9

^""^'^

For the example in this section,

ApEn(3) = -1.643418 -(-1.834372) = 0.190954 = 2*10(0.693147-0.190954) = 0.502193

(7) Compute P-value = igamcf2'""^, ^

For the example in this section, P-value = igamc

0.502193^ 2\ 0.261961.

2.13.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.1 3.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 7 of Section 2.13.4 is > 0.01 (P-value = 0.261961), the

conclusion is that the sequence is random.

Note that small values oiApEn(m) would imply strong regularity (see step 6 of Section 2.13.4).

Large values would imply substantial fluctuation or irregularity.

2.13.7 Input Size Recommendations

Choose m and n such that m < {.log: «J -2.

2.13.8 Example

(input) £= 11001001000011111101101010100010001000010110100011

000010001 101001 10001001 10001 1001 1000101000101 1 1000

(input) m = 2;« = 100

(processing) ApEn(m) = 0.665393

(processing) y^(ohs) = 5.550792

(output) P-value = 0.23530

51
(conclusion) Since P-value >0.01, accept the sequence as random.

2.14 Cumulative Sums (Cusum) Test

2.14.1 Test Purpose

The focus of this test is the maximal excursion (from zero) of the random walk defined by the

cumulative sum of adjusted (-1, +1) digits in the sequence. The purpose of the test is to determine whether the cumulative sum of the partial sequences occurring in the tested sequence

is too large or too small relative to the expected behavior of that cumulative sum for random

sequences. This cumulative sum may be considered as a random walk. For a random sequence,

the excursions of the random walk should be near zero. For certain types of non-random

sequences, the excursions of this random walk from zero will be large.

2.14.2 Function Call

CumulativeSums(moi/e, «), where:

n The length of the bit string.

Additional input for the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £/, £2, ... , £«•

mode A switch for applying the test either forward through the input sequence {mode =

0) or backward through the sequence {mode = 7).

2.1 4.3 Test Statistic and Reference Distribution

z: The largest excursion from the origin of the cumulative sums in the corresponding (- 1

,

+1) sequence.

The reference distribution for the test statistic is the normal distribution.

2.14.4 Test Description

(1) Form a normalized sequence: The zeros and ones of the input sequence (£) are converted

to values XiOi-\ and +1 using Xi = 2Zi - 1.

For example, if £ = 1011010111, thenX= 1, (-1), 1, 1, (-1), 1, (-1), 1, 1, 1.

(2) Compute partial sums Si of successively larger subsequences, each starting with Xi (if

mode - 0) orXn (if mode = 7).

52
Mode = 0 (forward) Mode = 1 (backward)

S2=Xj +X2

S3=Xi+X2+X3

Sk=Xi +X2+X3 + ... +Xk

Sn =X, +X2 +X3 + ... +Xk + ...+ Xn

51 =Xn

52 - Xn + Xn-1

53 Xn+ Xn-l + Xn-2

Sk= Xn+ Xn-l + Xn-2 + ... + Xn-k+l

Sn =Xn +X„.i + Xn-2 + ••• + ^/t-/ + .+ Xi

That is, Sk = Sk-\ + Xk for mode 0, and Sk = Sk.\ + Xn.k+\ for mode 1

For the example in this section, when mode = 0 andX= /, (-1), 1, 1, (-1), 1, (-1), 1, 1, 1,

then:

Si = l S2^ 1 + (-1) = 0

53 = 1 + (-1) + 1 ^ 1

54 = 1 + (-1) + 1 + I ^2

Ss = 1 + (-1) + 1 + 1 + (-1) = 1 Ss^ 1 + (-1) + J + 1 + (-1) + 1 = 2

S?^ 1 + (-1) + 1 + 1 + (-1) + 1 + (-1) = 1 58 = 1 + (-1) + 1 + 1 + (-1) + 1 + (-1) + 1= 2

59 = 1 + (-1) + 1 + 1 + (-1) + 1 + (-1) + 1 + 1 = 3

Sio = 1 + (-1) + 1 + 1 + (-1) + 1 + (-1) + 1 + 1 + 1 = 4

Compute the test statistic z = ^^'-^i-" ^ L where max,<^<„ |Sk I is (the absolute value

of) the largest of the partial sums Sk.

4 For the example in this section, the largest value of Sk is 4, so z = -=

-1 /4 Compute P-va/we = 1- <E)((4A: + l)z)-a)

(4^-l> Y

-3/4

<D((4A: + 3)z)-0

1 /4

(4A: + 1>

^

53
where O is the Standard Normal Cumulative Probability Distribution Function as defined in Section 5.5.3.3.

For the example in this section, P-value - 0.433798.

2.14.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.14.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 4 of Section 2.14.4 is > 0.01 {P-value = 0.433798), the

conclusion is that the sequence is random.

Note that when mode = 0, large values of this statistic indicate that there are either "too many

ones" or "too many zeros" at the early stages of the sequence; when mode = 1 , large values of

this statistic indicate that there are either "too many ones" or "too many zeros" at the late stages.

Small values of the statistic would indicate that ones and zeros are intermixed too evenly.

2.14.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n >

100).

2.14.8 Example

(input) e 1 100100100001 1 1 1 1 101 1010101000100010000101 1010001

000010001 101001 10001001 10001 1001 1000101000101 1 1000

(input) n 100

(input) mode = 0 (forward) || mode - 1 (reverse)

(processing) z = 1.6 (forward) \\z = 1.9 (reverse)

(output) P-value = 0.220968 (forward) |I P-value = 0.1 161 14(reverse)

(conclusion) Since P-value > 0.01, accept the sequence as random.

54
2.15 Random Excursions Test

2.15.1 Test Purpose

The focus of this test is the number of cycles having exactly K visits in a cumulative sum

random walk. The cumulative sum random walk is derived from partial sums after the (0,1)

sequence is transferred to the appropriate (-1, +1) sequence. A cycle of a random walk consists

of a sequence of steps of unit length taken at random that begin at and return to the origin. The

purpose of this test is to determine if the number of visits to a particular state within a cycle

deviates from what one would expect for a random sequence. This test is actually a series of

eight tests (and conclusions), one test and conclusion for each of the states: -4, -3, -2, -1 and +1,

+2, +3, +4.

2.15.2 Function Call

RandomExcursions(«), where:

n The length of the bit string.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the fiinction call; e = ^2, — , £«•

2.15.3 Test Statistic and Reference Distribution

y^(obs)\ For a given state x, a measure of how well the observed number of state visits

within a cycle match the expected number of state visits within a cycle, under an

assumption of randomness.

The reference distribution for the test statistic is the distribution.

2. 1 5.4 Test Description

(1) Form a normalized (-1 , +1) sequence X\ The zeros and ones of the input sequence (e) are changed to values of-1 and +1 via^ = 26, - 1.

For example, if e = 01 101 10101, then « = 70andZ=-/, 1, 1, -1, 1, 1, -1, 1, -1. 1.

(2) Compute the partial sums Si of successively larger subsequences, each starting with Xj.

Form the set 5= {Si}.

Si=Xi

55
S2=Xi +X2

S3=Xi+X2+X3

Sk=Xi+X2+X3 + ...+Xk

Sn=Xi+X2+X3+ ... +Xk+ ... + Xn

For the example in this section,

82^0

S3 = J 84 = 0

56 = 2

57 = l

58 = 2

59 = 1 Sjo - 2

The set S = {-1, 0, 1, 0, 1, 2, 1, 2, 1, 2}.

(3) Form a new sequence 5" by attaching zeros before and after the set S. That is, 5" = 0, si,

S2, ... , S„,0.

For the example in this section, S' = 0, -1, 0, 1, 0, 1, 2, 1, 2, I, 2, 0. The resulting

random walk is shown below.

(4) Let / = the total number of zero crossings in S', where a zero crossing is a value of zero

in 5"

' that occurs after the starting zero. J is also the number of cycles in S", where a cycle of y is a subsequence of 5^consisting of an occurrence of zero, followed by nozero values, and ending with another zero. The ending zero in one cycle may be the

beginning zero in another cycle. The number of cycles in 5" is the number of zero

crossings. If / < 500, discontinue the test^.

^ J times the minimum of the probabilities found in the table in Section 3.15 must be > 5 in order to satisfy the empirical rule for Chi-square computations.

-2-

Example Random Walk (5')

56
For the example in this section, if 5'= {0, -1, 0 1, 0, 1, 2, 1, 2, 1, 2, 0}, then J= 3 (there are zeros in positions 3, 5 and 12 of 5"). The zero crossings are easily observed in the

above plot. Since J =3, there are 3 cycles, consisting of {0, -1, 0}, {0, 1, 0} and {0, 1, 2,1,2,1,2, 0}.

For each cycle and for each non-zero state value x having values -4<x<-l and 1 <x<

4, compute the frequency of each jc within each cycle.

For the example in this section, in step 3, the first cycle has one occurrence of-1, the

second cycle has one occurrence of 1 , and the third cycle has three occurrences each of 1 and 2. This can be visualized using the following table.

Cycles

State Cycle 1 Cycle 2 Cycle 3

JC (0, -1,0) (0, 1, 0) (0,1,2,1,2,1,2,0)

-4 0 0 0

-3 0 0 0

-2 0 0 0

-1 1 0 0

1 0 1 3

2 0 0 3

3 0 0 0

4 0 0 0

For each of the eight states ofx, compute Vk(x) = the total number of cycles in which

state JC occurs exactly k times among all cycles, for 0, 1, 5 (for A: = 5, all

5 frequencies > 5 are stored in V5(jc)). Note that Yyk(^) = '^- k=0

For the example in this section,

• Vo(-l) = 2 (the -1 state occurs exactly 0 times in two cycles), = 1 (the -1 state occurs only once in 1 cycle), and

V2(-l) = ^3(-l) = V/-7; = V5(-1) = 0 (the -1 state occurs exactly {2, 3, 4, >5}

times in 0 cycles).

• Vo(l) = 1 (the 1 state occurs exactly 0 times in I cycle),

Vi(l) = 1 (the 1 state occurs only once in 1 cycle), = 1 (the 1 state occurs exactly three times in 1 cycle), and

\!2(1) = ^41) =V5(1) = 0 (the 1 state occurs exactly {2, 4, >5} times in 0

cycles).

• yfo(2) = 2 (the 2 state occurs exactly 0 times in 2 cycles),

V3(2) = 1 (the 2 state occurs exactly three times in 1 cycle), and

57
Vi(2) = V2(2) = V4(2) = V5(2) = 0 (the 1 state occurs exactly {1,2, 4, >5}

times in 0 cycles).

• "^oM) = S (the -4 state occurs exactly 0 times in 3 cycles), and

V](-4) = V2(-4) = V3(-4) = V4(-4) = V5(-4) = 0 (the -4 state occurs exactly {1,

2, 3, 4, >5} times in 0 cycles).

And so on....

This can be shown using the following table:

State X

Number of Cyc es 0 1 2 3 4 5

-4 3 0 0 0 0 0

-3 3 0 0 0 0 0

-2 3 0 0 0 0 0

-1 2 1 0 0 0 0

1 1 1 0 1 0 0

2 2 1 0 0 0 0

3 3 0 0 0 0 0

4 3 0 0 0 0 0

For each of the eight states ofx, compute the test statistic

5 A. /„i

X

(obs j = X

^^'^^^^ J''^k(^))

^ where nk(x) is the probability that the state x occurs k

k=0 JT^k(^)

times in a random distribution (see Section 3.15 for a table of Kk values). The values for

nic(x) and their method of calculation are provided in Section 3.15. Note that eight %

statistics will be produced (i.e., for x = -4, -3, -2, -1, 1, 2, 3, 4).

For example in this section, when x = 1,

2 _ (1-3(0.5))^ (1-3(0.25))^ (0-3(0.125))^ (1-3(0.0625))^ (0-3(0.0312))^ ^ (0-3(0.0312))^ ^ ~ 3(0.5) ^ 3(0.25) 3(0.125) 3(0.0625) 3(0.0312) 3(0.0312) = 4.333033

For each state ofjc, compute P-value = \g'Amc(5/2, x

^ (obs jjl) . Eight P-values will be

produced.

For the example when x= I, P-value = igamc

f 5_ 4.333033 ^ 2' 2 = 0.502529.

58
2.15.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.15.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 8 of Section 2.15.4 is > 0.01 {P-value = 0.502529), the

conclusion is that the sequence is random.

Note that if x^(obs) were too large, then the sequence would have displayed a deviation from the

theoretical distribution for a given state across all cycles.

2.15.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 1,000,000 bits (i.e., n > 10%

2.15.8 Example

(input) 8 = "the binary expansion of e up to 1 ,000,000 bits"

(input) n = 1000000 = 10^

(processing) J = 1490

State=j[: P-value Conclusion

-4 3.835698 0.573306 Random

-3 7.318707 0.197996 Random

-2 7.861927 0.164011 Random

-1 15.692617 0.007779 Non-random

+1 2.485906 0.778616 Random

+2 5.429381 0.365752 Random

+3 2.404171 0.790853 Random

+4 2.393928 0.792378 Random

(conclusion) For seven of the states ofx, the P-value is > 0.01, and the conclusion would be

that the sequence was random. However, for one state ofx (x = -

1 ), the P-value

is < 0.01, so the conclusion would be that the sequence is non-random. When

59
contradictions arise, further sequences should be examined to determine whether

or not this behavior is typical of the generator.

2.16 Random Excursions Variant Test

2.16.1 Test Purpose

The focus of this test is the total number of times that a particular state is visited (i.e., occurs) in a cumulative sum random walk. The purpose of this test is to detect deviations from the

expected number of visits to various states in the random walk. This test is actually a series of

eighteen tests (and conclusions), one test and conclusion for each of the states: -9, -8, . . ., -1 and

+l,+2, ...,+9.

2.16.2 Function Call

RandomExcursionsVariant(«), where:

n The length of the bit string; available as a parameter during the function call.

Additional input used by the function, but supplied by the testing code:

e The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; e = £y, 82, ...,£«.

2.16.3 Test Statistic and Reference Distribution

^; For a given state x, the total number of times that the given state is visited during the

entire random walk as determined in step 4 of Section 2. 13.4.

The reference distribution for the test statistic is the half normal (for large n). (Note: If ^ is distributed as normal, then |^| is distributed as half normal.) If the sequence is random, then the

test statistic will be about 0. If there are too many ones or too many zeroes, then the test statistic will be large.

2.16.4 Test Description

( 1 ) Form the normalized (- 1

, + 1 ) sequence Xin which the zeros and ones of the input

sequence (e) are converted to values of-1 and +1 viaX = Xi, X2, ... , Xn, where ^ = 2e/

-1.

For example, if e - 01 101 10101, then « = lOdindX^-l, 1, 1, -1, 1, 1, -1, 1, -1, 1.

60
Compute partial sums Si of successively larger subsequences, each starting with xj. Form

the set 5*= {Si}.

Si=Xj

S2=Xj+X2

S3=Xi+X2+X3

Sk=Xi+X2+X3 + ... +Xk

Sr,=Xi+X2+X3 + ...+Xk + .. .+ X„

For the example in this section,

51 = -] S6^2

52 = 0 S7 = l

53 = l S8 = 2

54 = 0 S9 = l

Ss = 1 Sio = 2

The set S = {-1, 0, 1, 0, 1, 2, 1, 2, 1, 2}.

Form a new sequence S' by attaching zeros before and after the set S. That is, 5" = 0, sj,

S2, ... , Sn, 0.

For the example, 5" = 0, -1, 0, J, 0, 1, 2, 1, 2, 1, 2, 0. The resulting random walk is shown below.

-2--

Example Random Walk (5')

For each of the eighteen non-zero states ofx, compute 't,(x) = the total number of times

that state x occurred across all J cycles.

For the example in this section, = 1, ^(1) = 4, ^(2) = 3, and all other l,(x) = 0.

61
(5) For each t,(x), compute P-value = erfc

j2J{A\x\-2)

^ See Section 5.5.3.3 for the definition of erfc.

Eighteen P-values are computed.

f

For the example in this section, when x = 1 , P-value - erfc

0.877371.

\4-3\

p*3[4\4\-2)

2.16.5 Decision Rule (at the 1 % Level)

If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise,

conclude that the sequence is random.

2.16.6 Conclusion and Interpretation of Test Results

Since the P-value obtained in step 7 of Section 2. 1 6.4 is > 0.0 1 for the state x = 1 (P-value =

0.877371), the conclusion is that the sequence is random.

2.16.7 Input Size Recommendations

It is recommended that each sequence to be tested consist of a minimum of 1,000,000 bits (i.e., n > 10\

2.16.8 Example

(input) e = "the binary expansion of e up to 1,000,000 bits"

(input) n = 1000000 = 10^

(processing) / = 1490

State(x) Counts P-value Conclusion

-9 1450 0.858946 Random

-8 1435 0.794755 Random

-7 1380 0.576249 Random

-6 1366 0.493417 Random

-5 1412 0.633873 Random

-4 1475 0.917283 Random

-3 1480 0.934708 Random

62
.9Am W.O lUv/lX ivaliUUlll

_11 1 SO? XvcUlui/lli 140Q \).\.Jl OVJ 1 IVaiiUUiil

1 '^fiQ ivallUUIIl

1 jyyj 0 441 9S4 ivanuuiii

+4 147Q 0 0^0901 IxailClUlll +5 1599 0 505683 J.XCU. R anHnm iViVJlX i +6 1628 0.445935 Random

+7 1619 0.512207 Random

+8 1620 0.538635 Random

+9 1610 0.593930 Random

(conclusion) Since the P-value > 0. 01 for each of the eighteen states of x, accept the sequence

as random.

63
3 TECHNICAL DESCRIPTION OF TESTS

This section contains the mathematical backgound for the tests in the NIST

test suite. Each subsection corresponds to the appropriate subsection in Section 2. The relevant references for each subsection are provided at the end

of that subsection.

3.1 Frequency (Monobit) Test

The most basic test is that of the null hypothesis: in a sequence of independent identically distributed Bernoulli random variables (X's or e's, where X

= 2e-l, and so S'^ = Xi + . . . + X„ = 2(ei + . . . + e„) — n), the probabiUty of ones is |. By the classic De Moivre-Laplace theorem, for a sufficiently large

number of trials, the distribution of the binomial sum, normalized by a/ti,

is closely approximated by a standard normal distribution. This test makes

use of that approximation to assess the closeness of the fraction of I's to ^. All subsequent tests are conditioned on having passed this first basic test.

The test is derived from the well-known limit Central Limit Theorem for

the random walk, Sn = + • • • + X„. According to the Central Limit

Theorem,

< - $(z) = ^

r e-'^'/^

This classical result serves as the basis of the simplest test for randomness.

It implies that, for positive z,

According to the test based on the statistic s = \Sn\/y/n, evaluate the observed value |s(o6s)| = |Xi + . . . + Xn\/y/n, and then calculate the corre- sponding P - value, which is 2[1 - $(|s(o6s)|)] = erfc{\s{obs)\/V2). Here,

erfc is the (complementary) error function

erfc{z) — —j^ \ e

^ du.

sJ-K Jz

Km P n—*oo

64
References for Test

[1] Kai Lai Chung, Elementary Probability Theory with Stochastic Processes.

New York: Springer-Verlag, 1979 (especially pp. 210-217).

[2] Jim Pitman, Probabihty. New York: Springer-Verlag, 1993 (especially

pp. 93-108).

3.2 Frequency Test within a Block

The test seeks to detect locaHzed deviations from the ideal 50 % frequency of

I's by decomposing the test sequence into a number of nonoverlapping subsequences and applying a chi-square test for a homogeneous match of empirical

frequencies to the ideal |. Small P — values indicate large deviations from

the equal proportion of ones and zeros in at least one of the substrings. The

string of O's and I's (or equivalent -I's and I's) is partitioned into a number of

disjoint substrings. For each substring, the proportion of ones is computed.

A chi-square statistic compares these substring proportions to the ideal |.

The statistic is referred to a chi-squared distribution with the degrees of freedom equal to the number of substrings.

The parameters of this test are M and A^, so that n = MA'', i.e., the original string is partitioned into A'' substrings, each of length M. For each of

these substrings, the probability of ones is estimated by the observed relative

frequency of I's, tt^, z = 1, . . . ,N. The sum

under the randomness hypothesis has the x^-distribution with A'' degrees of

freedom. The reported P — value is

N r 1

e-u/2^N/2-l ^ JO

Hobs)/2 g

, —u,U du

r(Ar/2)2^/2 r (A^/2)

65
References for Test

[1] Nick Maclaren, "Cryptographic Pseudo-random Numbers in Simulation,"

Cambridge Security Workshop on Fast Software Encryption. Dec. 1993.

Cambridge, U.K.: R. Anderson, pp. 185-190.

[2] Donald E. Knuth, The Art of Computer Programming. Vol 2: Seminumerical Algorithms. 3rd ed. Reading, Mass: Addison-Wesley, 1998 (especially

pp. 42-47).

[3] Milton Abramowitz and Irene Stegun, Handbook of Mathematical Functions: NBS Applied Mathematics Series 55. Washington, D.C.: U.S. Government Printing Office, 1967.

3.3 Runs Test

This variant of a classic nonparametric test looks at "runs" defined as substrings of consecutive I's and consecutive O's, and considers whether the

oscillation among such homogeneous substrings is too fast or too slow.

The specific test used here is based on the distribution of the total number of

runs, Vn- For the fixed proportion n = J2j ^j/n (which by the Frequency test of Section 3.1 must have been estabhshed to be close to 0.5: Itt — || < ^).

l,^p( yn-^nj{l-n) ^ \

(2)

V 2v^7r(l -n) - J

^

^ ^

^

To evaluate Ki, define for = 1, . .

.

, n — 1, r{k) = 0 if Cfc = e^+i and r{k) = 1

if Ck 7^ Cfc+i- Then 14 = YlkZl r{k) + 1. The P - value reported is

erfc |K(o6s)-2n7r(l-7r)|

2V2n7r(l - tt)

Large values of Vn{obs) indicate oscillation in the string of e's which is too

fast; small values indicate oscillation which is too slow.

66
References for Test

[1] Jean D. Gibbons, Nonparametric Statistical Inference, 2nd ed. New York:

Marcel Dekker, 1985 (especially pp. 50-58).

[2] Anant P. Godbole and Stavros G. Papastavridis, (ed), Runs and patterns in probability: Selected papers. Dordrecht: Kluwer Academic, 1994.

3.4 Test for the Longest Run of Ones in a Block

The length of the longest consecutive subsequence (run) of ones is another

characteristic that can be used for testing randomness. A string of length n, such that n = MN, must be partitioned into substrings, each of length M.

For the test based on the length of the longest run of ones Vj within the j-th.

substring of size M, K classes are chosen (depending on M). For each of

these substrings, one evaluates the frequencies I'oii'i, iI'k (z^o + ^^i + • • • +

uk = A^, i.e., the computed values of the longest run of ones within each of

these substrings belonging to any of the K -\- 1 chosen classes). If there are r ones and M — r zeroes in the m-bit block, then the conditional probabihty

that the longest string of ones v in this block is less than or equal to m has

the following form with U = min (m

(1962)):

r + 1, j (see David and Barton

P {v < m\r)

r + l\( M - j(m + 1)

7 / \ M - r

so that M

P{u<m) = Y:

r=:0 V /

(3)

The theoretical probabiHties ttcttj, . . . ,7rA- of these classes are determined

from (3).

The empirical frequencies i^i, ? = 0, . .

. , X are conjoined by the x^-statistic

67
which, under the randomness hypothesis, has an approximate x^-distribution

with K degrees of freedom. The reported P — value is

with P(a, x) denoting the incomplete gamma function as expressed in Section 3.2.

The following table contains selected values of K and M with the corresponding probabihties obtained from (3). Cases = 3, M = 8; K = 5, M = 128;

and K = 6, M = 10000 are currently embedded in the test suite code.

K = S,M = S

classes {u < 1} {u = 2} {u = 3} > 4}

probabihties ttq = 0.2148 tti =^ 0.3672 tts = 0.2305 tts = 0.1875

= 5, M = 128

classes {i/ < 4} = 5} {i/ = 6} {u = 7}

probabilities ttq = 0.1174 tti = 0.2430 7r2 = 0.2493 773 = 0.1752

{z/ = 8} {i^>9}

7r4 = 0.1027 7r5 = 0.1124

i^ = 5,M-=512

classes {^^ < 6} {i^ = 7} {i^ = S} {^^ = 9}

probabilities ttq = 0.1170 ttj = 0.2460 tts = 0.2523 tts 0.1755

{z/ = 10} {i^>ll}

7r4 = 0.1015 7r5 = 0.1077

if = 5, M = 1000

classes {u < 7} {z/ = 8} {u = 9} {z/ = 10}

probabilities ttq = 0.1307 tti = 0.2437 ttz = 0.2452 773 = 0.1714

68
{z/=ll} {u>12}

7r4 = 0.1002 7r5 = 0.1088

K = 6,M = 10000

classes {u < 10} {i/ = 11} {u = 12} {u = 13}

probabilities ttq = 0.0882 tti = 0.2092 7r2 = 0.2483 tts = 0.1933

{i/ = 14} {z/ = 15} {i/>16}

7r4 = 0.1208 7r5 = 0.0675 tts = 0.0727

Large values of indicate that the sequence has clusters of ones; the generation of "random" sequences by humans tends to lead to small values of Un

(see Revesz, 1990, p. 55).

References for Test

[1] F. N. David and D. E. Barton, Combinatorial Chance. New York: Hafner

PubUshing Co., 1962, p. 230.

[2] Anant P. Godbole and Stavros G. Papastavridis (ed), Runs and Patterns

in Probabihty: Selected Papers. Dordrecht: Kluwer Academic, 1994.

[3] Pal Revesz, Random Walk in Random and Non-Random Environments.

Singapore: World Scientific, 1990.

3.5 Binary Matrix Rank Test

Another approach to testing for randomness is to check for hnear dependence

among fixed-length substrings of the original sequence: construct matrices

of successive zeroes and ones from the sequence, and check for linear dependence among the rows or columns of the constructed matrices. The deviation

of the rank - or rank deficiency - of the matrices from a theoretically expected

value gives the statistic of interest.

This test is a specification of one of the tests coming from the DIEHARD

69
[1] battery of tests. It is based on the result of Kovalenko (1972) and also

formulated in Marsaglia and Tsay (1985). The result states that the rank

R of the M X Q random binary matrix takes values r = 0, 1, 2, . .

. , m where

m = min{M, Q) with probabihties

^ 2r{Q+M-r)-MQ

jQ

1 (l-2^-«)(l-2^-^)

i=0

1-2^

The probability values are fixed in the test suite code for M = Q = 32. The

number M is then a parameter of this test, so that ideally n = M'^N , where

A'' is the new "sample size." In practice, values for M and N are chosen so that the discarded part of the string, n — NM"^, is fairly small.

The rationale for this choice is that

Pm n = 0.2888..,

Pm-\ ^ ^Pm ^ 0.5776..,

4pM

Pm-2

9

0.1284..

and all other probabilities are very small (< 0.005) when M > 10.

For the A'" square matrices obtained, their ranks Re, i = I,. ..,N are evaluated, and the frequencies Fm, Fm-\ and — Fm — Fm-\ of the values M,

M — 1 and of ranks not exceeding M — 2 are determined:

FM-i = #{Ri^M-l].

To apply the x^-test, use the classical statistic

2 _ {Fm - 0.2888iV)^ (Fm-i - 0.5776Ar)^ ^ ~ 0.2888Ar 0.5776Ar

[N-Fm- Fm-1 - 0.1336A^)^

0.13336A/'

which, under the nuU (randomness) hypothesis, has an approximate x^-

distribution with 2 degrees of freedom. The reported P—value is exp{—x^(o6s)/2}.

70
Interpretation of this test: large values of x^iobs) indicate that the deviation of the rank distribution from that corresponding to a random sequence

is significant. For example, pseudo random matrices produced by a shiftregister generator formed by less than M successive vectors systematically

have rank Re = M, while for truly random data, the proportion of such

occurrences should be only about 0.29.

References for Test

[1] George MarsagUa, DIEHARD: a battery of tests of randomness.

http://stat.fsu.edu/~geo/diehard.html.

[2] I. N. Kovalenko (1972), "Distribution of the Unear rank of a random matrix," Theory of Probabihty and its Applications. 17, pp. 342-346.

[3] G. Marsaglia and L. H. Tsay (1985), "Matrices and the structure of ran- dom number sequences," Linear Algebra and its AppUcations. Vol. 67, pp.

147-156.

3.6 Discrete Fourier Transform (Spectral) Test

The test described here is based on the discrete Fourier transform. It is a member of a class of procedures known as spectral methods. The Fourier

test detects periodic features in the bit series that would indicate a deviation

from the assumption of randomness.

Let Xk be the k*'* bit, where k = l,...,n. Assume that the bits are coded —1 and +1. Let

n

fj = 1^2;^ exp {2ni{k - l)j/n),

where exp {27rikj/n) = cos {27rkj/n) + isin (27rfcj/n), j = 0, . . .

, n - 1, and

i = y/^. Because of the symmetry of the real to complex-value transform,

only the values from 0 to (n/2 - 1) are considered. Let modj be the modulus

of the complex number fj. Under the assumption of the randomness of the

series Xi, a confidence interval can be placed on the values of modj. More

specifically, 95 percent of the values of modj should be less than h = \/3n71
A P — value based on this threshold comes from the binomial distribution.

Let A^i be the number of peaks less than h. Only the first n/2 peaks are

considered. Let Nq = .95N/2 and d = (N^ - Nq) / ^n{.95){.05) /2. The

where is the cumulative probability function of the standard normal

distribution.

Other P — values based on the series fj or modj that are sensitive to departures from randomness are possible. However, the primary value of the

transform comes from a plot of the series modj. In the accompanying figure,

the top plot shows the series of modj for 4096 bits generated from a satisfactory generator. The line through the plot is the 95 % confidence boundary.

The P - value for this series is 0.8077. The bottom plot shows a corresponding plot for a generator that produces bits that are statistically dependent

in a periodic pattern. In the bottom plot, significantly greater than 5 % of

the magnitudes are beyond the confidence boundary. In addition, there is a

clear structure in the magnitudes that is not present in the top plot. The

P — value for this series is 0.0001.

[1] R. N. Bracewell, The Fourier Transform and Its Apphcations. New York:

McGraw-Hill, 1986.

P — value is

References for Test

72
No Evidence of Frequency Components

0 500 1000 1500 2000

Index

Clear Evidence of Frequency Components

0 500 1000 1500 2000

Index

73
3.7 Non-overlapping Template Matching Test

This test rejects sequences exhibiting too many or too few occurrences of a

given aperiodic pattern.

Let B = (e?,---,e^) be a given word (template or pattern, i.e., a fixed

sequence of zeros and ones) of length m. This pattern is to be chosen as if

it were a parameter of the test. We consider a test based on patterns for

fixed length m. A table of selected aperiodic words out of such patterns for

m = 2, . .

. , 8 is provided at the end of this section.

The set of periods of B

^ = {j, 1 < j < m - 1, e°^fc = e2, A; = 1, . .

. , m - j},

plays an important role. For example, when B corresponds to a run of m

ones, B = {1, . . . ,m — 1}. For the B above, ;B = 0, and B is an aperiodic

pattern (i.e., it cannot be written as CC . . . CC for a pattern G shorter than

B with C denoting a prefix of C) . In this situation, occurrences of B in the

string are non-overlapping.

In general, let W = H^(m, M) be the number of occurrences of the given

pattern B in the string. Note that the statistic W is defined also for patterns

B with )B ^ 0. The best way to calculate W is as the sum,

n—m-\-\

i=i

The random variables /(ei_|_fc_i = e°, A; = 1, • • • , m) are m-dependent, so that

the Central Limit Theorem holds for W. The mean and variance of the

approximating normal distribution have the following form,

n — m + 1

1 2m -n

For the test suite code, M and A'' are chosen so that n — MN and N = S.

74
Partition the original string into N blocks of length M. Let Wj = Wj{m, M)

be the number of occurrences of the pattern B in the block j, for j = 1, . .

.

, A/".

Let II = EWj = (M - m + 1)2-^". Then, for large M, Wj has a normal

distribution with mean fi, and variance cr^, so that the statistic

X (o6s) = ^-^y^ (4)

has an approximate x^-distribution with N degrees of freedom. Report the

P- value as 1-P(f,^^).

The test can be interpreted as rejecting sequences exhibiting irregular oc- currences of a given non-periodic pattern.

References for Test

[1] A. D. Barbour, L. Hoist, and S. Janson, Poisson Approximation (1992).

Oxford: Clarendon Press (especially Section 8.4 and Section 10.4).

Aperiodic Templates for small values of 2 < m < 5

m = 2 m 3 m = 4 m 5

0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1

1 0 0 0 1 1 1 0 0 1 0 1

1 1 0 1 0 0 0 0 1 0 1 1

1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1

1 1 1 0 0

1 1 0 1 0

1 0 1 0 0

1 1 0 0 0

1 0 0 0 0

1 1 1 1 0

75
Aperiodic Templates for small values of 6 < m < 8 m = 6 m = 7 m = 8

0 0 0 0 0 0 0 0 0 0 0 •' 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 1 ' 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 •' 0 0 0 0 0 1 0

0 0 0 1 1 0 0 0 0 1 1 ' 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 '• 0 0 0 0 1 0 0

0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0

0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 1 0 0 ^ 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0

0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1

1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0

1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1

1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1

1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0

1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1

1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1

1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0

1 0 0 0 0 0 0 0 0 1 0 1 1 1

1 0 0 1 0 0 0 0 0 1 1 0 1 0

1 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1

1 0 1 1 0 0 0 0 0 1 1 1 1 0

1 0 1 1 1 0 0 0 0 1 1 1 1 1

1 1 0 0 0 0 0 0 1 0 0 0 0 1

1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1

1 1 0 1 0 0 0 0 1 0 0 1 1 1

1 1 0 1 0 1 0 0 1 0 1 0 0 1

1 1 0 1 1 0 0 0 1 0 1 0 1 1

1 1 1 0 0 0 0 0 1 0 1 1 0 1

1 1 1 0 0 1 0 0 1 0 1 1 1 1

1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1

1 1 1 0 0 0 0 1 1 1 1 1 1

1 1 1 1 0 1 0 1 0 0 0 0 0 0 0

1 1 1 1 1 0 0 1 0 0 1 0 0 0 0

1 1 1 1 1 0 1 0 0 1 1 0 0 0

1 0 1 0 0 0 0 0

1 0 0 0 1 0 0

1 0 1 0 1 0 0 0

1 0 1 0 1 1 0 0

1 0 1 1 0 0 0 0

1 0 1 1 0 1 0 0

1 0 1 1 0 0 0

1 0 1 1 1 1 0 0

1 1 0 0 0 0 0 0

1 1 0 0 0 0 1 0

1 1 0 0 0 1 0 0

1 1 0 0 1 0 0 0

1 1 0 0 1 0 1 0

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 1 0 0 0 0 1 0 1 0

0 1 1 0 0

1 0 0 0 0 0

1 0 0 0 1 0

1 0 0 1 0 0

1 0 0 1 1 0

1 0 1 0 0 0

1 0 1 0 1 0

1 0 1 1 0 0

1 1 0 0 0 0

1 1 0 0 1 0

1 1 0 1 0 0

1 1 0 1 1 0

1 1 1 0 0 0

1 1 1 0 1 0

1 1 1 1 0 0

1 1 1 1 1 0

76
3.8 Overlapping Template Matching Test

This test rejects sequences which show too many or too few occurrences of

m-runs of ones, but can be easily modified to detect irregular occurrences of

any periodic pattern B.

To implement this test, parameters M and N are determined so that n = MN, i.e., the original string is partitioned into blocks, each of length M.

Let Wj = Wj{m,n) be the number of (possibly overlapping) runs of ones

of length m in the jth block. The asymptotic distribution of Wj is the compound Poisson distribution (the so-called Polya-Aeppli law, see Chrysaphinou and Papastavridis, 1988):

Eexp{tWj} exp

A(e^ - 1)

when (M - m + 1)2"

k J

A > 0 (i is a real variable).

(5)

The corresponding probabilities can be expressed in terms of the confluent

hypergeometric function $ =i Fi. li U denotes a random variable with the

compoimd Poisson asymptotic distribution, then for u > 1 with r] = A/2

7-n

=1

For example.

u-l

e-1

rje

-277-$(W+ 1,2,7?).

P{U = 0) = e P{U = 1) =

P{U = 2)

7?e" [^ + 2],

P{U = 3) =

r)e'8

7+"+^

P{U = 4) =

rje -n

16

rfi T? 3?? — + — + — + 1 24 2 2

77
The complement to the distribution function of this random variable has the

form

oo I Liu) = P{U > u) = e-'' £ yA(^,w)

£^u+l ^

with

Choose a: +1 classes or cells for U, i.e., {U = 0}, {U = I},- , {U = K -I},

{U > K}. The theoretical probabilities ttctti,.. .,7rK+i of these cells are found from the above formulas. A reasonable choice could be = 5, A =

2,77=1.

After [/i, . .

. , [/tv are found, evaluate the frequencies i'o,i'i, ,i'k of each

cell, i>Q + Vi-\- . . . + = N, and calculate the value of the chi-square statistic

The expression for the P — value is the same as that used in Section 3.7. The

interpretation is that for very small P — values, the sequence shows irregular occurrences of m-runs of ones.

References for Test

[1] 0. Chrysaphinou and S. Papastavridis, "A Limit Theorem on the Number of Overlapping Appearances of a Pattern in a Sequence of Independent

Trials." ProbabiHty Theory and Related Fields, Vol. 79 (1988), pp. 129-143.

[2] N.J. Johnson, S. Kotz, and A. Kemp, Discrete Distributions. John Wiley,

2nd ed. New York, 1996 (especially pp. 378-379).

3.9 Maurer's "Universal Statistical" Test

This test was introduced in 1992 by UeU Maurer of the Department of Computer Science at Princeton University. Maurer's test statistic relates closely

to the per-bit entropy of the stream, which its author asserts is "the correct

quahty measure for a secret-key source in a cryptographic appUcation." As

78
such, the test is claimed to measure the actual cryptographic significance of a defect because it is "related to the running time of [an] enemy's optimal

key-search strategy," or the effective key size of a cipher system.

The test is not designed to detect a very specific pattern or type of statistical defect. HoMrever, the test is designed "to be able to detect any one of

the very general class of statistical defects that can be modeled by an ergodic

stationary source w^ith finite memory." Because of this, Maurer claims that

the test subsumes a number of the standard statistical tests.

The test is a compression-type test "based on the idea of Ziv that a universal statistical test can be based on a universal source coding algorithm.

A generator should pass the test if and only if its output sequence cannot be

compressed significantly." According to Maurer, the source-coding algorithm

due to Lempel-Ziv "seems to be less suited for apphcation as a statistical test" because it seems to be difficult to define a test statistic whose distribution can be determined or approximated.

The test requires a long (on the order of 10 • 2^ + 1000 • 2^ with 6 < L < 16)

sequence of bits which are divided into two stretches of L-bit blocks (6 <

L < 16), Q (> 10 • 2^) initialization blocks and K 1000 • 2^) test blocks.

We take K = ceihng(n/L) — Q to maximize its value. The order of magnitude of Q should be specifically chosen to ensure that all possible L-bit

binary patterns do in fact occur within the initialization blocks. The test

is not suited for very large values of L because the initialization takes time

exponential in L.

The test looks backs through the entire sequence while walking through the

test segment of L-bit blocks, checking for the nearest previous exact L-bit

template match and recording the distance - in number of blocks - to that

previous match. The algorithm computes the log2 of all such distances for

all the L-bit templates in the test segment (giving, effectively, the number

of digits in the binary expansion of each distance). Then it averages over all the expansion lengths by the number of test blocks.

I Q+K

/„ = —[ ^

logs (#indices since previous occurrence of ith template)]

79
The algorithm achieves this efficiently by subscripting a dynamic look-up

table making use of the integer representation of the binary bits constituting

the template blocks. A standardized version of the statistic - the standardization being prescribed by the test - is compared to an acceptable range based

on a standard normal (Gaussian) density, making use of the test statistic's

mean which is given by formula (16) in Maurer (1992),

oo = 2-^^(1 -2-^)^-Mog2i

The expected value of the test statistic /„ is that of the random variable

log2 G where G = Gl is & geometric random variable with the parameter

1 - 2-^.

There are several versions of approximate empirical formulas for the vari- ance of the form

Varifn) = c{L, K)Var{\og^ G)/K.

Here, c{L, K) represents the factor that takes into account the dependent

nature of the occurrences of templates. The latest of the approximations

(Coron and Naccache (1998): not embedded in the test suite code) has the

form

c(i,if) = 0.7-^ + (l.6+i|^)/i-''/^.

However, Coron and Naccache (1998) report that "the inaccuracy due to [this

approximation] can make the test 2.67 times more permissive than what is theoretically admitted." In other words, the ratio of the standard deviation

of /„ obtained from the approximation above to the true standard deviation

deviates considerably from one. In view of this fact and also since all approximations are based on the "admissible" assumption that

^ oo, the

randomness hypothesis may be tested by verifying normality of the observed

values /„, assuming that the variance is unknown. This can be done using a

t-test.

The original sequence must be partitioned into r (r < 20) substrings, on

each of which the value of the universal test statistic is evaluated (for the

same value of parameters K^L and Q). The sample variance is evaluated.

80
and the P — value is

er/c

(

fn - E{L)

References for Test

[1] Ueli M. Maurer, "A Universal Statistical Test for Random Bit Generators," Journal of Cryptology. Vol. 5, No. 2, 1992, pp. 89-105.

[2] J-S Coron and D. Naccache, "An Accurate Evaluation of Maurer's Universal Test," Proceedings of SAC '98 (Lecture Notes in Computer Science).

Berlin: Springer-Verlag, 1998.

[3] H. Gustafson, E. Dawson, L. Nielsen, W. CaelH, "A computer package for

measuring the strength of encryption algorithms," Computers & Security. 13

(1994), pp. 687-697.

[4] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied

Cryptography. Boca Raton: CRC Press, 1997.

[5] J. Ziv, "Compression, tests for randomness and estimating the statistical

model of an individual sequence," Sequences (ed. R.M. CapoceUi). Berlin:

Springer-Verlag, 1990.

[6] J. Ziv and A. Lempel, "A universal algorithm for sequential data compression," IEEE Transactions on Information Theory. Vol. 23, pp. 337-343.

3.10 Lempel-Ziv Compression Test

This test compresses the candidate random sequence using the (1977) LempelZiv algorithm. If the reduction is statistically significant when compared to a theoretically expected result, the sequence is declared to be non-random.

To test a generator, many sequences are tested in this way. Significance

probabilities are calculated for each sequence, and the hypothesis that the

significance probabilities are uniformly distributed are tested, for example,

by the Kolmogorov-Smirnov test.

81
The Lempel-Ziv test is thought to subsume the frequency, runs, other compression, and possibly spectral tests, but it may intersect the random binary

matrix rank test. The test is similar to the entropy test and even more similar

to Maurer's Universal Statistical test. However, the Lempel-Ziv test directly

incorporates the compression heuristic that defines modern information theory.

There are several variations on the Lempel-Ziv algorithm (1977). The test used here assumes that is a binary sequence, and specifically proceeds as follows:

1. Parse the sequence into consecutive disjoint strings (words) so that the

next word is the shortest string not yet seen.

2. Number the words consecutively in base 2.

L.. 3. Assign each word a prefix and a suffix; the prefix is the number of the

previous word that matches all but the last digit; the suffix is the last

digit.

Note that what drives this compression is the number of substrings in the

parsing. It is possible that, for small n, the Lempel-Ziv compression is actually longer than the original representation.

Following the work of Aldous and Shields (1988), let W{n) represent the

number of words in the parsing of a binary random sequence of length n. They show that

"-'oo n/ log2 n

so that the expected compression is asymptotically well-approximated by

n/log2n, and that

a[W{n)\

which implies that a central Hmit theorem holds for the number of words in

the Lempel-Ziv compression. However, Aldous and Shields were unable to

determine the value of cr[iy(n)].

82
That difficulty was nominally overcome by Kirschenhofer, Prodinger, and

Szpankowski (1994) who prove that

a^[W{n)]

login

where C = 0.26600 (to five significant places) and 6{-) is a slowly varying

continuous fimction with mean zero and \6{-)\ < 10~^.

The given sequence is parsed, and the number of words counted. It is not

necessary to go through the complete Lempel-Ziv encoding, since the number

of words, W, is sufficient. W is used to calculate

which is then compared with a standard normal distribution. The test is preferably one-sided, since some patterned sequences actually are flagged for

being too long after compression.

It is unclear whether the asymptotics are usefully accurate for values of n of

the magnitude that may occur when testing random number generators. A

simulation study performed using the Blum-Blum-Shub generator (1986) indicated that the asymptotics are not usefuUy accurate for sequences of length

less than 10 million. Therefore, practitioners are urged to develop empirical

estimates of the average compression length and its standard deviation to use in place of E[W(n)] and cr[W(n)], respectively. The accuracy of such empirical estimates depends upon the randomness of the generator used. The

Blum-Blum-Shub generator was chosen because its randomness is provably

equivalent to the hardness of mathematical factorization.

The P — value is computed as

For this test, the mean and variance were evaluated using SHA-1 for million bit sequences. The mean and variance were computed to be 69586.25

W- n Z =

83
and 70.448718, respectively.

References for Test '

[1] D. Aldous and P. Shields (1988). "A Diffusion Limit for a Class of

Randomly-Growing Binary Trees," Probability Theory and Related Fields.

79, pp. 509-542.

[2] L. Blum, M. Blum, and M. Shub (1994), "A Simple Unpredictable PseudoRandom Number Generator," SIAM Journal on Computing. 15, pp. 364-383.

[3] P. Kirschenhofer, H. Prodinger, and W. Szpankowski (1994), "Digital

Search Trees Again Revisited: The Internal Path Length Perspective," SIAM

Journal on Computing. 23, pp. 598-616.

[4] U. M. Maurer (1992), "A Universal Statistical Test for Random Bit Generators," Journal of Cryptology. 5, pp. 89-105.

[5] J. Ziv and A. Lempel (1977), "A Universal Algorithm for Sequential Data

Compression," IEEE Transactions on Information Theory. 23, pp. 337-343.

3.11 Linear Complexity Test

This test uses linear complexity to test for randomness. The concept of

Hnear complexity is related to a popular part of many keystream generators, namely. Linear Feedback Shift Registers (LFSR). Such a register of

length L consists of L delay elements each having one input and one output.

If the initial state of LFSR is (e£_i, . . . ,61,60)5 then the output sequence,

(cl, cl+i, • • satisfies the following recurrent formula for j > L

tj = (ciCj-i -I- C2ej_2 H h CL€j-L) mod 2.

ci, . . . ,cl are coefficients of the connection polynomial corresponding to a

given LFSR. An LFSR is said to generate a given binary sequence if this

sequence is the output of the LFSR for some initial state.

84
For a given sequence s" = (ei, . .

. , e„), its linear complexity I/(s") is defined

as the length of the shortest LFSR that generates as its first n terms. The

possibihty of using the Hnear complexity characteristic for testing randomness is based on the Berlekamp-Massey algorithm, which provides an efficient

way to evaluate finite strings.

When the binary n-sequence s" is truly random, formulas exist [2] for the

mean, /z„ = EL{s^), and the variance, cr^ = Var{L{s^)), of the linear complexity I/(s") = Ln when the n-sequence s" is truly random. The Crypt-X

package [1] suggests that the ratio [Ln — fin)/crn is close to a standard normal

variable, so that the corresponding P — values can be found from the normal

error function. Indeed, Gustafson et al. [1] (p. 693) claim that "for large n,

Z>(s") is approximately normally distributed with mean n/2 and a variance

86/81 times that of the standard normal statistic z = (L{s'^) —

|)

This is completely false. Even the mean value fin does not oehave asymptotically precisely as n/2, and in view of the boundedness of the variance, this

diff'erence becomes significant. More importantly, the tail probabiHties of

the Umiting distribution are much larger than those of the standard normal

distribution.

The asymptotic distribution of (L„ — //n)/(7„ along the sequence of even or odd values of n is that of a discrete random variable obtained via a mixture

of two geometric random variables (one of them taking only negative values).

Strictly speaking, the asymptotic distribution as such does not exist. The

cases n even and n odd must be treated separately with two different limiting

distributions arising.

Because of this fact the following sequence of statistics is adapted

Tn={-mLn-U +

l-

(6)

Here

n 4 + rv. . . 2 18 • ^

^ These statistics, which take only integer values, converge in distribution to

the random variable T. This Hmiting distribution is skewed to the right.

While P{T = 0) = i, for A; = 1,2. . .

PiT = k) = ^,, (8)

85
It follows from (8) that

P{T>k> 0)

1 3 X

22fc:-2'

for < 0 (9) shows that

P{T <k) =

1 3x22|fcl-i*

So the P — value corresponding to the observed value T^^^ can be evaluated

in the following way. Let k = [I^Q^gl] + 1. Then the P - value is

1 1 1 3 X

22«-i 3 X

22«-2

In view of the discrete nature of this distribution and the impossibility of

attaining the uniform distribution for P — values, the same strategy can be

used that was used with other tests in this situation. Namely, partition the

string of length n, such that that n = MA'', into N substrings each of length

M. For the test based on the linear complexity statistic (6), evaluate Tm

within the j-th substring of size M, and choose K classes (depending on

M.) For each of these substrings, the frequencies, z/q, i^i, • • • , i'k-, of values of

Tm belonging to any oi K-\-l chosen classes, i/q + i^i + .. . + = A'", are determined. It is convenient to choose the classes with end-points at semi-integers.

The theoretical probabilities ttq, tti, . . . , Tr^- of these classes are determined

from (8) and (9). For this purpose, M has to be large enough for the limiting distribution given by (8) and (9) to provide a reasonable approximation.

M should exceed 500. It is recommended that M be chosen so that 500

<M< 5000.

The frequencies axe conjoined by the x^-statistic

K

0

86
which, under the randomness hypothesis, has an approximate ^^-distribution

with K degrees of freedom. The reported P — value is

V {K/2) 2^/2 = igamc

2

' 2

As before, a conservative condition for the use of the ^^-approximation is

For reasonably large values of M and N, the following classes {K = 6) seem

to be adequate: {T < -2.5}, {-2.5 <T< -1.5}, {-1.5 <T< -0.5},

{-0.5 <T< 0.5}, {0.5 <T< 1.5}, {1.5 <T< 2.5}, and {T > 2.5}.

The probabihties of these classes are ttq = 0.01047, tti = 0.03125, 7r2 =

0.12500, TTa = 0.50000, 7r4 = 0.25000, tts = 0.06250, tts = 0.020833. These

probabilities are substantially different from the ones obtained from the nor- mal approximation for which their numerical values are: 0.0041, 0.0432, 0. 1944,

0.3646, 0.2863, 0.0939, 0.0135.

[1] H. Gustafson, E. Dawson, L. Nielsen, and W. Caelh (1994), "A computer

package for measuring the strength of encryption algorithms," Computers

and Security. 13, pp. 687-697.

[2] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone (1997), Handbook

of AppUed Cryptography. CRC Press, Boca Raton, FL.

[3] R.A. Rueppel, Analysis and Design of Stream Ciphers. New York: Springer,

1986.

3.12 Serial Test

The (generalized) serial test represents a battery of procedures based on test- ing the uniformity of distributions of patterns of given lengths.

that

A^minTTj > 5.

References for Test

87
Specifically, for Zi, • • • , running through the set of all 2"^ possible 0, 1 vectors of length m, let i^ii-.j^ denote the frequency of the pattern (zi, • • • ,im)

in the "circularized" string of bits (ei, . .

. , e„, ei, . .. , Cm-i)-

Thus, ip^ is a x^-type statistic, but it is a common mistake to assume that

has the x^-distribution. Indeed, the frequencies i^i^-i^ are not independent.

The corresponding generaUzed serial statistics for the testing of randomness (Kimberley (1987), Knuth, D. E. (1998), Menezes, van Oorschot and

Vanstone, (1997)) are

and

(Here ipl = = 0.) Then V-^^ has a x^-distribution with 2"""^ degrees

of freedom, and V'^ip'^ has a x^-distribution with 2"""^ degrees of freedom.

Thus, for small values of m, m < [log2(n)J —2, one can find the corresponding

2m P — values from the standard formulas.

P - valuel = igamc (2"'-^ V^^)

P-value2 = igamc (2"'-^ V^^^

The result for Vipl and the usual counting of frequencies is incorrectly given

by Menezes, van Oorschot and Vanstone (1997) on p. 181, formula (5.2): +1

should be replaced by —1.

The convergence of VV^^ to the x^- distribution was proven by Good (1953).

References for Test

[1] I. J. Good (1953), "The serial test for samphng numbers and other tests

for randomness," Proc. Cambridge Philos. Soc. 47, pp. 276-284.

88
[2] M. Kimberley (1987), "Comparison of two statistical tests for keystream

sequences," Electronics Letters. 23, pp. 365-366.

[3] D. E. Knuth (1998), The Art of Computer Programming. Vol. 2, 3rd ed.

Reading: Addison-Wesley, Inc., pp. 61-80.

[4] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone (1997), Handbook

of Applied Cryptography. Boca Raton, FL: CRC Press, p. 181.

3.13 Approximate Entropy Test

Approximate entropy characteristics (Pincus and Singer, 1996) are based on

repeating patterns in the string. If Yi{m) = (e^, . .

. , e^+^.i), set

and

-I Ti+l—

n+ 1 - m ^

Cp is the relative frequency of occurrences of the pattern Yi{m) in the string,

and is the entropy of the empirical distribution arising on the set of

all 2"" possible patterns of length m,

$("^) = f:7r,log7r,,

e=i

where tti is the relative frequency of pattern £= (21, • • • , im) in the string.

The approximate entropy ApEn of order m, m > 1 is defined as

ApEn{m) = - $("^+^)

with ApEn{0) = -^^^l ''ApEn{m) measures the logarithmic frequency with

which blocks of length m that are close together remain close together for

blocks augmented by one position. Thus, small values of ApEn{m) imply

strong regularity, or persistence, in a sequence. Alternatively, large values of

ApEn{m) imply substantial fluctuation, or irregularity." (Pincus and Singer,

89
1996, p. 2083).

Pincus and Kalman (1997) defined a sequence to be m-irregular (m-random)

if its approximate entropy ApEn{'m) takes the largest possible value. They

evaluated quantities ApEn{m),m = 0, 1, 2 for binary and decimal expansions

of e, TT, \/2 and y/S with the surprising conclusion that the expansion of Vs

demonstrated more irregularity than that of tt.

For a fixed block length m, one should expect that in long random (irregular)

strings, ApEn{m) ~ log 2. The hmiting distribution of n[log2 — ApEn{m)]

coincides with that of a x^-random variable with 2"^ degrees of freedom. This

fact provides the basis for a statistical test, as was shown by Rukhin (2000).

Thus, with x^{obs) = n[log2 — ApEn{m)], the reported P — value is

igamc(2"^-\x'(o6s)/2).

Actually, this Umiting distribution of approximate entropy is more exact for

its modified definition as

il—im

where I'l-^.-i^ denotes the relative frequency of the template (ii,---,im) in

the augmented (or circular) version of the original string, i.e., in the string

(ei, . .

. , en, ei, . . . , Cm-i). Let uJi^...im = ^^^ii -im be the frequency of the pattern Zi • • • im. Under our definition, uJi^...i^ — Ylk^ii-imk-, so that for any m,

Define the modified approximate entropy as

By Jensen's inequality, log s > ApEn{m) for any m, whereas it is possible

that logs < ApEn{m). Therefore, the largest possible value of the modified

entropy is merely logs, which is attained when n = s"", and the distribution

of all m-patterns is uniform. When calculating the approximate entropy for

several values of m, it is very convenient to have the sum of all frequencies

of m-templates be equal to n.

90
When n is large, ApEn{m) and its modified version cannot differ much.

Indeed, one has with cj' ,• = fn - m + • = n — m + 1

and LUi <m — l. It foUows that

m — 1 n — m + 1

which suggests that for a fixed m, ^^'^^ and l)^"') must be close for large

n. Therefore, Pincus' approximate entropy and its modified version are also

close, and their asymptotic distributions must coincide.

[1] S. Pincus and B. H. Singer, "Randomness and degrees of irregularity,"

Proc. Natl. Acad. Sci. USA. Vol. 93, March 1996, pp. 2083-2088.

[2] S. Pincus and R. E. Kalman, "Not all (possibly) "random" sequences are created equal," Proc. Natl. Acad. Sci. USA. Vol. 94, April 1997, pp. 3513-

3518.

[3] A. Rukhin (2000), "Approximate entropy for testing randomness," Journal of Applied ProbabiHty. Vol. 37, 2000.

3.14 Cumulative Sums (Cusum) Test

This test is based on the maximum absolute value of the partial sums of the

sequence represented in the ±1 fashion. Large values of this statistic indicate

that there are either too many ones or too many zeros at the early stages of

the sequence. Small values indicate that ones and zeros are intermixed too

evenly. A dual test can be derived from the reversed time random walk with

S'i^ = Xn-\ + Xn-k-^i- With this definition, the interpretation of the test results is modified by replacing "the early stages" by "the late stages."

References for Test

91
The test is based on the Hmiting distribution of the maximum of the absolute values of the partial sums, maxi<fc<n \Sk\,

With the test statistic z — mQj.\<k<n\Sk\{phs) j \fn , the randomness hypothesis is rejected for large values of and the corresponding P — value is 1 - H {mdxi<k<n \Sk\{obs)/y/n) = 1 - G {maxi<k<n \Sk\{obs)/^/n) where the

function G{z) is defined by the formula (11).

The series H{z) in the last line of (10) converges quickly and should be

used for numerical calculation only for small values of z. The function G{z)

(which is equal to H{z) for all z) is preferable for the calculation for moderate

and large values of maxi<fc<„ \Sk\{obs)/\/n,

= t (-l)^xp{- '"-f^'' } du

OO = E {-i)'[mk+i)z)-m2k-i)z)]

k=—oo

oo = $(2) - $(-z) + 2 Y.i-l)'' M{2k + l)z) - $((2fc - l)z)]

k=i

00 = $(z) - ^-z) - 2 E [2$((4A; - 1)^) - $((4fc + 1)^) - $((4A; - 3)z)]

k=i

« $(z) - ^{-z) - 2 [2^{Sz) - $(52) - ^{z}]

4 2^

« 1 - ^=^exp{-—}, 2^00. (11)

where $(x) is the standard normal distribution.

More directly, using Theorem 2.6, p. 17 of Revesz (1990), one obtains

P f max \Sk\ > z)

\l<k<n J

92
oo = 1- E Pm-l)z<Sn<{4k+l)z))

k——oo

oo + J2 P{{4:k + l)z<Sr,<{4k^S)z)).

fc=—oo This formula is used for the evaluation of the P - values with

z= max \Sk\{obs)/y/n.

The randomness hypothesis is rejected for large values of z.

References for Test

[1] Frank Spitzer, Principles of Random Walk. Princeton: Van Nostrand,

1964 (especially p. 269).

[2] Pal Revesz, Random Walk in Random And Non-Random Environments.

Singapore: World Scientific, 1990.

3.15 Random Excursions Test

This test is based on considering successive sums of the binary bits (plus or minus simple ones) as a one-dimensional random walk. The test detects

deviations from the distribution of the number of visits of the random walk

to a certain "state," i.e., any integer value.

Consider the random walk Sk = Xi -\- . . . Xk as a sequence of excursions to

and from zero

Let J denote the total number of such excursions in the string. The limiting

distribution for this (random) number J (i.e., the number of zeros among the

sums Sk^k = 1, 2, . .

. , n when 5*0 = 0) is known to be

(?, ...,e) : Si-i Sk^O for i <k <£.

n-hm P oo (12)

93
The test rejects the randomness hypothesis immediately if J is too small,

i.e., if the following P — value is small:

P{J<J{obs))^^-l e-^Uu = Pi^-,^y

If J < max(0.005y^, 500), the randomness hypothesis is rejected. Otherwise

the number of visits of the random walk 5 to a certain state is evaluated.

Let ^{x) be the number of visits to a;, a; 7^ 0, during one 0-excursion. Its distribution is derived in Revesz (1990) and Baron and Rukhin (1999):

F(aar) = 0) = l--^ (13)

and for k — 1,2,

P,j(,).fc,._L(i__L)'-' (14)

This means that ^(a:) = 0 with probability 1 — l/2|a;|; otherwise (with probability l/2|a;|), ^{x) coincides with a geometric random variable with the

parameter l/2|a:|.

It is easy to see that

E^x) = 1, and

Var{^{x)) = i\x\ - 2. A useful formula is:

P(e(a;)>a+l) = 2a;P(aa;) = a + l) = ^(^l-^^ , a = 0,l,2,....

(15)

The above results are used for randomness testing in the following way. For

a "representative" collection of values (say, l<x<7or—7<a;<—1: -4 < a; < 4 is used in the test suite code), evaluate the observed frequencies

94
Ukix) of the number k of visits to the state x during J excursions which occur

in the string. So Uk{x) = Y/j^i ^{{x) with //^(x) = 1 if the number of visits to

X during the jth excursion {j = 1, . .

. , J) is exactly equal to fc, and ui{x) = 0

otherwise. Pool the values of ^{x) into classes, say, = 0, 1, . . . , 4 with an

additional class A; > 5. The theoretical probabihties for these classes are:

7ro(a;) = P(C(x) = 0) = l-^;

= P(a.)> 5) =

These probabihties have the form

7ro(a;) 'Kx{x) T^2{X) T^z{x) T^^[X)

X = 1 0.5000 0.2500 0.1250 0.0625 0.0312 0.0312

X = 2 0.7500 0.0625 0.0469 0.0352 0.0264 0.0791

X = 3 0.8333 0.0278 0.0231 0.0193 0.0161 0.0804

X = 4 0.8750 0.0156 0.0137 0.0120 0.0105 0.0733

X = 5 0.9000 0.0100 0.0090 0.0081 0.0073 0.0656

X — 6 0.9167 0.0069 0.0064 0.0058 0.0053 0.0588

X — 7 0.9286 0.0051 0.0047 0.0044 0.0041 0.0531

Compare these frequencies to the theoretical ones using the x^-test,

which, for any x under the randomness hypothesis, must have approximately

a x^-distribution with 5 degrees of freedom. This is a vahd test when

Jmin7rfc(a;) > 5, i.e., if J > 500. (The test suite code uses k^{x = 4)

for min7rfc(a;).) If this condition does not hold, values of ^(x) must be pooled

into larger classes.

95
The corresponding battery of P — values is reported. These values are obtained from the formula

[1] M. Baron and A. L. Rukhin, "Distribution of the Number of Visits For a Random Walk," Communications in Statistics: Stochastic Models. Vol. 15,

1999, pp. 593-597.

[2] Pal Revesz, Random Walk in Random and Non-random Environments.

Singapore: World Scientific, 1990.

[3] Prank Spitzer, Principles of Random Walk. Princeton: Van Nostrand,

1964, (especially p. 269).

3.16 Random Excursions Variant Test

An alternative to the random excursions test can be derived as foUows. Using

the notation of the previous subsection, let ^j{x) be the total number of visits

to X during J excursions. (The test suite code assumes J > 500.) Since Sk renews at every zero, ^j{x) is a sum of independent identically distributed

variables with the same distribution as ^{x) = ^i{x). Therefore, the limiting

distribution of ^j(a:),

is normal. The randomness hypothesis will be rejected when the P — value

References for Test

is small.

96
References for Test

[1] M. Baron and A. L. Rukhin, "Distribution of the Number of Visits For a Random Walk," Communications in Statistics: Stochastic Models. Vol 15,

1999.

[2] Pal Revesz, Random Walk in Random and Non-random Environments.

Singapore: World Scientific, 1990.

[3] Prank Spitzer, Principles of Random Walk. Princeton: Van Nostrand,

1964 (especially p. 269).

97
4. TESTING STRATEGY AND RESULT INTERPRETATION

Three topic areas will be addressed in this section: (1) strategies for the statistical analysis of a random number generator, (2) the interpretation of empirical results using the NIST Statistical

Test Suite, and (3) general recommendations and guidelines.

4.1 Strategies for the Statistical Analysis of an RNG

In practice, there are many distinct strategies employed in the statistical analysis of a random

number generator. NIST has adopted the strategy outlined in Figure 1. Figure 1 provides an

architectural illustration of the five stages involved in the statistical testing of a random number

generator.

Stage 1: Selection of a Generator

Select a hardware or software based generator for evaluation. The generator should produce a binary sequence of O's and 1 's of a given length n. Examples of pseudorandom generators

(PRNG) that may be selected include a DES-based PRNG from ANSI X9.17 (Appendix C), and

two further methods that are specified in FIPS 186 (Appendix 3) and are based on the Secure

Hash Algorithm (SHA-1) and the Data Encryption Standard (DES).

Stage 2: Binary Sequence Generation

For a fixed sequence of length n and the pre-selected generator, construct a set of m binary

sequences and save the sequences to a file^.

Stage 3: Execute the Statistical Test Suite

Invoke the NIST Statistical Test Suite using the file produced in Stage 2 and the desired

sequence length. Select the statistical tests and relevant input parameters (e.g., block length) to be applied.

Stage 4: Examine the P-values

An output file will be generated by the test suite with relevant intermediate values, such as test

statistics, and P-values for each statisfical test. Based on these P-values, a conclusion regarding

the quality of the sequences can be made.

Stage 5: Assessment: Pass/Fail Assignment

^ Sample data may also be obtained from George Marsaglia's Random Number CDROM, at http://stat.fsu.edu/pub/diehard/cdrom/.

98
GE NERAT O RS

G G G G G

G G G G G

Stage 1: Select a generator.

BINARY SEQUENCES

51 = {0, 1, 1, 1,0, 0, 1, 0, 1. 1.. .1} 52 = (0, 0, 1, 1, 0, 0, 1, 0, 1, 1,...0} 53 = (1, 0, 0, 1, 1, 0, 2, 0, 1, 0,...0}

Stage 2: A set of m sequences, each of length n, is produced from the selected generator.

S„={0, 1, 1, 1,0,1, 1,0, 1,0, ...1

Stage 3: Each binary stream is input into the test suite. Every statistical test evaluates the sequence and returns one or more P-values.

BATTERY OF STATISTICAL TESTS

SiS2

Testj Test2 Testjg

'1,2 ^1,16 \2

rn,l m,2 in,16.

Stage 4: P-values are probabilistic values wliich

lie m the unit interval, i.e., m the range

[0.11. .

P-VALUES

Pi_i = 0.0572 Pi_2 = 0.0392 Pi^i6= 0.8532

P„i = 1.0000 Pn,2 = 0.4634 P^i6 = 0.9999

ASSESSMENT Stage 5: PASS= (Pj J, Pi2. Pi 3, Pi5- ) P-vaiues are used to either affirm the null hypothesis

FAIL= (Pi 10 P2_4, Pg^S' le) ^^> that the sequence is random) or reject the hypothesis.

Figure 1 : Architecture of the NIST Statistical Test Suite

For each statistical test, a set of P-values (corresponding to the set of sequences) is produced.

For a fixed significance level, a certain percentage of P-values are expected to indicate failure.

For example, if the significance level is chosen to be 0.01 (i.e., a = 0.01), then about 1 % of the

sequences are expected to fail. A sequence passes a statistical test whenever the P-value > a

99
and fails otherwise. For each statistical test, the proportion of sequences that pass is computed

and analyzed accordingly. More in-depth analysis should be performed using additional

statistical procedures (see Section 4.2.2).

4.2 The Interpretation of Empirical Results

Three scenarios typify events that may occur due to empirical testing. Case 1 : The analysis of

the P-values does not indicate a deviation from randomness. Case 2: The analysis clearly

indicates a deviation from randomness. Case 3: The analysis is inconclusive.

The interpretation of empirical results can be conducted in any number of ways.

Two approaches NIST has adopted include (1) the examination of the proportion of sequences

that pass a statistical test and (2) the distribution of P-values to check for uniformity.

In the event that either of these approaches fails (i.e., the corresponding null hypothesis must be

rejected), additional numerical experiments should be conducted on different samples of the

generator to determine whether the phenomenon was a statistical anomaly or a clear evidence of

non-randomness.

4.2.1 Proportion of Sequences Passing a Test

Given the empirical results for a particular statistical test, compute the proportion of sequences

that pass. For example, if 1000 binary sequences were tested (i.e., m = 1000), a = 0.01 (the

significance level), and 996 binary sequences had P-values >.01, then the proportion is 996/1000 = 0.9960.

1,0 9994392

9805608

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Tests

Figure 2: P-value Plot

The range of acceptable proportions is determined

using the confidence interval defined

as,^±i. \P(1-P)

, where p = 1-a, and m is the

m

sample size. If the proportion falls outside of this

interval, then there is evidence that the data is non- random. Note that other standard deviation values

could be used. For the example above, the

confidence interval is .99 + 3}^^^^^ =.99 ±0.0094392 (i.e.,

V 1000 the proportion should lie above 0.9805607. This can be illustrated using a graph as shown in Figure 2. The confidence interval was calculated using a normal distribution as an approximation to the

binomial distribution, which is reasonably accurate for large sample sizes (e.g., n > 1000).

100
4.2.2 Uniform Distribution of P-values

The distribution of P-values is examined to ensure uniformity. This may be visually

illustrated using a histogram (see Figure 3),

whereby, the interval between 0 and 1 is divided

into 1 0 sub-intervals, and the P-values that lie within each sub-interval are counted and

displayed.

Uniformity may also be determined via an

application of a test and the determination of a P-value corresponding to the Goodness-of-Fit

Distributional Test on the P-values obtained for an arbitrary statistical test (i.e., a P-value of the

P-values). This is accomplished by computing

y!o>'

, where Fi is the number of Pi=I 'JO values in sub-interval /, and s is the sample size. A P-value is calculated such that P-valuer -

-I / ) . If P-valuer ^ 0.0001, then the sequences can be considered to be uniformly

distributed.

4.3 General Recommendations and Guidelines

In practice, many reasons can be given to explain why a data set has failed a statistical test. The following is a list of possible explanations. The hst was compiled based upon NIST

statistical testing efforts.

(a) An incorrectly programmed statistical test.

Unless otherwise specified, it should be assumed that a statistical test was tailored to handle a particular problem class. Since the NIST test code has been written to allow the selection of input parameters, the code has been generalized in any number

of ways. Unfortunately, this doesn't necessarily translate to coding ease. A few statistical tests have been constrained with artificial upper bounds. For

example, the random excursions tests are assumed to be no more than max { 1000,

n/128} cycles. Similariy, the Lempel-Ziv Compression test assumes that the longest

word is in the neighborhood of log2 n, where n is the sequence length. Conceivably,

fixed parameters may have to be increased, depending on experimental conditions.

101
(b) An underdeveloped (immature) statistical test.

There are occasions when either probabiUty or complexity theory isn't sufficiently

developed or understood to facilitate a rigorous analysis of a statistical test.

Over time, statistical tests are revamped in light of new results. Since many

statistical tests are based upon asymptotic approximations, careful work needs to be

done to determine how good an approximation is.

(c) An improper implementation of a random number generator.

It might be plausible that a hardware RNG or a software RNG has failed due to a flaw in the design or due to a coding implementation error. In each case, carefiil

review must be made to rule out this possibility.

(d) Improperly written codes to harness test input data.

Another area that needs to be scrutinized is the harnessing of test data. The test data

produced by a (P)RNG must be processed before being used by a statistical test. For

example, processing might include dividing the output stream from the (P)RNG into

appropriate sized blocks, and translating the O's to negative ones. On occasion, it was determined that the failures from a statistical test were due to errors in the code

used to process the data.

(e) Poor mathematical routines for computing P-values

Quality math software must be used to ensure excellent approximations whenever

possible. In particular, the incomplete gamma function is more difficult to approximate for larger values of the constant a. Eventually, P-value formulas will

result in bogus values due to difficulties arising from numerical approximations. To

reduce the likelihood of this event, NIST has prescribed preferred input parameters,

(f) Incorrect choices for input parameters.

In practice, a statistical test will not provide reliable results for all seemingly valid

input parameters. It is important to recognize that constraints are made upon tests on

a test-by-test basis. Take the Approximate Entropy Test, for example. For a sequence length on the order of 1 0^, one would expect that block lengths

approaching log2 n would be acceptable. Unfortunately, this is not the case. Empirical evidence suggests that beyond m = 14, the observed test statistic will

begin to disagree with the expected value (in particular, for known good generators,

such as SHA-1). Hence, certain statistical tests may be sensitive to input parameters.

Considerations must often be made regarding the numerical experimentation input

parameters, namely: sequence length, sample size, block size and template.

102
Sequence Length

The detennination as to how long sequences should be taken for the purposes of

statistical testing is difficult to address. If one examines the FIPS 140-1 statistical

tests, it is evident that sequences should be about 20,000 bits long.

However, the difficulty with taking relatively short sequence lengths is problematic

in the sense that some statistical tests, such as Maurer's Universal Statistical Test,

require extremely long sequence lengths. One of the reasons is the realization that

asymptotic approximations are used in determining the limiting distribution.

Statements regarding the distribution for certain test statistics are more difficult to address for short length sequences than their longer length counterparts.

Sample Size

The issue of sample size is tied to the choice of the significance level. NIST

recommends that, for these tests, the user should fix the significance level to be at least 0.001, but no larger than 0.01 ^ A sample size that is disproportional to the

significance level may not be suitable. For example, if the significance level (a) is chosen to be 0.001, then it is expected that 1 out of every 1000 sequences will be

rejected. If a sample of only 100 sequences is selected, it would be rare to observe a

rejection. In this case, the conclusion may be drawn that a generator was producing

random sequences, when in all likelihood a sufficiently large enough sample was not

used. Thus, the sample should be on the order of the inverse of the significance level

(a'^). That is, for a level of 0.001, a sample should have at least 1000 sequences.

Ideally, many distinct samples should be analyzed.

Block Size

Block sizes are dependent on the individual stadstical test. In the case of Maurer's

Universal Stafistical test, block sizes range fi"om 1 to 16. However, for each specific

block size, a minimum sequence length should be used. If the block size were fixed

at 16, a sequence of more than a billion bits would be required. For some users, that

may not be feasible.

Intuitively, it would seem that the larger the block size, the more information could

be gained fi-om the parsing of a sequence, such as in the Approximate Entropy test. However, a block size that is too large should not be selected either, for otherwise

the empirical results may be misleading and incorrect because the test statistic is better approximated by a distinct probability distribution. In practice, NIST advises

selecting a block size no larger than [jogj «J, where n is the sequence length.

However, certain exceptions hold, and thus NIST suggests choosing a smaller block

size.

Note that for FIPS 140-2, the significance level has been set to 0.0001 for the power up tests.

103
Template

Certain statistical tests are suited for detecting global non-randomness. However,

other statistical tests are more apt at assessing local non-randomness, such as tests developed to detect the presence of too many m-bit patterns in a sequence. Still, it makes sense that templates of a block size greater than [jogj n] should not be

chosen, since frequency counts will most probably be in the neighborhood of zero, which does not provide any useful information^ Thus, appropriate choices must be

made.

Other Considerations

In principle, there are many commonly occurring questions regarding randomness

testing. Perhaps the most frequently asked question is, "How many tests should one

apply?" In practice, no one can truly answer this question. The belief is that the

tests should be independent of each other as much as possible.

Another, frequently asked question concerns the need for applying a monobits test

(i.e., Frequency test), in lieu of Maurer's Universal Statistical test. The perception is that Maurer's Universal Statistical test supercedes the need to apply a monobits test. This may hold true for infinite length sequences. However, it is important to keep in

mind that there will be instances when a finite binary sequence will pass Maurer's

Universal Statistical test, yet fail the monobits test. Because of this fact, NIST

recommends that the Frequency test be applied first. If the results of this test support

the null hypothesis, then the user may proceed to apply other statistical tests.

4.4 Application of IVIultiple Tests

Given a concern regarding the application of multiple tests, NIST performed a study to determine the dependence between the tests. The performance of the tests was checked by

using a Kolmogorov-Smimov test of uniformity on the P-values obtained from the sequences.

However, it required an assumption that the sequences that were generated to test uniformity were sufficiently random. There are many tests in the suite. Some tests should intuitively give

independent answers (e.g., the frequency test and a runs test that conditions on frequencies

should assess completely different aspects of randomness). Other tests, such as the cusum test and the runs test, result in P-values that are likely to be correlated.

To understand the dependencies between the tests in order to eliminate redundant tests, and to ensure that the tests in the suite are able to detect a reasonable range of patterned behaviors, a

factor analysis of the resuhing P-values was performed. More precisely, in order to assess independence, m sequences of binary pseudorandom digits were generated, each of length n, and all A:=161 tests in the suite were applied to those sequences to determine their randomness.

Each test produced a significance probability; denote bypy the significance probability of test / on sequencej.

104
Given the uniformly distributed pij , the transformation = <I> [p^j ) leads to normally

distributed variables. Let zj be the vector of transformed significance probabilities

corresponding to the sequence. A principal components analysis was performed on the zj, ...

, Xm- Usually, a small number of components suffices to explain a great proportion of the

variability, and the number of these components can be used to quantify the number of

"dimensions'" of nonrandomness spanned by the suite tests. The principal component analysis

of this data was performed. This analysis extracts 161 factors, equal to the number of tests. The first factor is the one that explains the largest variability. If many tests are correlated, their

P-values will greatly depend on this factor, and the fi-action of total variability explained by this

factor will be large. The second factor explains the second largest proportion of variability,

subject to the constraint that the second factor is orthogonal to the first, and so on for

subsequent factors. The corresponding fi^actions corresponding to the first 50 factors were

plotted for the tests, based on Blum-Blum-Shub sequences of length 1,000,000. This graph

showed that there is no large redundancy among our tests.

The correlation matrix formed from the z/, ... , Xm was constructed via a statistical software

application (SAS). The same conclusion was supported by the structure of these matrices. The

degree of duplication among the tests seems to be very small.

105
5. USER'S GUIDE

This section describes the set-up and proper usage of the statistical tests developed by NIST that are available in the NIST test code. Descriptions of the algorithms and data structures that were

utilized are included in this section.

5.1 About the Package

This toolbox was specifically designed for individuals interested in conducting statistical testing

of cryptographic (P)RNGs. Several implementations of PRNGs utilized during the development

phase of the project have also been included.

Caveat: The test code was developed using a SUNworkstation under the Solaris operating

system. No guarantee is made regarding the compilation and execution ofthe PRNG

implementations on other platforms. For this reason, a switch has been incorporated into the source codes to disable the inclusion ofthe PRNGs. Theflag INCLUDEJGENERATORS can

befound in the defs.h headerfile.

This package will address the problem of evaluating (P)RNGs for randomness. It will be useful

in:

• identifying (P)RNGs which produce weak (or patterned) binary sequences,

• designing new (P)RNGs,

• verifying that the implementations of (P)RNGs are correct, • studying (P)RNGs described in standards, and

• investigating the degree of randomness by currently used (P)RNGs.

The objectives during the development of the NIST statistical test suite included:

• Platform Independence: The source code was written in ANSI C. However, some

modification may have to be made, depending on the target platform and the compiler.

• Flexibility: The user may freely infroduce their own math software routines.

• Extensibility: New statistical tests can easily be incorporated.

• Versatility: The test suite is useful in performing tests for PRNGs, RNGs and cipher

algorithms.

• Portability: With minor modifications, source code may be ported to different

platforms. The NIST source code was ported onto the SGI Origin, and a 200 MHz PC

using the Microsoft Visual C++ 6.0 development environment.

• Orthogonality: A diverse set of tests is provided.

• Efficiency: Linear time or space algorithms were utilized whenever possible.

106
5.2 System Requirements

This software package was developed on a SUN workstation under the Solaris operating system.

All of the source code was written in ANSI C. Source code porting activities were successful for

the SGI Origin (IRIX 6.5 with the SGI C compiler) and a desktop computer (IBM PC under

Windows 98 and Microsoft C++ 6.0).

In practice, minor modifications will have to be introduced during the porting process in order to ensure the correct interpretation of tests. In the event that a user wishes to compile and execute

the code on a different platform, sample data and the corresponding results for each of the

statistical tests have been provided. In this manner, the user will be able to gain confidence that

the ported statistical test suite is functioning properly. For additional details see Appendix C.

For the majority of the statistical tests, memory must be allocated dynamically in order to proceed. In the event that workspace cannot be provided, the statistical test returns a diagnostic

message.

5.3 How to Get Started

To setup a copy of the NIST test code on a workstation, follow the instructions below.

• Copy the sts.tar file into the root directory. Use the instruction, tar -xvf

sts.tar, to unbundle the source code.

• Several files and subdirectories should have been created. The eight

subdirectories include data/, experiments/, generators/, include/, obj/, src/

and templates/. The four files include assess, grid, makefile, and stats.

• The data/ subdirectory is reserved for pre-existing RNG data files that are under invesfigation. Currently, two formats are supported, i.e., data files consisting of ASCII zeroes and ones, and binary formatted hexadecimal

character strings.

• The experiments/ subdirectory will be the repository of the empirical results

for RNG data. Several subdirectories should be contained in it. These include

AlgorithmTesting/, BBS/, CCG/, G-SHA-1/, LCG/, MODEXP/, MS/,

QCGl/, QCG2/, and XOR/. All but the first of these subdirectories is meant

to store the results for the corresponding PRNG. The AlgorithmTesting/

subdirectory is the default subdirectory for empirical results corresponding to RNG data stored in the data/ subdirectory.

• The generators/ subdirectory contains the source codes for nine pseudo107
random number generators. These include Blum-Blum-Shub, Cubic

Congruential Generator, the FIPS 186 one way function based on SHA-1 (GSHA-1), Linear Congruential Generator, Modular Exponentiation, MicaliSchnorr, Quadratic Congruential Generator I and II, and Exclusive OR. Code

for the ANSI X9. 1 7 generator and the FIPS 1 86 one way fiinction based on DES (G-DES) were removed from the package because of possible export

issues. User defined PRNGs should be copied into this subdirectory, with the

corresponding modifications to the makefile, utilities l.c, defs.h, and proto.h

files.

• The include/ subdirectory contains the header files for the statistical tests, pseudo-random number generators, and associated routines.

• The objV subdirectory contains the object files corresponding to the statistical

tests, pseudo random number generators and other associated routines.

• The src/ subdirectory contains the source codes for each of the statistical tests.

• The templates/ subdirectory contains a series of non-periodic templates for

varying block sizes that are utilized by the NonOverlapping Templates

statistical test.

• User prescribed modifications may be introduced in several files. This will be

discussed subsequently in Section 5.5.2 and Appendix B.

• Edit the makefile. Modify the following lines:

(a) CC (your ANSI C compiler)

(b) ROOTDIR (the root directory that was prescribed earlier in the process,

e.g., rng/)

• Now execute Makefile. An executable file named assess should appear in the

project directory.

• The data may now be evaluated. Type the following: assess <sequenceLength>, e.g., assess 1000000.

Follow the menu prompts. The files stats and grid correspond respectively to the

logs of the per sequence frequency of zeroes and ones and the 0-1 matrix of

fail/pass assignments for each individual sequence and each individual statistical

test.

108
5.4 Data Input and Output of Empirical Results

5.4.1 Data Input

Data input may be supplied in one of two ways. If the user has a stand-alone program or hardware device which implements a RNG, the user may want to construct as many files of

arbitrary length as desired. Files should contain binary sequences stored as either ASCII

characters consisting of zeroes and ones, or as hexadecimal characters stored in binary format.

These files can then be independently examined by the NIST Statistical Test Suite.

In the event that storage space is a problem, the user may want to modify the reference

implementation and plug-in their implementation of the PRNG under evaluation. The bit

streams will be stored directly in the epsilon data structure, which contains binary sequences.

5.4.2 Output of Empirical Results

The output logs of empirical results will be stored in two files, stats and results, that correspond

respectively to the computational information, e.g., test statistics, intermediate parameters, and

P-values for each statistical test applied to a data set.

If these files are not properly created, then it is most probably due to the inability to open the

files for output. See Appendix J for further details.

5.4.3 Test Data Files

Five sample files have been created and are contained in the data/ subdirectory. Four of these

files correspond to the Mathematical generated binary expansion of several classical numbers for over 1,000,000 bits. These files are data.e, data.pi, data.sqrt2, and data.sqrtS. The Mathematica

program used in creating these files can be found in Appendix E. A fifth file, data.shal, was

constructed utilizing the SHA- 1 hash fiinction,

5.5 Program Layout

The test suite package has been decomposed into a series of modules which include the:

statistical tests, (pseudo)random number generators, empirical results (hierarchical) directories,

and data.

The three primary components of the NIST test suite are the statistical tests, the underlying

mathematical software, and the pseudo random number generators under investigation. Other

^ Mathematica, Stephen Wolfram's Computer Algebra System, http://www.mathematica.com.

109
components include the source code library files, the data directory and the hierarchical directory

(experiments/) containing the sample data files and empirical result logs, respectively.

5.5.1 General Program

The NIST test suite contains sixteen tests which will be usefiil in studying and evaluating the

binary sequences produced by random and pseudo random number generators. As in previous

work in this field, statistical tests must be devised which, under some hypothesized distribution,

employ a particular test statistic, such as the number of runs of ones or the number of times a

pattern appears in a bit stream. The majority of the tests in the test suite either (1) examine the

distribution of zeroes and ones in some fashion, (2) study the harmonics of the bit stream

utilizing spectral methods, or (3) attempt to detect patterns via some generalized pattern

matching technique on the basis of probability theory or information theory.

5.5.2 Implementation Details

In practice, any number of problems can arise if the user executes this software in unchartered

domains. It is plausible that sequence lengths well beyond the testing procedure (i.e., on the

order of 1 0^

) may be chosen. If memory is available, there should not be any reason why the

software should fail. However, in many instances, user defined limits are prescribed for data

structures and workspace. Under these conditions, it may be necessary to increase certain

parameters, such as the MAXNUMOFTEMPLATES and the MAXNUMBEROFCYCLES.

Several parameters that may be modified by a user are listed in Table 3.

The parametQT ALPHA denotes the significance level that determines the region of acceptance

and rejection. NIST recommends that ALPHA be in the range [0.00 1,0.01].

The parameter ITMAXis utilized by the special fiinctions; it represents the upper bound on the

maximum number of iterations allowed for iterative computations.

The parameter KAPPA is utilized by the gcfand gser routines defined in the special-functions.

c

file. It represents the desired accuracy for the incomplete gamma fiinction computations.

The parameter MAXNUMOFTEMPLATES indicates the maximum number of non-periodic

templates that may be executed by the Nonoverlapping Template Matchings test. For templates

of size w = P, up to 148 possible non-periodic templates may be applied.

The parameters NUMOFTESTS and NUMOFGENERATORS correspond to the maximum

number of tests that may be defined in the test suite, and the maximum number of generators

specified in the test suite, respectively.

Lastly, the MAXNUMBEROFCYCLES represents the maximum number of cycles that NIST

anticipates in any particular binary sequence.

110
Table 3. User Prescribed Statistical Test Parameters

Source Code Parameter Default Parameter Description/Definition

A T DZJ A ALrrlA U.Ul Significance Level

ITMAX 2000000 Max number of iterations

KAPPA 3e-15 Desired accuracy for incgam

MAXNUMOFTEMPLATES 40 Non-overlapping Templates Test

NUMOFTESTS 16 Max number of tests NUMOFGENERATORS 12 Max number of PRNGs

MAXNUMBEROFCYCLES 40000 Max number of cycles

5.5.3 Description of the Test Code

5. 5. 3. 1 Global Data Structures

Binary sequences are stored in the epsilon data structure. To efficiently store this information, a

bit field structure was introduced. This is a C structure defined to strictly utilize a single bit to store a zero or a one. In essence, the bit field structure utilizes the minimum amount of storage

necessary to hold the information that will be manipulated by the statistical tests. It is flexible

enough to allow easy manipulation by accessing individual bits via an index specification.

5.5.3.2 Special Data Structures

For many of the tests, efficiency is desired in both time and space. A binary tree data structure is used for this purpose. In this case, the binary tree is implemented as an array, whose root node

serves no particular purpose. The binary tree is used in several different ways. One way is as a Boolean structure where each individual node represents either a zero or a one, but whose

content indicates the absence or presence of an individual bit. Parsing this tree indicates the

presence or absence of a word of fixed length. In addition, the binary tree structure is used as an

efficient means to tabulate the frequency of all 2'" words of length w in a finite binary sequence.

This data structure is also employed in the construction of the dictionary required in the LempelZiv coding scheme. The restriction in this case, however, is that if the stream isn't equidistributed (i.e., is very patterned), then the Lempel-Ziv test may break down. This is due to the unbalanced binary tree'*^ which may ensue. In this case, the procedure is halted by the test

suite and a warning statement is returned.

'° The binary tree will be unbalanced due to the presence of too many words exceeding log2 n, where n is the sequence length.

( 111
5. 5. 3. 3 Mathematical Software

Special functions required by the test suite are the incomplete gammafunction and the

complementary errorfunction. The cumulative distribution function, also known as the standard

normalfunction, is also required, but it can be expressed in terms of the error function.

One of the initial concerns regarding the development of the reference implementation was the

dependencies that were required in order to gain reliable mathematical software for the special

functions required in the statistical tests. To resolve this matter, the test suite makes use of the

following libraries:

The Fast Fourier Transform routine was obtained at http://www.netlib.Org/fftpack/fft.c. The normal function utilized in this code was expressed in terms of the error function.

The complementary error function {erfc) utilized in the package is the ANSI C function

contained in the math.h header file and its corresponding mathematical library. This library

should be included during compilation.

The incomplete gamma function is based on an approximation formula whose origin is described

in the Handbook ofApplied Mathematical Functions [ 1 ] and in the Numerical Recipes in C book

[6]. Depending on the values of its parameters a and x, the incomplete gamma function may be

approximated using either a continued fraction development or a series development.

Standard Normal (Cumulative Distribution) Function

Complementary Error Function

Gamma Function

r(z) = j;rV',dt

Incomplete Gamma Function

P{a,x) =

y(a,x) _ 1 j^.e-'t^-'dt

where P(a,0) = 0 and P(a,oo) = 1.

112
Incomplete Gamma Function

where Q(a,0) = 1 and Q(a,oo) = o.

NIST has chosen to use the Cephes C language special functions math library in the test software. Cerphes may be found at http://people.ne.mediaone.net/moshier/index.htm]#Cephes or on the GAMS server at http.7/math.nist.gov/cgi-bin/gams-serve/list-module components/

CEPHES/CPROB/1 3 192.html. The specific functions that are utilized are igamc (for the

complementary incomplete gamma fbnction) and Igam (for the logarithmic gamma function).

5.6 Running the Test Code

A sample NIST Statistical Test Suite monolog is described below. Note: In this section bold

items indicate input.

In order to invoke the NIST statistical test suite, type assess, followed by the desired bit stream

length, n. For example, assess 100000. A series of menu prompts will be displayed in order to select the data to be analyzed and the statistical tests to be applied. The first screen appears as follows:

Once the user has prescribed a particular data set or PRNG, the statistical tests to be applied must

be selected. The following screen is displayed:

GENERATOR OPTIONS

[00] Input File

[02] Linear Congruential

[04] Micali-Schnorr

[06] Quadratic Congruential I [08] Cubic Congruential

[01] G Using SHA-1

[03] Blum-Blum-Shub

[05] Modular Exponentiation

[07] Quadratic Congruential II [09] Exclusive OR

OPTION —> 0

User Prescribed Input File: data/data.pi

113
STATISTICAL TESTS

[01] Frequency [02] Block Frequency

[03] Cumulative Sums [04] Runs

[05] Longest Runs of Ones [06] Rank

[07] Spectral - Discrete Fourier Transform [08] Nonperiodic Template Matchings

[09] Overlapping Template Matchings [10] Universal Statistical

[11] Approximate Entropy [ 1 2] Random Excursions

[13] Random Excursions Variant [14] Serial

[15] Lempel-Ziv Complexity [16] Linear Complexity

INSTRUCTIONS

Enter 0 if you DO NOT want to apply all of the

statistical tests to each sequence and 1 if you DO.

Enter Choice: 0

In this case, 0 has been selected to indicate interest in applying a subset of the available statistical

tests. The following screen is then displayed.

INSTRUCTIONS

Enter a 0 or 1 to indicate whether or not the numbered

statistical test should be applied to each sequence. For

example, 1111111111111111 applies every test to each

sequence.

1234567891111111

0123456

0000000010000000

As shown above, the only test applied was number 9, the Nonoverlapping templates test. A

query for the desired sample size is then made.

How many bit streams should be generated? 10

Ten sequences will be parsed using the data.pi file. Since a file was selected as the data

specification mode, a subsequent query is made regarding the data representation. The user must

specify whether the file consists of bits stored in ASCII format or hexadecimal strings stored in

binary format.

114
[0] BITS IN ASCII FORMAT [1] HEX DIGITS IN BINARY FORMAT

Select input mode: 0

Since the data consists of a long sequence of zeroes and ones, 0 was chosen. Given all necessary

input parameters the test suite proceeds to analyze the sequences.

Statistical Testing In Progress

During the execution of the statistical tests, two log files located under the rng/ directory are updated. One file is the stats file, the other is the grid file. The former contains the distribution

of zeroes and ones for each binary sequence, whereas the latter contains a binary matrix of

values corresponding to whether or not sequence / passed statistical test j. Once the testing

process is complete, the empirical results can be found in the experiments/ subdirectory.

Stafisfical Testing Complete! !!!!!!!!!!!

Upon completion, an in-depth analysis is performed utilizing a MATLAB^' script written to simplify the analysis of empirical results. Two types of analyses are conducted. One type

examines the proportion of sequences that pass a statistical test. The other type examines the

distribution of the P-values for each statistical test. More details are supplied in the Section 4.2.

5.7 Interpretation of Results

An analytical routine has been included to facilitate interpretation of the results. A file finalAnalysisReport is generated when stafistical tesfing is complete. The report contains a summary of empirical results. The results are represented via a table with p rows and q columns.

The number of rows, p, corresponds to the number of statistical tests applied. The number of

columns, ^ = 13, are distributed as follows: columns 1-10 correspond to the frequency of Pvalues^^, column 1 1 is the P-value that arises via the application of a chi-square test'\ column 12

is the proportion of binary sequences that passed, and the 13*^ column is the corresponding

statistical test. An example is shown in Figure 6.

See Section 1.2, Definitions and Abbreviations.

The unit interval has been divided into ten discrete bins.

I n order to assess the uniformity of P-values in the i* statistical test.

115
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES

CI C2 C3 C4 C5 C6 C7 C8 C9 CIO P -VALUE PROPORTION STATISTICAL TEST

6 12 9 12 8 7 8 12 15 11 0 . 616305 0.9900 Frequency

11 11 12 6 10 9 8 9 17 7 0 .474986 0.9900 Cusum

6 10 8 14 16 10 10 6 5 15 0 . 129620 0.9900 Cusum

7 9 9 11 11 11 8 12 12 10 0 . 978072 0 . 9900 Serial

13 6 13 15 9 7 3 11 13 10 0 .171867 0 . 9600 Serial

The minimum pass rate for each statistical test with the exception of the random

excursion (variant) test is approximately = 0.960150 for a sample

size = 100 binary sequences.

For further guidelines construct a probability table using the MAPLE program

provided in the addendiim section of the documentation.

Figure 6: Depiction of the Final Analysis Report

116
APPENDIX A: RANK COMPUTATION FOR BINARY MATRICES

Apply elementary row operations where the addition operator is taken to be the exclusive-OR

operation. The matrices are reduced to upper triangular form using forward row operations, and

the operation is repeated in reverse in order using backward row operations in order to arrive at a matrix in diagonal form. The rank is then taken to be the number of nonzero rows in the

resulting Gaussian reduced matrix.

Forward Application of Elementary Row Operations:

Let each element in the w by w matrix be designated as a,,;

1. Set/=1

•th 2. If element a, , = 0 (i.e., the element on the diagonal ?t 1), then swap all elements in the i row with all elements in the next row that contains a one in the i* column (i.e., this row is the k* row, where i <k<m) . If no row contains a "1" in this position, go to step 4.

3. If element a, , = 1 , then if any subsequent row contains a "1" in the i* column, replace

each element in that row with the exclusive-OR of that element and the corresponding

element in the i* row.

a. Set row = i + 1 b. Set col=i.

c. If arow.coi = 0, then go to step 3g.

^- ^row,col ~ ^row,col ® ^(,co/

e. If col=m, then go to step 3g.

f. co/=co/+ 7; go to step 3d.

g. If row = m, then go to step 4. h. row=row+r, go to step 3b.

4. If i<m-}, then i=i+r, go to step 2.

5. Forward row operations completed.

Backward Application of Elementary Row Operations :

1. Set /=/M.

117
2. If element a^j = 0 (i.e., the element on the diagonal ^ 1), then swap all elements in the i^ row with all elements in the next row that contains a one in the i^^ column (i.e., this row is the row, where 1 < k< i) . If no row contains a "1" in this position, go to step 4.

3. If element a, , = 1 , then if any preceding row contains a "1" in the i* column, replace

each element in that row with the exclusive-OR of that element and the corresponding

element in the i*row.

a. Set row = i -

b. Set col=i.

c. Ifcirow.coi = 0, then go to step 3g.

d. ^row,col ^row,col ® ^i,col

e. If coH J, then go to step 3g,

f. col^col - 7; go to step 3d.

g- If row = 1, then go to step 4. h. row^row-1; go to step 3b.

4. If i>2, then and go to step 2.

5. Backward row operation complete.

6. The rank of the matrix = the number of non-zero rows.

Example of Forward Row Operations :

A

100000

00000 1 10000 1 10 10 10

001011

0000 10

The original matrix.

B

100000

00000 1 00000 1 001010

001011

0000 10

Since ajj = 7 and rows 3 and 4 contain a 1 in the first column (see the

original matrix), rows 3 and 4 are replaced by the exclusive-OR of that

row and row 1

.

C

100000

00000 1 00000 1 001010

001011

Since ajj ^ 7 and no other row contains a "1" in this column (see B),

the matrix is not altered.

118
0000 1 0

D

100000

00000 1 001010

00000 1 001011

0000 10

Since asj ^ I, but the 4* row contains a "1" in the 3'^* column (see B or

C), the two rows are switched.

E

100000

00000 1 001010

00000 1 00000 1 0000 10

Since row 5 contains a "1" in the 3"^ column (see D), row 5 is replaced

by the exclusive-OR of row 1 and row 5.

F

100000

00000 1 001010

00000 1 00000 1 0000 10

Since a4j^ 1 and no other row contains a "1" in this column (see E),

the matrix is not altered.

G

100000

00000 1 001010

00000 1 0000 10

00000 1

Since asj^ 1, but row 6 contains a 1 in column 5 (see F), the two rows

are switched. Since no row below this contains a "1" in the 5 column,

the end of the forward process is complete.

The Subsequent Backward Row Operations:

H

100000

000000

001010

000000

0000 10

00000 1

Since a6,6 = J and rows 2 and 4 contain ones in the 6 column (see G), rows 2 and 4 are replaced by the exclusive-OR of that row and row 6.

I

100000

000000

00 1000

000000

0000 10

00000 1

Since asj = 7and row 3 contains a one in the 5* column (see H), row 3

is replaced by the exclusive-OR or row 3 and row 5.

119
J

100000

000000

00 1000

000000

0000 10

00000 1

Since a^j^ 1 and no other row has a one in column 4, the matrix is not

altered.

K

100000

000000

00 1000

000000

0000 10

00000 1

Since as, 3 = 1, but no other row has a one in column 3, the matrix is not

altered.

L

100000

000000

00 1000

000000

0000 10

00000 1

Since a2,2'^ 1 and no other row has a one in column 2, the matrix is not

altered, and he process is complete.

Since the final form of the matrix has 4 non-zero rows, the rank of the matrix is 4.

120
APPENDIX B: SOURCE CODE

Filename: defs.h

Debugging Aides:

1. #define FREQUENCY 1 2. #define BLOCK_FREQUENCY 1 3. #define CUSUM 1 4. #define RUNS 1 5. #define LONG_RUNS 1 6. #define RANK 1 7. #define MATRICES 0

8. #define DFT 1 9. #define APERIODIC_TEMPLATES 1 10. #define PERIODIC_TEMPLATES 1 11. #define UNIVERSAL 1 12. #defineAPEN 1 13. #define SERIAL 1 14. #define RANDOM_EXCURSIONS 1 15. #defineRANDOM_EXCURSIONS_VARL\NT 1 16. #define LEMPEL_ZIV 1 17. #define LINEAR_COMPLEXITY 1 18. #define DISPLAY_OUTPUT_CHANNELS 1 19. #define PARTITION 0

Note: For debugging purposes, switches were introduced to display/not display intermediate

computations for each statistical test. A one denotes true, i.e., show intermediate results; a zero denotes false, i.e., do not show intermediate results.

Filename: defs.h

Statistical Testing Alternatives:

1. #define INCLUDE_GENERATORS 1 2. #define L0NG_RUNS_CASE_8 0

3. #define LONG_RUNS_CASE_128 0

4. #define LONG_RUNS_CASE_10000 1

5. #define SAVE_FFT_PARAMETERS 0

6. #define SAVE_APEN_PARAMETERS 0

7. #define SAVE_RANDOM_EXCURSION_PARAMETERS 1

8. #defme SEQ_LENGTH_STEP_INCREMENTS 5000

Note: Statistical testing alternatives have been incorporated into the test suite using switches.

Line 1 refers to the inclusion (or exclusion) of the pseudo-random number generators contained

in the NIST test suite during compilation. The ability to enable or disable this function was

121
introduced under the realization that underlying libraries may not port easily to different

platforms. The user can disable the sample generators and should be able to compile the

statistical tests.

Lines 2-4 refer to different probability values that have been included in the Long Runs of Ones

Test. Since the statistical test partitions a sequence into sub-strings of varying length, the user has the freedom to select between several cases. The user should enable only one case and

disable the other two cases.

Lines 5-7 refer to the ability to store intermediate parameter values to a file for the sake of

constructing graphics. Line 5 will enable or disable the storage of the Fourier points and

corresponding moduli into the files, fourierPoints and magnitude, respectively. Line 6 will

enable or disable the storage of the sequence length and approximate entropy value for varying

sequence lengths into the files, abscissaValues and ordinateValues. Line 7 will enable or disable

the storage of the number of cycles for each binary sequence into the file, cyclelnfo.

Line 8 refers to the number of sequence length step increments to be taken during the generation

and storage of the approximate entropy values in the file, ordinateValues.

Filename: defs.h

Global Constants:

1. #defme ALPHA 0.01

2. #defme MAXNUMOFTEMPLATES 148

3. #defme NUMOFTESTS 16

4. #defmeNUMOFGENERATORS 9

5. #defme MAXNUMBEROFCYCLES 40000

6. #defme MAXFILESPERMITTEDFORPARTITION 400

Lines 1-6 correspond to test suite parameters that have been preset. Under various conditions,

the user may decide to modify them.

Line 1 refers to the significance level. It is recommended that the user select the level in the

range [0.001,0.01].

Line 2 refers to the maximum number of templates that may be used in the Nonoverlapping

Template Matching test.

Line 3 refers to the maximum number of tests that is supported in the test suite. If the user adds

additional tests, this parameter should be incremented.

Line 4 refers to the maximum number of generators that is supported in the package. If the user adds additional generators, this parameter should be incremented.

122
Line 5 refers to the maximum number of expected cycles in the random excursions test. If this

number is insufficient, the user may increase the parameter appropriately.

Line 6 refers to the maximum number of files which may be decomposed by the

partitionResultFile routine. This routine is applied only for specific tests where more than one

P-value is produced per sequence. This routine decomposes the corresponding results file into

separate files, dataOOl, dataOOl, dataOOS, ...

123
APPENDIX C: EMPIRICAL RESULTS FOR SAMPLE DATA

The user is urged to validate that the statistical test suite is operating properly. For this reason,

five sample files have been provided. These five files are: (1) data.pi, (2) data.e,

(3) data.shal, (4) data.sqrt2, and (5) data.sqrtS. For each data file, all of the statistical tests were applied, and the results recorded in the following tables. The Block Frequency, Long Runs

of Ones, Non-overlapping Template Matching, Overlapping Template Matching, Universal,

Approximate Entropy, Linear Complexity and Serial tests require user prescribed input

parameters. The exact values used in these examples has been included in parenthesis beside

the name of the statistical test. In the case of the random excursions and random excursions

variant tests, only one of the possible 8 and 1 8 P-values, respectively, has been reported.

Example #1: The binary expansion ofn

Statistical Test P-value

Frequency 0.578211

Block Frequency (w = 100) 0.014444

Cusum-Forward 0.628308

Cusum-Reverse 0.663369

Runs 0.419268

Long Runs of Ones (M = 10000) 0.024390

Rank 0.083553

Spectral DFT 0.012947

Non-overlapping Templates (m ^ 9, B = 000000001) 0.165757

Overlapping Templates (m = 9) 0.296897

Universal (L = 7, Q = 1280) 0.669012

Approximate Entropy {m = 5) 0.634457

Random Excursions (x = +7) 0.844143

Random Excursions Variant {x = -1) 0.760966

Lempel Ziv Complexity 0.311714

Linear Complexity (M = 500) 0.255475

Serial (w = 5, V^l) 0.583812

124
Example #2: The binary expansion ofe

Statistical Test P-value

Frequency 0.953749

Block Frequency (m = yc/O) 0.619340

Cusiim-Forward 0.669887

Cusum-Reverse

Runs 0.561917

Long Runs or Ones (M - 10000) 0.718945

Rank 0.306156

Spectral DFT 0.443864

NonOverlapping Templates {m = 9, B ^ 000000001) 0.078790

Overlapping Templates {m = 9) 0.1 10434

Umversal (L = 7, ^ = y2(56>) 0.282568

Approximate Entropy (m = 5) 0.361688

Random Excursions (x = +1) 0.778616

Random Excursions Variant (x = -1) 0.826009

Lempel Ziv Complexity 0.000322

Linear Complexity (M = 500) 0.826335

Serial = 5, V^^) 0.225783

Example #3: A G-SHA-1 binary sequence

Statistical Test P-value

Frequency 0.604458

Block Frequency (m = 100) 0.833026

Cusum-Forward 0.451231

Cusum-Reverse 0.550134

Runs 0.309757

Long Runs of Ones (M = 10000) 0.657812

Rank 0.577829

Spectral DFT 0.086702

NonOverlapping Templates (m = 9, B = 000000001) 0.496601

Overlapping Templates (m = 9) 0.339426

Universal (L = 7, Q = 1280) 0.411079

Approximate Entropy (m = 5) 0.731449

Random Excursions (x = +1) 0.000000

Random Excursions Variant (x ^ -1) 0.000000

Lempel Ziv Complexity 0.398475

Linear Complexity (M = 500) 0.309412

Serial (m = 5, V^'j 0.742275

125
Example U4: The binary expansion of yf2

Statistical Test P-value

Frequency 0.811881

Block Frequency (m = 100) 0.289410

Cusum-Forward 0.879009

Cusum-Reverse 0.957206

Runs 0.313427

Long Runs of Ones (M - 10000) 0.012117

Rank 0.823810

Spectral DFT 0261 MA

NonOverlapping Templates {m = 9,B^ 000000001) 0.569461

Overlapping Templates (m ^ 9) 0.791982

Universal {L = 7,Q = 1280) 0.130805

Approximate Entropy (m = 5) 0.853227

Random Excursions {x = +1) 0.216235

Random Excursions Variant (x = -7) 0.566118

Lempel Ziv Complexity 0.949310

Linear Complexity (M = 500) 0.317127

Serial (m = 5, V^'

)

0.873914

Example #5; The binary expansion of 41

Statistical Test P-value

Frequency 0.610051

Block Frequency {m = 100) 0.573925

Cusum-Forward 0.917121

Cusum-Reverse 0.689519

Runs 0.261123

Long Runs of Ones (M = 10000) 0.446726

Rank 0.314498

Spectral DFT 0.463412

NonOverlapping Templates {m = 9, B = 000000001) 0.532235

Overlapping Templates {m = 9) 0.082716

Universal (L = 7, Q = 1280) 0.165981

Approximate Entropy {m = 5) 0.404616

Random Excursions (x = +1) 0.783283

Random Excursions Variant (x = -7) 0.155066

Lempel Ziv Complexity 0.989651

Linear Complexity (M = 500) 0.346469

Serial (m = 5, V^^) 0.100780

126
APPENDIX D: CONSTRUCTION OF APERIODIC TEMPLATES

For the purposes of executing the Non-overlapping Template Matching statistical test, all 2'" mbit binary sequences which are aperiodic were pre-computed. These templates, or patterns, were

stored in a file for m = 2 to m = 21. The ANSI-C program utilized in finding these templates is provided below. By modifying the parameter M, the template library corresponding to the

template can be constructed. This parameter value should not exceed B, since the dec2bin

conversion routine will not operate correctly. Conceivably, this source code can be easily

modified to construct arbitrary 2"^ m-bit binary sequences for larger m.

#include <stdio.h>

#include <math.h>

#define B 32

#define M 6

int *A;

static long nonPeriodic;

unsigned displayBits (FILE* , long, long)

int main (

)

{

FILE *fpl, *fp2;

long i, j, count, num;

A = (unsigned*) calloc (B, sizeof (unsigned) )

fpl = fopen( "template" , "w" )

fp2 = fopen( "datalnfo" , "a");

num = pow ( 2 , M)

count = log (num) /log (2 )

nonPeriodic = 0

ford = 1; i < num; i + +) displayBits ( fpl , i,count);

fprintf (fp2 , "M = %d\n", M)

fprintf (fp2, "# of nonperiodic templates = %u\n"

nonPeriodic)

fprintf (fp2 , "# of all possible templates = %u\n" , num)

fprintf (fp2 ," {# nonperiodic} / {# templates} = %f \n"

(double) nonPeriodic/num)

fprintf (fp2, "==========================================

fprintf (fp2 , " ===============\n" )

f close ( fpl)

f close ( fp2 )

free (A)

return 0

void displayBits (FILE* fp, long value, long count)

{

int i, j, match, c, displayMask =1 « (B-1)

127
for(c = 1; c <= B; C++) { _ if (value & displayMask) for(i =0; 1 < B; l++j A[i] = 0;

A[c-1] = 1;

else

A[c-1] = 0;

value <<= 1;

}

for(i =1; i < count; i++) {

match = 1;

if ( (A[B-count] ! = A[B-1]) &&

( (A[B-count] != A[B-2] )

I I (A[B-count + l] !=A[B-1]))) {

for(c = B-count; c <= (B-l)-i; C++) {

if (A[c] != A[c+i] ) {

match = 0

break;

}

}

}

if (match) {

/* printf ( " \nPERIODIC TEMPLATE: SHIFT = %d\n",i); */

break;

}

}

if (Imatch) {

for(c = B-count; c < (B-1); C++) fprintf (fp, "%u" , A[c] )

fprintf (fp, "%u\n" , A[B-1] )

nonPeriodic++

}

return;

128
APPENDIX E: GENERATION OF THE BINARY EXPANSION OF

IRRATIONAL NUMBERS

The sample Mathematica program utilized in constructing four sample files is shown below.

Mathematica Program **********************************************************

* Purpose: Converts num to its decimal expansion using *

* its binary representation. *

* *

* Caution: The $MaxPrecision variable must be set to *

* the value of d. By default, Mathematica *

* sets this to 50000, but this can be increased.* **********************************************************

BinExp [num_, d_] := Module [ {n, L}

If[d > $MaxPrecision, $MaxPrecision = d]

n = N [num, d] ; L = First [RealDigits [n, 2]

] ; SE = BinExp [E, 302500] ; Save [ "data.e" , {SE} ]

SP = BinExp [Pi, 302500]

Save [ "data. pi" , {SP} ]

S2 = BinExp [Sqrt [2] , 302500]

Save [ " data . sqrt2 " , { S2 } ]

S3 = BinExp [Sqrt [3] , 302500]

Save [ " data . sqrt3 " , { S3 } ] ;

129
APPENDIX F: NUMERIC ALGORITHM ISSUES

For each binary sequence, an individual statistical test must produce at least one P-value.

P-values are based on the evaluation of special functions, which must be as accurate as possible

on the target platform. The log files produced by each statistical test, report P-values with six

digits of precision, which should be sufficient. However, if greater precision is desired, modify

the printfstatements in each statistical test accordingly.

During the testing phase, NIST commonly evaluated sequences on the order 10^; hence, results are based on this assumption. If the user wishes to choose longer sequence lengths, then be aware that numerical computations may be inaccurate'"* due to machine or algorithmic

limitations. For further information on numerical analysis matters, see [6]'^.

For the purposes of illustration, sample parameter values and corresponding special function

values are shown in Table F.l and Table F.2. Table F.l compares the results for the incomplete

gamma function for selected parameter values for a and x. The results are shown for Maple

Matlab'*^, and the Numerical Recipe'^ routines. Recall that the definitions for the gamma

function and the incomplete gammafunction are defined, respectively, as:

Since the algorithm used in the test suite implementation of the incomplete gammafunction is based on the numerical recipe codes, it is evident that the function is accurate to at least the

seventh decimal place. For large values of a, the precision will degrade, as will confidence in the

result (unless a computer algebra system is employed to ensure high precision computations).

Table F.2 compares the results for the complementary errorfunction (see Section 5.3.3) for

selected parameter values for jc. The results are shown for ANSI C, Maple, and Matlab. Recall

that the definition for the complementary errorfunction is:

According to the contents of the GNU C specifications at ''lusr/local/lib/gcc-lib/sparc-sun- solaris2. 5. 1/2.7.2. 3/specs (gcc version 2.7.2.3)," the limits. h header file on a SUN Ultra 1 workstation, the maximum number of digits of precision of a double is 15. Visit http://www.ulib.org/webRoot/Books/Numerical Recipes/ or http://beta.ul.cs.cmu.edu/webRoot/

Books/Numerical Recipes/, particularly. Section 1.3 (Error, Accuracy, and Stability).

See Section 1.2, Definitions and Abbreviations.

The parameter values for eps and itmax were fixed at 3x10"'^ and 2,000,000 respectively. Special function routines based on Numerical Recipe codes will be replaced by non-proprietary codes in the near future.

r(2) = r? e 'dt

where Q(a,0) = 1 and Q(a,oo) 0.

130
Table F.l: Selected Input Parameters for the Incomplete Gamma Function

a = X = 600 Q(a,x) a = x = 800 Q(a,x)

Maple

Test Suite

0.4945710333

nU.tr/tJ 4Q4S71/ I O^^l \JDJ I 0.4945710331

Maple

iVlallaU

Test Suite

0.4952983876

\j .'-ry J Z.y O D O 1 \) 0.4952983876

a = x- 1000 Q(a,x) a = x= 10000 Q(a,x)

Maple

Matlab

Test Suite

0.4957947559

0.4957947558

0.4957947558

Maple

Matlab

Test Suite

0.4986701918

0.4986701917

0.4986701917

a-x= 100000 Q(a,x) a = x- 1000000 Q(a.x)

Maple

Matlab

Test Suite

0.4995794779

0.4995794779

0.4995794778

Maple

Matlab

Test Suite

0.4998670192

0.4998670196

0.4998670205

Table F.2: Selected Input Parameters for the Complementary Error Function

X erfc(x) X erfc(x)

0.00 Test Suite

Maple

Matlab

1.000000000000000

1.000000000000000

1.000000000000000

0.50 Test Suite

Maple

Matlab

0.479500122186953

0.479500122186950

0.479500122186953

1.00 Test Suite

Maple

Matlab

0.157299207050285

0.157299207050280

0.157299207050285

1.50 Test Suite

Maple

Matlab

0.033894853524689

0.033894853524690

0.033894853524689

2.00 Test Suite

Maple

Matlab

0.004677734981047

0.004677734981050

0.004677734981047

2.50 Test Suite

Maple

Matlab

0.000406952017445

0.000406952017440

0.000406952017445

3.00 Test Suite

Maple

Matlab

0.000022090496999

0.000022090497000

0.000022090496999

3.50 Test Suite

Maple

Matlab

0.000000743098372

0.000000743098370

0.000000743098372

Thus, it is evident that the various math routines produce results that are sufficiently close to each other. The differences are negligible. To reduce the likelihood for obtaining an inaccurate

P-value result, NIST has prescribed recommended input parameters.

131
APPENDIX G: HIERARCHICAL DIRECTORY STRUCTURE

rng/

makefile

makefile!

assess

The NIST Statistical Test Suite makefile. This file is invoked in order to recompile the entire test suite, including PRNGs.

The NIST Statistical Test Suite makefile. This file is invoked in order to recompile the NIST test suite without the PRNGs (Note: the PRNGs may

not compile on all platforms without user intervention).

The NIST Statistical Test Suite executable file is called assess.

data/ This subdirectory contains the names of all data files to be analyzed.

Sample files include the binary expansions to well known constants such

as e,%, V2 , andVi .

experiments/ This subdirectory contains the empirical result subdirectories for each

RNG.

AlgorithmTesting/

CCG/

LCG/

MS/

QCG2/

BBS/

G-SHA-1/

MODEXP/

QCGl/

XOR/

For each subdirectory there is a set of nested directories, that is.

apen/

cumulative-sums/

frequency/

linear-complexity/

nonperiodic-templates/

random-excursions/

rank/

serial/

block-frequency/

mi

lempel-ziv / longest-run/

overlapping-templates/

random-excursions-variant/

runs/

universal/

For each nested directory there are two files created upon execution of an

individual statistical test. The results file contains a P-value list for each

binary sequence, and the stats file contains a list of statistical information

for each binary sequence.

generators/ This subdirectory contains the source code for each PRNG. In the

132
event that the user is interested in evaluating their PRNG (onHne), their source code may, for example, be added as generators4.c in this directory,

with additional changes made in the utilities2. c file and the defs.h file,

generators l.c: contains BBS, MS, LCG

generators2.c: contains ModExp, QCGl, QCG2, CCGl, XOR

generators3.c: contains G-SHA-1

sha.c : contains routines required by the G-SHA-1 PRNG.

grid This file contains bits which represent the acceptance or rejection of a

particular sequence for each individual statistical test that is run. The Pvalue computed for the sequence is compared to the chosen significance

level a.

include/ This subdirectory contains all of the header files that prescribe

any global variables, constants, and data structures utilized in the

reference implementation. In addition, the subdirectory contains all function declarations and prototypes.

cephes-protos.h config.h

config2.h defs.h

f2c.h generators l.h

generators2.h generatorsS .h globals.h lip.h

lippar.h matrix.h

mconfig.h mp.h

proto.h sha.h

special-fiinctions.h utilities 1 .h utilities2.h

obj/ This subdirectory contains the object files corresponding to the source codes.

approximateEntropy. o

cephes.o

dfft.o

frequency.o

generators 1.0

generatorsS.

linearComplexity.o

matrix, o nonOverlappingTemplateMatchings.o

overlappingTemplateMatchings.o

randomExcursions.o randomExcursionsVariant.o

rank.o runs.o

sha.o special-functions.o

assess.o cusum.o

discreteFourierTransform.o

functions.o

generators2.o

lempelZivCompression.o

lip.o

mp.o

133
universal.o

src/

utilities 1.0 utilities2.o

stats

This subdirectory contains the source codes for the statistical tests.

assess.c

dfft.c

cephes.c

lip.c

matrix.c

mp.c

special-functions.c

frequency,c blockFrequency.c cusum.c

The driver program for this package

The discrete fourier fransform routine

Defines the incomplete gamma function

Long integer precision library utilized by

Pate Williams implementation of the

Blum-Blum-Shub and Micali-Schnorr

source codes

Source code for the determination of rank

for binary matrices

Multiprecision integer package

Numerical routines for the handling of

special functions

Frequency Test

Block Frequency Test

Cumulative Sums Test

Runs Test

Longest Run Of Ones Test

Rank Test

runs.c longestRunOfOnes.c

rank.c

discreteFourierTransform.c

: Spectral Test

nonOverlappingTemplateMatchings.c

: Nonoverlapping Template Matchings Test

OverlappingTemplateMatchings.c

: Overlapping Template Matchings Test

universale : Universal Test

approximateEntropy.c: Approximate Entropy Test

randomExcursions.c : Random Excursions Test

randomExcursionsVariant.c

: Random Excursions Variant Test

serial. c : Serial Test

lempelZivComplexity.c

Lempel-Ziv Complexity Test

Linear Complexity Test

Serial Test

Utility fiinctions...

Utility functions...

linearComplexity.c

serial.

c

utilities l.c utilities2.c

This file contains the frequency distributions for individual

sequences.

templates/ Non-Periodic Template Library:

134
This subdirectory contains the templates (or patterns) which are evaluated

in the NonOverlapping Template Matching Test. The corresponding file

is opened for the prescribed template block length m. Currently, the only

options for which nonperiodic templates have been stored are those which

lie in [2,2 1]. In the event that m> 21, the user must pre-compute the

non-periodic templates.

template2

template?

template 12

template 17

templates

templates

template 13

template 18

template4

template9

template 14

template 19

templates

template 10

template 15

template20

template6

template 1

template 16

template21

135
APPENDIX H: VISUALIZATION APPROACHES

There are several visualization approaches that may be used to investigate the randomness of

binary sequences. Three techniques involve the Discrete Fourier Transform, approximate

entropy and the linear complexity profile.

(a) Spectral - Discrete Fourier Transform (DFT) Plot

Figure H.l depicts the spectral components (i.e., the modulus of the DFT) obtained via

application of the Fast Fourier Transform on a binary sequence (consisting of 5000 bits)

1 ft extracted fi-om the Blum-Blum-Shub pseudo-random number generator . To demonstrate how

the spectral test can detect periodic features in the binary sequence, every 10* bit was changed to a single one. To pass this test, no more than 5 % of the peaks should surpass the 95 % cutoff,

(determined to be sqrt(3 *5000) = 1 22.474487 1 ). Clearly, greater than 5 % of the peaks exceed

the cutoff point in the figure. Thus, the binary sequence fails this test.

600

500 -

400 -

2500

Figure H.l; Discrete Fourier Transform Plot

The Blum-Blum-Shub pseudo random number generator, based on the intractability of the quadratic residuocity

problem is described in the Handbook of Applied Cryptography, by Menezes, et. al.

136
(b) Approximate Entropy (ApEn) Graph

Figure H.2 depicts the approximate entropy values (for block length = 2) for three binary

sequences, the binary expansion of e and tc, and a binary sequence taken from the SHA-1

pseudo-random number generator. In theory, for an w-bit sequence, the maximum entropy value

that can be attained is In (2) ~ 0.69314718. The x-axis reflects the number of bits considered in

the sequence. The y-axis reflects the deficit from maximal irregularity, that is, the difference

between the In (2) and the observed approximate entropy value. Thus, for a fixed sequence

length, one can determine which sequence appears to be more random. For a sequence of

1,000,000 bits, e appears more random than both n and the SHA-1 *^ sequence. However, for

larger block sizes, this is not the case.

Sequence Length ^lO^

Figure H.2: Approximate Entropy Graph

It is worth noting that, for larger block sizes and sequence lengths on the 0(10 ), SHA-1

binary sequences yield deficit values on the 0(10'^).

137
(c) Linear Complexity Profile

Figure H.3 depicts the linear complexity profile for a pseudo-random number generator that is strictly based on the XOR (exclusive-or) operator. The generator is defined as follows: given a random binary seed, ;c, , ,

• • • , x,27 , subsequent bits in the sequence are generated according to

the rule, x, = ® x._i2-j for i > 128.

The Berlekamp-Massey algorithm computes the connection polynomial that, for some seed

value, reconstructs the finite sequence. The degree of this polynomial corresponds to the length

of the shortest Linear Feedback Shift Register (LFSR) that represents the polynomial. The linear

complexity profile depicts the degree, which for a random finite length (n-bit) sequence is about

n/2. Thus, the x-axis reflects the number of bits observed in the sequence thus far. The y-axis

depicts the degree of the connection polynomial. Atn = 254, observe that the degree of the

polynomial ceases to increase and remains constant at 127. This value precisely corresponds to the number of bits in the seed used to construct the sequence.

Linear Complexity Profile for the XOR PRNG

0 lii 1 I I I I I I 1 1 0 50 100 150 200 250 300 350 400 450 500 Sequence Length

Figure H.3; Linear Complexity Profile

For a description of the algorithm see Chapter 6 - Stream Ciphers, which may be accessed at http://www.cacr.math.uwaterloo.ca/hac/

138
APPENDIX I: INSTRUCTIONS FOR INCORPORATING ADDITIONAL

STATISTICAL TESTS

In order to add another statistical test to the test suite, the user should make the following

modifications:

1 . [In the file include/defs. h]

Insert any test input parameters into the testParameters structure. Increment the value

of NUMOFTESTS by the number of tests to be added.

2. [In the file include/proto.h]

Insert the statistical test function prototype declaration.

3. [In the file srdutilitiesl.c\

Embed the test function call into the nist_test_suite function. For example, if the

current number of tests is 1 6, and one test is to be added, insert the following code:

if ( (testVector [0] ==1) || ( testVector [17] == 1))

myNewTest ( tp .myNewTestlnputParameters , tp.n)

4. [In the file srdmyNewTest.c]

Define the statistical test function. Note: The programmer should embed fprintf

statements using stats[x\, and results[x\ as the corresponding output channel for writing

intermediate test statistic parameters and P-values, respectively, x is the total number of

tests.

5. [In the file srdutilities2.c]

(a) hi the function, openOutputStreams, insert the string, "myNewTesf into the

testNames variable. In the function, chooseTests, insert the following lines of code (as

modified by the actual number of total tests):

printf ("\t\t\t 12345678911111111\n" )

printf ("\t\t\t 01234567\n" )

Note: For each PRNG defined in the package, a sub-directory myNewTest must be

created.

(b) In the function, displayTests, insert a printf statement. For example, if the total number of tests is 17, insert

139
printfC [17] My New Test\n" ) ;

(c) If an input test parameter is required, in the function, fixParameters, insert the

following lines of code (under the assumption that myNewTestParameter is an

integer). For example, if the total number of tests is 1 7, insert

if (testVector [17] == 1) {

printf ( " \ tEnter MyNewTest Parameter Value: ");

scanf ( "%d" , &tp .myNewTestParameter )

140
APPENDIX J: INSTRUCTIONS FOR INCORPORATING ADDITIONAL

PRNGs

In order to add a PRNG to the test suite, the user should make the following modifications:

1 . [In the file include/defs. h]

hicrement the variable NUMOFGENERATORS by one.

2. [In the file mc\ude/generators4.h]

Insert the generator function prototype declaration. For example,

void myNewPRNG ( ) ;

3. [In the file generators/generators4.c]

Define the generator function. The general scheme for each PRNG defined in the test suite is as follows:

Allocate space for epsilon, the n-bit BitField array,

for i = 1 to numOfBitStreams {

Construct an n-bit sequence using myNewGenerator and

store in epsilon.

Invoke the nist_test_suite

}

Deallocate the space given to epsilon.

Note: A sub-directory called myNewPRNG/ must be created. Under this new directory, a set of sub-directories must be created for each of the test suite statistical tests. The

script createScript has been included to facilitate this operation.

4. [In the file srdutilities2.c]

(a) In the function, generatorOptions, insert the following lines of code:

case 12: *streamFile = "myNewPRNG";

break;

(b) In the function, invokeTestSuite, insert the following lines of code:

case 12 : myNewPRNG ( )

break;

(c) In the function, openOutputStreams, insert the generator string name into the

generatorDir variable. For example.

141
char generatorDir [20] [20] = { " AlgorittunTesting/ "

,

... , " XOR /

"

, " MYNEWPRNG/

" } ; Similarly, in the routine, partitionResultFile, in the file, assess.c.

142
APPENDIX K: GRAPHICAL USER INTERFACE (GUI)

K.1 Introduction

A simple Tcl/Tk graphical user interface (GUI) was developed as a front-end to the NIST

Statistical Test Suite. The source code may be found in the file, rng-gui.tcl. The interface

consists of a single window with four regions. The topmost region contains the software product

laboratory affiliation. The left half of the window consists of a checklist for the sixteen statistical

tests. The user should select or de-select the set of statistical tests to be executed.

The right half of the window is sub-divided into an upper and lower portion. The upper portion

consists of required parameters that must be provided in order to execute the tests. The lower

portion consists of test dependent parameters that must be provided only if the corresponding test has been checked.

1 A Suite of Statistical Tests Developed to Investigate Randomness in Cryptogiaphic Randonn Number Generators The National Institute of Standards and Technology (WIST)

Information Technology Laboratory (ITL)

jlU^^STICAL TEST CHECKL

Statistical Test Suite, Copyright 2000

ST REQUIRED INPUT PARAMETERS

F MonobiTest

EiAetbinayd^ttieamfis'Hffle'. | data e W BbckFtequencjiTett W Cumiatiye Sums (Cu«ufn)Teti EnUsseciuencetei^^^bitst | 1000000

17 fluwTest

Ente* rwrnbet ot s«|u»)ces: j

1

Long RtRsdOflw Test F Bank Test

I*' Disaete Fouw Ttairfofm (Sp«:tral) Te«t

Ente« «tfe«n Ofor ASQI, 1 f« 8tr»«jc

) 0

TEST DEPENDENT INPUT PARAMETERS

F KorH>veri4vir«Tenvfe>teM<tehin9sT(»t Ent«btockfiequen<9bfeick^^(inWx^ | 100 B' W Overtopping Ter^e Matehngs Test EtTJwnorvoveriipwtgteraftetelenfiShJaibits}: | 9 B W Universai Statistical Test

EiTtwovBtlappingtemplate length (in bits):

| 9 AppttJwn^EnfropjtTest

Enteurwy«Mlbtockleog»){lnbSs): ] 7

SetialTest W RwKtom Ewaiiwts Te^

Erkerixiv«s«rfntiafe«ito«tep«: | 1280

17 Random ExcmionsVadst Test Ente a«KQ>w«te8rta)|:8>bteck length fin WsJ. j 5 W Leo<jet-2iv Test Enter s«iat block Iwigthfiibls): | 5 ^ |7 Lineal eo«ti(teafy Test Ertofc»a cOT?)(e)(^sJ)strsig length fin bil# | 50C| w Execute

1 Qtit J

Figure ICl: Tcl/Tk GUI for the NIST Statistical Test Suite

Once the user has selected the statistical tests, the required input parameters, and the test dependent input parameters, then the user should depress the Execute button to invoke the

143
battery of statistical tests. This will result in the de-iconification of the GUI. Upon completion,

the GUI will re-iconify. The user should then proceed to review the file, finalAnalysisReport.txt

to assess the results.

K.2 An Example

The following table presents an example of the use of the GUI. The user has checked all sixteen

of the statistical tests and entered:

data.e as the binary date stream

filename

• P as the overlapping template block length

• a sequence length of 1000000 bits • 7 as the universal block length

• 7 as the number of binary

sequences

• 1280 as the universal initialization steps

• 0 as the stream type • 5 as the approximate entropy block length

• 100 diS the block frequency block

length

• 5 as the serial block length

• P as the nonoverlapping template

block length

• 500 as the linear complexity substring length

K.3 Guidance in tlie Selection of Parameters

Section 2 provides the recommended parameter choices for each statistical test.

K.4 Interpretation of Results

Section 4.2 contains information regarding the interpretation of empirical results.

K.5 Tcl/Tk Installation Instructions

Tcl/Tk may be obtained from the Scriptics website at http://www.scriptics.com/. Download

Tcl/Tk 8. 1 for the target platform from http://dev.scriptics.com/software/tcltk/choose.html.

144
K.6 References

[ 1 ] Brent Welch, Practical Programming in Tel and Tk, 2°'^ edition. Prentice Hall PTR, 1 997.

[2] Clif Flyntf, Tcl/Tk for Real Programmers. Academic Press, 1999.

145
APPENDIX L: DESCRIPTION OF THE REFERENCE PSEUDO RANDOM

NUMBER GENERATORS

The NIST Statistical Test Suite supplies the user with nine pseudo-random number generators.

A brief description of each pseudo-random number generator follows. The user supplied

sequence length determines the number of iterations for each generator.

L.l Linear Congruential Generator (LCG)

The input parameter for the Fishman and Moore^* LCG^^ is fixed in code but may be altered by

the user.

Input Parameter:

zo = 23482349

Description:

Given a seed zo, subsequent numbers are computed based on z/+; - a*Zi mod (2^'-l), where a is a function of the current state. These numbers are then converted to uniform values in [0,1]. At

each step, output '0' if the number is < 0.5, otherwise output ' 1

'.

L.2 Quadratic Congruential Generator I (QCG-I)

The input parameters to the QCG-I are fixed in code, but may modified by the user.

Input Parameters:

;? = 987b6a6bf2c56a97291c445409920032499f9ee7adl28301b5d0254aala9633fdbd378

d40149fl e23al 3849f3d45992f5c4c6b7 1 04099bc301 f6005f9d8 1 1 5el

xo = 3844506a9456c564b8b8538e0ccl 5aff46c95e69600f084f0657c2401b3c244734b62e

a9bb95be4923b9b7e84eeafla224894efD328d44bc3eb3e983644da3f5

^' Fishman, G. S. and L. R. Moore (1986). An exhaustive analysis of multiplicative congruential random number

generators with modulus 2**31-1, SIAM Journal on Scientific and Statistical Computation, 7, 24-45. Additional information may be found in Chapter 16 (Pseudo-Random Sequence Generators & Stream Ciphers),

Section 16.1 (Linear Congruential Generators) of Bruce Schneier's book. Applied Cryptography: Protocols,

Algorithms and Source Code in C, 2°^ edition, John Wiley & Sons, 1996.

146
Description:

Using a 512-bit prime p, and a random 512-bit seed jco, construct subsequent elements (each 512-

bit numbers) in the sequence via the rule:

^i+i - modp, for / > 0.

L.3 Quadratic Congruential Generator II (QCG-II)

The input parameter to the QCG-II is fixed in code, but may be modified by the user.

Input Parameter:

X0 = 7844506a9456c564b8b8538e0ccl5aff46c95e69600f084fD657c2401b3c244734b62e

a9bb95be4923b9b7e84eeafla224894efD328d44bc3eb3e983644da3f5

Description:

Using a 512-bit modulus, and a random 512-bit seed xo, construct subsequent elements (each

512-bit numbers) in the sequence via the rule:

Xi+] = 2xi + 3xi + 1 mod 2^^\ for / > 0.

L.4 Cubic Congruential Generator (CCG)

The input parameter to the CCG is fixed in code, but may be modified by the user.

Input Parameter:

X(7=7844506a9456c564b8b8538e0ccl5aff46c95e69600fD84fD657c2401b3c244734b62ea

9bb95be4923b9b7e84eeafla224894ef0328d44bc3eb3e983644da3f5

Description:

Given a 5 12 bit seed xq, construct subsequent 5 12-bit strings via the rule:

jc/+y = Xi mod 2^^^, for / > 0.

L.5 Exclusive OR Generator (XORG)

The input parameter to the XORG is a 127-bit , seed that is fixed in code, but may be user modified.

147
Input Parameter:

jc,,X2 ,. . .,x,27 = 000101 101 101 1001000101 1 1 100100101001 1011101 1010001000000101

01111111010100100001010110110000000000100110000101110011111111100111

Description:

Choose a bit sequence, Xi ,JC2 ,. ..,x^2i Construct subsequent bits via the rule:

X,. = x,._, © x,._i27 , for / > 128.

L.6 Modular Exponentiation Generator (MODEXPG)

The input parameters to the MODEXPG are fixed in code, but they may be user modified.

Input Parameters:

5eeJ=7AB36982CElADF832019CDFEB2393CABDF0214EC

p = 987b6a6bf2c56a9729 1 c445409920032499f9ee7ad 1 2830 Ib5d0254aal a9633fdbd378

d40149fle23al3849f3d45992f5c4c6b7104099bc301f6005f9d8115el

g = 3844506a9456c564b8b8538e0ccl5aff46c95e69600fD84fD657c2401b3c244734b62ea

9bb95be4923b9b7e84eeafla224894ef0328d44bc3eb3e983644da3f5

Description: A sequence {x,} of 512-bit pseudo-random numbers can be generated as follows:

Choose a 5 12-bit prime p, and a base g, as in the Digital Signature Standard (DSS). Choose an

arbitrary 160-bit seed;;. Let xy = g^^^"^ modp and x,+/ = g^' mod p, for / > 1 where is the

lowest-order 160 bits of x,. Splicing together the {x,} will generate an n-bit sequence.

L.7 Secure Hash Algorithm Generator (SHAIG)

The input parameters to the SHAIG are fixed in code, but may be user modified. The length of

the key, keylen should be chosen in the interval [160, 512].

Input Parameters:

seedlen = 1 60

Xseed = 237c5f791c2cfe47bfbl6d2d54a0d60665b20904

keylen - 1 60

Xkey = ec822a619d6ed5d9492218a7a4c5bl5d57c61601

148
Description:

For a detailed description of SHAIG (the FIPS 186 one-way function using SHA-1), visit

http://www.cacr.math.waterloo.ca/hac/about/chap5.pdf.ziD. especially p. 175.

L.8 Blum-Blum-Shub Generator (BBSG)

The input parameters to the BBSG are not fixed in code. They are variable parameters, which

are time dependent. The three required parameters are two primes, p and q, and a random integer

s.

Input Parameters :

Two primes p and q such that each is congruent to 3 modulo 4. A random integer s (the seed),

selected in the interval [1, pq-1] such that gcd(s,pq) = 1. The parameters p, q and s are not fixed

in code; thus, the user will not be able to reconstruct the original sequence because these values

will vary (i.e., they are dependent on the system time). To reproduce a sequence the user must

modify the code to fix the variable input parameters.

Description:

For a detailed description of the Blum-Blum-Shub pseudo-random number generator, visit

http://www.cacr.math.waterloo.ca/hac/about/chap5.pdf.zip, especiallv P. 186. Pate Williams'

ANSI C reference implementation may be located at fl:p://www.mindspring.

com/users/pate/crvpto/chap05/blumblum.c.

L.9 Micali-Schnorr Generator (MSG)

The input parameters to the MSG are not fixed in code. They are variable parameters, which are time dependent. The four required parameters are two primes, p and q, an integer e, and the seed

xo.

Input Parameters :

Two primes p and q. A parameter e, selected such that 1 <e <^ = (p-l)(q-l), gcd(e, = 1, and

80e <N^floor(Ig n + 1). A random sequence xq (the seed) consisting of r (a function ofe and

n) bits is chosen. The parameters e, p, q, and xo are not fixed in code; thus, the user will not be

able to reconstruct the original sequence because these values will vary (i.e., they are dependent on the system time). To reproduce a sequence the user must modify the code to fix the variable

input parameters.

Description:

For a detailed description of the Micali-Schnorr pseudo-random number generator, visit

http://www.cacr.math.waterloo.ca/hac/about/chap5.pdf.zip, especially p. 186. Pate Williams'

149
ANSI C reference implementation may be located at ftp ://www.mindspring.

com/users/pate/crvpto/chap05/micali. c

.

L.IO Test Results

The following table depicts test-by-test failures for the above reference generators.

Statistical Test

Excessive

Rejections

Lacks

Uniformity

Generator

Frequency X X Modular Exponentiation

X X Cubic Congruential

X X Quadratic Congruential (Type I) Block Frequency X Cubic Congruential

X X XOR

Cusum X X Micali-Schnorr

X X Modular Exponentiation

X X Cubic Congruential

X X Quadratic Congruential (Type I) Runs X Modular Exponentiation

X X Cubic Congruential

X Quadratic Congruential (Type I) Rank X X XOR

Spectral X X Cubic Congruential

X Quadratic Congruential (Type II) Aperiodic

Templates

X ANSI X9.17

X Micali-Schnorr

X Modular Exponentiation

X X Cubic Congruential

X Quadratic Congruential (Type I) X Quadratic Congruential (Type II) X X XOR

Periodic Templates X Modular Exponentiation

X X XOR

Approximate

Entropy

X X Modular Exponentiation

X X Cubic Congruential

X X Quadratic Congruential (Type I) X X XOR

Serial X X Modular Exponentiation

X X Cubic Congruential

X X Quadratic Congruential (Type I) X X XOR

Table M.l: Illustration of Rejection/Uniformity Failures

150
APPENDIX M: REFERENCES

[I] M. Abramowitz and I. Stegun, Handbook of Mathematical Functions, Applied

Mathematics Series. Vol. 55, Washington: National Bureau of Standards, 1964;

reprinted 1968 by Dover PubHcations, New York.

[2] T. Cormen, C. Leiserson, & R. Rivest, Introduction to Algorithms. Cambridge,

MA:The MIT Press, 1990.

[3] Gustafson et al., "A computer package for measuring strength of encryption

algorithms," Journal of Computers & Security. Vol. 13, No. 8, 1994, pp. 687-

697.

[4] U. Maurer, "A Universal Statistical Test for Random Bit Generators," Journal of

Cryptology. Vol. 5, No. 2, 1992, pp. 89-105.

[5] A. Menezes, et al.. Handbook of Applied Cryptography. CRC Press, Inc., 1997.

See http://www.cacr.math.uwaterloo.ca/hac/about/chap5.pdfzip.

[6] W. Press, S. Teukolsky, W. Vetterling, Numerical Recipes in C : The Art of

Scientific Computing, 2nd Edition. Cambridge University Press, January 1993.

[7] G. Marsaglia, DIEHARD Statistical Tests: http://stat.fsu.edu/~geo/diehard.html.

[8] T. Ritter, "Randomness Tests and Related Topics," http://www.io.com/~ritter/

RES/RANDTEST.HTM.

[9] American National Standards Institute: Financial Institution Key Management

(Wholesale), /American Bankers Association, ANSI X9.17 - 1985 (Reaffirmed

1991).

[ 1 0] FIPS 1 40- 1 , Security Requirements for Cryptographic Modules, Federal

Information Processing Standards Publication 140-1. U.S. Department of

Commerce/NIST, National Technical Information Service, Springfield, VA, 1994.

[II] FIPS 1 80- 1

, Secure Hash Standard, Federal Information Processing Standards

Publication 180-1. U.S. Department of Commerce/NIST, National Technical

Information Service, Springfield, VA, April 17, 1995.

[12] FIPS 1 86, Digital Signature Standard (DSS), Federal Information Processing

Standards Publication 186. U.S. Department of Commerce/NIST, National

Technical Information Service, Springfield, VA, May 19, 1994.

151
MAPLE, A Computer Algebra System (CAS). Available from Waterloo Maple Inc.; http.V/www.maplesoft.com.

152


Technical Publications

Periodical

Journal of Research of the National Institute of Standards and Technology—Reports NIST research and development in those disciplines of the physical and engineering sciences in which the Institute is active. These include physics, chemistry, engineering, mathematics, and computer sciences. Papers cover a broad range of subjects, with major emphasis on measurement methodology and the basic technology

underlying standardization. Also included from time to time are survey articles on topics closely related to the Institute's technical and scientific programs. Issued six times a year.

Nonperiodicals

Monographs—Major contributions to the technical literature on various subjects related to the

Institute's scientific and technical activities. Handbooks—Recommended codes of engineering and industrial practice (including safety codes) devel- oped in cooperation with interested industries, professional organizations, and regulatory bodies. Special Publications—Include proceedings of conferences sponsored by NIST, NIST annual reports, and

other special publications appropriate to this grouping such as wall charts, pocket cards, and bibliographies.

National Standard Reference Data Series—Provides quantitative data on the physical and chemical

properties of materials, compiled from the world's literature and critically evaluated. Developed under a worldwide program coordinated by NIST under the authority of the National Standard Data Act (Public

Law 90-396). NOTE: The Journal of Physical and Chemical Reference Data (JPCRD) is published

bimonthly for NIST by the American Chemical Society (ACS) and the American Institute of Physics (AIP).

Subscriptions, reprints, and supplements are available from ACS, 1155 Sixteenth St., NW, Washington, DC

20056.

Building Science Series—Disseminates technical information developed at the Institute on building

materials, components, systems, and whole structures. The series presents research results, test methods, and

performance criteria related to the structural and environmental functions and the durability and safety

characteristics of building elements and systems.

Technical Notes—Studies or reports which are complete in themselves but restrictive in their treatment of

a subject. Analogous to monographs but not so comprehensive in scope or definitive in treatment of the subject area. Often serve as a vehicle for final reports of work performed at NIST under the sponsorship of

other government agencies.

Voluntary Product Standards—Developed under procedures published by the Department of Commerce

in Part 10, Title 15, of the Code of Federal Regulations. The standards establish nationally recognized

requirements for products, and provide all concerned interests with a basis for common understanding of

the characteristics of the products. NIST administers this program in support of the efforts of private-sector

standardizing organizations.

Order the following NIST publications—FIPS and NISTIRs—from the National Technical Information

Service, Springfield, VA 22161.

Federal Information Processing Standards Publications (FIPS PUB)—Publications in this series collectively constitute the Federal Information Processing Standards Register. The Register serves as the

official source of information in the Federal Government regarding standards issued by NIST pursuant to the Federal Property and Administrative Services Act of 1949 as amended, Public Law 89-306 (79 Stat.

1 127), and as implemented by Executive Order 1 1717 (38 FR 12315, dated May 11, 1973) and Part 6 of

Title 15 CFR (Code of Federal Regulations).

NIST Interagency or Internal Reports (NISTIR)—The series includes interim or final reports on work

performed by NIST for outside sponsors (both government and nongovernment). In general, initial distribution is handled by the sponsor; public distribution is handled by sales through the National Technical

Information Service, Springfield, VA 22161, in hard copy, electronic media, or microfiche form. NISTIR's

may also report results of NIST projects of transitory or limited interest, including those that will be

published subsequently in more comprehensive form.
wc 3 2-

00 o o00VO

05 • a. c/3 o • — rti 5 » I 9 o 5.Oo33nn