Pseudorandom Number Generation

We uses PRNGs everyday over internet, network security applications and protocols such as RSA and authentication algorithms.
There are two requirements for generating a sequence of random numbers:
1- Randomness
2- Unpredictability

For sure, to generate a sequence of random numbers must has randomness and we can define this concept statistically by two criteria :

1. Uniform distribution: means the frequency of occurrence of ones and zeros should be approximately equal.
2. Independence: means no sequence can be inferred from another sequence.
   

   Note 1: We can preform tests for uniform distribution but we can’t prove independence.

Unpredictability means the successive members of sequence of numbers must be unpredictable.

PRNGs take input called the seed, the seed is a fixed value, then producing output by using a deterministic algorithm and any additional outputs are feedback to PRNG algorithm again as input.
The seed must be secure because PRNG uses a deterministic algorithm so if the attacker can deduce the seed then he can determine the output of PRNG.

• Purpose-built algorithm: Algorithms that are design for generating pseudorandom such as RC4.
• Algorithms based on existing cryptographic algorithms: There are some cryptographic algorithms need a random input to produce ciphertext such as in a symmetric key encryption and hashing functions.

This algorithm is widely used to produce random numbers and it’s proposed by Lehmer.
This algorithm has 4 parameters:

• m –> The modules
• a –> The multiplier
• c –> The increment
• X0 –> The starting value
  And the equation is :
  \(X_{n+1} = (aX_{n}+c) mod(m)\)

This algorithm should pass three tests:

1. The function should generate all numbers from 0 to m before repeating.
2. The sequence should be random.
3. The function should implement efficiently with 32 bit arithmetic.
   For example:
   If we use Linear Congruential Generator a=7, c=0, m=32, x0=1, then the output = {7,17,23,1,7,…}
   We have a repeating value after 5th time {7}
   So we need some modifications, m value should be equal to the maximum representable non-negative integer for the computer such as \(2^{31}\), It’s recommended to use m as a prime number such as \(2^{31} - 1\).
   That gives us about 2 billion choices for a, but a few choices will pass the three tests such as \(a=7^{5}\)  c=0.

BBS is a secure PRNG, first we need a prime numbers p and q so that (p mod(4))=(q mod(4))=3, for example 7 and 11, then let n=p*q, the we choose a random number S, and S should be relatively prime to n.
Then BBS generates a sequence of bits Bi according to the next algorithm
\({X}_{0}={S}^{2} mod (n)\)
\(For \ i=0\ to\ \infty\)
\({X}_{i}=(X-1)^{2}mod(n)\)
\({B}_{i}={X}_{i}mod(2)\)

TRNG uses nondeterministic source to produce random numbers by measuring unpredictable natural processes such as radiation, gas discharge …etc.
We can use some source of randomness on our computers such as sound input ,video input .

Note 2: TRNG is not practical for stream cipher.
Note 3: TRNG may produce an output that is biased (the number of ones and zeros are not equal) and to eliminate this bias is by passing the bit stream through a hashing function such as MD5 and SHA1.