Pohlig-Hellman Attack in ECDLP

Elliptic Curves

In its more general form, an Elliptic Curve is a curve defined by an equation of the form

over some field F.

For example,

\(E(F)\) defines a set of points that satisfy the elliptic equation in the field \(F\).

\(\mathcal{O}\) means Origin, \((0, 0)\). It does not satisfy the elliptic equation but it is necessary for operation. Actually, we usually use simpler curves, like the curves mentioned with example.

Group Operation

We can create a group operation \(+\) over the set \(E(F)\). I’ll explain how to add 2 points on an Elliptic curve with image.

Let’s do \(P+Q\).

1. Draw the line \(L\) through \(P\) and \(Q\).

2. The line \(L\) intersects the cubic curve \(E\) in a third point. Call that third point \(R\).

3. Draw the vertical line through \(R\). We define the \(P+Q\) to be the reflected point of \(R\).

If you want to do \(P+P\), line \(L\) becomes the tangent line to \(E\) at \(P\).

Let’s do \(P+(-P)\).

Unfortunately, \(L\) does not intersect \(E\) in a third point. Therefore, we should define \(P+(-P)\). That’s why Origin is necessary!

There is a algebraic definition of add operation but it doesn’t necessary in this article so I’ll skip it.

Choice of Field

Elliptic cuves can have points with coordinates in any field, such as \(\mathbb{F}_{p}\), \(\mathbb{Q}\), \(\mathbb{R}\). In this article, I will consider the attack against curves over prime fields, \(\mathbb{F}_{p}\).

If you don’t know about prime fields, see this site. Actually.. If you don’t know prime field yet, this article is not easy to understand…

Elliptic Curve Discrete Logarithm Problem

The security of Elliptic Curve Cryptosystems relies on the difficulty of the Elliptic Curve Discrete Logarithm Problem(ECDLP). The ECDLP is as follows:

The fastest algorithm to compute \(k\) currently is a combination of the Pohlig-Hellman attack and the Pollard Rho algorithm.

I usually make the elliptic curve in Sage.

sage: p = 31
sage: E = EllipticCurve(GF(p), [2,3])
sage: E
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 31

Let \(P=(8, 29)\) and \(Q=(30,0)\). If we want to know \(k\), just bruteforce \(k\), 1 to 31.

sage: Q==8*P
True

Pohlig-Hellman Attack

