maple3142 · September 3, 2023 13:52
diff --git a/challenge.py b/challenge.py
 from Crypto.Util.number import bytes_to_long, getStrongPrime, isPrime

 SIZE = 512
 e = 65537

 with open("flag.txt", "rb") as f:
    m = bytes_to_long(f.read())


 def encrypt(m):
    while True:
        p = getStrongPrime(SIZE)
        if p % 4 != 3:
            continue
        q = p**2 + 1
        assert q % 2 == 0
        if isPrime(q // 2):
            break

    r = getStrongPrime(SIZE * 3)
    n = p * q * r
    c = pow(m, e, n)
    return n, c

 if __name__ == "__main__":
    n0, c0 = encrypt(m)
    n1, c1 = encrypt(c0)
    n2, c  = encrypt(c1)
    
    assert m < n0 and c0 < n1 and c1 < n2

    print(f"{n0 = }")
    print(f"{n1 = }")
    print(f"{n2 = }")
    print(f"{c = }")
diff --git a/solve1.sage b/solve1.sage
 # polynomials of this form are found from https://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf

 def xfactor(n):
    # works for n0, n2
    x = ZZ["x"].gen()
    fm = x ^ 4 + x ^ 3 + 2 * x ^ 2 - 4 * x + 3
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        Q = R.quo(x ^ 4 + x ^ 3 + 2 * x ^ 2 - 4 * x + 3)  # (x+10)^4%13
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[2]), n)
        if 1 < g < n and g != 2:
            if g % 2 == 0:
                g = g // 2
            return g


 def xfactor2(n):
    # works for n0, n2
    x = ZZ["x"].gen()
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        Q = R.quo(x ^ 4 + x ^ 3 + 6 * x ^ 2 + 4 * x + 7)  # (x+7)^4%9
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[2]), n)
        if 1 < g < n and g != 2:
            if g % 2 == 0:
                g = g // 2
            return g


 def xfactor3(n):
    # works for n2
    x = ZZ["x"].gen()
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        Q = R.quo(x ^ 4 + 2 * x ^ 3 + 12 * x ^ 2 + 11 * x + 4)  # (x+11)^4%21
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[3]), n)
        if 1 < g < n and g != 2:
            if g % 2 == 0:
                g = g // 2
            return g


 def xfactor4(n):
    # works for n2
    x = ZZ["x"].gen()
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        Q = R.quo(x ^ 4 + 3 * x ^ 3 + 6 * x ^ 2 + 3 * x + 15)  # (x+6)^4%21
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[1]), n)
        if 1 < g < n and g != 2:
            if g % 2 == 0:
                g = g // 2
            return g


 def xfactor5(n):
    # works for n0, n2
    x = ZZ["x"].gen()
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        Q = R.quo(x ^ 4 + 2 * x ^ 3 + 16 * x ^ 2 + 15 * x + 20)  # (x+15)^4%29
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[3]), n)
        if 1 < g < n and g != 2:
            if g % 2 == 0:
                g = g // 2
            return g


 def xfactoridk(n):
    x = ZZ["x"].gen()
    k = 4
    R = Zmod(n // 2)["x"]
    while True:
        # Q = R.quo(R.random_element(k))
        m = 4 * randint(1, 10) + 1
        Q = R.quo((x + randint(1, m)) ^ 4 % m)
        t = Q.random_element() ^ n
        for r in t:
            g = gcd(ZZ(r), n)
            if 1 < g < n and g != 2:
                if g % 2 == 0:
                    g = g // 2
                return g


 n0 = 2225430931171742309590021519105966475844903120525251695523178697527164517579408722711234826878134715797958935338297220265219226300894104569683398115477309720146133327771551725898555731073195872615344013293830504833975586322888278505407028728358704076958757010651157187703590446070184475402381423002650018961176138080716492888165846018003948098783356464323529675777057669124960883202381329499903833929145776324767105873925604946203377344270453210673160949689173847913552580965627850373944000352535059741109945493930667082352120467668696892025338540674581804184012586508599980388614005841857756073388547010787419566713640593253393760294361380501268647194072700469161564801422062289612799077904053452873270626350344212851096671449544321083683295414578870019009973045854170182382727860252857661748412713089966679619926823123247413785351460232424404830410781479607957931804764853243150370282741306050098774071355352739054474451634
 n1 = 2902329412270422842046535537001829377101537009153437279635535810278434063798803011470300739477859973827804786523545631179151215334688591839100812419605935760343991435071529882290299578846926467539408283727659051727132824597767222204754385000922681803386720819376465332388864543914078985294145479810606939222216383992286555895625853236491670375192622257155324284843244985545335465287362978215468434024271360080629114844889632675838906705328434449254889213297204035441822688091905656285656394151888204813879831078518928280869696466456390295366642520858089743604875788588249336171615693244751835983410852651127201544553612939088629003265218371417691048176635309364177044766701358377699795232952223152202935931059435421693779930916345845000682337073473149480724440072954904488040982778824725894449815768323509113465949295885603507498264370200923890015168241317006892330098266102128139597393563667677149651852497591025375864995894
 n2 = 2698475686226075727922875574386187058823492611476922860002358023029458657639771046953188201255060157568452129035734125439148211777113077172699940634324873324215170011819062645840127796875859469544990957728137431988601270975684770637979035052867477977135046888339850058116075131487036010413025295336351318831932946017313896447399626404226081450654480696921933686024836824222725331434630860814073299971171985338695128471382400248446104698091918097284406685177571757576346104366533260396493391152625570996491323167431913429943280452394061818054700358743295078061379642722526722798849978301919288950925184032065663817295192580893874999752693149611358550350818715304128021388607152904308446247044586483671654400663194258959113083519729557346058033091028387951702363249337821312037811112961745545487386151697928672795052978212263588647246581101365061877097109610041442299782938306502554711766258351303138088215251384602023526008306
 c = 455863941518777164711770638979677880927658884443865631033897785343512024881240506534356967942892027877135486160509476701275815929848009398883449015317262269637078789489300868180050247683134640577557921243140012052769671350276575359906209128022339484800125461286625807989539284512845543800050389821886658291410385822676589559167498095507901135565361739054522943630178652900330646157249631289777807329635511930165179798945740623391647529488849119945002536479271720932005411578811021167696333363450291124963171113696111175552039612491025708563452996748563325978371575392639525343252323936250405264810240402204231449417720360563959912594724161981999949790954676689174892668918502596075232694999802765416963512949372636906834074116898300028734808122746800724758981906759390103788098490346680322106983439986634895869391836228573537087341579101170066428103231030001696195855900811066771366634772538895069431962669344145287299078725
 p0 = xfactor(n0)
 p1 = xfactoridk(n1)
 p2 = xfactor(n2)
 q0 = p0 ** 2 + 1
 q1 = p1 ** 2 + 1
 q2 = p2 ** 2 + 1
 r0 = n0 // (p0 * q0)
 r1 = n1 // (p1 * q1)
 r2 = n2 // (p2 * q2)
 assert p0 * q0 * r0 == n0
 assert p1 * q1 * r1 == n1
 assert p2 * q2 * r2 == n2
 phi0 = (p0 - 1) * (q0 // 2 - 1) * (r0 - 1)
 phi1 = (p1 - 1) * (q1 // 2 - 1) * (r1 - 1)
 phi2 = (p2 - 1) * (q2 // 2 - 1) * (r2 - 1)
 e = 65537
 d0 = pow(e, -1, phi0)
 d1 = pow(e, -1, phi1)
 d2 = pow(e, -1, phi2)
 c1 = pow(c, d2, n2)
 c0 = pow(c1, d1, n1)
 m = pow(c0, d0, n0)
 flag = int(m).to_bytes(512, 'big').strip(b'\x00')
 print(flag)
 # WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}
diff --git a/solve2.sage b/solve2.sage
 n0 = 2225430931171742309590021519105966475844903120525251695523178697527164517579408722711234826878134715797958935338297220265219226300894104569683398115477309720146133327771551725898555731073195872615344013293830504833975586322888278505407028728358704076958757010651157187703590446070184475402381423002650018961176138080716492888165846018003948098783356464323529675777057669124960883202381329499903833929145776324767105873925604946203377344270453210673160949689173847913552580965627850373944000352535059741109945493930667082352120467668696892025338540674581804184012586508599980388614005841857756073388547010787419566713640593253393760294361380501268647194072700469161564801422062289612799077904053452873270626350344212851096671449544321083683295414578870019009973045854170182382727860252857661748412713089966679619926823123247413785351460232424404830410781479607957931804764853243150370282741306050098774071355352739054474451634
 n1 = 2902329412270422842046535537001829377101537009153437279635535810278434063798803011470300739477859973827804786523545631179151215334688591839100812419605935760343991435071529882290299578846926467539408283727659051727132824597767222204754385000922681803386720819376465332388864543914078985294145479810606939222216383992286555895625853236491670375192622257155324284843244985545335465287362978215468434024271360080629114844889632675838906705328434449254889213297204035441822688091905656285656394151888204813879831078518928280869696466456390295366642520858089743604875788588249336171615693244751835983410852651127201544553612939088629003265218371417691048176635309364177044766701358377699795232952223152202935931059435421693779930916345845000682337073473149480724440072954904488040982778824725894449815768323509113465949295885603507498264370200923890015168241317006892330098266102128139597393563667677149651852497591025375864995894
 n2 = 2698475686226075727922875574386187058823492611476922860002358023029458657639771046953188201255060157568452129035734125439148211777113077172699940634324873324215170011819062645840127796875859469544990957728137431988601270975684770637979035052867477977135046888339850058116075131487036010413025295336351318831932946017313896447399626404226081450654480696921933686024836824222725331434630860814073299971171985338695128471382400248446104698091918097284406685177571757576346104366533260396493391152625570996491323167431913429943280452394061818054700358743295078061379642722526722798849978301919288950925184032065663817295192580893874999752693149611358550350818715304128021388607152904308446247044586483671654400663194258959113083519729557346058033091028387951702363249337821312037811112961745545487386151697928672795052978212263588647246581101365061877097109610041442299782938306502554711766258351303138088215251384602023526008306
 c = 455863941518777164711770638979677880927658884443865631033897785343512024881240506534356967942892027877135486160509476701275815929848009398883449015317262269637078789489300868180050247683134640577557921243140012052769671350276575359906209128022339484800125461286625807989539284512845543800050389821886658291410385822676589559167498095507901135565361739054522943630178652900330646157249631289777807329635511930165179798945740623391647529488849119945002536479271720932005411578811021167696333363450291124963171113696111175552039612491025708563452996748563325978371575392639525343252323936250405264810240402204231449417720360563959912594724161981999949790954676689174892668918502596075232694999802765416963512949372636906834074116898300028734808122746800724758981906759390103788098490346680322106983439986634895869391836228573537087341579101170066428103231030001696195855900811066771366634772538895069431962669344145287299078725


 def xfactor(n):
    # idea: elements of order p^2-1 is like GF(p^2)
    # so it should be like a+by for some y, and y^2-a=0
    # so there is probably a good substitution to make y=f(x)
    # since GF(p^4)'s modulus must be degree 4, f(x) must be quadratic
    Z = Zmod(n // 2)
    R = Z["x"]
    while True:
        f = R.random_element(2)
        Q = R.quo(f ^ 2 + Z.random_element())
        t = Q.random_element() ^ n
        g = gcd(ZZ(t[3]), n // 2)
        if 1 < g < n:
            return g


 p0 = xfactor(n0)
 p1 = xfactor(n1)
 p2 = xfactor(n2)
 q0 = p0**2 + 1
 q1 = p1**2 + 1
 q2 = p2**2 + 1
 r0 = n0 // (p0 * q0)
 r1 = n1 // (p1 * q1)
 r2 = n2 // (p2 * q2)
 assert p0 * q0 * r0 == n0
 assert p1 * q1 * r1 == n1
 assert p2 * q2 * r2 == n2
 phi0 = (p0 - 1) * (q0 // 2 - 1) * (r0 - 1)
 phi1 = (p1 - 1) * (q1 // 2 - 1) * (r1 - 1)
 phi2 = (p2 - 1) * (q2 // 2 - 1) * (r2 - 1)
 e = 65537
 d0 = pow(e, -1, phi0)
 d1 = pow(e, -1, phi1)
 d2 = pow(e, -1, phi2)
 c1 = pow(c, d2, n2)
 c0 = pow(c1, d1, n1)
 m = pow(c0, d0, n0)
 flag = int(m).to_bytes(512, "big").strip(b"\x00")
 print(flag)
 # WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}
diff --git a/solve3.sage b/solve3.sage
 import re

 n0 = 2225430931171742309590021519105966475844903120525251695523178697527164517579408722711234826878134715797958935338297220265219226300894104569683398115477309720146133327771551725898555731073195872615344013293830504833975586322888278505407028728358704076958757010651157187703590446070184475402381423002650018961176138080716492888165846018003948098783356464323529675777057669124960883202381329499903833929145776324767105873925604946203377344270453210673160949689173847913552580965627850373944000352535059741109945493930667082352120467668696892025338540674581804184012586508599980388614005841857756073388547010787419566713640593253393760294361380501268647194072700469161564801422062289612799077904053452873270626350344212851096671449544321083683295414578870019009973045854170182382727860252857661748412713089966679619926823123247413785351460232424404830410781479607957931804764853243150370282741306050098774071355352739054474451634
 n1 = 2902329412270422842046535537001829377101537009153437279635535810278434063798803011470300739477859973827804786523545631179151215334688591839100812419605935760343991435071529882290299578846926467539408283727659051727132824597767222204754385000922681803386720819376465332388864543914078985294145479810606939222216383992286555895625853236491670375192622257155324284843244985545335465287362978215468434024271360080629114844889632675838906705328434449254889213297204035441822688091905656285656394151888204813879831078518928280869696466456390295366642520858089743604875788588249336171615693244751835983410852651127201544553612939088629003265218371417691048176635309364177044766701358377699795232952223152202935931059435421693779930916345845000682337073473149480724440072954904488040982778824725894449815768323509113465949295885603507498264370200923890015168241317006892330098266102128139597393563667677149651852497591025375864995894
 n2 = 2698475686226075727922875574386187058823492611476922860002358023029458657639771046953188201255060157568452129035734125439148211777113077172699940634324873324215170011819062645840127796875859469544990957728137431988601270975684770637979035052867477977135046888339850058116075131487036010413025295336351318831932946017313896447399626404226081450654480696921933686024836824222725331434630860814073299971171985338695128471382400248446104698091918097284406685177571757576346104366533260396493391152625570996491323167431913429943280452394061818054700358743295078061379642722526722798849978301919288950925184032065663817295192580893874999752693149611358550350818715304128021388607152904308446247044586483671654400663194258959113083519729557346058033091028387951702363249337821312037811112961745545487386151697928672795052978212263588647246581101365061877097109610041442299782938306502554711766258351303138088215251384602023526008306
 c = 455863941518777164711770638979677880927658884443865631033897785343512024881240506534356967942892027877135486160509476701275815929848009398883449015317262269637078789489300868180050247683134640577557921243140012052769671350276575359906209128022339484800125461286625807989539284512845543800050389821886658291410385822676589559167498095507901135565361739054522943630178652900330646157249631289777807329635511930165179798945740623391647529488849119945002536479271720932005411578811021167696333363450291124963171113696111175552039612491025708563452996748563325978371575392639525343252323936250405264810240402204231449417720360563959912594724161981999949790954676689174892668918502596075232694999802765416963512949372636906834074116898300028734808122746800724758981906759390103788098490346680322106983439986634895869391836228573537087341579101170066428103231030001696195855900811066771366634772538895069431962669344145287299078725

 # elliptic curves utils copied from https://hxp.io/blog/86/hxp-CTF-2021-f_cktoring-writeup/

 def inv(f):
    ff = f.lift().change_ring(QQ)
    gg = f.parent().modulus().change_ring(QQ)
    hh = xgcd(ff,gg)            # compute xgcd over ℚ
    assert hh[0] == 1
    return f.parent()(hh[1])    # reduce back

 # X1 is P-Q, X2 is P, X3 is Q, returns 2P, P+Q
 def xDBLADD(a,b,X1,X2,X3):
    Z1 = Z2 = Z3 = 1
    if X1 == (): X1,Z1 = 1,0
    if X2 == (): X2,Z2 = 1,0
    if X3 == (): X3,Z3 = 1,0
    X4 = (X2^2-a*Z2^2)^2-8*b*X2*Z2^3
    Z4 = 4*(X2*Z2*(X2^2+a*Z2^2)+b*Z2^4)
    R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^2*Z3^2
    S = (X2*Z3-X3*Z2)^2
    X5 = R-S*X1
    Z5 = S
    return (X4*inv(Z4) if Z4 else ()), (X5*inv(Z5) if Z5 else ())

 def xMUL(a,b,n,P):
    Q,PQ = (),P
    for bit in map(int,f'{n:b}'):
        if bit:
            P,Q = xDBLADD(a,b,PQ,P,Q)
        else:
            Q,P = xDBLADD(a,b,PQ,Q,P)
    return Q

 def xfactor(n):
    Z = Zmod(n // 2)
    R = Z["x"]
    while True:
        # curves of the form y^2 = x^3 + ax over GF(p^2) can have trace 0 if p % 4 == 3
        # https://yujinhkim.github.io/data/orders-elliptic-curves.pdf
        # but doing factoring on elliptic curves is slower
        Q = R.quo(R.random_element(2))
        a, b = Q.random_element(), 0
        x = Q.random_element()
        try:
            xMUL(a, b, n, x)
        except ZeroDivisionError as e:
            vs = list(map(ZZ, re.findall('[0-9]+', e.args[0])))
            g = gcd(vs[0], n // 2)
            if 1 < g < n:
                print(g)
                return g


 p0 = xfactor(n0)
 p1 = xfactor(n1)
 p2 = xfactor(n2)
 q0 = p0**2 + 1
 q1 = p1**2 + 1
 q2 = p2**2 + 1
 r0 = n0 // (p0 * q0)
 r1 = n1 // (p1 * q1)
 r2 = n2 // (p2 * q2)
 assert p0 * q0 * r0 == n0
 assert p1 * q1 * r1 == n1
 assert p2 * q2 * r2 == n2
 phi0 = (p0 - 1) * (q0 // 2 - 1) * (r0 - 1)
 phi1 = (p1 - 1) * (q1 // 2 - 1) * (r1 - 1)
 phi2 = (p2 - 1) * (q2 // 2 - 1) * (r2 - 1)
 e = 65537
 d0 = pow(e, -1, phi0)
 d1 = pow(e, -1, phi1)
 d2 = pow(e, -1, phi2)
 c1 = pow(c, d2, n2)
 c0 = pow(c1, d1, n1)
 m = pow(c0, d0, n0)
 flag = int(m).to_bytes(512, "big").strip(b"\x00")
 print(flag)
 # WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}
	from Crypto.Util.number import bytes_to_long, getStrongPrime, isPrime

	SIZE = 512
	e = 65537

	with open("flag.txt", "rb") as f:
	m = bytes_to_long(f.read())


	def encrypt(m):
	while True:
	p = getStrongPrime(SIZE)
	if p % 4 != 3:
	continue
	q = p**2 + 1
	assert q % 2 == 0
	if isPrime(q // 2):
	break

	r = getStrongPrime(SIZE * 3)
	n = p * q * r
	c = pow(m, e, n)
	return n, c

	if __name__ == "__main__":
	n0, c0 = encrypt(m)
	n1, c1 = encrypt(c0)
	n2, c = encrypt(c1)

	assert m < n0 and c0 < n1 and c1 < n2

	print(f"{n0 = }")
	print(f"{n1 = }")
	print(f"{n2 = }")
	print(f"{c = }")
	# polynomials of this form are found from https://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf

	def xfactor(n):
	# works for n0, n2
	x = ZZ["x"].gen()
	fm = x ^ 4 + x ^ 3 + 2 * x ^ 2 - 4 * x + 3
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	Q = R.quo(x ^ 4 + x ^ 3 + 2 * x ^ 2 - 4 * x + 3) # (x+10)^4%13
	t = Q.random_element() ^ n
	g = gcd(ZZ(t[2]), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	def xfactor2(n):
	# works for n0, n2
	x = ZZ["x"].gen()
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	Q = R.quo(x ^ 4 + x ^ 3 + 6 * x ^ 2 + 4 * x + 7) # (x+7)^4%9
	t = Q.random_element() ^ n
	g = gcd(ZZ(t[2]), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	def xfactor3(n):
	# works for n2
	x = ZZ["x"].gen()
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	Q = R.quo(x ^ 4 + 2 * x ^ 3 + 12 * x ^ 2 + 11 * x + 4) # (x+11)^4%21
	t = Q.random_element() ^ n
	g = gcd(ZZ(t[3]), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	def xfactor4(n):
	# works for n2
	x = ZZ["x"].gen()
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	Q = R.quo(x ^ 4 + 3 * x ^ 3 + 6 * x ^ 2 + 3 * x + 15) # (x+6)^4%21
	t = Q.random_element() ^ n
	g = gcd(ZZ(t[1]), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	def xfactor5(n):
	# works for n0, n2
	x = ZZ["x"].gen()
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	Q = R.quo(x ^ 4 + 2 * x ^ 3 + 16 * x ^ 2 + 15 * x + 20) # (x+15)^4%29
	t = Q.random_element() ^ n
	g = gcd(ZZ(t[3]), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	def xfactoridk(n):
	x = ZZ["x"].gen()
	k = 4
	R = Zmod(n // 2)["x"]
	while True:
	# Q = R.quo(R.random_element(k))
	m = 4 * randint(1, 10) + 1
	Q = R.quo((x + randint(1, m)) ^ 4 % m)
	t = Q.random_element() ^ n
	for r in t:
	g = gcd(ZZ(r), n)
	if 1 < g < n and g != 2:
	if g % 2 == 0:
	g = g // 2
	return g


	n0 = 2225430931171742309590021519105966475844903120525251695523178697527164517579408722711234826878134715797958935338297220265219226300894104569683398115477309720146133327771551725898555731073195872615344013293830504833975586322888278505407028728358704076958757010651157187703590446070184475402381423002650018961176138080716492888165846018003948098783356464323529675777057669124960883202381329499903833929145776324767105873925604946203377344270453210673160949689173847913552580965627850373944000352535059741109945493930667082352120467668696892025338540674581804184012586508599980388614005841857756073388547010787419566713640593253393760294361380501268647194072700469161564801422062289612799077904053452873270626350344212851096671449544321083683295414578870019009973045854170182382727860252857661748412713089966679619926823123247413785351460232424404830410781479607957931804764853243150370282741306050098774071355352739054474451634
	n1 = 2902329412270422842046535537001829377101537009153437279635535810278434063798803011470300739477859973827804786523545631179151215334688591839100812419605935760343991435071529882290299578846926467539408283727659051727132824597767222204754385000922681803386720819376465332388864543914078985294145479810606939222216383992286555895625853236491670375192622257155324284843244985545335465287362978215468434024271360080629114844889632675838906705328434449254889213297204035441822688091905656285656394151888204813879831078518928280869696466456390295366642520858089743604875788588249336171615693244751835983410852651127201544553612939088629003265218371417691048176635309364177044766701358377699795232952223152202935931059435421693779930916345845000682337073473149480724440072954904488040982778824725894449815768323509113465949295885603507498264370200923890015168241317006892330098266102128139597393563667677149651852497591025375864995894
	n2 = 2698475686226075727922875574386187058823492611476922860002358023029458657639771046953188201255060157568452129035734125439148211777113077172699940634324873324215170011819062645840127796875859469544990957728137431988601270975684770637979035052867477977135046888339850058116075131487036010413025295336351318831932946017313896447399626404226081450654480696921933686024836824222725331434630860814073299971171985338695128471382400248446104698091918097284406685177571757576346104366533260396493391152625570996491323167431913429943280452394061818054700358743295078061379642722526722798849978301919288950925184032065663817295192580893874999752693149611358550350818715304128021388607152904308446247044586483671654400663194258959113083519729557346058033091028387951702363249337821312037811112961745545487386151697928672795052978212263588647246581101365061877097109610041442299782938306502554711766258351303138088215251384602023526008306
	c = 455863941518777164711770638979677880927658884443865631033897785343512024881240506534356967942892027877135486160509476701275815929848009398883449015317262269637078789489300868180050247683134640577557921243140012052769671350276575359906209128022339484800125461286625807989539284512845543800050389821886658291410385822676589559167498095507901135565361739054522943630178652900330646157249631289777807329635511930165179798945740623391647529488849119945002536479271720932005411578811021167696333363450291124963171113696111175552039612491025708563452996748563325978371575392639525343252323936250405264810240402204231449417720360563959912594724161981999949790954676689174892668918502596075232694999802765416963512949372636906834074116898300028734808122746800724758981906759390103788098490346680322106983439986634895869391836228573537087341579101170066428103231030001696195855900811066771366634772538895069431962669344145287299078725
	p0 = xfactor(n0)
	p1 = xfactoridk(n1)
	p2 = xfactor(n2)
	q0 = p0 ** 2 + 1
	q1 = p1 ** 2 + 1
	q2 = p2 ** 2 + 1
	r0 = n0 // (p0 * q0)
	r1 = n1 // (p1 * q1)
	r2 = n2 // (p2 * q2)
	assert p0 * q0 * r0 == n0
	assert p1 * q1 * r1 == n1
	assert p2 * q2 * r2 == n2
	phi0 = (p0 - 1) * (q0 // 2 - 1) * (r0 - 1)
	phi1 = (p1 - 1) * (q1 // 2 - 1) * (r1 - 1)
	phi2 = (p2 - 1) * (q2 // 2 - 1) * (r2 - 1)
	e = 65537
	d0 = pow(e, -1, phi0)
	d1 = pow(e, -1, phi1)
	d2 = pow(e, -1, phi2)
	c1 = pow(c, d2, n2)
	c0 = pow(c1, d1, n1)
	m = pow(c0, d0, n0)
	flag = int(m).to_bytes(512, 'big').strip(b'\x00')
	print(flag)
	# WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}
	import re

	n0 = 2225430931171742309590021519105966475844903120525251695523178697527164517579408722711234826878134715797958935338297220265219226300894104569683398115477309720146133327771551725898555731073195872615344013293830504833975586322888278505407028728358704076958757010651157187703590446070184475402381423002650018961176138080716492888165846018003948098783356464323529675777057669124960883202381329499903833929145776324767105873925604946203377344270453210673160949689173847913552580965627850373944000352535059741109945493930667082352120467668696892025338540674581804184012586508599980388614005841857756073388547010787419566713640593253393760294361380501268647194072700469161564801422062289612799077904053452873270626350344212851096671449544321083683295414578870019009973045854170182382727860252857661748412713089966679619926823123247413785351460232424404830410781479607957931804764853243150370282741306050098774071355352739054474451634
	n1 = 2902329412270422842046535537001829377101537009153437279635535810278434063798803011470300739477859973827804786523545631179151215334688591839100812419605935760343991435071529882290299578846926467539408283727659051727132824597767222204754385000922681803386720819376465332388864543914078985294145479810606939222216383992286555895625853236491670375192622257155324284843244985545335465287362978215468434024271360080629114844889632675838906705328434449254889213297204035441822688091905656285656394151888204813879831078518928280869696466456390295366642520858089743604875788588249336171615693244751835983410852651127201544553612939088629003265218371417691048176635309364177044766701358377699795232952223152202935931059435421693779930916345845000682337073473149480724440072954904488040982778824725894449815768323509113465949295885603507498264370200923890015168241317006892330098266102128139597393563667677149651852497591025375864995894
	n2 = 2698475686226075727922875574386187058823492611476922860002358023029458657639771046953188201255060157568452129035734125439148211777113077172699940634324873324215170011819062645840127796875859469544990957728137431988601270975684770637979035052867477977135046888339850058116075131487036010413025295336351318831932946017313896447399626404226081450654480696921933686024836824222725331434630860814073299971171985338695128471382400248446104698091918097284406685177571757576346104366533260396493391152625570996491323167431913429943280452394061818054700358743295078061379642722526722798849978301919288950925184032065663817295192580893874999752693149611358550350818715304128021388607152904308446247044586483671654400663194258959113083519729557346058033091028387951702363249337821312037811112961745545487386151697928672795052978212263588647246581101365061877097109610041442299782938306502554711766258351303138088215251384602023526008306
	c = 455863941518777164711770638979677880927658884443865631033897785343512024881240506534356967942892027877135486160509476701275815929848009398883449015317262269637078789489300868180050247683134640577557921243140012052769671350276575359906209128022339484800125461286625807989539284512845543800050389821886658291410385822676589559167498095507901135565361739054522943630178652900330646157249631289777807329635511930165179798945740623391647529488849119945002536479271720932005411578811021167696333363450291124963171113696111175552039612491025708563452996748563325978371575392639525343252323936250405264810240402204231449417720360563959912594724161981999949790954676689174892668918502596075232694999802765416963512949372636906834074116898300028734808122746800724758981906759390103788098490346680322106983439986634895869391836228573537087341579101170066428103231030001696195855900811066771366634772538895069431962669344145287299078725

	# elliptic curves utils copied from https://hxp.io/blog/86/hxp-CTF-2021-f_cktoring-writeup/

	def inv(f):
	ff = f.lift().change_ring(QQ)
	gg = f.parent().modulus().change_ring(QQ)
	hh = xgcd(ff,gg) # compute xgcd over ℚ
	assert hh[0] == 1
	return f.parent()(hh[1]) # reduce back

	# X1 is P-Q, X2 is P, X3 is Q, returns 2P, P+Q
	def xDBLADD(a,b,X1,X2,X3):
	Z1 = Z2 = Z3 = 1
	if X1 == (): X1,Z1 = 1,0
	if X2 == (): X2,Z2 = 1,0
	if X3 == (): X3,Z3 = 1,0
	X4 = (X2^2-aZ2^2)^2-8bX2Z2^3
	Z4 = 4(X2Z2(X2^2+aZ2^2)+b*Z2^4)
	R = 2(X2Z3+X3Z2)(X2X3+aZ2Z3)+4bZ2^2Z3^2
	S = (X2Z3-X3Z2)^2
	X5 = R-S*X1
	Z5 = S
	return (X4inv(Z4) if Z4 else ()), (X5inv(Z5) if Z5 else ())

	def xMUL(a,b,n,P):
	Q,PQ = (),P
	for bit in map(int,f'{n:b}'):
	if bit:
	P,Q = xDBLADD(a,b,PQ,P,Q)
	else:
	Q,P = xDBLADD(a,b,PQ,Q,P)
	return Q

	def xfactor(n):
	Z = Zmod(n // 2)
	R = Z["x"]
	while True:
	# curves of the form y^2 = x^3 + ax over GF(p^2) can have trace 0 if p % 4 == 3
	# https://yujinhkim.github.io/data/orders-elliptic-curves.pdf
	# but doing factoring on elliptic curves is slower
	Q = R.quo(R.random_element(2))
	a, b = Q.random_element(), 0
	x = Q.random_element()
	try:
	xMUL(a, b, n, x)
	except ZeroDivisionError as e:
	vs = list(map(ZZ, re.findall('[0-9]+', e.args[0])))
	g = gcd(vs[0], n // 2)
	if 1 < g < n:
	print(g)
	return g


	p0 = xfactor(n0)
	p1 = xfactor(n1)
	p2 = xfactor(n2)
	q0 = p0**2 + 1
	q1 = p1**2 + 1
	q2 = p2**2 + 1
	r0 = n0 // (p0 * q0)
	r1 = n1 // (p1 * q1)
	r2 = n2 // (p2 * q2)
	assert p0 * q0 * r0 == n0
	assert p1 * q1 * r1 == n1
	assert p2 * q2 * r2 == n2
	phi0 = (p0 - 1) * (q0 // 2 - 1) * (r0 - 1)
	phi1 = (p1 - 1) * (q1 // 2 - 1) * (r1 - 1)
	phi2 = (p2 - 1) * (q2 // 2 - 1) * (r2 - 1)
	e = 65537
	d0 = pow(e, -1, phi0)
	d1 = pow(e, -1, phi1)
	d2 = pow(e, -1, phi2)
	c1 = pow(c, d2, n2)
	c0 = pow(c1, d1, n1)
	m = pow(c0, d0, n0)
	flag = int(m).to_bytes(512, "big").strip(b"\x00")
	print(flag)
	# WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}