This post will serve as a basic introduction to something everyone who cares about privacy or information security ought to be familiar with. At less than a thousand words, it will probably only take you fifteen minutes or so to read and understand.
Public key encryption has been around for decades and has served as an indispensable solution to one of the biggest problems in the secure transfer of information over the web. With the recent revelations over NSA Spying and the establishment of Bitcoin as a somewhat mainstream form of currency, I find myself in more conversations about this feature of information security lately than ever before. How does it differ from just plain old symmetric encryption and why are the two named as such? Last but not least, what major problem does public key encryption solve and how does it achieve this?
In my previous post on low-tech cryptanalysis, I explained how pen and paper ciphers (like substituting each letter of the alphabet with something else) are easy to break but also suffer from a critical flaw that makes them very insecure to use over the web. For someone to use any “secret code” to send messages to someone else, you must first send them the cipher for that code. If you are doing this over the internet, there’s a pretty good chance that cipher will be intercepted and used to read the messages encoded with it. Thus a more robust solution is needed that is both secure when properly implemented and is also safe to implement over a public network.
This is where public key encryption comes in. Public key encryption is often known as asymmetric key encryption because it depends on the use of two “keys” that serve entirely different purposes. One key is used to encrypt messages that are sent to a given recipient, while another is used to decrypt such messages. These are respectively known as the public and private key. When using public key encryption to communicate, you begin by generating a set of these keys. The public key is shared with everyone who may potentially want to send you a message.
This video above gets the basic point right, however I should note that the correct term for the kind of math functions that asymmetric encryption uses is mathematical trap, not “one-way function.” This distinction is critical because the latter term refers to a math function that isn’t just improbable to reverse, but impossible to undo.
So now we know asymmetric encryption takes advantage of math problems that can easily be done in one direction, but require too much computing power to reverse. Why is this important, or useful to begin with? Simply put, encryption that operates this way can be used to communicate with people over public networks without having to actually meet in person to exchange a cipher.
As an example, consider simple multiplication and division problems. Obviously the kind of math used in public key encryption schemes is exponentially more sophisticated that the simple examples I will show here, but the underlying concept remains the same. Take a moment to ponder the following math problems, and decide which one is easier to do:
1. What is the answer to the following: 10 x 100
2. Which numbers were originally multiplied together to get this result: 1,000
At face value, you likely would be tempted to answer the second question by saying “ten times a hundred.” But consider just how many ways there are of getting this outcome using positive integers alone: 1 x 1000, 2 x 500, 4 x 250, 5 x 200, 10 x 100, 20 x 50, 25 x 40, 1000 x 1, 500 x 2, 250 x 4, 200 x 5, 100 x 10, 50 x 20, 40 x 25, and so on. If we broke it down into decimals, the number of possibilities would be even higher. Guessing every possible answer to find the right pair is impractical. With the kinds of mathematical functions that public key encryption actually uses, it becomes nearly impossible with today’s computer hardware.
Multiplying two numbers has only one answer. Dividing a digit on the other hand is another story altogether, the number of ways of doing so makes it unlikely that you can use a computer to search through all the possibilities and find the pair that was actually used for the encrypted result – hence the term “mathematical trap.”
Now comes the final question: How does public key encryption put this feature of math functions to use?
Public key encryption works by having a user generate a pair of keys, one public and one private key. The public key is sent out to anyone who might want to sent them a message, while the private key – as the name suggests – is kept hidden. Remember the first of the two problems listed above that involved the simple task of multiplying two numbers together? This loosely resembles how a public key operates.
When someone wants to send a message to you, they will take your public key and use it to scramble the message they wish to send to you. This requires very little computational power (recall how easy multiplying two numbers was). But if someone wants to decrypt that same message, they would almost never succeed at doing so because of all computational resources required to break it. Remember the second problem listed above and how there were so many possibilities to sort through? The only way to reverse this successfully is if you have the private key, which makes it possibly to reverse the message encryption without having to sort through endless possibilities.
Naturally of course, only you have the private key in question. So the end result is that you can share a public key that can only encrypt messages (multiply two numbers) but cannot be used to reverse the result. That way you can send out a key which people in turn can use to send messages to you that any third party would fail to decipher. This makes asymmetric encryption perfect for communicating over the internet with people you never meet in person.
In my next post, I will go into greater detail on RSA schemes, elliptic curve cryptography, and quantum cryptography.