If p is a prime and g and x are integers, then computation of y such that y ≡ g x mod p , 0 ≤ y ≤ p - 1 is fast. On the other hand the inverse problem, that is, for given p, g, and y to establish x, appears to be quite hard in general. This inverse problem is called the discrete logarithm problem. SUN Microcomputers has implemented a secure identification feature that uses discrete exponentiation modulo a prime of 192 bits as part of its Network File System.
The main goal of this paper is to show that it is quite easy to compute discrete logarithms modulo that prime. The authors also suggest that even cryptosystems based on 512-bit primes will become computationally insecure in the near future.
The paper’s presentation is exceptionally good. The method of computation is described clearly. The authors give several comments on their experiences with the implementation. Incorporating these suggestions in a new implementation could lead to considerable speed-up. Furthermore, these remarks can stimulate further theoretical research on the relevant areas. Finally, the paper is well documented.