Information Technology Reference
In-Depth Information
maximum value as
α
i
, which is 0.176163 for 20 and 0.181317 for 30 bit se-
quences. Due to the correlations in this suite, coverage reduces around 30%.
Testing short sequences, these correlations should be considered. As the length
of the sequences increase, it is possible to observe weaker correlation between
tests. For instance, in Table 2 for
n
= 20, the number of highlighted cells (pro-
portion
>
0
.
10) is 37, whereas this number decreases to 27 for
n
= 30 given in
Table 3. It should be noted that in case of testing longer sequences by level-2
version of these tests, correlations still exist whenever the input block size is
small.
4 Sensitivity of Tests
To have more confidence in a random number generator, it is advantageous to
use as many randomness tests as possible. In this part of the study, we propose
to apply simple transformations to input sequences that significantly change the
output
p
-value of a randomness test as an alternative to developing more tests.
Definition 1.
Consider a randomness test
T
and a one-to-one transformation
σ
:
L
L
where
L
is the set of all
n
bit binary sequences.
T
is said to be
invariant under
σ
if for any
S
in
L
,
T
(
S
)=
T
(
σ
(
S
))
.
→
Here, we define a new concept of
sensitivity
to measure the effect of a transfor-
mation to output
p
-values. If a test
T
is invariant under
σ
,sensitivityof
T
to
σ
is represented by 0. If the transformation has small effect on the test results,
that is, there is a significant correlation between
T
(
S
)and
T
(
σ
(
S
)), sensitivity
is represented by 1. Whenever
T
(
S
)and
T
(
σ
(
S
)) are statistically independent,
sensitivity is represented by 2, in those cases
T
(
σ
(
.
)) can be added to the test
suite as a new test.
The transformation
σ
can be chosen in various ways, in this section, we con-
sider a few of them as examples.
-
Complementation
is applying the unary bitwise NOT operation, that is
σ
c
(
s
1
,...,s
n
)=(
s
1
⊕
1
,...,s
n
⊕
1).
-
l
-Rotation
is a circular shift operation commonly used in cryptography, that
is
σ
l−rot
(
s
1
,...,s
n
)=(
s
l
+1
,...,s
n
,s
1
,...,s
l
). Most of the level-2 tests are
invariant to
l
-rotation, when
l
is equal to the block length.
-
i
th
Bit flip
is simply flipping
i
th
bit of the sequence, that is
σ
f
i
(
s
1
,...,s
n
)=
(
s
1
,...,s
i
⊕
1
,...,s
n
).
-
Reversing
is simply considering the sequence backwards, that is
σ
rvs
(
s
1
,...,s
n
)=(
s
n
,...,s
1
).
-
l
th
Derivative
of a sequence is the summation of the sequence and its
l
-bit
rotation, that is
σ
d
l
(
s
1
,...,s
n
)=(
s
1
⊕
s
l
). This
transformation is not one-to-one and applying such transformations results
in changes in the
α
values. To make the transformation one-to-one, following
simple modification can be done:
s
l
+1
,...,s
n−l
⊕
s
n
,...,s
n
⊕
σ
d
l
(
s
1
,...,s
n
)=(
s
1
⊕
s
l
+1
,...,s
n−l
⊕
s
n
,...,s
n−
1
⊕
s
l−
1
,s
n
).
