## 11/20/2015

### cryptography11

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.