Fast Generation of {RSA}-Moduli with Almost Maximal Diversity

This paper describes a new method for generating primes together with a proof of their primality that is extremely efficient (for 100-digit primes the average running time is equal to the average time required for finding a "strong pseudoprime" of the same size that passes the Miller-Rabin test for only four bases), that yields primes that are nearly uniformly distributed over the set of all primes in a given interval, and that is easily modified to yield (with no additional computational effort) primes that are nearly uniformly distributed over the subset of these primes that satisfy certain security constraints for use in the RSA cryptosystem. This method is used to generate, for a given encryption exponent $e$, an RSA-modulus $m=pq$ that is nearly uniformly distributed over all secure RSA-moduli in a given interval $I$, i.e., over the set of all integers in $I$ that are (1) the product of exactly two primes $p$ and $q$ none of which is smaller than a given limit $L$, where (2) $(p-1,e)=(q-1,e)=1$ and (3) $p-1$ and $q-1$ each contain a prime factor greater than a given limit $L'$, and where (4) for all but a provably (given) small fraction of plaintexts in $Z_{m}^{*}$, the minimum number of iterated encryptions with exponent $e$ required to recover the plaintext, is provably greater than a given limit $M$. Our method exploits a well-known result due to Pocklington \cite{pock} that allows one to prove the primality of $p$ when only a partial factorization of $p-1$ is known. These prime factors of $p-1$ are generated by recursive application of the prime generating procedure. Although the discussion is centered on the RSA system, our method can of course be used in other cryptographic systems, such as the Diffie-Hellman public key distribution system, that require large primes satisfying certain security constraints.