Cryptography Reference
In-Depth Information
s
2
=
s
0
+2
s
3
=
s
0
+3
...
Talking in terms of an FSM, the state register is initialized with the seed
s
0
,
the next-state function is the function that increments
s
by one (i.e.,
s
i
+1
=
s
i
+1
for
i
0), and the output function is the one-way function. The output sequence of
such a PRBG is as follows:
≥
f
(
s
0
)
,f
(
s
0
+1)
,f
(
s
0
+2)
,f
(
s
0
+3)
,...
Depending on the properties of the one-way function
f
, it may be necessary
to keep only a few bits of the (
i
+1)
th
0 (mainly to
destroy possible correlations between successive values). Examples of suitable one-
way functions include block ciphers, such as DES or AES (see Chapter 10), with a
secret key, or cryptographic hash functions, such as MD5 or SHA-1 (see Chapter 8).
output value
f
(
s
+
i
) for
i
≥
Algorithm 12.1
ANSI X9.17 PRBG.
(
s, k, n
)
I ← E
k
(
D
)
for
i
=1to
n
do
x
i
← E
k
(
I ⊕ s
)
s ← E
k
(
x
i
⊕ I
)
output
x
i
(
x
1
,x
2
,...,x
n
)
A practically relevant PRBG is specified in ANSI X9.17 [4] and illustrated in
Algorithm 12.1. It defines a way to pseudorandomly generate encryption keys and
initialization vectors for use with DES. In the specification of Algorithm 12.1,
E
k
denotes a TDEA or 3DES encryption with keying option 2, according to Section
10.2.1.6 (in this option, only two DES keys are used, and in Algorithm 12.1
k
refers to both of them). The algorithm takes as input a random (and secret) seed
value
s
,a3DESkey
k
, and an integer
n
. It then produces and outputs a sequence
of
n
pseudorandom 64-bit strings
x
1
,x
2
,...,x
n
.
D
is an internally used 64-bit
representation of the date and time (in a resolution that is as fine as possible), and
I
is an intermediate value that is determined in an initialization step at the beginning
of the algorithm.