Watch the animated version here 👇🏻
What is the discrete logarithm problem ?
In order to understand the Diffie-Hellman algorithm, one must understand the discrete logarithm problem in Maths.
The logarithmic function follows the concept of a trapdoor function. A trapdoor function is easy to compute in one direction, yet difficult to compute in the opposite direction.
Let’s visualize it this way:
Given 2 teaspoons of coffee, 1 teaspoon of sugar and half cup of milk, you can make coffee.
Now given the same coffee, can you guess the exact amounts of coffee, sugar, and milk?
Modulo operation is an operation where the result is the remainder of the division operation performed with two given integers as operands.
We say 13 mod 5 ≡ 3 because 13 = 5 x 2 + 3
What if we want to find x such that 5^x mod 13 ≡ 11 ?
Let’s try many values for x and check after how many tries we find the answer.
After 8 tries, we will find that for x = 8 we will get 5 to the power x mod 13 is 11
Now here is where it gets interesting.
Let’s say we have x ≡ g^y mod p .
But now we have p is a very large prime number (instead of 13) and g and x are also very large numbers (instead of 5 and 11).
And by large, we mean, really large. Imagine for example p being equivalent to 2048 bits
p=292463028894281219037597349727360684779483317376473239399537257843546320734871513839651347201104480199877191389522614785890996622493775440722572336903336882065975199234931879695261910015161305537526235180562475469982005301778126151856278585195545100903316048416565416635315530213841740854981894053524430751990450476315137696784232893772161407889014577329968174019042697407332291644176957214843165640734510101308586892775505187939228207220238747243895829499434176678189216930154964392995431879145409980273938229601680574417474486982384981120906945098803000392061156847661464691587852166635245652933518718150794527
Can you find y given these circumstances?
This is the gist of the discrete logarithm problem, and even with the current generation computers it would take a very long time to solve.
One of the reasons prime numbers are used is to avoid repeating patterns.
For example, let's take p = 12, a non prime number
- 21 mod 12 = 2
- 22 mod 12 = 4
- 23 mod 12 = 8
- 24 mod 12 = 4 (repeating)
- 25 mod 12 = 10
- 26 mod 12 = 2 (repeating)
- 27 mod 12 = 4 (repeating)
- 28 mod 12 = 8 (repeating)
For example for p=11, prime number:
- 21 mod 11 = 2
- 22 mod 11 = 4
- 23 mod 11 = 8
- 24 mod 11 = 5
- 25 mod 11 = 10
- 26 mod 11 = 9
- 27 mod 11 = 7
- 28 mod 11 = 3
- 29 mod 11 = 6
- 210mod 11 = 1
The discrete logarithm problem is the base of the Diffie-Hellman exchange algorithm.
Diffie-Hellman
Diffie-Hellman key exchange can be used to securely exchange a secret key over an insecure network. It works using the concepts of prime numbers and modulo operations.
First, JayP and Joe both agree on two numbers: g, and p, a large prime number. Those will be shared over the public internet.
Then, each of JayP and Joe will generate a random private key which will not be shared over the internet.
After that JayP computes his public key using the formula in the screenshot below, and sends it to Joe.
Similarly, Joe also computes his public key the same way and sends it to JayP.
To recap, until now, both parties have shared over the public internet the params g and p, and their respective public keys. The private keys were not shared. Now let’s see how the shared secret will be derived from these params.
JayP computes the shared secret on his side using the equation shown in the screenshot below.
Joe also computes the shared secret on his side using the same equation.
The secret key they have each calculated independently will be the same.
Why? Well, due to simple maths. Let’s apply substitution of the public keys in each side.
This explains how both JayP and Joe contribute to generating a shared secret value without actually transmitting it.
Given p, g, and y, it is very easy to compute S.
But over the public internet, Chady can only see p and g, and it will be very hard for him to compute y. Computing y is the discrete logarithm problem we just talked about earlier.
In the TLS handshake, the shared secret will be fed into what’s called a key derivation function.
The KDF takes as input the shared secret, and other params such as a salt and some additional app-specific info.
With all these inputs, the KDF will produce many keys, for example the MAC key, and the symmetric key used for data encryption.
Shameless Self Promotion 😨
I'm kickstarting my new YouTube channel, JayPMedia, where I'll be sharing all things web development. If you're keen to learn and grow with me, hit that subscribe button and let's dive into the world of coding and learning 😉
Also published here:
Top comments (0)