What are encryption keys and how do they work? 🔐

Written after my first look into the world of crypto, more knowledge always welcome.

• What is a ?key??
• Symmetric-key encryption
• Diffie?Hellman?Merkle key exchange
• Asymmetrical-key algorithms
• RSA algorithm for public/private keys
• Forward secrecy

? What is a ?key??

In cryptography a ?key? is a piece of information used in combination with an algorithm (a ?cipher?) to transform plaintext into ciphertext (encryption) and vice versa (decryption).

A cipher can be ?reciprocal? if it is used for both encryption and decryption, or ?non-reciprocal? if a transformation to the key is required when using it in reverse.

Non-reciprocal cipher

A simple Caesar cipher transforms each letter of a plaintext message by shifting it a set number of places in a set direction along the basic 26 character Latin alphabet. The encryption and decryption here is not reciprocal, the key must be transformed (-3 to +3) to alter the direction of the shift when moving between encryption and decryption.

Caesar cipher with a left shift of three

Reciprocal cipher

ROT13 (rotate 13) is a specific implementation of the Caesar cipher where the shift is 13 places. Due to the basic Latin alphabet being 26 characters long this means that the direction of the shift does not matter, the result is the same in either direction. They key (13) can be used without transformation.

ROT13, where a shift of 13 results in a reciprocal cipher

Symmetric-key encryption

Symmetric-key algorithms use the same keys for both encryption and decryption. The keys may be identical or there may be a simple transformation to switch between the two states. The Caesar and ROT13 ciphers above both use a symmetric-key.

The key acts as a shared secret between two (or more) parties that can be used to send private information that cannot be read by anyone without a copy of the key.

Symmetric-key usage

As seen above, Alice and Bob share the same secret key. Alice can use the key to encrypt any message before passing it over a public channel. Here prying eyes can only see the result of the encryption, but do not know the method to decrypt it. Once Bob receives the message it can be decrypted using Bob?s copy of the key, returning it to plaintext.

The main drawback here is the chicken and egg problem of sharing the secret key. Without a secure channel the key cannot be shared, but without the key no secure channel can be created. In times past this meant meeting in the real to swap a physical copy of the key, the only way to secure against anyone listening in. However, in 1976 a new method was published, allowing this to be done securely online.

Diffie-Hellman-Merkle key exchange

This method allows two parties to remotely establish a shared secret (a key in our case) over an assumed insecure channel. This key can then be used in subsequent communications along with a symmetric-key algorithm.

Colours are generally used instead of numbers when explaining this, due to the correlation of undoing the mathematical operations being used to the complexity of knowing which two colours where mixed to create a new, third, colour.

Diffie-Hellman-Merkle protocol to establish a shared secret key

Alice and Bob each start with their own, private, values R and G, as well as a public common value Y. Alice uses Y along with her private value to create RY, and Bob GY. These are publicly shared. This is safe, as it is extremely computationally difficult to determine the exact private values from these new values. Alice can then use Bob?s new public combination along with her private value to create RGY, and importantly Bob can use Alice?s new public combination to create the exact same RGY value. They now have a shared secret they can use to encrypt future messages and know the other can decrypt them when received.

A main security flaw in this protocol is the inability to verify the authenticity of the other party while setting up this shared secret. It is assumed you are talking to a trusted other party. This leaves the protocol open to a ?man-in-the-middle? attack by someone listening in from the start of the exchange.

Eve performing a man-in-the-middle attack

Above it can be seen how the Eve effectively eavesdrops and intercepts the exchange to set themselves up in the position to read any message shared between Alice and Bob. Eve can receive a message from Alice, decrypt it using their shared secret key, read it, then re-encrypt it using the key Eve shares with Bob. When Bob receives the message it can be decrypted using his secret key, which he incorrectly assumes he shares with Alice.

We will come back to Diffie-Hellman-Merkle later, but now will look at solving this vulnerability using public-private key pairs.

Asymmetrical-key algorithms

Also known as public key cryptography, asymmetrical-key algorithms use a pair of keys for every party: public keys which are published openly, and private keys, which are never revealed. You may have seen this if you?ve set up ?ssh? (secure shell) login in your terminal before.

This accomplishes two things: encryption/decryption between parties, and authentication of a message?s sender.

Generation of the key pair

Key pair generation

This will be covered in greater detail when looking at RSA later on. Simply put each party, say Alice, picks a private random value, inputs this into a key generation program, and receives two keys. It is arbitrary which of these is made public and which is kept private, but the privacy of the private key is paramount.

What is important here is that anything encrypted with one key can be decrypted with the other, and vice versa. Unlike symmetrical-keys a single key is not used for both directions, but rather the other one of the pair, and either can decrypt a message encrypted by the other.

Public/private key usage

Here Bob wants to send a message to Alice. Bob encrypts a message using Alice?s public key and sends it across a public channel. No harm can come here, as Alice?s public key cannot also be used to decrypt a message it encrypted, and it is exceptionally complex to guess Alice?s private key based on her public one and the ciphertext message. Once received Alice?s private key can be used to decrypt the message to see its contents.

Authentication using key pairs

