A High-level Overview of Modern Cryptography

Table of contents

Open Table of contents

Introduction

There are many different definitions of Cryptography but if we break down the core idea behind it it’s that of deriving procedures to protect protocols against malicious actors. Protocols in that context mean a set of steps that need to be carried out to achieve an outcome.

Such procedures can be further broken down into Cryptographic Primitives and Cryptographic Protocols. Primitives are the core building blocks such as Encryption, Key Exchange, Signatures, Hash Functions, etc. Protocols are more complex constructions such as the Signal Protocol that use Cryptographic Primitives behind the scenes.

The core properties Cryptographic Primitives and Protocols share are:

  1. Confidentiality: Protect Information (e.g. encrypting data)
  2. Authentication: Identify with whom we interact

Historical Cryptography

One of the simplest ways to implement cryptography is to utilize what’s called “security by obscurity”. This essentially means that the algorithm that makes up the cryptographic construction has to be kept secret to ensure security.

Some of us might remember our attempts at inventing encryption / decryption schemes when were kids where we removed vowels from words or added suffixes to obfuscate words to prevent the grown-ups from tapping into our conversations.

The main issue with such schemes that rely on “security by obscurity” is that they’re immediately broken once the inner workings are known. Sure, we can come up with a new scheme but it’s pretty expensive to do so anytime the old one is broken. Plus it’s really hard to invent new schemes that guarantee a certain level of security.

To get around this issue we could parameterize some aspects of the scheme so that we’re able to alter its behavior “from the outside”. Looking at the Caesar Cipher which is a substitution cipher that remaps characters of the alphabet to a shifted equivalent we could parameterize the number of left- or right-shifts that have to occur to derive the proper character remapping. We could, for example, say that we shift 3 characters to the right so that an A maps to a D, a B to an E, a C to an F, etc.

We can call such a parameter a key.

This brings us to the idea behind Kerckhoffs’s Principle: Rather than relying on the algorithm being hidden we should assume that it’ll eventually fall into the hands of our adversary. Our security should rely on the key we’re using with our scheme to be kept private. This way we can swap out keys if they’re compromised and don’t need to invent new schemes as their functionality gets known because it should be assumed that that knowledge is public information anyways.

Symmetric Cryptography

Symmetric Cryptography encompasses constructions that rely on a single key being used.

Symmetric encryption is an example in which a single key is used for both, the encryption- and decryption of data.

To outline how symmetric encryption works let’s say that we have a message m, a key k and two algorithms encrypt and decrypt. As per Kerckhoffs’s Principle only the key k is private knowledge.

encrypt turns the message m with the help of key k into a ciphertext c (“random noise”):

Encrypt(k,m)=cEncrypt(k, m) = c

decrypt does the reverse and turns the ciphertext c with the help of the key k into the message m:

Decrypt(k,c)=mDecrypt(k, c) = m

So to ensure that the scheme works we need to prove that:

Decrypt(k,Encrypt(k,m))=mDecrypt(k, Encrypt(k, m)) = m

Symmetric Cryptography is oftentimes also called ”Secret Key Cryptography“.

Symmetric Cryptography works great as long as both parties that use it agreed on the same key beforehand in a non-adversarial setting. But what if the only communication channel we have is one in which adversaries can eavesdrop?

That’s where Asymmetric Cryptography can help.

Asymmetric Cryptography

Asymmetric Cryptography defines constructions in which multiple keys are used for different functions. The most prominent example is that of public- and private key usage. While private keys should remain secret, public keys can be shared with anyone (even adversaries). We can therefore say that participants have an asymmetric view of the keys being used.

Asymmetric Cryptography is oftentimes also called ”Public Key Cryptography“.

Asymmetric Cryptography allows for the construction of different primitives:

Key Exchange

Using public- and private keys we can derive a protocol to compute a shared secret among two parties over an insecure communication channel (let’s call them Alice and Bob).

For the sake of argument let’s assume that a is Alice’s private key and the multiplication of a with a publicly known value we call G is her public key:

skAlice=apkAlice=aGs_kAlice = a\\p_kAlice = aG

Bob does the same thing. He has a secret value b which is his secret key and he multiplies this value with the publicly known value G to derive his public key:

