What is a shared secret and why do we need it? It’s a piece of information that you and your friend know, but nobody else knows. You can use this shared secret to encrypt your communication, to ensure it is for your ears and your friend’s ears only.

Mathematically, we can model this secret as some integer. The existence of this integer is not secret—all integers are known to everyone—but knowing among the vast space of integers to use this one to decrypt communication between you and your friend is very hard and that is what forms the basis of this secret.

The Walls Have Ears

Arriving at the secret without constraints is not hard. Whisper into Bob the Builder’s ear that the integer is 42, and you have your shared secret key right there.

The hard part is if you assume the channel through which you are communicating is not safe.

If the walls have ears, how do you share your secret?

For example: on the internet, we have an insecure protocol (HTTP), yet you want to authenticate with your password and transfer funds securely. How do we make a fundamentally insecure channel secure?

The answer is with a bit of math. Enter Diffie-Hellman key exchange.

Diffie-Hellman, Incorporated

A startup, DH Inc. sells a matte black aluminum cube that promises to help you and your friend communicate securely over insecure channels—for the low, low price of 1 Bitcoin. (And because your friend needs one too, the total comes out to 2 Bitcoin, and DH Inc just raised a Series C from top-tier VCs based on this virality.)

An expensive DH, Inc. box

Here’s how they say it will work:

  1. You pick one prime number, and one DH number (we’ll come back to this).
  2. Over an insecure channel, you send your friend these two numbers.
  3. Both you and your friend pick secret numbers (your secret and friend secret)—these are not sent over the insecure channel—and enter them into the DH Inc cube.
  4. The DH Inc cube will whirr and crank for a few seconds, and steam will come out of the top of the cube, and out pops a number—seemingly always less than the prime number you picked in step 1?
  5. You send over the insecure channel the output of the DH Inc cube to your friend, and receive your friend’s DH Inc output number.
  6. You input your friend’s DH Inc output number into your DH Inc cube, and your friend inputs the output you sent into their DH Inc cube.
  7. Your cube whirrs again, even more steam hisses out the top, and the cube lights up green. Done! You get another number, and your friend gets another number outputted, and those two numbers are guaranteed to be the same. That “shared secret” can be used to encrypt further communication over the insecure channel. At no point in time did you send over your secret, or did your friend send over their secret—those are still within the DH Cube. All you sent was a prime number, a special DH number, and the outputs of the cube. Other folks, even if they buy DH cubes, and observe all outputs you send, cannot replicate the shared secret because they don’t have the individual secrets trapped within your DH cube and your friend’s DH cube.
  8. You transmit information about DH Inc’s latest funding round to your friend and gossip back and forth.

You, being this generation’s young Steve Wozniak, want to make an open source version of this box. To do that, you have to figure out how it works.

How does it work? RTFM

Luckily, you find an FAQ on DH Inc’s website. It turns out you don’t need the hardware at all!

All the box does is:

  1. Take an input number to the power of your secret (aka, multiply the input number by itself x times where x is your secret):
    • \[(\text{input number})^{\text{your secret}} = \text{input number} \cdot \text{input number} \cdot \ldots \cdot \text{input number}\]
  2. Take that result and modulo it by the prime number you picked:
    • \[(\text{input number})^{\text{your secret}} \mod (\text{prime number you picked})\]
    • A modulus just takes the remainder of a division by that number.
    • For example: 7 modulo 5 → 5 goes into 7 once → you have 2 left over → 7 modulo 5 is 2.
    • Another example: 19 modulo 7 → 7 goes into 19 twice (7 * 2 is 14) → 19 - (7 * 2) = 19 - 14 = 5 leftover → 19 modulo 7 is 5.
    • It’s also called “clock arithmetic”: if it is 9PM where you are and your friend is 6 hours ahead of you, you “wrap around” the clock to get 3AM instead of 15PM.
      • In a remote world, people get very good at clock arithmetic as they have to balance times across time zones :) - Essentially, if the result of the many multiplications above is extremely large (powers grow quickly, after all), we map that very large number back to the space between 1 and the prime number you picked. We’ll go into why later.
  3. The cube then sleeps 3 seconds, generates steam, hisses and shakes, and outputs the number back to you.

Unbelievably, you’re doing all the hard work here! You’re finding a prime, the special DH number, and all this box does is some arithmetic and generate steam. We’ll come back to how to pick the prime and DH number later.

The first question in our minds is: how does this box possibly arrive at the same number for two different people after all these steps?

Let’s visualize what’s going on here.

