2
$\begingroup$

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.

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

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
$\endgroup$
  • $\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 May 14 at 17:17
  • $\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$ – Samuel Neves May 14 at 17:18
1
$\begingroup$

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.

$\endgroup$

protected by Community May 14 at 14:38

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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