Cryptography

16 Generation of Pseudorandom and Prime Numbers for Cryptographic Applications

As emphatically underlined in previous chapters, random numbers (RNs) and prime numbers (PNs) play a fundamental role in cryptography. In particular, cryptographic keys and nonces used in some cryptographic algorithms shall appear as entirely random bit-strings for observers (i.e. attackers).

In general, there exist two basic strategies for generating random numbers: non-deterministic and deterministic strategies. In the first category, a physical process is used to generate bit sequences, while in the second category, an algorithm is used. Non-deterministic RN generators produce true RNs, while deterministic RN generators produce pseudo RNs. The second category of RN generators is the most dominant in computer-based systems and are built using deterministic random bit generators (DRBGs). The latter are algorithms that output random bit-strings, which mainly depend on an initial input called seed. Therefore, the outputs of DRBGs are pseudorandom bit-strings instead of true random ones. Even if the algorithm of a DRBG is known, when the seed is picked from a (very) large set and kept secret, the DRBG output is very likely to be unpredictable and looks like a random value.

Pseudorandom bit-strings are also called pseudorandom numbers and DRBGs are referred to as Pseudo Random Number Generators (PRNGs). The first part of this chapter addresses basic and recommended algorithms to generate pseudo RNs. ...