On the first run of the DH cube, we’re taking the special DH number you picked in step 1, multiplying it by itself an arbitrary number of times (specified by your secret), and performing a modulus operation—just taking the remainder with respect to division by the prime (also picked in step 1).

\[(\text{input number})^{\text{your secret}} \mod (\text{prime}) \rightarrow \text{send to friend}\]

In the next step, we don’t send your secret to your friend—that would let anyone listening on the insecure channel know your secret number and then derive the shared secret. Instead, we send the result of this computation to your friend over the insecure channel.

Why won’t this give away the shared secret we derive later? Let’s take a look at the next step to find out.

You take the output of the DH Cube, and send it to your friend.

Then, your friend inputs that number into their DH Cube and gets the shared secret. How is this done?

We figured out that the DH Cube is only doing one thing: multiplying an input by itself x times and taking the remainder with respect to a prime.

Your friend’s cube is doing the same operation, just with their secret.

\[\begin{align*} &(\text{DH Cube output you sent to your friend})^{\text{friend secret}} \mod (\text{prime}) \\ &= \left( (\text{DH number})^{\text{your secret}} \mod (\text{prime}) \right)^{\text{friend secret}} \mod (\text{prime}) \\ &= \text{friend-derived secret} \end{align*}\]

Not only did you send your DH cube output to your friend over the insecure channel, you also received your friend’s DH cube output. What does that look like?

\[\begin{align*} &(\text{DH Cube output you received from your friend})^{\text{your secret}} \mod (\text{prime}) \\ &= \left( (\text{DH number})^{\text{friend secret}} \mod (\text{prime}) \right)^{\text{your secret}} \mod (\text{prime}) \\ &= \text{your derived secret} \end{align*}\]

And the key thing we’re saying—how this all works—is they’re the same.

\[\text{friend-derived secret} = \text{your derived secret} \\ = \text{shared secret}\]

Here’s a short proof for how this works—we basically want to show that it doesn’t matter in which order you exponentiate the DH number and modulo it (whether it’s your secret first or your friend’s secret first), you’ll get the same thing.

As we’ve observed, exponentiation is just multiplying something by itself some number of times. So we’ll prove commutativity of multiplication in modulus space; and if we find multiplication works commutatively in modulus space, we know exponentiation works in modulus space.

Let’s try to prove multiplicative commutativity in modulo space. Here’s our desired result.

\[\big((a \mod n) \cdot (b \mod n) \big) \mod n \\ = (a \cdot b) \mod n \\ \text{if we can prove the above, then by commutativity of normal multiplication,} \\ = (b \cdot a) \mod n\]

Let’s start with the product of a and b modulo n.

\[(a \cdot b) \mod n\]

What is a, and what is b?

Another way of writing a is:

\[a = \text{root}_a + \text{constant}_a \cdot n \implies a \mod n = \text{root}_a \\ b = \text{root}_b + \text{constant}_b \cdot n \implies b \mod n = \text{root}_b\]

We’ll abbreviate root and constant. The following means the same thing as above, but makes the proof a bit cleaner.

\[a = \text{r}_a + \text{k}_a \cdot n \implies a \mod n = \text{r}_a \\ b = \text{r}_b + \text{k}_b \cdot n \implies b \mod n = \text{r}_b\]

We’ll plug the definition of a and b into the product.

\[(a \cdot b) \mod n \\ = \big((\text{r}_a + \text{k}_a \cdot n ) \cdot ( \text{r}_b + \text{k}_b \cdot n)\big) \mod n \\ = (r_ar_b + r_ak_bn+r_bk_an+k_ak_bn^2 ) \mod n\]

We can group the terms:

\[=\big(r_ar_b +n\cdot( r_ak_b+r_bk_a+k_ak_bn) \big) \mod n\]

Because we’re working in mod space n, we know that n * anything is going to be 0 when modulo’d with n. So we can rewrite the above as:

\[= (r_ar_b) \mod n\]

We noted above that

\[\text{r}_a = a \mod n \\ \text{r}_b = b \mod n\]

So let’s substitute:

\[(a \cdot b) \mod n \\ = (r_a \cdot r_b) \mod n \\ = \big( (a \mod n) \cdot (b \mod n) \big) \mod n\]

Which is our desired result!

Mapping this back to exponentiation: because exponentiation is iterative multiplication, we can replace the b term with a to see how the above works with powers.

\[\big( (a \mod n) \cdot (a \mod n) \big) \mod n \\ \begin{align*} &= (a \cdot a) &\mod n \\ &= a^2 &\mod n \end{align*}\]

Connecting this to our example above: the shared secret is the same because the order of the exponentiation doesn’t matter. Your friend receives the result that you exponentiated with your secret and exponentiates that result; you receive the result that your friend exponentiated with their secret and exponentiated that. You get the same result, and that’s your shared secret key.

