# Cryptographic random numbers for key generation

I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are a lot of questions regarding the generation of random primes, but I'm interested in the generation of a random number. There seem to be some official guidelines by the government (for example, NIST FIPS 186-4 (PDF) is referred to in a couple of other answers to questions about random prime generation) for the generation of keys for certain protocols, but they are not an easy read and I don't think they answer my questions.

I think I understand the basic principles: Entropy is gathered by the operating system or a daemon to provided a small amount of unpredictable data that is used as a seed for a cryptographically secure pseudo-random number generator (CSPRNG). The CSPRNG generates the random numbers that are used to generate random primes (either a probable or provable prime).

What is a good CSPRNG? I couldn't find the algorithm that OpenSSL uses (it's very well possible that there are multiple). Wikipedia lists a bunch, but doesn't provide sufficient information on implementation and performance.

Also, are there any additional constraints on the prime or prime pair that is generated? I vaguely remember reading something about prime products of a certain form that are no good for use in cryptographic keys (because they are easy to factor with some tricks).

• CSPENG: Fortuna. IIRC "big enough" means something around twice the length of the security level. You don't need strong primes, random primes are kina likely to be strong (enough) primes but you're on the safe side if you use them. Aug 9, 2015 at 21:46
• Ah, I should have read the wikipedia page more carefully. Shame I only read it after I posted the question. Apearently it is not useful to pick strong primes and one should pick large enough primes instead, see crypto.stackexchange.com/questions/1151/…. Can you provide a little more information about Fortuna? Why do you name that one? Is it the most commonly used CSPRNG, or the one that OpenSSL uses? Aug 9, 2015 at 22:39
• That's the one for OpenSSL. Note that I've come to understand that - depending on the platform - OpenSSL's random functions may be tricky to trust. Aug 10, 2015 at 0:15
• Many cryptographic libraries utilize the operating system RNG, which you may or may not trust, I wrote a wrapper around the OS RNG specifically for key generation, under the assumption that it is possible to compromise the OS RNG to generate poor entropy or predictable values Aug 10, 2015 at 6:54
• @RichieFrame very interesting. is your wrapper for your private use or free to use? Aug 11, 2015 at 11:44

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key from in the first place. Typically, there is a source of entropy. This is turned into (almost) uniform randomness (a.k.a. a key) using a randomness extractor. In cryptographic applications, this is often achieved by just applying a hash function like SHA256 to the source.

When OpenSSL is run in Linux, it takes its initial random source from /dev/urandom. This is already a problem since /dev/urandom (unlike /dev/random) is not blocking, which means that it provides randomness even if the Linux entropy pool is empty. What makes it worse is that OpenSSL does not reseed if the entropy pool was originally low.

I just heard an interesting talk at BlackHat 2015 about this. The above claim about OpenSSL is based on their analysis of the code. You can see more information in their PPT and white paper (I don't agree with everything they say but it's very informative and good work).

I suggest that you reseed the OpenSSL generator yourself (using rand_seed) either by calling /dev/random yourself (you can query to see if the entropy pool has enough randomness in order to prevent blocking; use the command: # cat /proc/sys/kernel/random/entropy_avail), or by using RDSEED, which is a hardware generator inside all Intel chips from Ivy Bridge. See (https://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed for more info.)

It seems that due to Snowden fears, Linux does not use RDSEED. My opinion is that it should certainly be used, at least to add randomness to the OpenSSL generator.

One final note: if you generate a new process to check the available entropy, then you will modify the pool. It seems that the Linux operating system using 256 bits of randomness from the pool every time a process is generated (for random memory allocation etc.). This is huge overkill and means that the entropy sorely needed for crypto applications may be exhausted for things that don't need real randomness. Anyway, that's life. So, if you want to constantly poll, then generate a single process that will periodically check entropy_avail, and don't generate a new process every time.