skBob=bpkBob=bGs_kBob = b\\p_kBob = bG

Let’s furthermore assume that extracting a form aG (or b from bG) is computationally very expensive (i.e. it takes a very, very long time) and therefore considered “infeasible”.

If Alice now sends her public key (aG) to Bob and Bob sends his public key (bG) to Alice they can both multiply such keys with their private keys to get the same, shared secret:

secret=(aG)b=(bG)a=abGsecret = (aG)b = (bG)a = abG

Note that this works even if the public keys are sent via an insecure communication channel as the only information an eavesdropper can learn is aG or bG which is useless as it’s computationally infeasible to extract a or b as per our definition above.

The steps outlined here are how the Diffie-Hellmann Key Exchange work, one of the very first asymmetric cryptography protocols.

Aside: The attentive reader might be thinking how we can ensure that we got the public key from the “correct” Alice or Bob. As outlined above, the protocol is susceptible to a man-in-the-middle (MITM) attack. Solutions to that issue will be discussed in another Blog Post.

Asymmetric Encryption

Asymmetric encryption also allows for the construction of an encryption scheme in which different keys are used for encryption and decryption.

The earliest and most prominent example is the RSA Cryptosystem. Using RSA, a participant generates a set of two keys, a public key that can be shared publicly and a private key that should be kept secret.

Any participant that wants to send an encrypted message to another participant can use their public key to do so. A message encrypted under the public key can only be decrypted via the corresponding private key.

To show how asymmetric encryption works let’s say that we have a message m, a public key pk, a private key sk and two algorithms encrypt and decrypt.

encrypt turns the message m with the help of public key pk into a ciphertext c (“random noise”):

Encrypt(pk,m)=cEncrypt(pk, m) = c

decrypt does the reverse and turns the ciphertext c with the help of the private key sk into the message m:

Decrypt(sk,c)=mDecrypt(sk, c) = m

To ensure that the scheme works we need to prove that:

Decrypt(sk,Encrypt(pk,m))=mDecrypt(sk, Encrypt(pk, m)) = m

Digital Signature

Asymmetric Cryptography can also be used to digitally sign and verify documents.

A private key is used to sign a payload while the public key can be used by anyone with access to it to ensure that the signature is valid.

Digital Signatures have a huge advantage compared to handwritten signatures in that they’re “unforgeable” and “message dependent” which means that the signature varies anytime a payload is signed.

The RSA Cryptosystem is one of the earliest constructions that supports digital signatures. Using RSA, a participant generates a set of two keys, a public key that can be shared publicly and a private key that should be kept secret.

To digitally sign a payload the participant uses her private key and the message (“payload”) to create the signature. To validate the signed message anyone with access to the public key and the signature can verify whether the signature is valid.

To see how digital signatures work, let’s say that we have a message (“payload”) m, we want to sign, a public key pk, a private key sk as well as two algorithms sign and verify.

sign takes the message m and creates a signature s with the help of the private key sk:

Sign(sk,m)=sSign(sk, m) = s

verify validates whether the signature s is valid by using the public key pk. Its output is either true or false:

Verify(pk,s)=true∣falseVerify(pk, s) = true|false

Classifications

We’ve already talked about Historical, Symmetric and Asymmetric Cryptography. Are there more classifications we should consider?

Generally speaking, there are endless ways to classify cryptographic primitives and protocols and there’s clearly no right or wrong way of doing so.

What you’ll see often in the literature is the separation between Symmetric- and Asymmetric Cryptography.

However, there’s another interesting lens to look through…

As it turns out, most symmetric schemes utilize heuristics to derive their security, i.e. they rely on experts analyzing the soundness and robustness via observations and statistical analysis. In contrast, most asymmetric schemes rely on hard mathematical problems to derive their security. Methods relying on heuristics are usually faster to execute compared to math-heavy approaches.

With that in mind, we could categorize cryptographic constructions into Heuristic-based and Mathematical-based.

To sum things up: Symmetric Cryptography, that’s oftentimes heuristic-based is usually fast to execute whereas Asymmetric Cryptography, that’s rooted in hard mathematical problems is usually slower to execute.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.