Asymmetric Key Cryptography: Part 1

Technology by Adam on 2005-04-14 01:07

On an almost daily basis, I find myself wondering why asymmetric key cryptography is not used in more places. This powerful and mature technology is the perfect solution to numerous problems of information sharing and identify verification which face commerce, communication, and many other aspects of human life. But it has yet to find its way into common use outside of tools targeted at highly technical users - with the one very notable exception of SSL encryption used for secure web browsing.

Before I can launch into this particular rant, however, an introduction to the subject is in order. Very few people understand asymmetric crypto (or even know what it is), despite its importance and the fact that they use it every time they make a purchase online.

Cryptography is the science (or, some might say, the art) of encryption - also known as ciphers or codes. That is: the transformation of human-readable content (like this post, or an email, or a phone number) into encoded data that is not readable, appearing instead as seemingly random series of letters and numbers. The recipient can decode the data and produce the original, human-readable content using a decryption key. Anyone who intercepts the data during its transfer - for example, stealing it out of the mail - will not be able to understand the contents.

If you’ve ever used a secret decoder ring, then you’ve worked with cryptography. These toys usually have a very simple scheme which maps letters to numbers, let’s say: A = 1, B = 2, C = 3 and so on. Using the scheme on the ring, you can encrypt the word “cat” into the numbers “3 1 20″. That series of digits doesn’t mean anything to most people (or if it does, it probably does not refer to a feline). But you could write these numbers on a piece of paper and mail it to your friend who also has the decoder ring, and they could decrypt it to using to ring to produce the original text.

This is called symmetric cryptography, because the same ring (or key, as we will call it henceforth) is used both to encrypt the message, and decrypt it on the other end.

The decoder ring algorithm described above is trivially easy to crack. With a large enough sample of encrypted data (a few paragraphs, such as an average letter or email), a code-breaker can use their knowledge of the statistical occurrences of letters in the english language, coupled with copious amounts of trail-and-error, to learn the code without ever acquiring a decoder ring.

There are, however, excellent symmetric key algorithms which are next to impossible for a code-breaker to crack, except by what is known as the “brute force method” - trying every possible key in sequential order, usually utilizing a very powerful computer.

Symmetric encryption has existed for thousands of years. Much more recent is the introduction of asymmetric encryption, also known as public key encryption. Invented about three decades ago, this type of cryptography uses two keys, one used to encrypt, and one used to decrypt.

At first glance this may not seem very useful. But consider the case of sending messages to multiple recipients. With symmetric keys, each decoder ring / key you give out greatly decreases the privacy of your future messages. If you give the same key to ten friends, that means that any message you send to one friend could (potentially) be intercepted by another friend and decrypted. Worse, they could take your message, modify it slightly and re-encode it using the key, and then send it along to its original recipient. That recipient would decode it and read the altered message, believing it to be the original as sent by you.

With asymmetric keys, one key is designated the public key - for giving out to recipients; and one is the private key, which is kept secret and given to no one. Your public key can be handed out freely. In fact, people often post them to their websites or make them available via key servers, like this one. (Remember that with symmetric cryptography, handing out the key publicly would effectively make your encryption worthless.)

So now if I want to send someone a private message, I’ll encrypt it using their public key. This produces a block of data that no one - not even me, person who encrypted it - can decrypt, except for the holder of the private key. In this way I can be certain that my message cannot be read by anyone but the intended recipient. You get all the benefits of standard symmetric encryption, but without having to worry about compromising your privacy by handing out the key.

So that’s one part of it. Amazingly enough, however, this is not the coolest part of public key crypto.

Consider encrypting some data the other way, using a private key as the encryption key. This would mean that only the public key can decrypt it. Does this seem like a pointless endeavor? It should - after all, my public key is public - meaning (potentially) anyone can access it, and therefore anyone can decrypt a message encrypted with it.

So, why encrypt with a private key? The answer: identify verification. Remember, only I have my private key. If I provide a block of data that can be decrypted with my public key, then it is certain that it was encrypted with my private key, i.e., by me and me alone. Therefore, the data can only have come from me.

This is what is known as a digital signature. Digital signatures are one of the most important practical technological breakthroughs of the 20th century, and we have only just begun to see its effect.

Digital signing is already supported by almost every major email client (with the notable exception of Outlook). The implementation is actually quite simple. With an email, you have a known block of text: the message body itself. The digital signature is then just be a copy of the message, encrypted with the author’s private key. The recipient’s email client decrypts that portion with the author’s public key, and compares it letter-for-letter with the unencrypted message. If they are identical, then it is certain that it was sent by the author and no one else, and that it was not modified in transit.

Now, consider legal documents such as contracts or checks. Handwritten signatures can easily be forged. Even if the signature is real, the document itself can easily be modified after the fact using a bit of digital editing, or even with some whiteout and a pair of scissors.

With a digital signature, the entire document is duplicated in the signature, thus guaranteeing that it is impossible to tamper with the contents after the fact. Any change to the contents will invalidate the signature, as the decrypted data will no longer match.

If you’ve made it this far, then: Congratulations! You now know more about cryptography than approximately 99.999% of the population. You are probably also starting to get an inkling of the immense potential of this technology - thus leaving you well-prepared to read Part 2.

4 comments per 'Asymmetric Key Cryptography: Part 1'

  1. Robert Earl Hazelett says:

    I enjoyed this lesson involving cryptography. Maybe that’s true because of your ability to clearly explain an idea or a point. You are a good writer.

    Keep up your efforts while I search for the rest of your essays. :^)

    Bob Hazelett

  2. keepsmile says:

    huhu i enjoyed this lesson too…

  3. cheery cindy says:

    nice lesson..thanx.. ;-)

  4. The Pageman says:

    I was just explaining this to my Junior college students to explain how secure 128-bit SSL is whenever it is used for e-commerce :)

Post a comment

Enter your comment (some HTML allowed)