June 12, 2013

There's a notable Dilbert cartoon, published on October 25, 2001. In this cartoon, our geek protagonist, Dilbert, is touring the Land of the Accounting Trolls. He's introduced to their random number generator, a troll who repeatedly says, "nine." Dilbert questions whether this is truly random. His troll tour guide says, "That's the problem with randomness - You can never be sure."[1]

As the Dilbert cartoon illustrates, true randomness is hard to quantify. Every programming language has a random number function, but the idea that an algorithm can give you something random is flawed at a fundamental level. There's a famous quotation by computer pioneer, John von Neumann, that
"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method."
Since random numbers are important in computer simulations, such as the Monte Carlo method, von Neumann went against his own advice and developed a simple pseudorandom number generator, called the middle-square method, which was useful in the early days of computing.

Unknown to von Neumann, but known to the present readers of Wikipedia, this simple method of generating pseudorandom numbers was invented by Brother Edvin, a Franciscan friar, circa 1245. There are two problems with this method, but they're fortunately very apparent when they happen.

The first is when the middle digits become all zeros. After that point, the generator output is always zero. The other problem is that the generator can enter a mode in which it outputs the same short sequence, over and over.

 An example of the middle-square pseudorandom number generator. A six digit seed is selected. This is squared, the middle of six digits are selected, to be squared again. The six digit numbers are the random sequence. Note that we always drop the three digits at the right and pad zeros on the left. (Rendered by the author using Inkscape.)

Another simple random number generator is the linear congruential generator, a recurrence relation published by D.H. Lehmer in 1948, as follows:
Xn = (aXn-1 + c) mod m
This generator gives a long list of pseudorandom numbers when proper values are selected for a, c and m. Computer scientist, Donald Knuth, prefers to use
a=6364136223846793005, c=1442695040888963407, and m = 264.
The choice of a power of two for m simplifies the modulus operation.

These are just two examples of many simple pseudorandom number generators proven to be useful in the early days of computing when processors were slow and memory was small. Since we now have fast computers, we can be more creative with our pseudorandom number generators. One example of a more elaborate generator is the Mersenne twister; which, as its name implies, involves the Mersenne primes. Aside from that fact, it's somewhat hard to describe, but it's used as the random number generator in Python, PHP, and some other programming languages.

Most random number generators are suitable for computer simulations if we're careful to select those with sufficiently large periods. Cryptographic randomness is another case entirely, since the common pseudorandom number algorithms we might use in our cipher will be known also to our adversaries. Certain regularities in the output of such algorithms offer a signature of what method we might be using.

Physical random number generation is an alternative to algorithmic generation. The simplest of these is casting dice, but this method is slow and tedious.

 Six dice will generate random numbers from 111,111 to 666,666, which could be scaled to the range, 0 to 555,555. Each die, of course, needs to be assigned to a decimal place. (Illustration by the author.)

There are quite a few electronic physical random number generators, some of which are based on the white noise inherent in analog electronics, and some take as an input the environmental noise from Geiger counters and radio receivers. In a previous article (Random Computing, July 26, 2010), I wrote about Intel's demonstration of harvesting the randomness inherent in the transition between low voltage (digital "0") and high voltage (digital "1") states of transistors in integrated circuits.

As I described in another article (Quantum Random Numbers, September 27, 2010), a more exotic physical random number generator was built by researchers at the Max Planck Institute for the Physics of Light (Max-Planck-Institut für die Physik des Lichts) in Erlangen, Germany. Their device optically harvests the randomness from the virtual processes in the quantum foam of the vacuum state.

One novel physical random number generator is Lavarand, created by Silicon Graphics. In what might be called a merger of art and algorithm, random numbers were generated from images of active lava lamps. Silicon graphics hosted a web site for the technique in the late 1990s, but the web site is no longer active. The method is described in US Patent No. 5,732,138, "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system."[2]

 Figure three of the Lavarand patent.[2] (Via Google Patents.)

The simplest way to encrypt a message is through use of a one-time pad, which is just a list of random numbers. If these are binary numbers, an exclusive-or (XOR) is used to encode your binary message, and another application of this XOR operation conveniently decodes it. If the sender and recipient have a "pad" containing the random number list, encoding and decoding is easy.

