Cryptography: Theory and Practice:Pseudo-random Number Generation

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Another approach in constructing very fast PRBGs is to combine LFSRs in some way that the output looks less linear. One such method, due to Coppersmith, Krawczyk and Mansour, is called the Shrinking Generator. Suppose we have two LFSRs, one of degree k₁ and one of k₂. We will require a total of k₁ + k₂ bits as our seed, in order to initialize both LFSRs. The first LFSR will produce a sequence of bits, say a₁, a₂, …, and the second produces a sequence of bits b₁, b₂, ….Then we define a sequence of pseudo-random bits z₁, z₂, … by the rule

where i_k is the position of the kth 1 in the sequence b₁, b₂, …. These pseudo-random bits comprise a subsequence of the bits produced by the first LFSR. This method of pseudo-random bit generation is very fast and is resistent to various known attacks, but there does not seem to be any way to prove that it is secure.

In the rest of this chapter, we will investigate PRBGs that can be proved to be secure given some plausible computational assumption. There are PRBGs based on the fundamental problems of factoring (as it relates to the RSA public-key cryptosystem) and the Discrete Logarithm problem. A PRBG based on the RSA encryption function is shown in Figure 12.2, and a PRBG based on the Discrete Logarithm problem is discussed in the exercises.

We now give an example of the RSA Generator.

**Table 12.2** Bits produced by RSA generator
i	s_i	z_i
0	75634
1	31483	1
2	31238	0
3	51968	0
4	39796	0
5	28716	0
6	14089	1
7	5923	1
8	44891	1
9	62284	0
10	11889	1
11	43467	1
12	71215	1
13	10401	1
14	77444	0
15	56794	0
16	78147	1
17	72137	1
18	89592	0
19	29022	0
20	13356	0

Example 12.2

Suppose n = 91261 = 263 × 347, b = 1547, and s₀ = 75364. The first 20 bits produced by the RSA Generator are computed as shown in Table 12.2. Hence the bit-string resulting from this seed is

10000111011110011000.

12.2 Indistinguishable Probability Distributions

There are two main objectives of a pseudo-random number generator: it should be fast (i.e., computable in polynomial time as a function of k) and it should be secure. Of course, these two requirements are often conflicting. The PRBGs based on linear congruences or linear feedback shift registers are indeed very fast. These PRBGs are quite useful in simulations, but they are very insecure for cryptographic applications.

Let us now try to make precise the idea of a PRBG being “secure.” Intuitively, a string of k^m bits produced by a PRBG should look “random.” That is, it should be impossible in an amount of time that is polynomial in k (equivalently, polynomial in ) to distinguish a string of pseudo-random bits produced by a PRBG from a string of truly random bits.

This motivates the idea of distinguishability of probability distributions. Here is a definition of this concept.

DEFINITION 12.2 Suppose p₀ and p₁ are two probability distributions on the set of bit-strings of length . Let be a probabilistic algorithm that runs in polynomial time (as a function of ). Let ε > 0. For j = 0, 1, define

We say that A is an ε-distinguisher of p₀ and p₁ provided that

and we say that p₀ and p₁ are ε-distinguishable if there exists an ε-distinguisher of p₀ and p₁.

REMARK If A is a deterministic algorithm, then the conditional probabilities

always have the value of 0 or 1.

The intuition behind this definition is as follows. The algorithm A tries to decide if a bit-string of length is more likely to have arisen from probability distribution p₁ or from probability distribution p₀. This algorithm may use random numbers if desired, i.e., it can be probabilistic. The output represents the algorithm’s guess as to which of these two probability distributions is more likely to have produced, . The quantity E_A (p_j) represents the average (i.e., expected) value of the output of A over the probability distribution p_j, for j = 0, 1. This is computed by summing over all possible sequences the product of the probability of the -tuple and the probability that A answers “1” when given as input. A is an ε-distinguisher provided that the values of these two expectations are at least ε apart.

Table of Contents