The group \(E(\mathbb{F}_{p})\) is obviously a finite group and it has no more than \(2p+1\) points. The order of \(E(\mathbb{F}_{p})\) is defined as \(\#E(\mathbb{F}_{p})\).

sage: E.order()
32

The Pohlig-Hellman attack simplifies the problem of solving the ECDLP in \(E(\mathbb{F}_{p})\) to solving the ECDLP in the prime subgroups of \(\langle P\rangle\), the subgroup generated by \(P\).

Let \(n\) be the order of \(E(\mathbb{F}_{p})\).

We want to find \(k_{i}\equiv k\mod p_{i}^{e_{i}}\) for each prime and solve the \(k\) using the Chinese Remainder Theorem.

To do this let \(P_{0}=\cfrac{n}{p_{i}^{e_{i}}}P\) and \(Q_{0}=\cfrac{n}{p_{i}^{e_{i}}}Q\).

Then, \(P_{0}\) has order \(p_{i}^{e_{i}}\) since \(p_{i}^{e_{i}}P_{0}=nP\).

Therefore, \(Q_{0}=k_{i}P_{0}\) and we can solve \(k_{i}\) by bruteforcing \(1\) to \(p_{i}^{e_{i}}\).

Actually, this is not a pohlig-hellman attack yet. But it’s hard to explain everything at once, so first of all, you should know that this is the extent of the attack.

Example 1

Although I don’t exaplain the whole of Pohlig-Hellman attack, this attack can be quite tricky to you so I’ll give you an example.

sage: p = 37
sage: E = EllipticCurve(GF(p), [1, 4])
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 37
sage: E.order()
28

The order of \(E\) is 28.

sage: P
(6 : 2 : 1)
sage: Q
(27 : 20 : 1)

Let’s find the \(k\) that satisfies \(Q=k\cdot P\).

If we don’t know Pohilg-Hellman attack, we just bruteforce the \(k\).

sage: for k in range(0, E.order()):
....:     if k*P == Q:
....:         print(k)
....:         break
....:     
17

Easy, isn’t it? But if we make the prime field with the big prime, bruteforcing is impossible.

Now, we know the Pohlig-Hellman attack! Let’s use it.

First, factorize the order. \(28=2^{2}\cdot 7\).

Let’s find the \(k_{0}\), \(k_{1}\) that satisfies \(k_{0}\equiv k\mod {2^{2}}\), \(k_{1}\equiv k\mod {7}\)

sage: n = E.order()
sage: P0 = (n//2^2)*P
sage: Q0 = (n//2^2)*Q
sage: for k0 in range(0, 2^2):
....:     if k0 * P0 == Q0:
....:         print(k0)
....:         break
....:     
1

sage: P1 = (n//7)*P
sage: Q1 = (n//7)*Q
sage: for k1 in range(0, 7):
....:     if k1 * P1 == Q1:
....:         print(k1)
....:         break
....:     
3

By CRT(Chinese Remainder Theorem), \(k=17\).

Is everything OK? Let’s see the real Pohlig-Hellman attack.

We want to find \(k_{i}\equiv k\mod p_{i}^{e_{i}}\) for each prime and we do this by representing \(k_{i}\) such that \(k_{i}=z_{0}+z_{1}p_{i}+z_{2}p_{i}^{2}+ \dots +z_{e-1}p_{i}^{e-1}\) and then compute each \(z_{j}\) in sequence.

To do this let \(P_{0}=\cfrac{n}{p_{i}}P\) and \(Q_{0}=\cfrac{n}{p_{i}}Q\).

Then, \(P_{0}\) has order \(p_{i}\) since \(p_{i}P_{0}=nP\). Therefore, \(Q_{0}=z_{0}P_{0}\) and we can solve \(z_{0}\) by bruteforcing \(1\) to \(p_{i}\).

We can get each \(z_{j}\) by solving \(Q_{j}=z_{j}P_{0}\) where

Then CRT!

Example 2

sage: p = 113
sage: E = EllipticCurve(GF(p), [2, 5])
sage: E
Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 113
sage: n = E.order()
sage: n.factor()
2^2 * 3^3

sage: P
(23 : 50 : 1)
sage: Q
(10 : 102 : 1)

Let’s find the \(k_{0}\), \(k_{1}\) that satisfies \(k_{0}\equiv k\mod {2^{2}}\), \(k_{1}\equiv k\mod {3^{3}}\)

We can represent \(k_{0} = z_{0}+2z_{1}\).

sage: P0 = (n//2)*P
sage: Q0 = (n//2)*Q
sage: for z0 in range(0, 2):
....:     if z0 * P0 == Q0:
....:         print(z0)
....:         break
....:     
1
sage: Q1 = (n//2^2)*(Q-z0*P)
sage: for z1 in range(0, 2):
....:     if z1 * P0 == Q1:
....:         print(z1)
....:         break
....:     
1

sage: P0 = (n//3)*P
sage: Q0 = (n//3)*Q
sage: for z0 in range(0, 3):
....:     if z0 * P0 == Q0:
....:         print(z0)
....:         break
....:     
2
sage: Q1 = (n//3^2) * (Q - z0*P)
sage: for z1 in range(0, 3):
....:     if z1 * P0 == Q1:
....:         print(z1)
....:         break
....:     
2
sage: Q2 = (n//3^3) * (Q-z0*P-z1*3*P)
sage: for z2 in range(0, 3):
....:     if z2 * P0 == Q2:
....:         print(z2)
....:         break
....:     
1

By CRT, \(k=71\).

If you are a good coder, this process will be simpler!

If you see my first references, Weak Curves in Elliptic Curve Cryptography, there is a simple code in sage.

Conclusion : If the order of elliptic curve has only small prime cofactors, ECDLP is easily to solve!

References

Weak Curves In Elliptic Curve Cryptography

An Introduction to the Theory of Elliptic Curves