I can only really remember honestly enjoying one maths lesson in my life.  It was spread over a number of lectures as part of my degree course at Edinburgh University and taught us all how RSA Public Key cryptography actually works.  Now, I’ve long since forgotten the finer details and I don’t pretend to be a cryptographer, but I thought it might useful if I gave a layman’s guide to the basics of Public Key cryptography.

Why don’t we just use a Password?

Let’s assume that we have two people who would like to communicate privately.  To keep with tradition, lets call them Alice and Bob.  Traditionally, we’d suggest that Alice should encrypt a message using a secret password; send the encrypted message to Bob; and then Bob uses the same secret password to decrypt the message.  When Bob wants to reply to Alice, he performs the same process, encrypting his message with the same secret password.

We call this symmetric cryptography because both the sender and receiver need the same information.  Both of them can encrypt and decrypt messages using the password.  There’s no way to distinguish between the two on the basis of what information they have or how they encrypt their messages.  This leads us to two critical problems:

  • How does Alice tell Bob what the secret password is without letting anyone else know?  After all, if she has a secure way to share the password, well, why not just use that same communication medium to send the message and skip all this encryption stuff?
  • What if a third person, Chuck, intercepts the password unbeknown to Alice or Bob?  Well, Chuck could cause all sorts of trouble.  He could theoretically read any of the encrypted messages passed between Alice and Bob.  Or, if he really wanted to, he could send his own encrypted messages to either party, pretending to be Alice or Bob.

So, maybe we need a Better Way…

Public Key Cryptography

Public Key cryptography relies on some fancy maths to get round some of the problems inherit with the traditional shared-secret approach.  Rather than a shared password, everyone has two keys; a Public Key and a Private Key.  Anything encrypted with the Public key can only be decrypted by the corresponding Private Key, and likewise, anything encrypted by a Private Key can only be decrypted by the corresponding Public Key.  And, importantly, it must be computationally infeasible to guess one key given the other.  Like I said, some very clever maths going on there and, that’s what we spent several hours learning at the lecture I opened this post with.

The point about it being computationally infeasible to work out what either key might be given the other is more important that you might immediately realise.  The whole concept behind Public Key cryptography is that you keep our Private Key locked away and never share it with anyone.  In fact, you probably want to use a traditional symmetric cryptography to encrypt your Private Key with a secret password that only you know so that only you can use the Private Key.  Meanwhile, you can openly communicate our Public Key to everyone; post it on your website, put it in your email signature or register it with public key libraries.

So, if you want to send a secret message to someone, you would encrypt it using their Public Key, safe in the knowledge that only the corresponding Private Key is able to decrypt it.  Likewise, if you want to give the recipient some reassurance that the message came from you, then you could re-encrypt the resulting cipher text with your Private Key.  Anyone with your Public Key can decrypt the resulting message, but only you could have created that message.

How does Public Key Cryptography work?

Let’s go back to our example, but this time lets assume that Alice and Bob have both created their own Public and Private key pairs.  Likewise, lets assume that they’ve both published their Public Keys to a key-exchange library – meaning that Chuck also has both Alice and Bob’s Public Key too.

If Alice wants to send a message to Bob, she first looks up Bob’s Public key from library.  She encrypts her message using Bob’s Public Key.  She can then pass the message on to Bob, safe in the knowledge that only Bob’s Private Key (which only Bob has) can decrypt the message.  Now, this means that even if Chuck does intercept the message, there’s nothing he can do, because he only has Bob’s Public Key and not Bob’s Private Key.  Poor Chuck.

When Bob receives Alice’s message, he uses his (very well protected) Private Key to decrypt the message that Alice originally encrypted using his Public Key.  To Reply, Bob repeats the same process that Alice followed, using Alice’s Public Key (that everyone has) to encrypt a message so that only Alice’s Private Key can decrypt it.

So, we’ve demonstrated that Alice and Bob can now communicate privately without the need to share any secret passwords.  In fact, Public Key cryptography actually relies on Alice and Bob having some method of openly sharing their Public Keys.

Dealing with Impostors

Well, if you’ve been paying attention then you’re probably thinking “that’s great, but Chuck could still impersonate either Alice or Bob”.  You’re quite right!  But, by using the same principles of Public and Private keys, we can also digitally “sign” a message to prove that it came from a particular person.

So, Alice and Bob have both created their own Public and Private key pairs; they’ve shared the Public Keys to everyone, including Chuck who would like to get up to mischief.  Alice wants to send a message (M) to Bob and she wants to prove to Bob that it came from her and not Chuck.

Alice begins by encrypting her message firstly using her Private Key.  She then encrypts it a second time using Bob’s Public Key.  The message has been encrypted twice: the first encryption guarantees that the message is from Alice (because only she has access to her Private Key); and the second encryption guarantees that no one but Bob can read it (because only Bob’s Private Key can decrypt it).

When Bob receives the message, he firstly decrypts the message using his Private Key.  He then decrypts the message using Alice’s Public Key.  If this works, then it means the message must have been encrypted using Alice’s Private Key, which only Alice has access to.

So, if Chuck was to intercept the message, he wouldn’t be able to decrypt it because other than Bob, nobody has access to Bob’s Private Key.  Likewise, he can’t pretend to be Alice and send a message to Bob because only Alice can encrypt messages using Alice’s Private Key.

Did you follow that okay?  Don’t worry if you’re scratching your head – just go back over it again, it sometimes just takes a while to get your head around asymmetric cryptography if you’ve been used to shared secret passwords for a long time.

Man in the Middle

Of course, nothing is perfect; as I stated earlier, Public Key authentication relies on Alice and Bob being able to share public keys.  However, all parties need to be confident that they have the right public keys.

As before, let’s assume that Alice wants to send a private message to Bob and they haven’t already exchanged Public Keys.  However, let’s also assume that Chuck is able to intercept communications between the two and possibly deliver false messages.

Alice firstly asks Bob for his public key.  If Bob sends his public key to Alice, but Chuck is able to intercept it, a man-in-the-middle attack can begin.  Chuck sends a forged message to Alice that claims to be from Bob, but instead includes Chuck's public key.

Alice, believing this public key to be Bob's, encrypts her message with Chuck's key and sends the encrypted message back to Bob. Chuck again intercepts, decrypts the message using his (Chuck) Private Key, possibly alters the messages, and re-encrypts it using the public key that Bob originally sent to Alice.  When Bob receives the newly encrypted message, he believes it came from Alice.

Thankfully, there are various solutions to the problem of verifying the ownership of a Public Key.  It’s a topic in its own right, but Public Key Infrastructure (PKI) and Web Of Trust (WoT) are solutions that leverage both technology and human supervision to bind public keys with user identities with a degree of confidence.  Lets discuss that another day!