Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers (8 page)

The number-mixing trick, step 3: The public-private numbers are available to anyone who wants them.

Actually, when you think about it the right way, this isn't amazing at all. When Arnold and you managed to both produce the same shared secret color, it was because you mixed together the same three original colors, but in a different order: each of you kept one of the colors private, combining it with a publicly available mixture of the other two. The same thing has happened here with numbers. You both arrived at the same shared secret by multiplying together the same three numbers: 4, 6, and 7. (Yes, as you can check for yourself, 4 × 6 × 7 = 168.) But
you
arrived at the shared secret by keeping 4 private and “mixing” (i.e., multiplying) it with the publicly available mixture of 6 and 7 (i.e., 42) that had been announced by Arnold. On the other hand,
Arnold
arrived at the shared secret by keeping 6 private and mixing it with the publicly available mixture of 4 and 7 (i.e., 28) that you had announced.

Just as we did in the paint-mixing trick, let's now verify that Eve has no chance of working out the shared secret. Eve gets to hear the value of each public-private number as it is announced. So she hears you say “28,” and Arnold say “42.” And she also knows the public number, which is 7. So
if
Eve knew how to do division, she could work out all your secrets immediately, just by observing that 28 ÷ 7 = 4, and 42 ÷ 7 = 6. And she could go on to compute the shared secret by calculating 4 × 6 × 7 = 168. However, luckily, we are using pretend math in this game: we assumed that multiplication was a one-way action and therefore Eve
doesn't
know how to divide. So she is stuck with the numbers 28, 42, and 7. She can multiply some of them together, but that doesn't tell her anything about the shared secret. For example, if she takes 28 × 42 = 1176, she is way off. Just as in the paint-mixing game her result was too yellow, here her result has too many 7's. The shared secret has only one factor of 7 in it, since 168 = 4 × 6 × 7. But Eve's attempt at cracking the secret has two factors of 7 in it, since 1176 = 4 × 6 × 7 × 7. And there's no way she can get rid of that extra 7, since she doesn't know how to do division.

The number-mixing trick, step 4: Only you and Arnold can make the shared secret number, by multiplying together the numbers shown by arrows.

Paint-Mixing in Real Life

We have now covered all of the fundamental concepts needed for computers to establish shared secrets on the internet. The only flaw in the paint-mixing-with-numbers scheme is that it uses “pretend math,” in which we pretended that none of the parties could do division. To complete the recipe, we need a real-life math operation that is easy to do (like mixing paint) but practically impossible to undo

(like unmixing paint). When computers do this in real life, the mixing operation is a thing called
discrete exponentiation
and the unmixing operation is called the
discrete logarithm.
And because there is no known method for a computer to calculate discrete logarithms efficiently, discrete exponentiation turns out to be just the kind of oneway action we are looking for. To explain discrete exponentiation properly, we're going to need two simple mathematical ideas. And we'll also need to write a few formulas. If you don't like formulas, just skip the rest of this section—you already understand almost everything about this topic. On the other hand, if you really want to know how computers do this magic, read on.

The first important math idea we need is called
clock arithmetic.
This is actually something we are all familiar with: there are only 12 numbers on a clock, so every time the hour hand goes past 12, it starts counting again from 1. An activity that starts at 10 o'clock and lasts 4 hours finishes at 2 o'clock, so we might say that 10 + 4 = 2 in this 12-hour clock system. In mathematics, clock arithmetic works the same way, except for two details: (i) the size of the clock can be any number (rather than the familiar 12 numbers on a regular clock), and (ii) the numbers start counting from 0 rather than 1.

The figure on the next page gives an example using the clock size 7. Note that the numbers on the clock are 0, 1, 2, 3, 4, 5, and 6. To do clock arithmetic with clock size 7, just add and multiply numbers together as normal—but whenever an answer is produced, you only count the
remainder
after dividing by 7. So to compute 12 + 6, we first do the addition as normal, obtaining 18. Then we notice that 7 goes into 18 twice (making 14), with 4 left over. So the final answer is

