Cryptography 11

Pseudorandom Number Generation (PRNG)

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

1- Randomness:

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:

Uniform distribution means the frequency of occurrence of ones and zeros should be approximately equal.

2- Independence:

Independence means no sequence can be inferred from another sequence.

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

2- Unpredictability:

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

Pseudorandom Number Generation is:

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.

PRNG Types:

1- Purpose-built algorithm:

Algorithms that are design for generating pseudorandom such as RC4.

2- Algorithms based on existing cryptographic algorithms:

There are some cryptographic algorithms need a random input to produce a ciphertext such as in a symmetric key encryption and hashing functions.

PRNG Algorithm Types:

1- Linear Congruential Generators:

This algorithm is widely used to produce random numbers and it's proposed by Lehmer.

This algorithm has 4 parameters:

1- m --> The modules

2- a --> The multiplier

3- c --> The increment

4- X0 --> The starting value

And the equation is :

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.

2- Blum Blum shub Generator (BBS):

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)\)

True Random Number Generation (TRNG)

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 #1: TRNG is not practical for stream cipher.

Note #2: 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.