Random number generation for cryptography
Author: Jamie McLauchlin
Revised: April 6, 2007
There are numerous applications for random numbers which has led to the development of many methods for generating them. Some of the earliest methods for generating random numbers include rolling dice or flipping a coin. More recently, physical phenomenon such as thermal noise, which appears to be truly random, has been used as the basis for hardware random number generators. There are countless applications for random numbers including gambling, statistical sampling, and computer simulation, but one of the most significant is that random numbers form the centerpiece of cryptography. [1]
Contents 1 Random number generators vs. pseudo random number generators 2 Application for cryptography 3 Examples of pseudorandom number generators 3.2 Inversive congruential generator

Random number generators vs. pseudo random number generators
There are two main methods used for generating random numbers. The first measures a physical phenomenon that is thought to be random and compensates for any potential biases in the measurements. The second uses computational algorithms to produce long sequences of apparently random results, which are determined by a shorter initial seed or key.
A hardware, or true, random number generator is a piece of electronics that plugs into a computer and produces genuine random numbers as opposed to pseudorandom numbers, which are produced by a computer program. The usual method is to amplify noise generated by a resistor or a semiconductor diode and feed this to a comparator or Schmitt trigger. If the output is sampled, a series of bits are given that are statistically independent. These bits can be assembled into bytes, integer or floating point numbers, and then if necessary into random numbers from other distributions using certain methods. [2]
The computational methods for generating random numbers are known as pseudorandom number generators (PRNGs). A PRNG is a deterministic algorithm that is used to generated a sequence of numbers that approximate the properties displayed by random numbers. This sequence is not truly random since it is determined by initializing what is known as a "seed." A seed is a random event, such as the current time of day in milliseconds, that is used to simulate a different sequence every time it is used. A computer is likely to generate pseudorandom numbers and not actual random numbers. [3] A PRNG cannot be regarded as a "true" random number generator, since its output is predictable.
Random numbers form the centerpiece of cryptography provided the seed that the random number generator provides remains secretive and a high degree of randomness is maintained. A seed represents a secret parameter, known only by the communicants, for a specific message exchange context. seeds are important since ciphers without variable keys are easy to break. [4] A PRNG that is suitable for a cryptographic application is called a cryptographically secure PRNG (CSPRNG). The difference between a PRNG and CSPRNG is quite complex since a CSPRNG is required to meet certain criteria and be resistant to known attacks. Certification of an algorithm takes years of review and even then there is potential for future attacks to be developed. [3]
Examples of pseudorandom number generators
Blum Blum Shub (BBS) is a pseudorandom number generator that was proposed by Lenore Blum, Manuel Blum, and Michael Shub in 1986.
BBS has the form:
x_{n+1} = (x_{n})^{2} mod M
where M = pq and p and q are large prime numbers. At each iteration of the algorithm, an output is derived from x_{n} which is usually either the parity bit of x_{n} or one or more of the least significant bits of x_{n}. [5] The parity bit is a binary digit that indicates whether the number of bits with the value of one in a given set of bits is odd or even. [6]
It is important that p and q both be congruent to 3 (mod 4) and that the gcd(φ(p1), φ(q1)) should be small. [5] The two integers a and b are considered congruent modulo n if a  b is divisible by n or if they have the same remainder upon being divided by n. [7] gcd(a, b), or the greatest common divisor of a and b, represents the largest positive integer that divides both integers a and b without a remainder. [8] Euler's totient function, φ(n), of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. [9] Two integers are considered to be coprime when they have no common factor other than 1 and 1, or equivalently, their gcd is 1. [10]
This PRNG is suitable for cryptography, though it is not very fast. It possesses a very strong security proof. When the primes p and q are chosen appropriately and a sufficient number of lowerorder bits of each x_{n} are output. [5]
n^{}^{1}^{ }= m (mod p) [12]
The standard formula for an inversive congruential generator is
x_{i+}_{1} = (ax_{i}^{1} + c) (mod m)
where
0 ≤ x_{i }< m. [11]
[1] http://en.wikipedia.org/wiki/Random_number_generator
[2] http://www.robertnz.net/true_rng.html
[3] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[4] http://en.wikipedia.org/wiki/Cryptography
[5] http://en.wikipedia.org/wiki/Blum_Blum_Shub_generator
[6] http://en.wikipedia.org/wiki/Parity_bit
[7] http://en.wikipedia.org/wiki/Congruence_relation
[8] http://en.wikipedia.org/wiki/Greatest_common_divisor
[9] http://en.wikipedia.org/wiki/Euler%27s_totient_function
[10] http://en.wikipedia.org/wiki/Coprime
[11] http://en.wikipedia.org/wiki/Inversive_congruential_generator
[12] http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Advanced Encryption Method (AES)