Let’s say you want to send an encrypted message to your friend in order to avoid it being intercepted and read by a third party. You just generate a random secret key and encrypt the message with it. Let’s say you use AES. But how do you let your friend know the key to decrypt it?

You could give the key to your friend offline. Just write it on paper and give it to him/her. But what if it’s not an option?

What if you can only use an **insecure** data communication channel with a middleman intercepting the messages?

There is a way to securely exchange secret keys even in the presence of a third party!

You just exchange some information with your friend and **both of you come up with the same key**. The middleman also sees the messages you’ve exchanged. But he will never be able to guess the secret key. Does it sound exciting? Let’s see how it’s possible.

#### Diffie-Hellman Algorithm

The algorithm is based on an extremely simple algebraic feature that we are all familiar with.

The **commutative property of multiplication**. In other words:

A * B * C = B * A * C = C * A * B, …

I know, it doesn’t yet seem relevant to anything yet.

### A very rough (and incomplete) example

Let’s

**imagine**, the**division**operation**doesn’t exist**.You and your friend

**both know**some number, let’s say,**12345**.You generate some random Private key, let’s say,

**23456**Your friend generates a random Private key too, let’s say

**34567**You multiply your Private key

**23456**by**12345 = 289564320 (Public key)**Your friend multiplies his/her Private key

**34567 by 12345 = 426729615 (Public key)***!!! at this point, we just imagine the division operation doesn’t exist !!!*You and your friend send the results of multiplication (the Public keys) to each other (

**289564320**and**426729615**)Your friend multiplies your Public key

**289564320**by his Private key**34567 = 10009369849440**You multiply your friend’s

**Public key****426729615**by your Private key**23456 = 10009369849440, and this is the shared key***Profit! You came up with the same value!*

But… the only problem is that the division operation actually exists, so it’s extremely easy to extract the Private key from a Public key.

A middleman could just divide Public keys by **12345,** and extract the Private keys**: 289564320/12345 = 23456, 426729615/12345 = 34567**, and then just multiply the private keys by the shared number: **23456 * 34567 * 12345 = 10009369849440.**

That was the general idea of the Diffie Hellman, and now let’s focus on an actual form.

Let’s combine the Diffie-Hellman idea with **Elliptic Curve Cryptography** as it’s the most used implementation nowadays.

To fully understand the topic, I highly recommend checking my article on Elliptic Curve Cryptography. It requires no more than middle-school math.

#### Very short: Essentials of Elliptic Curves cryptography

I don’t think it’s possible to explain how the Elliptic curves are used in cryptography briefly. But here are the most important properties:

We can multiply any point lying on a curve by a scalar value

There is no feasible way to extract the scalar value back (to divide a point by a scalar value or by another point)

A private key in elliptic curve cryptography is just a random value that’s kept secret

The corresponding Public key is just a result of the multiplication of some certain point

**G**by the Private key (PublicKey = PrivateKey * G)The

**G**point is standardized and everyone uses it

#### How to securely exchange the keys over a public network?

Let’s suppose we have two parties: Alice and Bob (why again these names?).

Here is a[way too] colorfulexplanation of the Diffie-Hellman key exchange mechanism. It may not look too pretty, but the colors which occur as the results of multiplication are actually the mixes of original colors.Squaresindicatescalarvalues, and thecirclesindicatepointson an Elliptic curve.

Both Alice and Bob generate **big random numbers**, and we call these numbers the **Private Keys**:

Then Alice **multiplies** her **Private Key** by the publicly known **G point** in order to get her **Public Key**:

And Bob multiplies his **Private Key** by the same **point G** to get his **Public Key**:

Now they both have their pairs of PrivateKey-PublicKey:

The next step is to exchange the public keys.

Alice **sends** her **Public** Key to Bob. And Bob **sends** his **Public** Key to Alice:

After that, Alice and Bob have each other’s **Public** keys, but a middleman **also** potentially knows their Public keys:

If you remember, **Private** Key **can’t be extracted** back from the **Public** key. So knowing the **Public keys** is **of no use** to a middleman.

#### Then the magic happens.

**Alice** takes **Bob’s Public Key** (a point on an Elliptic curve) and **multiplies** it into **her Private Key**.

**Bob** does the same. He **takes** **Alice’s Public Key** and **multiplies** it into **his** own **Private Key:**

#### They end up with the same Secret key without explicitly exchanging it

