Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers

by John MacCormick

A paper document with a handwritten signature.

  A bank that stores the identities of its customers together with handwritten signatures on file.

  To verify Ravi's signature on the document promising to pay Fran-coise, we just need to go to the paper signature bank and ask to see Ravi's signature. Obviously, we are making two important assumptions here. First, we assume the bank can be trusted. In theory, it would be possible for the bank employees to switch Ravi's signature for an imposter's, but we are going to ignore this possibility here. Second, we assume it is impossible for an imposter to forge Ravi's signature. This assumption, as everyone knows, is plain wrong: a skilled forger can easily reproduce a signature, and even amateurs can do a reasonable approximation. Nevertheless, we need the assumption of unforgeability—without it, the paper signature is useless. Later on, we will see how digital signatures are essentially impossible to forge. This is one of the big advantages of digital signatures over paper ones.

  SIGNING WITH A PADLOCK

  Our first step toward digital signatures is to abandon paper signatures altogether and adopt a new method of authenticating documents that relies on padlocks, keys, and locked boxes. Every participant in the new scheme (in our running example, that means Ravi, Takeshi, and Francoise) acquires a large supply of padlocks. It is crucial that the padlocks belonging to each individual participant are identical—so Ravi's padlocks are all the same. Additionally, each participant's padlocks must be exclusive: no one else can make or obtain a padlock like Ravi's. And finally, all padlocks in this chapter have a rather unusual feature: they are equipped with biometric sensors which ensure they can only be locked by their owner. So if Francoise finds an open padlock belonging to Ravi, she can't use it to lock anything. Of course, Ravi also has a supply of keys that will open his padlocks. Because all of his padlocks are identical, all the keys are identical too. The situation so far is shown schematically on the following page. This is the initial setup for what we might call the “physical padlock trick.”

  Now let's suppose that just as before, Ravi owes Francoise $100, and Francoise would like to record that fact in a verifiable way. In other words, Francoise wants the equivalent of the document on the previous page, but without relying on a handwritten signature. Here is how the trick is going to work. Ravi makes a document saying “Ravi promises to pay $100 to Francoise,” and doesn't bother to sign it. He makes a copy of the document and places this document in a lockbox. (A lockbox is just a strongly made box that can be locked with a padlock.) Finally, Ravi locks the box with one of his padlocks and gives the locked box to Francoise. The complete package is shown in the figure on the facing page. In a sense that will be made precise very soon, the locked box is the signature for the document. Note that it would be a good idea for Francoise, or some other trusted witness, to watch while the signature is created. Otherwise, Ravi could cheat by putting a different document into the box. (Arguably, this scheme would work even better if the lockboxes were transparent. After all, digital signatures provide authenticity, not secrecy. However, transparent lockboxes are a little counterintuitive, so we won't pursue this possibility.)

  In the physical padlock trick, each participant has

  an exclusive supply of identical padlocks and keys.

  Perhaps you can already see how Francoise can now authenticate Ravi's document. If anyone, perhaps even Ravi himself, tries to deny the authenticity of the document, Francoise can say “Okay Ravi, please lend me one of your keys for a minute. Now I'm going to open this lockbox using your key.” In the presence of Ravi and some other witnesses (maybe even a judge in a court of law), Fran-coise opens the padlock and displays the contents of the lockbox. Then Francoise can continue: “Ravi, as you are the only person with access to padlocks that work with this key, no one else can possibly be responsible for the contents of the lockbox. Therefore, you and only you wrote this note and put it in the lockbox. You do owe me $100!”

  Although it sounds convoluted when you first encounter it, this method of authentication is both practical and powerful. It does have some drawbacks, however. The main problem is that it requires Ravi's cooperation: before Francoise can prove anything, she has to persuade Ravi to lend her one of his keys. But Ravi could refuse, or even worse, he could pretend to cooperate but in fact give her a different key—a key that will not open his padlock. Then, when Fran-coise fails to open the lockbox, Ravi can say, “See, that's not one of

  To make a verifiable signature using the physical padlock trick, Ravi places a copy of the document in a lockbox and locks it with one of his padlocks.

  my padlocks, so a forger could have created the document and put it in there without my knowledge.”

  To prevent this cunning approach by Ravi, we still need to resort to a trusted third party such as a bank. In contrast to the paper signature bank on page 152, our new bank will store keys. So instead of giving the bank a copy of their signatures, participants now give the bank a physical key that will open their padlocks. A physical key bank is shown in the figure on the following page.

  This bank is the final piece in the puzzle, completing the explanation of the physical padlock trick. If Francoise ever needs to prove that Ravi wrote the IOU, she just takes the lockbox to the bank with some witnesses and opens it there with Ravi's key. The fact that the padlock opens proves that only Ravi could be responsible for the contents of the box, and the box contains an exact copy of the document that Francoise is trying to authenticate.

  SIGNING WITH A MULTIPLICATIVE PADLOCK

  The key-and-padlock infrastructure that we've built up turns out to be exactly the approach required for digital signatures. Obviously, however, we can't use physical padlocks and physical keys for signatures that must be transmitted electronically. So the next step is to replace the padlocks and keys with analogous mathematical objects that can be represented digitally. Specifically, the padlocks and keys will be represented by numbers, and the act of locking or unlocking will be represented by multiplication in clock arithmetic. If you're not too familiar with clock arithmetic, now would be a great time to reread the explanation given in chapter 4, on page 52.

  A physical key bank stores keys that will open each participant's padlocks. Note that each of the keys is different.

  To create unforgeable digital signatures, computers use absolutely enormous clock sizes—typically tens or hundreds of digits in length. However, in this description, we will be using an unrealistically small clock size to ensure that the calculations are simple.

  Specifically, all the examples in this section will use a clock size of 11. Because we will be multiplying numbers together using this clock size quite a bit, I've provided a table on the next page, listing all the values for multiplying together numbers less than 11. As an example, let's compute 7 × 5. To do it manually, without using the table, we would first compute the answer using regular arithmetic: 7 × 5 = 35. Then, we take the remainder after dividing by 11. Now, 11 goes into 35 three times (giving 33) with 2 left over. So the final answer should be 2. Looking at the table, we see the entry in row 7 and column 5 is indeed 2. (You can also use column 7 and row 5—the order doesn't matter, as you can check for yourself.) Try out another couple of multiplication examples for yourself to make sure you understand.

  Before going on, we need a slight change to the problem that we're trying to solve. Previously, we've been looking for ways for Ravi to “sign” a message (actually, an IOU) to Francoise. The message was written in plain English. But from now on, it will be much more convenient to work with numbers only. Therefore, we have to agree that it would be easy for a computer to translate the message into a sequence of numbers for Ravi to sign. Later, if and when someone needs to authenticate Ravi's digital signature of this sequence of numbers, it will be a simple matter to reverse the translation and convert the numbers back into English. We encountered this same problem when talking about checksums (page 68) and the shorter-symbol trick (page 109). If you would like to understand this issue in more
detail, look back over the discussion of the shorter-symbol trick—the figure on page 111 gives one simple, explicit possibility for translating between letters and numbers.

  The multiplication table for clock size 11.

  So, instead of signing a message written in English, Ravi has to sign a sequence of numbers, perhaps something like “494138167543…83271696129149.” However, to keep things simple, we will start off by assuming the message to be signed is ridiculously short: in fact, Ravi's message will consist of a single digit, like “8” or “5.” Don't worry: we will eventually learn how to sign messages of a more sensible length. For now, however, it's better to stick with single-digit messages.

  With these preliminaries out of the way, we are ready to understand the heart of a new trick, called the “multiplicative padlock trick.” As with the physical padlock trick, Ravi is going to need a padlock and a key that unlocks the padlock. Obtaining a padlock is surprisingly easy: Ravi first selects a clock size and then chooses essentially any number less than the clock size as his numerical “padlock.” (Actually, some numbers work better than others, but these details would lead us too far astray.) To make things concrete, let's say Ravi chooses 11 as his clock size and 6 as his padlock.

  How to “lock” a numeric message using a “padlock,” creating a digital signature. The top row shows how to physically lock a message in a box using a physical padlock. The bottom row shows the analogous mathematical operation, in which the message is a number (5), the padlock is another number (6), and the process of locking corresponds to multiplication with a given clock size. The final result (8) is the digital signature for the message.

  Now, how can Ravi “lock” his message into a lockbox with this padlock? As strange as it might sound, Ravi is going to use multiplication to do this: the “locked” version of his message will be the padlock multiplied by the message (using clock size 11, of course). Remember, we are dealing with the simple case of a single-digit message right now. So suppose Ravi's message is “5.” Then his “locked” message will be 6 × 5, which is 8—with clock size 11, as usual. (Doublecheck this using the multiplication table on the previous page.) This process is summarized in the figure above. The final result, “8,” is Ravi's digital signature for the original message.

  Of course, this type of mathematical “padlocking” would be pointless if we couldn't later unlock the message using a mathematical “key” of some sort. Fortunately, it turns out there is an easy way to unlock messages. The trick is to use multiplication again (applying the clock size, as usual), but this time we'll multiply by a different number—a number selected especially so that it unlocks the previously chosen padlock number.

  Let's stick with the same concrete example for the moment, so Ravi is using a clock size of 11, with 6 as his padlock number. turns out that the corresponding key is 2. How do we know that? We will come back to this important question later. For the moment, let's stick with the easier task of verifying that the key works once someone else has told us its numeric value. As mentioned earlier, we unlock a padlocked message by multiplying by the key. We have already seen, in the figure on the previous page, that when Ravi locks the message 5 with padlock 6, he gets the locked message (or digital signature) 8. To unlock, we take this 8 and multiply by the key 2, which gives 5 after applying the clock size. Like magic, we have ended up back with the original message, 5! The whole process is shown in the figure above, where you can also see a couple of other examples: the message “3” becomes “7” when padlocked, and reverts to “3” when the key is applied. Similarly, “2” becomes “1” when locked, but the key converts it back to “2.”

  How to “lock” and subsequently “unlock” a message using a numeric padlock and a corresponding numeric key. The top row shows the physical version of locking and unlocking. The next three rows show examples of numerically locking and unlocking messages using multiplication. Note that the locking process produces a digital signature, whereas the unlocking process produces a message. If the unlocked message matches the original message, the digital signature is verified and the original message is authentic.

  This figure also explains how to verify digital signatures. You just take the signature and unlock it using the signer's multiplicative key. If the resulting unlocked message matches the original message, the signature is authentic. Otherwise, it must have been forged. This verification process is shown in more detail in the table on the next page. In this table, we stick with a clock size of 11, but to show that there is nothing special about the numeric padlock and key we have been using up to this point, different values are used for these. Specifically, the padlock value is 9, and the corresponding key value is 5. In the table's first example, the message is “4” with signature “3.” The signature unlocks to “4,” which matches the original message so the signature is genuine. The next row of the table gives a similar example for the message “8” with signature “6.” But the final row shows what happens if the signature is forged. Here, the message is again “8” but the signature is “7.” This signature unlocks to “2,” which does not match the original message. Hence, the signature is forged.

  How to detect a forged digital signature. These examples use a padlock value of 9 and a key value of 5. The first two signatures are genuine, but the third is forged.

  If you think back to the physical key and padlock scenario, you will remember that the padlocks have biometric sensors preventing use by others—otherwise a forger could use one of Ravi's padlocks to lock any desired message into a box, thus forging a signature of that message. The same reasoning applies to numeric padlocks. Ravi must keep his padlock number secret. Each time he signs a message, he can reveal both the message and the signature, but not the padlock number used to produce the signature.

  What about Ravi's clock size and his numeric key? Must these also be kept secret? The answer is no. Ravi can announce his clock size and key value to the general public, perhaps by publishing them on a website, without compromising the scheme for verifying signatures. If Ravi does publish his clock size and key value, anyone can obtain these numbers and thus verify his signatures. This approach appears, at first glance, to be very convenient indeed—but there are some important subtleties to be addressed.

  A numeric key bank. The role of the bank is not to keep the numeric keys and clock sizes secret. Instead, the bank is a trusted authority for obtaining the true key and clock size associated with any individual. The bank freely reveals this information to anyone who asks for it.

  For example, does the approach eliminate the need for a trusted bank, which was required both for the paper signature technique and for the physical padlock-and-key technique? The answer is no: a trusted third party such as a bank is still required. Without it, Ravi could distribute a false key value that would make his signatures appear invalid. And, even worse, Ravi's enemies could create a new numeric padlock and corresponding numeric key, make a website announcing that this key is Ravi's, and then digitally sign any message they want using their newly minted numeric padlock. Anyone who believes that the new key belongs to Ravi will believe that the enemies' messages were signed by Ravi. Thus, the role of the bank is not to keep Ravi's key and clock size secret. Instead, the bank is a trusted authority for the value of Ravi's numeric key and clock size. The figure above demonstrates this.

  A useful way to summarize this discussion would be: numeric padlocks are private, whereas numeric keys and clock sizes are public. It is, admittedly, a little counterintuitive for a key to be “public,” because in our everyday lives we are used to guarding our physical keys very carefully. To clarify this unusual use of keys, think back to the physical padlock trick described earlier. There, the bank kept a copy of Ravi's key and would happily lend it to anyone wishing to verify Ravi's signature. So the physical key was, in some sense, “public.” The same reasoning applies to multiplicative keys.

  This is a good time to address an important practical issue: what if we want to sign a message
longer than one digit? There are several different answers to this question. An initial solution is to use a much larger clock size: if we use a 100-digit clock size, for example, then exactly the same methods allow us to sign 100-digit messages with 100-digit signatures. For a message longer than this, we could just divide it into 100-digit chunks and sign each chunk separately. But computer scientists have a better way of doing this. It turns out that long messages can—for the purposes of signing—be reduced down into a single chunk (of, say, 100 digits), by applying a transformation called a cryptographic hash function. We've encountered cryptographic hash functions before, in chapter 5, where they were used as a checksum to ensure the content of a large message (such as a software package) was correct (see page 73). The idea here is very similar: a long message gets reduced to a much smaller chunk before signing takes place. This means that extremely large “messages,” such as software packages, can be signed efficiently. To keep things simple, we'll ignore the issue of long messages for the rest of the chapter.

  Another important question is: where do these numeric padlocks and keys come from originally? It was mentioned earlier that participants can choose essentially any value for their padlock. The details hiding behind the word “essentially” here require an undergraduate course in number theory, unfortunately. But assuming you haven't had the chance to study number theory, allow me to provide the following teaser: if the clock size is a prime number, then any positive value less than the clock size will work as a padlock. Otherwise, the situation is more complicated. A prime number is a number that has no factors, other than 1 and itself. So you can see that the clock size 11 used so far in this chapter is indeed prime.

  Thus, choosing the padlock is the easy part—especially if the clock size is prime. But once the padlock is chosen, we still need to come up with the corresponding numeric key that unlocks the chosen padlock. This turns out to be an interesting—and very old—mathematical problem. Actually, the solution has been known for centuries, and the central idea is even older: it is a technique known as Euclid's algorithm, documented over 2000 years ago by the Greek mathematician Euclid. However, we don't need to pursue the details of key generation here. It is enough to know that, given a padlock value, your computer can come up with the corresponding key value using a well-known mathematical technique called Euclid's algorithm.