PohligHellman Attack in ECDLP
Elliptic Curves
In its more general form, an Elliptic Curve is a curve defined by an equation of the form
\[y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}\]over some field F.
For example,
\[y^{2}=x^{3}3x+4\]\(E(F)\) defines a set of points that satisfy the elliptic equation in the field \(F\).
\[E(F) = \{(x,y)\in F^{2}: y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}\} \cup \{\mathcal{O}\}\]\(\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.
\[y^{2}=x^{3}+ax+b\]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\).

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

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

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!
\[P+(P) =\mathcal{O}\]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 PohligHellman 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
PohligHellman 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 PohligHellman 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})\).
\[n=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdots p_{r}^{e_{r}}\]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 pohlighellman 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 PohligHellman 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 PohilgHellman 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 PohligHellman 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 PohligHellman 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_{e1}p_{i}^{e1}\) 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
\[Q_{j}=\cfrac{n}{p_{i}^{j+1}}(Qz_{0}Pz_{1}p_{i}P\cdots z_{j1}p_{i}^{j1}P)\]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)*(Qz0*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) * (Qz0*Pz1*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