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 77 by 33 is 11. We say that 7mod3=17 \bmod 3 = 1; we refer to the 33 as the modulus or base of the operation.

Remainders are closely related to the division algorithm:

Division algorithm: Let aa and bb be integers such that b0b \neq 0. Then there exist unique integers qq and rr such that a=qb+ra = qb + r, where 0r<b0 \leq r < |b|.

All this says is that if we have two integers aa and bb, we can express aa as a multiple of bb plus some constant remainder. Or, said differently, if we divide some integer aa (dividend) by a non-zero integer bb (divisor), we’ll get an integer known as the quotient (qq) and a remainder (rr). 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 4÷24 \div 2.

The binary modulo operator (amodba \bmod b) just gives us the remainder (rr) in this equation. For example:

  • 0mod4=00 \bmod 4 = 0 because 0=0(4)+00 = 0(4) + 0
  • 1mod4=11 \bmod 4 = 1 because 1=0(4)+11 = 0(4) + 1
  • 2mod4=22 \bmod 4 = 2 because 2=0(4)+22 = 0(4) + 2
  • 3mod4=33 \bmod 4 = 3 because 3=0(4)+33 = 0(4) + 3
  • 4mod4=04 \bmod 4 = 0 because 4=1(4)+04 = 1(4) + 0
  • 5mod4=15 \bmod 4 = 1 because 5=1(4)+15 = 1(4) + 1
  • 6mod4=26 \bmod 4 = 2 because 6=1(4)+26 = 1(4) + 2
  • 7mod4=37 \bmod 4 = 3 because 7=1(4)+37 = 1(4) + 3
  • etc.

Modular arithmetic also works with negative integers:

  • 1mod4=3-1 \bmod 4 = 3 because 1=1(4)+3-1 = -1(4) + 3
  • 2mod4=2-2 \bmod 4 = 2 because 2=1(4)+2-2 = -1(4) + 2
  • 3mod4=1-3 \bmod 4 = 1 because 3=1(4)+1-3 = -1(4) + 1
  • 4mod4=0-4 \bmod 4 = 0 because 4=1(4)+0-4 = -1(4) + 0
  • 5mod4=3-5 \bmod 4 = 3 because 5=2(4)+3-5 = -2(4) + 3
  • etc.

The modulo operation always has a finite range of [0,b1][0, b-1]. In other words, if we divide any number by bb, we’re always going to get a result in the set {0,1,2,3,...,b1}\{0, 1, 2, 3, ..., b - 1\}. Once we evaluate bmodbb \bmod b, we wrap back around to zero. (b+1)modb(b + 1) \bmod b gets us back to 11, and so on. In the examples above, our range is {0,1,2,3}\{0, 1, 2, 3\} because b=4b = 4.

Modulo as a One-Way Function

One useful property of the modulo operator is that it’s a one-way function: Given some modulus pp, there are infinitely many possible inputs that can generate the same remainder. For example, if I tell you that xmod4=3x \bmod 4 = 3, you’ll have a hard time figuring out what value of xx I used to generate this output. There are infinitely many candidates—I could’ve used x=3x = 3, x=1x = -1, x=5x = -5, x=12358712385235x = 12358712385235, 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 bb divides aa, then there exists some integer kk such that a=kba = kb. We use the notation bab|a to mean that bb divides aa.

