If you just read my previous post on Symmetric Cryptography, you may be convinced that our encryption algorithms are secure if we use the same key, but are now stuck wondering how these keys are shared in the first place. That’s where Asymmetric Cryptography comes in.

In Asymmetric Cryptography, our algorithms are based on mathematics rather than logical operations. The idea is that we create mathematical problems so hard to solve that they’re not worth solving.

Asymmetric Cryptography uses two keys - a public key and a private key, and these keys are such that it is computationally infeasible to derive the private key from the public key. In this blog post, I’m going to show you how two people can exchange a shared secret over an insecure channel just by sharing each other’s public key. Sounds like magic right? Read on.

Diffie-Hellman

Diffie-Hellman Key Exchange (DH-KEX) is the standard, most-common key exchange mechanism.

Imagine that you’re Alice and I’m Bob and we want to have a private conversation over a public channel. The first thing you and I do is publically agree on a set of base parameters. For example, we choose a number g called a generator, and a very large prime number p1.

To illustrate this process, we will be using the hazmat module, part of the cryptography package in Python2.

from cryptography.hazmat.primitives.asymmetric import dh

base_parameters = dh.generate_parameters(generator=2, key_size=2048)

We’re each then going to create our own private key between 1 and p. Note that we never share our private keys with each other.

Your private key:

alice_private_key = base_parameters.generate_private_key()

My private key:

bob_private_key = base_parameters.generate_private_key()

We then take our private keys and combine them with g to generate our own unique public keys.

The DHPrivateKey class has a method called public_key() that does just that:

alice_public_key = alice_private_key.public_key()

bob_public_key = bob_private_key.public_key()

So now we each have 1 private key and 1 public key. We send each other our public keys over the insecure public channel, right under everyone’s noses.

Using each other’s public key and our own secret private key, we can generate our shared secret.

Your shared secret:

shared_secret = alice_private_key.exchange(bob_public_key)

My shared secret:

shared_secret = bob_private_key.exchange(alice_public_key)

The magic here is that our shared secrets are in fact one and the same, and just between you and me. Nobody else eavesdropping on our conversation could have used our public keys to generate the same secret.

In DH-KEX, we usually call this shared secret a Pre-Master Secret.

We can then put our secret through a Hash-Key Derivation Function (HKDF) to derive a fixed-length key. I’ll talk more about hash functions in a future blog post, but just for your reference, doing that may look something like this:

from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

derived_key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'hkdf-example',
).derive(shared_secret)

All of our future messages through the insecure public channel could now be encrypted with a symmetric encryption algorithm like AES using the derived_key above.

Elliptic Curves

Elliptic curves are a drop-in mathematical replacement for the modular arithmetic of DH-KEX. In the context of Diffie-Hellman, elliptic curves are often abbreviated as ECDH (i.e. Elliptic Curve variant of Diffie-Hellman).

The benefit of using ECDH is that we need much shorter keys to achieve the same level of security3; which is important because as computational power increases, so must our key length.

The following table illustrates that point in greater detail:

Symmetric Diffie-Hellman Elliptic Curve DH:EC
80 1024 160 6:1
112 2048 224 9:1
128 3072 256 12:1
192 7680 384 20:1
256 15360 512 30:1

So suppose you want 128 bits of security (e.g. AES-128). That means an attacker would have to try 2^128 different encryptions to try and brute-force your key. That level of security requires a 3072-bit DH key. With ECDH, we only require a 256-bit key to achieve the same level of security; making it much faster and easier to compute than regular DH.

Ephemeral Mode

In addition to having a robust key, it’s best practice to perform a new key-exchange every time we start a new conversation over an insecure public channel.

Say you visit a website and perform a DH-KEX to create a key for encryption. If you were to continue using that same key for future conversations, and a future attacker was able to compromise it, then theoretically, not only would they be able to decrypt your future conversations, but they would also be able to go back and decrypt all of your previous conversations (for as long as you were using that same key).

ECDH Ephemeral (ECDHE) ensures that we perform a new key-exchange every time we start a conversation; so that if an attacker compromises our session key, only that session is affected. Another term for this is Perfect Forward Secrecy (PFS).

To ensure PFS, websites using HTTPS perform a key-exchange everytime you visit, messaging apps like Signal perform a key-exchange everytime you send a message, and encrypted calling apps perform a key-exchange everytime you place a phone call. Because of this, your phone is constantly performing key-exchanges; it’s even likely performing one right now.

