Diffie-Hellman cipher by Prof G.Samid (http://wesecure.net/)

Diffie-Hellman cipher is a response to the challenge of 'strangers' cryptography. Traditionally Alice and Bob would exchange a cryptographic key over a secure channel, and then use that key to communicate over insecure channels. Alas, the Internet creates a vast need for stragners to exchange secret messages. Such is the case when a customer wishes to purchase an item from an online store. Seller and buyer and strangers to each others; they have not had an opportunity to exchange a secret key and use it later. 

This challenge which was first (a bit awkwardly) addressed by Ralph Merkle has been satisfactorily addressed by his pals: Diffie and Hellman, extending the Merkle principle. The Merkle principle was as follows: Alice prepares a set of mathematical challenges which involve choice. Bob makes his choice and communicates it to Alice who can respond to Bob with the advantage of being the one who prepared these challenges. Hackey the hacker does not have that edge, and is left in the cold.

The Merkle solution to this challenge was not very practical, and prompted Diffie and Hellman to come up with their concept.

Their idea was that a computational result, R, can sometimes be computed in two different ways: one using information available to Alice, and the other using information available to Bob -- so that Hackey will remain out of the loop.

As an example: given a set of 1000 different integers, one wishes to find the identity of the integer that ranks 401 in the set (bottom up). One way to find it is to build the ranking from the bottom (lowest number) upward until the 401st number is spotted. Another way is to identify the number from the top down, and thereby identify th 599th number from the top. The result should be the same, but the computational pathway is different. That is the principle of the Diffie Hellman cipher.

Alice sends Bob a psuedo-key, and both Alice and Bob use that psuedo key to generate a pair of keys: one they keep private, the other they make public so Bob now knows Alice's public key and Alice now knows Bob's public key. Of course, Hackey now knows these public keys too, but he does not know either private key by contrast to Alice and Bob who each knows their own private key -- that's the point!

Now the scheme works by having a mathematical result, R, computed two ways: each with his or her private key and the other's public key.

Example:
Since the pair of private-public keys chosen by the parties is mathematically linked, it is necessary to insure that Hacky cannot derive the private key from the public key. Since it is impossible to impose such a condition, Diffie and Hellman retreated to impose intractability -- to find a mathematical arrangement where it would be exceedingly difficult to derive the private key from the public key (not impossible, but difficult!). They came to realize that modular log computation is generally considered difficult:

Y = a^Xmod n is easy to compute, while:

X = log_aY mod n is intractable. Hence, if Y will be a privae key and X its corresponding public key, then Hackey will be over his head with trying to compute X from Y.
Example: compute:

Y = 3⁷mod 5 3⁷= 2187 = 437*5 + 2, hence Y=2
Now: to compute:

X = log₃2 mod 5
one tries: for
X = 0 =log₃1 mod 5,
X = 1 =log₃3 mod 5,
X = 2 =log₃4 mod 5,
X = 3 =log₃2 mod 5,
X = 4 =log₃1 mod 5
X = 5 =log₃4 mod 5
X = 6 =log₃4 mod 5
X = 7 =log₃2 mod 5
X = 8 =log₃1 mod 5

Since the possible results for Y are only five options, there are many X values the solve this equation. Which immediately suggests that the mod basis should be a large number! This should work because there is no major compuational shortcut to what we tried here, checking the values of X=0,1,2,3,..
Based on the this assumed intractability Diffie and Hellman made a clever and creative use of a known mathematical relationship:

Z = a^XYmod n= (a^X)^Ymod n= (a^Y)^Xmod n which allowed them to set:

U = a^X, and V = a^Y and write:

Z = U^Y= V^X which means that the result Z can be computed by one who knows U and Y, as well as by one who knows V and X!
To implement this great idea it is necessary to find good values for n and a. n we have already reasoned must be a large number. What about a?
Upon examination we see that if a=0, we have Y = 0^X= 0 so Y would be limited to 0,n,2n,3n,....kn. Not good. Remember -- we need intractability, Hackey must find it difficult to compute. Similarly for a=1 we have: Y = 1^X= 1, and hence Y=1,n+1, 2n+1,....kn+1. Same problem. So Diffie and Hellman reasoned that a must be a 'root' of n, defined as a number such that for any residue 0 <=r < n, there will be some number t such that:

a^t= r mod n Such an a will pose the required intractability on Hacky. So now we are ready to implement Diffie and Hellman cipher. Alice will choose n and a (the psuedo key), and pass them along to Bob. Both Alice and Bob will choose a random private key: Alice will choose X and Bob will choose Y. Alice will now compute her public key U=a^X, and Bob will compute his public key V=a^Y, and send them to each other. Based on our reasoning above, Hacky, aware of U and V will find it difficult to reverse compute them to either X or Y (intractability!), but Alice and Bob, on the other hand will compute the same result Z:

Z = U^Y= V^X which will serve as their shared cryptographic key.
Example:
Let n=7, then a=5
Alice selects Ra=3 and computes: Ua = 5³mod 7 = 125 mod 7 = 6
Bob selects Rb = 2 and computes Ub = 5²mod 7 = 4 mod 7
Alice computes K = 4³mod 7 = 1
Bob computes K = 6²mod 7 = 1
"1" is the shared result. Remember n must be large (not n=7) for intractability kick in.