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())
```