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

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.