Actually, it’s a very simple math trick.

Let’s take a look at how their Public keys are calculated:

Not let’s look at how both parties calculate the shared keys:

Let’s see if **BobSecretKey** = **AliceSecretKey** by comparing their definitions:

Let’s substitute **AlicePublicKey **and** BobPublicKey** with their definitions:

**The expressions are the same.**

If you don’t yet understand why and how we are able to multiply points on Elliptic curves like numbers, I recommendreading the article.

Both Alice and Bob now have ended up with the same **SecretKey** (point on a curve), which they didn’t expose to a middleman.

And the middleman can do nothing with their **Public Keys** which he has potentially intercepted.

#### Let’s implement it in Python

In my article on Elliptic curves, I have a code snippet for using the secp256k1 elliptic curve, written in Python. For more details on how it works, check the article's PART V.

What’s important is that we have the `g_point`

instance, which has the .multiply method for multiplying the point by any scalar value. The return value of this method is also a point.

Let’s pick random private keys for Alice and bob:

```
alice_private_key = 4115217275797054326758545175592171983915694080873854598446270747 #any random number
bob_private_key = 4954095651507529369947464574074855803473979998363142920136936367 #any random number
```

Then let’s calculate the public keys for both of them:

```
alice_public_key = g_point.multiply(alice_private_key)
bob_public_key = g_point.multiply(bob_private_key)
```

Now let’s imagine they have sent the public keys to each other. Alice calculates the secret key on her side:

`alice_secret_key = bob_public_key.multiply(alice_private_key)`

Bob calculates his secret key on his side:

`bob_secret_key = alice_public_key.multiply(bob_private_key)`

Now let’s print the secret keys:

```
print(bob_secret_key.x, bob_secret_key.y)
print(alice_secret_key.x, alice_secret_key.y)
```

The result:

It works!

#### Here is the complete Python code using zero dependencies for you to try it yourself

```
def find_inverse(number, modulus):
return pow(number, -1, modulus)
class Point:
def __init__(self, x, y, curve_config):
a = curve_config['a']
b = curve_config['b']
p = curve_config['p']
if (y ** 2) % p != (x ** 3 + a * x + b) % p:
raise Exception("The point is not on the curve")
self.x = x
self.y = y
self.curve_config = curve_config
def is_equal_to(self, point):
return self.x == point.x and self.y == point.y
def add(self, point):
p = self.curve_config['p']
if self.is_equal_to(point):
slope = (3 * point.x ** 2) * find_inverse(2 * point.y, p) % p
else:
slope = (point.y - self.y) * find_inverse(point.x - self.x, p) % p
x = (slope ** 2 - point.x - self.x) % p
y = (slope * (self.x - x) - self.y) % p
return Point(x, y, self.curve_config)
def multiply(self, times):
current_point = self
current_coefficient = 1
pervious_points = []
while current_coefficient < times:
# store current point as a previous point
pervious_points.append((current_coefficient, current_point))
# if we can multiply our current point by 2, do it
if 2 * current_coefficient <= times:
current_point = current_point.add(current_point)
current_coefficient = 2 * current_coefficient
# if we can't multiply our current point by 2, let's find the biggest previous point to add to our point
else:
next_point = self
next_coefficient = 1
for (previous_coefficient, previous_point) in pervious_points:
if previous_coefficient + current_coefficient <= times:
if previous_point.x != current_point.x:
next_coefficient = previous_coefficient
next_point = previous_point
current_point = current_point.add(next_point)
current_coefficient = current_coefficient + next_coefficient
return current_point
secp256k1_curve_config = {
'a': 0,
'b': 7,
'p': 115792089237316195423570985008687907853269984665640564039457584007908834671663
}
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
g_point = Point(x, y, secp256k1_curve_config)
##############################
alice_private_key = 4115217275797054326758545175592171983915694080873854598446270747 #any random number
bob_private_key = 4954095651507529369947464574074855803473979998363142920136936367 #any random number
alice_public_key = g_point.multiply(alice_private_key)
bob_public_key = g_point.multiply(bob_private_key)
alice_secret_key = bob_public_key.multiply(alice_private_key)
bob_secret_key = alice_public_key.multiply(bob_private_key)
print(bob_secret_key.x, bob_secret_key.y)
print(alice_secret_key.x, alice_secret_key.y)
```

In case you might need it, here is an online tool for running Python code right in your browser

Mikhail Karavaev