The Diffie-Hellman Key Exchange

The Diffie-Hellman Key Exchange allows two strangers who have no prior knowledge about each other to securely establish a secret key that they can use to communicate securely even if all of their messages are being intercepted by an eavesdropper.

In this article, we will learn about the Diffie-Hellman Key Exchange and the Miller-Rabin Primality Test. We will describe the six steps of the Diffie-Hellman Key Exchange at a high level and then work through a brief example of the Key Exchange. We will then describe the five steps of the Miller-Rabin Primality Test and work through a brief example of the algorithm. Next, we will apply what we have learned by creating a Python program that successfully implements the Diffie-Hellman Key Exchange.

Prerequisite Knowledge:

This article assumes that the reader understands concepts such as modular arithmetic and sets, and has a general understanding of Python or a similar programming language. In addition, the following list will be useful when going through this article:

1. A pseudoprime is an integer that is probably prime.
2. A group is a set with an operation that combines two operands.
3. A group’s order is its cardinality. In other words, it describes how many elements it contains.
4. The multiplicative group modulo p for a prime p is denoted by (ℤ/pℤ)*. It is the set of order (p-1) with elements {1,2,…,p-1} under the operation multiplication modulo p.
5. A generator of the group (ℤ/pℤ)* has order (p-1) modulo q.
6. The order of any integer g that is a generator of (ℤ/pℤ)* is the smallest positive y such that g^y = 1 (mod p).

The Diffie-Hellman Key Exchange:

The Diffie-Hellman Key Exchange involves the following six steps:

1. Together, PersonA and PersonB choose a very large pseudoprime p with (p-1)/2 also being pseudoprime. Since the prime factorization of (p-1) is 2((p-1)/2), then any generator of (ℤ/pℤ)* will have the order of a divisor of p-1. That is, each element of (ℤ/pℤ)* has either order of 1, 2, (p-1)/2, or p-1. Next, PersonA and PersonB choose an integer g such that g generates (ℤ/pℤ)*. The process of finding a g that generates (ℤ/pℤ)* involves finding an element of order p-1. If 2 has order (p-1)/2, then g = -2 has order (p-1) modulo p. It is not necessary that g generates (ℤ/pℤ)*, but for security reasons, this is the approach that we will use. If soundness, and not security, is the reader’s greatest objective, then picking a random g such that 1≤g≤p will suffice.
2. PersonA secretly chooses an integer n that they don’t tell anyone.
3. PersonB secretly chooses an integer m that they don’t tell anyone.
4. PersonA computes g^n (mod p) and tells PersonB the resulting integer.
5. PersonB computes g^m (mod p) and tells PersonA the resulting integer.
6. Both PersonA and PersonB are now able to compute the shared secret key denoted by s:

A Brief Example of the Diffie-Hellman Key Exchange:

Here we will work through an example of the Diffie-Hellman Key Exchange where p is a 29-digit integer.

1. Let p = 74,406,850,220,820,509,198,642,540,543 and g = 74,406,850,220,820,509,198,642,540,541. Note that p and (p-1)/2 are prime and g is a generator of (ℤ/pℤ)*.
2. Let n = 7,160,624,108.
3. Let m = 8,460,590,791.
4. So, g^n (mod p) = 47,826,684,805,755,333,836,688,086,773.
5. So, g^m (mod p) = 1,783,357,463,939,102,724,432,550,267.
6. Therefore, s = 9,896,557,491,816,756,391,504,944,966.

Miller-Rabin Primality Test:

Up to this point, we should have a good understanding of the Diffie-Hellman Key Exchange, but how the heck are we supposed to find a 29-digit p that works? Enter the Miller-Rabin Primality Test. This algorithm will tell us whether an integer is pseudoprime or composite. Simply go through the following four steps until a 29-digit pseudoprime is found.

1. Let n be a random 29-digit integer.
2. Compute the unique integers m and k such that m is odd and n-1 = m(2^k).
3. Let a be a random integer such that 1<a<n.
4. Let b = a^m (mod n) and 1≤r≤(k-1). If b ≡ ±1 (mod n) or b^(2^r)≡-1(mod n) for any r, then n is pseudoprime. Otherwise, n is composite.

If we want to use a pseudoprime, n, in the Diffie-Hellman Key Exchange, then we need to check if (n-1)/2 is also pseudoprime. We can check this by simply using a slight variation of the Miller-Rabin Primality Test which is shown below.

1. Let x = (n-1)/2.
2. Compute the unique integers m and k such that m is odd and x-1 = m(2^k).
3. Let a be a random integer such that 1<a<x.
4. Let b = a^m (mod x) and 1≤r≤(k-1). If b ≡ ±1 (mod x) or b^(2^r)≡-1(mod x), then x is pseudoprime. Otherwise, x is composite.

A Brief Example of the Miller-Rabin Primality Test:

Here we will work through an example of the Miller-Rabin Primality Test where n and (n-1)/2 are shown to be pseudoprime.

Part 1: Find if n Is Pseudoprime or Composite

1. Let n = 24,645,693,377,521,872,504,085,245,467.
2. Solving for the unique integers m and k such that n-1 = m(2^k), we find that m = 12,322,846,688,760,936,252,042,622,733 and k = 1.
3. Let a = 8,625,146,190,036,362,446,236,062,645.
4. Therefore, b = a^m (mod n) = 1. Since 1 modulo n = b modulo n, we can say that b ≡ ±1 (mod n). Therefore, n is pseudoprime.

