How do you communicate with a website securely? How do you know you are communicating with the website you think you are? How do you sign a message such that the recipient can verify that it was sent by you?

The answer to all these questions lies in public key cryptography. This post will explain the basics of public key cryptography and how it is used to securely communicate with who you want to communicate with.

Public/Private Keys

You use a mathematical function to generate a pair of keys. One is called the private key, the other the public key.

Anything encrypted with the public key can only be decrypted with the corresponding private key, and vice versa.

+-----------------------------+   private key   +-----------+
| encrypted with public key   |   ---------->   | decrypted |
+-----------------------------+                 +-----------+

+-----------------------------+   public key    +-----------+
| encrypted with private key  |   ---------->   | decrypted |
+-----------------------------+                 +-----------+

Anything encrypted with the public key can only be decrypted with the corresponding private key, and vice versa.

Encrypting and Decrypting

Everyone or every server or every entity in some system that needs to communicate securely has a pair of keys. They keep their private key secret, and give their public key to anyone who wants to communicate with them.

When you want to send a message to someone, you encrypt it using their public key. Only they can decrypt it using their corresponding private key. Thus the message is secure, because anyone snooping on the communication can’t decrypt/understand the message content.

Similarly, when someone wants to send you a message, they encrypt it using your public key, and only you can decrypt it using your private key.

Signing

You can also use your private key to sign a message, such that anyone who gets the message can verify that it (the content) was indeed signed/sent by you.

To sign a message:

calculate the hash of the message
encrypt the hash with your private key

The encrypted hash is the signature of the message. When someone gets the message, they:

calculate the hash of the message
decrypt the signature using your public key
if the decrypted signature matches the hash of the message, then they know it was signed/sent by you

Notice there is a distinction between the message and the signature. The signature is the hash encrypted with a private key. The message is the actual content you want to send.

Sender:

+------------------+            +------------------+
|  hash            |    --->    |  encrypted(hash) |
|  message         |    *       |  message         |
+------------------+            +------------------+

*encrypted with sender's private key. 'encrypted(hash)' is known as the signature of the message

Receiver:

+------------------+            +------------------+
| encrypted(hash)  |    --->    |  hash <------+   |
| message          |    *       |  message <---|   |
+------------------+            +--------------|---+
                                               |
*decrypted with sender's public key            |
                                               |
                                    if "hash" = hash(message), then the message 
                                    was signed by someone who owns the private 
                                    key corresponding to the public key used to
                                    decrypt the signature

Authentication

Here is how you can verify that someone or something (say a server) is who they say they are:

the person, server, etc. claims to be the entity associated with a certain public key
you generate a random string, encrypt it with the public key, and send it to the entity
the entity decrypts the string using their private key, and sends it back to you
you verify that the string you sent and the string you received are the same

SSH uses this method to authenticate.

SSH Authentication

A lot of online services, like github allow you to authenticate via SSH. You generate a public/private key pair, and upload the public key to github using their website. When you want to push/pull from a github repo, github asks you to prove that you are who you say you are by sending you a randomly generated string that was encrypted with the public key you uploaded. You decrypt the string using your private key, and send it back to github. If the string you sent back is the same as the string github sent you, then github knows you are who you say you are, and it will allow the push/pull.

Any other service that allows you to authenticate via SSH will use the same method.

Certificates

A certificate is a message signed by someone trusted. The message contains a lot of information, but the most important piece is the public key of the thing that is certified. Other information is basically what it is certified for, what it owns, etc.

A certificate is created and signed by a “trusted authority”. You send a request to the authority, giving them your public key, and telling them what you are certified for or own. For example, I could say that I own google.com. The authority will first verify that you indeed own google.com and then once verified, it was create a certificate with the message “I certify that the public key of google.com is ". In addition to the message section, the certificate also contains the signature of the authority (as explained previously).

When you present this certificate to someone, they can verify that it is indeed signed by the authority (they know the public key of the trusted authority). If it is, then they can trust the content of the certificate. So if the verified certificate says this is google, then it is google.

HTTPS (TLS/SSL)

When you visit a website, you want to make sure that the server you are communicating with is the website it claims to be. You also want to make sure that the communication is secure (i.e. transmissions between you and the server are encrypted).

Here is how it works:

the server presents you with a certificate
you (the client) verify that the certificate is indeed signed by a trusted authority
you (the client) generate what is known as the “pre-master secret”, and encrypt it with the public key of the server (i.e. the public key in the certificate)
the server decrypts the pre-master secret using its private key
both the client and server use the pre-master secret to independently derive the same symmetric key they will use for all subsequent messages

Summary

Public key cryptography is used to securely communicate with someone or something. You can encrypt a message with someone’s public key such that only they can decrypt it with their private key. You can also sign a message with your private key such that anyone can verify that it was indeed signed by you. Certificates are used to verify that someone or something is who they say they are, according to some trusted authority. HTTPS uses public key cryptography as well as certificates to securely communicate with a server.

It is important to remember that securely communicating with someone or something entails:

Making sure that the person/thing is the holder of the public key they claim to be. This is done using “challenges” (i.e. the random string sent to the entity to decrypt with their private key and send back).
Making sure that the person/thing (public key) owns something or is verified to provide some service via a trusted authority. This is done via trusted authority signed certificates.
Making sure the communication itself between you and the entity is secure. This is done by encrypting all the messages exchanged between you and the entity. In the case of HTTPS, both you and the entity will derive a symmetric key and use that for encryption, however, I guess you could each just encrypt sent data with the other’s public key.

Thanks for stoppin by! Hopefully you had a fun read!