Cryptography Reference
In-Depth Information
deterministic random number generators. The specification establishes four
classes of increasing security:
K1:
A sequence of random vectors composed of random numbers should
with high probability contain no identical consecutive elements. Statistical
properties of the generated random numbers are unimportant. The length of
the random vectors and the probability of error depend on the application.
K2:
The generated random numbers should be indistinguishable from true
random numbers based on statistical tests. The tests to be applied are the
monobit test, poker test, runs and longruns tests from [BSI2] and [FIPS], as
well as the additional statistical test of autocorrelation. Altogether, what is
checked is how well a given sequence of bits (or a part of such a sequence)
satisfies the following conditions:
•
Zeros and ones appear equally often.
•
After a sequence of
n
zeros (respectively ones), the next bit will be a
one (zero) with probability one-half.
•
A given output contains no information about the next output.
K3:
It should be impossible for all practical purposes for an attacker to be able
to calculate or guess from a known sequence of generated random numbers
any previous or future random numbers or an inner state of the generator.
K4:
It should be impossible for all practical purposes for an attacker to calculate
or guess from an inner state of the generator previous random numbers or
states.
12.3.1 Chi-Squared Test
As motivation for dealing with tests for evaluation of property K2, we look first at
the
chi-squared test
(also written “
χ
2
test”), which with the Kolmogorov-Smirnov
test is among the most important tests of goodness of fit. The chi-squared test
gives information on how well an empirically obtained probability distribution
corresponds to a theoretically expected distribution. The chi-squared test
computes the statistic
t
(
H
(
X
i
)
−
n
pr (
X
i
))
2
n
pr (
X
i
)
χ
2
=
,
(12.8)
i
=1
where for
t
distinct events
X
i
we designate
H
(
X
i
)
the observed frequency of the
event
X
i
,
pr (
X
i
)
the probability for the occurrence of
X
i
, and
n
the number of
observations. For the case to which these distributions correspond, the statistic
χ
2
, viewed as a random variable, has the expected value
E
χ
2
=
t
1
. The
threshold values that lead to the rejection of the test hypothesis of equality of
−
