DHKE Attacks

Small prime

If the prime \(p\) is small enough, then the DLP is not hard enough and can thus be solved in little time with existing algorithms.

1
2
3
4
5
6

from sage.all import *

# Recover one of the secrets
a = discrete_log(Mod(A, p), Mod(g, p))
# Compute shared secret
s = g^a % p

Smooth prime

The public prime modulus \(p\) must be chosen such that \(p=2q+1\) where \(q\) is also a prime. If not, then \(p-1\) might be a smooth number (i.e a number having a lot of small factors).

If so, then the Pohlig–Hellman algorithm can be used to compute the discrete logarithm very quickly.

Sage uses this algorithm when necessary under the hood, so you can use the same function presented above.

Now, here is a simple script to generate such smooth primes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from Crypto.Util.number import isPrime

def smooth_p(bit_length=256):
    mul = 1
    i = 1
    while 1:
        mul *= i
        if (mul + 1).bit_length() >= bit_length and isPrime(mul + 1):
            return mul + 1
        i += 1

Small Subgroup Attack

This attack exploits the same vulnerability created by a smooth prime number. You can thus refer to the previous attacks to take advantage of it.

Nevertheless, here are some resources to read more about it.

• Small Subgroup Attacks - Florianjw’s blog
• Small-Subgroup-Confinement-Attack