Diffie-Hellman

The Diffie–Hellman key exchange is a method that generates a shared secret over a public channel. This method is based on the discrete logarithm problem which is believed to be hard to solve.

Key generation (Textbook DH)

Suppose a situation where Alice and Bob want to create a shared secret key. They will use a public channel to do so.

They chose a standard prime number $p$ and a generator $g$ . $g$ is usually 2 or 5 to make computations easier. $p$ and $g$ are public and $GF(p) = {0, 1, ..., p-1} = {g^0 \mod p, g^1 \mod p, ..., g^{p-1} \mod p}$ is a finite field.
They create private keys $a$ and $b$ respectively. $a, b \in GF(p)$ .
They compute the public keys $A$ and $B$ and send them over the public channel. $A = g^a \mod p$ $B = g^b \mod p$
They can now both compute the shared secret key $s$ : Alice computes $s = B^a \mod p$ and Bob computes $s = A^b \mod p$ .
$s = B^a = A^b = g^{ab} \mod p$

They can now use the shared secret $s$ to derive a symmetric key for AES for example, and use it to encrypt their messages.

Attacks

DH with weak prime using Pohlig–Hellman - Wikipedia
The public prime modulus $p$ must be chosen such that $p = 2*q + 1$ where $q$ is also a prime. If $p-1$ is smooth (i.e have a lot of small, under 1000, factors), the Pohlig–Hellman algorithm can be used to compute the discrete logarithm very quickly. Sagemath’s discrete_log function can be used to compute the discrete logarithm for such primes.
Use this script to generate smooth numbers of selected size.
- smooth_number_generator.py
Low-entropy secret with a partially smooth prime
Even when $p-1$ is not fully smooth, Pohlig–Hellman still leaks the private key modulo the smooth part of $p-1$ . This is enough to fully recover a low-entropy secret (for example a private key derived from a short password or hashed with a weak function).
Write $p - 1 = N \cdot M$ where $N$ is the smooth part (product of the small prime factors) and $M$ is the rough cofactor. The map $x \mapsto x^M$ projects onto the unique subgroup $H = \langle g^M \rangle$ of smooth order $N$ . With $h := g^M$ and $y := F^M$ , the public key $F = g^f$ becomes $y = h^f$ inside $H$ , so a discrete log in $H$ recovers
$f \bmod N$
If the secret satisfies $f < N$ , this recovers $f$ entirely.
```
from sage.all import *
N = prod(P**e for P, e in factor(p-1) if P < 10**12)  # smooth part
M = (p-1) // N
f = discrete_log(Mod(F, p)**M, Mod(g, p)**M, ord=N)   # f mod N
```
DH with small prime
The security of Diffie-Hellman is lower than the number of bits in $p$ . Consequently, is p is too small (for example 64bits), it is possible to compute the discrete logarithm in a reasonable amount of time.
```
from sage.all import *
a = discrete_log(Mod(A, p), Mod(g, p))
```

smooth_number_generator.py