34 DIFFIE AND HELLMAN can achieve cost ratios approximately 10 000 to 1,which are as their key.User i obtains Ky by obtaining Y,from the public too small for most applications.If inexpensive,high bandwidth file and letting data links come available,ratios of a million to one or greater could achieved and the system would be of substantial practi- Ky=Y mod g (9) cal value. We now suggest a new public key distribution system which has several advantages.First,it requires only one "key"to =(a)mod g (10) be exchanged.Second,the cryptanalytic effort bears to grow exponentially in the effort of the legitimate users.And,third, its use can be tied to a public file of user information which (11) serves to authenticate user 4 to user B vice versa.By making the =o=mod q. public file essentially a read memory,one personal appearance allows a user to authenticate his identity many times to many User j obtains Ki in the similar fashion users.rkle's technique requires 4 and B to verify each other's activities through other means. Kg=乎modq. (12) The new technique makes use of the apparent difficulty computing logarithms over a finite field GF(g)with a one Another user must compute Ky from Y and Y,for example, number g of elements.Let by computing Y=a mod g, for1≤X≤g-1, (4) Ku=YdogeY))mod g. (13) Here a is a fixed primitive element of GF(g),then X is arranged We thus see that if logs mod g are easily computed the system to as the logarithm of y to the base o,mod g: can be broken.While we do not currently have a proof of the converse (i.e.,that the system is secure if logs mod g are X=loga Y mod g,for1≤Y≤q-1. (5) difficult to compute),neither do we see any way to compute Ky from Y,and Y without first obtaining either X,or X. Calculation of y from X is easy,taking at most 2 X log2 g If g is a prime slightly less than 25,then all quantities are multiplications [6,pp.398-422].For example,for X= representable as b bit numbers.Exponentiation then takes at most 2b multiplications mod g,while by hypothesis taking logs Y=a18=((a2)222×a2. (6) requires=operations.The cryptanalytic effort therefore grows exponentially relative to legitimate efforts.If b=200, Computing X from Y,on the other hand can be much more cult then at most 400 multiplications are required to compute Y and,for certain carefully chosen values of g.requires on the from Xi,or Ky from Y,and X,yet taking logs mod q requires order of operations,using the best known ithm 7,pp.9,2100 or approximately 103 operations. 575-576],[81. The security ofour technique depends crucially on the seculty of computing logarithms mod g.and if an algorithm whose 4 ONE-WAY AUTHENTICATION complexity grew as logag were to be found,our m would be broken.While the simplicity of the problem statement might The problem of authentication is perhaps an even more serious allow such simple algorithms,right instead allow a proof of barrier to the universal adoption of telecommunications for the problem's difficulty.How we assume that the best known business transactions than the problem of key distribution. algorithm for uting logs mod g is in fact close to optimal and Authentication is at the heart of any system involving contracts hence g is a good measure of the problem's complexity,and billing.Without it,business cannot function.Current elec- properly chosen g. tronic authentication systems cannot meet the need for a purely Such user generates an independent random number chosen digital,unforgeable,message dependent signature.They pro- uniformly from the set of integers (1,2,...,q-such keeps vide protection against third party forgeries,but do not protect X,secret,but places against disputes between transmitter and receiver. In order to develop a system capable of replacing the current Y=a mod q (7) written contract with some purely electronic form of communi- cation,we must discover a digital phenomenon with the same Public file with his name and address.When users i wish to properties as a written signature.It must be easy for anyone to communicate privately,they use recognize the signature as authentic,but impossible for anyone other than the legitimate signer to produce it.We will call any Ky=a mod g (8) such technique one-way authentication.Since any digital signal34 DIFFIE AND HELLMAN can achieve cost ratios approximately 10 000 to 1, which are as their key. User i obtains Kij by obtaining Yj from the public too small for most applications. If inexpensive, high bandwidth file and letting data links come available, ratios of a million to one or greater could achieved and the system would be of substantial practi- Kij 5 Yj Xi mod q (9) cal value. We now suggest a new public key distribution system which has several advantages. First, it requires only one ‘‘key’’ to 5 (aXj ) Xi mod q (10) be exchanged. Second, the cryptanalytic effort bears to grow exponentially in the effort of the legitimate users. And, third, its use can be tied to a public file of user information which 5 aXjXi 5 aXjXi mod q. (11) serves to authenticate user A to user B vice versa. By making the public file essentially a read memory, one personal appearance User j obtains Kij in the similar fashion allows a user to authenticate his identity many times to many users. rkle’s technique requires A and B to verify each other’s Kij 5 Yi Xj mod q. (12) activities through other means. The new technique makes use of the apparent difficulty Another user must compute Kij from Yi and Yj computing logarithms over a finite field GF , for example, (q) with a one number q of elements. Let by computing Kij 5 Yi Y 5 a (logaYj) mod q. (13) x mod q, for 1 # X # q 2 1, (4) Here a is a fixed primitive element of GF(q), then X is arranged We thus see that if logs mod q are easily computed the system to as the logarithm of Y to the base a, mod q: can be broken. While we do not currently have a proof of the converse (i.e., that the system is secure if logs mod q are X 5 loga Y mod q, for 1 # Y # q 2 1. (5) difficult to compute), neither do we see any way to compute Kij from Yi and Yj without first obtaining either Xi or Xj. Calculation of Y from X is easy, taking at most 2 3 log2 q If q is a prime slightly less than 2b , then all quantities are multiplications [6, pp. 398–422]. For example, for X 5 representable as b bit numbers. Exponentiation then takes at most 2b multiplications mod q, while by hypothesis taking logs Y 5 a18 5 (((a2 ) 2 ) 2 ) 2 3 a2 . (6) requires q1/2 5 21/2 operations. The cryptanalytic effort therefore grows exponentially relative to legitimate efforts. If b 5 200, Computing X from Y, on the other hand can be much more cult then at most 400 multiplications are required to compute Yi and, for certain carefully chosen values of q, requires on the from Xi, or Kij from Yi and Xj, yet taking logs mod q requires order of q1/2 operations, using the best known ithm [7, pp. 9, 2100 or approximately 1030 operations. 575–576], [8]. The security of our technique depends crucially on the seculty of computing logarithms mod q, and if an algorithm whose 4 ONE-WAY AUTHENTICATION complexity grew as log2q were to be found, our m would be broken. While the simplicity of the problem statement might The problem of authentication is perhaps an even more serious allow such simple algorithms, right instead allow a proof of barrier to the universal adoption of telecommunications for the problem’s difficulty. How we assume that the best known business transactions than the problem of key distribution. algorithm for uting logs mod q is in fact close to optimal and Authentication is at the heart of any system involving contracts hence q1/2 is a good measure of the problem’s complexity, and billing. Without it, business cannot function. Current elec￾properly chosen q. tronic authentication systems cannot meet the need for a purely Such user generates an independent random number chosen digital, unforgeable, message dependent signature. They pro￾uniformly from the set of integers {1,2, ???, q—such keeps vide protection against third party forgeries, but do not protect Xi secret, but places against disputes between transmitter and receiver. In order to develop a system capable of replacing the current Y written contract with some purely electronic form of communi- i 5 aXi mod q (7) cation, we must discover a digital phenomenon with the same Public file with his name and address. When users i wish to properties as a written signature. It must be easy for anyone to communicate privately, they use recognize the signature as authentic, but impossible for anyone other than the legitimate signer to produce it. We will call any K such technique one-way authentication. Since any digital signal ij 5 aXiXj mod q (8)