The Diffie-Hellman key exchange uses a large prime pand a primitive root gof this prime. These numbers are both public. To start the key exchange process, Alice chooses a secret number aless than the large prime, and computes ga(mod p). Alice sends this answer, call it A, to Bob. The Diffie-Hellman key exchange algorithm was first published in 1976 by Whitfield Diffie and Martin Hellman, although the algorithm had been invented a few years earlier by the British government intelligence agency GCHQ but was kept classified. The Diffie-Hellman method works best if p = 2q+1 where q is also a prime. (For example, 5 and 11 are prime and 11 = 2 x 5 + 1.) Then half the integers 1,2.,p-1 are generators, and it is possible to check whether g is a.
The Diffie-Hellman protocol is a method for two computer users to generate a shared private key with which they can then exchange information across an insecure channel. Let the users be named Alice and Bob. First, they agree on two prime numbers and , where is large (typically at least 512 bits) and is a primitive root modulo . (In practice, it is a good idea to choose such that is also prime.) The numbers and need not be kept secret from other users. Now Alice chooses a large random number as her private key and Bob similarly chooses a large number . Alice then computes , which she sends to Bob, and Bob computes , which he sends to Alice.
Now both Alice and Bob compute their shared key , which Alice computes as
and Bob computes as
Alice and Bob can now use their shared key to exchange information without worrying about other users obtaining this information. In order for a potential eavesdropper (Eve) to do so, she would first need to obtain knowing only , , and .
This can be done by computing from or from . This is the discrete logarithm problem, which is computationally infeasible for large . Computing the discrete logarithm of a number modulo takes roughly the same amount of time as factoring the product of two primes the same size as , which is what the security of the RSA cryptosystem relies on. Thus, the Diffie-Hellman protocol is roughly as secure as RSA.
SEE ALSO:Cryptography, Public-KeyCryptography, RSA EncryptionDiffie-hellman Key Exchange Calculator
This entry contributed by David Terr
REFERENCES:Diffie, W. and Hellman, M. 'New Directions in Cryptography.' IEEE Trans.Info. Th.22, 644-654, 1976.
Hershey, J. E. CryptographyDemystified. New York: McGraw-Hill, pp. 162-166, 2003.
Schneier, B Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed. New York: Wiley, pp. 513-516, 1996.
Referenced on Wolfram|Alpha: Diffie-Hellman ProtocolCITE THIS AS:Diffie-hellman Calculator
Terr, David. 'Diffie-Hellman Protocol.' From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Diffie-HellmanProtocol.html
HomeTake on the roles of Alice and Bob! Exchange secret keys using the Diffie-Hellman key exchange method!! Use your keys to encrypt messages!!!
The Diffie-Hellman key exchange uses a large prime p and a primitive root g of this prime. These numbers are both public.
To start the key exchange process, Alice chooses a secret number a less than the large prime, and computes ga (mod p). Alice sends this answer, call it A, to Bob. Bob now chooses his own secret number b, and computes gb (mod p). Bob sends this answer, call it B, to Alice.
Finally, Alice computes Ba (mod p), and Bob computes Ab (mod p). They both get the same answer, but no-one else will know this secret answer, because only Alice knows a, and only Bob knows b. This secret answer is their private key, which they can use to encrypt messages.
[You may wonder why someone intercepting Alice and Bob's communication can't solve gx = A (mod p) to calculate Alice's secret number a. This is a hard problem, known as the discrete logarithm problem. That this is difficult is the strength of this method of key exchange.]
First you must be Alice. Choose a large prime from the list below (or one of your own choice) and a corresponding primitive root of that large prime. Then choose a secret number which is smaller than your large prime.
- 22953686867719691230002707821868552601124472329079 primitive root 11
- 30762542250301270692051460539586166927291732754961 primitive root 7
- 29927402397991286489627837734179186385188296382227 primitive root 2
- 95647806479275528135733781266203904794419563064407 primitive root 5
- 48705091355238882778842909230056712140813460157899 primitive root 6
- 53542885039615245271174355315623704334284773568199 primitive root 3
- 622288097498926496141095869268883999563096063592498055290461 primitive root 2
- 610692533270508750441931226384209856405876657993997547171387 primitive root 2
- 4669523849932130508876392554713407521319117239637943224980015676156491 primitive root 3
- 4906275427767802358357703730938087362176142642699093827933107888253709 primitive root 2
- 18532395500947174450709383384936679868383424444311405679463280782405796233163977 primitive root 5
- 282755483533707287054752184321121345766861480697448703443857012153264407439766013042402571 primitive root 2