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

s i − k ,..., s i − 1 , he can compute a vector defined by

⎛
⎝

⎞
⎠ .

ϕ 1 ( s i − k ,..., s i − 1 )

ϕ 2 ( s i − k ,..., s i − 1 )

B i =

.
ϕ k ( s i − k ,..., s i − 1 )

Once he gets more than k vectors, say for instance B 1 ,..., B i , he can deduce a linear

relationship

j = 0 γ j B j

i − 1

γ i B i =

with integral coefficients γ 1 ,...,γ i . Now since we know that s i is a scalar product

between B i and a secret constant vector modulo a secret modulus m , we deduce that

j = 0 γ j s j

i − 1

γ i s i ≡ (mod m ) .

This is used to get an estimate of m by the difference

j = 0 γ j s j .

i − 1

γ i s i −

More precisely, we attack the generator as depicted in Fig. 3.16. Here m is a multiple of
m , which approximates m with increasing precision. After a few steps, we get m

= m ,

α i by solving a linear system modulo m .

and we can recover the

3.5.3 Practical Examples

We mention three practical cryptographic pseudorandom generators.

First, we notice that the OFB mode and CTR mode of block ciphers consist of trans-
forming the block cipher into a pseudorandom generator to be used with the Vernam
cipher. The OFB and CTR modes thus already define how to make a pseudorandom
generator from a block cipher.

Second we mention the ANSI X9.17 standard generator (Ref. [2]) based on Triple-
DES: The generator uses a timestamp and an internal seed. The new generation r is