为什么Smart的攻击在ECDLP上不起作用？

Question

问题如下：

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

正如我们所看到的，P.order()等于p，所以很明显我们可以使用智能攻击来计算k的值，所以我根据论文椭圆曲线密码学中的弱曲线实现了智能攻击。

当我们使用这种攻击时，k= 9762415993955：

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

但实际上，k的正确值是152675955744921：

sage: P*152675955744921 == Q
True

所以我的问题是：

为什么Smart的攻击在ECDLP上不起作用？

智能攻击的实现是正确的，因为它可以计算一些以前的CTF游戏中k的正确值。

Answer 1

攻击不起作用的原因是因为你碰到了一个特殊的情况--典型的提升。在这种情况下，\mathbb{Q}_p上的提升曲线与\mathbb{F}_p上的曲线同构，在这种情况下，无法从中提取额外的信息。日刊版本 of Smart的论文提到了这个案例。

解决办法很简单:如果我们碰到一个特殊的升力，随机提升！我们可以通过提升\mathbb{Q}_p曲线y^2 = x^3 + (p\cdot a')x + (8856682 + p\cdot b')来实现这一点，对于一些任意的a'和b'，这减少了所有相同的模块p，但不太可能遇到相同的问题。这样我们就可以轻松地将攻击重写为

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)

它现在成功了：

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