Power Up (AtHackCTF) solution

solve.sage

import itertools
from pathlib import Path


def tonelli3(a,p,many=False):
    def solution(p,root):
        g=p-2
        while pow(g,(p-1)//3,p)==1: g-=1  #Non-trivial solution of x**3=1
        g=pow(g,(p-1)//3,p)
        return sorted([root%p,(root*g)%p,(root*g**2)%p])

    a=a%p
    if p in [2,3] or a==0: return [a]
    if p%3 == 2: return [pow(a,(2*p - 1)//3, p)] #One solution

    #No solution
    if pow(a,(p-1)//3,p)>1: return []

    #p-1=3**s*t
    s=0
    t=p-1
    while t%3==0: s+=1; t//=3

    #Cubic nonresidu b
    b=p-2
    while pow(b,(p-1)//3,p)==1: b-=1

    c,r=pow(b,t,p),pow(a,t,p)
    c1,h=pow(c,3**(s-1),p),1
    c=pow(c,p-2,p) #c=inverse modulo p

    for i in range(1,s):
        d=pow(r,3**(s-i-1),p)
        if d==c1: h,r=h*c,r*pow(c,3,p)
        elif d!=1: h,r=h*pow(c,2,p),r*pow(c,6,p)
        c=pow(c,3,p)

    if (t-1)%3==0: k=(t-1)//3
    else: k=(t+1)//3

    r=pow(a,k,p)*h
    if (t-1)%3==0: r=pow(r,p-2,p) #r=inverse modulo p

    if pow(r,3,p)==a:
        if many:
            return solution(p,r)
        else: return [r]
    else: return []

def long_to_bytes(n):
    bi = bin(n)[2:]
    bi = '0'*(-len(bi)%8) + bi
    o = []
    for i in range(0, len(bi), 8):
        x = int(bi[i:][:8], 2)
        o.append(x)
    return bytes(o)

def bytes_to_long(b):
    a = 0
    for x in b:
        a <<= 8
        a |= x
    return a

e = 0x10001
n = 2878484237144058957039174874624090770599900489784647154744423901387428048184111906123929155824159
p, q, r = 155191288826882271830043206382359, 116912239795315244984923068717187, 158648706275555173588212318392723
assert n == p * q * r
assert p != q and q != r and p != r
phi = (p-1) * (q-1) * (r-1)
c = bytes_to_long(Path('output.bin').read_bytes())
assert c == 2752038986049592181723384951865337963659457489663088773309001862032268491249904286559337569484222
m3 = pow(c, pow(e, -1, phi), n)
b = [p, q, r]
for a0 in tonelli3(m3, b[0], True):
    for a1 in tonelli3(m3, b[1], True):
        for a2 in tonelli3(m3, b[2], True):
            a = [int(a0), int(a1), int(a2)]
            print(long_to_bytes(crt(a, b)))