12 + 6 = 4 (clock size 7)

In the examples below, we'll be using 11 as the clock size. (As discussed later, the clock size in a real implementation would be much, much larger. We are using a small clock size to keep the explanation as simple as possible.) Taking the remainder after dividing by 11 isn't too hard, since the multiples of 11 all have repeated digits like 66 and 88. Here are a few examples of calculations with a clock size of 11:

7 + 9 + 8 = 24 = 2 (clock size 11)
8 × 7 = 56 = 1 (clock size 11)

The second math idea we need is
power notation.
This is nothing fancy: it's just a quick way of writing down lots of multiplications of the same number. Instead of writing 6 × 6 × 6 × 6, which is just 6 multiplied by itself 4 times in a row, you can write 6
⁴
. And you can combine power notation with clock arithmetic. For example,

Left: When using a clock size of 7, the number 12 is simplified to the number 5—just start at zero and count 12 units in a clockwise direction, as shown by the arrow. Right: Again using a clock size of 7, we find that 12 + 6 = 4—starting at 5, where we ended in the left figure, add on another 6 units in clockwise direction.

The table on the following page shows the first ten powers of 2, 3, and 6 when using clock size 11. These will be useful in the example we're about to work through. So before plunging on, make sure you're comfortable with how this table was generated. Let's take a look at the last column. The first entry in this column is 6, which is the same thing as 6
¹
. The next entry represents 6
²
, or 36, but since we're using clock size 11 and 36 is 3 more than 33, the entry in the table is a 3. To calculate the third entry in this column, you might think that we need to work out 6
³
=
6
?
6
?
6, but there is an easier way. We have already computed 6
²
for the clock size we're interested in—it turned out to be 3. To get 6
³
, we just need to multiply the previous result by 6. This gives 3 × 6 = 18 = 7 (clock size 11). And the next entry is 7 × 6 = 42 = 9 (clock size 11), and so on down the column.

OK, we are finally ready to establish a shared secret, as used by computers in real life. As usual, you and Arnold will be trying to share a secret, while Eve eavesdrops and tries to work out what the secret is.

This table shows the first ten powers of 2, 3, and 6 when using clock size 11. As explained in the text, each entry can be computed from the one above it by some very simple arithmetic.

To keep the math as easy as possible, we'll use very small numbers in this example. So suppose you choose 8 as your private number, and Arnold chooses 9. These two numbers—8 and 9—are not themselves shared secrets, but just like the private colors you chose in the paint-mixing trick, these numbers will be used as
ingredients
to “mix up” a shared secret.

These public numbers—11 and 2—are analogous to the public color that you and Arnold agreed on at the start of the paint-mixing trick. Note that the paint-mixing analogy does break down a little here: whereas we needed only one public color, two public numbers are needed.

Specifically, the mixing is done according to the formula

PPN = base
^{private number}
(clock size)

This formula might look a little weird written out in words, but it's simple in practice. In our example, we can work out the answers by consulting the table on the previous page:

your PPN = 2
⁸
= 3 (clock size 11) Arnold's PPN = 2
⁹
= 6 (clock size 11)

You can see the situation after this step in the figure on the following page. These public-private numbers are precisely analogous to the “public-private mixtures” that you made in the third step of the paint-mixing trick. There, you mixed one pot of the public color with one part of your private color to make your public-private mixture. Here, you have mixed your private number with the public numbers using power notation and clock arithmetic.

This is done according to the formula

shared secret = other person's PPN
^{private number}
(clock size)

Again this looks a little weird written out in words, but by consulting the table on the previous page, it works out simply in numbers:

your shared secret = 6
⁸
= 4 (clock size 11)
Arnold's shared secret = 3
⁹
= 4 (clock size 11)

The final situation is shown in the figure on page 57.

Naturally, your shared secret and Arnold's shared secret end up being the same number (in this case, 4). It depends on some sophisticated mathematics in this case, but the basic idea is the same as before: although you mixed your ingredients in a different order, both you and Arnold used the same ingredients and therefore produced the same shared secret.