Here are some examples of this notation:

  • 242|4 because 4=2(2)4 = 2(2) (two divides four)
  • 3153|15 because 15=3(5)15 = 3(5) (three divides fifteen)
  • 1a1|a because a=1(a)a = 1(a) (one divides any number)
  • If x0x \neq 0, then xxx|x because x=1(x)x = 1(x) (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 pp, give us the same remainder. For example:

  • 9mod4=19 \bmod 4 = 1
  • 5mod4=15 \bmod 4 = 1
  • 1mod4=11 \bmod 4 = 1
  • … 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:

ab(modp)a \equiv b \pmod{p}

You would read this as: “aa and bb are congruent modulo pp.” In plain terms, this says that aa and bb have the same remainder when divided by pp.

For example, in our earlier exploration, we found that many numbers map to the same remainder when divided by 44. Here are just some of those congruence relations:

  • 04(mod4)0 \equiv 4 \pmod{4} because 0=0(4)+00 = 0(4) + 0 and 4=1(4)+04 = 1(4) + 0
  • 15(mod4)1 \equiv 5 \pmod{4} because 1=0(4)+11 = 0(4) + 1 and 5=1(4)+15 = 1(4) + 1
  • 35(mod4)-3 \equiv 5 \pmod{4} because 3=1(4)+1-3 = -1(4) + 1 and 5=1(4)+15 = 1(4) + 1
  • 37(mod4)3 \equiv 7 \pmod{4} because 3=0(4)+33 = 0(4) + 3 and 7=1(4)+37 = 1(4) + 3

Congruence Modulo and Divisibility

Okay, so congruence modulo means that two numbers aa and bb have the same remainder when divided by pp, so we say that ab(modp)a \equiv b \pmod{p}. But we can also express this relationship in equation form by applying the division algorithm to a÷pa \div p and b÷pb \div p:

a=q1(p)+rb=q2(p)+ra = q_1(p) + r \\ b = q_2(p) + r

For some q1,q2Zq_1, q_2 \in \Z.

Observe that pp and rr are the same in both equations; this is because pp is the shared modulus, and rr is the shared remainder. This is just another way of expressing the same idea behind ab(modp)a \equiv b \pmod{p}.

Subtracting the second equation from the first gives us:

(ab)=(q1q2)p(a - b) = (q_1 - q_2)p

Since q1Zq_1 \in \Z and q2Zq_2 \in \Z, it follows that q1q2Zq_1 - q_2 \in \Z, so this goes back to our definition of divisibility, which says that aba - b is divisible by pp if it can be written as some integer multiple of pp. Indeed, that’s the case here! So we can conclude that:

pabp|a-b

This leads us to an equivalent and very useful definition of congruence modulo:

Congruent modulo: Two integers aa and bb are congruent modulo pp if pabp|a - b. (Or, equivalently, if pbap|b-a since we can factor out a (1)(-1) from both sides: ba=(q2q1)p=q3pb - a = (q_2 - q_1)p = q_3p. In other words, ab(modp)a \equiv b \pmod{p} 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:

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 r=amodpr = a \bmod p be the remainder of dividing aa by pp. Then ra(modp)r \equiv a \pmod{p}. That is, both rr and aa generate the same remainder when divided by pp. 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 r=amodpr = a \bmod p is the remainder of dividing aa by pp. Then, by applying the division algorithm to aa and pp, we can also express this fact as a=qp+ra = qp + r, where qZq \in \Z is the quotient of dividing aa by pp and rZr \in \Z is the same remainder as in our statement. Now, we want to show that prap|r-a to prove that ra(modp)r \equiv a \pmod{p}. We can do this by rearranging the equation:

a=qp+rar=qpra=p(q)prara(modp)a = qp + r \\ a - r = qp \\ r - a = p(-q) \\ p|r-a \\ r \equiv a \pmod{p}

Now, for the reverse direction, suppose that ra(modp)r \equiv a \pmod{p}. Then it follows by the definition of congruence modulo that prap|r-a, which in turn means we can write rar-a as a multiple of pp for some constant k1Zk_1 \in \Z:

ra=k1pa=k1pra=(k1)p+ra=k2p+rr - a = k_1p \\ -a = k_1p - r \\ a = (-k_1)p + r \\ a = k_2p + r

Where k2=k1Zk_2 = -k_1 \in Z.

Per the division algorithm, this equation tells us that r=amodpr = a \bmod p is the remainder of dividing aa by pp.

Congruence of Product

Congruence of product: If ab(modp)a \equiv b \pmod{p} and cd(modp)c \equiv d \pmod{p}, then acbd(modp)ac \equiv bd \pmod{p}.

Proof: By definition of congruence modulo, if ab(modp)a \equiv b \pmod{p} and cd(modp)c \equiv d \pmod{p}, then pabp|a-b and pcdp|c-d. This allows us to write two equations:

ab=k1(p)cd=k2(p)a-b = k_1(p) \\ c-d = k_2(p)

For some k1,k2Zk_1, k_2 \in \Z.

Rearranging these equations to solve for aa and cc, we get:

a=k1(p)+bc=k2(p)+da = k_1(p) + b \\ c = k_2(p) + d

Finally, multiplying the two equations together gives us:

ac=(k1p+b)(k2p+d)ac=k1k2p2+k1dp+k2bp+bdacbd=p(k1k2p+k1d+k2b)ac = (k_1p + b)(k_2p + d) \\ ac = k_1k_2p^2 + k_1dp + k_2bp + bd \\ ac - bd = p(k_1k_2p + k_1d + k_2b) \\

Since k1,k2,p,b,dZk_1, k_2, p, b, d \in \Z, it must be true that k3=k1k2p+k1d+k2bZk_3 = k_1k_2p + k_1d + k_2b \in \Z. Thus, this simplifies to:

acbd=p(k3)ac - bd = p(k_3)

Therefore, pacbdp|ac-bd, which means that acbd(modp)ac \equiv bd \pmod{p}.

Congruence of Powers

Congruence modulo also has the following useful property:

Congruence of powers: If ab(modp)a \equiv b \pmod{p}, then anbn(modp)a^n \equiv b^n \pmod{p}.

In other words, this says that if two integers have the same remainder when divided by pp, then they will still have the same remainder as each other when divided by pp 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 ab(modp)a \equiv b \pmod{p}. For the base step of n=1n = 1, this is tautologically true because a1b1(modp)    ab(modp)a^1 \equiv b^1 \pmod{p} \iff a \equiv b \pmod{p}, which we’re told is the case. Next, suppose n>1n > 1. We will show that if anbn(modp)a^n \equiv b^n \pmod{p}, then an+1bn+1(modp)a^{n+1} \equiv b^{n+1} \pmod{p}.

Induction step: Suppose anbn(modp)a^n \equiv b^n \pmod{p} for n>1n > 1. We’re given that ab(modp)a \equiv b \pmod{p}, so we can use the the product rule to multiply the left-hand side of this relation by aa and the right-hand side by bb:

anabnb(modp)a^{n}a \equiv b^nb \pmod{p}

But that’s just an+1bn+1(modp)a^{n+1} \equiv b^{n+1} \pmod{p}.

Therefore, by induction, anbn(modp)a^n \equiv b^n \pmod{p}.

Transitive Property of Congruence

Finally, one of the steps in the Diffie-Hellman algorithm will make use of this property:

Transitive property: If ax(modp)a \equiv x \pmod{p} and bx(modp)b \equiv x \pmod{p}, then ab(modp)a \equiv b \pmod{p}.

Proof: Suppose ax(modp)a \equiv x \pmod{p} and bx(modp)b \equiv x \pmod{p}. Then, by definition:

ax=(k1)pbx=(k2)pa - x = (k_1)p \\ b - x = (k_2)p

For some k1,k2Zk_1, k_2 \in \Z.

Subtracting the second equation from the first gives:

ab=(k1k2)pa-b = (k_1-k_2)p

Since k1,k2Zk_1, k_2 \in \Z, it follows that k1k2Zk_1-k_2 \in \Z, and thus pabp|a-b. Therefore, ab(modp)a \equiv b \pmod{p}.

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:

  1. gg, known as the generator, and
  2. pp, a very large prime number, which we’ll call the prime modulus.

They share gg and pp 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:

  1. Alice and Bob privately choose secret numbers AA and BB, respectively. These are their private keys, and they will never share them with each other or anyone else.
  2. Alice computes gAmodpg^A \bmod p privately. Let’s call this remainder rAr_A. Observe that by congruence of a remainder, rAgA(modp)r_A ≡ g^A \pmod{p}. Similarly, Bob computes gBmodpg^B \bmod p privately. Let’s call this result rBr_B. Again, by congruence of a remainder, rBgB(modp)r_B ≡ g^B \pmod{p}. These two facts will be very important later. Refer back to the proof if you’re unsure why these relations are true.
  3. Alice sends rAr_A to Bob publicly, and Bob sends rBr_B to Alice publicly. Eve can intercept both numbers, but she’ll have a very difficult time working out what AA and BB were used, especially if Alice and Bob chose a large prime modulus pp.
  4. Alice privately computes (rB)Amodp(r_B)^A \bmod p to get another remainder, rkr_k. Bob privately computes (rA)Bmodp(r_A)^B \bmod p and somehow gets the same remainder, rkr_k. Here, rkr_k is their shared private key.
  5. Now, Alice and Bob use this shared private key, rkr_k, to secure their communication. To arrive at the same key, Eve would need to know either AA or BB, 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 gAg^A by pp, which we defined to be rAr_A:

rA=gAmodpr_A = g^A \bmod p

And Bob calculated the remainder of dividing gBg^B by pp, which we defined to be rBr_B:

rB=gBmodpr_B = g^B \bmod p

By congruence of remainder, we also concluded the following:

rAgA(modp)rBgB(modp)r_A \equiv g^A \pmod{p} \\ r_B \equiv g^B \pmod{p} \\

In other words, rAr_A and gAg^A generate the same remainder when divided by the prime modulus, pp. Likewise, rBr_B and gBg^B generate the same remainder when divided by pp. 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:

(rA)B(gA)B(modp)(rB)A(gB)A(modp)(r_A)^B \equiv (g^A)^B \pmod{p} \\ (r_B)^A \equiv (g^B)^A \pmod{p} \\

Simplifying the right-hand side of each relation, we get:

(rA)BgAB(modp)(rB)AgAB(modp)(r_A)^B \equiv g^{AB} \pmod{p} \\ (r_B)^A \equiv g^{AB} \pmod{p} \\

The right-hand side of each relation is the same. Per the transitive property of congruence modulo, this implies that:

(rA)B(rB)A(modp)(r_A)^B \equiv (r_B)^A \pmod{p}

In other words, (rA)B(r_A)^B and (rB)A(r_B)^A generate the same remainder, rkr_k, when divided by pp. So when Alice and Bob compute their remainders privately in the final step, they actually get the same value for rkr_k—just as if they had both shared their private keys AA and BB and then calculated gABmodpg^{AB} \bmod p publicly. But in reality, Alice doesn’t know BB, Bob doesn’t know AA, 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!

Sources and Further Reading