Understanding-the-Diffie-Hellman-Key-Exchange
The Diffie–Hellman Key Exchange Method (hereafter called the D-H method) allows two parties agree upon a shared secret number, a symmetric key, over an insecure communications channel/medium, where attackers/hackers might be listening in. The benefit of using a symmetric key over public key cryptography lies in the fact that encryption of a plaintext message into a ciphertext message and decryption of the ciphertext message back to the original plaintext message happens much faster using a symmetric key. Moreover, a symmetric key encryption scheme is also much easier to implement as compared to that of an asymmetric one.
Before going any further into the D-H method, let us go and check back on some mathematical concepts first – the concept of ‘Primitive Roots’.
Primitive Roots
A primitive root modulo n (primitive root mod n, where n is a positive integer) is an integer g such that every integer relatively prime to n is congruent to a power of g mod n. For a positive integer n, the integers x and y are congruent mod n, if their remainders when divided by n are the same. For example, 24 (mod 7) = 3 and 31 (mod 7) = 3. Here, x=24, y=31 and n=7.
Thus, 24 divided by 7 produces a remainder 3. Similarly, 31 divided by 7 produces a remainder 3. In other words, both 24 and 31 when divided by 7 produce the same remainder 3. So, we can say that 24 and 31 are congruent mod 7.
Simplifying further, an integer g is a primitive root modulo n, if for every integer a relatively prime to n, there is an integer z such that a ≡ (g
z (mod n)).
Now, let us check to find out if 2 is a primitive root modulo 5. Here, g=2 and n=5. All the integers relatively prime to 5 are 1, 2, 3, 4.
For a = 1:
20 (mod 5) = 1 (mod 5) = 1 = a
For a = 2:
21 (mod 5) = 2 (mod 5) = 2 = a
For a = 4:
22 (mod 5) = 4 (mod 5) = 4 = a
For a = 3:
23 (mod 5) = 8 (mod 5) = 3 = a
Thus, for every integer a (1, 2, 3, 4) relatively prime to n=5, there is an integer z (0, 1, 2, 3) such that a ≡ (gz (mod n)). Therefore, integer g=2 is a primitive root modulo 5.
Let us check with another example. Is 4 a primitive root modulo 5? Here, g=4 and n=5. All the integers relatively prime to 5 are 1, 2, 3, 4.
For a = 1:
40 (mod 5) = 1 (mod 5) = 1 = a
For a = 4:
41 (mod 5) = 4 (mod 5) = 4 = a
42 (mod 5) = 16 (mod 5) = 1
43 (mod 5) = 64 (mod 5) = 4
44 (mod 5) = 256 (mod 5) = 1
45 (mod 5) = 1024 (mod 5) = 4
………………………..
………………………..
And, the pattern continues.
Therefore, for integers 2 and 3 which are relatively prime to n=5, there isn’t an integer z such that a (here, 2 and 3) ≡ (gz (mod n)). Thus, integer g=4 is not a primitive root modulo 5.
D-H method Algorithm
> Parties A1 and B2 agree upon a prime number P and Base g. g is a primitive root modulo P. P and g are not secret and can be disclosed to anyone. g can be a small number, but P must be a very big number – P needs to be very big for the whole security piece to work securely. P is usually a 2048- or 4096-bits long number.
> A1 and B2 each select their own random private integer. Let us assume that A1 selects a and B2 selects b. Both a and b are kept secret – even A1 doesn’t know b and B2 doesn’t know a.
> A1 calculates A = ga mod P and sends A to B2 over the insecure communications channel/medium. Anyone seeing A results in no harm.
> B2 calculates B = gb mod P and sends B to A1 over the insecure communications channel/medium. Anyone seeing B results in no harm.
> A1 calculates the shared secret, SA1 = Ba mod P = gab mod P
> B2 calculates the shared secret, SB2 = Ab mod P = gab mod P
Thus, algebraically, SA1 = SB2. So, by now, A1 and B2 both have got a secret symmetric key that they can safely use to encrypt a plaintext message into a ciphertext message and decrypt the ciphertext message back to the original plaintext message.
At this point, A1 and B2 have a shared secret key that anybody acting as a ‘Man in the Middle’ over the insecure communications channel/medium wouldn’t know about/be able to compute, even though that rogue actor knew about P, g, A and B – because that rogue actor has got no clue about what a and b are.
D-H method Algorithm_Steps involved
D-H method example
Step# 01: A1 and B2 agree upon P = 5 and g = 2.
Step# 02: A1 selects a random private integer/key, a = 6 and B2 selects a random private integer/key, b = 4.
Step# 03: A1 calculates A = ga mod P = 26 mod P = 64 mod 5 = 4
B2 calculates B = gb mod P = 24 mod 5 = 16 mod 5 = 1
Step# 04: A1 and B2 exchange the public numbers/values among themselves. A1 receives B=1 and B2 receives A=4.
Step# 05: A1 calculates the shared secret, SA1 = Ba mod P = 16 mod 5 = 1 mod 5 = 1
B2 calculates the shared secret, SB2 = Ab mod P = 44 mod 5 = 256 mod 5 = 1
Thus, 1 is the shared secret (symmetric key).
Implementation of the D-H method using the Python Programming Language
from __future__ import print_function
P = int(input(' Please enter the value of P.'))
print(' Thanks for entering the value of P as ' + str(P))
g = int(input(' Please enter the value of g.'))
print(' Thanks for entering the value of g as ' + str(g))
a = int(input(' \n Please enter the value of a.'))
b = int(input(' Please enter the value of b.'))
A = (g**a) % P
print( "\n A1 sends over to B2: " , A )
B = (g ** b) % P
print( " B2 sends over to A1: " , B )
A1SharedSecret = (B ** a) % P
print( " \n A1 Shared Secret: ", A1SharedSecret )
B2SharedSecret = (A**b) % P
print( " B2 Shared Secret: ", B2SharedSecret )
Please enter the value of P.23
Thanks for entering the value of P as 23
Please enter the value of g.5
Thanks for entering the value of g as 5
Please enter the value of a.6
Please enter the value of b.15
A1 sends over to B2: 8
B2 sends over to A1: 19
A1 Shared Secret: 2
B2 Shared Secret: 2
What can you do with the Shared Secret (Symmetric Key)?
Of course, the shared secret symmetric key can be safely used for encrypting a plaintext message into a ciphertext message and decrypting the ciphertext message back to the original plaintext message. Let us look at an example below.
NOTE: - Please note that the following encryption and decryption examples are for illustration and understanding purposes only and the author never prescribes implementing them for use on production software.
Let us assume that A1 wants to send (Hush! a very secret message, A) to B2. Let us also assume the shared secret symmetric key to be 2.
ASCII code for 'A': 'A' decimal code - 6510.
A1 can raise the shared secret symmetric key 2 to the power of the ASCII Decimal value of the plaintext (that he wants to send over to B2) message (in our case, ‘A’).
So, 265 = 36,893,488,147,419,103,232
Thus, using the shared secret symmetric key 2, A1 encrypts the plaintext message ‘A’ to the ciphertext message 36893488147419103232 and sends over the ciphertext message to B2.
B2 has now got a job in his hand to decrypt the ciphertext message back to the original plaintext message. Decryption is just the opposite of encryption in meaning as well as action. The logarithm, or log, is the inverse of the mathematical operation of exponentiation.
If a = xb, then b = logxa
In our case, 265 = 36,893,488,147,419,103,232 [x=2, b=65 and a=36,893,488,147,419,103,232]
Thus, in order to decrypt the ciphertext message back to the original plaintext message, B2 must calculate b = logxa
b = logxa = log236893488147419103232 = 65
B2 has calculated b = 65. He then converts the ASCII Decimal value of 65 back to ‘A’ and thus, successfully decrypts the ciphertext message back to the original plaintext message.
You might have already guessed by now that in our above illustration, A1 and B2 had agreed upon previously to use the exponentiation and logarithmic, or log functions as means of encrypting and decrypting the plaintext and ciphertext messages, respectively. As already mentioned previously, this is not a real-world scenario/implementation but simply a demonstration in order to make everyone understand how the shared secret symmetric key can be used for encrypting a plaintext message into a ciphertext message and decrypting the ciphertext message back to the original plaintext message.
Summary
So, by now, you must have realized that the magic of the D-H method lies in the fact that both A1 and B2 arrived at the exact same shared secret symmetric key, without one knowing nothing about the other’s randomly chosen private integer/key. When the shared secret symmetric key is later used for encrypting traffic, both A1 and B2 are going to be certain that nobody else, except them, know about the shared secret symmetric key that they had created together. Even if someone rogue records the traffic for later analysis, there is absolutely no way to figure out what the key is, even though the exchanges that happened between A1 and B2 during the key creation process might have very well been visible. It would be virtually impossible for anyone analyzing the traffic later to break in because the key was never saved/stored, transmitted and made visible anywhere.
***********************************************************************************************************************************************************
The author of the technical article, Subhasish Sarkar (SS), is an IBM Z Champion for 2020.
***********************************************************************************************************************************************************