 Strong primes

The RSA cryptosystem (§8.2) uses a modulus of the form n = pq, where p and q are distinct odd prunes. The primes p and q must be of sufficient size that factorization of their product is beyond computational reach. Moreover, they should be random primes in the sense that they be chosen as a function of a random input through a process defining a pool of candidates of sufficient cardinality that an exhaustive attack is infeasible. In practice, the resulting primes must also be of a pre-determined bitlength, to meet system specifications. The discovery of the RSA cryptosystem led to the consideration of several additional constraints on the choice of p and q which are necessary to ensure the resulting RSA system safe from cryptanalytic attack, and the notion of a strong prime (Definition 4.52) was defined. These attacks are described at length in Note 8.8(iii); as noted there, it is now believed that strong primes offer little protection beyond that offered by random primes, since randomly selected primes of the sizes typically used in RSA moduli today will satisfy the constraints with high probability. On the other hand, they are no less secure, and require only minimal additional running time to compute; thus, there is little real additional cost in using them.

• 4.52 Definition A prime number p is said to be a strong prime if integers r, s, and t exist such that the following three conditions are satisfied:
• (i) p - 1 has a large prune factor, denoted r;
• (ii) p+ 1 has a large prune factor, denoted s; and
• (iii) r - 1 has a large prime factor, denoted t.

In Definition 4.52, a precise qualification of “large” depends on specific attacks that should be guarded against; for further details, see Note 8.8(iii).

4.53 Algorithm Gordon’s algorithm for generating a strong prime

SUMMARY: a strong prime p is generated.

• 1. Generate two large random primes s and t of roughly equal bitlength (see Note 4.54).
• 2. Select an integer to- Find the first prime in the sequence 2it + 1, for i = i0, i0 + 1, io + 2,... (see Note 4.54). Denote this prime by r = 2it + 1.
• 3. Compute po = 2(sr_2 mod ijs — 1.
• 4. Select an integer jo. Find the first prime in the sequence p0 + 2jrs, for j = jo, jo + 1, jo + 2.... (see Note 4.54). Denote this prime by p = p0 + 2jrs.
• 5. Return(p).

Justification. To see that the prime p returned by Gordon’s algorithm is indeed a strong prune, observe first (assuming г ф s) that sr_1 = 1 (mod r); this follows from Fermat’s theorem (Fact 2.127). Hence, p0 = 1 (mod r) and p0 = -1 (mod s). Finally (cf. Definition 4.52),

• (i) p - 1 = po + 2jrs -1 = 0 (mod r), and hence p — 1 has the prime factor ?•;
• (ii) p + 1 = po + 2jrs +1 = 0 (mod s), and hence p + 1 has the prime factor s; and
• (iii) r — 1 = 2it = 0 (mod t), and hence r - 1 has the prime factor t.
• 4.54 Note (implementing Gordon’s algorithm)
• (i) The primes s and t required in step 1 can be probable primes generated by Algorithm 4.44. The Miller-Rabin test (Algorithm 4.24) can be used to test each candidate for primality in steps 2 and 4, after ruling out candidates that are divisible by a small prime less than some bound B. See Note 4.45 for guidance on selecting B. Since the Miller-Rabin test is a probabilistic primality test, the output of this implementation of Gordon’s algorithm is a probable prime.
• (ii) By carefully choosing the sizes of primes s, t and parameters г0, jo, one can control the exact bitlength of the resulting prime p. Note that the bitlengths of r and s will be about half that of p, while the bitlength of t will be slightly less than that of r.
• 4.55 Fact (running time of Gordon’s algorithm) If the Miller-Rabin test is the primality test used in steps 1,2, and 4, the expected time Gordon’s algorithm takes to find a strong prime is only about 19% more than the expected time Algorithm 4.44 takes to find a random prime.