The Pohlig-Hellman Attack

Curve 25519 has a little bit of a problem — in that it has a subgroup with a co-factor of 8. This means that we have an eighth of the total range of a group, and which can be compromised by the Pohlig-Hellman attack. Within X25519, we get around this by clamping the three least significant bits (LSB), and there is no equivalent method for Ed25519. For this, we can turn to Ristretto255 [here], which makes sure we have a prime number order. So, let’s look at the attack method on a non-prime order.

The attack operates on both discrete logarithm and elliptic curve problems, and was created by Steve Pohlig and Marty Hellman [1]:

So what’s an order of a group?

In cryptographic systems, we typically implement within a group with a prime order of ℓ. But what does this mean? Well, let’s say we have a simple cipher and where we modular multiply by h, and then to decipher, we modulo divide by h. The cipher would then be:

c=h.x (mod p)

If we select p as 7 and h as 2, we then map:

x=0 -> c=0
x=1 -> c=3
x=2 -> c=6
x=3 -> c=2
x=4 -> c=5
x=5 -> c=1
x=6 -> c=4