smart_attack.sage

'''My idea was to generate a curve Ep with #Ep=p. This is an anomalous curve, and using Smart’s attack, the discrete log problem can be moved to solving a simple division by lifting the curve of the p-adics, which is just division! Then after making one curve easy, I would keep generating primes p until I found a (q,a,b) where Eq

had a smooth order, allowing us to solve the discrete log easily.
Generating anomalous curves

I refered to Generating Anomalous Elliptic Curves to generate anomalous curves, and iterated through all primes p
where Ep was anomalous. If q=2p+1 was prime, then I stored the tuple (p,a,b) in a list. I did this until I had plenty of curves to look through.

If the order of a curve defined over a field Fp is equal to p, then that means the curve is anomalous, and there's an attack (called Smart's attack) that we can apply to solve the discrete log easily. So we can apply this to the curve defined over Fp. This also implies that every point generated by the curve also has an order of p

.

For the other curve defined over Fq
, notice that the order is somewhat smooth, meaning that the number can be decomposed into small-ish primes. Other than the last prime factor, the other numbers are fairly small primes. This kind of smooth order implies the Pohlig Hellman attack, where we solve the discrete log problem by solving the discrete log over the subgroups of the group generated by the point G.


'''

# http://www.monnerat.info/publications/anomalous.pdf
D = 19
j = -2^15*3^3

def anon_prime(m):
    while True:
        p = (19*m*(m + 1)) + 5
        if is_prime(p):
            return m, p
        m += 1

curves = []
def anom_curve():
    m = 2**61 + 2**60 # chosen so the curves have bit length 128
    while True:
        m, p = anon_prime(m)
        a = (-3*j * inverse_mod((j - 1728), p)) % p
        b = (2*j * inverse_mod((j - 1728), p)) % p
        E = EllipticCurve(GF(p), [a,b])
        
        if E.order() == p:
            G = E.gens()[0]
            print(f'Found an anomalous prime of bit length: {p.nbits()}')
            if is_prime(2*p + 1):
                print(f'Found an anomalous prime with safe prime q = 2p+1. p={p}')
                if p.nbits() != 128:
                    exit()
                curves.append([p,a,b])
                print(curves)
        m += 1


# one of this curve has smooth order
for param in curves:
    p, a, b = param
    q = 2*p + 1
    E1 = EllipticCurve(GF(p), [a,b])
    E2 = EllipticCurve(GF(q), [a,b])
    assert E1.order() == p
    print(factor(E2.order()))


# performing smart attack
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)

# print(SmartAttack(G,rG,p))  Q = rG --> find r