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

by John MacCormick

  If you're still dissatisfied with this explanation, maybe you will be happier once I reveal a dramatic turn that we will be taking soon: the whole “multiplicative” approach to padlocks and keys has a fundamental flaw and must be abandoned. In the next section, we'll be using a different numerical approach to padlocks and keys—an approach that is actually used in practice. So why did I bother to explain the flawed multiplicative system? The main reason is that everyone is familiar with multiplication, which means that the system could be explained without requiring too many new ideas all at once. Another reason is that there are some fascinating connections between the flawed multiplicative approach and the correct approach we will consider next.

  But before moving on, let's try to understand the flaw in the multiplicative approach. Recall that padlock values are private (i.e., secret), whereas key values are public. As just discussed, a participant in a signature scheme freely chooses a clock size (which is made public) and a padlock value (which remains private), and then generates the corresponding key value using a computer (via Euclid's algorithm, in the particular case of the multiplicative keys we have been using so far). The key is stored in a trustworthy bank, and the bank reveals the key's value to anyone who asks. The problem with a multiplicative key is that the same trick—essentially Euclid's algorithm—that is used to generate a key from a padlock works perfectly well in reverse: exactly the same technique allows a computer to generate the padlock value corresponding to a given key value! We can immediately see why this trashes the whole digital signature scheme. Because the key values are public, the supposedly secret padlock values can be computed by anyone. And once you know someone's padlock value, you can forge that person's digital signature.

  SIGNING WITH AN EXPONENT PADLOCK

  In this section, we will upgrade our flawed multiplicative system to a digital signature scheme, known as RSA, that is actually used in practice. But the new system will use a less-familiar operation called exponentiation in place of the multiplication operation. In fact, we went through the same sequence of explanatory steps when building up our understanding of public key cryptography in chapter 4: we first worked through a simple but flawed system that used multiplication, and then looked at the real version using exponentiation.

  So, if you're not too familiar with power notation, like 59 and 34, this would be a great time to go back to page 52 for a refresher. But as a one-line reminder, 34 (“3 to the power of 4”) means 3×3x3×3. In addition, we need a few more technical terms. In an expression like 34, the 4 is called the exponent or power and the 3 is called the base. The process of applying an exponent to a base is called “raising to a power,” or, more formally, exponentiation. As in chapter 4, we will be combining exponentiation with clock arithmetic. All the examples in this section of the chapter will use clock size 22. The only exponents we will need are 3 and 7, so I've provided a table above showing the value of n3 and n7, for every value of n up to 20 (when the clock size is 22).

  Values for exponentiating by 3 and 7 when the clock size is 22.

  Let's check a couple of the entries in this table now, to ensure they make sense. Take a look at the row corresponding to n = 4. If we weren't using clock arithmetic, then we could work out that 43 = 4 × 4 × 4 = 64. But applying the clock size of 22, we see that 22 goes into 64 twice (giving 44), with 20 left over. That explains the entry of 20 in the column for n3. Similarly, without clock arithmetic you can work out that 47 = 16, 384 (okay, you can trust me on that one), which happens to be 16 more than the nearest multiple of 22 (that's 22 × 744 = 16, 368, just in case you are interested). So that explains the 16 in the column for n7.

  Now we are finally ready to see a genuine digital signature in action. The system works exactly the same as the multiplicative method from the previous section, with one exception: instead of locking and unlocking messages using multiplication, we use exponentiation. As before, Ravi first chooses a clock size that will be made public. Here, Ravi uses clock size 22. Then he selects a secret padlock value, which can be anything less than the clock size (subject to some fine print that we'll discuss briefly later). In our example, Ravi chooses 3 as his padlock value. Then, he uses a computer to work

  Locking and unlocking messages using exponentiation.

  out the corresponding key value for the given padlock and clock size. We'll learn a few more details about this later on. But the only important fact is that a computer can easily compute the key from the padlock and clock size, using a well-known mathematical technique. In this case, it turns out that the key value 7 corresponds to the previously selected padlock value 3.

  The figure above shows some concrete examples of how Ravi can sign messages, and how others can unlock the signatures to check them. If the message is “4,” the signature is “20”: we get this by exponentiating the message with the padlock as exponent. So we need to compute 43, which gives 20 once the clock size is taken into account. (Don't forget, you can easily check any of these computations using the table on the previous page.) Now, when Francoise wants to verify Ravi's digital signature “20,” she first goes to the bank to get authoritative values for Ravi's clock size and key. (The bank looks the same as before, except with different numbers—see the figure on page 161.) Then Francoise takes the signature, exponentiates by the key value, and applies the clock size: this gives 207 = 4, again using the table on the previous page. If the result matches the original message (and in this case it does), the signature is authentic. The figure shows similar calculations for the messages “8” and “7.”

  The table on the following page shows the process again, this time emphasizing the verification of the signature. The first two examples in this figure are identical to the previous figure (messages “4” and “8,” respectively), and they have genuine signatures. The third example has message “8” and signature “9.” Unlocking, by applying the key and clock size, gives 97 = 15, which doesn't match the original message. Therefore, this signature is forged.

  How to detect a forged digital signature with exponentiation. These examples use a padlock value of 3, a key value of 7, and a clock size of 22. The first two signatures are genuine, but the third is forged.

  As mentioned earlier, this scheme of exponent padlocks and exponent keys is known as the RSA digital signature scheme, named for its inventors (Ronald Rivest, Adi Shamir, and Leonard Adleman), who first published the system in the 1970s. This may sound eerily familiar, because we already encountered the acronym RSA in chapter 4, on public key cryptography. In fact, RSA is both a public key cryptography scheme and a digital signature scheme—which is no coincidence, as there is a deep theoretical relationship between these two types of algorithms. In this chapter, we have explored only the digital signature aspect of RSA, but you may have noticed some striking similarities to the ideas in chapter 4.

  The details of how to choose clock sizes, padlocks, and keys in the RSA system are truly fascinating, but they aren't needed to understand the overall approach. The most important point is that in this system, a participant can easily compute an appropriate key value once the padlock value has been chosen. But it is impossible for anyone else to reverse the process: if you know the key and clock size being used by someone else, you can't work out the corresponding padlock value. This fixes the flaw in the multiplicative system explained earlier.

  At least, computer scientists think it does, but nobody knows for sure. The issue of whether RSA is truly secure is among the most fascinating—and vexing—questions in the whole of computer science. For one thing, this question depends on both an ancient unsolved mathematical problem and a much more recent hot topic at the intersection of physics and computer science research. The mathematical problem is known as integer factorization;, the hot research topic is quantum computing. We are going to explore both of these aspects of RSA security in turn, but before we do that, we need a slightly better understanding of what it really means for a digital signature scheme like RSA to be “secure.”

>   The Security of RSA

  The security of any digital signature scheme comes down to the question, “Can my enemy forge my signature?” For RSA, this in turn boils down to “Can my enemy compute my private padlock value, given my public clock size and key value?” You might be distressed to learn that the simple answer to this question is “Yes!” In fact, you already knew that: it's always possible to work out someone's padlock value by trial and error. After all, we are given a message, a clock size, and a digital signature. We know the padlock value is smaller than the clock size, so we can simply try every possible padlock value in turn, until we find one that produces the correct signature. It's just a matter of exponentiating the message by each trial padlock value. The catch is that, in practice, RSA schemes use absolutely enormous clock sizes—say, thousands of digits long. So even on the fastest existing supercomputer, it would take trillions of years to try all the possible padlock values. Therefore, we are not interested in whether an enemy could compute the padlock value by any means whatsoever. Instead, we want to know if the enemy can do so efficiently enough to be a practical threat. If the enemy's best method of attack is trial and error—also known as brute force by computer scientists—we can always choose our clock size large enough to make the attack impractical. If, on the other hand, the enemy has a technique that works significantly faster than brute force, we might be in trouble.

  For example, going back to the multiplicative padlock and key scheme, we learned that a signer can choose a padlock value and then compute the key value from this using Euclid's algorithm. But the flaw was that adversaries did not need to resort to brute force to reverse this process: it turned out that Euclid's algorithm could also be used to compute the padlock given the key, and this algorithm is vastly more efficient than brute force. That's why the multiplicative approach is considered insecure.

  The Connection between RSA and Factoring

  I promised earlier to reveal a connection between the security of RSA and an age-old mathematical problem called integer factorization. To understand this connection, we need a few more details about how an RSA clock size is chosen.

  First, recall the definition of a prime number: it is a number that has no factors other than 1 and itself. For example, 31 is prime because 1 × 31 is the only way to produce 31 as the product of two numbers. But 33 is not prime, since 33 = 3 × 11.

  Now we are ready to walk through how a signer such as our old friend Ravi can generate a clock size for RSA. The first thing Ravi does is choose two very large prime numbers. Typically these numbers will be hundreds of digits long, but as usual we will work with a tiny example instead. So let's say Ravi chooses 2 and 11 as his prime numbers. Then he multiplies them together; this produces the clock size. So in our example, the clock size is 2 × 11 = 22. As we know, the clock size will be made public along with Ravi's chosen key value. But—and this is the crucial point—the two prime factors of the clock size remain secret, known only to Ravi. The math behind RSA gives Ravi a method of using these two prime factors to compute a padlock value from a key value and vice versa.

  The details of this method are described in the panel on the next page, but they are irrelevant for our main purpose. All we need to realize is that Ravi's enemies cannot compute his secret padlock value using the publicly available information (the clock size and key value). But if his enemies also knew the two prime factors of the clock size, they could easily compute the secret padlock value. In other words, Ravi's enemies can forge his signature if they can factorize the clock size. (Of course, there maybe other ways of cracking RSA. Efficient factorization of the clock size is just one possible method of attack.)

  In our small example, factoring the clock size (and thus cracking the digital signature scheme) is absurdly easy: everyone knows that 22 = 2 × 11. But when the clock size is hundreds or thousands of digits long, finding the factors turns out to be an extremely difficult problem. In fact, although this so-called “integer factorization” problem has been studied for centuries, no one has found a general method of solving it that works efficiently enough to compromise a typical RSA clock size.

  The history of mathematics is peppered with unsolved problems that fascinated mathematicians by their aesthetic qualities alone, inspiring deep investigation despite the lack of any practical application. Rather astonishingly, many of these intriguing-yet-apparently-useless problems later turned out to have great practical significance—and in some cases, the significance was discovered only after the problem had been studied for centuries.

  Ravi chooses two prime numbers (2 and 11, in our simple example) and multiplies them together to produce his clock size (22). Let's refer to this as the “primary” clock size for reasons that will soon become apparent. Next, Ravi subtracts one from each of the original two prime numbers, and multiplies those numbers together. This produces Ravi's “secondary” clock size. In our example, Ravi is left with 1 and 10 after subtracting one from each of the original primes, so the secondary clock size is 1 × 10 = 10.

  At this point, we encounter an extremely gratifying connection to the flawed multiplicative padlock-and-key system described earlier: Ravi chooses a padlock and key according to the multiplicative system, but using the secondary clock size instead of the primary. Suppose Ravi chooses 3 as his padlock number. It turns out, when using the secondary clock size of 10, that the corresponding multiplicative key is 7. We can quickly verify that this works: the message “8” padlocks to 8 × 3 = 24, or “4” in clock size 10. Unlocking “4” with the key gives 4 × 7 = 28, which is “8” after applying the clock size—the same as the original message.

  Ravi's work is now done: he takes the multiplicative padlock and key just chosen, and uses them directly as his exponent padlock and key in the RSA system. Of course, they will be used as exponents with the primary clock size, 22.

  The gory details of generating RSA clock, padlock, and key values.

  Integer factorization is just such a problem. The earliest serious investigations seem to have been in the 17th century, by the mathematicians Fermat and Mersenne. Euler and Gauss—two of the biggest names in the mathematical canon—made contributions in the centuries immediately following, and many others have built on their work. But it was not until the discovery of public key cryptography in the 1970s that the difficulty of factoring large numbers became the linchpin of a practical application. As you now know, anyone who discovers an efficient algorithm for factoring large numbers will be able to forge digital signatures at will!

  Before this begins to sound too alarming, I should clarify that numerous other digital signature schemes have been invented since the 1970s. Although each scheme depends on the difficulty of some fundamental mathematical challenge, the different schemes rely on different mathematical challenges. Therefore, the discovery of an efficient factorization algorithm will break only the RSA-like schemes.

  On the other hand, computer scientists continue to be baffled by an intriguing gotcha that applies to all of these systems: none of the schemes has been proved secure. Each of them depends on some apparently difficult, much-studied mathematical challenge. But in each case, theoreticians have been unable to prove that no efficient solution exists. Thus, although experts consider it extremely unlikely, it is possible in principle that any one of these cryptography or digital signature schemes could be cracked wide open at any time.

  The Connection between RSA and Quantum Computers

  I've made good on my promise to reveal a connection between RSA and an old mathematical problem, but I have yet to explain the connection to the hot research topic of quantum computing. To pursue this, we must first accept the following fundamental fact: in quantum mechanics, the motion of objects is governed by probabilities—in contrast to the deterministic laws of classical physics. So if you build a computer out of parts that are susceptible to quantum-mechanical effects, the values it computes are determined by probabilities, instead of the absolutely certain sequence of 0s and 1s that a classical co
mputer produces. Another way of viewing this is that a quantum computer stores many different values at the same time: the different values have different probabilities, but until you force the computer to output a final answer, the values all exist simultaneously. This leads to the possibility that a quantum computer can compute many different possible answers at the same time. So for certain special types of problems, you can use a “brute force” approach that tries all of the possible solutions simultaneously!

  This does only work for certain types of problems, but it just so happens that integer factorization is one of the tasks that can be performed with vastly greater efficiency on quantum computers than on classical ones. Therefore, if you could build a quantum computer that could handle numbers with thousands of digits, you could forge RSA signatures as explained earlier: factorize the public clock size, use the factors to determine the secondary clock size, and use this to determine the private padlock value from the public key value.

  As I write these words in 2011, the theory of quantum computing is far ahead of its practice. Researchers have managed to build real quantum computers, but the biggest factorization performed by a quantum computer so far is 15 = 3 × 5—a far cry indeed from factoring a thousand-digit RSA clock size! And there are formidable practical problems to be solved before larger quantum computers can be created. So no one knows when, or if, quantum computers will become large enough to break the RSA system once and for all.