Cryptography Reference
In-Depth Information
the distributions for given error probabilities can be read from tables of the
chi-squared distribution for
t −
1
degrees of freedom (cf. [Bos1], Section 4.1).
The chi-squared test is employed in connection with many empirical tests
to measure their results for correspondence with the theoretically calculated test
distributions. The test is particularly simple to apply for sequences of uniformly
distributed (which is our test hypothesis!) random numbers
X
i
in a range of
values
W
=
{
0
,...,ω−
1
}
: We assume that each of the numbers in
W
is
taken with the same probability
p
=1
/ω
and thus expect that among
n
random
numbers
X
i
each number from
W
appears approximately
n/ω
times (where
we assume
n>ω
). However, this should not be
exactly
the case, because the
probability
P
k
that among
n
random numbers
X
i
a specific value
w ∈ W
appears
k
timesisgivenby
P
k
=
n
k
p
k
(1
n
!
p
)
n
−
k
=
k
!(
n − k
)!
p
k
(1
p
)
n
−
k
.
−
−
(12.9)
This
binomial distribution
indeed has the largest values for
k ≈ n/ω
, but the
probabilities
P
0
=(1
− p
)
n
and
P
n
=
p
n
are not equal to zero. Under the
assumption of random behavior we therefore expect to observe in the sequence
of the
X
i
frequencies
h
w
of individual values
w ∈ W
according to the binomial
distribution. Whether this actually occurs is established by the chi-squared test in
calculating
ω
−
1
ω
−
1
(
h
j
−
n/ω
)
2
n/ω
=
ω
n
χ
2
=
h
i
− n.
(12.10)
i
=0
i
=0
The test is repeated for several random samples (partial sequences of
X
i
). A
rough approximation to the chi-squared distribution allows us t
o
deduce t
ha
t
in most cases the test result
χ
2
must lie in the interval
ω
2
√
ω, ω
+2
√
ω
.
Otherwise, the given sequence would attest to a lack of randomness. Based on
this, the probability of an error, namely, that an actually “good” random sequence
is declared “bad” based on the result of the chi-squared test, is about two percent.
It is in this sense that the error probability of
10
−
6
that results from the given
bounds is to be interpreted in the following tests. The bounds are set such that
a “halfway reasonable” probability generator would almost always pass the test,
so that known attacks against cryptographic algorithms based on statistical
weaknesses in random number generators would fail (see [BSI2], page 7).
5
The linear congruence generator in the ISO-C standard that we considered
above passes this simple test, as do the pseudorandom number generators that
we shall implement below for the FLINT/C package.
−
5
Take note that the test is valid only for a sufficiently large number of samples: This number
must be at least
n
=5
ω
(see [Bos2], Section 6.1), with an even larger number to be preferred.
