Random Numbers

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." - John von Neumann.

Introduction

Come on, there's got to be something that's truly random, right? Well, the answer is maybe. Frequencies from outer space are fairly random, detecting the rate of emissions from radioactive material is pretty random, or even some kind of physical noise generator could work. Actually, it's currently impossible to prove something to be truly random. So, the next best thing is to adhere to the attributes of randomness as much as possible. There are 2 properties of randomness that are striven for: Uniform distribution and Independence. Uniform distribution is when the frequency of occurring elements are practically the same and independence refers to the inability to predict an element based on another element or group of element(s). Thus, it is important that a high degree of unpredictability is reached so that it is extremely difficult to predict the next number after a series of (random) numbers.

PseudoRandom Number Generators

Linear Congruential

Although, deterministic algorithms are used for cryptographic processes, the algorithm has to pass many reasonable tests of randomness. One such test is the Linear Congruential by Lehmer. It follows as such:

X_n + 1 = (aX_n + c) mod(m) where m > 0; 0 ≤ a < m; 0 ≤ c < m; 0 ≤ X₀ < m such that X₀ is the seed.

This equation is periodic which means the set of results will be the same over and over again, which can be a flaw. However, the key is to have a very large m, so that each cycle is very long. Ideally a good value for m would be 2³¹.

To have a robust pseudo random number generation process there are 3 criteria to pass:

1. Random appearance, via statistical tests that convey the confidentiality.
2. Full cycle such that all numbers should be used up before being repeated.
3. 32 bit arithmetic implementation.

To achieve a statically uniform and independent result, certain values of a, such as 7⁵, c = 0 and m being prime must be achieved, then the period is m - 1. Keep in mind, however, that the only truly random thing about this algorithm is the seed X₀. Afterwards, all of the subsequent numbers can deterministically be obtained. An opponent could realize the algorithm and if he knows the parameters he could know other subsequent numbers. However, all of the parameters don't even have to be known, just four X values and then via a system of linear equations, the opponent can solve for the other variables.

Blum Blum Shub Generator

The Blum Blum Shub generator is a popular pseudorandom bit generator described in the following equations:

p ≡ q ≡ 3 mod(4) where p and q are prime p such that mod(4) = q mod(4) = 3.

The following is the algorithm:

X0 = s2 mod z
for j from 1 to ∞ do
 Xi = (Xi-1)2 mod(z)
 Bi = Xi mod(2)
end for loop

Where z = p x q, s is a chosen random number but s has to be relatively prime to z. B_i is then the pseudorandom bit sequence. So, this algorithm does not allow a greater than 50 / 50 chance at guessing the k + 1 but after k because of the difficulty in factoring z, which classifies this as unpredictable as possible.

You're probably thinking about the seed. The more seeds and the more random they are the better and more random your sequences can be. One seed that is usually considered is the the system time and date.

Cryptographic Purpose

The more random a process or entity is, the less likely a pattern can be surfaced from it. There is an obvious inverted correlation between randomness and order. There is also a correlation between randomness and resources or overhead. Since a session key can be produced frequently it is important that it is done so as randomly as possible. Keys can be generated pseudo-randomly without dependency. Sub-keys cannot be feasibly deduced computationally via other sub-keys as long as the master key is protected. Additionally, stream ciphers must adhere to the principles of randomness. Other security processes make use of random numbers such as authentication with "nonces" short for number once. During handshaking nonces are used to prevent any kind of replay attack.

Links

http://world.std.com/~reinhold/truenoise.html
http://www.random.org/
http://www.NoEntropy.net/
http://www.geocities.com/cyberdiction/