Asymmetric Cryptography – Introduction

In everyday life – private and business – often the problem occurs where you want to send a secret message over a public, unsecure channel. Such a message could be an email, a binary image for the latest firmware of your device or even a video conference with your business partner. A good example of an unsecure channel could be the internet but also a USB stick sent via postal service. Several mechanisms are available to solve this problem, some of which I want to elaborate on in this blog series.
In this post I will introduce you to asymmetric cryptography by showing the drawbacks of symmetric cryptography and how asymmetric cryptography can solve these problems. I will then dive deeper into the (mathematical) details of the subject.

Symmetric Cryptography

A simple method to transfer a message securely is to use symmetric encryption. The sender encrypts a message with a secret key and sends the resulting ciphertext to a recipient. The latter then decrypts the message using the same key (or a copy thereof).

Example

Bob wants to sell his vintage Ferrari. To get a good price he performs a secret auction where every participant sends him a proposed value of the car from which he then chooses the highest bidder. Alice is interested in buying the vehicle and wants to tell Bob how much she intends to bid. To prevent Charlie from reading her bid (and increase his bid accordingly) she encrypts her message to Bob («I will bid 1.2 million dollars.«) with a key (098F6BCD46…) she shared previously with Bob. To compute the ciphertext she chooses the AES algorithm in CBC mode. She then sends the resulting ciphertext (101F4C012B…) to Bob.

Without knowing the secret key Charlie has no way to read Alice’s bid. Bob now decrypts the message by applying the shared key on the received message by using the same algorithm. The result is again the message that Alice originally wrote.

Key Agreement

The problem with this method is that Alice and Bob have to arrange a way to exchange their shared key. Of course they could meet in advance and agree on a shared key, which is impractical for most common cases. If Alice was to send the shared secret over an unsecure channel to Bob and Charlie was able to intercept it, he could not only read the messages Alice and Bob exchange but also tamper with them. Therefore Alice and Bob will have a shared key but the channel they want to set up with it will neither be confidential nor authentic and Charlie could comfortably play Man-in-the-middle.

Asymmetric Cryptography

This is where asymmetric cryptography comes to the rescue. With asymmetric cryptography there is no shared secret but a key pair one half of which is called the private key and the other half is called the public key (hence the widely used synonym «public key cryptography»). The public key is shared with any involved parties (or even made generally publicly available) whereas the private key is kept secret. Unlike using symmetric cryptography the private key is not even shared between trusted parties; each party will have their own key pair. Using certain mathematical properties (the details of which I will cover in the next installment of this series) it is computationally easy to derive the public counterpart of a certain private key. On the other hand it is very hard to compute the original private key from a known public key. The respective key pairs of two parties can now be used to derive a commonly known secret value, which then can be used as a key for symmetric encryption/decryption.

Encryption & Digital Signatures

Asymmetric cryptography can also be used directly to encrypt messages. To do this the sender encrypts the message with the recipient’s public key. This is done in a way that only the owner of the corresponding private key is able to decrypt the message. With this method, if Alice wants to send a secret message to Bob, she only needs to obtain his public key in order to do so. No preliminary key agreement is required. Unfortunately, now Bob does not know that the message he received has really been sent by Alice. Since his public key is available to anyone, Charlie could have used it to send an encrypted message to Bob in Alice’s name. To avoid this problem Alice can use her private key to sign the message (using a so-called Digital Signature Algorithm). Bob can then use Alice’s public key to verify that the message was indeed sent by her.

In the next part of this series, I will go into more detail about how asymmetric cryptography works on a mathematical level.