Random numbers are used extensively within encryption techniques, particularly for generation of keys. As the key is primarily the guardian of your data, it is vital that it is truly random to ensure it can't be guessed or determined by frequency analysis (or other methods).

This is particularly important for block cipher algorithms which use the same key over and over again on successive blocks of data !

This section explains how random is not necessarily random, and how there are different types of randomness for different applications :)

It also presents a hardware circuit which is cheap to build that can be used for the generation of cryptographically secure random numbers of any length.

During my career I spent several years researching noise, in particular fundamental types of random noise distributions. From these studies, I would like to explain the true nature of randomness, and more importantly, what a cryptographer needs to consider when choosing an anlogue random source.

I am sure that many cryptographers might not understand the subtle differences, and this is by no means any criticism to the experienced cryptographer. The study of randomness is a different discipline. I have found references on many web sites detailing a few ways to generate random numbers from analogue methods. Not all of these have been accurate.

I have had several articles published in peer reviewed journals on the concept of randomness, particularly in the field of electromagnetic radiation sources. I would like to share this information in the hope that cryptographers might benefit from this.

One other thing to point out. If you look at any web sites (or books) which discuss random numbers and cryptography...Be careful !

If the article was written more than two years or so ago, then it might make recommendations for randomness that are not strong enough to survive current methods for breaking keys.

Readers of this site might think I have gone way over the top with this section on randomness, but as this is the heart of cryptography, I think it deserves as much attention, if not more than the encryption algorithms themselves.

2 Different types of Randomness

It might come as a bit of a surprise, but the cryptographers definition of random is not necessarily the same as that of physicists and mathematicians !

The cryptographer ideally wants a stream of random numbers that are known as uniform deviates. The easiest way to explain this is to consider a range of numbers, say 1 to 1 million. For an ideal uniform random number generator based on this number sequence, the generator should produce an output stream that generates numbers between 1 and 1 million in an arbitrary fashion with no sequence as to the numbers. The same number should never come out twice until all 1 million values have been generated. An ideal uniform generator should also never produce the same sequence of numbers if it is run several times.

There are various statistical tests that can be applied to a series of random numbers to test just how random they are. These will be discussed in Part 7 of this section.

Obviously, the cryptographer wont usually want a range of numbers that fall into the category of 1 to 1 million, but will be more likely to require either a stream of random bits, or bytes. The principle remains the same, ie that there should be no statistical distribution of generated numbers.

It is actually quite difficult to devise a practicable uniform random number generator as we will see later.

So what does the Physicist or Mathematician understand by random ?

In addition to recognising uniform deviates (ie without a statistical distribution), Physicists and Mathematicians also categorise randomness as occurring within known statistical distributions.

This might seem to be a contradiction, but it can be explained as follows.

Let us take a typical example of naturally occurring randomness which conforms to a distribution.

When you switch on a light in your own home, you get a certain "level" of light. If you use a light bulb of a higher or lower wattage, then the level of light increases or decreases. However, regardless of the wattage bulb you use, the apparent light level remains constant (assuming your electricity supply is stable).

The level of light is not actually constant, but fluctuates slightly. These fluctuations are known as noise, and are so small that they are indistinguishable to the human eye.

However, they do occur and are measurable with a photodiode and suitable circuitry. This effect is known as Shot Noise and is due to the discrete nature of radiation, which is composed of photons arriving randomly in time.

It can be shown however that although the photons arrive randomly in time, thus leading to small fluctuations in the apparent (or mean) light level, this randomness actually has a statistical distribution.

If you were to measure such variations, you would see that certain levels occur more often than others, although it is impossible to predict which level will occur next (hence the randomness). The distribution is known as gaussian.

There are other random sequences that conform to statistical distributions such as the binomial, 1/f etc.

If a random sequence conforms to a statistical distribution, then obviously it is not as secure as a random sequence which has no distribution.

Obviously, as far as cryptography is concerned, it is important when choosing a random number generator, that the type of random distribution is understood to be of the uniform kind, or at least has a fairly "flat" distribution. We will be discussing this further within this section to explain how random numbers are generated and what to look for to ensure cryptographic security.

3 Pseudo Random Number Generators

Anyone who has ever used a high level programming language such as C or Basic will probably have noticed that such languages have a built in random number generator.