\[\begin{align*} &(\text{DH Cube output you sent to your friend})^{\text{friend secret}} \mod (\text{prime}) \\ &= (\text{DH number})^{\text{your secret}} \mod (\text{prime})^{\text{friend secret}} \mod (\text{prime}) \\ &= (\text{DH number})^{\text{your secret} \cdot \text{friend secret}} \mod (\text{prime}) \\ \\ &= \text{friend-derived secret} = \text{your derived secret} = \text{shared secret} \\ \\ &= (\text{DH number})^{\text{friend secret} \cdot \text{your secret}} \mod (\text{prime}) \\ &= \left( (\text{DH number})^{\text{friend secret}} \mod (\text{prime}) \right)^{\text{your secret}} \mod (\text{prime}) \\ &= (\text{DH Cube output you received from your friend})^{\text{your secret}} \mod (\text{prime}) \end{align*}\]

There are nuances embedded in this, but this in broad strokes is how you can make a fundamentally insecure channel secure—all without paying a Bitcoin for the DH box.

Below, we’ll investigate some of the nuances.

An example with real numbers

Let’s pick a random prime number (229) and a random DH number for that prime number (90).

We’ll work out the Diffie-Hellman key exchange manually for these two numbers.

Let’s say you pick a secret 673 and your friend picks a secret 404. You do not tell each other your secrets.

Let’s run the open-source version of the DH Cube.

\[(\text{DH number})^\text{your secret} \mod (\text{prime}) \\ \begin{align*} \\&= 90^{673} \mod 229 \\&= 24 \end{align*}\]

You pass this number 24 to your friend. Your friend runs the open-source DH Cube on this number and includes their secret in the computation.

\[(\text{your result})^\text{friend secret} \mod (\text{prime})\\ \begin{align*} &=24^{404} \mod 229 \\ &= 144 \end{align*}\]

Your friend knows the shared secret is 144, but you don’t know that yet because you haven’t received the first result from your friend.

So your friend writes down 144 for safekeeping (taking care to not send that information to you). They clear out your result from the machine, inputting the DH number instead.

\[(\text{DH number})^\text{friend secret} \mod (\text{prime}) \\ \begin{align*} \\&= 90^{404} \mod 229 \\&= 91 \end{align*}\]

Your friend sends you this number, 91, and you run the open-source box with your secret, 673.

\[(\text{friend result})^\text{friend secret} \mod (\text{prime})\\ \begin{align*} &=91^{673} \mod 229 \\ &= 144 \end{align*}\]

Now you know, thanks to a reverse-engineered DH Inc machine, a shared secret with your friend!

Formatted, somewhat poorly written DiffieHellman code in Wolfram Language.

What is the special DH Inc number?

We know that this DH Inc number gets multiplied with itself many times before getting modulo’d, and we don’t know exactly how many times beforehand, because exactly how many times is the product of your secret key and your friend’s secret key.

This requires picking a special number—one that, once exponentiated any number of times and modulo’d, will eventually retrieve the set of numbers between 1 and the prime.

Why is this part important? If the exponentiated and modulo’d result only maps to a few values out of the possible set of values, then that means there are much fewer choices for the shared secret. And because the DH number gets sent over the insecure channel, a nosy listener could figure out that the periodicity of the resulting generated values is much lower than what the prime implies, and attempt to decode your subsequent ostensibly secret gossip about the Kardashians with your friend.

The below is an example of a “good” DH number, from the example above (90 with prime 229). This “good” DH number is also called a primitive root, or a generator, because it generates the set of possible residues for that prime number after successive power + modulo operations.

The column order is flipped to make it easier to verify that for every expected generated value (1..228) we have an exponent that maps to that number.

Generated Table

In this case, the number 90 is special because, when exponentiated and modulo’d, we are able to retrieve all numbers between 1 and 229 (this is termed the least residue system modulo 229).

If we try the same thing with DH number as 89, for example, we only get 12 unique numbers/residues (1, 18, 89, 94, 95, 107, 122, 134, 135, 140, 211, 228) instead of 228 unique residues. This makes the secret generation much weaker because only 12/228, or ~5%, of the space of possible residues are used for possible secrets.

In practice, the prime space is huge, and the DH numbers are good, so that generating the secret space would take an unimaginably long time.

Trivia

The inventor of public key cryptography—six years prior to Diffie & Hellman’s work—had their work classified for his entire life as it was discovered during employment by the British intelligence service. James H. Ellis died a month before his work was given public acknowledgement.