Watch the Animated Version Here 👇🏻 https://youtu.be/aHSP1bmzqPo?embedable=true 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 a 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 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 (instead of 13), and (instead of 5 and 11). p which is a very large prime number g and x are also very large numbers 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? , and even with the current generation  of computers, it would take a very long time to solve. ⌛️ This is the gist of the discrete logarithm problem 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, . Those will be shared over the public internet. JayP and Joe both agree on two numbers: g, and p, a large prime number Then, over the internet. each of JayP and Joe will generate a random private key that will not be shared Computing the Public Keys 🔑 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. . Now, let’s see how the shared secret will be derived from these params. The private keys were not shared Computing the Secret 🤫 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 the substitution of the public keys on each side. This explains how both JayP and Joe contribute to generating a shared secret value without actually transmitting it. Security of Diffie-Hellman 🔐 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. Key Derivation Function 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 key, and the symmetric key used for data encryption. MAC Shameless Self Promotion 😨 I'm kickstarting my new YouTube channel, , 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 😉 JayPMedia Also published here: https://medium.com/@jaypmedia/diffie-hellman-its-simple-maths-explained-in-5-minutes-f9061f04557c https://dev.to/jaypmedia/diffie-hellman-its-simple-maths-explained-in-5-minutes-3f2e

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

Diffie-Hellman & Its Simple Maths: A Quick Explanation for Web Developers🙆🏻‍♂️

Too Long; Didn't Read

Jean-Paul Rustom

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Diffie-Hellman & Its Simple Maths: A Quick Explanation for Web Developers🙆🏻‍♂️

Too Long; Didn't Read

Jean-Paul Rustom

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES