Posted on 7 mins read

Most people are familiar with the http:// that begins web site URLs. And some may have noticed that any website with a login form or sensitive information starts with https:// instead. The “S” stands for “Secure,” and the algorithms that make it work are crazy and wonderful. To understand why HTTPS is so magical, let’s use an analogy.

Suppose you gather three accomplished programmers: Janice, Natalia, and Mario. These three have never met or communicated in any way. You place them in a room, seated in a row with Natalia in the middle.

[ Janice | Natalia | Mario ]

Then you give them a challenge. It goes like this:

  1. You’ll give Janice a secret message she needs to send to Mario.
  2. If Natalia discovers the secret message, she’ll get a prize, but Janice and Mario will get nothing.
  3. If Mario receives the secret message without Natalia finding out what it is, Mario and Janice will both get a prize, and Natalia will get nothing.
  4. They can only communicate by passing notes back and forth. Natalia can read any note she wants.

It seems like an impossible puzzle. If Natalia is reading all the notes they pass back and forth, how can Janice and Mario communicate in secret? This is the same problem we face on the web. Your web browser is always communicating with remote servers, and they may have never communicated before. Any message sent over the Internet could potentially be intercepted and read by a third party, so how do we keep these messages secret, to avoid your passwords and bank account numbers being stolen? The answer is HTTPS.

Take a minute to think about this puzzle. One idea you might have is that if Janice and Mario could exchange just a little bit of information (a number) in secret, they could use that to encode the rest of their messages. They could use a number-substition cipher (A = 1, B = 2, C = 3, and so on), then plug each number into an equation along with the secret number in order to make it harder to guess which numbers equal which letters. Natalia could know about the equation, but if she didn’t know the secret number she wouldn’t be able to reverse the equation and decode the message.

This idea is called a symmetric-key algorithm and we use it all the time! It’s a great way to encode and decode secret messages.

All that’s left is to figure out how to exchange the secret number. Janice knows some cool things about prime numbers and has an idea of how to do this.

First, Janice picks two prime numbers, called p and g. She sends them to Mario; it’s okay if Natalia sees them.

var p = 23;
var g = 5;

Then Janice picks a secret number, any number she wants. Let’s say that number is 3.

var janiceSecret = 3;

She creates the following function:

function computeExchange(g, secret, p) {
  var exchange = Math.pow(g, secret) % p;
  return exchange;
}

So she’ll raise g to the power of secret, divide by p, and return the remainder of that division.

computeExchange(g, janiceSecret, p);
> 10

The answer is 10. Janice sends that number to Mario.

var numberFromJanice = 10;

Then Mario chooses a secret number, say 8, and runs the same function.

var marioSecret = 8;
computeExchange(g, marioSecret, p);
> 16

Mario gets 16 and sends that number to Janice.

var numberFromMario = 16;

There’s just one more step. Janice runs the function again, but instead of using g, she uses the number Mario just sent her.

computeExchange(numberFromMario, janiceSecret, p);
> 2

And Mario does the same: he runs the function again, but replaces g with the number Janice sent him.

computeExchange(numberFromJanice, marioSecret, p);
> 2

Both of them got the number 2! Is this a coincidence? No, it’s not. In fact, it’s a mathematical certainty. Regardless of the prime numbers they choose as p and g, and no matter what they choose as their secret numbers, they’ll end up with the same number–not necessarily 2. In this case, they’ll use 2 as the secret number to encode and decode their message. This is called a Diffie-Hellman key exchange. Let’s pick some different numbers and do it again:

function computeExchange(g, secret, p) {
  var exchange = Math.pow(g, secret) % p;
  return exchange;
}

var p = 29;
var g = 7;
console.log('p and g are:', p, g)

var janiceSecret = 8;
var marioSecret = 5;

var numberFromJanice = computeExchange(g, janiceSecret, p);
console.log('Janice sends Mario', numberFromJanice);
var numberFromMario = computeExchange(g, marioSecret, p);
console.log('Mario sends Janice', numberFromMario);

var janiceKey = computeExchange(numberFromMario, janiceSecret, p);
var marioKey = computeExchange(numberFromJanice, marioSecret, p);

console.log('Their shared key should match:', janiceKey, marioKey);

(Note that this won’t work for slightly larger values of p, g, janiceSecret, and marioSecret, because JavaScript doesn’t handle big numbers very well. It’ll work just fine in Python.)

Both janiceKey and marioKey evaluate to 16. That number is very special. It was never exchanged in a note. Natalia has never seen it. Natalia can’t reverse the equation because she doesn’t know Janice or Mario’s secret number. The best she can do is guess what their secret number might have been and try to figure out the encoding/decoding key based on that. For small numbers like the ones we used, she can probably do that. But if Janice’s and Mario’s secret keys are very large numbers, like 115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 935 (a 256-bit number), then it becomes prohibitively difficult. And there’s definitely no way Natalia will figure out their shared key and decode the message before the challenge ends, you run out of patience, or someone dies of old age.

That’s pretty much what your browser does every time you connect to a server that uses HTTPS. It’s called a “TLS handshake.” Someone could be sniffing the Internet connection, reading every message your browser sends and receives from the very first moment, and still be unable to decode your messages once the shared key is determined. Pretty crazy, huh?

There’s one piece missing. Suppose Natalia is especially devious and comes up with a plan to cheat the challenge: as each message comes by, she’ll replace it with a different message she’s created in secret. This way, she can do separate TLS handshakes with Janice and Mario and neither of them will know. When a message comes from Mario, she’ll decode it using the shared key she created with him (but which he thinks he created with Janice), then encode it using the shared key she created with Janice (who thinks she created it with Mario). This a type of man-in-the-middle attack.

Luckily, there is a solution to this problem. Imagine that Janice and Mario are especially insightful and they predict that this might happen. They approach you before you start the challenge and point out that it could be cheated. To prevent that, they each sign their name on a note and ask you to post it where everyone can see. That way, they can sign the messages they send, and unless Natalia knows how to forge signatures very quickly, they’ll know that the messages are authentic by comparing the signature on each note to the publicly visible one.

Computers sign messages using digital signatures, which is more math magic I won’t get into here. But in short, one party provides a public key, a message, and a signature, and another party uses math to prove that the message matches the public key. On the web, this public key is usually provided by a trusted source, known as a Certificate Authority, and pre-installed on your operating system or web browser. That way, your computer can use information it already possesses to verify the authenticity of messages from uncertain sources and make sure it’s setting up secure communication with the intended server.

All of this to stop people from knowing which cat videos you’re watching. And your credit card number, I guess.

comments powered by Disqus