What is pseudo random number

Good Description

1. What is Pseudo Random Number
Generator (PRNG)?
•It is a mechanism for generating random numbers on a
computer that are indistinguishable from truly random
numbers.
•Many applications don’t have source of truly random bits;
instead they use PRNGs to generate these numbers.
•Pseudo random because it is not possible to generate truly
random numbers from deterministic thing like computer.

2. Why Study PRNGs ?
•They are used everywhere in cryptography. Random numbers
are in session keys, public key generation, initialization vector
and many other places.
•PRNG is a single point of failure for many real-world
cryptosystems. If random numbers are insecure then the entire
application is insecure.
•Many systems use badly-designed PRNGs, or use them in ways
that make various attacks easier than they need be.

3. Characteristics of good PRNGs ?
•Should generate on average as many 1’s as 0’s.
01111110 01101001
•Should be random enough to hide patterns and correlation.
10101010
•Should have a large period.
0110100111001010 0001100001101001
•Should not produce preferred strings
11001100
•Knowledge of some outputs should not help predict past or future outputs

4. PRNG Model
•Collect
Collect unpredictable inputs.
inputs are collected in a “seed
pool”.
•State (secret state)
After collecting sufficient seed
data, move to a stable state.
•Generate
Generate random outputs by
performing various operations on
the seed data.

5. RSA PRNG
•To generate a bit stream of size l
•Choose two prime numbers p = 11 and q = 19,(n= p*q = 209)
•m = (p-1)(q-1),(m = 180)
•Choose e such that gcd(e,m) is 1.(e = 7)
•Select X0(seed) such that 1 < X0< n(let X0= 72)
•For i = 1 to l do
–Xi = (Xi-1)^e mod n
–Zi = least significant bit of Xi
•X1 = 72^7 mod 209
•X1 = 184Z1 = 0
X2 = 200Z2 = 0
X3 = 205Z3 = 1
•00110110…………