The Diffie-Hellman key exchange (DHKE) is different then most of the cryptography we have been covering in this blog. That is because we will not be using the DHKE for encrypting data, but instead as the name suggests it is a way we can exchange keys.
The Diffie-Hellman key exchange was proposed by Whitfield Diffie and Martin Hellman in 1976, and as you may recall we also mention them in The RSA Cryptosystem post. The DHKE provides a solution to a common problem that we have sorta ignored in symmetric cryptography, which is key distribution. The DHKE’s security* is based on the discrete logarithm problem which I am planning to dedicate a blog post to. The DHKE has become a fundamental technique used in many commercial cryptographic protocols like SSH, TLS, and IPSec. More so for Elliptic Curve Diffie-Hellman Key Exchange (ECDHKE), if that means nothing to you that is expected and will also be discussed in a future post.
(* I used an asterisk when talking about DHKE’s security because the discrete logarithm problem which it is based on, has been theoretically compromised by the belief that Quantum Computers using Shor’s Algorithm will be able to solve the discrete logarithm problem in the future)
The basic idea behind the DHKE is that exponentiation in a finite field is a one-way function and the exponentiation is commutative. But what does that mean? I’ll get to that, but first, let me actually show you the DHKE protocol in a diagram, but first, we need a bit of set-up for the protocol:
Diffie-Hellman Key Exchange protocol
Diffie-Hellman Key Exchange Set-up:
- Choose a large prime p.
- Choose an integer α ∈ {2, 3, …, p – 2}.
- Make p and α public.
These parameters (p and α) are sometimes called domain parameters or public parameters, which as you can guess are public meaning everyone can see them in the plain. If two parties which we call Alice and Bob know the public parameters, then they can generate a joint secret in the following key exchange protocol:
As you can see both parties Alice and Bob have computed the same session private key kAB. But it may be a little difficult to believe that, but lets break it down a bit and show a quick proof of correctness:
Diffie-Hellman Key Exchange proof of correctness:
Alice computes: Ba ≡ (αb)a ≡ αab mod p.
Bob computes: Ab ≡ (αa)b ≡ αab mod p.
Therefore Alice and Bob have the same private key that they established on an open and insecure channel! They can now use the key to establish secure communication between themselves by using that key for a symmetric algorithm like AES.
This may still be a little strange to believe a malicious person in reading all the messages between Alice and Bob couldn’t figure out the private key themselves. So I think it may help to look at an example with smaller numbers than we would use:
Example with public parameters p = 29 and α = 2:
Alice chooses a = 5. Then A = 25 ≡ 3 mod 29.
Bob chooses b = 12. Then B = 212 ≡ 7 mod 29.
Then Alice sends A = 3 to Bob, and Bob sends B = 7 to Alice.
Alice computes kAB = Ba ≡ 75 = 16 mod 29.
Bob computes kAB = Ab ≡ 312 = 16 mod 29.
As you can see both Alice and Bob now have the same value kAB = 16. Without ever sharing their own private values a and b making it very difficult for a third party to discover the private key.
You may even notice that the computation of DHKE is quite similar to the RSA cryptosystem. Therefore we can use the same technique we used for RSA namely the square-and-multiply algorithm to speed this up. This is important to know, because just like RSA the parameters in DHKE need to be quite large, specifically the modulus p should be at least 2048 bits, ideally twice that. You may also wonder what α is. Well that is the Greek symbol for alpha, and it needs a special property, namely it needs to be a primitive element.
The next section of this post will discuss what a primitive element is, how to find it, and the maths behind it.
Finite Groups
Once again we are needing to discuss advanced algebra, if you haven’t gotten the hint yet it is very important to Cryptography and is used everywhere. But if you need a refresher I recommend looking over the relevant parts of these past blog posts:
We will be adding onto what we have learned already in this post specifically to understand how we derive the alpha (α) we need for DHKE. So lets first start by reminding ourselves what a group is:
Definition of a group:
A group is a set of elements G with an operation ∘ that combines two elements of G. The group has the following properties:
- The group operation is closed. That is, if a, b G, then a ∘ b = x ∈ G.
- The group operation is associative.
- There is an element 1 ∈ G called the neutral element or identity element, that if a ∘ 1 = 1 ∘ a = a for all a ∈ G.
- For each a ∈ G there exists an element a-1 ∈ G, called the inverse of a, such that a ∘ a-1 = a-1 ∘ a = 1.
- A group G is abelian (or commutative) if a ∘ b = b ∘ a, for all a, b ∈ G.
*Note that all groups have properties 1-4, but if a group is also commutative then we call those abelian groups.
Examples of Groups:
- (ℤ, +) is a group. Meaning the set of integers with addition forms an abelian group, where e = 0 is the identity element and -a is the inverse of an element a ∈ ℤ.
- (ℤ \ 0, ⋅) is not a group since there is no possible identity element.
*note that (ℤ \ 0) means the set of integers minus the number 0.
- (ℤ9, ⋅) is not a group since not all elements have an inverse. To show this we only need to show one element from ℤ9, that is not relatively prime to 9 i.e. gcd(0, 9) = 0. Even though there are 6 other elements with inverses in ℤ9, specifically elements 1, 2, 4, 5, 7, and 8 are relatively prime to 9 so they have inverses in ℤ9.
Taking a look at the example above what if we could make (ℤ9, ⋅) a group? We know it has elements in it that would satisfy all the conditions to be a group, it’s just a few that ruin it. But what if we could just get rid of the elements that don’t satisfy the inverse condition? For example:
ℤ9* = {1, 2, 4, 5, 7, 8}
Now if we test all the conditions of a group against (ℤ9*, ⋅) we can see that it is a group! Lets give a definition to this:
Definition:
The set ℤn* which consists of all integers i = 0, 1, …, n – 1 for which gcd(i, n) = 1 forms an abelian group under multiplication modulo n. The identity element is e = 1.
If you are similar to me you may have the same thought I had when I first learned of this, and that is what about closeness. Recall that the first condition of a group is that if you do an operation on two elements of a group the result will also be in the group. But what if that result is one of the elements we just kicked out? If this were the case then this would no longer be a group, and this is correct it would if it were possible. Surprisingly the result can’t be an element that we kicked out. This has quite a clever and elegant proof, but I understand most don’t enjoy reading maths proofs like I do so I will spare you. But if you still don’t believe me I suggest you try it yourself with the example above!
It is important to state that in cryptography in many cases we are using groups in the form ℤp* where p is a prime, and this still forms a multiplicative group. You may think this is redundant because if p is prime then of course p will be relatively prime to all the elements in ℤp*. But don’t forget 0! So in fact you have to take out 0 from all these groups, in this case, the group would look like this:
ℤp* = {1, 2, …, p – 1}
It is also important to note that the inverse a-1 of each element a ∈ ℤn* can be computed using the Extended Euclidean Algorithm, if you want to learn more about that make sure to check out the Introduction to Asymmetric Cryptography.
Cyclic Groups
In cryptography, we almost always work within finite structures. For example, the AES is built in a finite field. But I kind of just assumed we are working on the same definition of finite, so lets have a probably redundant definition just to ensure we are on the same page:
Definition:
A group (G, ∘) is finite if it has a finite number of elements. We call that amount of elements the cardinality (or order) of the group G denoted |G|.
Here are a few examples of cardinality for groups:
Examples of Group cardinality:
- (ℤ9*, ⋅) the cardinality of ℤ9* is |ℤ9*| = 6.
- (ℤn, ⋅) the cardinality of ℤn is |ℤn| = n.
This is pretty simple, but there is a reason! The next part is an important fact to notice about finite groups. To show this let me first introduce it in an example and then we will define it.
Example: Let ℤ11* = {1, 2, …, 10}, and lets ask the question. What happens if we compute all the powers of a = 3 inside this finite group we made ℤ11*. Let’s list them all out:
a1 = 3 mod 11 = 3.
a2 = 9 mod 11 = 9.
a3 = 27 mod 11 = 5.
a4 = 81 mod 11 = 4.
a5 = 243 mod 11 = 1.
a6 = 729 mod 11 = 3.
a7 = 2,187 mod 11 = 9.
a8 = 6,561 mod 11 = 5.
a9 = 19,683 mod 11 = 4.
a10 = 59,049 mod 11 = 1.
Did you notice anything from that example? Our answers are repeated after we reach 1! Notice how after a5 =ur answers start cycling from the top starting again with 3 and going till we get 1 again with a10. Maybe now it is clear why this section is titled “Cyclic Groups”.
Now you may be asking, so what? Why is this important? Consider a scenario where we wanted to compute:
3306,432,218 mod 11 = ?
Well I don’t know, my cat walked on my keyboard to type that number. But at least we know that there are only 5 possible answers i.e. 1, 3, 9, 5, and 4. This property has a notation and it is called the “order of a” and is denoted as ord(a). For exampled, ord(3) = 5. Let’s do another example, but this time have a goal of finding the order of a.
Example: Let ℤ11* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and a = 2. What is ord(2) = ?. Well lets list all to results we get from the powers of 2 in ℤ11*.
a1 = 2 mod 11 = 2.
a2 = 4 mod 11 = 4.
a3 = 8 mod 11 = 8.
a4 = 16 mod 11 = 5.
a5 = 32 mod 11 = 10.
a6 = 64 mod 11 = 9.
a7 = 128 mod 11 = 7.
a8 = 256 mod 11 = 3.
a9 = 512 mod 11 = 6.
a10 = 1,024 mod 11 = 1.
a11 = 2,048 mod 11 = 2.
Notice how we don’t start repeating until a10= 1, so ord(2) = 10. *note how |ℤ11*| = 10, this will be important soon.
If you are observant you may have noticed that we have all possible elements from ℤ11* generated from powers of 2 modulo 11. These are actually very special numbers and we call them generators because they “generate” groups. Here is a definition of generators:
Definition of Cyclic Groups:
A group G which contains an element α with maximum order ord(α) = |G| is said to be cyclic. Elements with this maximum order are called generators or primitive elements.
An important thing to notice is the use of α, this is not a coincidence. Recall the public parameters needed in DHKE which were a large prime p and an integer α. This is by design, and we can finally answer how we get this α for DHKE. The public parameter α is a generator! So now we have to figure out how we find these cyclic groups G, which by definition a cyclic group must have an element α such that ord(α) = |G|? Thankfully it’s actually pretty easy, and we have a theorem for it!
Theorem:
For every prime p, the group (ℤp*, ⋅) is an abelian finite cyclic group.
Okay so now we know how to get a cyclic group, thus for each cyclic group, we make we know there exists at least one generator. But we don’t have a good method of finding these generators that is better than just brute-forcing them. Unfortunately, there is no fast algorithm to find these generators (at least that I know of). But that doesn’t mean hope is lost because there is no rule saying we can’t reuse public parameters. There are many publications with finite groups and their generators which you can use for your Diffie-Hellman Key Exhchange.
These groups are very popular in cryptography because these are the most popular for building discrete logarithm cryptosystems (which the next post will cover). I should also mention as of the time I am writing this (Nov 2023) it is still believed when quantum computers obtain enough qubits, that cryptosystems like DHKE and RSA that rely on the discrete logarithm problem for security will be rendered unsafe. Even if that is the case, I believe that these cryptosystems give a great starting point for readers wanting to get into public key infrastructure, and post-quantum cryptography.
Code Implementation
Here is my code implementation of the Diffie-Hellman Key Exchange protocol in Python this is done for educational purposes, so should not be used for documents that need verifiable security. This implementation for my blog uses Group #14 from https://www.ietf.org/rfc/rfc3526.txt. If you want to see more cryptography implementations check out my GitHub here.
# By: Hunter Richardson
# Date: 11/4/2023
# For the purpose of education
# This implementation is tested using NIST standards:
# Used Group #14 from https://www.ietf.org/rfc/rfc3526.txt
import random
p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
alpha = 2
def main():
a = random.randint(2, p-2)
A = pow(alpha, a, p)
b = random.randint(2, p-2)
B = pow(alpha, b, p)
K_A = pow(B, a, p)
K_B = pow(A, b, p)
if K_A == K_B:
K_AB = K_A
print("K_AB = " + str(K_AB))
else:
print("Something went wrong, and K_A != K_B")
if __name__ == '__main__':
main()
