solve.sage

from math import isqrt, gcd
from Crypto.Util.number import *

# Reference paper https://eprint.iacr.org/2022/1241.pdf
# Idea is basically continued fraction as hinted in challenge title
def phi_0(n, N):
    # phi_n,0(N)
    x1 = ((isqrt(N)**n-1)/(isqrt(N)-1))**2/2
    x2 = ((isqrt(2*N)**n-1)/(isqrt(2*N)-1))/2 * (((isqrt(2*N)/2)**n-1)/(isqrt(2*N)/2-1))
    return x1 + x2

def solve(n, N, e):
    phiN = phi_0(n, N)
    c = continued_fraction(Integer(e)/phiN)
    for i in range(1, 1000):
        k = int(c.numerator(i))
        d = int(c.denominator(i))
        if (e*d-1) % k == 0 and k > 2**10:
            # print(f"Guessed phi: {(e*d-1) // k}")
            # print(f"Guessed d: {d}")
            # print(f"i = {i}")
            return d

d = []

N = 97612005002255328088089410975523983681740354800179039894937915732930244664586629120094932234362725524185511994009850035922533559839893979074939037832668549750255468381192887812469917667115839541015495242839376266431038121426628287675447989631207259597586333251571969522037989427555616133183042678577218636039
e = 76116130167787561359953887266200869082448529331107937460219287530308978477708991999616543343406382355689250048669403437942401267295685636067522489421767819007148067769751457394505797110602169754511939818788483430730012575308299189299157812591392734160576417069436538119185074252625496946207312639052459476691
d.append(solve(2, N, e))
N = 82898492840033848499679066573599199466262845944574446435099699953454086638324386416129279494828609729766998439132172194894188387716844097335523066318666261933348513791114624155336437054163128912934864480178839237943154511986161169068625070999701692457965233641625122455113801192492673037347038351956273261209
e = 4209437149177720414392052396995336370571472638739290885909782621676928212352728218779571626530884770305850882606520062302514835362331092897621059096111410844919671863579044484955054277159466422627065939698416080746679841734383574957303171143150437215717944527004524163060734647488552780385109395365103554265493136383680197786179491825415327877829363932241445886199163804911851983235568877189260370900147226881457732043676609664875472514523869518158935427849891304397052900751093562294098001282747462255107311383605819243052786444806092296448159814920695343700003324553167747140120222023780385726663202175975632841101
d.append(solve(3, N, e))
N = 74994178474501705271671940639744064973727732038326591115828216310018498822567967944888584927591599150655580137956560356301728244890598527629795727836492659456865084635190916504902969902122979161893704294891200235692036639700141954229504462610034653592940594511895628524050995435988759181763969824436031245313
e = 1489343297993123282242703585767862889532966168614466114229659752495521741344828171911376172581419167249138037648594483979411817592040147160238477726426615905245322859547191851844862266610905034585090032979459885344332508376146458008432418485138745167332564668471655885462387844870978937353124271354756749987557641173034038037138552554286596191926276854019397533360181392329678995160770713221738607291949604788483647158238145885370267789175042383720834228546234687195524802723091258548142868749009819341250311783811669486498714774091479332840123020791916467567722826634424992913028930995948675696110790085249624326162007313472329046629836566951986389110657545671708876118803228632059850860536273457909861781873059134865932188230401277356396602494704882757454481213539839098539947582560234411030973307998825870210215033177749651750411682404527804606701340350999128273688467096980925538961234964285918052638858734125375270072587641505250814286217419987349217586276836222849825473745401814287955844160842207855608228330415022147681694596413651097936005515497301045029721788331269208281455180641244748905469345705931987679143863830321305138722585532495234826613572876602582994268211475793765951624522296606385747914811802020368502982841323574845193182348705392733364068634167943152196883988138300398486795444947317920558342244022638552596544997423504070874736567161433560622253197613565603458736833008516912312579020461040855359316882678726669756450813443842584222951463074601799430267187315529031340358497011459213690622999701314023178557960651
d.append(solve(6, N, e))

d = [int(x) for x in d]
# print(d)

'''
Flag is broken to a, b, c
a*d[0]^2 + b*d[0] + c = x
a*d[1]^2 + b*d[1] + c = y
a*d[2]^2 + b*d[2] + c = z
'''
x = 12885959655953139374785717692048211268233398655222955130228721746869891559409080848367142483157517829612928194235174347299097615553919212787225377729454255371358309685093996459461793296183459238094074717707949401000365552082820354011
y = 23144924364202496361036242964551729244108242071387074122924446048219898057065538815277890013860024253422666710259842325295228086904295846675276536535237894072110755426259617054492417613772645109337095876879440959135444974146373938103
z = 10216090816848970230135050433869173852319169856151418349231810820430643701522230150158652915588855848669985626642166987135416343716291162149831827545892183798838168834007800941773301995075510960084628367588300016798178754792796044603
A = Matrix([[d[0]^2, d[0], 1], [d[1]^2, d[1], 1], [d[2]^2, d[2], 1]])
b = vector([x, y, z])
x = A.solve_right(b)
# print(x)

print("".join([long_to_bytes(int(x[i])).decode() for i in range(3)]))