Prime Number Generation and RSA Keys
Marc Jóye, Pascal Paillier · 2025
Numerous cryptographic primitives rely on prime numbers, a good representative being the RSA cryptosystem used for encryption or digital signatures. The output distribution of the primes that are generated also matters. In 2012, two independent teams of researchers collected RSA public keys from a wide variety of sources. Quite surprisingly, a non-negligible fraction of the collected RSA moduli exhibited a common prime factor. Sharing a common factor for non-duplicate RSA moduli completely compromises the security as calculating their greatest common divisor reveals the secret factors and thus enables computing the private keys. Primality testing has been an active research topic for many years. Computationally, two types of outputs are distinguished by nature: true primes and probable primes. The difference rests in the way these are generated. A probable prime (also known as pseudoprime ) is usually obtained through a compositeness test, which is typically weaker but faster than a primality test.