Where do key generation algorithms take the randomness from?

Question

I was just wondering, because in many encryption tools like Veracrypt or GnuPG you have to generate pseudo randomness with your mouse movement. So, where do automatically generated keys take that randomness from? For example, when you generate a RSA certificate with OpenSSL.

Answer 1

Applications that generate key get the randomness (entropy) from the operating system. The operating system, in turn, gets the randomness where it can find it. Ideally the OS gets randomness from a proper hardware generator, which is present in modern PC and smartphone processors. These hardware generators are based on physical phenomena that are not reproducible; a variety of techniques exist. Additionally, the OS accumulates randomness through the timing of user actions (such as moving the mouse), of network packets, of disk reads, etc. White noise from a microphone or camera can also provide randomness. The difficulty with such ad hoc sources is that it's difficult to estimate how random they are: a hard disk's timing is predictable in theory (and an SSD much more), a given user tends to act in broadly similar manners, a sensor may be saturated, etc. This is why a dedicated hardware generator is preferable, assuming that it's programmed and used properly.

Hardware randomness sources are never used directly, because they tend to have strong biases: they don't come in neat bits that have an even chance of being 0 or 1. The randomness is fed through a cryptographic algorithm called a pseudorandom number generator (PRNG) which produces a practically endless stream of uniformly random bits from a small amount (hundreds of bits) of entropy.

Operating systems have a useful tool to reduce the expense of collecting entropy: entropy doesn't wear out, so it can be saved and reuse. An operating system can save the state of the random generator and, at boot time, load it, generate a new state and save that. This way, as soon as there has been sufficient entropy once, there is sufficient entropy forever on that machine.

Applications such as Veracrypt, GnuPG, etc. ask the OS for randomness. On Linux, they can read /dev/random or /dev/urandom, or call the getrandom system call (the differences between those are beyond the scope of this answer). On Windows, the system call is CryptGenRandom. Other operating systems designed to support cryptographic applications have similar interfaces.

Applications almost always use the OS's random generator as a seed for their own PRNG. This is cryptographically safe and improves performance.

Why do some applications ask you to move the mouse? There are several reasons:

• In case the OS doesn't have as much entropy in its random generator, this improves the situation a bit.
• Some applications were written for 20th century operating systems that lacked a random generator interface (e.g. Windows 9x) and needed to collect their own entropy.
• As you can witness, it gives the user a warm fuzzy feeling that they're getting something really random. It's actually mostly for show.

Answer 2

The OpenSSL library provides a number of software based random number generators based on a variety of sources. Software based RNG (Random Number Generators) generate random numbers by executing software algorithms. For this purpose a number of algorithms is specified by standard bodies including NIST, ANSI X9 committee and XXX. OpenSSL furthermore allows the inclusion of your own RNG hardware if the hardware you want to use offers an ENGINE interface. Recent OpenSSL versions that run on Unix-like operating systems try to seed their RNG using /dev/random, /dev/urandom and EGD. The /dev/random source is a special file that serves as a blocking pseudorandom number generator which allows access to environmental noise collected from device drivers and other sources. But note that OpenSSL does not try to estimate how much entropy its RNG has. It is up to you to ensure that it has enough before the RNG is used.

In general you can say that truly random numbers are quite hard to produce from deterministic processes such as a computer that executes instructions. The lower the entropy of your system, the harder it is to create truly random numbers suited for cryptographic applications. This seems to be a huge problem in embedded systems and applications which often have a deterministic start-up behavior in regard to memory content or peripherals for example.

As mentioned creating good random numbers requires an adequate level of entropy. The example you provide collects some of its entropy from a user's mouse movement which is thought to be quite random. If you don't want to shout into your microphone or move your mouse for every key you need to generate, there is also the option to use hardware modules. Nowadays these can be acquired quite cheaply (starting in the two-digit range). The company I used to work for example used a hardware random number generator which made use of the fundamentally random nature of quantum optics as a source of true randomness. It was USB-interfaced an allowed random data streams with a speed up to 16 Mbps. We used that hardware as an ENGINE for OpenSSL to create our ECC and RSA keys.