Random Number Generation: Types and Techniques

Case Study: RSA Key Generation 

 

Encryption means nothing at all if the random number generators it relies on are 

poorly constructed. This fact became relevant on a global scale when a standard for 

encryption named RSA was shown to be predictable in some cases. RSA is a public-key 

algorithm that uses secret prime values to compute a modulus n. This n value used in 

both the encryption and decryption of messages, and security relies on its prime factors 

remaining secret. The range of possible prime numbers is large enough that they should 

never be reused or guessed. However, researchers found that they were able to remotely 

break the encryption on .4% of all the RSA signed certificates in their study, which 

included 5.8 million samples (Lenstra, et al., 2012). To break the encryption, researchers 

simply needed to use the Euclidean algorithm on all the samples to see if any of them 

shared a common factor in the modulus. If they did, then both of the RSA certificates 

could be broken, because the prime numbers were discovered. After studying the problem 

with RSA, the researchers found that its root was in the random number generators being 

used for these certificates. The repeated primes were mostly isolated to cases where the 

RSA certificate was created by an embedded device, such as a firewall, router, or printer. 

These devices typically do not have enough entropy to create unpredictable prime 

numbers. Also, devices from the same manufacturer likely have the same starting 

---

RANDOM NUMBER GENERATION                                                                             21 

 

condition for their generators, meaning that the first random numbers produced will be 

similar. Therefore, when these devices were used to create random prime numbers a 

couple primes were frequently repeated. That allowed the attackers to do their pair-wise 

comparison of certificates and break the resulting encryptions. This phenomenon 

reinforced the fact that strong random number generators form the backbone of modern 

cryptography.