3.7 Randomness and entropy

In cryptography, the security of most protocols and mechanisms depends on the generation of random sequences of bits or numbers. These sequences must have a sufficient length and be random in a very specific sense: we do not want an attacker to be able to guess part of or the whole sequence. To make this idea more precise, cryptographers use the concept of entropy.

You might be familiar with the notion of entropy from physics. There, entropy is a fundamental property of any complex system and, loosely speaking, describes the tendency of such systems to disorder. As an example, take a gas being injected into a container. At first, the gas particles will still be clustered closely together. But as time passes by, the gas particles will float around and distribute themselves randomly within that container. They do so because the latter configuration offers more possible states (i.e., locations and velocities) for the gas particles; in other words, the entropy of...