Diffie Hellman encryption method

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 other 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.

Encrypt and decrypt a number

Select the 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.
  For instance, let's use p=103079
- 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.
  For instance, let's use g=7.
Select the private key and share the public key.
Let's 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.
  Here is a function to compute the public key given the global parameters and the private key a
```
def publickey(g,a,p):  
	astar=pow(g,a,p)
	return astar
```
  Suppose Alice selects a=13, her public key is ? [compute it]
  Suppose Bob selects b=11, his public key is ? [compute it]
Compute the super key for encoding and decoding.
- 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.
```
# compute the superkey x given the public key of Bob and the private key of Alice
def superkey(bstar,a,p): 
	x=pow(bstar,a,p)
	return x
```
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. For this part you need to compute the modular inverse "compute X s.t. T*X = 1 mod P, if it exists.
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
If the number is t=36, and the superkey is x, to encrypt compute
encrypted=(t+x)%p
To decrypt the number encrypted do
decrypted=(encrypted-x)%p
Only the users who have the same superkey can encrypt and decrypt.

Try the python code diffie.py to encrypt a number.

Encrypt and decrypt a word

To apply the encryption/decryption scheme described above, a word needs to be converted to a number. To encrypt the word as number, take the ascii code for each character, and treat each character as a digit when converting numbers in different bases. The encoding of the word is what is encrypted, transmitted, and then decoded by the recipient.

Encrypt and decrypt a sentence

Text can be shared in different ways. For instance, the text 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.