One implementation of this method on a Sparc II was able to find 256-bit primes in an average of 2.8 seconds, 512-bit primes in an average of 24.0 seconds, 768-bit primes in an average of 2.0 minutes, and 1024-bit primes in an average of 5.1 minutes [918].

Strong Primes

If n is the product of two primes, p and q, it may be desirable to use strong primes for p and q. These are prime numbers with certain properties that make the product n difficult to factor by specific factoring methods. Among the properties suggested have been [1328,651]:

The greatest common divisor of p - 1 and q - 1 should be small.

Both p - 1 and q - 1 should have large prime factors, respectively p’ and q’.

Both p’ - 1 and q’ - 1 should have large prime factors.

Both p + 1 and q + 1 should have large prime factors.

Both (p - 1)/2 and (q - 1)/2 should be prime [182]. (Note that if this condition is true, then so are the first two.)

Whether strong primes are necessary is a subject of debate. These properties were designed to thwart some older factoring algorithms. However, the fastest factoring algorithms have as good a chance of factoring numbers that meet these criteria as they do of factoring numbers that do not [831].

I recommend against specifically generating strong primes. The length of the primes is much more important than the structure. Moreover, structure may be damaging because it is less random.

This may change. New factoring techniques may be developed that work better on numbers with certain properties than on numbers without them. If so, strong primes may be required once again. Check current theoretical mathematics journals for updates.

11.6 Discrete Logarithms in a Finite Field

Modular exponentiation is another one-way function used frequently in cryptography. Evaluating this expression is easy:

a^x mod n

The inverse problem of modular exponentiation is that of finding the discrete logarithm of a number. This is a hard problem:

Find x where a^x ≡ b (mod n).

For example:

If 3^x ≡ 15 mod 17, then x = 6

Not all discrete logarithms have solutions (remember, the only valid solutions are integers). It’s easy to see that there is no solution, x, to the equation

3^x = 7 (mod 13)

It’s far more difficult to solve these problems using 1024-bit numbers.

Calculating Discrete Logarithms in a Finite Group

There are three main groups whose discrete logarithms are of interest to cryptographers:

— The multiplicative group of prime fields: GF(p)

— The multiplicative group of finite fields of characteristic 2: GF(2ⁿ)

— Elliptic curve groups over finite fields F : EC(F)

The security of many public-key algorithms is based on the problem of finding discrete logarithms, so the problem has been extensively studied. A good comprehensive overview of the problem, and the best solutions at the time, can be found in [1189, 1039]. The best current article on the topic is [934].

If p is the modulus and is prime, then the complexity of finding discrete logarithms in GF(p) is essentially the same as factoring an integer n of about the same size, when n is the product of two approximately equal-length primes [1378, 934]. This is:

e^{(1+ 0(1))(ln (p))(1/2)(ln (ln (p)))(1/2)}

The number field sieve is faster, with an heuristic asymptotic time estimate of

e^{(1.923+ 0(1))(ln (p))(1/3)(ln (ln (p)))(2/3)}

Stephen Pohlig and Martin Hellman found a fast way of computing discrete logarithms in GF(p) if p - 1 has only small prime factors [1253]. For this reason, only fields where p - 1 has at least one large factor are used in cryptography. Another algorithm [14] computes discrete logarithms at a speed comparable to factoring; it has been expanded to fields of the form GF(pⁿ) [716]. This algorithm was criticized [727] for having some theoretical problems. Other articles [1588] show how difficult the problem really is.

Computing discrete logarithms is closely related to factoring. If you can solve the discrete logarithm problem, then you can factor. (The converse has never been proven to be true.) Currently, there are three methods for calculating discrete logarithms in a prime field [370, 934, 648]: the linear sieve, the Gaussian integer scheme, and the number field sieve.

The preliminary, extensive computing has to be done only once per field. Afterward, individual logarithms can be quickly calculated. This can be a security disadvantage for systems based on these fields. It is important that different applications use different prime fields. Multiple users in the same application can use a common field, though.

In the world of extension fields, GF(2ⁿ) hasn’t been ignored by researchers. An algorithm was proposed in [727]. Coppersmith’s algorithm makes finding discrete logarithms in fields such as GF(2¹²⁷) reasonable and finding them in fields around GF(2⁴⁰⁰) possible [368]. This was based on work in [180]. The precomputation stage of this algorithm is enormous, but otherwise it is nice and efficient. A practical implementation of a less efficient version of the same algorithm, after a seven-hour precomputation period, found discrete logs in GF(2¹²⁷) in several seconds each [1130, 180]. (This particular field, once used in some cryptosystems [142, 1631, 1632], is insecure.) For surveys of some of these results, consult [1189, 1039].

More recently, the precomputations for GF(2²²⁷), GF(2³¹³), and GF(2⁴⁰¹) are done, and significant progress has been made towards GF(2⁵⁰³). These calculations are being executed on an nCube-2 massively parallel computer with 1024 processors [649, 650]. Computing discrete logarithms in GF(2⁵⁹³) is still barely out of reach.

Like discrete logarithms in a prime field, the precomputation required to calculate discrete logarithms in a polynomial field has to be done only once. Taher ElGamal [520] gives an algorithm for calculating discrete logs in the field GF(p²).