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] 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:
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 recommend reading 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 numberThen 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
