| Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
|
This article |
| Directory of all articles |
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.
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:
- 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."
- 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.
- Roarke Horstmeyer, Benjamin Judkewitz, Ivo Vellekoop and Changhuei Yang, "Physical key-protected one-time pad," arXiv Preprint Server, May 16, 2013.
- One-Time Pad Reinvented to Make Electronic Copying Impossible, Physics arXiv Blog, Technology Review, May 20, 2013.
- Tony Warnock, "Random-Number Generators," Los Alamos Science (Monte Carlo Special Issue, 1987), pp. 137-141 (PDF file).
- Laszlo Hars, "Random Topics," SummerCon (June 11-13, 2004, Pittsburgh, PA).
Permanent Link to this article
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.