Asymmetric key cryptography

This is a sapling 🌱 post and will be updated.

Introduction

This is a note I wrote for my own understanding of how the asymmetric key cryptography is used by stuff we use daily, such as https, ssh, pgp etc. The intent of the note is to get a sort of big picture overview of the methods.

This note relies a lot on the basic understanding of asymmetric key cryptography. “The Code Book” by Simon Singh is a really good book for this - I enjoyed reading it and it gave me a very good idea of the problems with symmetric key encryption, how people dealt with it historically and how asymmetric key cryptography changed the rules of the game completely. Anyway, I totally recommend reading the book. Till then, here is a video from a channel I like that provides a good understanding of public key cryptography.

The key concept, that both the book and the video explains, is that asymmetric key cryptography is based on generation of a set of two keys (a key-pair) - the public key and the private key. Using this, two actions can be done:

1. Encryption: When a message is encrypted by a public key, it can only be decrypted by the private key. As long as only I have my private key, everybody else can send me encrypted messages using my public key, and only I can decrypt it. So everybody will be able to send me confidential messages.
2. Signing: I can encrypt something with my private key and everybody will be able to decrypt it with my public key. Since only I can encrypt a message with my private key, this proves my authenticity as no one else other than me have my private key. Encrypting a message with my private key hence becomes my digital signature.

So, I can do two things when I am sending someone an email. I can encrypt part of the message, like my signature, with my private key. This ensures that the recipient knows it is me that send the email. Then I encrypt the whole message with the recipients public key. So when the recipient receives the email, they alone can decrypt it using their private key, and then verify my signature using my public key. It is wild that two people who haven’t physically met can actually send completely encrypted messages and verify it came from the right person! No wonder encryption and signing form the basis of the modern encryption methods on the internet.

The big caveat is that of identity impersonation. There is no guarantee that the person claiming to be someone is actually that person. That is, someone could easily generate tons of public-private key pairs and put out the public keys claiming to be different people. How can one verify that the one claiming to own a public-private key pair is actually that person?

The solution is to have a method of trusting the public key of a person. This can be solved in many ways, and that is what different methods below achieve.

HTTPS (and SSL)

For HTTPS, the problem of trust is solved by having a trusted authority. These authorities are assumed to be trusted and their public keys are often packaged with the browser (Google trust services, Internet Security Research Group etc.). Trust originates from these sources and if a public key contains the signature of one of these sources, they are deemed verified by the trusted sources. This is what server certificates are.

When contacting a domain, each server provides a certificate. This certificate is issued by the trusted source (or a trusted source of a trusted source) and contains the public key of the server hosting the domain and some metadata such as domain name, validity of the certificate, encryption algorithm used etc.¹ It also has a signature encrypted by the private key of the trusted source and some safety checks such as hashes² to ensure the certificate files have not been tampered with.³

Once the certificate is verified, a symmetric key is sent to the server that is used to encrypt all further communication.⁴ This way, every session can have different keys allowing the communication between servers to be secure.

SSH with public keys (secure shell)

For SSH, the problem of trust is solved manually. That is, you add the public key of the client computer manually to the server and you manually verify the public key of the server computer. This is the classic example of the asymmetric cipher. The limitation is that you need to know the public key of the server. Then you (or the admin) will have to manually copy your public key into the server. This limitation does not allow easy scalability but ensures authenticity for a small number of connections (which is generally the case with standard SSH).

GPG and PGP

(to be updated)

Signal protocol

(to be updated)

Encryption algorithms

(to be updated)

Footnotes

Footnotes

1. The certificates can be easily seen in Mozilla Firefox by clicking the padlock symbol → connection secure → More information → view certificate. All the metadata associated with the certificate is displayed and the public key can be downloaded. I assume this is similar for other browsers. ↩

2. Hashes are super cool! They are basically compression algorithms that take a large string and make it into a smaller one. What is cool is the uniqueness of hashes - that is, if a particular large string gives you one hash and you modify just one character, the new hash will be different! So if a certificate (or a file) claims to have a particular hash and you compute its hash and find it different, something is different about the certificate (or the file) and cannot be trusted. So you can verify if things like certificates are the same by just having hashes. ↩

3. From what I understand, the signature itself is just a hash of the certificate generated by the trusted source and encrypted using its private key (please do correct me in case my understanding is wrong). By decrypting the signature with the public key of the trusted source, the hash of the certificate generated by source is obtained. This can be compared with the certificate sent by the server. This ensures that the certificate created by the source has not been tampered with. I find this very elegant! ↩

4. My understanding comes from this stackoverflow page, this youtube video and this cool github page. ↩