In the early 1970s there was only one type of encryption: symmetric encryption. By the late 1970s there were two. It is hard to express how truly revolutionary the idea of asymmetric encryption was. Asymmetric encryption directly tackles the symmetric-key-distribution problem by providing a means for two people who have not previously agreed on a secret symmetric key to do so in plain sight of an attacker. Asymmetric encryption seems like magic. And it is. Even more wizardly, it has indirectly facilitated many other amazing things that cryptography can now help us do in cyberspace, such as digitally signing documents, making payments with digital currency, and voting.
A Huge Bunch of Keys
In order to appreciate the power of asymmetric encryption, recall the previous example, in which you unexpectedly needed a key in order to encrypt communications with a website you had previously never visited. What would it take to solve this problem using symmetric encryption alone?
Earlier I observed that you could solve this problem by having a key delivered by some physical means. Either you, or the website, could generate a cryptographic key and then arrange for it to be delivered manually to the other party, perhaps using an express delivery service. All of this would cost you money and, more importantly, time. In the case of buying something online, this idea is preposterous.
An alternative is to share a key with the website before you even connect. Since the key you share with one website must be different from the key you share with another, key sharing would require you to have a key for every possible website you might ever want to visit.
The problem with this idea is the elephantine scale of it. There are over 1.5 billion websites in cyberspace.1 If you have to store a unique symmetric key for each of these websites, then you will need to store over 1.5 billion secret keys. Given that half the world’s population has access to the internet, if an online merchant wants the capability of allowing each user to buy goods from its website, the merchant needs to store 3.5 billion keys.
Intriguingly, it’s not storage capacity that’s the problem. If each of these 3.5 billion keys were an AES key of 128 bits, then the merchant would need to safeguard 45 gigabytes’ worth of keys (a memory stick capable of this amount of storage costs less than a meal for two in a cheap restaurant). What makes this idea such a nightmare is the logistics of managing all these keys. How would we distribute them? How would we keep track of which keys are for which websites? How would we cope with all those new websites created every minute of every day of every year?
A third option would be to have a global key center that everyone on the internet trusted. You could each share a symmetric key with this global key center. This key would be sent to you in advance, perhaps on a smartcard, similarly to the way your bank has conveyed a key to you. When you wanted a key to securely communicate with a website, you could ask the global key center to generate a new key for this purpose. It could send this key to you, encrypted using the key you share with the center. A similar process could be used to send this key to the website.
If only.
First there is a political problem. Who, on the internet, is so trusted by all users that they could provide the services of the global key center? The Americans don’t trust the Russians, who don’t trust the British, who don’t trust the French, who don’t trust the Ruritanians, and so on. Perhaps the burden of this role could be passed to the United Nations? It might work, but an even bigger issue is the centralized nature of this architecture. Every time anyone wanted to talk to anyone else, they would first need to interact with the global key center. This requirement would slow all communications down. There would also be catastrophic implications if the global key center became temporarily unavailable, or if it were compromised.
It’s worth noting, however, that the key-center solution works perfectly well for smaller organizations. For example, a private company’s organizational relationship with its employees makes sharing a key with each employee possible. Further, many companies have their own centralized networks, which make requesting keys from a central key center a workable solution. In this situation, the users are not really “strangers,” since they all share a common relationship with the key center through their contract of employment.2 For large, less structured populations (such as the global internet population), this doesn’t work.
The bottom line is this: in general, it’s not feasible to use only symmetric encryption when sharing secrets with strangers.
Padlock Madness
To seek inspiration about how we might share a secret with a stranger, consider a somewhat artificial scenario from the physical world. A silly story maybe, but hopefully illustrative.
Suppose you are given the name and address of a stranger on the other side of town to whom you must send a secret written letter. This premise sounds unlikely, so let’s make the scenario plausible by conceptualizing the stranger as a lawyer you’ve spoken to on the phone but are unable to visit, and the secret letter as your last will and testament.
One obvious way of proceeding is to seal the letter in an envelope and put it in the mail. However wonderful the postal system is, one problem with this approach is that an inquisitive employee could steam open the envelope and sneak a peek. A more robust solution would be to place the letter in a briefcase, secured by lock and key, and send the briefcase by courier. But how would the lawyer get the key to unlock the briefcase?
Recall that there are two types of physical locks. While one type requires the same key to both lock and unlock, padlocks allow anyone to lock, but only the key holder to unlock.
Here’s a version of the previously described scenario in which padlocks are used to secure the secret letter that you send to your lawyer.3 First, you place the letter in a briefcase, and then you lock the briefcase using a padlock for which only you have the key. Now you have a courier deliver the locked briefcase to the lawyer. Although trusted to deliver the briefcase, the courier might try to inspect the letter; hence the need to lock it away (cryptographers would describe the courier as “honest but curious”).
Upon receiving the briefcase, the lawyer is unable to open it because she doesn’t have the key to your padlock. So, she adds a second padlock to the briefcase, this time using a padlock for which only she has the key. She then returns the briefcase to the courier and asks him to take it back to you. The briefcase is now more impregnable than ever, since it is secured by two padlocks, and nobody has the key to both.
On receipt, you unlock your padlock, leaving only the lawyer’s lock on the briefcase. You now return it to the courier and ask him to deliver it, once again, to the lawyer. Exasperated, but undoubtedly happy with the triple fare, the courier escorts the briefcase back across town. Finally, the lawyer removes her padlock and is able to open the briefcase to retrieve the letter.
A crazy process maybe, but it works. What’s really going on? The ultimate purpose of the to-and-fro is to secure the briefcase with a padlock that the lawyer can open. The proposed solution, fun though it is, seems a rather overengineered means of securely delivering a confidential letter. However, a worthy refinement saves a bit of time, some money, and quite a few carbon emissions (unless the courier is on a bicycle). You could first call the lawyer on the phone and request a padlock. She could courier the padlock to you. On receipt, you could secure the briefcase using her padlock, then courier the locked briefcase back to her.
This padlock-by-courier idea is still a bit clunky, but it’s an improvement on the triple trip. More significantly, it’s precisely the model on which asymmetric encryption is based.
Padlocks in Cyberspace
Alas, a physical padlock requires physical delivery. Suppose, however, that a physical padlock could defeat the conventional laws of physics and teleport itself instantly to wherever it was required! We would then have an efficient solution to the problem of how to share a secret with a stranger in the physical world.
Cyberspace, fortunately, is a place where teleportation is almost possible. Conceptually, a digital “padlock” could be dispatched with lightning speed, by email perhaps, and then used to snap shut the equivalent of a digital briefcase. This idea, if realizable, would allow us to share secrets with strangers in cyberspace. When we connect to a website we have never previously visited, all we need is a digital padlock, which is what asymmetric encryption provides.
A padlock is a lock that, in theory, everyone can close but only the key holder can open. A digital padlock thus needs to be a form of encryption that allows anyone to encrypt but only the designated recipient to decrypt. Since everyone can encrypt and encryption involves a key, the key used for digital padlock encryption will need to be something everyone knows—in other words, a key that is not secret. Such a key is known as a public key because it can be made publicly available. Consequently, asymmetric encryption is often referred to as public-key encryption.
In contrast, the designated recipient should be the only person capable of unlocking a digital padlock. Just as for symmetric encryption, the key used to decrypt will need to be kept secret by the recipient. This key is usually referred to as a private key, because it is private to the key holder and not shared with anyone else, just as for a physical padlock key. In the case of asymmetric encryption, the keys used to encrypt and decrypt are thus different. Of course, even though the encryption key and decryption key are different, they must be related to one another in some way.
Let’s take stock of what asymmetric encryption requires. Anyone can encrypt using the public key, but only the holder of the private key can decrypt. Encryption, therefore, involves a process anyone can perform but nobody, other than the private key holder, can reverse. How is such a process possible?
When you think about it, life is full of examples of things that are easy to do but hard to reverse. A good example is cooking your dinner from fresh ingredients. While it’s easy to cook a tasty dinner from scratch, extracting the original ingredients back from the dinner on your plate is normally impossible, since the chemical processes involved in cooking transform and bind them in an irreversible way.
Cooking is not a perfect analogy for asymmetric encryption, because it’s impossible to recover the original ingredients. In the case of asymmetric encryption, we want it to be impossible for almost everyone, but we do want someone to be able to recover these ingredients—namely, the holder of the private key. Decryption is thus possible, albeit only in a special circumstance. Since decryption cannot be impossible, we’ll have to settle for the next best thing. For anyone lacking knowledge of the private key, decryption should be extremely hard to perform.4
An asymmetric encryption scheme needs to be built around something that computers find easy to do but that is extremely hard to reverse. Converting us into internet slaves? Turning us into social media junkies? Making us busier? Losing us sleep? These might all fit the brief, but we need something more precise. We need to find a computational task that computers find easy to do but is hard to reverse.
The Blinking Cursor
To get a feel for how an asymmetric encryption scheme could be built, it’s worth becoming aware of what hard means for a computer. Suppose money is no object. Imagine you have a challenging task you want a computer to perform. You buy a computer, program it to perform the task, and then press the Return key. The computer grinds away for a few hours, which soon becomes days. As weeks and months go by, the computer becomes increasingly hot. Ultimately, smoke emerges from the back. What do you do next? Go and buy a bigger, better computer?
Maybe! But maybe not. Computers are extremely powerful machines and can do amazing things, but some computing tasks quickly get out of control on even the best of computers. If you ask a computer to perform such a task, you might not always see smoke, but you certainly won’t see an answer.
To see how this happens, imagine a task that is doable for a human being but takes a bit of effort. Consider the weekly cleaning of a house. How long does this take you? Half a day, say? (I live with someone who would challenge this estimate as being rather optimistic.) Yes, it’s work, and it’s tiring, but it’s a task that can be completed within an acceptable amount of time. Suppose you discover that you are rather good at cleaning houses, and you decide to make a living doing that. You first need to market your business proposition.
One obvious marketing strategy is to contact a few neighbors. The woman next door asks you to clean for her, so now you have half a day of paid work. The family down the road needs a cleaner, and so do both of that family’s neighbors. You ring a few more doorbells, and eventually you find six more houses to clean. You now have a full-time job. You could stop now, but you detect there’s an even bigger market for domestic cleaning in the local area. You take on an employee, and in a short while you have a small business with several staff. Your fledgling venture into the world of commerce has been a great success. Importantly, your business is steadily growing in a very manageable way.
Now let’s consider a slightly different marketing strategy. In this scenario you decide to advertise your services among your friends on a social media site, such as Facebook. Suppose you have 100 friends, and 10 of these friends respond positively. Your weekly calendar is immediately full. Now, let’s imagine that, as part of your advertising pitch, you ask your friends to forward the cleaning offer to all their Facebook friends. Assuming they each have 100 friends different from yours, and you experience a similar acceptance rate (we’re making all sorts of assumptions in this scenario, so let’s not get hung up on the details), then your offer of cleaning will have reached an incredible 10,000 people and you’ll be inundated by 1,000 requests for house cleaning. Ouch! If you want to pursue this business opportunity, you urgently need to hire 100 cleaners.
Almost overnight, you’ve gone from being self-employed to becoming a significant local enterprise. If, heaven forbid, each of these 10,000 friends of friends then forwards your cleaning offer to their friends, you’ll be marketing to 1 million new customers and can expect another 100,000 cleaning requests. In the blink of an eye, the whole project is out of control. In just two additional iterations of this viral marketing process, you will have 1 billion customers and be cleaning everything from igloos in the Arctic to thatched huts in the Kalahari.
The serious point behind this example is that some tasks scale well as numbers increase, while others spin madly out of control. This behavior applies just as much to computing tasks as it does to house cleaning. Some tasks on a computer are very doable. For example, computers are excellent at adding two numbers together. You can keep feeding your computer bigger and bigger numbers to add together, and it will perform the task as dutifully as a dog fetches a stick. As the numbers get larger, you will eventually reach the limit of your computer’s processing capability, at which point it will decline to give an answer. If you insist on adding these giant numbers together, all you need to do is buy a bigger computer. However, some other computing tasks don’t work like this at all. Just as in our viral marketing exercise, some tasks rapidly become infeasible to manage on any computer. Even when you ask the most powerful computer in the entire world to conduct them, its cursor merely blinks back—not just for a few hours, but for the rest of your life.5
A combination of these types of computing tasks is precisely what is necessary in order to accomplish asymmetric encryption. The encryption algorithm needs to be a manageable computation, so that any computer can perform it. On the other hand, without knowledge of the private key, any computer that tries to run the decryption algorithm should end up displaying a helpless, blinking cursor—as your brain would do, if tasked with finding 100 million cleaners by tomorrow afternoon.
The Prime Factor
Not many people truly understand the role of cryptography in protecting computer systems (you are, of course, well on your way to becoming a notable exception), but one thing that does seem widely recognized is that the security of computers has something to do with prime numbers, or (more simply) primes.6 While primes are used throughout cryptography, their role in asymmetric encryption algorithms is what has garnered them the most attention.
Primes are whole numbers (greater than 1) with a very simple arithmetic property: the only two numbers dividing a prime without leaving a remainder are 1 and the prime itself. The smallest prime is 2 (it is the only even prime, since 2 divides all other even numbers without remainder). Also prime are 3, 5, and 7. But 9 is not a prime, since 3 divides into 9. The next two odd numbers — 11 and 13 — are prime, but 15, also divisible by 3, is not. This pattern continues forever because there are infinitely many primes.
Primes are, in a sense, the basic building blocks of all whole numbers, since every whole number can be formed by multiplying some primes together. For example, 4 = 2 × 2, 15 = 3 × 5, 36 = 2 × 2 × 3 × 3. In fact, for every whole number there is only one collection of primes that can be multiplied together to form the number. For example, 100 = 2 × 2 × 5 × 5. No group of primes besides 2,2,5,5 can be multiplied together to make 100. The primes 2,2,5,5—which are known as 100’s prime factors—thus form the unique “DNA” of the number 100.
This singular connection between a number and its prime factors forms the basis for the most famous asymmetric encryption algorithm: RSA, named after its inventors, Rivest, Shamir, and Adleman.7 The relationship between a number and its prime factors creates exactly the types of computational tasks that were earlier identified as necessary in order to accomplish asymmetric encryption: going in one direction, it’s manageable; going in the other, it’s a circuit-board burner.
The doable direction is multiplication. A computer can multiply any two primes. Hopefully, your schooling has left you also capable of multiplying primes. Try multiplying the following primes, in order, and preferably in your head (reach for pen and paper only if required!): 3 × 11, 5 × 13, 7 × 23, 11 × 31, 23 × 23, 31 × 41.
How was this experience for you? You probably took a little bit longer on each multiplication as you progressed, but each calculation surely took you less time than it takes to make a cup of tea.
With the help of pen and paper, you could surely multiply even more impressive primes. Go on—what’s 23,189 multiplied by 50,021? (Really work this out. You’ll need the answer in a moment.) Using techniques very similar to those you learned in school (if you failed to complete the previous task, then you’ve simply forgotten, as opposed to never having known), computers can multiply truly enormous primes together. In this sense, multiplication is an easy computing task. As the numbers get larger, the time taken to complete the computation increases, but it’s a feasible task and an answer can be obtained.
The reverse of prime multiplication is to be given a number and asked to compute its prime factors. Let’s assume a starting number that consists of two primes multiplied together. The question is: Which two primes? This doesn’t feel like it should be a mind-boggling, brain-blowing challenge, does it? Surprisingly, this computational task rapidly veers out of control on a computer. As the numbers get larger, a point is reached, counterintuitively quickly, when even the world’s most powerful supercomputers, such as China’s Sunway TaihuLight with its almost 100 petaflops* of processing power,8 display the likes of a blinking cursor or spinning wheel of death.
To get a feel for how factoring becomes so difficult so quickly, use the wondrous computer in your own brain to try to determine the two prime factors for each of the following numbers: 21, 35, 51, 91, 187, 247, 361, 391. Note how much longer you take (and how your brain increasingly hurts) as you progress through these simple examples.
Did you give up before the end? These are very small numbers in the general scheme of things! What about 83,803? Or, more significantly, 1,159,936,969? If you still have the piece of paper where you recently demonstrated your multiplication skills, you will have discovered that 1,159,936,969 = 23,189 × 50,021. Would you have ever, otherwise, been able to work it out? Given that the most obvious factorization tactic is to try dividing by the smallest prime (2), then by 3, then by 5, and so on, and given that there are 2,586 primes to try before you reach 23,189, I doubt it.9
Yet, on the cryptographic scale of things, 23,189 and 50,021 are very small primes. The primes recommended these days for use in RSA are more than 450 digits long.10 Despite the magnitude of these primes, you can easily use a laptop computer to multiply them together. However, if you give the answer to the Sunway TaihuLight and ask it to find the two prime factors—blink, blink, blink, . . .
A Digital Padlock Based on Factoring
For its security, the RSA asymmetric encryption algorithm relies on the difficulty of determining prime factors. Without going into the specific details, the basic idea is as follows.
If you want to create a digital padlock, you first generate two enormous primes, each on the order of 450 digits long. These primes must be kept secret and essentially form your private key (in fact, your private key is something that can be worked out from these primes, not the primes themselves, but this is a detail). Only you can know what these two primes are.
You now multiply the two primes together. The approximately 900-digit result of this multiplication, alongside another value, is your public key. You can tell all your friends your public key; you can display it on your website; you can print it on your business card. It doesn’t matter who sees your public key. The difficulty of determining the prime factors of a number means that, although the two primes are hardwired into the public key, nobody owns a computer powerful enough to work out what they are.
There’s a little bit of undergraduate-level mathematics behind the full details of how RSA encryption really works,11 but we can skip that. What’s important is that anyone who wants to send you an encrypted message must first obtain your public key (which is relatively straightforward, since it’s not a secret). To encrypt a message to you, they begin by encoding the plaintext as a number (there are standard ways of doing this). The encryption process essentially consists of a series of multiplications involving the plaintext and your public key.
Since computers can multiply numbers, encryption is doable. After you receive the ciphertext, you can apply the decryption process. Decryption is also doable, since it, too, involves a series of multiplications, this time involving the ciphertext and your private key. Anyone else who intercepts the ciphertext and tries to make sense of it needs to somehow undo the encryption process without knowing the private key. However, the only known method of reversing RSA encryption involves determining the two prime factors associated with the public key. Since no computer appears able to do this in a reasonable amount of time, RSA is believed to be a strong mechanism for providing confidentiality.
Some of the language that I just used merits further unpacking. First, I argued that no computer can determine prime factors in a reasonable amount of time. Note that I did not say that determining prime factors is impossible. Because it’s not; it is possible. As noted earlier, trying to divide by every prime from 2 onward will eventually result in the two prime factors being found. Given the computers used today, however, the human race is more likely to face extinction, or at least to evolve into a different species, before all the possible prime factors of a 900-digit number have been tested.12 Note that this argument is based only on the computers we use today; a more accurate security assessment needs to take into account the computing capability we expect to have in the future.
A perhaps more alarming issue is that it is only believed that no computer can find prime factors efficiently. The claim that determining prime factors is hard can be based only on what we know, not on what we don’t know. A more accurate version of this claim is that, even with the smartest techniques known today, determining prime factors seems to be hard. This doesn’t mean that some child genius, or indeed artificial intelligence, of the future won’t come up with a new method of determining prime factors. Such a method would have catastrophic consequences for any technologies relying on RSA. For the security of many of the things we do in cyberspace today, the possibility just doesn’t bear thinking about. Except it does, and I will, before the end of this book.
A Reliance on Hard Sums
While a design for a new symmetric encryption algorithm scratched on the back of an envelope is unlikely to end up passing the stringent security requirements of an AES competition finalist, neither might it be disgracefully insecure. As a result, many symmetric encryption algorithms have been proposed, particularly block ciphers. Although the majority have eventually been found wanting, a decent number have had no significant flaws found in their design and are, at least in theory, available for use.13
In contrast, there have only ever been a handful of serious proposals for asymmetric encryption algorithms. Creating a digital padlock requires rather counterintuitive properties. A computing task needs to be found that is easy to do and hard to reverse, but possible to reverse if you know a special piece of information. Not many such computing tasks are known.14
The concept of asymmetric encryption was first suggested in the 1970s. The idea was conceived independently in both the secret governmental world of GCHQ (Government Communications Headquarters) in the UK, and the public academic world of Stanford University in the US. The secret discovery came first, but in true British style, an idea that would help to drive a computing revolution in the 1990s was quietly set aside. Interestingly, in both cases only the idea of asymmetric encryption was initially proposed, not a concrete example of an actual asymmetric encryption algorithm. Indeed, in both cases it was other researchers who followed up on the initial idea by proposing how asymmetric encryption could be realized. Most extraordinary of all, in both GCHQ and academia, researchers seeking an example of an asymmetric encryption algorithm essentially came up with the idea of RSA.15
This tells us two things. First, finding examples of asymmetric encryption algorithms is difficult. Second, RSA is, in some sense, a “natural” solution. Mathematicians throughout history have extensively studied the problem of finding prime factors of a number, so it’s an obvious computational task around which to try to design asymmetric encryption. Importantly, it’s also a simple problem to understand, which helps foster wider confidence in RSA. As a result, RSA was by far the most important asymmetric encryption algorithm of the late twentieth and early twenty-first century, being widely adopted by almost all applications requiring asymmetric encryption.
That said, RSA is not the only asymmetric encryption algorithm you might come across. At least one other asymmetric encryption algorithm, based on a mathematical concept called elliptic curves, is used fairly widely. While the security of RSA encryption relies on the difficulty of computing prime factors, the security of elliptic-curve encryption depends on the difficulty of working out something called discrete logarithms.16
This direct linkage to a specific computational problem is both the great strength and potential weakness of asymmetric encryption. The security of a block cipher can be likened somewhat to building an intricate series of barricades. To access the plaintext, an attacker needs to tunnel under a wall, cut some barbed wire, choose which of several secret pathways to follow to the next barricade, climb over a slippery mound, swim a ditch, and fight their way through a field of head-high maize. To make the block cipher more secure, more barricades are stacked until it is believed that an attacker will not be able to fight their way through.
In contrast, the security of asymmetric encryption is connected to the computational problem around which the algorithm is designed. If the problem is well understood and widely believed to be difficult, which is the case for seeking prime factors, then confidence can be placed in the security of the associated asymmetric encryption algorithm. But if, for some reason, the computational problem turns out not to be as hard as everyone hoped, the algorithm is doomed. This situation is more like wearing a protective suit made from material believed to be bulletproof. If it really is bulletproof, we’re fine. If it’s not, beware of loud bangs.
This uncertainty, at least partly, explains why the world has been somewhat conservative about adopting new asymmetric encryption algorithms based on less well studied computational problems than factoring and computing discrete logarithms. At the end of this book I will look to the future and discover that this is a conservatism we’re going to need to overcome as soon as possible.
Problems with Padlocks
As you’ve seen, creating a digital padlock is possible. Asymmetric encryption enables us to establish confidentiality on a link between our computer and a website we have never previously visited. We first obtain the public key of the website, which could, for example, be prominently displayed on its home page. The public key then enables us to send encrypted data to the website. Brilliant and elegant!
Alas, not quite. Unfortunately, there are two difficulties with this concept of a digital padlock, and they are both significant. Neither are showstoppers, but they are party poopers. The approaches used to address them dictate the ways in which asymmetric encryption is used today in real systems.
The first problem is inherent even in the physical scenario that I used to motivate asymmetric encryption. Remember the lawyer and the hyperactive courier? I argued that an efficient solution to sending a confidential physical letter to the lawyer was for the lawyer to first courier a padlock to you. There’s a catch here that I glossed over. A courier shows up at your home, rings your doorbell, and hands you a package containing a padlock. This might work, but what happens if the courier is dishonest? After all, the courier could have discarded the lawyer’s padlock and replaced it with one of his own. You lock the letter in the box, believing that only the lawyer can unlock it. Unfortunately, in reality, only the courier can unlock it. The problem here is that you cannot be sure the padlock you are given is the padlock that genuinely belongs to the lawyer.
This scenario is analogous to obtaining a public key from a website. Can you really be sure the public key on a website is the genuine one for communicating securely with the business you think owns the website? Maybe the website was hacked. Is this even the correct website for the business you think you’re conducting a transaction with? The history of fraud and other evils in cyberspace is full of examples of innocent users failing to distinguish fake websites from genuine ones. Asymmetric encryption relies on the assumption that you have the correct public key before you encrypt anything. If this is in doubt, all bets are off.17
Addressing the problem of determining the validity of public keys means we must establish procedures for reliably linking people and organizations to public keys—a task that is surprisingly difficult. Like many technologies, cryptography works brilliantly until you involve human beings. We might be clever, innovative, creative, and eager to embrace new ideas, but we can also be lazy, selfish, manipulative, and naive. Manufacturing a secure padlock is one thing. Finding a reliable and honest courier service is quite another. I’ll return to this thorny issue when I later consider how cryptography gets broken.
However, assuming we can find a way of placing some faith in the correctness of ownership of a public key, there is yet another problem, this time a technical one. All the asymmetric encryption algorithms we know today are slow. By slow I don’t mean “like a snail.” What I mean is this: relative to symmetric encryption, asymmetric encryption is slow. If you encrypt data using AES, then there is almost no delay. When you encrypt data using RSA, there is a slight delay, although you, personally, probably won’t notice it. For example, RSA encryption on a laptop might take a few thousandths of a second. Who cares? Such a delay, however, matters to a website deluged by millions of requests for secure connections. All these thousandths of a second start to add up to real seconds, resulting in delays noticeable by humans.
Once upon a time, delays of seconds did not matter. In Laurie Lee’s England of the 1920s, as portrayed in Cider with Rosie, Rosie would have merrily initiated an RSA encryption (had RSA been invented, and had she had any device on which to use it!) and then headed off to milk the cow and churn some butter, delighted to get back some ciphertext in an hour or two’s time.18
In today’s frenetic world, seconds are important. Stock prices rise and fall in the flutter of an eyelid. Consumers abandon shopping carts if their screen fails to respond promptly. Commuters hurtling through an automated ticket barrier don’t have fractions of a second to spare before the travelers behind thunder into them. Everything needs to happen now. This need for speed applies particularly to something like encryption, which nobody really wants to do, but which is done out of necessity. This means that encryption had better be very, very fast.
The Best of Both Worlds
Symmetric encryption is fast, but it has a particularly challenging key-distribution problem. Asymmetric encryption is slow but conveniently allows encryption keys to be downloaded from websites. Each type of encryption has a positive feature that nicely complements the other. How can we harness the benefits of both types of encryption while overcoming their drawbacks?
If we return now to our favorite scenario, here’s the answer: The courier delivers a physical padlock from the lawyer. You first take a conventional key (the type of key you use to both lock and unlock). You place the confidential letter in a box, which you lock with the conventional key. You then place the conventional key itself into a smaller box, which you lock with the lawyer’s padlock. Now, you courier both boxes to the lawyer, who first opens the small box, and then uses the key it contains to open the larger box. This analogy is getting sillier, the more we complicate it, so instead, let’s focus on websites, where this solution makes far more sense.
Here’s the idea, which is often called hybrid encryption. You want to secure a confidential connection to a website. You first obtain the public key of the website. You’d love to use this public key to encrypt your data, but sadly, asymmetric encryption is slow. So, you generate a symmetric key and speedily AES-encrypt your data by using this key instead. You then RSA-encrypt the symmetric key by using the public key of the website. The process might, indeed, be slow, but all you are encrypting here is a small piece of data—namely, a symmetric key. At about 128 bits, this is likely to be much smaller than all the data you really want to protect over the communication channel to the website. Finally, you send the two items of encrypted data to the website. The website first (slowly) decrypts the RSA ciphertext to recover the symmetric key. The website then (speedily) decrypts the AES ciphertext by using the symmetric key. It’s the best of both worlds.
When asymmetric encryption is used in everyday technologies, it is almost always deployed as part of a hybrid encryption process. Hybrid encryption is commonly used, just as described, to secure the connection between two computers, such as when a web browser connects to a website. Hybrid encryption is also typically used for securing email, where a symmetric key is asymmetrically encrypted by using the email recipient’s public key, and then the body of the email is symmetrically encrypted by using the symmetric key.19
It’s a Miracle; Get Me Out of Here!
Asymmetric encryption is miraculous; there is no better word to describe it. For centuries, cryptographers had to live with the symmetric-key-distribution problem. They did not imagine there would turn out to be a cryptographic solution to it. The idea of a digital padlock is revolutionary, as it enables strangers to secure communications with other strangers. In the late 1990s, asymmetric encryption enabled confidentiality to be provided to the increasing number of fledgling World Wide Web users. You could argue that the success of the web is, at least in small part, down to the miracle of asymmetric encryption.
However, the two issues identified earlier regarding the use of asymmetric encryption should never be underestimated. Reliably linking users to their public keys is a complex process. And asymmetric encryption is slow. Around the year 2000, asymmetric encryption began a rapid descent on the famous Gartner Hype Cycle20 from the “peak of inflated expectations” to the “trough of disillusionment,” as the booming, and then busting, dot-com businesses realized that asymmetric encryption was a miraculous beast with a sting in its tail. What they didn’t realize is that you should never use asymmetric encryption, even in its hybrid form, unless you truly must.
The core issue is this: the only times you genuinely need to use a digital padlock are when you are operating in a relatively open environment, where you don’t have full control over the wider system (including the users and the underlying network). This is precisely the case when we browse the web, or send emails around the globe. If, on the other hand, you are in a closed environment, where you can exert control over the system, then you don’t need asymmetric encryption at all.
Choose your favorite user of encryption technology. Choose banks. Mobile phone companies. Car companies deploying electronic keys. Issuers of smartcards for transportation ticketing. Controllers of a Wi-Fi network. In all these examples, there is an entity that has control over users of the system, the network being used, and, most importantly, a managed process by which symmetric keys can be distributed. Whenever you can control users and easily distribute keys, there is absolutely no need for asymmetric encryption. If you can encrypt quite happily by using only speedy symmetric encryption, this is precisely what you should do.
Asymmetric encryption should be regarded as a tool solving a very specific problem: how to share a secret with a stranger. Solutions to achieving this seemingly impossible task might well have their drawbacks, but what matters is that they’re possible, and available to use whenever (but only whenever) we strictly need them.
* 100 petaflops = 100,000,000,000,000,000 operations per second.