Rosio Pavoris a blog

Another post in my series on cryptography for beginners. This time: the difference between symmetric and asymmetric encryption!

Basically, there are two main types of encryption: symmetric and asymmetric.
The most important difference between them is that symmetric encryption uses the same key for encrypting and decrypting, while asymmetric encryption uses different keys. Let’s see what this means.

Symmetric Encryption

Symmetric encryption is by far the oldest. It’s also generally more secure and less computationally expensive than asymmetric encryption.

One example of symmetric encryption is the Caesar substitution cipher. This works by taking your message letter by letter, and replacing each one by the letter that comes X places after it in the alphabet.
For instance, if your message is “LOL DONGS” and X is 3, the encrypted message is “ORO GRQJV” (well, spaces are generally omitted as well, but that’s not that important). 3 is the key in this case, and the message can be decrypted easily if the key is known.¹

In the case of the Caesar cipher, the key is always a number, but it doesn’t have to be. For instance, the basic XORing cipher uses a passphrase as its key.
Remember that XOR is the exclusive or operation in boolean algebra. The truth table looks like this:

A XOR cipher looks at the bits that represent your message (for instance, in ASCII) and the bits that represent your key, and XOR the first bit of the message with the first bit of the key, the second bit of the message with the second bit of the key, and so on, repeating the key as often as is necessary.²
For instance, if your message is “LOL DONGS” and your key is “GASP“, it will look something like this:

You can then try to display the message again, but it will as often as not produce a lot of unprintable characters (in our case, the result is ␋␎␟p␃␎␝␗␔, or (vertical tab)(shift out)(unit separator)p(end of text)(shift out)(group separator)(end of trans. block)(device control 4), in words; that’s only one printable character), so data encrypted this way is generally stored as a raw binary file. To decrypt it, you just XOR it with the key again.
This by way of example. Modern encryption algorithms are, of course, vastly more complex, though most of them do involve XORing at some level.

Most ciphers out there are symmetric. Some modern examples include DES, AES (AKA Rijndael; developed at the KUL, dontchaknow), Schneier’s Blowfish and Twofish, and IDEA.
Symmetric ciphers can be further divided into block and stream ciphers, depending on how they work, but that’s not important right now.

Asymmetric Encryption

Asymmetric or public-key encryption, on the other hand, uses a different key for decrypting the message than was used for encrypting it.
The encryption key is referred to as the public key, because anyone can have access to it without compromising the encrypted message (even though that key was also used for encrypting it). The decryption key is the private key, because obviously only the person the message is intended for can have access to it.

“But Carin,” I hear you cry, “How can this be? How can you encrypt a message and be unable to decrypt it later?”
That’s an excellent question, and most (well, all, to my knowledge) asymmetric encryption algorithms depend on the fact that it’s very hard to factor large numbers effectively.
In theory, if you could factor numbers as easily as you could multiply them, asymmetric encryption as we know it today would be impossible; the strength of asymmetric encryption depends on the fact that it’s faster (or nearly so) to bruteforce your way to the message than it is to factor the numbers and get it the “easy” way.³

Asymmetric encryption is a relatively new concept, in large part because it’s only the computational power we’ve developed in recent years that made it possible.
It’s potentially much more convenient than symmetric ciphers, because you don’t have to figure out a secure way of getting your key to the person you’re sending an encrypted message to. However, it has its downsides.

For instance, RSA⁴ (the most popular asymmetric cipher in use today, for various reasons) works by raising a numerical representation of the message to the power of part of the public key; specifically, the product of two large prime numbers. In a typical implementation, these prime numbers are 1024 or 2048 bits in size (1024 is now considered unsafe).
As you can imagine, this is somewhat computationally expensive, even with the various optimisations that are possible. In fact, it’s hugely slow compared to symmetric encryption.

Not only that, key generation is very important; even ignoring the hypothetical dangers of quantum computing, if your keys are badly chosen, you might as well be sending plaintext over the network.
Chosing proper keys is important for symmetric ciphers as well, of course, but it’s generally easier to spot a shitty key for symmetric ciphers (everyone knows “password” is a bad key, right? RIGHT?) than it is for asymmetric ones. There are guidelines that help you pick decent keys, but still.

All the same, it’s still hugely popular on the internet, for various reasons.
Because of the computational cost, it’s often just used to encrypt a key, which can then be used for some type of symmetric encryption, which ideally is the best of both worlds.

PGP (and GnuPG) uses asymmetric encryption for e-mail encryption, which is a nice application, since both encryption and decryption can happen on the client-side, where there’s presumably more computing power to spare than on the server.

Another important application is digital signatures, which I’ll come back to in a future post.
For instance, if you want to prove you wrote a message, you can just encrypt the plaintext message with your private key. Anyone with your public key could then decrypt it to get the plaintext back and verify that it must have been someone with access to your private key who wrote it. Not every asymmetric algorithm is suitable for this, but RSA is.

There are countless other applications which would take forever to explain and aren’t exactly within the scope of this post. Suffice it to say that any type of real security on the internet relies heavily on public-key cryptography.

So yes

It’s all quite interesting.
This is, of course, just meant to be a brief introduction. If you want to see asymmetric cryptography in action, I’ll devote a future post to the Diffie-Hellman key exchange algorithm, which is really just a special case of RSA and so very, very shiny.
Also coming up: much more on digital signatures and how they apply to SSL and the like.

That’s probably more than the casual internet person is interested in knowing (even though all of this is all what stands between the Internet and total oblivion), but it’s interesting, so I’m going to write about it and you’re going to read it, dammit.

¹ ROT13 is a specific variety of the Caesar cipher with key 13 that was popular for hiding movie spoilers and whatnot on Usenet. It’s particularly easy to decrypt, since the decryption algorithm is exactly the same as the encryption algorithm, instead of the reverse. You could say it’s particularly symmetrical.

² Note that if the key is as long as the message (or longer) and sufficiently random, the encrypted message is unbreakable, even in theory. This is a special case known as the one-time pad. “One-time”, because each key or pad can only be used once, lest it be compromised.
It’s still a popular cipher in certain areas (the Cold War era spy with a briefcase full of one-time pads is a common enough stereotype), but it’s unfeasible for most large-scale applications.

³ Which is also why quantum computing is such a threat to asymmetric encryption. Shor’s algorithm allows one to factor large numbers on a quantum computer in polynomial time (specifically, O((log n)³) time, while the fastest traditional factoring algorithms run in exponential time), which would render asymmetric encryption only slightly more powerful than ROT13 (which can be bruteforced in O(n) time, BTW).

⁴ RSA stands for Rivest, Shamir, and Adleman, after its designers. You’ll remember Ronald Rivest from the Message Digest series of hashing algorithms (though RSA is considerably older than these).