Smart Attack

🐀🐀搞不懂捏，记录一下方便查阅

Smart Attack适用于椭圆曲线的阶和模数一样的情况

paper里的原文如下：

for some integer m. It would be nice to be able to apply a “logarithm” map to the above equation and hence solve the discrete logarithm problem. Such a “logarithm” would be a homomorphism from the group , into a group for which solving the logarithm problem is easy, such as . However, no such logarithm map is known which is defined on curves over , however, such a map is known for curves over .

假设在一个曲线E（有限域为）上有点 和 ，要解决，步骤如下：

1. 将 、两点用 Hensel’s lemma 提升到p的p适域上，并计算其坐标，记为和。在p适域上，x坐标不变，y坐标表示为p进制展开的无穷级数。
2. 计算和，记为和。
3. 计算和。（x()表示点的x坐标，y()表示点的y坐标）

# sagemath
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)