Tikalon Blog by Dev Gualtieri

Tikalon Header

One Time Pads

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.

Middle-square pseudorandom number generator

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:

X_n = (aX_n-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 = 2⁶⁴.

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 die faces

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 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,' by Landon Curt Noll, Robert G. Mende and Sanjeev Sisodiya, March 24, 1998.

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 optical scattering.

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: