The basic idea of using a modification of the Diffie-Hellman scheme is not necessarily bad. What this paper shows is that the prime p has to be much larger for security. As we mention in Section 9, primes of 512 or fewer bits should definitely be avoided (even though it is not now feasible to compute discrete logarithms modulo a prime of 512 bits). The basic difficulty with this approach is of course the added computational burden. The time to execute the Diffie-Hellman scheme in software is proportional to D3, where D is the number of bits of p, so that going from 200 to 800 bits raises the complexity by a factor of 64.
There are several ways to deal with the problems of using a larger modulus. One is simply to use faster machines. Speeds of even small workstations are increasing very rapidly. Another, complementary approach, is to use faster algorithms. At the level of basic arithmetic, there are methods such as that of P. Montgomery [32] or methods using precomputed tables [2] that offer substantial speedups in modular multiplication over standard algorithms. One can also use addition chain methods [21] to carry out modular exponentiation with fewer modular multiplications than the usual method. (See [6] for some recent work on this.) The survey paper [8] discusses these and related methods.
Another approach is to use variants of the system that require fewer modular multiplications. One way to do this is to use secret keys mthat are relatively short (say m of 150 bits). Another, somewhat similar, way to do this is to use the idea of Schnorr [38], and choose g to be not a primitive element, but a generator of a multiplicative subgroup modulo p that is of order 2150 or so.
An easy way to improve the security of the scheme is to have a different prime for each user. With the presently known algorithms, the precomputation phase of the discrete logarithm algorithm when applied to a 100 decimal digit prime might take a year on a 100-mips computer. If that prime is used by everyone on a network, individual secret keys could then be obtained in minutes. However, if every user had a different prime, obtaining any such key would require a year, which might be regarded as sufficiently secure.
Instead of using discrete exponentiation modulo a prime, one could possibly gain some speed by using addition on elliptic curves [22,31]. Operations on elliptic curves are rather complicated, but no subexponential algorithms are known for the analog of the discrete logarithm problem on general elliptic curves, and so one could use much smaller primes. However, recently Menezes, Vanstone, and Okamoto [29] have shown that on some elliptic curves discrete logarithms can be computed in subexponential time, so one has to be on guard against further breakthroughs that might destroy the attractiveness of elliptic curve cryptosystems.
The Diffie-Hellman scheme is only one of many that can be used for authentication. In recent years, some very fast public key schemes have been developed. The Fiat-Shamir one [17] is perhaps the most widely known, but there are many other schemes [4,7,9,19,30,38]. They are more than an order of magnitude faster than RSA and Diffie-Hellman methods (for the same size modulus), and so can be implemented in software without excessive computational requirements. However, while those systems are very suitable for smart card applications, for example, they are not always appropriate for use in computer networks, when one might have to cope with active attackers who might control the communication channel.
The fast signature schemes mentioned above belong to the class of identity-based systems, in which there is no need to maintain a database of authentication information for all users. In those systems there is a trusted key authentication center (KAC) which provides each user Awith a secret key KA that is derived from A's basic identification information (login name, or machine routing number in a network). Using the secure key KA and the universally known public key of the KAC, user A can then produce a signature that can only come from A, and which will not enable anyone to generate signatures later. This simplifies the security problems, since it is not necessary to worry about monitoring a large secure authenticated file of information about users.
There are several identity-based cryptosystems that serve not only to authorize users, but also to generate session keys [3,20,23,35,36,40]. They could be used very effectively in settings like that of the Sun NFS. Unfortunately, their running times are all comparable to those of the RSA and Diffie-Hellman systems. It is desirable to find a scheme of this kind that would be as fast as some of the signature schemes that are known, since that would alleviate the problem of having to use large moduli.