Random numbers are very important to cryptography. The security of a cryptographic key depends on that key being difficult to reproduce, and random numbers make for hard-to-guess keys. But how can we be sure the output of a random number generator is truly random?
Random vs. Pseudorandom Numbers
Random number generation is a surprisingly old practice. One of the simplest examples is flipping a coin. Other methods include (with increasing levels of complexity) rolling dice, or shuffling cards, spinning a segmented wheel, or rolling marked ping-pong balls around in a giant can. Nowadays we use computers, which are able to produce a much higher degree of complexity, but not true randomness.
Pseudorandom number generators (PRNGs) are able to produce a series of numbers that approximate randomness, but are not truly random. Because PRNGs rely on a deterministic seed, it is possible to regenerate the key if you know enough about the generation process for it. For example, if the seed was the clock time when the number was generated, then to duplicate the generation process, you would just need to know what time it was generated.
Seeding schemes more complex than the clock example can increase the level of difficulty in reproducing a pseudorandom number, but they inherently lack true randomness. An attacker could potentially monitor the seed input for the PRNG at the system level, or input their own seed data so they know in advance every so-called "random" number that came out of it.
Truly random numbers are beyond hard to guess. They are numbers for which there exists no method of prediction. Cryptography revolves around making keys more and more difficult to guess. The more difficult it becomes to guess, the closer it is to true randomness, to real chaos.
True chaos is found in quantum mechanics.
Capturing Chaos For Uncrackable Cryptography
Peter Bierhorst is a professor at the University of Colorado Boulder who has been working on generation of truly random numbers as part of his work with the National Institute of Standards and Time (NIST). It's the government agency that keeps track of measurements and measuring.
The NIST is constantly concocting more machines and methods to measure more things, more accurately. They are the people who built the atomic clock, then built a better atomic clock because plus or minus a bajillionth of a second was just not precise enough.
Bierhorst and his colleagues published a paper describing how they produced certifiably random numbers through the observation and recording of the quantum state of a single photon. The team built a machine that emits a single photon at a time and records the photon's orientation as either a 0 or a 1.
Any given photon's quantum orientation is entirely unpredictable under the laws of quantum physics. In fact, its orientation is not even determined one way or another before it is detected. Generating a number in this way harnesses the natural chaos in the universe to achieve true randomness.
Amazing as that machine sounds, quantum random number generators based on photons have been built before. Quantum RNGs are readily available for purchase, though somewhat expensive. There are two things that make Bierhorst's RNG different:
- The machine is rather large, which is important due to communication distance. Any method of cheating the output data from the photon would require a signal that exceeds the speed of light. As far as we know, that is impossible.
- Bierhorst developed a method of proving that the input photon had not been tampered with. Not a method of making tampering difficult, but a mathematical proof that conclusively demonstrates tampering did not happen.
One downside is that the certifiably random quantum RNG is a little slow. It takes about 10 minutes to produce 1024 bits of true chaos.
Chaos As A Public Utility
One can begin to imagine commercial applications of this technology, like building it into every single electronic device. No doubt these will someday be developed. But as a researcher at the NIST, Bierhorst is not thinking about monetization. His plan is more like the approach taken with the atomic clock - turn the quantum RNG into a public service.
From here on out, we can power social anarchy with the inherent universal chaos that surrounds us.