Part 2: Find if (n-1)/2 Is Pseudoprime or Composite

1. Let x = (n-1)/2 = 12,322,846,688,760,936,252,042,622,733.
2. Solving for the unique integers m and k such that x-1 = m(2^k), we find that m = 3,080,711,672,190,234,063,010,655,683 and k = 2.
3. Let a = 4,658,103,515,624,502,847,038,292,640.
4. Therefore, b = a^m (mod x) = 1. Since 1 modulo x = b modulo x, we can say that b ≡ ±1 (mod x). Therefore, x=(n-1)/2 is pseudoprime.

Bringing It All Together: An Example in Python of the Diffie-Hellman Key Exchange Which Utilizes the Miller-Rabin Primality Test:

We will now implement the aforementioned key exchange and algorithm in Python.

The Miller-Rabin Primality Test in Python

Below is a brief description of each function in the proceeding code which will return a pseudoprime p such that (p-1)/2 is also pseudoprime when the chooseP() function is called.

1. powerTests(a, m, n, k): This is step 4 of the Miller-Rabin Primality Test. We first set b equal to a^m (mod n) by utilizing the Python pow(base, exponent, modulus) function. From here, we realize that if b ≡ ±1 (mod n), then b equals 1 or n-1. If this is the case, then n is pseudoprime and we return True to indicate this finding. Otherwise, if the pseudoprimality of n has not been determined yet, then we iterate over all possible values of r and check if b^(2^r)≡-1(mod n) by utilizing the Python pow(base, exponent, modulus) function. Note that if this is the case, then b^(2^r) = n-1. So, if b^(2^r)≡-1(mod n) for any r, then n is pseudoprime and we return True to indicate this finding. Otherwise, we return False.
2. computeMandK(n): This is step 2 of the Miller-Rabin Primality Test. We start by initializing m and k such that m = n-1 and k = 0. Note that with these initial values of m and k, the equation n-1 = m(2^k) is satisfied. However, m may not be odd, so we enter a while loop and update the values of m and k until m is odd. Note that by adding 1 to k and by dividing m by 2 on each loop iteration, the equation n-1 = m(2^k) continues to be satisfied.
3. generateRandomInt(lowerBound, upperBound): This function is used to choose p and a, thus it is steps 1 and 3 of the Miller-Rabin Primality Test. Returns a random integer Z such that lowerBound≤Z≤upperBound.
4. MRPrimalityTest(): Continues to perform the Miller-Rabin Primality Test on random 29-digit integers until a pseudoprime is found.
5. isPrime(n): Performs the Miller-Rabin Primality Test on (p-1)/2.
6. chooseP(): This is the main function from which all other functions stem from. It ensures that a pseudoprime is found that can be used for the Diffie-Hellman Key Exchange. That is, p and (p-1)/2 are pseudoprime. It also ensures that 2 has order (p-1)/2.

Simulating PersonA and PersonB With a Person Object:

To implement the remaining steps of the Diffie-Hellman Key Exchange, we need to somehow represent PersonA and PersonB so that tasks such as choosing secret integers n and m, computing and sharing g^n (mod p) and g^m (mod p), and computing the shared secret key s are possible. We will achieve this by creating a Person class that will be used to create the objects personA and personB. Here is a brief description of the data members and methods of the Person class:

Data Members:

1. p: The agreed upon pseudoprime which was found using the Miller-Rabin Primality Test.
2. g: The agreed upon integer which has the same order as (ℤ/pℤ)* and 1<g<p.
3. _secretInt: For personA, this is n and for personB this is m.
4. intToShare: The integer that they share with the other person.
5. intFromOtherPerson: The integer that was shared by the other person.
6. _sharedSecretKey: The shared secret key s.

Methods:

1. __init__(self, p, g): Initialize all data members.
2. chooseSecretInt(self): Secretly choose a random integer. For personA, this is n and for personB, this is m.
3. setIntFromOtherPerson(self, intFromOtherPerson): Takes the integer that the other person shared as a parameter and sets the data member intFromOtherPerson equal to this parameter.
4. computeIntToShare(self): Helper function for sendInt(self). Computes and returns g^(_secretInt) (mod p) by using the Python pow(g, _secretInt, p) function.
5. sendInt(self): Returns the integer to share with the other person.
6. computeSharedSecretKey(self): Computes the shared secret key and stores it in its _sharedSecretKey data member.

Performing the Diffie-Hellman Key Exchange:

Below is a working example of the Diffie-Hellman Key Exchange that utilizes all of the code that we have previously talked about. The program imports the Person class and the chooseP() function from MillerRabinPrimalityTest.py. The program then chooses p and g according to the Diffie-Hellman Key Exchange requirements. PersonA and PersonB are then created and they each choose a secret key. Each person then sends and receives a computed integer corresponding to steps 4 and 5 of the Diffie-Hellman Key Exchange. Finally, each person computes s and the result is printed to the console.

A sample output of the preceding program shows that our implementation of the Diffie-Hellman Key Exchange was successful!

Agreed upon p = 52715485256194169359137162299
Agreed upon g = 52715485256194169359137162297
PersonA secretly computes g^n (mod p) = 40768582547499338665116868709
PersonB secretly computes g^m (mod p) = 43084512410369395738880134222
PersonA computes s = 44150840871111848693028463930
PersonB computes s = 44150840871111848693028463930

References:

Stein, William. Elementary Number Theory: Primes, Congruences, and Secrets. 2017.