Published • Updated
Modular Arithmetic and the Diffie-Hellman Algorithm
I recently took an interest in cryptography and began working through Simon Singh’s The Code Book and some supplementary resources for beginners. For the most part, it was smooth sailing until I arrived at the chapter on public key cryptography and the Diffie-Hellman key exchange. The concept itself made sense after I read through some analogies involving color mixing, especially in this video by Art of the Problem: Public key cryptography - Diffie-Hellman Key Exchange (full version). But I knew that anything more than a superficial understanding of this algorithm was going to require that I become comfortable with the math.
What bothered me is that I couldn’t find many good resources on the Diffie-Hellman key exchange algorithm that really took the time to explain all the math in depth, from start to finish. And most resources assumed I’d fill in the gaps myself. For example, the Computerphile YouTube channel has a great introductory video on the math behind Diffie-Hellman, but it glosses over one of the most important parts—namely, why congruence modulo guarantees that Alice and Bob will arrive at the same private key. So, in this article, I want to first explain congruence modulo in a way that made it click for me and then apply that understanding to the Diffie-Hellman key exchange.
Table of Contents
Prerequisite Knowledge
Modular Arithmetic and the Modulo Operator
In number theory, the binary modulo operation gives the remainder of dividing one number by another number. For example, the remainder of dividing by is . We say that ; we refer to the as the modulus or base of the operation.
Remainders are closely related to the division algorithm:
Division algorithm: Let and be integers such that . Then there exist unique integers and such that , where .
All this says is that if we have two integers and , we can express as a multiple of plus some constant remainder. Or, said differently, if we divide some integer (dividend) by a non-zero integer (divisor), we’ll get an integer known as the quotient () and a remainder (). This should sound familiar from your days of long division. Notice that the remainder can be zero if the quotient divides evenly into the dividend, as in .
The binary modulo operator () just gives us the remainder () in this equation. For example:
- because
- because
- because
- because
- because
- because
- because
- because
- etc.
Modular arithmetic also works with negative integers:
- because
- because
- because
- because
- because
- etc.
The modulo operation always has a finite range of . In other words, if we divide any number by , we’re always going to get a result in the set . Once we evaluate , we wrap back around to zero. gets us back to , and so on. In the examples above, our range is because .
Modulo as a One-Way Function
One useful property of the modulo operator is that it’s a one-way function: Given some modulus , there are infinitely many possible inputs that can generate the same remainder. For example, if I tell you that , you’ll have a hard time figuring out what value of I used to generate this output. There are infinitely many candidates—I could’ve used , , , , and so on.
Divisibility
Since modular arithmetic is about remainders, and remainders arise from division, it’s important to understand the concept of divisibility and the notation that we use:
Divisibility: If divides , then there exists some integer such that . We use the notation to mean that divides .
Here are some examples of this notation:
- because (two divides four)
- because (three divides fifteen)
- because (one divides any number)
- If , then because (any nonzero number divides itself)
This notation for divisibility will be important in the next section on congruence modulo.
Congruence Modulo
Now that we have a better understanding of the modulo operator and some of its related notations, let’s understand one of the most important concepts underlying the Diffie-Hellman key exchange: congruence modulo.
Earlier, we observed that there are many numbers that, when divided by , give us the same remainder. For example:
- … and so on.
It would be inconvenient to have to spell out this relationship with words every time we want to express this “sameness,” so we can instead use a special notation to mean the same thing:
You would read this as: “ and are congruent modulo .” In plain terms, this says that and have the same remainder when divided by .
For example, in our earlier exploration, we found that many numbers map to the same remainder when divided by . Here are just some of those congruence relations:
- because and
- because and
- because and
- because and
Congruence Modulo and Divisibility
Okay, so congruence modulo means that two numbers and have the same remainder when divided by , so we say that . But we can also express this relationship in equation form by applying the division algorithm to and :
For some .
Observe that and are the same in both equations; this is because is the shared modulus, and is the shared remainder. This is just another way of expressing the same idea behind .
Subtracting the second equation from the first gives us:
Since and , it follows that , so this goes back to our definition of divisibility, which says that is divisible by if it can be written as some integer multiple of . Indeed, that’s the case here! So we can conclude that:
This leads us to an equivalent and very useful definition of congruence modulo:
Congruent modulo: Two integers and are congruent modulo if . (Or, equivalently, if since we can factor out a from both sides: . In other words, is symmetric.)
This fact may not seem all that exciting, but it makes it easier for us to prove several useful properties of congruence modulo that are essential to understanding the math in the Diffie-Hellman exchange. And that’s precisely what we’ll do in the next section.
Congruence Modulo Rules
A big thanks to the following resources for helping me with these proofs:
- Bill Dubuque’s answer on the Math StackExchange forum
- https://proofwiki.org/
- Quantitative Reasoning: Computers, Number Theory and Cryptography (PDF).
I highly recommend working through them yourself—these proofs are going to help us understand how the math works in the Diffie-Hellman key exchange.
Note that there are more modulo rules than the ones we’re going to focus on here for the purposes of understanding Diffie-Hellman. For example, congruence modulo also obeys a sum rule that, while interesting, is not relevant to our discussion.
Congruence of Remainder
Congruence of remainder: Let be the remainder of dividing by . Then . That is, both and generate the same remainder when divided by . Intuitively, this just means that a remainder keeps returning itself if we repeatedly divide it by the modulus that generated it in the first place.
Proof: This is an if-and-only-if statement, so we’ll prove both directions.
First, suppose is the remainder of dividing by . Then, by applying the division algorithm to and , we can also express this fact as , where is the quotient of dividing by and is the same remainder as in our statement. Now, we want to show that to prove that . We can do this by rearranging the equation:
Now, for the reverse direction, suppose that . Then it follows by the definition of congruence modulo that , which in turn means we can write as a multiple of for some constant :
Where .
Per the division algorithm, this equation tells us that is the remainder of dividing by .
Congruence of Product
Congruence of product: If and , then .
Proof: By definition of congruence modulo, if and , then and . This allows us to write two equations:
For some .
Rearranging these equations to solve for and , we get:
Finally, multiplying the two equations together gives us:
Since , it must be true that . Thus, this simplifies to:
Therefore, , which means that .
Congruence of Powers
Congruence modulo also has the following useful property:
Congruence of powers: If , then .
In other words, this says that if two integers have the same remainder when divided by , then they will still have the same remainder as each other when divided by if we raise both of them to the same power. (But the remainder need not be the same as before.)
Proof: We will use a proof by weak induction.
Suppose that . For the base step of , this is tautologically true because , which we’re told is the case. Next, suppose . We will show that if , then .
Induction step: Suppose for . We’re given that , so we can use the the product rule to multiply the left-hand side of this relation by and the right-hand side by :
But that’s just .
Therefore, by induction, .
Transitive Property of Congruence
Finally, one of the steps in the Diffie-Hellman algorithm will make use of this property:
Transitive property: If and , then .
Proof: Suppose and . Then, by definition:
For some .
Subtracting the second equation from the first gives:
Since , it follows that , and thus . Therefore, .
The Diffie-Hellman Key Exchange
We’re done with the theoretical part. Now, it’s time to look at the Diffie-Hellman key exchange itself and understand why the math works. Armed with the proofs we just completed, we should be able to show that Alice and Bob are able to generate the same private key using information they shared with each other publicly (known as public-key exchange).
In public key exchange, Alice and Bob want to communicate private information with each other, but they must do so over a public (and therefore insecure) communication network where Eve is eavesdropping on them. The Diffie-Hellman key exchange allows Alice and Bob to establish a shared key for deciphering each other’s messages by sharing information publicly in such a way that it’s difficult for Eve to figure out what private keys they used independently.
Alice and Bob Go Public
To do this, Alice and Bob are going to leverage modular arithmetic and their knowledge of congruence modulo. First, they agree on two numbers:
- , known as the generator, and
- , a very large prime number, which we’ll call the prime modulus.
They share and publicly, so Eve also knows what they are. But as we’re about to discover, this won’t compromise the security of Alice and Bob’s communication.
The key exchange proceeds as follows:
- Alice and Bob privately choose secret numbers and , respectively. These are their private keys, and they will never share them with each other or anyone else.
- Alice computes privately. Let’s call this remainder . Observe that by congruence of a remainder, . Similarly, Bob computes privately. Let’s call this result . Again, by congruence of a remainder, . These two facts will be very important later. Refer back to the proof if you’re unsure why these relations are true.
- Alice sends to Bob publicly, and Bob sends to Alice publicly. Eve can intercept both numbers, but she’ll have a very difficult time working out what and were used, especially if Alice and Bob chose a large prime modulus .
- Alice privately computes to get another remainder, . Bob privately computes and somehow gets the same remainder, . Here, is their shared private key.
- Now, Alice and Bob use this shared private key, , to secure their communication. To arrive at the same key, Eve would need to know either or , which were never shared publicly.
But how is this possible?
How Did Alice and Bob Get the Same Number?
In step two, Alice calculated the remainder of dividing by , which we defined to be :
And Bob calculated the remainder of dividing by , which we defined to be :
By congruence of remainder, we also concluded the following:
In other words, and generate the same remainder when divided by the prime modulus, . Likewise, and generate the same remainder when divided by . This is a trivial fact that follows from the nature of modular arithmetic: remainders just wrap back around to themselves upon repeat division with the same modulus.
Here is where the magic happens. Using congruence of powers, we can keep these congruence relations intact and raise both sides to the same power, as Alice and Bob did in the final step:
Simplifying the right-hand side of each relation, we get:
The right-hand side of each relation is the same. Per the transitive property of congruence modulo, this implies that:
In other words, and generate the same remainder, , when divided by . So when Alice and Bob compute their remainders privately in the final step, they actually get the same value for —just as if they had both shared their private keys and and then calculated publicly. But in reality, Alice doesn’t know , Bob doesn’t know , and Eve is completely stumped!
Summary
Admittedly, that was a lot of math and theory just for a few paragraphs’ worth of explanation, but this foundational knowledge is what finally made the Diffie-Hellman algorithm click for me. It wasn’t until I worked through these proofs myself and put them all together that I understood how it all works. I mainly wrote this article for myself as a post-mortem, in the spirit of learning by teaching and in case I ever forget the proofs. I hope it also helped you!