Introduction

If p is a prime and g and x integers, then computation of y such that

$$y \equiv g^x \bmod p,\ \ 0 \leq y \leq p-1$$ (1)

is referred to as discrete exponentiation. Using the successive squaring method, it is very fast (polynomial in the number of bits of |p| + |g| + |x|). On the other hand, the inverse problem, namely, given p, g, and y, to compute some x such that Equation 1 holds, which is referred to as the discrete logarithm problem, appears to be quite hard in general. Many of the most widely used public key cryptosystems are based on the assumption that discrete logarithms are indeed hard to compute, at least for carefully chosen primes.

The current state of knowledge about discrete logarithms is surveyed in [28,34]. There are algorithms that compute discrete logarithms in GF (p) in time roughly $q^\frac{1}{2}$, where q is the largest prime dividing p-1. Therefore, it is advisable to choose p such that p-1 is divisible by at least one large prime q, say $q \gtrsim 10^{30}$. Further, since solutions x to Equation 1 (for p,g, and y given) are determined only modulo the multiplicative order of g modulo p, it is advisable to choose g with its order divisible by a large prime. If these precautions are observed, then the best published algorithms [12] for computing discrete logarithms modulo a prime phave running time

$$\mbox{exp}((1+ o(1))(\log p)^{\frac{1}{2}}(\log \log p)^{\frac{1}{2}})\ \ \mbox{ as } p \rightarrow \infty.$$ (2)

(Section 8 discusses a very recent discovery, the number field sieve, that is expected to be much faster asymptotically, but is not practical at this time.) The estimate given by Equation 2 is of roughly the same form as that of most of the fast practical algorithms for factoring composite integers of about the same size as p. An important feature of the estimate above is that it applies to a precomputation phase that has to be carried out once for each prime p. Once that phase is completed, individual discrete logarithms modulo that prime are much easier to compute.

Equation 2 is only an asymptotic estimate and does not say how large a prime p one could handle in practice in a reasonable amount of time. Currently large hard integers (hard here means that they are not of a special form and do not have small prime factors) with 100 to 110 decimal digits are factored in the equivalent of under a year on a 100 mips (million instructions per second) computer [26]. (The actual computation is spread over hundreds of workstations, and uses only their idle time.) The general feeling among experts in factoring integers and computing discrete logarithms was that the two problems were of roughly equal difficulty in practice as well as in theory. However, no computations of discrete logarithms in large prime fields have been reported before. Discrete logs have been computed in the field GF (2¹²⁷) by Coppersmith [10] and by Blake, Fuji-Hara, Mullin, and Vanstone [5]. This showed that the scheme implemented first in software by MITRE and then on a prototype chip by Hewlett-Packard was insecure. However, since in fields of characteristic two the discrete log problem is much easier than it is in prime fields (especially when one uses the Coppersmith algorithm [10,28,34]), it was not clear what impact this result had for the security of prime fields.

The complexity of computing discrete logs in prime fields is of substantial practical interest, since it provides an estimate of the size of the prime that has to be used. Sun Microcomputers, Inc., has implemented a secure identification feature as part of their Network File System (NFS), and this system has been incorporated into Unix $^{\rm {TM}}$ System V Release 4.0. The Sun scheme uses discrete exponentiation modulo a prime of 192 bits. This paper shows that it is quite easy to compute discrete logs modulo that prime, which makes it possible to break the NFS security in a very clean way. In a few days on a moderately fast machine it is possible to prepare a database of less than a megabyte that will then enable the cryptanalyst to obtain any particular user's secret key in a matter of at most a few minutes. While the preparation of the database does require extensive and sophisticated programming, once it is accomplished, the breaking of individual logs can be performed with hardly any programming effort at all by using a symbolic manipulation system such as Macsyma, Maple, or Mathematica. (If such a system is used, though, the time to break an individual key might be on the order of hours instead of minutes.) While the NFS security feature was already known to be weak, our results show that it can be broken in a very simple way.

The attack on the Sun cryptosystem provides the first experimental evidence concerning the difficulty of computing discrete logarithms in GF(p). In order to better estimate the running time required to calculate discrete logs in larger prime field, most of the basic computations were also performed modulo a particular prime of 224 bits. These computations are mentioned briefly in Section 5.

The general conclusion to be drawn from the results reported here is that computing discrete logarithms modulo a prime is only a little harder than factoring integers of that same size. In particular, with about the same amount of effort that is used now to factor 110 decimal digit integers, one should be able to compute discrete logarithms modulo primes of about 100 digits.

Section 2 below presents the Sun NFS cryptosystem, and discusses some of its deficiencies. We mention in Section 3 some of the methods that could be used to strengthen it. The discrete log algorithm that was used is outlined in Section 4. Sections 5 through 7 describe various parts of the implementation. Section 8 sketches a new algorithm that was invented recently and is not currently practical, but might become so with additional improvements. Finally, Section 9 presents a summary of the results and some recommendations.