What lies beneath Public-Key-Cryptography?

Oh! how much we love hearing about hacking, watching geeky movies and spewing out names of fancy Crypto¹-algorithms. You’re probably hearing about Web3.0 a lot lately, or how secure Signal is, or critique about the military grade encryption of the Russians and what not. We wish all of this was happening magically (spoiler alert: its not!). But how about actually understanding what lies underneath? What’s saving you from someone getting access to your funds, your Facebook account, or your iCloud. As you should expect, mathematics comes to our rescue. This is what the current security of the internet is based on: Mathematical Problems. Computationally Hard Mathematical Problems.

Specifically, Number theory (regarded as the Queen of Mathematics). As it indicates, it deals with all things numbers (Think of everything as numbers. Shouldn’t be hard!). Numbers, good old numbers! Sounds simple, right?

Q: So, how does these numbers secure the internet?

We’re gonna get there, I promise! All you need is to know how multiplication works. Yes! Multiplication, 2*2 = 4. Yeah, right! you did this in high school. If I ask you to perform multiplication of 991*997, some might do it in the head, or with the Chinese multiplication trick (pun intended!), or simply with your phone within no time. But what if I ask you to tell me what numbers did I multiply to make up the number 1742399. It might be a bit hard to do. However, if I give you a number that looks something like this:

For the current fastest supercomputer, it should take more than the age of this universe to find the two numbers that were multiplied to give this number. This is called the “Integer Factorization Problem”. That’s it! Yes! That’s it. This is the problem that your internet currently relies on!

RSA (named after Ron Rivest, Adi Shamir and Leonard Adleman) is the most widely used public-key cryptosystem which relies on the problem of Integer Factorization. TLS (Transport Layer Security) which is an IETF(Internet Engineering Task Force) standard forming the basis for HTTPS protocol used RSA for key exchange until TLS1.2. In fact, the currently used key-exchange mechanism in TLS1.3 is the Ephemeral-Diffie-Hellman Key Exchange relying on another form of public-key cryptography called as the Diffie-Hellman-key-exchange (named after Whitfield Diffie and Martin Hellman) This problem relies on another mathematical hard problem known as the “Discrete Logarithm Problem”. I know, that’s a lot of cryptography jargon! But it’s all gonna be worth it.

Ever wondered how you’re able to communicate with someone securely over the internet when you are hundreds or thousands of miles away from each other? Even when you haven’t even met before? The first question however is: How do you exchange keys with that person to be able to exchange information securely afterwards. Lost? Hang on for a moment! Let’s take a deep breath and start with the simple classical case. We’ll take help from our good old friends Alice and Bob:

Alice and Bob have to communicate securely with each other . They decide to meet at a place over a phone call and exchange the pair of keys physically that they will use to encrypt their communication. They’re good, right? But how do they communicate with each other if they happen to be miles apart or if someone happens to get access to Alice’s or Bob’s key. They will be able to decrypt and read each of the messages encrypted with those keys earlier. A mathematically intriguing and beautiful concept that helps us achieve this is nothing short of crème de la crème. Let’s illustrate how this is achieved:

Since Diffie Hellman is a concept in public-key cryptography, let’s assume that there are two publically available parameters. Let’s call them x and m and yet again think of them as numbers. Since both has the public parameters, Alice and Bob compute their corresponding keys as:

Alice: Alice chooses a key for herself (say a) and then performs the operation:

Alice performs this operation with her corresponding private key a

Bob: Bob chooses a key for himself (say b) and then performs the operation:

Bob performs this operation with his corresponding private key b

Then they exchange these corresponding keys with each other. Thus Alice receives:

The key Alice received from Bob and performs exponentiation with her private key

While Bob receives:

The key Bob received from Alice and performs exponentiation with his private key

Then they both perform the exponentiation of the received result with their own private key and both receive:

This is the agreed upon public key which is same for both parties even while keeping their inputs secret

which is the same for both parties due to the commutative property of exponentiation. Voila!

For your understanding, you can tweak in the actual values into the protocol and check how the values turn out to be the same at both ends. Given the public parameters x and m. The discrete logarithm problem is the following:

Given x and m, compute the logarithm of β base x mod m

Some important Caveats and points:

• While the above was tried with simpler numbers, the actual numbers are chosen based on a certain criteria. For instance, the integer factorization problem becomes hard for numbers that have a large number of digits and specifically where n (the number to be factored) is a product of prime numbers.
• The Diffie-Hellman parameters are chosen in such a manner that the Discrete Logarithm problem is hard in a chosen integer group particularly cyclic groups of prime order (The discussion of groups is omitted to keep this as simpler as possible and limited to numbers only).
• RSA has been dropped from TLS 1.3 as the key-exchange mechanism² and uses Ephemeral DH instead.
• The fundamental key agreement technique Diffie-Hellman is implemented in many technologies like SSH(Secure Shell), IPSec and TLS.

[1]: PRESIDENTIAL ALERT: CRYPTO STANDS FOR CRYPTOGRAPHY

[2]: A Detailed Look at RFC 8446 (a.k.a. TLS 1.3) by Nick Sullivan