Alice is able to authenticate it was Bob who sent the message

An incredibly important benefit of key pairs is the ability to authenticate the sender of a message.

• Bob encrypts the plaintext message with Alice?s public key. Only Alice?s private key can decrypt this.
• Bob then creates a digital signature. He encrypts his ciphertext message with his own private key. Only Bob?s public key will be able to decrypt this.
• Bob sends both the ciphertext message and the signature to Alice.
• Alice uses Bob?s public key to decrypt the signature. If the result of this matches the ciphertext message then Alice knows that Bob sent the message, as only Bob?s private key could have encrypted the message in a way Bob?s public key could decrypt it to match.
• Alice can then decrypt the ciphertext message using her private key and read it, confident it is from Bob.

Asymmetric algorithms are relatively slow compared to symmetric algorithms, we will look at this further when looking at forward secrecy. Asymmetric-key pairs are often used to establish initial communication, authentication when needed, while a symmetric key can be used for message encryption from that point forwards.

RSA algorithm

RSA (Rivest?Shamir?Adleman) was one of the first asymmetric public key systems and is widely used. We will look at it here in the context of public/private key generation. You can skip this if you are happy just knowing some ?maths magic? is used to create and use the pair.

A key pair generated for Alice

We will look at how to both use and how to generate the above keys in RCA.

RSA key usage

Lets first look at how to use them. We will pick one to share publicly and have other parties use for encryption of their outgoing messages. Remember, this could be either of them, everything we are about to do we could also do starting with the other key. Alice sets the keys as below.

Let?s say we are Bob and the message we want to send to Alice is simply the letter ?B?.

Public key encryption:

• We convert B to an integer, as our algorithm is based in numbers, not letters. For simplicity we will say B = 2, as it is the second letter of the Latin alphabet. This would be agreed by both parties and does not need to be secure.
• We use Alice?s public Key 1 to encrypt this integer, using the sum: 2**5(mod14).
• This equals 4 (which if we wanted to represent as a letter we would use 4 = D as agreed on in point one).

Private key decryption:

• So now Alice gets a message of ?4? and must decrypt it. Alice has access to her private key, Key 2 ? (11, 14).
• Alice can use this to do the sum: 4**11(mod14).
• As you?ve read this far you?re likely not surprised this gives us? 2!

Remember, the reverse of this can be done (signing a message with a private key and decrypting using a public key) as described in ?Authentication using key pairs? earlier.

RSA key generation

So how were the two keys above generated? Obviously they are extremely simplified examples, and use much smaller numbers than would ever be used in reality, but are still valid.

Each key can be represented as (e, N), (d, N).

Two prime numbers are chosen at random, and then have a series of steps performed on them to create the values of e, d, and N.

A list of mathematical steps here looses all context, so instead I would recommend watching this maths teacher explain it far better than I ever could:

Forward secrecy (FS)

Let?s finally tie this all together by looking at the concept of forward secrecy.

Also known as perfect forward secrecy (PFS), this implementation of cryptography provides security of past sessions against future secret keys being compromised.

A asymmetric system counts as having forward secrecy if it generates one random shared key per session, and uses the long lived asymmetric private key only for signing messages. This means the compromise of of a session key cannot compromise past messages, nor could the compromise of the long lived private key. The compromise of the private key would still open up the possibility of future man-in-the-middle attacks so.

An asymmetric-key is necessary for signing messages, but asymmetric ciphers are slow to use in comparison to symmetric ciphers. It is common that once asymmetric-keys are set up, and a secure channel created, symmetric keys are then used for encrypting all following messages that are to be sent, signed with the asymmetric-key.

We can see a simple example of establishing forward secrecy when exchanging messages here:

1. Alice and Bob each generate a pair of long-term, asymmetric public and private keys, then verify public-key fingerprints. These keys will only be used for is authentication, including signing messages and signing during session key exchange. These keys will not be used for encryption of any kind.
2. Alice and Bob use a key exchange algorithm such as Diffie-Hellman-Merkle, to securely agree on an ephemeral (short lived) session key. They use the keys from step 1 only to authenticate one another during this process.
3. Alice sends Bob a message, encrypting it with a symmetric cipher using the session key negotiated in step 2.
4. Bob decrypts Alice?s message using the key negotiated in step 2.
5. The process repeats for each new message sent, starting from step 2 (and switching Alice and Bob?s roles as sender/receiver as appropriate). Step 1 is never repeated unless a private key is compromised (or a new device set up without the private key).

Final thoughts

Cryptography and encryption keys is a rabbit hole that only gets deeper, but hopefully these universal concepts will help new areas make sense. Asking is a protocol is asymmetric or symmetric, used for encryption or for key exchange, ephemeral or long lived, can help provide context to the many different protocols and combinations that exist.

If you would like a focus to future reading I can suggest going through the steps in WhatsApp?s end-to-end encryption (E2EE, simply where as seen the server holds no key to decrypt messages) public white paper.

Thanks!

Useful videos

• Computerphile: Public Key Cryptography
• Computerphile: Key Exchange Problems
• RSA Maths: Eddie Woo