The "one-time" designation means that such a random number list should be used only once. If that's true, then the cipher is unbreakable. Of course, this means that both sender and receiver need many such random number lists (their "pads"). In the case of extended message (digital files, for example) these pads would just be used to seed a random number generator, as in the Lavarand system.

A team of scientists and engineers from the California Institute of Technology (Pasadena) and the University of Twente (Enschede, the Netherlands) have developed a novel one-time pad using the scattering of light in a material.[3-4] In their experiments, a spatial light modulator is used to shine random light patterns through an opal diffusion filter to generate about 10 gigabits of random numbers.

 Apparatus for one-time pad generation using light scattering.Fig. 2b of ref. 3, (Via arXiv.)[3]

In theory, a terabit of random numbers could be extracted from a cubic millimeter of such material; and, annealing will change the material's microstructure and reset it to create a new pad.[4] The glass cannot be duplicated, and its data content would take an extremely long time for an eavesdropper to copy, so it would be apparent that the piece was missing.[4]

The system is a public key cryptography system in which the communicants meet to shine the same random patterns through their diffusing glasses to create a series of combined keys. The combined keys and their random generators are published, but only the two communicants can use their glasses and this information to send and receive coded messages.[4]

As long as the communicants keep possession of their glass, the system is secure. More interestingly, it should be secure against cryptanalysis by future quantum computers.[4] However, this is true for any one-time pad; and, as more than one Internet commentator has stated, the real novelty is the system's convenient way to generate and store one-time pads.

### References:

1. This cartoon may have been inspired by the Beatles composition, Revolution 9, which appeared on their white album. This experimental music track has a male voice repeatedly saying, "number nine."
2. Landon Curt Noll, Robert G. Mende and Sanjeev Sisodiya, "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system," US Patent No. 5,732,138, March 24, 1998.
3. Roarke Horstmeyer, Benjamin Judkewitz, Ivo Vellekoop and Changhuei Yang, "Physical key-protected one-time pad," arXiv Preprint Server, May 16, 2013.
4. One-Time Pad Reinvented to Make Electronic Copying Impossible, Physics arXiv Blog, Technology Review, May 20, 2013.
5. Tony Warnock, "Random-Number Generators," Los Alamos Science (Monte Carlo Special Issue, 1987), pp. 137-141 (PDF file).
6. Laszlo Hars, "Random Topics," SummerCon (June 11-13, 2004, Pittsburgh, PA).

Linked Keywords: Dilbert cartoon, published on October 25, 2001; cartoon; geek; Dilbert; Accounting Troll; random number generator; troll; randomness; random; programming language; algorithm; John von Neumann famous quotation; John von Neumann; computer simulation; Monte Carlo method; pseudorandomness; pseudorandom number generator; middle-square method; history of computing hardware; early days of computing; Wikipedia; generating pseudorandom numbers; Franciscan friar; sequence; seed; square; numerical digit; Inkscape; linear congruential generator; recurrence relation; recursive relation; Derrick Henry Lehmer; D.H. Lehmer; computer scientist; Donald Knuth; power of two; modulus operation; central processing unit; CPU; memory; Mersenne twister; Mersenne prime; Python; PHP; programming language; random number generator attack; cryptographic randomness; cipher; physical random number generation; dice; decimal representation; decimal place; electronic; white noise; analog electronics; natural environment; environmental; noise; Geiger counters; radio receiver; Intel; voltage; transistor; integrated circuit; research; researcher; Max Planck Institute for the Physics of Light; Erlangen, Germany; quantum foam; vacuum state; Lavarand; Silicon Graphics; art; lava lamp; US Patent; Google Patents; one-time pad; binary number; exclusive-or; XOR; computer file; digital file; scientist; engineer; California Institute of Technology (Pasadena); University of Twente (Enschede, the Netherlands); scattering of light; material; experiment; spatial light modulator; opal; diffusion filter; gigabit; arXiv; terabit; cubic millimeter; annealing; microstructure; eavesdropper; public key cryptography; key; cryptanalysis; quantum computer; Internet; Revolution 9; white album; Landon Curt Noll, Robert G. Mende and Sanjeev Sisodiya, "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system," US Patent No. 5,732,138, March 24, 1998.

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books