Sneaky_RSA Solver

solver.sage

#!/usr/bin/env sage
from Crypto.Util.number import long_to_bytes

n = 502836922512486610504545362770164087747314568872499828554488035958487618069922372009938568627862332381791785204353412309048442266790788127586913418481611102032369784610186635918107975841710391423008666409824129040501563972923707425783141884753202039153453753743392862691624406109086024607836030202826295630221116437441121382375260821932448574939909495800160786027658225717271401949960794363690329988511853563276529456313673706170640973867577950303263264174744662074209624615772736887075860916876858014327808943244020378093080950653168444374777563212489171657106506007764866226182751595372496526204915222217458440333
c = 454299223081792062362266220272909342019088865255924397686063995369782539258602100653334224583697202750174516779986136385042681109098618245901753010482912126772319800524707384204412864735122227332558561469933425891929047574263342649505707030588755665342779116075595839226683446035639065221099312344027251296278816044435598483785519251184553119911948247021102493061312736949663223013577741782565723976032198127768131782494362406604566816919581212956442519613286856721248569706006200392439016984851104716207808412808617170072535735227141363960654334580183781101395963792191724146280446583964397787403023719275569361303

primes = []

cnt = 8 # p * q * r**2 * s**4
while n != 1:
    a = n.nth_root(cnt, truncate_mode=1)[0] # a = gmpy2.iroot(n, cnt)[0]
    while n % a != 0:
        a = next_prime(a) # a = gmpy2.next_prime(a)

    acnt = 0
    while n % a == 0:
        n //= a
        acnt += 1

    cnt -= acnt
    primes.append( (a, acnt) )

sqrts = []

for (p, pcnt) in primes:
    sqrts.append( mod(c, p^pcnt).sqrt(all=True) )

def backtrack(v, idx, sqrts):
    if idx == len(sqrts):
        s = long_to_bytes(v)
        if s.startswith("FLAG{"):
            print(s)
            exit(0)
        return

    for u in sqrts[idx]:
        backtrack(v.crt(u), idx + 1, sqrts)

backtrack( mod(0, 1), 0, sqrts)

# FLAG{Was_this_challenge_tricky_or_sneaky?_My_cat_also_knows_rabin_cryptosystem_and_hensel_lifting_We_also_need_some_looooooooooooooooooooooooooooooooooong_flag}