Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 92

Generator

r 1 ,..., r d

r d + 1

Adversary

Figure 3.15. Adversarial model for a pseudorandom generator.

3.5 Cryptographic Pseudorandom Generators

3.5.1 Usage and Threat Model

Regular probabilistic algorithms use pseudorandom generators. They usually have to
look like random to statistical tests. Secure application also need randomness, like
simply choosing a secret key. Cryptographic pseudorandom generators need to be
robust against malicious adversaries who will try to predict new random generations
as depicted in Fig. 3.15.

For instance, if we use the Vernam cipher with a secret key generated by a cryp-
tographic pseudorandom generator, we do not want an adversary who can perform a
known plaintext attack to be able to predict the next key, otherwise the encryption is
not secure against a known plaintext attack.

3.5.2 Congruential Pseudorandom Generator

A famous pseudorandom generator which was first proposed for secure applications
is the congruential pseudorandom generator. A general version of it is defined by a
parameter k and k functions ϕ 1 ,...,ϕ k from Z k to Z . The pseudorandom generator

is defined by a secret modulus m , secret coefficients

α 1 ,...,α k , and a secret initial

state s 1 ,..., s k . The time counter is initially set to i = k . For a new generation, we first

increment i and output

j = 1 α j ϕ j ( s i − k ,...,

k

s i = s i − 1 ) mod m .

This pseudorandom generator is quite weak as shown by Joan Boyar and
Hugo Krawczyk (see Refs. [36, 106, 107]). Assuming that an adversary has seen