How to exchange a secret key over an insecure network (EC-Diffie-Hellman algorithm)
Tags: python, security, programming, cybersecurity
Published: 2022-12-15 18:25:44

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 are using [AES](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard). 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?

![Source: https://www.treinaweb.com.br/blog/termos-comuns-de-seguranca-man-in-the-middle](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1r596errijc25y0rith5.png)
_Source of the image: https://www.treinaweb.com.br/blog/termos-comuns-de-seguranca-man-in-the-middle_

**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 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](https://dev.to/exemak/bitcoin-signatures-from-scratch-14-the-magic-of-elliptic-curves-2n7h). 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?](http://cryptocouple.com/)).

> Here is a **[way too] colorful** explanation 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. **Squares** indicate **scalar** values, and the **circles** indicate **points** on an Elliptic curve.

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xptakiwy8hnx2stoarwd.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pw5gbye8foiytzjuo9lq.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zd7ow9tu4tsih53f6tqu.png)

Now they both have their pairs of PrivateKey-PublicKey:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/df780f650iu98qa4yo5z.png)
The next step is to exchange the public keys. 

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zojxvkj456gsczv13xf3.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c5y60g2mvgl3ida4o58b.png)

If you remember, **Private** Key **can’t be extracted** back from the **Public** key. So knowing the **Public keys** is o**f 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jt17bia7jgv89qht9ny3.png)
**Bob** does the same. He takes **Alice’s Public Key** and **multiplies** it into his own **Private** Key:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/onckmsus6o453avlnpki.png)

### 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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ut7mkoxbhh79yobho4n.png)
Not let’s look at how both parties calculate the shared keys:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o1sgc96wjrb6ynrkrxun.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7re78inny0783ykjn9g2.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e9uk53jf7fwwo06u6tyy.png)

**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 recommend [reading the article](https://dev.to/exemak/bitcoin-signatures-from-scratch-14-the-magic-of-elliptic-curves-2n7h).

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 4](https://dev.to/exemak/bitcoin-signatures-from-scratch-44-ecdsa-implementation-in-python-using-zero-dependencies-410c).

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 private 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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jafvgvg4ev5s3j4zna7b.png)
It works!

### Here is the complete Python code using zero dependencies for you to try it yourself
Complete code: 
{% embed https://gist.github.com/exemak/3d853b15535f3dba816106b5170f97f3.js %}

In case you might need it, here is an [online tool for running Python code right in your browser](https://www.programiz.com/python-programming/online-compiler/)

---
exemak@gmail.com

[t.me/exemak](https://t.me/exemak)

Mikhail Karavaev