Fast Generation of {RSA}-Moduli with Almost Maximal Diversity
Ueli Maurer
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.