Diffie–Hellman key exchange

Diffie–Hellman establishes a shared secret that can be used for secret communications by exchanging data over a public network. The following diagram illustrates the general idea of the key exchange by using colours instead of a very large number. The crucial part of the process is that Alice and Bob exchange their secret colours in a mix only. Finally this generates an identical key that is mathematically difficult (impossible for modern supercomputers to do in a reasonable amount of time) to reverse for another party that might have been listening in on them. Alice and Bob now use this common secret to encrypt and decrypt their sent and received data. Note that the yellow paint is already agreed by Alice and Bob:


Explanation which includes the encryption's mathematics:

1. Alice and Bob agree to use a prime number p=23 and base g=5.
2. Alice chooses a secret integer a=6, then sends Bob A = g^a mod p
   • A = 5⁶ mod 23
   • A = 15,625 mod 23
   • A = 8
3. Bob chooses a secret integer b=15, then sends Alice B = g^b mod p
   • B = 5¹⁵ mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. Alice computes s = B ^a mod p
   • s = 19⁶ mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. Bob computes s = A ^b mod p
   • s = 8¹⁵ mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. Alice and Bob now share a secret: s = 2. This is because 6*15 is the same as 15*6. So somebody who had known both these private integers might also have calculated s as follows:
   • s = 5^6*15 mod 23
   • s = 5^15*6 mod 23
   • s = 5⁹⁰ mod 23
   • s = 807,793,566,946,316,088,741,610,050,849,573,099,185,363,389,551,639,556,884,765,625 mod 23
   • s = 2 
      
   • Both Alice and Bob have arrived at the same value, because (g^a)^b and (g^b)^a are equal mod p. Note that only a, b and g^ab = g^ba mod p are kept secret. All the other values – p, g, g^a mod p, and g^b mod p – are sent in the clear. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a, b, and p would be needed to make this example secure, since it is easy to try all the possible values of g^ab mod 23. There are only 23 possible integers as the result of mod 23. If p were a prime of at least 300 digits, and a and b were at least 100 digits long, then even the best algorithms known today could not find a given only g, p, g^b mod p and g^a mod p, even using all of mankind's computing power.