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

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)

But actually the correct value of k is 152675955744921:

sage: P*152675955744921 == Q

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.

  • $\begingroup$ 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$. $\endgroup$
    – kelalaka
    Commented May 10, 2019 at 13:43
  • $\begingroup$ Thanks for your reply, but why Smart's attack doesn't work? $\endgroup$ Commented May 10, 2019 at 13:48
  • $\begingroup$ 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. $\endgroup$
    – Hellman
    Commented May 11, 2019 at 12:48
  • $\begingroup$ 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. $\endgroup$ Commented May 12, 2019 at 6:29

2 Answers 2


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]:

    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]:

    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
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes
    Commented May 14, 2019 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 14, 2019 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.