Whenever I've tried to look up cryptography explanations online, I'm usually greeted with examples that (IMO) are a bit too focused on the implementation details. The high-level concepts just seem to get lost in all those details.

So I wanted to write a primer that focuses only on the high level, abstract concepts.

The basic idea you have to start with is this:

Any message can be converted to a number, and any number can be converted to a message, via an encoding/decoding scheme, so encrypting and decrypting messages is entirely a numerical operation.^[1]

Thus, cryptography is all about a special class of numerical functions.

In fact, the basics of cryptography can be boiled down to five numerical functions, which we call: keygen, encrypt, decrypt, sign, and verify.

keygenkeygen

keygen() -> (pk, sk)

keygen uses randomness to create two numbers, a public key, pk, and a secret key sk.

The public key is meant to be shared publicly, and its purpose is to allow anyone to send you a secret message.

The secret key is meant to be kept private. It lets you unlock the secret messages that others have sent you.

Since the public key is meant to be shared, a security requirement is that an attacker cannot easily figure out sk, even if they have access to pk.^[2]

encryptencrypt

encrypt(m, pk) -> c

encrypt takes two inputs:

• A message m (which remember, is just a number)
• A public key pk (which is also just a number)

It outputs another number, c, which we call a "ciphertext".

Anyone who has your public key can now encrypt a message and send it to you in the form of a ciphertext.

An important requirement here is that an attacker cannot figure out m, even if they have access to c and pk. That is, they cannot decipher the message with just the ciphertext and the public key. They need the secret key to do so.

decryptdecrypt

decrypt(c, sk) -> m

decrypt takes two inputs:

• A ciphertext, c (also just a number)
• A secret key sk (also just a number)

It outputs a number, m, which should be the original message.

A simple requirement here is simply that any message encrypted with pk is recoverable by sk, if (pk, sk) were generated from the same keygen function. Mathematically, it is equivalent to requiring: decrypt( encrypt(m, pk), sk) = m

Another requirement is that an attacker can't simply decrypt the message by guessing at keys. This requires the set of possible keys to be very large, and the keygen step to be unpredictable. This means that if you used a small keyspace, or a predictable method for keygen (such as a computer random number generator with a common seed like 42), then your secret key could be easily guessed.

We now know how keygen, encrypt, and decrypt are used to send and receive secret messages. But how can I prove to someone that the message came from me? That's where sign and verify come in, using the same public and private key pair (pk, sk) that we already talked about.

signsign

sign(m, sk) -> sig

sign takes two inputs:

• A message, m (which could also be a ciphertext)
• A secret key sk

It outputs a number, sig, which can be thought of as a signature.

Now, if you want to send someone a message m and prove that it's from you, you would send them (m, sig): the message along with your signature.

verifyverify

verify(m, sig, pk) -> true/false

verify takes three inputs:

• A message, m, which could also be a ciphertext
• A signature sig (just a number)
• A public key pk

It outputs a simple true/false, indicating whether the signature was indeed produced by secret key sk.

The correctness requirement is that verify(m, sign(m, sk), pk) = true for any matching (pk, sk) and false otherwise. That is, signatures produced by sk resolve to true when verified with pk.

The security requirement is that an attacker could not have produced a valid signature for m if they only know pk. That is, they can't guess the correct sig which would cause verify(m, sig, pk) to resolve to true.

ConclusionConclusion

So, that's it. Cryptography revolves around these five numerical operations: keygen, encrypt, decrypt, sign, and verify. The trick is finding functions which satisfy the correctness and security requirements.

Notably, this requires the existence of "trapdoor" functions, which are easy to compute in one direction but hard to compute in the other direction. For example, if the relationship between pk and sk is deterministically given by $pk=f(sk)$, then $f(sk)$ needs to be easy to compute, but the inverse $f^{-1}(pk)$ must be prohibitively expensive to compute.

An example of such a trapdoor function is prime factorization, which is used in RSA cryptography. The public key is just the product of two huge prime numbers and the secret key is those two primes. If you know the two primes, computing the public key is easy. But if you only know the public key, factoring this huge number into the two primes is very difficult.

Bitcoin uses a trapdoor function based on elliptic curve cryptography, which is just another way to give us the ability to derive public keys which can't easily be reversed to get the private key. Bitcoin uses the sign and verify functions to authorize transactions: you sign a transaction with your secret key to prove you control the funds, and the network verifies the signature using your public key.

1. Note that the transforming a message to a number (encoding), and transforming a number to a message (decoding), is not in itself cryptography. Anyone can encode or decode a message if they know the scheme. Cryptography is about how to send a message in such a way that only the intended recipient is able to read it, even if an attacker knows the scheme. ↩

2. There's also a simpler form of cryptography that generates only a secret key with no public key. That's called "symmetric cryptography". In that case, you would have to find a way to share sk secretly with the people you want to communicate privately with. ↩