|
Contents 1 Random number generators vs. pseudo random number generators 2 Application for cryptography 3 Examples of pseudo-random 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 pseudo-random numbers, which are produced by a computer program. The usual method is to amplify noise generated by a resistor or a semi-conductor 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 pseudo-random 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 pseudo-random 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 pseudo-random number generators
Blum Blum Shub (BBS) is a pseudo-random number generator that was proposed by Lenore Blum, Manuel Blum, and Michael Shub in 1986.
BBS has the form:
xn+1 = (xn)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 xn which is usually either the parity bit of xn or one or more of the least significant bits of xn. [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(φ(p-1), φ(q-1)) 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 lower-order bits of each xn are output. [5]
Inversive congruential generator
An inversive congruential generator is a type of non-linear congruetnial pseudo-random number generator, which use the modular multiplicative inverse (if it exists) to generate the next number in a sequence. [11] The modular multiplicative inverse of an integer n modulo p is an integer m such that
n-1 = m (mod p) [12]
The standard formula for an inversive congruential generator is
xi+1 = (axi-1 + c) (mod m)
where
0 ≤ xi < 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/Pseudo-random_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)