Entropy – From Pseudo Randomness to Quantum RNGs
What is entropy and why do we need it in security and cryptographic systems?
Let us start at the beginning: In information theory terms, entropy, called also Shannon’s entropy, measures the unpredictability of a message generated by a specific source. We can also say it measures the randomness of a message. In a scenario where we want to hide information from an attacker, we want the randomness to be as high as possible. Ideally, the encrypted message should contain no patterns, each bit should be completely independent of all others so that it becomes impossible to predict or modify its contents.
In order to achieve that, the encryption key which is the source of the message’s randomness should have high entropy as well, meaning that a high-quality source of randomness needs to be used for its generation procedure. There are two main ways how a cryptographic system can generate randomness.
The first one is the implementation of pseudo randomness. As the name already suggests, this method can achieve a high level of randomness, but not true randomness. It uses a deterministic algorithm called PRNG (pseudorandom number generator) or DRNG (deterministic random number generator).
The difference between the quality of pseudo and true randomness can be quickly seen by comparing the two pictures below . The left one demonstrates the output of a true random number generator (TRNG), the right one the output of a PHP PRNG function rand() on Microsoft Windows. On the right picture even a human eye can detect unwanted patters.
These pictures also explain the famous quote by mathematician John von Neumann in 1951: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
In order to achieve true randomness a hardware component is needed. TRNGs derive random numbers or bits from various physical processes. A few examples of them are atmospheric noise, which a radio can detect, thermal noise an electrical conductor generates, and, surprisingly, even movement of hot wax in lava lamps.
Compared to PRNGs, TRNGs are usually noticeably slower and take more time to produce random values, since they rely on reading and evaluating external processes. As already mentioned, they are also non-deterministic and have no period, although the same sequence of numbers can be produced several times by chance.
As our understanding of quantum mechanics slowly increases, a new group of TRNGs has started appearing some years ago - Quantum random number generators (QRNG). Instead of taking advantage of classical random properties, these generators rely on quantum properties instead. Utimaco’s partner, QuintessenceLabs, for example first used lasers but later switched to a much more effective method of Quantum tunneling. Their QRNG presently has a rate of 1 Gbit/s. Some other quantum phenomena that can be exploited to generate perfect randomness are photons travelling through a semi-transparent mirror, and nuclear decay.
If you are interested in reading more about the impact of quantum mechanics and quantum computers on the world of security and cryptography, there is a previous blog post, What Are the Threats of Quantum Computing?, dedicated to this topic.
Prepared by Nastja Cepak, PhD Cryptography, CREAplus