There is always a starting point, isn’t it?
Files given:
def ison(C, P):
c, d, p = C
u, v = P
return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0
c, d, p = Curve
flag = flag.lstrip(b'CCTF{').rstrip(b'}')
l = len(flag)
lflag, rflag = flag[:l // 2], flag[l // 2:]
s, t = bytes_to_long(lflag), bytes_to_long(rflag)
assert s < p and t < p
P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
print(f'ison(C, P) = {ison(Curve, P)}')
print(f'ison(C, Q) = {ison(Curve, Q)}')
print(f'P = {P}')
print(f'Q = {Q}')
print(f's * P = {peam(Curve, P, s)}')
print(f't * Q = {peam(Curve, Q, t)}')
The code uses the Edwards model of an elliptic curve. First, we can easily solve for \(p,c,d\) as we are given \(6\) points on the curve
\[u^2+v^2-c^2(1+du^2v^2)=0\pmod p\]
by solving \(c,d\) for various pairs of points then taking an appripriate GCD of all the \(c,d\)s.
In order to convert this back into an elliptic curve to use sage functions on, we use the help of mathematica to verify our computations: calc.nb
\[u^2+v^2-c^2(1+du^2v^2)=0\pmod p\] Substitute \(u\to\frac{2cx}y,v\to\frac{c(x-1)}{x+1}\) \[\frac{y^2}{c^4d-1}+x^3-\frac{2(c^4d+1)}{c^4d-1}x^2+x=0\pmod p\] Substitute \(x\to\frac x{1-c^4d}+\frac23\frac{c^4d+1}{c^4d-1},y\to\frac y{1-c^4d}\) \[y^2=x^3+\frac1{27}\left(-9-126c^4d-9c^8d^2\right)x+\frac1{27}\left(-2+66c^4d+66c^8d^2-2c^{12}d^3\right)\]
Now this finally allows us to input the elliptic curve into sage:
sage: a = -(9*c^8*d^2+126*c^4*d+9)/27
....: b = -(2*c^12*d^3-66*c^8*d^2-66*c^4*d+2)/27
....: E = EllipticCurve(FF,[a,b])
....: print(factor(E.order()))
2^2 * 4911931 * 50689183 * 350206513 * 1138886473 * 2275732843
which means discrete log is easy! We can now run discrete log and get the flag quite quickly.
Solution at solve.sage
Flag:
CCTF{nOt_50_3a5Y_Edw4rDs_3LlipT!c_CURv3}