Cryptography Reference
In-Depth Information
need for a natural source of randomness. It is rather a “randomness expander” that
must still be given a truly random seed to begin with.
In practice, many additive stream ciphers are based on a PRBG. For example,
the practically relevant and widely deployed additive stream cipher ARCFOUR
(RC4) addressed in Section 10.3 basically represents a PRBG.
B"
+++
3
1
=
Figure 12.1
An idealized model of an FSM-based PRBG.
Due to its deterministic nature, a PRBG must be implemented as an FSM,
and this FSM generates a binary sequence that is cyclic (with a potentially very
large cycle). Figure 12.1 illustrates an idealized model of an FSM-based PRBG. The
model comprises
A state register;
A next-state function f ;
An output function g .
The state register is initialized with a seed s 0 , and the next-state function f
computes s i +1
0. For each s i , the function g computes an output
value x i for the PRBG (typically a bit or a series of bits). Consequently, the PRBG
generates and outputs a sequence
from s i for i
( x i ) i≥ 1 = x 1 ,x 2 ,x 3 ,...
In this idealized model, the function f operates recursively on the state
register, and there is no other input to the PRBG than the seed. Some PRBGs used
in practice slightly deviate from this idealized model by allowing the state to be
 
Search WWH ::




Custom Search