CryptoBook
Search…
Diffie-Hellman

Overview

We need to make some changes: separate the explanation from the code, add a subpart about the MITM and maybe to develop more the instructions
Let's say Alice and Bob want to exchange a secret over an insecure channel. In other words, anyone can read the messages they send, but the goal is to ensure that only Alice and Bob can calculate the secret key.
Diffie-Hellman key exchange provides a solution to this seemingly impossible task. Since code may be easier to understand than a detailed explanation, I'll provide it first:
1
import Crypto.Util.number as cun
2
import Crypto.Random.random as crr
3
4
5
class DiffieHellman:
6
def __init__(self, p: int):
7
self.p = p
8
self.g = 5
9
self.private_key = crr.randrange(2, p-1)
10
11
def public_key(self) -> int:
12
return pow(self.g, self.private_key, self.p)
13
14
def shared_key(self, other_public_key: int) -> int:
15
return pow(other_public_key, self.private_key, self.p)
16
17
18
p = cun.getPrime(512)
19
alice = DiffieHellman(p)
20
bob = DiffieHellman(p)
21
22
shared_key = bob.shared_key(alice.public_key())
23
assert shared_key == alice.shared_key(bob.public_key())
Copied!
Here's a brief explanation of the code:
    We choose a prime
    pp
    and a generator
    gFpg \in \mathbb{F}_p
    Alice picks a private key
    aZp1a \in \mathbb{Z}_{p-1}
    Bob picks a private key
    bZp1b \in \mathbb{Z}_{p-1}
    Alice's public key is
    gamodpg^a \mod p
    Bob's public key is
    gbmodpg^b \mod p
    Their shared key is
    gab(ga)b(gb)a(modp)g^{ab} \equiv (g^a)^b \equiv (g^b)^a \pmod p
So anybody observing the messages sent between Alice and Bob would see
p,g,ga,gbp, g, g^a, g^b
, but they wouldn't be able to calculate the shared key
gabg^{ab}
.
This is because given
gg
and
gag^a
, it should be infeasible to calculate
aa
. If this sounds familiar, that's because it's the Discrete Log Problem.
The original paper can be found here. It uses the group of integers modulo a prime to perform the key exchange. In practice however, any group with a hard discrete log problem can be used.
Last modified 5mo ago
Export as PDF
Copy link