# Where do key generation algorithms take the randomness from?

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.

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.
• Very good answer, but about apps that ask you to "move the mouse": In famous Debian CSPRNG predictability those applications managed to be safe from that mistake. So it might be all for fun and giggles until OS PRNG turns out to be broken. – axapaxa Apr 24 '17 at 23:53
• @axapaxa No, the infamous Debian bug was in the application, not in the OS. The RNG in the OS was working perfectly fine, what the application did was to fail to read it. Moving the mouse wouldn't have helped unless the application happened to read entropy from separate sources (as opposed to what most mouse-wiggle-requesting applications actually do, which is to let the OS collect entropy), to have this bug when reading entropy from the OS and not when reading entropy from another channel. – Gilles 'SO- stop being evil' Apr 24 '17 at 23:56
• @axapaxa It's actually a bad idea for an application to try to do its own mouse wiggling entropy gathering, because of the risk of such bugs. The more complex the code, the higher the risk of bugs. – Gilles 'SO- stop being evil' Apr 24 '17 at 23:57
• You are right, bug wasn't in OS but in OpenSSL shipped with Debian. Moving mouse would have helped when application collects it on it's own entropy (which was my assumption! - otherwise it's pointless). The more complex the code the higher risk of bug - agreed. But I don't agree that such thing is pointless, because your implementation will always be less complex than OS/OpenSSL, right? So IMO it ain't pointless, it's security in depth. – axapaxa Apr 25 '17 at 10:13
• @axapaxa It's difficult for an application to collect entropy from mouse movements, and an application that doesn't access the GUI can't do it at all. Your implementation may be less complex than the OS but it's reviewed by fewer people and probably written by people with less expertise. Adding security checks is security in depth. Adding countermeasures is not always security in depth, it can be counterproductives when these countermeasures are buggy. – Gilles 'SO- stop being evil' Apr 25 '17 at 11:49

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.

• ok thank you , but what is the default source for randomness in OpenSSL ? – Richard R. Matthews Apr 24 '17 at 19:21
• According to the Debian weak key summary, the default setting of openssl is to use /dev/urandom plus the process ID. – mat Apr 25 '17 at 14:18