The Diffie-Hellman is a method for two users to exchange information
that is encrypted. The method was proposed in 1976. It is the
base for many methods used in VPN, SSH, PGP and otehr PKI systems.
The method is called asymmetric key exchange, because anyone can
encrypt messages using the public key of the recipient but only
the holder of the private key used to generate the public key can decrypt.
The security depends on the secrecy of the private key and the use of large
numbers that make brute force decryption very difficult.
Selection of shared numbers.
select a large prime number P. To be effective P should have
at least 512 bits. It is good to select a P so that (P-1)/2 is
also prime.
select a number G. In practice G is a small number. To be
technically correct G should be a primitive root of P modulo P.
What this means is that for any pair of positive integers less than P.
G raised to the power of those numbers never produces the same result.
Selection of private key and sharing of public key.
We now look at two users, Alice and Bob.
Alice selects a number A as her private key.
She computes her public key as A*= G^A mod P.
Bob selects his private key B and computes his
public key B*=G^B mod P.
The public keys are shared with everyone.
Computation of super key.
Alice computes her super key as X = (B*)^A mod P.
Bob computes his super key as X = (A*)^B mod P.
X turns out to be the same for Alice and Bob, even though
they never shared their private keys. The superkeys are
for a pair of users. The same user can be in multiple pairs,
using a separate superkey for each pair.
Use the superkey to encrypt and decrypt.
To encrypt a number T, Alice or Bob use the superkey key X
and compute (T*X) mod P.
To decrypt a number T, Alice or Bob use the superkey key X
and compute (T/X) mod P.
Alternatively, the encryption and decryption can be done in a simpler
way by computing
To encrypt a number T, Alice or Bob use the superkey key X
and compute (T+X) mod P.
To decrypt a number T, Alice or Bob use the superkey key X
and compute (T-X) mod P
Only the users who have the same superkey can encrypt and
decrypt.
Encrypt and decrypt text.
To apply the scheme described above, words need to be converted
to numbers in such a way that each word is encoded as a different
number. The encoding of a word is what is encrypted, transmitted,
and decoded by the recipient.
Text can be shared in different ways. For instance, it can be split
into words, each word encoded as a number, and all the numbers
put together into a list. Alternatively, each word and its corresponding
encoding can be placed into a dictionary.