This is a Chapter from the Handbook of Applied Cryptography, by A. Menezes, P. van
`Oorschot, and S. Vanstone, CRC Press, 1996.
`For further information, see www.cacr.math.uwaterloo.ca/hac
`
`CRC Press has granted the following speci(cid:12)c permissions for the electronic version of this
`book:
`
`Permission is granted to retrieve, print and store a single copy of this chapter for
`personal use. This permission does not extend to binding multiple chapters of
`the book, photocopying or producing copies for other than personal use of the
`person creating the copy, or making electronic copies available for retrieval by
`others without prior permission in writing from CRC Press.
`
`Except where over-ridden by the speci(cid:12)c permission above, the standard copyright notice
`from CRC Press applies to this electronic version:
`
`Neither this book nor any part may be reproduced or transmitted in any form or
`by any means, electronic or mechanical, including photocopying, micro(cid:12)lming,
`and recording, or by any information storage or retrieval system, without prior
`permission in writing from the publisher.
`
`The consent of CRC Press does not extend to copying for general distribution,
`for promotion, for creating new works, or for resale. Speci(cid:12)c permission must be
`obtained in writing from CRC Press for such copying.
`
`c(cid:13)1997 by CRC Press, Inc.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, Cover
`
`

`
`Chapter 
`
`PseudorandomBitsandSequences
`
`Contents in Brief
`
`Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 169
`5.1
`5.2 Random bit generation : : : : : : : : : : : : : : : : : : : : : : : 171
`Pseudorandom bit generation : : : : : : : : : : : : : : : : : : : : 173
`5.3
`: : : : : : : : : : : : : : : : : : : : : : : : : : : 175
`5.4
`Statistical tests
`5.5 Cryptographically secure pseudorandom bit generation : : : : : : 185
`5.6 Notes and further references : : : : : : : : : : : : : : : : : : : : 187
`
`5.1 Introduction
`
`The security of many cryptographic systems depends upon the generation of unpredictable
`quantities. Examples include the keystream in the one-time pad (x1.5.4), the secret key in
`the DES encryption algorithm (x7.4.2), the primes p; q in the RSA encryption (x8.2) and
`digital signature (x11.3.1) schemes, the private key a in the DSA (x11.5.1), and the chal-
`lenges used in challenge-response identification systems (x10.3). In all these cases, the
`quantities generated must be of sufficient size and be “random” in the sense that the proba-
`bility of any particular value being selected must be sufficiently small to preclude an adver-
`sary from gaining advantage through optimizing a search strategy based on such probability.
`For example, the key space for DES has size 256. If a secret key k were selected using a
`true random generator, an adversary would on average have to try 255 possible keys before
`guessing the correct key k. If, on the other hand, a key k were selected by first choosing a
`16-bit random secret s, and then expanding it into a 56-bit key k using a complicated but
`publicly known function f, the adversary would on average only need to try 215 possible
`keys (obtained by running every possible value for s through the function f).
`This chapter considers techniques for the generation of random and pseudorandom
`bits and numbers. Related techniques for pseudorandom bit generation that are generally
`discussed in the literature in the context of stream ciphers, including linear and nonlinear
`feedback shift registers (Chapter 6) and the output feedback mode (OFB) of block ciphers
`(Chapter 7), are addressed elsewhere in this book.
`
`Chapter outline
`The remainder of x5.1 introduces basic concepts relevant to random and pseudorandom
`bit generation. x5.2 considers techniques for random bit generation, while x5.3 considers
`some techniques for pseudorandom bit generation. x5.4 describes statistical tests designed
`
`169
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 169
`
`

`
`170
`
`Ch.5 PseudorandomBitsandSequences
`
`to measure the quality of a random bit generator. Cryptographically secure pseudorandom
`bit generators are the topic of x5.5. x5.6 concludes with references and further chapter notes.
`
`5.1.1 Background and Classification
`5.1 Definition A random bit generator is a device or algorithm which outputs a sequence of
`statistically independent and unbiased binary digits.
`
`5.2 Remark (random bits vs. random numbers) A random bit generator can be used to gener-
`ate (uniformly distributed) random numbers. For example, a random integer in the interval
`[0; n] can be obtained by generating a random bit sequence of length blg nc + 1, and con-
`verting it to an integer; if the resulting integer exceeds n, one option is to discard it and
`generate a new random bit sequence.
`
`x5.2 outlines some physical sources of random bits that are used in practice. Ideally,
`secrets required in cryptographic algorithms and protocols should be generated with a (true)
`random bit generator. However, the generation of random bits is an inefficient procedure in
`most practical environments. Moreover, it may be impractical to securely store and transmit
`a large number of random bits if these are required in applications such as the one-time pad
`(x6.1.1). In such situations, the problem can be ameliorated by substituting a random bit
`generator with a pseudorandom bit generator.
`
`5.3 Definition A pseudorandom bit generator (PRBG) is a deterministic1 algorithm which,
`given a truly random binary sequence of length k, outputs a binary sequence of length l (cid:29) k
`which “appears” to be random. The input to the PRBG is called the seed, while the output
`of the PRBG is called a pseudorandom bit sequence.
`
`The output of a PRBG is not random; in fact, the number of possible output sequences is at
`most a small fraction, namely 2k=2l, of all possible binary sequences of length l. The intent
`is to take a small truly random sequence and expand it to a sequence of much larger length,
`in such a way that an adversary cannot efficiently distinguish between output sequences of
`the PRBG and truly random sequences of length l. x5.3 discusses ad-hoc techniques for
`pseudorandom bit generation. In order to gain confidence that such generators are secure,
`they should be subjected to a variety of statistical tests designed to detect the specific char-
`acteristics expected of random sequences. A collection of such tests is given in x5.4. As
`the following example demonstrates, passing these statistical tests is a necessary but not
`sufficient condition for a generator to be secure.
`
`5.4 Example (linear congruential generators) A linear congruential generator produces a
`pseudorandom sequence of numbers x1; x2; x3; : : : according to the linear recurrence
`n (cid:21) 1;
`integers a, b, and m are parameters which characterize the generator, while x0 is the (secret)
`seed. While such generators are commonly used for simulation purposes and probabilistic
`algorithms, and pass the statistical tests of x5.4, they are predictable and hence entirely in-
`secure for cryptographic purposes: given a partial output sequence, the remainder of the
`(cid:3)
`sequence can be reconstructed even if the parameters a, b, and m are unknown.
`
`xn = axn−1 + b mod m;
`
`1Deterministic here means that given the same initial seed, the generator will always produce the same output
`sequence.
`
`c(cid:13)1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 170
`
`

`
`x5.2 Randombitgeneration
`
`171
`
`A minimum security requirement for a pseudorandom bit generator is that the length
`k of the random seed should be sufficiently large so that a search over 2k elements (the
`total number of possible seeds) is infeasible for the adversary. Two general requirements
`are that the output sequences of a PRBG should be statistically indistinguishable from truly
`random sequences, and the output bits should be unpredictable to an adversary with limited
`computational resources; these requirements are captured in Definitions 5.5 and 5.6.
`
`5.5 Definition A pseudorandom bit generator is said to pass all polynomial-time2 statistical
`tests if no polynomial-time algorithm can correctly distinguish between an output sequence
`of the generator and a truly random sequence of the same length with probability signifi-
`cantly greater that 1
`2 .
`
`5.6 Definition A pseudorandom bit generator is said to pass the next-bit test if there is no
`polynomial-time algorithm which, on input of the first l bits of an output sequence s, can
`predict the (l + 1)st bit of s with probability significantly greater than 1
`2 .
`
`Although Definition 5.5 appears to impose a more stringent security requirement on
`pseudorandom bit generators than Definition 5.6 does, the next result asserts that they are,
`in fact, equivalent.
`
`5.7 Fact (universality of the next-bit test) A pseudorandom bit generator passes the next-bit
`test if and only if it passes all polynomial-time statistical tests.
`
`5.8 Definition A PRBG that passes the next-bit test (possibly under some plausible but un-
`proved mathematical assumption such as the intractability of factoring integers) is called a
`cryptographically secure pseudorandom bit generator (CSPRBG).
`
`5.9 Remark (asymptotic nature of Definitions 5.5, 5.6, and 5.8) Each of the three definitions
`above are given in complexity-theoretic terms and are asymptotic in nature because the no-
`tion of “polynomial-time” is meaningful for asymptotically large inputs only; the resulting
`notions of security are relative in the same sense. To be more precise in Definitions 5.5, 5.6,
`5.8, and Fact 5.7, a pseudorandom bit generator is actually a family of such PRBGs. Thus
`the theoretical security results for a family of PRBGs are only an indirect indication about
`the security of individual members.
`
`Two cryptographically secure pseudorandom bit generators are presented in x5.5.
`
`5.2 Random bit generation
`
`A (true) random bit generator requires a naturally occurring source of randomness. De-
`signing a hardware device or software program to exploit this randomness and produce a
`bit sequence that is free of biases and correlations is a difficult task. Additionally, for most
`cryptographic applications, the generator must not be subject to observation or manipula-
`tion by an adversary. This section surveys some potential sources of random bits.
`Random bit generators based on natural sources of randomness are subject to influence
`by external factors, and also to malfunction. It is imperative that such devices be tested
`periodically, for example by using the statistical tests of x5.4.
`
`2The running time of the test is bounded by a polynomial in the length l of the output sequence.
`
`Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 171
`
`

`
`172
`
`Ch.5 PseudorandomBitsandSequences
`
`(i) Hardware-based generators
`Hardware-based random bit generators exploit the randomness which occurs in some phys-
`ical phenomena. Such physical processes may produce bits that are biased or correlated, in
`which case they should be subjected to de-skewing techniques mentioned in (iii) below.
`Examples of such physical phenomena include:
`1. elapsed time between emission of particles during radioactive decay;
`2. thermal noise from a semiconductor diode or resistor;
`3. the frequency instability of a free running oscillator;
`4. the amount a metal insulator semiconductor capacitor is charged during a fixed period
`of time;
`5. air turbulence within a sealed disk drive which causes random fluctuations in disk
`drive sector read latency times; and
`6. sound from a microphone or video input from a camera.
`Generators based on the first two phenomena would, in general, have to be built externally
`to the device using the random bits, and hence may be subject to observation or manipula-
`tion by an adversary. Generators based on oscillators and capacitors can be built on VLSI
`devices; they can be enclosed in tamper-resistant hardware, and hence shielded from active
`adversaries.
`
`(ii) Software-based generators
`Designing a random bit generator in software is even more difficult than doing so in hard-
`ware. Processes upon which software random bit generators may be based include:
`1. the system clock;
`2. elapsed time between keystrokes or mouse movement;
`3. content of input/output buffers;
`4. user input; and
`5. operating system values such as system load and network statistics.
`The behavior of such processes can vary considerably depending on various factors, such
`as the computer platform. It may also be difficult to prevent an adversary from observing or
`manipulating these processes. For instance, if the adversary has a rough idea of when a ran-
`dom sequence was generated, she can guess the content of the system clock at that time with
`a high degree of accuracy. A well-designed software random bit generator should utilize as
`many good sources of randomness as are available. Using many sources guards against the
`possibility of a few of the sources failing, or being observed or manipulated by an adver-
`sary. Each source should be sampled, and the sampled sequences should be combined using
`a complex mixing function; one recommended technique for accomplishing this is to apply
`a cryptographic hash function such as SHA-1 (Algorithm 9.53) or MD5 (Algorithm 9.51) to
`a concatenation of the sampled sequences. The purpose of the mixing function is to distill
`the (true) random bits from the sampled sequences.
`
`(iii) De-skewing
`A natural source of random bits may be defective in that the output bits may be biased (the
`probability of the source emitting a 1 is not equal to 1
`2 ) or correlated (the probability of
`the source emitting a 1 depends on previous bits emitted). There are various techniques for
`generating truly random bit sequences from the output bits of such a defective generator;
`such techniques are called de-skewing techniques.
`
`c(cid:13)1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 172
`
`

`
`x5.3 Pseudorandombitgeneration
`
`173
`
`5.10 Example (removing biases in output bits) Suppose that a generator produces biased but
`uncorrelated bits. Suppose that the probability of a 1 is p, and the probability of a 0 is 1 − p,
`where p is unknown but fixed, 0 < p < 1. If the output sequence of such a generator is
`grouped into pairs of bits, with a 10 pair transformed to a 1, a 01 pair transformed to a 0, and
`00 and 11 pairs discarded, then the resulting sequence is both unbiased and uncorrelated. (cid:3)
`A practical (although not provable) de-skewing technique is to pass sequences whose
`bits are biased or correlated through a cryptographic hash function such as SHA-1 or MD5.
`
`5.3 Pseudorandom bit generation
`
`A one-way function f (Definition 1.12) can be utilized to generate pseudorandom bit se-
`quences (Definition 5.3) by first selecting a random seed s, and then applying the function to
`the sequence of values s, s+1, s+2; : : : ; the output sequence is f (s), f (s+1), f (s+2); : : : .
`Depending on the properties of the one-way function used, it may be necessary to only keep
`a few bits of the output values f (s + i) in order to remove possible correlations between
`successive values. Examples of suitable one-way functions f include a cryptographic hash
`function such as SHA-1 (Algorithm 9.53), or a block cipher such as DES (x7.4) with secret
`key k.
`Although such ad-hoc methods have not been proven to be cryptographically secure,
`they appear sufficient for most applications. Two such methods for pseudorandom bit and
`number generation which have been standardized are presented in x5.3.1 and x5.3.2. Tech-
`niques for the cryptographically secure generation of pseudorandom bits are given in x5.5.
`
`5.3.1 ANSI X9.17 generator
`Algorithm 5.11 is a U.S. Federal Information Processing Standard (FIPS) approved method
`from the ANSI X9.17 standard for the purpose of pseudorandomly generating keys and
`initialization vectors for use with DES. Ek denotes DES E-D-E two-key triple-encryption
`(Definition 7.32) under a key k; the key k should be reserved exclusively for use in this
`algorithm.
`
`5.11 Algorithm ANSI X9.17 pseudorandom bit generator
`
`INPUT: a random (and secret) 64-bit seed s, integer m, and DES E-D-E encryption key k.
`OUTPUT: m pseudorandom 64-bit strings x1; x2; : : : ; xm.
`1. Compute the intermediate value I = Ek(D), where D is a 64-bit representation of
`the date/time to as fine a resolution as is available.
`2. For i from 1 to m do the following:
`2.1 xi Ek(I (cid:8) s).
`2.2 s Ek(xi (cid:8) I).
`3. Return(x1; x2; : : : ; xm).
`
`Each output bitstring xi may be used as an initialization vector (IV) for one of the DES
`modes of operation (x7.2.2). To obtain a DES key from xi, every eighth bit of xi should be
`reset to odd parity (cf. x7.4.2).
`
`Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 173
`
`

`
`174
`
`Ch.5 PseudorandomBitsandSequences
`
`5.3.2 FIPS 186 generator
`The algorithms presented in this subsection are FIPS-approved methods for pseudorandom-
`ly generating the secret parameters for the DSA (x11.5.1). Algorithm 5.12 generates DSA
`private keys a, while Algorithm 5.14 generates the per-message secrets k to be used in sign-
`ing messages. Both algorithms use a secret seed s which should be randomly generated, and
`utilize a one-way function constructed by using either SHA-1 (Algorithm 9.53) or DES (Al-
`gorithm 7.82), respectively described in Algorithms 5.15 and 5.16.
`
`5.12 Algorithm FIPS 186 pseudorandom number generator for DSA private keys
`
`INPUT: an integer m and a 160-bit prime number q.
`OUTPUT: m pseudorandom numbers a1, a2; : : : ; am in the interval [0; q − 1] which may
`be used as DSA private keys.
`1. If Algorithm 5.15 is to be used in step 4.3 then select an arbitrary integer b, 160 (cid:20)
`b (cid:20) 512; if Algorithm 5.16 is to be used then set b 160.
`2. Generate a random (and secret) b-bit seed s.
`3. Define the 160-bit string t = 67452301 efcdab89 98badcfe 10325476
`c3d2e1f0 (in hexadecimal).
`4. For i from 1 to m do the following:
`4.1 (optional user input) Either select a b-bit string yi, or set yi 0.
`4.2 zi (s + yi) mod 2b.
`4.3 ai G(t; zi) mod q. (G is either that defined in Algorithm 5.15 or 5.16.)
`4.4 s (1 + s + ai) mod 2b.
`5. Return(a1; a2; : : : ; am).
`
`5.13 Note (optional user input) Algorithm 5.12 permits a user to augment the seed s with ran-
`dom or pseudorandom strings derived from alternate sources. The user may desire to do
`this if she does not trust the quality or integrity of the random bit generator which may be
`built into a cryptographic module implementing the algorithm.
`
`5.14 Algorithm FIPS 186 pseudorandom number generator for DSA per-message secrets
`
`INPUT: an integer m and a 160-bit prime number q.
`OUTPUT: m pseudorandom numbers k1; k2; : : : ; km in the interval [0; q − 1] which may
`be used as the per-message secret numbers k in the DSA.
`1. If Algorithm 5.15 is to be used in step 4.1 then select an integer b, 160 (cid:20) b (cid:20) 512;
`if Algorithm 5.16 is to be used then set b 160.
`2. Generate a random (and secret) b-bit seed s.
`3. Define the 160-bit string t = efcdab89 98badcfe 10325476 c3d2e1f0
`67452301 (in hexadecimal).
`4. For i from 1 to m do the following:
`4.1 ki G(t; s) mod q. (G is either that defined in Algorithm 5.15 or 5.16.)
`4.2 s (1 + s + ki) mod 2b.
`5. Return(k1; k2; : : : ; km).
`
`c(cid:13)1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 174
`
`

`
`x5.4 Statisticaltests
`
`175
`
`5.15 Algorithm FIPS 186 one-way function using SHA-1
`INPUT: a 160-bit string t and a b-bit string c, 160 (cid:20) b (cid:20) 512.
`OUTPUT: a 160-bit string denoted G(t; c).
`1. Break up t into five 32-bit blocks: t = H1kH2kH3kH4kH5.
`2. Pad c with 0’s to obtain a 512-bit message block: X ck0512−b.
`3. Divide X into 16 32-bit words: x0x1 : : : x15, and set m 1.
`4. Execute step 4 of SHA-1 (Algorithm 9.53). (This alters the Hi’s.)
`5. The output is the concatenation: G(t; c) = H1kH2kH3kH4kH5.
`
`5.16 Algorithm FIPS 186 one-way function using DES
`
`INPUT: two 160-bit strings t and c.
`OUTPUT: a 160-bit string denoted G(t; c).
`1. Break up t into five 32-bit blocks: t = t0kt1kt2kt3kt4.
`2. Break up c into five 32-bit blocks: c = c0kc1kc2kc3kc4.
`3. For i from 0 to 4 do the following: xi ti (cid:8) ci.
`4. For i from 0 to 4 do the following:
`4.1 b1 c(i+4)mod5, b2 c(i+3)mod5.
`4.2 a1 xi, a2 x(i+1)mod5 (cid:8) x(i+4)mod5.
`
`
`4.3 A a1ka2, B b01kb2, where b01 denotes the 24 least significant bits of b1.
`4.4 Use DES with key B to encrypt A: yi DESB(A).
`4.5 Break up yi into two 32-bit blocks: yi = LikRi.
`5. For i from 0 to 4 do the following: zi Li (cid:8) R(i+2)mod5 (cid:8) L(i+3)mod5.
`6. The output is the concatenation: G(t; c) = z0kz1kz2kz3kz4.
`
`5.4 Statistical tests
`
`This section presents some tests designed to measure the quality of a generator purported
`to be a random bit generator (Definition 5.1). While it is impossible to give a mathematical
`proof that a generator is indeed a random bit generator, the tests described here help detect
`certain kinds of weaknesses the generator may have. This is accomplished by taking a sam-
`ple output sequence of the generator and subjecting it to various statistical tests. Each statis-
`tical test determines whether the sequence possesses a certain attribute that a truly random
`sequence would be likely to exhibit; the conclusion of each test is not definite, but rather
`probabilistic. An example of such an attribute is that the sequence should have roughly the
`same number of 0’s as 1’s. If the sequence is deemed to have failed any one of the statistical
`tests, the generator may be rejected as being non-random; alternatively, the generator may
`be subjected to further testing. On the other hand, if the sequence passes all of the statisti-
`cal tests, the generator is accepted as being random. More precisely, the term “accepted”
`should be replaced by “not rejected”, since passing the tests merely provides probabilistic
`evidence that the generator produces sequences which have certain characteristics of ran-
`dom sequences.
`x5.4.1 and x5.4.2 provide some relevant background in statistics. x5.4.3 establishes
`some notation and lists Golomb’s randomness postulates. Specific statistical tests for ran-
`domness are described in x5.4.4 and x5.4.5.
`
`Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 175
`
`

`
`176
`
`Ch.5 PseudorandomBitsandSequences
`
`5.4.1 The normal and chi-square distributions
`The normal and (cid:31)2 distributions are widely used in statistical applications.
`
`5.17 Definition If the result X of an experiment can be any real number, then X is said to be
`a continuous random variable.
`
`R 1
`
`5.18 Definition A probability density function of a continuous random variable X is a function
`f (x) which can be integrated and satisfies:
`(i) f (x) (cid:21) 0 for all x 2 R;
`−1 f (x) dx = 1; and
`(ii)
`(iii) for all a; b 2 R, P (a < X (cid:20) b) =
`(i) The normal distribution
`The normal distribution arises in practice when a large number of independent random vari-
`ables having the same mean and variance are summed.
`
`R b
`
`a
`
`f (x) dx.
`
`5.19 Definition A (continuous) random variable X has a normal distribution with mean (cid:22) and
`variance (cid:27)2 if its probability density function is defined by
`−(x − (cid:22))2
`1
`p
`2(cid:27)2
`(cid:27)
`2(cid:25)
`Notation: X is said to be N ((cid:22); (cid:27)2). If X is N (0; 1), then X is said to have a standard
`normal distribution.
`
`(cid:26)
`
`(cid:27)
`
`f (x) =
`
`exp
`
`; −1 < x < 1:
`
`A graph of the N (0; 1) distribution is given in Figure 5.1. The graph is symmetric
`
`0.45
`
`0.4
`
`0.35
`
`0.3
`
`0.25
`
`0.2
`
`0.15
`
`0.1
`
`0.05
`
`0
`
`-3
`
`f(x)
`
`-2
`
`-1
`
`0
`
`1
`
`2
`
`3
`
`x
`
`Figure5.1: The normal distribution N(0; 1).
`
`about the vertical axis, and hence P (X > x) = P (X < −x) for any x. Table 5.1 gives
`some percentiles for the standard normal distribution. For example, the entry ((cid:11) = 0:05,
`x = 1:6449) means that if X is N (0; 1), then X exceeds 1:6449 about 5% of the time.
`Fact 5.20 can be used to reduce questions about a normal distribution to questions about
`the standard normal distribution.
`
`c(cid:13)1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 176
`
`

`
`x5.4 Statisticaltests
`
`177
`
`(cid:11)
`x
`
`0:1
`1:2816
`
`0:05
`1:6449
`
`0:025
`1:9600
`
`0:01
`2:3263
`
`0:005
`2:5758
`
`0:0025
`2:8070
`
`0:001
`3:0902
`
`0:0005
`3:2905
`
`Table5.1:Selected percentiles of the standard normal distribution. If X is a random variable having
`a standard normal distribution, then P (X > x) = (cid:11).
`
`5.20 Fact If the random variable X is N ((cid:22); (cid:27)2), then the random variable Z = (X − (cid:22))=(cid:27) is
`N (0; 1).
`
`(ii) The (cid:31)2 distribution
`The (cid:31)2 distribution can be used to compare the goodness-of-fit of the observed frequencies
`of events to their expected frequencies under a hypothesized distribution. The (cid:31)2 distribu-
`tion with v degrees of freedom arises in practice when the squares of v independent random
`variables having standard normal distributions are summed.
`
`f (x) =
`
`8<
`:
`
`5.21 Definition Let v (cid:21) 1 be an integer. A (continuous) random variable X has a (cid:31)2 (chi-squ-
`are) distribution with v degrees of freedom if its probability density function is defined by
`1
`x(v=2)−1e−x=2; 0 (cid:20) x < 1;
`Γ(v=2)2v=2
`0;
`x < 0;
`where Γ is the gamma function.3 The mean and variance of this distribution are (cid:22) = v,
`and (cid:27)2 = 2v.
`A graph of the (cid:31)2 distribution with v = 7 degrees of freedom is given in Figure 5.2.
`Table 5.2 gives some percentiles of the (cid:31)2 distribution for various degrees of freedom. For
`
`f(x)
`
`0.12
`
`0.1
`
`0.08
`
`0.06
`
`0.04
`
`0.02
`
`0
`
`0
`
`x
`Figure5.2: The (cid:31)2 (chi-square) distribution with v = 7 degrees of freedom.
`
`5
`
`10
`
`15
`
`20
`
`example, the entry in row v = 5 and column (cid:11) = 0:05 is x = 11:0705; this means that if
`X has a (cid:31)2 distribution with 5 degrees of freedom, then X exceeds 11:0705 about 5% of
`the time.
`3The gamma function is defined by Γ(t) =
`
`R 1
`0 xt−1e−xdx, for t > 0.
`
`Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 177
`
`

`
`178
`
`Ch.5 PseudorandomBitsandSequences
`
`v
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`27
`28
`29
`30
`31
`63
`127
`255
`511
`1023
`
`0.100
`2.7055
`4.6052
`6.2514
`7.7794
`9.2364
`10.6446
`12.0170
`13.3616
`14.6837
`15.9872
`17.2750
`18.5493
`19.8119
`21.0641
`22.3071
`23.5418
`24.7690
`25.9894
`27.2036
`28.4120
`29.6151
`30.8133
`32.0069
`33.1962
`34.3816
`35.5632
`36.7412
`37.9159
`39.0875
`40.2560
`41.4217
`77.7454
`147.8048
`284.3359
`552.3739
`1081.3794
`
`0.050
`3.8415
`5.9915
`7.8147
`9.4877
`11.0705
`12.5916
`14.0671
`15.5073
`16.9190
`18.3070
`19.6751
`21.0261
`22.3620
`23.6848
`24.9958
`26.2962
`27.5871
`28.8693
`30.1435
`31.4104
`32.6706
`33.9244
`35.1725
`36.4150
`37.6525
`38.8851
`40.1133
`41.3371
`42.5570
`43.7730
`44.9853
`82.5287
`154.3015
`293.2478
`564.6961
`1098.5208
`
`(cid:11)
`
`0.025
`5.0239
`7.3778
`9.3484
`11.1433
`12.8325
`14.4494
`16.0128
`17.5345
`19.0228
`20.4832
`21.9200
`23.3367
`24.7356
`26.1189
`27.4884
`28.8454
`30.1910
`31.5264
`32.8523
`34.1696
`35.4789
`36.7807
`38.0756
`39.3641
`40.6465
`41.9232
`43.1945
`44.4608
`45.7223
`46.9792
`48.2319
`86.8296
`160.0858
`301.1250
`575.5298
`1113.5334
`
`0.010
`6.6349
`9.2103
`11.3449
`13.2767
`15.0863
`16.8119
`18.4753
`20.0902
`21.6660
`23.2093
`24.7250
`26.2170
`27.6882
`29.1412
`30.5779
`31.9999
`33.4087
`34.8053
`36.1909
`37.5662
`38.9322
`40.2894
`41.6384
`42.9798
`44.3141
`45.6417
`46.9629
`48.2782
`49.5879
`50.8922
`52.1914
`92.0100
`166.9874
`310.4574
`588.2978
`1131.1587
`
`0.005
`7.8794
`10.5966
`12.8382
`14.8603
`16.7496
`18.5476
`20.2777
`21.9550
`23.5894
`25.1882
`26.7568
`28.2995
`29.8195
`31.3193
`32.8013
`34.2672
`35.7185
`37.1565
`38.5823
`39.9968
`41.4011
`42.7957
`44.1813
`45.5585
`46.9279
`48.2899
`49.6449
`50.9934
`52.3356
`53.6720
`55.0027
`95.6493
`171.7961
`316.9194
`597.0978
`1143.2653
`
`0.001
`10.8276
`13.8155
`16.2662
`18.4668
`20.5150
`22.4577
`24.3219
`26.1245
`27.8772
`29.5883
`31.2641
`32.9095
`34.5282
`36.1233
`37.6973
`39.2524
`40.7902
`42.3124
`43.8202
`45.3147
`46.7970
`48.2679
`49.7282
`51.1786
`52.6197
`54.0520
`55.4760
`56.8923
`58.3012
`59.7031
`61.0983
`103.4424
`181.9930
`330.5197
`615.5149
`1168.4972
`
`Table5.2: Selected percentiles of the (cid:31)2 (chi-square) distribution. A (v; (cid:11))-entry of x in the table
`has the following meaning: if X is a random variable having a (cid:31)2 distribution with v degrees of
`freedom, then P (X > x) =(cid:11) .
`
`c(cid:13)1997 by CRC Press, Inc. — See accompanying notice at front of chapter.
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1012, p. 178
`
`

`
`x5.4 Statisticaltests
`
`179
`
`Fact 5.22 relates the normal distribution to the (cid:31)2 distribution.
`
`5.22 Fact If the random variable X is N ((cid:22); (cid:27)2), (cid:27)2 > 0, then the random variable Z = (X −
`(cid:22))2=(cid:27)2 has a (cid:31)2 distribution with 1 degree of freedom. In particular, if X is N (0; 1), then
`Z = X 2 has a (cid:31)2 distribution with 1 degree of freedom.
`
`5.4.2 Hypothesis testing
`A statistical hypothesis, denoted H0, is an assertion about a distribution of one or more ran-
`dom variables. A test of a statistical hypothesis is a procedure, based upon observed values
`of the random variables, that leads to the acceptance or rejection of the hypothesis H0. The
`test only provides a measure of the strength of the evidence provided by the data against
`the hypothesis; hence, the conclusion of the test is not definite, but rather probabilistic.
`
`5.23 Definition The significance level (cid:11) of the test of a statistical hypothesis H0 is the proba-
`bility of rejecting H0 when it is true.
`
`In this section, H0 will be the hypothesis that a given binary sequence was produced
`by a random bit generator. If the significance level (cid:11) of a test of H0 is too high, then the test
`may reject sequences that were, in fact, produced by a random bit generator (such an error
`is called a Type I error). On the other hand, if the significance level of a test of H0 is too
`low, then there is the danger that the test may accept sequences even though they were not
`produced by a random bit generator (such an error is called a Type II error).4 It is, therefore,
`important that the test be carefully designed to have a significance level that is appropriate
`for the purpose at hand; a significance level (cid:11) between 0:001 and 0:05 might be employed
`in practice.
`A statistical test is implemented by specifying a statistic on the random sample.5 Statis-
`tics are generally chosen so that they can be efficiently computed, and so that they (approxi-
`mately) follow an N (0; 1) or a (cid:31)2 distribution (see x5.4.1). The value of the statistic for the
`sample output sequence is computed and compared with the value expected for a random
`sequence as described below.
`1. Suppose that a statistic X for a random sequence follows a (cid:31)2 distribution with v
`degrees of freedom, and suppose that the statistic can be expected to take on larger
`values for nonrandom sequences. To achieve a significance level of (cid:11), a threshold
`value x(cid:11) is chosen (using Table 5.2) so that P (X > x(cid:11)) = (cid:11). If the value Xs of the
`statistic for the sample output sequence satisfies Xs > x(cid:11), then the sequence fails the
`test; otherwise, it passes the test. Such a test is called a one-sided test. For example,
`if v = 5 and (cid:11) = 0:025, then x(cid:11) = 12:8325, and one expects a random sequence to
`fail the test only 2:5% of the time.
`2. Suppose that a statistic X for a random sequence follows an N (0; 1) distribution, and
`suppose that the statistic can be expected to take on both larger and smaller values for
`nonrandom sequences. To achieve a significance level of (cid:11), a threshold value x(cid:11) is
`chosen (using Table 5.1) so that P (X > x(cid:11)) = P (X < −x(cid:11)) = (cid:11)=2. If the value
`
`4Actually, the probability (cid:12) of a Type II error may be completely independent of (cid:11). If the generator is not a
`random bit generator, the probability (cid:12) depends on the nature of the defects of the generator, and is usually d