A new approach, a new attack. Can you attack this curve?

Files given:

• output.txt
• double_miff.py

def onmiff(a, b, p, G):
	x, y = G
	return (a*x*(y**2 - 1) - b*y*(x**2 - 1)) % p == 0

l = len(flag) // 2
m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])

assert m1 < (p // 2) and m2 < (p // 2)
assert onmiff(a, b, p, P) and onmiff(a, b, p, Q)
assert P[0] == m1 and Q[0] == m2

print(f'P + Q = {addmiff(P, Q)}')
print(f'Q + Q = {addmiff(Q, Q)}')
print(f'P + P = {addmiff(P, P)}')

The python file uses the flag to generate points on the curve over where are unknown. It then outputs the points .

To compute , we rewrite the equations as

then we know that the matrix must have determinant mod . This gives us three values that must be mod , hence we can get a multiple of . By taking the largest prime factor of all the determinants, we obtain a likely value of .

From this value of , we can easily compute the values of as well.

Since this curve is an elliptic curve, we can use sage's vast library of functions to obtain from :

QQp.<x,y,z>=PolynomialRing(QQ)
r_pol = QQ(a)*x*(y**2 - 1) - QQ(b)*y*(x**2 - 1)
h_pol = r_pol.homogenize(var=z)
phi = EllipticCurve_from_cubic(h_pol)
E = phi.codomain().change_ring(FF)
tocurve = lambda a,b:E([i.change_ring(FF).subs(x=a,y=b,z=1) for i in phi.defining_polynomials()])
fromcurve = lambda a,b: (lambda P:[i/P[-1] for i in P[:-1]])\
    ([i.change_ring(FF).subs(x=a,y=b,z=1) for i in phi.inverse().defining_polynomials()])

PQ = tocurve(*PQ)
P2 = tocurve(*P2)
Q2 = tocurve(*Q2)

print([bytes.fromhex(hex(fromcurve(*i.xy())[0])[2:]) for i in P2.division_points(2)])
print([bytes.fromhex(hex(fromcurve(*i.xy())[0])[2:]) for i in Q2.division_points(2)])

and this gives us the flag

Solution at solve.sage