Remember that this paint-mixing game is meant to explain how to establish a shared secret. At this point you may well be wondering what on earth mixing paints has got to do with cryptography, but don't worry. You are about to learn an amazing trick that is actually used by computers to establish shared secrets in a public place like the internet!
First, we need to know the objective of the game. The objective is for you and Arnold to each produce the same mixture of paint, without telling Eve how to produce it. If you achieve this, we'll say that you and Arnold have established a “shared secret mixture.” You are allowed to have as much public conversation as you like, and you are also allowed to carry pots of paint back and forth between the middle of the room and your private mixing area.
Now we begin our journey into the ingenious ideas behind public key cryptography. Our paint-mixing trick will be broken down into four steps.
Step 1. You and Arnold each choose a “private color.”
Your private color is not the same thing as the shared secret mixture that you will eventually produce, but it will be one of the ingredients in the shared secret mixture. You can choose any color you want as your private color, but you have to remember it. Obviously, your private color will almost certainly be different from Arnold's, since there are so many colors to choose from. As an example, let's say your private color is lavender and Arnold's is crimson.
Step 2. One of you publicly announces the ingredients of a new, different color that we'll call the “public color.”
Again, you can choose anything you like. Let's say you announce that the public color is daisy-yellow. Note that there is only one public color (not two separate ones for you and Arnold), and, of course, Eve knows what the public color is because you announce it publicly.
Step 3. You and Arnold each create a mixture by combining one pot of the public color with one pot of your private color. This produces your “public-private mixture.”
Obviously, Arnold's public-private mixture will be different from yours, because his private color is different from yours. If we stick with the above example, then your public-private mixture will contain one pot each of lavender and daisy-yellow, whereas Arnold's public-private mixture consists of crimson and daisy-yellow.
At this point, you and Arnold would like to give each other samples of your public-private mixtures, but remember it's against the rules to directly give a mixture of paint to one of the other people in the room. The only way to give a mixture to someone else is to make several batches of it and leave them in the middle of the room so that anyone who wants one can take it. This is exactly what you and Arnold do: each of you makes several batches of your public-private mixture and leaves them in the middle of the room. Eve can steal a batch or two if she wants, but as we will learn in a minute, they will do her no good at all. The figure on the following page shows the situation after this third step of the paint-mixing trick.
OK, now we're getting somewhere. If you think hard at this point, you might see the final trick that would allow you and Arnold to each create an identical shared secret mixture without letting Eve in on the secret. Here's the answer:
The paint-mixing trick, step 3: The public-private mixtures are available to anyone who wants them.
Step 4. You pick up a batch of Arnold's public-private mixture and take it back to your corner. Now add one pot of your private color. Meanwhile, Arnold picks up a batch of your public-private mixture and takes it back to his corner, where he adds it to a pot of his private color.
Amazingly, you have both just created identical mixtures! Let's check: you added your private color (lavender) to Arnold's public-private mixture (crimson and daisy-yellow), resulting in a final mixture of 1 lavender, 1 crimson, 1 daisy-yellow. What about Arnold's final mixture? Well, he added his private color (crimson) to your public-private mixture (lavender and daisy-yellow), resulting in a final mixture of 1 crimson, 1 lavender, 1 daisy-yellow. This is exactly the same as your final mixture. It really is a shared secret mixture. The figure on the next page shows the situation after this final step of the paint-mixing trick.
Now, what about Eve? Why can't she create a batch of this shared secret mixture? The reason is that she doesn't know your private color or Arnold's private color, and she needs at least one of them to create the shared secret mixture. You and Arnold have thwarted her, because you never left your private colors exposed, on their own, in the middle of the room. Instead, you each combined your private color with the public color before exposing it, and Eve has no way of “unmixing” the public-private mixtures to obtain a pure sample of one of the private colors.
The paint-mixing trick, step 4: Only you and Arnold can make the shared secret color, by combining the mixtures shown by arrows.
Thus, Eve has access only to the two public-private mixtures. If she mixes one batch of your public-private mixture with one batch of Arnold's public-private mixture, the result will contain 1 crimson, 1 lavender, and 2 daisy-yellow. In other words, compared to the shared secret mixture, Eve's mixture has an extra daisy-yellow. Her mixture is too yellow, and because there's no way to “unmix” paint, she can't remove that extra yellow. You might think Eve could get around this by adding more crimson and lavender, but remember she doesn't know your private colors, so she wouldn't know that these are the colors that need to be added. She can only add the combination of crimson plus daisy-yellow or lavender plus daisy-yellow, and these will always result in her mixture being too yellow.
Paint-Mixing with Numbers
If you understand the paint-mixing trick, you understand the essence of how computers establish shared secrets on the internet. But, of course, they don't really use paint. Computers use numbers, and to mix the numbers they use mathematics. The actual math they use isn't too complicated, but it's complicated enough to be confusing at first. So, for our next step toward understanding how shared secrets are established on the internet, we will use some “pretend” math. The real point is that to translate the paint-mixing trick into numbers, we need a one-way action: something that can be done, but can't be undone. In the paint-mixing trick the one-way action was “mixing paint.” It's easy to mix some paints together to form a new color, but it's impossible to “unmix” them and get the original colors back. That's why paint-mixing is a one-way action.
We found out earlier that we would be using some pretend math. Here is what we are going to pretend: multiplying two numbers together is a one-way action. As I'm sure you realize, this is definitely a pretense. The opposite of multiplication is division, and it's easy to undo a multiplication just by performing a division. For example, if we start with the number 5 and then multiply it by 7, we get 35. It's easy to undo this multiplication by starting with 35 and dividing by 7. That gets us back to the 5 we started with.
But despite that, we are going to stick with the pretense and play another game between you, Arnold, and Eve. And this time, we'll assume you all know how to multiply numbers together, but none of you knows how to divide one number by another number. The objective is almost the same as before: you and Arnold are trying to establish a shared secret, but this time the shared secret will be a number rather than a color of paint. The usual communication rules apply: all communication must be public, so Eve can hear any conversations between you and Arnold.
OK, now all we have to do is translate the paint-mixing trick into numbers:
Step 1. Instead of choosing a “private color,” you and Arnold each choose a “private number.”
Let's say you choose 4 and Arnold chooses 6. Now think back to the remaining steps of the paint-mixing trick: announcing the public color, making a public-private mixture, publicly swapping your public-private mixture with Arnold's, and finally adding your private color to Arnold's public-private mixture to get the shared secret color. It shouldn't be too hard to see how to translate this into numbers, using multiplication as the one-way action instead of paint-mixing. Take a couple of minutes to see if you can work out this examp
le for yourself, before reading on.
The solution isn't too hard to follow; you've already both chosen your private numbers (4 and 6), so the next step is
Step 2. One of you announces a “public number” (instead of the public color in the paint-mixing trick).
Let's say you choose 7 as the public number.
The next step in the paint-mixing trick was to create a public-private mixture. But we already decided that instead of mixing paints we would be multiplying numbers. So all you have to do is
Step 3. Multiply your private number (4) and the public number (7) to get your “public-private number,” 28.
You can announce this publicly so that Arnold and Eve both know your public-private number is 28 (there's no need to carry pots of paint around anymore). Arnold does the same thing with his private number: he multiplies it by the public number, and announces his public-private number, which is 6 × 7, or 42. The figure on the following page shows the situation at this point in the process.
Remember the last step of the paint-mixing trick? You took Arnold's public-private mixture, and added a pot of your private color to produce the shared secret color. Exactly the same thing happens here, using multiplication instead of paint-mixing:
Step 4. You take Arnold's public-private number, which is 42, and multiply it by your private number, 4, which results in the shared secret number, 168.
Meanwhile, Arnold takes your public-private number, 28, and multiplies it by his private number, 6, and—amazingly—gets the same shared secret number, since 28 × 6 = 168. The final result is shown in the figure on the facing 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 64. 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 61. The next entry represents 62, 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 63 = 6 ? 6 ? 6, but there is an easier way. We have already computed 62 for the clock size we're interested in—it turned out to be 3. To get 63, 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.
Step 1. You and Arnold each separately choose a private number.
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.
Step 2. You and Arnold publicly agree on two public numbers: a clock size (we'll use 11 in this example) and another number, called the base (we'll use the base 2).
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.
Step 3. You and Arnold each separately create a public-private number (PPN) by mixing up your private number with the public numbers, using power notation and clock arithmetic.
Specifically, the mixing is done according to the formula
PPN = baseprivate 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:
Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers Page 6