- the art of writing or solving codes, especially secret codes, ciphers, etc.
- encryption and decryption
"Cryptography isn't just for spies, we all rely on it nearly every day."
Cletus is a farmer, ask him if he uses cryptography and he'd probably say "Crypto what? That 'bout graveyards or some such?"
"No Cletus," you'd politely correct him, "cryptography is about protecting your privacy. It is a critical component of e-commerce. It provides protection from criminals as well as invasive data collection. Not only does cryptography create security, it also prevents censorship and safeguards individual freedom from overbearing governments."
After a moment of intense contemplation, Cletus might respond "I don't know nothin 'bout all that. Alls I know is I ain't got nothin to hide and this here shotgun protects my freedom. Ain't no commie spies gonna censor me none. Murica!"
Trying not to sound too exasperated, you'd continue "That's great Cletus but haven't you ever shopped online, like maybe at Walmart.com or GunsAmerica.com? If you have nothing to hide, how do you keep thieves from stealing your credit card information?"
"I don't use no credit cards and I sure as heck don't use none of that Internets hooey. The Good Lord willing, I got all I need right here on my farm."
Indeed, Cletus is lucky enough to own a coffee farm on a tropical island with a year-round growing season. In addition to coffee, his farm also has a plethora of fruit trees, a garden overflowing with vegetables, a noisy flock of chickens and plenty of delicious wild pigs to eat. With enough hard work, he can grow all the food he needs. He doesn't ever have to leave the farm, at least not until he needs more diesel for his pickup truck, runs out of ammunition for the shotgun or drinks his last beer.
Cletus might not be much for book learning but he's a friendly guy and quite resourceful. When he runs out of ammo he simply trades some coffee with his friends at the local gun shop. When he runs out of alcohol to drink or diesel for his pickup, he knows a guy up the mountain who built himself a moonshine still.
"Problem is," Cletus explains, "that feller's a cranky old bastard who don't like coffee none. What kind of backwards hillbilly don't drink no coffee?! I tell you what. I reckon that boy's two fries short of a Happy Meal."
To get around this minor alcohol procurement setback, Cletus trades his coffee with a neighbor who grows tea, then has to find a tea drinker who grows hops, then trades the hops with the cranky, non-coffee-drinking, home-brew aficionado up the mountain. It requires a little extra leg work but Cletus reckons it's better than having to deal with unwanted complexities such as e-commerce or needing a "city-type job so's I can shop at the Walmarts."
Not having regular employment makes it relatively easy for Cletus to avoid cryptography. All he has to do is avoid the Internet, cell phones, credit cards, gas stations, Walmart, hospitals, the welfare office and any part of society that tracks, stores or otherwise uses any personal information of any kind.
If, like Cletus, you stay completely off the grid and barter for everything instead of using money then you may not need cryptography either. For the rest of us, it's an important part of our lives. Unfortunately, Cletus isn't the only one that lacks a clear understanding of cryptography. He's also not the only one that's a little scared of it. Nearly every politician in the world has expressed concern that cryptography makes it difficult for government security agencies and law enforcement to protect us from terrorists and criminals.
It doesn't do anybody any good if terrorists can move toward encrypted communication that no law enforcement agency can break into before or after. There must be some way. I don't know enough about the technology to be able to say what it is ... but I have a lot of confidence in our tech experts. Hillary Clinton, 19 Dec 2015, 3rd Democratic National Debate
This isn't just one politician's view, it's nearly all of them, Democrat and Republican. On the bright side, yea, finally something that all they can agree on. Unfortunately, they're all wrong and their lack of understanding is disturbing. No politician, no government agency, no International coalition, no collection of geniuses can prevent the bad guys from using cryptography. That's not a pleasant thought but it's true.
With the possible exception of Cletus, the rest of us rely on cryptography every day. It is an important and ubiquitous part of our society and it affects your daily life in ways you may not even realize. Luckily, as you'll see, it's not that complicated.
Secret-key cryptographyCryptography has been around for a very long time. One of the earliest and simplest examples is a shift cipher, sometimes called Caesar cipher because it was supposedly used way back in ancient Rome. Fancy-pants cryptography experts like to call it a rot-N substitution cipher because it rotates each letter by N places in the alphabet. Whatever you want to call it, it's a very simple code to break. It worked for Caesar because most of his enemies were illiterate or simply assumed the encoded message was in a foreign language they didn't understand. If you're literate, and the secret message is in English, you can break it by knowing that the most common letter or symbol is e, the second most common is t, and so on.
Simple substitution and transposition ciphers work fine if you're passing a note to a friend at school or afraid your little brother might find your diary but if your needs are more serious, like communicating across enemy lines or protecting bank records, then you'll probably want something slightly more secure. When military commanders started relying on long distance radio communications during the World Wars, suddenly all sorts of complex cryptography was invented. The famous German Enigma machine enciphered messages that were nearly impossible for the Allies to break. Likewise, the Japanese were completely stumped by the Navajo Code Talkers. Even today, such methods can be nearly impossible to break if you don't know the secret.
All the above methods are known as secret-key cryptography, or symmetric cryptography. That means that whatever the secret is, whether a password, algorithm or code book, it must be known by both the sender and receiver while kept secret from everyone else. The secret can't be changed unless both the sender and receive know the new secret. If the enemy ever manages to get ahold of the secret, whether by espionage, bribery, burglary, trickery, defection, brute force, or pure luck, then every message sent can be decrypted. Even worse, if the good guys don't know that the bad guys have the secret then the bad guys can pretend to be the good guys and create their own messages.
"Command Base to Alpha Team, initiate the attack."
"... um, Command Base to Alpha Team, we changed our mind, you should drop your weapons and run away."
The problem with a secret-key cryptography is that both parties have to know the secret. It would be far more secure if the secret didn't have to be shared at all. If there's no shared secret then there's no code book to be lost, stolen or copied; nobody to be bribed, tortured or lured to the dark side; no vulnerable cipher for the enemy's clever team of code breakers to decipher. If only there was some type of cryptography that didn't require a shared secret key. While at it, this magic cryptography should also be easy to use and impossible to break.
Well, in 1977, three nerds at MIT (Rivest, Shamir, and Aldeman) managed to create just such a method. They had been working on the problem for more than a year when Rivest, after a night with a little too much Passover wine, was laying on his couch and thinking about math, as nerds sometimes do. That's when he finally devised the algorithm that would change the world forever. That algorithm became known as RSA security and it is still widely used today.
The formal name for this newfangled magic is public-key cryptography, or asymmetric cryptography. It's asymmetric because there are two keys, one that is secret and the other which can be made public. There's no need for a shared secret, the algorithm is straightforward, it can be used by anyone, and it is guaranteed unbreakable! With all this magic in a single package, it's no wonder governments are afraid of it.
Just in case you don't see how astoundingly awesome this is, I'm going to say it again. So, like, one person uses this magic math formula to encrypt a secret message. Then the person receiving the message can use the magic math formula to decrypt the secret message. Nobody else on the planet can decrypt the secret message even though the magic math formula isn't a secret. This magic math formula is so powerful that governments are afraid of it yet so easy that anybody can use it.
That all sounds too good to be true, right? If the magic math formula is really that powerful, there's no way it can be so easy that anybody can use it, right? What could this magic math formula possibly be? Here it is:
Yup, that's it, simple multiplication. Well, the details are a bit more complicated but that's the basic idea. P and Q are the private key and N is the public-key. The trick is that you have to choose p and q very carefully. Here's why.
Some math problems are very difficult to find an answer to even if we know how to solve them. The fancy word for this is intractable. A less fancy description is trap-door. A trap-door problem is easy to solve one direction but not the other. Prime factorization is an example of this. It's easy to multiply two prime numbers together but if all you have is the answer, it's far more difficult to figure out which two numbers were multiplied together to get there. It's like a one-way trap-door.
To understand this better we have to first remember that a prime number is any number that is only divisible by one and itself.
Once we have our list of prime numbers, we can factor any other number into primes by finding the prime numbers that multiply together to make the original number. For example:
6 = 2 × 3
12 = 2 × 2 × 3
30 = 2 × 3 × 5
60 = 2 × 2 × 3 × 5.
... and so on.
Most of us learned about prime factors in math class then quickly proceeded to forget about it. No big deal, factorization wasn't a hugely important part of society until public-key cryptography was invented and even now computers do all the work for us. The important thing to remember is that computing prime factors is very time consuming while verifying the answer is easy. Or, said another way, multiplying is easy but prime factorization is hard.
Here's another example. Is 5149 prime? If not, what are its factors? It's not divisible by 2, nor 3, nor 5, nor 7...
Keep going, I'll wait.
It takes awhile.
Ok, here's a hint, what is 19 × 271?
Once you have the answer it is trivial to verify but finding the answer is difficult. This is an example of P vs NP and it is an important computer science problem with some interesting ramifications. Even really smart math geniuses agree that computing prime factors of large numbers is so time consuming that it is basically impossible. The experts call this type of math hard. You might feel that all math is hard but the experts disagree, some problems are hard while others are easy. The trick that makes public-key cryptography work is using math that is hard, such as prime factorization.
Is prime factorization really so difficult that it makes cryptography secure? Computers are good at math, why can't they can just solve it? What about future computers that are even faster, will they be able to break today's cryptography? Let's find out in this blue box...
Now that we understand how math such as prime factorization is easy to do in one direction but impossible in the other direction, we can use it for cryptography. Start by randomly choosing two very large prime numbers, preferably a couple hundred digits each. Let's call these numbers your private-key. Now multiply them together and that is your public-key. Your private-key stays secret while your public-key can be published to the world. It's safe to give away your public-key because the one-way math makes it practically impossible to decrypt your private-key.
Now for the really cool part. With a little more math, anybody that has your public-key can send you messages that only you can decrypt with your private-key. Likewise, you can use anybody else's public-key to send them messages that only they can decrypt with their private-key. This means private information can be sent right across the Internet because even if someone is eavesdropping, the only way to decrypt the intercepted information is with your private-key and you're the only person in the world who knows what it is. Confidentiality is guaranteed. Even if Chuck is listening in, he can't understand what Alice is saying to Bob.
Another neat trick happens if the process is done the other way around. If I use my private-key to encrypt a message then you or anybody else can use my public-key to decrypt the message. The world knows the message came from me because I'm the only one with my private-key. This is called authentication and it's a great way to create a digital signature. This prevents man-in-the-middle attacks such as Chuck pretending to be Bob and sending fake messages to Alice.
The RSA guys invented public-key cryptography in 1977 and in 1991 another clever fellow, Phil Zimmermann, published a popular piece of software called PGP. It hides all the math of RSA behind an easy to use interface. While that software is still used, it is currently owned by Symantec. No problem, the protocol is public domain and there is a popular, free, open-source alternative called GPG that works just as good.
The one-way nature of prime factorization is easy to understand and considered unbreakable but it's not the only security algorithm. Other math geniuses have discovered even more intractable algorithms such as Elliptic Curve Cryptogrophy. ECC produces more security with smaller keys. For example, a 20 digit ECC key is more secure than a 200 digit RSA key. Even though the math is more difficult for most humans, the smaller key size makes it faster for computers. That means less powerful computers, such as mobile phones, can still stay ahead of more powerful computers, such as giant networks of eavesdropping super computers. Whether using prime numbers or funny curves, almost all Internet security that we use today is built on top of this intractable mathematical wizardry.
The only remaining issue is publishing the public keys. If all you're doing is exchanging email with friends then your public-key can be published anywhere. Once your friends have your public key then it doesn't matter if someone else makes a bogus key with your name on it because your friends already have the real key. On the other hand, if you're doing business with the public in general then you don't want anybody else publishing fake keys with your name.
To manage this public-key publication process there is a complex hierarchy of Certificate Authorities. Symantec (owners of VeriSign), Comodo and GoDaddy are the top three. For a small fee, about $100 per year, they're happy to issue an SSL certificate to anybody that wants one. All you have to do is provide some ID so they can verify your real-world identity. For example, you can't pretend to be Microsoft.com because they already have an SSL certificate with a trusted Certificate Authority.
If you have ever purchased anything on the Internet, visited your bank's website, or logged into any website that requires a password, then you have used public-key cryptography. If the website address starts with
https://, that s (and often a lock icon ) indicates that the website is using an SSL certification. An eavesdropper can see that you visited the website but only you and the website know what information was transferred. Of course this security only applies to the communication, whether or not the website keeps the data on their servers secure is a whole different issue.
Good or Bad?
It's easy to see why those who are concerned with security, such as governments, banks, and online merchants, use public-key cryptography. It is far better than an envelope with a wax seal or a code book that might fall into the wrong hands. The mathematical wizardry of public-key cryptography is far more secure than a messenger boy could ever be. How secure? Let's put it this way, the U.S. government considers cryptographic software a munition. Shortly after Zimmerman published PGP in 1991 he was investigated for violating the Arms Export Control Act. PGP allows anybody to communicate in a way that even the authorities can't listen in and that's not a power we want the bad guys to have.
As much as governments would like to control cryptography, doing so is about as easy as controlling the motions of the planets, changing the value of pi, or eradicating email spam. This won't stop the authorities from trying though. The Edward Snowden leaks revealed that the NSA inserted back doors into commercial software. It was also shown that large corporations such as Google and Apple could be legally compelled to decrypt smartphone data. In response, these companies changed their encryption software to something that even they can't break. In response to that, President Obama, following British Prime Minister Cameron's lead, stated that law enforcement and intelligence agencies should have the ability to decrypt anything necessary for preventing crime or fighting terrorism. This isn't an issue of Democrats versus Republicans, and it's not an issue of criminal versus innocent, this is an issue that affects the privacy, security, and freedom of everyone, everywhere.
It's not likely that this controversy will end any time soon. There's no question about it, encryption does indeed make it more difficult for security agencies and law enforcement to monitor the bad guys. In a recent (2016) court case, the FBI once again demanded that Apple needs to provide an encryption backdoor. Apple's CEO recognized the danger of this demand but refusing the demands of the U.S. government is not easy. The FBI sited a law from 1789 to justify giving them access. They claimed that this access would only be used as necessary. The problem is, if the FBI's backdoor key was ever leaked, the entire world would instantly be vulnerable to attack. This risk might be justified if there was a good reason for it but a government sanctioned backdoor like this won't help stop the criminals. They can simply use their own encryption key rather than the one hard-coded on their iPhone, thereby rendering the backdoor pointless. A government sanctioned backdoor only hurts innocent citizens.
weakening encryption ... would hurt only the well-meaning and law-abiding citizens who rely on companies like Apple to protect their data. Criminals and bad actors will still encrypt, using tools that are readily available... Tim Cook, Apple CEO, 2016 Open Letter to Customers
You may have noticed over the past few years that many website addresses have changed from
https://, with the s meaning secure. Even websites with no obvious need for security, such as Google and Wikipedia, have switched to SSL for everything. The reasons for this are nuanced and complex. It is partially to give users more privacy but it also helps protect the website owners from unwanted liability. Using cryptography is like using window blinds, it keeps the nosey neighbors from watching everything you're doing. You might not care if the neighbors watch but Google, Wikipedia, and Facebook don't want to be responsible if something goes wrong. It's far easier and safer for them to simply encrypt everything.
When the general public starts using encryption, that causes a problem for governments that want to censor the Internet. For example China doesn't want its citizens looking up information on Wikipedia about Tiananmen Square. At first they censored everything. When that proved too problematic, they censored just the offensive Wikipedia page. They even got clever and delivered their own fake pages instead, pages that looked authentic but had the government's prefered version of history. Now Wikipedia has switched to
https:// which means the Chinese censors have no way to know what page their citizens are looking at and no way to change those pages. As a result, they're back to censoring everything.
Whether it's censorship in China or fighting terrorism in the U.S. and Europe, it doesn't really matter what anybody wants because it's too late to put this genie back in the bottle. Not only is public-key cryptography widely published and accessible, it's already programmed into our computers for us. Clever criminals will continue finding ways to trick us and the authorities will continue finding ways to control us but nobody can break the encryption.
We live in a world where Target knows if your daughter is pregnant, Facebook can spark a revolution, and Nigerian investors need your help. It's scary to think that the authorities might not be able to protect us from the bad guys but cryptography helps us protect ourselves even if the authorities are the bad guys. Cryptography has taken some power away from those in charge and given it to the rest of us, both the good guys and the bad guys.
"So what's the answer," you might ask, "is cryptography good or bad?"
"Both" I would answer. "But it's not a matter of liking it or hating it. Cryptography is here to stay so what's important is understanding it because that's the only way we'll be able to make intelligent decisions. To see if you understand cryptography better than the politicians, let's see if you can pass this little test."
"What?! Nobody said there would be a test!?"
"Don't worry, it's an easy test. It's more of a game really."
Hint: If you get stuck, the important parts are highlighted above in yellow.
Public-Key Cryptography Test
- Level 1
- Level 2
- Level 3
- Level 4
- Level 5
Level 1: Encryption
Help Bob decrypt Alice's secret message.
Alice used her secret key to encrypt the message,
drag and drop the key that will decrypt the message.
Level 2: Confidential
Help Alice send a confidential message to Bob.
Prevent Eve from eavesdropping, even if she has
a copy of everyone's public keys.
Level 3: Authenticated
Help Alice digitally sign her message.
Help Bob verify that the message came from Alice.
Don't let Chuck send a fake message.
Level 4: Full Security
Help Alice send a signed and confidental message.
Help Bob authenticate and decrypt the message.
Don't let Chuck make changes, don't let Eve eavesdrop.
Level 5: Extra Credit
Help the Internet get a copy of Alice's message.
While private-key cryptography is very secure,
sometimes there are other ways to EDIT a message.
SummaryLike language, public-key cryptography is used by everyone yet owned by noone. Also like language, authorities sometimes try to control usage they deem harmful. Ultimately, like language, cryptography can be used for good or bad.
Authentic: The private-key provides a digital signature. If I'm the only one with my private-key then I'm the only one that can make my signature.
Confidential: The public-key provides encryption. If I use your public-key to encrypt a message then you're the only one that can decrypt it.
Public-key cryptography is both easy to use and provably secure. Maybe some day someone will figure out how to break it but currently not even giant government supercomputers can break public-key cryptography. There is no denying that public-key cryptography is a powerful tool and an important part of our society. It can dramatically affect our privacy, security, and freedom. But that's just the beginning. Next, let's see how public-key cryptography could make our money obsolete.
Part 2: Will Bitcoin make money obsolete?