How Asymmetric (Public Key) Encryption is Possible, and Why It Matters

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.

 

Cryptography 101: Low-Tech Cryptanalysis Explained

Well, with Bitcoin going mainstream, public resentment against the NSA at an all-time high, and people not having a clue what Cody Wilson of Defense Distributed means by labeling himself a Crypto Anarchist, it looks like a few posts on cryptography and Crypto Anarchy are in order.  There will probably be five posts; this one will be an intro to cryptanalysis, the next will explain how public key encryption works, after that I will do another one on elliptic curve and quantum cryptography schemes. From there a post will be devoted to a primer on Crypto Anarchy and the last post will be a categorical list of software tools for any beginning Cypherpunk.

 

Now for some beginning cryptanalysis. To put it bluntly, this post will be an introduction to code breaking that will look at some very simple means of encoding and sending “secret” messages by hand. As it turns out these are pretty trivial to break, but their biggest drawback becomes apparent if you try to use such low-tech methods over the world wide web.

 

Let’s start with the traditional substitution cipher. There’s nothing very sophisticated about it; you simply take a letter of the alphabet and replace it with something else. This could be another letter, a symbol you made up, or what have you. The most famous yet very simple example is the Caesar Cipher. Each letter of the alphabet is replaced by a letter three spaces to the left of it; the letter D is written as A, E is written as B, and so forth. Here’s what the cipher looks like as well as how it “encodes” a message:

 

How a typical substitution cipher works.

How typical substitution ciphers work. A letter is replaced with something else.

 

Simple enough right? Now let’s look at another method called a transposition cipher. Rather than replacing a letter of the alphabet with something else, you simply change where the letters are actually located on the message sheet itself. Here’s a simple example:

 

One of many transposition ciphers. Location is what matters.

One of many transposition ciphers. Location is what matters.

 

So now we know the two main low-tech methods for encoding messages, but breaking them is pretty simple to do.

 

The means of breaking these two general approaches to making “secret codes” varies greatly. For substitution ciphers the longer the message is (or the more material you can intercept over time), the easier it becomes to decipher the meaning of the text. While a number of various techniques can be applied for doing so, they all usually stem from just two strategies: frequency analysis and letter pairs.

 

Frequency analysis takes advantage of the fact that each letter of the alphabet will appear at different rates; the letter “E” for example is the most commonly used letter of the alphabet and chances are the most common letters/symbols in a message will be vowels. This is why it cost money to suggest a vowel on “Wheel of Fortune” – filling in a vowel makes it much easier to guess the puzzle. Letter pairs of course tend to be two vowels as well. Plugging those in can help you decipher a message with some trial and error. The more material you have to work with (longer messages, more messages, or both) the more successful the techniques will be.

 

Transposition ciphers on the other hand are a different story. They are almost always easier to break if the message is very short. In the case of the rail fence example pictured above, it only seems easy because the visible message (25 letters) isn’t concealed by bogus letters that hide how the letters in the message (25 total) have been transposed. The obvious way to try break the cipher would be to take a given letter, and see if a pattern can be found with other corresponding letters that eventually form a word. More complicated means exist for breaking various transposition ciphers, but all that’s beside the point of this post.

 

These two approaches to encoding messages have their own distinct pros and cons. What they both have in common however is that they simply lack the level of security needed to encrypt information sent over the internet. This is because any recipient of an encoding message must have the cipher needed to decode it, and sending it over the internet where a malicious third party could intercept it defeats the whole purpose of using the cipher in the first place.

 

What we need is something that allows someone to send messages to you that are encoded that you can decrypt, but does not require you to send the necessary key for decryption over any information channel an adversary might be listening into. My next post will explain how asymmetric encryption – better known as public key cryptography – solves this dilemma.