Rating:
We have an elliptic curve over a non-prime field. The goal is to find the y coordinate of a point given the x coordinate.
$$y^2 \equiv x^3 + ax + b\ (mod\ n)$$
First factor n:
```
sage: n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
sage: ecm.factor(n)
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
690712633549859897233,
690712633549859897233,
690712633549859897233,
690712633549859897233,
690712633549859897233,
690712633549859897233,
651132262883189171676209466993073,
651132262883189171676209466993073,
651132262883189171676209466993073,
651132262883189171676209466993073,
651132262883189171676209466993073]
```
n = 2^63 * 690712633549859897233^6 * 651132262883189171676209466993073^5
Now I modified sympy's function to find sqrt mod n.
```python
from sympy.ntheory.residue_ntheory import _sqrt_mod_prime_power, _product
from sympy.polys.galoistools import gf_crt1, gf_crt2
from sympy.polys.domains import ZZ
from Crypto.Util.number import long_to_bytes
def sqrt_mod_n(a, factors_of_n):
v = []
pv = []
for px, ex in factors_of_n.items():
if a % px == 0:
rx = _sqrt_mod1(a, px, ex)
else:
rx = _sqrt_mod_prime_power(a, px, ex)
v.append(rx)
pv.append(px**ex)
mm, e, s = gf_crt1(pv, ZZ)
sqrts = []
for vx in _product(*v):
r = gf_crt2(vx, pv, mm, e, s, ZZ)
sqrts.append(int(r))
return sqrts
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
for r in sqrt_mod_n(x**3 + a*x + b, {2:63, 690712633549859897233:6, 651132262883189171676209466993073:5}):
flag = long_to_bytes(r)
if b"CCTF" in flag:
print(flag.decode())
```