FAST GENERATION OF PRIME-NUMBERS AND SECURE PUBLIC-KEY CRYPTOGRAPHIC PARAMETERS

A very efficient recursive algorithm for generating nearly random prov able primes is presented. The expected time for generating a prime is only slightly greater than the expected time required for generating a pseudoprime of the same size that passes the Miller-Rabin test for on ly one base. Therefore our algorithm is even faster than algorithms pr esently used for generating only pseudoprimes because several Miller-R abin tests with independent bases must be applied for achieving a suff icient confidence level. Heuristic arguments suggest that the generate d primes are close to uniformly distributed over the set of primes in the specified interval. Security constraints on the prime parameters o f certain cryptographic systems are discussed, and in particular a det ailed analysis of the iterated encryption attack on the RSA public-key cryptosystem is presented. The prime-generation algorithm can easily be modified to generate nearly random primes or RSA-moduli that satisf y these security constraints. Further results described in this paper include an analysis of the optimal upper bound for trial division in t he Miller-Rabin test as well as an analysis of the distribution of the number of bits of the smaller prime factor of a random k-bit RSA-modu lus, given a security bound on the size of the two primes.