However, these are not cryptographically secure and you should refrain from using them within your own programs. As far as ANSI C is concerned, then I would advise against using such inbuilt routines for anything !

The routines work by calculating a long sequence of "so called" random numbers. When calling the routine, you need to start the position in this chain with what is called a seed number. After that, the routines spit out a sequence of numbers starting from the seed position.

There are many problems with this. First of all, the overall sequence is fixed, so multiple calls with the same seed starting value will produce the same sequence of so called random numbers.

Second, then in the case of ANSI C (and probably many other languages), the routine only returns a two byte value, hence the maximum number of random numbers you can get is -32768 to 32767. That's hardly secure at all !

Thirdly, and more important...such pseudo random number generators are based on known mathematical routines, so the sequences can be found quite easily.

There have been many other routines devised to get round the -32768 to 32767 limit, but all software only algorithms still have the problem in that they produce a sequence of numbers that conform to a mathematical equation, and hence can be broken quite easily.

Stay clear of all software only routines if you want your data to remain secure.

I wont even discuss any of the more advanced software only routines within this section as they can't be used for strong cryptography. The following sections discuss other ways to generate random numbers that are cryptographically secure.

4 Analogue Random Uniform Generators

So how can we generate a truly random uniform number from an analogue source ?

There are several designs on the market, but be aware, not all (if any) are truly random in the uniform sense.

It might seem surpising, but there are not many phenomena that exhibit truly random behaviour in the uniform sense.

OK, so you've got the likes of Brownian Motion (first discovered by Thomas Brown) which appears to be random, however Einstein later showed the phenomenon to obey definite statistical laws devised by Boltzman and Maxwell.

There are some truly random events such as background cosmic radiation levels and light scattering phenomena from interstellar dust, but these aren't exactly easy to measure to use as a random number generator !

So how can you get a truly uniform sequence ?

By taking a sequence which has symmetry, it is possible to convert this into a uniform sequence as we will see later on in this section.

5 Analogue Random Gaussian Generators

There are many easy ways to generate a random sequence that has a gaussian distribution. For example, we have already stated that a light bulb (given a suitably regulated power supply) generates random noise that conforms to a gaussian distribution.

This also applies to LED's, lasers etc.

However, the cheapest way of generating a gaussian random sequence is to go out and buy a resistor of high ohmic value. This will cost around £0.05, that's right 5 pence !

Anything with resistance generates what is called Thermal or Johnson Noise due to agitation of electrons caused by temperature effects. The distribution conforms almost perfectly to a gaussian distribution.

Given a high gain amplifier and some frequency limiting, it is easy to generate a dynamic true gaussian random voltage from this.

I have seen many references that advocate the use of a soundcard without a microphone attached to produce a random sequence based upon thermal noise. However, as the frequency range of the soundcard is typically 100Hz to 40KHz, this encompasses the 1/f range of randomness and should be avoided as it skews the distribution, thus causing asymmetry and other problems due to the convolution of multiple probablitity density functions. The technique also has other problems in that the A/D convertors used often have predictable problems in converting the noise source into a number.

Team up an electronics engineer, a statistician and a cryptologist and they will soon break a key devised from this method !

We will be using a resistor as the basis for a cheap hardware based random number generator later on in this section.

6 Converting Gaussian to Uniform

OK. If we take a gaussian random number generator, we end up with a series of numbers that have a mean value if we plot its' probability density function (PDF). A sketch of the PDF would look something like this :-

Anyone who has studied statistics at college will recognise this as a normal distribution and will realise that 68% of all values lie within plus or minus one standard deviation from the mean, through to 99.997% of values lying within four standard deviations from the mean.

However, it has symmetry, so all we need to do to convert this gaussian sequence into a uniform sequence is to look to see if a value is less than or greater than the mean and assign a zero or a one to obtain a uniform random binary sequence.

It is made easier in our case if we use thermal noise from a resistor, and AC couple it so the mean is always zero. We can then use a comparator circuit to give us our binary sequence that can be read in directly through a serial or parallel port, thus obviating the need for an A/D convertor (which would immediately turn our random sequence into a non-random sequence due to the limitations of such devices).

7 Test Procedures for Randomness

8 Analogue Random Uniform Circuit

9 Test Results for the Design