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 - reinstate Monica 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$

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