So we now have a way of exchanging keys over a public channel, but how do I know for sure that I just exchanged keys with Alice, and how do you know for sure that you just exchanged keys with Bob? The truth is that neither of us would have had any idea if a man in the middle just exchanged keys with both of us. If that was the case, all of our fancy math was for nothing because the man in the middle can now intercept all of our messages.

We need a way to authenticate the person on the other end and that’s where public key cryptography comes into play.

RSA

Rivest-Shamir-Adleman (RSA) is currently the most common method for public key cryptography4.

With RSA, we (again) need to generate a public-private key pair. This time our public key is generated from two numbers, e and n, where e is a chosen small number (usually 3 or 65537) while n is a very large randomly generated semi-prime number (usually 2048 or 4096 bits). Our private key is then calculated from e and n.

Generating the public and private keys is a relatively time-consuming process in RSA and is not meant to be performed often.

Recall that with DH-KEX, much of the work was in the key-exchange itself. With RSA, much of the work is in generating the key pair; the encryption/authentication comes later.

One of the interesting things about RSA is that the keys are completely reversible, meaning that we can encrypt our messages with our public key and decrypt with our private key, or we can do the opposite - encrypt with our private key and decrypt with our public key.

This leads to two very different use-cases: encryption and digital signatures.

Encryption

Say we’re in a group chat with some friends, and I paste in my RSA public key. You could go and use my public key to encrypt a message (with no knowledge of the private key) and come back and paste the ciphertext into the group chat. I would then be able to decrypt the ciphertext back into plaintext, but none of our friends would.

Likewise, we can use RSA to send encrypted data to a server (prominent before the days of TLS).

Say you visit a website and obtain its public key (e.g. certificate). You could then encrypt data sent to that website using its RSA public key and Optimal Asymmetric Encryption Padding (OAEP)5. The website would then be able to decrypt the data using its private key.

Side note: This concept of taking someone’s public key and using it to encrypt data that only they themselves can then decrypt is also how protocols like Pretty Good Privacy (PGP) work.

Digital Signatures

The most important use-case for RSA, however, is for digital signatures.

Say you have Bob’s public key and you want to verify that the person you are sending messages to is indeed Bob. You could send a message to Bob and tell him to encrypt it with his private key and send back the ciphertext. You could then decrypt the ciphertext with Bob’s public key and check that it reveals the original message. If the messages match, you will have verified Bob’s identity.

Likewise, we can send a message to a server as a challenge. The server then hashes and encrypts the message using its private key to create a digital signature6. We can then decrypt the signature with the server’s public key and see if the messages match up.

DSA

Digital Signature Algorithm (DSA) is an alternative to RSA for digital signatures, but has not been as prominent for historical reasons.

DSA acts a lot like RSA but uses Diffie-Hellman-style mathematics, and that allows us to substitute in elliptic curves; these Elliptic Curve variants of DSA (ECDSA) are being widely adopted thanks to efficient key size and are likely to overtake RSA in prominence in the near future.



  1. In the real world we would typically use predefined standard base parameters.

    For example, instead of using a completely random prime number, we would typically use a prime number that has been tested and shown to be safe.

    The downside of using standard base parameters is that it’s theoretically possible that they can be made vulnerable by a coordinated effort to compromise them. One such effort by the NSA successfully weakened a DH generator and prime called Oakley Group 2. The vulnerability known as logjam could then be used in downgrade attacks on TLS which affected a lot of VPN traffic (downgrading cipher suites in TLS was possible prior to version 1.3). ↩

  2. We wouldn’t normally code our own DH-KEX like we’ve done here; most languages have higher-level library functions that handle these operations for us, making them more efficient and less prone to human error. ↩

  3. For the same reason we use standard base parameters in DH-KEX1, we typically use standard elliptic curves in ECDH like X25519 and P-256. ↩

  4. While it’s true that RSA is currently the most common method for public key crypography, it’s likely to be superceded by elliptic curve algorithms in the near future ↩

  5. RSA doesn’t really work well if the message is too small. OAEP takes a padding scheme and hash function and creates a nice long block which could then be encrypted using RSA. The added benefit of a padding scheme is that it adds a bit of randomization to the ciphertext so you don’t run into the AES-ECB issue. ↩

  6. The recommended padding scheme for signatures is PSS. ↩