Introduction

This article is about end-to-end encryption and more specifically “secure key exchange”. You use it all the time, including to read this article. It’s used in the secure launch of a nuclear strike, in the banking system or even when you’re sending private messages. Remember the website setup on a Raspberry Pi from our previous article? Yes, even there, 'secure key exchange' is a vital component of the SSH protocol. Basically anytime there is a communication sent there’s a good chance you’re using end-to-end encryption.

;

Background information

What is end to end encryption and what problem does it solve?

Encryption is the method of cloaking messages, coding them in such a way that only the intended recipient can decipher them, thereby ensuring that intermediaries — whether they are mere message carriers or malicious eavesdroppers — are unable to tamper with or read the content. Without encryption there’s no guarantee for data integrity or confidentiality. It is important to note that governments around the world regulate encryption so that they can read messages and even censor them.

What problem does secure key exchange solve?

For end to end encryption to work the two parties that need to communicate need to exchange a secret called a “key” which is used to cloak and uncloak the messages at either end. However since all communication is facilitated via public channels, a significant problem arises: How can the key be exchanged securely without it being intercepted? This is the topic of today.

Introducing the problem

Here’s the example problem: Imagine two people, Romeo and Juliet, at opposite ends of a crowded stadium, each with a megaphone, needing to share secret messages with each other. Broadcasting openly would expose their forbidden secret to everyone, especially their families. Before they begin their communication they need to perform the key exchange.

Intuitive but flawed solutions

Here are some seemingly intuitive ways this problem could be solved but each with their own flaws.

Pre-exchange meetup

One intuitive approach would be to meet in secret ahead of time before communicating to exchange this key. However this would be impractical to meet up every time they want to communicate especially if there are large distances involved between each side of the stadium.

Shouting it out

Romeo and Juliet could use their megaphones to loudly announce their keys to each other at a predetermined interval amongst the chatter of other messages. This is analogous to transmitting unencrypted keys over a network. The issue here is basically the same as broadcasting the messages directly. Everyone else in the stadium could hear and copy the keys, thereby nullifying the entire process of encryption.

Using a rule to predetermine keys

Romeo and Juliet could come up with a simple protocol to determine keys for example, using the current date or the names of the teams playing in the stadium. This resembles using predictable or weak key generation algorithms in the real world. The pitfall of this approach is that anyone observing their pattern could guess their keys. If the pattern is known, the key is no longer secret.

Challenge for you

Take a moment to pause and think about how you would solve the problem before continuing onto the solution to see if you can figure it out.

Solution

Continuing on with our stadium analogy Romeo and Juliet have come up with a clever way to overcome the problem. For this analogy to work we have to imagine that there are an infinite amount of colours and each one can be identified by a number. Here’s how it works:

1. First, Romeo selects a colour, let's say #11 and loudly announces to Juliet, through his megaphone, his chosen colour number. This is public information, so everyone in the stadium hears it.
2. Juliet then chooses her own prime colour, perhaps #13, and declares her choice publicly through her megaphone. This too can be heard by all.
3. Next, Romeo and Juliet each blend their publicly announced colour with a secret colour they've chosen for themselves, which they keep confidential. Romeo might have a secret colour number of #17 and Juliet one of #19. They each create a unique colour mix that remains undisclosed. For this analogy, we will multiply the two numbers to signify that they are mixed. So Romeo’s mix is #11 x #17 = #187 and Juliet’s mix is #13 x #19 = #247.
4. Then, Romeo sends his mixed colour to Juliet, and Juliet reciprocates by sending her mixed colour number to Romeo. Keep in mind, these mixed colours numbers are composed of their publicly declared colour and their secret colour.
5. When Romeo receives Juliet's mixed colour #247, he blends it with his secret colour #17 to receive #4199, and Juliet does the same #187 x #19 to receive the same number #4199. Romeo and Juliet end up with the same colour, an amalgamation of all four colours. But even though the intermediate mixed colour numbers were made public, no one else in the stadium can replicate the final colour number because they do not know Romeo and Juliet's secret colour numbers.

This strategy succeeds because reversing the colour mixing—akin to factoring large numbers into their prime elements—is complex. In reality, key exchange algorithms employ sizable prime numbers, some thousands of digits long. Their choice of initial colours being primes isn't accidental; it's the difficulty of factoring these large numbers that gives this method its inherent security.