Challenge files

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.

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