# Why Smart's attack doesn't work on this ECDLP?

The Problem is as follows:

sage: p=235322474717419
sage: a=0
sage: b=8856682
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(200673830421813, 57025307876612)
sage: Q = E(40345734829479, 211738132651297)
sage: P.order() == p
True


As we can see, P.order() is equal to p, so obviously we can use Smart's attack to calculate the value of k, so i implement the Smart's attack according to the paper Weak Curves In Elliptic Curve Cryptography.

And when we use this kind of attack we will get k = 9762415993955:

sage: SmartAttack(P,Q,p,8)
9762415993955


But actually the correct value of k is 152675955744921:

sage: P*152675955744921 == Q
True


So my question is:

Why Smart's attack doesn't work on this ECDLP?

P.S. The implement of Smart's attack is correct cuz it can calculate the correct value of k in some former CTF games.

• The Smart's attack works when the trace is 1 i.e the order of the EC group is equal to the order of the scalar ring. Here both are $p$. May 10 '19 at 13:43
• Thanks for your reply, but why Smart's attack doesn't work? May 10 '19 at 13:48
• Is there something wrong ?If the sssa attack can't work.How did you get the correct value of k is 139189752582973. I try sssa attack on it.And i get k is 139189752582973 rather than 165356703608039. May 11 '19 at 12:48
• i use discrete_log_rho() in sagemath to get k = 139189752582973, could you please show me how did you get the correct value of k? I implement the Smart's attack according to this paper above. May 12 '19 at 6:29

The reason the attack does not work is because you are hitting a special case—the canonical lift. This is the case where the lifted curve over $$\mathbb{Q}_p$$ is isomorphic to the curve over $$\mathbb{F}_p$$, in which case no additional information can be extracted from it. The journal version of Smart's paper mentions this case.

The solution is simple: if we are hitting a special lift, randomize the lift! We can do this by lifting to the $$\mathbb{Q}_p$$ curve $$y^2 = x^3 + (p\cdot a')x + (8856682 + p\cdot b')$$, for some arbitrary $$a'$$ and $$b'$$, which reduces all the same modulo $$p$$, but will be unlikely to hit the same issue. So we can easily rewrite the attack as

def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break

Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break

p_times_P = p*P_Qp
p_times_Q = p*Q_Qp

x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()

phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)


which now succeeds:

sage: p=235322474717419
sage: a=0
sage: b=8856682
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(200673830421813, 57025307876612)
sage: Q = E(40345734829479, 211738132651297)
sage: assert(P.order() == p)
sage: n = SmartAttack(P, Q, p)
sage: assert(n*P == Q)
sage: n
152675955744921

• Samuel, why is the comment above not required anymore? Is it answered with the edit? If so, how? Or do you see it as a different question? May 14 '19 at 17:17
• I fixed the reason why it wasn't working. Also, these parameters are part of some Chinese challenge, so I replaced all parameters in the question and answer with random ones, to avoid the solutions being triviallly Googleable. May 14 '19 at 17:18

There are more than one method to solve efficiently the discrete logarithm on anomalous elliptic curves. One of them (in the link you gave) is to lift the curve to $$p$$-adic numbers. The other consist simply to add slopes of lines during computation of $$pP$$ et $$pQ$$ with any scalar multiplication algorithm. I cannot explain why the first method doesn't seem to work in this example since I am not really familiar enough with $$p$$-adic numbers, but I can explain the second one below with more details.

• Points on the curve are associated with one more values in $$\mathbf F_p$$. Example : $$[P_1, \alpha_1]$$, $$[P_2,\alpha_2]$$.
• The addition of two points needs to take care of this new value in this way with an augmented addition which we will note $$\oplus$$: $$[P_1, \alpha_1] \oplus [P_2, \alpha_2] = [ P_1 + P_2, \alpha_1 + \alpha_2 + a_0(P_1,P_2)],$$ where the function $$a_0$$ returns the slope of the line that goes through the two points (or $$0$$ if one of the points is the infinity point or if the line is vertical).
• Now we can compute $$p[P,0]$$ and $$p[Q,0]$$ with the augmented addition (a simple double-and-add do the work) and we get respectively $$[\infty, \alpha]$$ and $$[\infty, \beta]$$ where the values $$\alpha$$ and $$\beta$$, viewed as integers, satisfy the relation $$\beta P = \alpha Q,$$ and we get the discrete logarithm by multiplying $$\beta$$ with the inverse mod $$p$$ of $$\alpha$$ for a total complexity $$O(\log p)$$.

Why it works is a little bit more complicated to explain here, but some informations can be found here and here.