from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(777)
t = getPrime(777)
tmp = getPrime(15)
e = 65537
n = p*q
print(f"c = {pow(m,e,n)}")
print(f"leak = {p*r-q*t-tmp}")
print(f"r = {r}")
print(f"t = {t}")
'''
c = 45437656714471121627138355157760519584383877487083560638903569231003753429372236070673691857077169730892603519190227245821716759904875309795146278716052074220641458531647162288390402966859091110298425439892694611261350164211397322166134468062254148404013023967282115714260566980579790675450977684598154683785
leak = 917729846530514329091476751337548142663910269694651103714041735452546026352121711031281639288281121290785017229906183907137403178781576858736428178204769128767097523395085267085771922696024764050979069087497065064591318989089775212833290963557483734212236438863620201740169796194249006164247654534569614690567400813756683870275745415498464733530190060496080241170104695379710002184233081
r = 793229623087740428917628841295655826564196384346081225806981956029244585596768549762915374835268249941097061878943697142938918149057462225787338641617803276170476918982550729029779739695910685814521000495703548880378158347199461860861
t = 744863076918695565453771645986298395285065781545937584151938034629094359251294022583665909210010813743205258526086574787553912036903279151072458100492653680636375191905874208421015881385428664217006240902142289558937906046107628918859
'''

from Crypto.Util.number import *
from gmpy2 import *
c = 71234358574362873102364773802615022440394390446444390689714741290273256497624990382730338332158663555287988268595847316457126725465934797593513638874080685234812619607085870642413735129064333224013231845589579968352149987746733082038743926312136617735737911790112644979985292337941440005746915062896129072777
leak = 2217488402566151788696168373426094740519351868786430669391214527591322807736221920621550927091543088314007690386894840897074614743933753244173854967425133479984993125811498747715413075715060875227040103463552575330232198985262343584404068367662218021241516914268202429825385451154716855517698999217286233212883976929431520295647139310474770195069360507813140653593200423906263689190196941
r = 646318094023677204527871439846728286610915145770782515880490500338118827547552454143674595295593483857447183764297927877955433524028721434976463867920536240963456378175496414765880178663672652425288097309012713851733051985028662176767
t = 411152195791514027140198841770649225930812047768916179668614369267330226695072559818563655559461575922343428542543751957306358237424055209296982269437988221098480220776423566575802287022940784911752257706236556835428048277615354900397
 
tmp=1<<14
tmp=next_prime(tmp)
 
while int(tmp).bit_length()==15:
    x=leak+tmp
 
    pr=x%t
    p=pr*invert(r,t)%t
 
    qt=x%r
    q=qt*invert(-t,r)%r
    
    flag=long_to_bytes(pow(c,invert(65537,(p-1)*(q-1)),p*q))
    if b'SHCTF' in flag:
        print(flag)
        break
 
    tmp=next_prime(tmp)
#b'SHCTF{004df497-194a-4adb-a675-498ff80946a4}'

from Crypto.Util.number import *
from gmpy2 import*
from flag import flag

m = bytes_to_long(flag)
p = getPrime(1024)
q = next_prime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(m, e, n)
print(c)
print(d)

'''
c = 14754616342385889226523163233456626568583338878447677477264123879922299212851590995108562476976996490186514544769418956576341111197302389433443137591895978122078984343835532649853533922077743108464133594580310257053247234842242258806721334957785422917026938427617572724815559629348765182822868167461354410531375298557821414707229842536823730755256236156265393650672208226959679400363171690605392134085613189512188350291521387717943632410029686096047041138679963736410397635219464470679503925465247560375777761232386822645099986930268675702669789410403561035948651071816164753385550305724927173844685486745218901991290
d = 1584002925248818192743719398743841252208212886071330412633566311356101418040520835843589445425449520698531124917534031266832064627999754033796468790621713333536602778546404704190223202391198167915559642317735981777155889248989261442106757720828921863135304104689505591364608198280118905994363913345364214854979318711326654443828720544265881180686096392455926490169653966632767375383674720009286851902968122706469860651407253475439283722507941794337069535019618439934799606721929935849809583256872132873264812878836099510558296186289301055199336236663148519774947000850709818659346623288768867037411488897123286770273
'''

from Crypto.Util.number import *
from gmpy2 import*
c = 6732251865518539816164424072881268319031331097652330813280683433357801335392912177839752934223666820817426632127352928430012362924774912477109386830642999347655174646486445749282081282131296883166737218186933150962954375021792510359249354608393910760866285720493437099307009772363622740758020450195058117428033257931181355503862561253831338555714889714354329478309157001314105412865222237034290374400091189055727376519273128476126263310458266841590313023188003911952343519869473445661561073623892887752662030827442327135879769080060164402731521556649771103135168057114303776160563813899618546785999749664177453632113
d = 11371580488052460364061084069704641839174413746220695175554663449524234948335256195937545669217400540775148109520252191887923992650699774976840228129947067273971611578960093458221417649211802998948255284549550327209608951277790691750176306647013841775784127208779682066022248206322448435923296521731067094090722931128289230166731316016559509613812382769439697093763600981220856565912350418801087801159700549049260015100996680924659351921989952140635505978192913908332000472530408585162635570201105801365273780636017489787165910874274076972387901429211792329811097435011802258823111183660801103517212211007626963313585
 
e=0x10001
 
p_bits=1024
q_bits=1024
 
k_phi = e*d -1
pphi = []
for k in range(e,2,-1):
    if k_phi % k == 0:
        tmp = k_phi // k
        if int(tmp).bit_length()==p_bits+q_bits:
            pphi.append(tmp)
print(len(pphi))
for k in pphi:
    pp=iroot(k,2)[0]
    pp=next_prime(pp)
    for i in range(100):
        flag=long_to_bytes(pow(c,invert(e,pp-1),pp))
        if b'SHCTF' in flag:
            print(flag)
            exit()
        pp=next_prime(pp)
#b'SHCTF{a47dee42-f097-4aa8-b0a4-5183df80b230}'

import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 88542777790587575958856535465544599238988794938932395236356028878208693584553921119734886663063387114985956647258226878203724318615294722034106396937919235154861105785869874151270067925203729926989428004839944095750101187948993624810926392104761625157561710259470296817872143022024487507072861006495754688653
c = 4141222246815895616291413394343312964175715946241779591801652809315536569381063955911406475498467635919469098028234013454537502595095924767681446516595753207198369151203658212276072550342924879998539629809265836285575387813466965366640792684375303199812785289313990143066954674834496302632946904071326609297
e = 1245551412820870740174723390060313799694721899963655821368021
dp = 3987147738497114215543342475012772407316738649850763986799558233896894884270854903426184789815541134132666857825062494954944564442089304100964792551427901
'''

import gmpy2 as gp

e = 
n = 
dp = 
c = 

for x in range(1, e):
	if(e*dp%x==1):
		p=(e*dp-1)//x+1
		if(n%p!=0):
			continue
		q=n//p
		phin=(p-1)*(q-1)
		d=gp.invert(e, phin)
		m=gp.powmod(c, d, n)
		if(len(hex(m)[2:])%2==1):
			continue
		print('--------------')
		print(m)
		print(hex(m)[2:])
		print(bytes.fromhex(hex(m)[2:]))

import gmpy2
from Crypto.Util.number import *

def solve_dp_leak(e,dp,n,c):
    p = gmpy2.gcd(pow(5,e*dp,n)-5,n)
    q = n//p
    phi = (p-1)*(q-1)
    try:
        d = gmpy2.invert(e,phi)
        m = pow(c,d,n)
        flag = long_to_bytes(m)
        return flag
    except:
        pass

n = 64921145375403083545531864956984072151341856682908111104267811008333409469629440124743589471022387528791249789776590881987854906662741019934835451842451919000617925805744632898434110555454137681326076564563593722826588259739946684132723368750061113163201190149766894752415770470935877082883818815783228793301
c = 44359153953700249051087265515623429893507549101698748624219639421725336531447633500661794130815898489480094607965932371706122863829042269163279628456581736821883648892589019882848750637212268727873179153330759038867740405957550265592570772766459698597324782564295219919626040670464946117978529709691316881784
e = 1039743120668324617408742378768011653641207981199791545288831
dp = 8095244708261074732722010639332938624538458336137147330884467084239259958828296552002478065663880970649018267223959758006546150783644433676150589502506131
flag = solve_dp_leak(e,dp,n,c)
print(flag)

from Crypto.Util.number import *
import gmpy2
flag = b'SHCTF{********}'
assert len(flag) == 39
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x3
pad = b'a_easy_problem'
c = pow(bytes_to_long(flag + pad),e,n)
print(f'n = {n}')
print(f'c = {c}')
'''
n = 91962111715720628931777486647875963597059245014993834637215306985302903621464344605955155370348537698530851713548856588595357527678260117697489817054763356250308965979522594496834705694372742092292311232828638584584609342951267373570856946545879808444285055808517549024876269033273404965254049332343508104863
c = 835987509864121006527888651109319907471805581850280147445733978677695297628994680781831454726352944669970247353856138381638935782695381894498099459107034055303822413288778616502133532974585719609649449865222654363240517858566923788177475848463204393365238566405496963006673163725540787729555001445755141253
'''
    

import libnum
n = 101194231761192803646875794770841105131876105333404505987513576849142365482512109876401629071314564545841743473668262668053559550015874646299248232349238400201145583346187330958825878235324968882794481192056169683711007095999439320830763275487477094590502701333963154552470777678553556993349171608134555815527
c = 54067443511581567434123971345564905390315631873898717856316286990552318113901362505672245448553258416669456882532743580961176229271906817289588426185966004215569829572814038485471312399063659287164712291139771809733004385057875146223151700601326161190474536508680332925332614914475852998934930375151571163346
e = 0x3
pad = b'a_easy_problem'
PR.<x> = PolynomialRing(Zmod(n))
f = (x * 256 ** len(pad) + libnum.s2n(pad)) ** e - c

f = f.monic()
root = f.small_roots(X=2 ** (39 * 8),beta=0.9,epsilon=0.03)
print(root)
print(libnum.n2s(int(root[0])))

#sage
from Crypto.Util.number import *
from secret import flag

flag = flag[6:-1]
l = len(flag)
m1 = bytes_to_long(flag[:l//2])
m2 = bytes_to_long(flag[l//2:])
#RSA
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
r_q = int(bin(q)[2:][::-1] , 2)
leak = p ^^ r_q
c = pow(m2,e,n)

#ECC
E = EllipticCurve(Zmod(n),[114514,1919810])
G = E.lift_x(Integer(m1))
P = G * e
print(f'leak = {leak}')
print(f'n = {n}')
print(f'c = {c}')
print(f'P = {P}')
# leak = 5599968251197363876087002284371721787318931284225671549507477934076746561842
# n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
# c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
# P = (4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627 : 3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519 : 1)

from Crypto.Util.number import *
import sys

pxorq = 5599968251197363876087002284371721787318931284225671549507477934076746561842
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
c = 6803450117490196163076010186755045681029929816618361161925865477601994608941714788803007124967390157378525581080320415602012078322064392991884070073083436
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)


def find(ph, qh, pl, ql):
    l = len(ph)
    tmp0 = ph + (256 - 2 * l) * "0" + pl
    tmp1 = ph + (256 - 2 * l) * "1" + pl
    tmq0 = qh + (256 - 2 * l) * "0" + ql
    tmq1 = qh + (256 - 2 * l) * "1" + ql
    if (int(tmp0, 2) * int(tmq0, 2) > n):
        return
    if (int(tmp1, 2) * int(tmq1, 2) < n):
        return
    if (int(pl, 2) * int(ql, 2) % (2 ** (l - 1)) != n % (2 ** (l - 1))):
        return

    if (l == 128):
        pp0 = int(tmp0, 2)
        if (n % pp0 == 0):
            pf = pp0
            qf = n // pp0
            print(pf)
            print(qf)
            phi = (pf - 1) * (qf - 1)
            d = inverse(e, phi)
            m1 = pow(c, d, n)
            print(long_to_bytes(m1))
            exit()

    else:
        if (pxorq[l] == "1" and pxorq[255 - l] == "1"):
            find(ph + "1", qh + "0", "1" + pl, "0" + ql)
            find(ph + "0", qh + "0", "1" + pl, "1" + ql)
            find(ph + "1", qh + "1", "0" + pl, "0" + ql)
            find(ph + "0", qh + "1", "0" + pl, "1" + ql)
        elif (pxorq[l] == "1" and pxorq[255 - l] == "0"):
            find(ph + "1", qh + "0", "0" + pl, "0" + ql)
            find(ph + "0", qh + "0", "0" + pl, "1" + ql)
            find(ph + "1", qh + "1", "1" + pl, "0" + ql)
            find(ph + "0", qh + "1", "1" + pl, "1" + ql)
        elif (pxorq[l] == "0" and pxorq[255 - l] == "1"):
            find(ph + "0", qh + "0", "1" + pl, "0" + ql)
            find(ph + "0", qh + "1", "0" + pl, "0" + ql)
            find(ph + "1", qh + "0", "1" + pl, "1" + ql)
            find(ph + "1", qh + "1", "0" + pl, "1" + ql)
        elif (pxorq[l] == "0" and pxorq[255 - l] == "0"):
            find(ph + "0", qh + "0", "0" + pl, "0" + ql)
            find(ph + "1", qh + "0", "0" + pl, "1" + ql)
            find(ph + "0", qh + "1", "1" + pl, "0" + ql)
            find(ph + "1", qh + "1", "1" + pl, "1" + ql)


find("1", "1", "1", "1")
#p = 64760524083545528318139240449356269097871629401328435356643510319660757701117
#q = 109947782034870726628911928816041880655659770652764045401662566933641952899777
#-908f-7c002c687387

#sage
from Crypto.Util.number import *

p = 64760524083545528318139240449356269097871629401328435356643510319660757701117
q = 109947782034870726628911928816041880655659770652764045401662566933641952899777
e = 65537
n = 7120275986401660066259983193598830554385933355254283093021239164350142898387660104515624591378875067038235085428170557400012848874756868985306042421950909
E = EllipticCurve(Zmod(n),[114514,1919810])
Eq = EllipticCurve(Zmod(p),[114514,1919810])
Ep = EllipticCurve(Zmod(q),[114514,1919810])
P = E(4143131125485719352848137000299706175276016714942734255688381872061184989156686585992844083387698688432978380177564346382756951426943827434190895490233627,3879946878859691332371384275396678851932267609535096278038417524609690721322205780110680003522999409696718745532857001461869452116434787256032366267905519)

phi = Ep.order()*Eq.order()
d = inverse_mod(e,phi)
G = P*d
x = G.xy()[0]
flag = long_to_bytes(int(x))
print(flag)
#a67b2a9b-0542-4646

from Crypto.Util.number import *
import gmpy2
from flag import flag

class gen_AGCD():
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)

    def enc_(self,M,e):
        C = pow(M,e,self.p*self.q)
        return C

    def re_n(self):
        n = self.p * self.q
        return n

    def re_approximate_n(self):
        k = getPrime(512)
        r = getPrime(247)
        n_approx = k*self.p + r
        return n_approx

if __name__ == '__main__':
    e = 65537
    m1 = flag[:len(flag)//2]
    m2 = flag[len(flag)//2:]
    Encrypt1,Encrypt2 = gen_AGCD(),gen_AGCD()
    C1,C2 = Encrypt1.enc_(bytes_to_long(m1),e),Encrypt2.enc_(bytes_to_long(m2),e)
    N1,N2 = Encrypt1.re_n(),Encrypt2.re_n()

    N1_reveal = []
    for i in range(3):
        N1_reveal.append(Encrypt1.re_approximate_n())

    N2_reveal = Encrypt2.re_approximate_n()

    print('N1 = ',N1)
    print('N1_reveal = ',N1_reveal)
    print('N2 = ',N2)
    print('N2_reveal = ',N2_reveal)
    print('C1 = ',C1)
    print('C2 = ',C2)


N1 =  102962552313473681728723322027597495151261114315051654555740869168148851188107854721536927044442477024748737428557517373823588689936901897797548745673854079501679297287539034025897513808964218875037065595406090476664786378152185622507380646052951461871717529116320541684644754051755754531805285234195783459797
N1_reveal =  [84964829388932061103921957564400125835225719859859510858139343342261376376157402024398819986017063183458456828492439572516643205332521427900739404476385470419622209362062083925319479315213697191724734211420880495849938453677919942805188598151056713085050385277709604039546106740559422133098067538922509028026, 55669509569768064992718044981508136553780767046165209632722329021340164900457535356449024438332915321096786789178632805942918771290307399969035141367566285033608334974253364423607773168674448262916865622517458219728181629393946832062619043643614691875540521738073083356495356354589975146111840434325826819198, 77685152020329500125709975458280809065472024091250688730112377730513223488123677602004197722852227049782404484028558802978507114097790917123660341486556373425727358230049052549163794395853900552906583518153257035524675564804300429030789204176869525785233188403701602735082197253517936111533915552254489942100]
N2 =  145695734665913924175257010903736847918479731583810112670586295711507006721687964045835283940602289356463440889254858811892174016632853579082476117049110447325282176943898704794699667611214913712864592929971488447744298834755679410556926588941532837174941263569541567155147274901631570672266026762222017289227
N2_reveal =  106591311015041707504427951524895388920764384711385757797259452186432986318069454764620553244440558018454822708698461947331019517972650964856645609803899846038300130117604888308467416926253698141673017770502681168291198497788777522823584345758599336082924744440309241874946430102035624053576103790460393511000
C1 =  31594760924666716787696903268342555231641698238925332007707704877423492362096435897073322741916758988157019741830738840842789410609168701142508513641113736572436428873604154027131784982853515763286590388817560388868474399310388515155495051085286726425733319515674947391576533055200594330161967599295787080238
C2 =  4381442301959411454419528795285171587562699421595269409042378524455996065490866727436284838704991923851683436641171227423822439331431086471420344514064543535743315441111296570325222557430574781227184974662494500152603806343531164187542532001697617016254670457335540803929721604735961633537756194281168094293

from Crypto.Util.number import long_to_bytes
#https://eprint.iacr.org/2016/215.pdf
Len = len(N1_reveal)
A = [[0 for i in range(Len)] for j in range(Len)]

for i in range(Len):
    A[0][0] = 2**251
    A[i][i] = -N1_reveal[0]
    A[0][i] = N1_reveal[i]

A = matrix(ZZ,A)
A_solve = A.LLL()
p1 = int(N1_reveal[0]//(abs(A_solve[0][0])//(2^251)))
q1 = N1//p1
flag1 = long_to_bytes(int(pow(C1,inverse_mod(65537,(p1-1)*(q1-1)),N1)))

from Crypto.Util.number import *
def solve2(N,N1,t,k,sys):
    var('x y')
    f = N1-x
    Q_polys = []
    for j in range(t + 1):
        # print(max(k-j,0),min(j,k),max(j-k,0))
        x1,x2,x3 = max(k-j,0),min(j,k),max(j-k,0)
        Q_polys.append(N^(max(k-j,0))*f^(min(j,k))*x^(max(j-k,0)))

    # print(Q_polys)
    len = t+1
    B = []
    num = 0
    for i in Q_polys:
        J = i.coefficients()
        b = [0*x for x in range(len)]
        for j in J:
            # print(j[0],j[1])
            b[j[1]] = ZZ(j[0])*(2**sys)**ZZ(j[1])
        B.append(b[::-1])
        num+=1
    B = matrix(QQ,B)
    solve_B = B.LLL()

    print('===We have find the right B_LLL===')
    BB = solve_B[0]
    a = []
    for i in range(len):
        a.append(BB[i]//((2^sys)^(t-i)))
    f1 = 0
    for i in range(t+1):
        f1 += a[i]*x^(t-i)
    m = f1.roots(multiplicities=False)
    print(m)
    return m

r_solve = solve2(N2, N2_reveal, 32, 16, 247)[0]
p2 = GCD(int(N2),int(N2_reveal-r_solve))
q2 = N2//p2
phi2 = (p2-1)*(q2-1)
d2 = inverse(int(e),int(phi2))
flag2 = long_to_bytes(pow(int(C2),int(d2),int(N2)))

from tqdm import *
from itertools import *
from multiprocessing import Pool
 
################################################ gen data
e = 65537
N = 140467306170270103085247508412489910487748378129459335724515767186097064975754544045630037530915800592540391724032146546032522637400331469533944394808073412880910356816384584939641130518688696505047701134385883270706411370356446043518762317844784816655044013536852156232391544081389664919694551145695399468209
m = 1
rho = 243
a = ["pad"] + [112361172352758758900704170210296813010289510849392179799708472107731966956610675285107363588332515564687781269380345968222030537131341680443039011164210540824825702663120697518389091670478368564009900422608869461335061183241377132579449529050747663021748003410091799048984189262111414502180481142308877537330]
 
 
def attack(ii):
    a = ["pad"] + [112361172352758758900704170210296813010289510849392179799708472107731966956610675285107363588332515564687781269380345968222030537131341680443039011164210540824825702663120697518389091670478368564009900422608869461335061183241377132579449529050747663021748003410091799048984189262111414502180481142308877537330 - 2^243*ii]
 
    ################################################ params
    t,k = 20,10
    R = 2^rho
    indices = []
    for i in product([i for i in range(t+1)] , repeat=m):
        if(sum(list(i)) <= t):
            indices.append(["pad"] + list(i))
 
 
    ################################################ attack
    PR = ZZ[tuple(f"X{i}" for i in range(m))]
    X = ["pad"] + list(PR.gens())
    poly = []
    monomials=set()
    for i in indices:
        f = 1
        for ij in range(1,len(i)):
            f *= (X[ij] - a[ij])^i[ij]
        l = max(k-sum(i[1:]),0)
        f *= N^l
        poly.append(f)
        for mono in f.monomials():
            monomials.add(mono)
 
 
    ################################################# LLL and resultant to find roots
    L = Matrix(ZZ,len(poly),len(monomials))
    monomials = sorted(monomials)
    for row,shift in enumerate(poly):
        for col,monomial in enumerate(monomials):
            L[row,col] = shift.monomial_coefficient(monomial)*monomial(*([R]*m))
 
 
    res = L.LLL()
    vec1 = res[0]
 
    h = 0
    for idx,monomial in enumerate(monomials):
        h += (vec1[idx] // monomial(*([R]*m))) * monomial
    h = h.change_ring(ZZ)
    res1 = h.monic().roots()
 
    if(res1 != []):
        print(ii,res1)
 
lists = [i for i in range(2^4)]
with Pool(64) as pool:
    r = list(pool.imap(attack, lists[::-1]))
print(r)
# https://tangcuxiaojikuai.xyz/post/4a67318c.html 第一部分 1.12 12
#15 [(-271336741980068587844448337263932213024816515815388263122784492996415507, 1)]
#14 [(13863439776247006048821931668679415913595054659189563401850065117344542701, 1)]
r=13863439776247006048821931668679415913595054659189563401850065117344542701
# print(int(r).bit_length())  #243
r=r+2^243*14
p2=GCD(N2,N2_reveal-r)
flag2=long_to_bytes(int(pow(C2,inverse_mod(65537,p2-1),p2)))

from Crypto.Util.number import *
from enc import flag

seed = bytes_to_long(flag)

a = getPrime(400)
b = getPrime(400)
p = getPrime(400)
c = []
for i in range(3):
    seed = (seed*a+b)%p
    c.append(seed>>80)
print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')
print(f'c = {c}')

'''
a = 2475888996632094582034122163505958703059936413843532352796751833709426858969562425221138286394228921214141232352754363633
b = 1905480696303984902796083235070180899781860050180854546296493122498519159940315402346589283466547617432046217796603160773
p = 2209046612698920104484284797114056179410109590589945885514075526562344194607111614640088528695744803046785464320831674877
c = [3046229294982134450591178033489768650552322716872597427107928034748567068803980276957057890481, 973001372006880118889917783354942758117321515064139462745181212051769645104406522505813126876854, 890186362163854321562009885401997664814267684052369722289787654117599676602992999049017980432156]
'''
'''

from Crypto.Util.number import long_to_bytes
a = 2441165060340363548034817419913152429437367671051257983130193376968866003652656064753193540692576823353722522219951236377
b = 2536384599388118977308934726385759683875116193910292140931807458602198040481977699550435249496535909362102559820360131151
p = 1898350626517014951217210423867648293636462375574846448952061608918022029275967066566474923728317050045578381447025802447
c = [1206170611286987749822509820930522025955557233442828617888124729629984583540215838639710785581993, 852222709497386792919622853438477061105763652894458161025475550177341850861286444913870176145661, 1304945544687728464084706289648969970911515894526834307083141183941320491375891396365871606911311]
 
h = [0] + c
 
length = len(h)
for i in range(length):
    h[i] <<= 80
 
A = [1]
B = [0]
 
for i in range(1, len(h)-1):
	A.append(a*A[i-1] % p)
	B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % p)
 
A = A[1:]
B = B[1:]
 
 
 
Ge = Matrix(ZZ,length,length)
 
for i in range(len(A)):
    Ge[i,i] = p
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]
 
K = 2**80
Ge[-2,-2] = 1
Ge[-1,-1] = K
 
for line in Ge.LLL():
    if abs(line[-1]) == K:
        L1 = line[-2]
        seed1 = h[1] + L1
        seed = (seed1 - b) * inverse_mod(a,p) % p
        print(f"seed = {seed}")
        print(long_to_bytes(seed))

# sage
import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

output =  [3046229294982134450591178033489768650552322716872597427107928034748567068803980276957057890481, 973001372006880118889917783354942758117321515064139462745181212051769645104406522505813126876854, 890186362163854321562009885401997664814267684052369722289787654117599676602992999049017980432156]
a = 2475888996632094582034122163505958703059936413843532352796751833709426858969562425221138286394228921214141232352754363633
b = 1905480696303984902796083235070180899781860050180854546296493122498519159940315402346589283466547617432046217796603160773
n = 2209046612698920104484284797114056179410109590589945885514075526562344194607111614640088528695744803046785464320831674877


PR.<x,y> = PolynomialRing(Zmod(n))
f = ((output[0]<<80)+ x) * a + b - ((output[1]<<80) + y)
roots = small_roots(f,(2^80, 2^80), m=4, d=4)
s1 = (output[0]<<80) + roots[0][0]
m = (s1 - b) * inverse_mod(a, n) % n
print(bytes.fromhex(hex(m)[2:]))

from Crypto.Util.number import getPrime,bytes_to_long
import random
from os import getenv

BANNER = """
 __          __  _                            _______       _____ _                     _      
 \ \        / / | |                          |__   __|     / ____| |                   (_)     
  \ \  /\  / /__| | ___ ___  _ __ ___   ___     | | ___   | (___ | |__   __ _ _ __ ___  _ _ __ 
   \ \/  \/ / _ \ |/ __/ _ \| '_ ` _ \ / _ \    | |/ _ \   \___ \| '_ \ / _` | '_ ` _ \| | '__|
    \  /\  /  __/ | (_| (_) | | | | | |  __/    | | (_) |  ____) | | | | (_| | | | | | | | |   
     \/  \/ \___|_|\___\___/|_| |_| |_|\___|    |_|\___/  |_____/|_| |_|\__,_|_| |_| |_|_|_|   
"""
print(BANNER)

flag = getenv("GZCTF_FLAG","GZCTF_NOT_DEFINE")
m = bytes_to_long(flag.encode())
n = getPrime(1024)
coefficients = [m] + [random.randrange(1,n-1) for i in range(100)]
print(f"n = {n}")

def f(x):
    sum = 0
    for i in range(len(coefficients)):
        sum += coefficients[i]*pow(x,i,n) % n
        sum %= n
        
    return sum

while 1:
    x = int(input("Please Input x: "))
    if x == 0:
        print("Not Allowed!!!")
        exit()
    res = (x,f(x))
    print(res)

from pwn import *
from Crypto.Util.number import *
 
r=remote("210.44.150.15",40430)
 
r.recvuntil(b'n = ')
n=eval(r.recvline().strip().decode())
 
m=[]
for i in range(1,101+1):
    r.recvuntil(b'Please Input x: ')
    r.sendline(str(i).encode())
 
    tmp=eval(r.recvline().strip())
    m.append(tmp)
    
flag=0
for i in range(len(m)):
    tmp1=1
    tmp2=1
    for j in range(len(m)):
        if i==j:
            continue
        tmp1*=-m[j][0]
        tmp2*=(m[i][0]-m[j][0])
    flag=(flag+m[i][1]*tmp1*inverse(tmp2,n))%n
print(long_to_bytes(flag))

from pwn import *
from Crypto.Util.number import *

sh = remote(host,port)

sh.recvuntil(b"n = ")
n = int(sh.recvline().decode())
PT = []

for i in range(101):
    sh.sendlineafter(b"Please Input x:",str(i+1).encode())
    res = eval(sh.recvline().decode())
    PT.append(res)
    
R.<x> = PolynomialRing(Zmod(n))

recover_f = R.lagrange_polynomial(PT)
m = recover_f(0)
flag = long_to_bytes(int(m))
print(flag)

from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
assert len(flag)==47
leak = cos(m).n(1000)
print(leak)
# 0.982986717026051523775689061128623398913716255464419265504704959461292114149510361613827827832793334890682930344871015798797235443155666550182278434353933798075760336073743564317792255228218620688463838126060619033247131957845171463388367372437867860524109961940806277727950981541880151172951132210062

from Crypto.Util.number import *

leak = 
acos = arccos(leak)
RR = RealField(1000)
pi = RR(pi)
Ge = Matrix(QQ,[[1,0,2^750],[0,2^375,2^750*acos],[0,0,2^750*2*pi]])
Ge = Ge.LLL()[0]
m = abs(Ge[0])
print(long_to_bytes(int(m)))

class Random(object):
    def __init__(self, s0, s1):
        self.s0 = s0
        self.s1 = s1
        self.state = [s0, s1]
    def current(self):
        val = (self.s0 + self.s1) & 0x1fffffffffffff
        return val >> 4
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        s1 &= 0xffffffffffffffff
        self.state[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26)
                
        random_val = (self.state[1] + s0) & 0xffffffffffffffff 
        
        return random_val
    def Next(self):
        return next(self) & 0x1fffffffffffff

import colorama, hashlib, random, string
from colorama import Fore as cf
from os import urandom, getenv

flag = getenv("GZCTF_FLAG","GZCTF_NOT_DEFINE")
s0, s1 = [int.from_bytes(urandom(8), 'big') for _ in [0, 0]]
prng = Random(s0, s1)
colorama.init()

def number_to_circled(num):
    circled_numbers = {
        '0': '⓪', '1': '①', '2': '②', '3': '③', '4': '④', '5': '⑤',
        '6': '⑥', '7': '⑦', '8': '⑧', '9': '⑨'
    }
    return ' '.join(circled_numbers[d] for d in str(num))

welcome = f"""
        ╔═══════════════════════════╗
        ║  🔒 Smart Lock System 🔒  ║
        ╠═══════════════════════════╣
        ║                           ║
        ║   1.  {cf.YELLOW} Spy   password{cf.RESET}     ║
        ║   2.  {cf.YELLOW}Input  password{cf.RESET}     ║
        ║                           ║
        ╚═══════════════════════════╝
"""
print(welcome)

def proof_of_work():
    prefix = "".join(random.choices(string.ascii_letters, k=8))
    answer = "".join(random.choices(string.ascii_letters, k=4))
    hashes = hashlib.sha256((prefix + answer).encode()).hexdigest()
    print(f"🔍 Prove you deserve to see the password! Solve this PoW:")
    print(f"   Find a ANSWER {cf.LIGHTGREEN_EX}hashlib.sha256(('{prefix}'+{cf.RED} ANSWER{cf.LIGHTGREEN_EX}).encode()).hexdigest()[:10] =='{hashes[:10]}'{cf.RESET}")
    
    suffix = input(f"   Enter your {cf.RED}ANSWER{cf.RESET}: ")
    attempt = hashlib.sha256((prefix + suffix).encode()).hexdigest()
    
    if attempt.startswith(hashes[:10]):
        return True
    else:
        print(f"❌ {cf.RED}Spy failed. {cf.RESET}\n")
        return False

while True:
    chose = input("Please make your selection: ")
    if chose == "1":
        if proof_of_work():
            password = prng.Next()
            password = number_to_circled(password)
            output_text = f"👀 The Peek at password: {cf.LIGHTGREEN_EX}{password}{cf.RESET}"
            box_width = len(output_text) - 6
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text}  ║")
            print("╚" + "═" * box_width + "╝\n")
        else:
            continue
    elif chose == "2":
        password = prng.Next()
        print(                  "╔═════════════════════════════════════╗")
        user_input = input(    f"║ 🔑 Enter password: {cf.YELLOW}")
        print(  f"{cf.RESET}╚═════════════════════════════════════╝")
        if user_input == str(password):
            output_text = f"🔓 {cf.GREEN}Access Granted!{cf.RESET} Secret is {cf.LIGHTMAGENTA_EX}{flag}{cf.RESET}"
            box_width = len(output_text) - 17
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text} ║")
            print("╚" + "═" * box_width + "╝\n")
            break
        else:
            output_text = f"❌ {cf.RED}Access Denied! Incorrect password.{cf.RESET}"
            box_width = len(output_text) - 7
            print("╔" + "═" * box_width + "╗")
            print(f"║ {output_text} ║")
            print("╚" + "═" * box_width + "╝\n")
            break
    else:
        output_text = f"⚠️ {cf.RED}Invalid selection. Please choose 1 or 2.{cf.RESET}"
        box_width = len(output_text) + -8
        print("╔" + "═" * box_width + "╗")
        print(f"║ {output_text} ║")
        print("╚" + "═" * box_width + "╝\n")

# sage
import z3
import sys
import itertools

# XorShift128+ algorithm in python
class XorShift128Plus(object):
    def __init__(self, s0, s1):
        self.s0 = s0
        self.s1 = s1
        self.state = [s0, s1]
    
    def current_double(self):
        val = (self.s0 + self.s1) & 0x1fffffffffffff
        return val
    
    # This function generates another 64-bit integer
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        s1 &= 0xffffffffffffffff
        self.state[1] = s1 ^ s0 ^ (s1>>17) ^ (s0>>26)
                
        random_val = (self.state[1] + s0) & 0xffffffffffffffff 
        
        return random_val
    
    # This function generates another floating point-type number in the range [0,1)
    def next_double(self):
        return next(self) & 0x1fffffffffffff
    
class Cracker(object):
    def __init__(self, known_values):
        self.s0 = z3.BitVec('s0', 64)
        self.s1 = z3.BitVec('s1', 64)
        self.state = [self.s0, self.s1]

        self.solver = z3.Solver()

        # The known variable will contain the values that we generated in Firefox
        self.known = known_values
    
    def __next__(self):
        s1 = self.state[0]
        s0 = self.state[1]
        
        self.state[0] = s0
        s1 ^= (s1 << 23)
        self.state[1] = s1 ^ s0 ^ z3.LShR(s1,17) ^ z3.LShR(s0,26)
                
        return self.state[1] + s0
    
    def crack(self):
        for val in self.known:
            nextval = z3.fpToFP(z3.get_default_rounding_mode(), next(self) & 0x1fffffffffffff, z3.Float64())
            self.solver.add(nextval == val)

        if self.solver.check() != z3.sat:
            raise Exception("Not solved!")
        
        model = self.solver.model()
        s0 = model[self.s0].as_long()
        s1 = model[self.s1].as_long()
        
        return (s0, s1)

def circled_to_num(num):
    circled_numbers = {
        '0': '⓪', '1': '①', '2': '②', '3': '③', '4': '④', '5': '⑤',
        '6': '⑥', '7': '⑦', '8': '⑧', '9': '⑨'
    }
    circled_numbers = {y:x for x,y in circled_numbers.items()}
    return int(''.join(circled_numbers[digit] for digit in str(num).replace(' ','')))

import hashlib, itertools, string
def pow(s1,s2):
    for s in itertools.product(string.ascii_letters,repeat=4):
        if hashlib.sha256((s1 + "".join(s)).encode()).hexdigest()[:10] == s2:
            return "".join(s)

from pwn import *
p = remote('210.44.150.15', 20786)

pwd = []
def get_num():
    p.sendlineafter(b'Please make your selection: ',b'1')
    p.recvuntil(b'Find a ANSWER ')
    PoW_data = p.recvline().decode()

    print(PoW_data)
    import re
    pattern = r"sha256\(\('(\w+)'\+.*\)\.hexdigest\(\)\[:10\] =='(\w+)'"
    match = re.search(pattern, PoW_data)

    if match:
        p1 = match.group(1)
        p2 = match.group(2)
        print(p1,p2)

    answer = pow(p1,p2) 
    p.sendline(answer)
    p.recvuntil(b'The Peek at password: ')
    num = p.recvline().decode()
    print(num)
    num = num[5:-9]
    print(num)

    pwd.append(num)

get_num()
get_num()
get_num()

known_values = [circled_to_num(x) for x in pwd]

cracker = Cracker(known_values)
(s0, s1) = cracker.crack()
print(s0,s1)
prng = XorShift128Plus(s0, s1)

assert prng.next_double()==known_values[0]
assert prng.next_double()==known_values[1]
assert prng.next_double()==known_values[2]

x3= prng.next_double()
success(str(x3))

p.sendlineafter(b'Please make your selection: ',b'2')
p.sendlineafter(b'Enter password: ',str(x3).encode())
# p.interactive()
p.recvuntil(b'Access Granted!')
success(p.recvline())

import hashlib
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
from my_own_flag import flag

def MT_19937(num,en_c):
    seed1 = os.urandom(16)
    random.seed(seed1)
    number = []
    for i in range(num):
        number.append(random.getrandbits(32))
    cal = 0
    for i in range(num,num+en_c):
        cal += random.getrandbits(32)
    return number,cal

def encrypt(cal,flag):
    key = hashlib.sha256(str(cal).encode()).digest()
    A = AES.new(key, AES.MODE_ECB)
    c = A.encrypt(pad(flag,16))
    return c

def main():
    LEN = len(flag)
    m1,m2 = flag[:LEN//2],flag[LEN//2:]

    Num = 624
    # encrypt m1
    K1 = MT_19937(Num,Num)
    c1 = encrypt(K1[1],m1)

    # encrypt m1
    K2 = MT_19937(Num, Num//4)
    c2 = encrypt(K2[1], m2)

    with open('data.txt','w') as f:
        f.write(str(K1[0])+'\n')
        f.write(str(K2[0][:600])+'\n')
        f.write(str(c1)+'\n')
        f.write(str(c2)+'\n')

if __name__ == '__main__':
    main()

[1212937457, 714280275, 2934808054, 289447810, 634020656, 2582053193, 2648476152, 3584472561, 2877037797, 1051288028, 3007240724, 3583122714, 2377373219, 2233668169, 2300136290, 4277363949, 572508719, 3707687803, 868724505, 2234515288, 2182162330, 2354654192, 3676064525, 16386761, 1934246009, 396534601, 3406538372, 1978740790, 51554945, 1642830773, 3255471879, 249329746, 1871028531, 1670146144, 3955249559, 3523216280, 4225679888, 1979625069, 1711120506, 4224015378, 2357192253, 1437719734, 1861766583, 252037050, 3805173581, 3845899039, 239338040, 3335618070, 1909354144, 2380236080, 3120658839, 2738735651, 1749563272, 4028406006, 198730175, 4095736523, 2224365497, 1850797931, 123559677, 277130374, 1547602417, 2312967225, 1064405558, 620877831, 4182002366, 2717144120, 2424475877, 1261886189, 2666842961, 1250633055, 1445939400, 2496676732, 46718503, 1726056600, 2892333819, 3874613567, 2801764620, 3279121957, 62950328, 14090298, 3016963976, 235881318, 1152787765, 3549713637, 3184265794, 461262349, 1835258817, 706701716, 366259495, 2484440259, 2306336615, 2418024433, 107268664, 3018120752, 3915797798, 1685880034, 2782876985, 2876720582, 3803172243, 1745503879, 1965535595, 2831775453, 3139448870, 770826076, 559187920, 4292272948, 86904027, 1821662944, 58381562, 250790584, 2122997254, 2937312684, 3225034461, 1493971528, 913420791, 2911905254, 2938402784, 1430747115, 2654595902, 3315197237, 602765188, 1471009311, 3788529131, 913593424, 3280524381, 1554400422, 3250536147, 3480550436, 821401975, 3216026683, 762420368, 1733854366, 2395038075, 533527872, 3040490234, 2855012365, 2984904790, 2830464734, 2200935030, 523059886, 3795772367, 2905400361, 667720140, 3155311553, 1860651089, 1053555607, 2889478721, 1812821011, 3391980212, 3433665687, 2480476597, 1319654037, 1076583906, 2287201297, 966928688, 2542225146, 2246098689, 3117124345, 1844896511, 3104215564, 1303510082, 2924158615, 3648677443, 3308489255, 3809196505, 3199516268, 2254502655, 2126047470, 1763846642, 3851973930, 1280609700, 2415985988, 1312349771, 2103486452, 4229394974, 1937464844, 2763672456, 1366425769, 1532462738, 1864298394, 1203192658, 3679892306, 4138733297, 39437090, 1317880030, 132948638, 2315846286, 3394291148, 3207221552, 3834885856, 2367158425, 3183864791, 3303289072, 519407526, 4127464161, 1556426685, 2427155757, 2010011401, 2823249259, 3638339516, 2266010959, 345885116, 471672470, 2713191580, 731238671, 1694687550, 2523761501, 3533913138, 163820753, 1829608711, 587056408, 1129980234, 3642159144, 2546599527, 758703728, 1713442774, 1864598338, 2763096157, 2308766766, 1132350895, 2776604596, 1921085522, 1409581297, 2643399928, 3285649744, 1248611904, 2694186262, 2676127368, 2579578748, 3784393865, 2655293049, 1378866508, 1251610536, 1048557165, 3045231444, 4236456301, 2496231577, 4118010676, 3079411364, 2425576144, 2431718306, 543894373, 118186072, 2594647421, 1833894329, 3876640493, 1916631983, 2765860034, 3905895682, 2207230275, 2554838603, 3199831939, 2516271151, 3080023814, 3594335532, 1197450849, 2621744299, 447615180, 1616950869, 3109651542, 2553431350, 4165466937, 2130063794, 1459492895, 1141470511, 948009682, 325807524, 1681494454, 3137320840, 4219461371, 609761579, 942363481, 2404858793, 1697226342, 830264373, 230968933, 831865647, 4164463522, 2968510743, 1464271639, 1397831008, 2559413030, 3515044508, 772056268, 3152446673, 3117754594, 833212973, 4252629747, 2565179775, 3005093783, 3595030314, 4042182692, 298671165, 3183128227, 3429794312, 4122368172, 1900961662, 3589294443, 3190786481, 1744404482, 1921785452, 3011999869, 642164068, 3695788414, 2275346981, 1428956574, 2697326707, 2202213004, 3287889517, 919861723, 726410498, 337174656, 2417998504, 2752587611, 3856581958, 141509063, 1762431188, 2065705145, 2031960873, 1892209091, 2395039500, 1058479586, 1537034270, 502217054, 3102018820, 1433274316, 1372952271, 2918921770, 239909451, 1398298200, 2339489735, 372558373, 2263872236, 2426192905, 337209508, 3983991978, 2574803724, 2837664572, 1569892789, 2625063195, 3262762020, 24150029, 2016099290, 2239153990, 85602273, 973040529, 2956276779, 4218049523, 2043716624, 2788573458, 1218787308, 939708241, 2861205992, 2427634523, 4128874493, 2326852266, 2593724377, 1680473968, 2763572707, 4240616686, 2863701585, 3551633590, 1765256405, 2110583291, 357590304, 2511138801, 859903599, 35591840, 3786321031, 3559501147, 3107666783, 2356867678, 1369801910, 2488594855, 2148205170, 3944224524, 2219844222, 466009157, 2328231114, 2777059464, 1585865212, 2871297568, 2558165993, 1561563095, 438633926, 2619385032, 2185942244, 2501145168, 2161107203, 912485991, 3956413626, 4065963551, 1527306118, 378382496, 1016367697, 82832444, 2484726280, 867566307, 1037338825, 4291735272, 901722138, 3956112428, 1060890097, 4210262544, 2525835262, 786274933, 2563584713, 2738164238, 3438656534, 564065202, 3288501195, 1074332184, 2947775555, 3790174897, 3607901153, 2332098514, 3648669449, 3879104921, 3983960923, 548882335, 1817587379, 1555057777, 2705918139, 2755720626, 2706833366, 2947946695, 3082750952, 2323554320, 1804494628, 1677086381, 2771841028, 2470056271, 3431120732, 4073503495, 2929631518, 80800254, 605951710, 1664206366, 2498279527, 360922649, 2590660538, 3724444465, 3559953317, 3002864163, 3369368155, 1569518356, 3831143803, 4184782515, 1602338537, 2640186368, 2864951447, 514648741, 887020932, 166121609, 476244781, 2238614863, 3039706334, 3586500526, 3038068930, 3989751746, 3699955508, 3559348520, 884358906, 444882591, 3769021913, 3665754928, 1911261614, 1234192084, 3450557803, 3232410240, 494096069, 660552292, 1365481833, 520081058, 1027987838, 3165505556, 1257833693, 2146291679, 3634622224, 589123893, 1195030125, 1602406253, 772753497, 2661121530, 2938530200, 1070706826, 3890477657, 2112901265, 4253917692, 2291562806, 67613984, 2608069358, 1726139310, 3018885048, 367067728, 3838771641, 1357927847, 2616452172, 722979624, 4153031784, 607660099, 3164865398, 3199368055, 1885230388, 1055777913, 3475913336, 1546318749, 578282810, 1558944130, 2955660875, 2214838829, 4202836988, 1405916968, 2593459723, 3648360966, 3644813488, 598912719, 876098814, 355483438, 685352898, 4099087273, 2983380912, 450980374, 2753208777, 429297943, 3462109454, 3134522829, 2064548393, 2200750558, 4247753845, 251220053, 1556849099, 2022648175, 3563632884, 2175932589, 1463719656, 1887673611, 3541708446, 3033219582, 3255799816, 534398633, 3481196045, 825005812, 1629237540, 640085217, 899503755, 3105157116, 488231507, 2708835929, 2648663900, 2048030022, 1503411342, 4059850866, 1281156549, 3171426598, 2637361895, 1110841056, 606897504, 3001264062, 912267483, 148124465, 202684836, 1425732680, 3637635336, 1455737055, 2977077407, 54987379, 1056796337, 1832170261, 1870208138, 4074249428, 2993704297, 381772606, 2362720677, 2164369676, 250156737, 3409786877, 1590821450, 2959971180, 3682255149, 302283211, 4204651015, 1294232346, 3088162584, 4209012441, 784333825, 1275400791, 885466807, 1249631254, 1236809354, 2627231325, 2391839654, 1638467843, 2797229961, 3799496431, 237846505, 3432655604, 1690038717, 1493561006, 4229115929, 3784624191, 2891696687, 3557702324, 1120718375, 2593253432, 1415584860, 551110044, 1510986691, 3267929936, 2341598281, 247215742, 3192053018, 2856032615, 3290505354, 907961089, 4128700570, 4195745607, 2035634741, 1047086449, 216435127, 1997121891, 3391563810, 2813128796, 1517545322]
[2137201486, 2243095490, 3817098931, 229608464, 73854451, 2470370137, 647955184, 1997583099, 2122796155, 3754429965, 915090235, 3330907022, 4045925639, 1616378187, 3477748127, 3235608209, 4168058459, 137624259, 2992531650, 509166204, 3920545433, 1915159362, 3901263233, 4228481818, 2816405167, 1786108715, 3305752402, 2384763695, 227465801, 1052658065, 3153900057, 117311308, 1595474528, 1087880165, 3166831564, 1588364714, 528237288, 617272354, 618281932, 1618791873, 3810883062, 894018392, 2575794219, 103568311, 3298607681, 536028939, 3467146346, 2201685940, 1076138845, 918210863, 1341794665, 3456513087, 1710914773, 1894309846, 2312381988, 127727152, 876614149, 1709878784, 1156541415, 1555452594, 182448271, 408344822, 2898434231, 1998211488, 3592206445, 1085073460, 3397525879, 663024038, 3434587726, 2768736843, 617681814, 2865397550, 3463093384, 2746629701, 2006818690, 1121017677, 2047400279, 1921768902, 528024592, 2892263293, 2798869302, 3481658697, 2848153687, 1134481165, 3720776629, 486120970, 2683483151, 3252410704, 2891974166, 2121509882, 4160792826, 2915283137, 4014112386, 1792273527, 805496405, 1407962158, 3622679727, 3512697173, 2901255951, 3111681208, 2877903904, 827923100, 3729787569, 925768344, 923906770, 3606973890, 1181029191, 689515782, 1651144572, 3459362488, 2412684107, 1362064386, 4159398924, 2922809145, 1602978249, 3705882625, 4293462677, 764953390, 4178674632, 2074025926, 1925824438, 2523046149, 1263372335, 1677306491, 760292173, 3736532489, 2036587975, 514100070, 706857874, 1060105302, 2578078966, 2320134376, 3639164974, 1710455599, 45505402, 2407597519, 2537656373, 56251495, 1630733521, 519864415, 1444518872, 513906964, 3852284907, 800496493, 872675679, 3155530732, 683268660, 3856797215, 137673146, 3607443770, 3700387644, 965766446, 2454233777, 954672952, 2855774032, 3552757435, 3025907069, 1402938518, 3041387870, 3456472325, 447871942, 1327563590, 620160190, 1007188755, 180115074, 52020277, 1774723235, 2887773879, 3508414970, 3631951842, 1763635376, 1924307117, 4204987693, 2494477117, 4017134019, 368620157, 2814392181, 2199699352, 1158269085, 2580589087, 1747804339, 1012560482, 933361529, 176586313, 2808905110, 83750114, 3090684109, 1767704883, 4189833886, 4249260150, 2157821862, 2112716220, 261010276, 3168798078, 1920566780, 1823590666, 2244335700, 2816218464, 3295774792, 2283997010, 3733740723, 3169836042, 1782097885, 1421909608, 3071286976, 2529056825, 2917504380, 2500113967, 1340022169, 1325786585, 2696541388, 3763160733, 3603998832, 72655495, 2892272720, 2785458061, 1724578654, 2144338844, 2899719547, 318345339, 2511462884, 3220707099, 1676208778, 2586878575, 3209502577, 3013180194, 2700788434, 3611106949, 1712906930, 3381158761, 962420077, 1928661992, 1241692316, 3587734972, 2361851891, 729570171, 1255993130, 2059230370, 3819451535, 2490865889, 1229457976, 3062266381, 3350574651, 1861939269, 3074031276, 1122137253, 3267903554, 2691684836, 3042505532, 1103427454, 2126863565, 3686667924, 4181984974, 238390653, 2037278833, 2930470784, 424623283, 3074336567, 4019540123, 447553681, 491252047, 2134100060, 3683266682, 2218397687, 1535505498, 628745497, 445350701, 186184731, 3190072310, 1084556173, 277509904, 2898643406, 4292667973, 2903270520, 2565372604, 303440546, 1808627640, 3069152665, 2075086265, 350493108, 3426866771, 1167370872, 2856612905, 1133769957, 2168578594, 361418126, 1788736419, 3450707887, 1988560242, 3106183307, 420765626, 1595814948, 813997149, 2474462651, 3945801301, 1785414095, 4177305184, 3071687740, 1273724577, 4178527412, 2536332142, 2692000853, 2172897829, 1472311250, 1630835977, 2274186143, 3947343331, 1836099636, 3955763613, 271610193, 2479541262, 3666471942, 4217699594, 341808580, 1517926781, 3311123634, 1738600938, 3870938757, 2309182531, 3189576099, 1594683626, 1900151562, 3625455382, 3527220315, 471268317, 4085391597, 1205291118, 1903466784, 934489768, 717103328, 407385599, 1146912039, 2148396650, 3906209540, 3002211292, 4003244728, 1595357238, 4224659669, 3679773598, 1554305724, 1879798896, 856183762, 2448013518, 2839667183, 3541976537, 1201501683, 2210517506, 3074699110, 2545660131, 3696626258, 1684534318, 3093429986, 2603224784, 3784468515, 1931537793, 570789340, 376758771, 2307788100, 2180860578, 201860820, 3293433128, 1396840567, 2231737923, 3343569549, 890147328, 3369945506, 3155052764, 4225372249, 3097945008, 1976073442, 1939061106, 3009821364, 3636790064, 1722351481, 571067187, 3660829870, 625774796, 962877120, 4093260308, 2994561947, 1780515932, 4180215026, 4252365298, 2947348994, 2484307881, 1869054839, 1567538899, 2381016872, 650248596, 2837463974, 3547259433, 1653667021, 276270749, 1685266082, 3605301102, 3560229703, 3732548108, 3643340502, 2787020632, 301650068, 1692193275, 3053122330, 446613045, 753748541, 3639322954, 2521151846, 3846032512, 2540737292, 1022192711, 4242180248, 2050165414, 2033316505, 3063183472, 2547887329, 1562411323, 2846186023, 1057549601, 200005518, 2515317663, 614142733, 2822762719, 1111596810, 730033186, 3539522165, 2876952827, 1093300071, 2988803720, 2788643910, 1815173676, 923492540, 1571870569, 1732017323, 3912738621, 1932484987, 1369226061, 1043943980, 659920686, 87860672, 3117771700, 536701, 1276716714, 399069847, 675178237, 4148780498, 2293633457, 510556418, 3306441120, 3969884840, 931665570, 1269866789, 1486094185, 1896845492, 2955478105, 3949294788, 2483398248, 2792552965, 367597061, 955979053, 4141216471, 3162398417, 783759084, 605101703, 3200303074, 1835668453, 3586071304, 2174558649, 2997422459, 3634493394, 4138976583, 164027380, 490279465, 2469644175, 43130477, 1547916166, 2406583577, 1303190434, 1431585058, 1519905099, 1079834268, 231749295, 1635997362, 1423407810, 2814537500, 2894136671, 3686889877, 1812711299, 4226627996, 3754118359, 20804048, 4285391186, 2958387414, 2233166520, 3070925064, 1320913219, 2976334802, 4041836979, 382095839, 1388937175, 1819247059, 3838255239, 3380204370, 3935811842, 2751480313, 164540071, 2340071112, 610666648, 595972300, 2011517128, 213838138, 4255091509, 3777157969, 2402199559, 3852693289, 4206005132, 3787527275, 1471785983, 2589388076, 631286274, 3524096200, 590972337, 1887865600, 1760603763, 643231370, 2643740969, 2388499010, 1722852753, 645073667, 3177739276, 1242181637, 2984331308, 567911875, 753620395, 3743678155, 4278357119, 2815496781, 1270587449, 4259346098, 589049437, 3257834517, 3637173709, 2882662502, 2892380404, 1843952012, 2832065071, 1053718106, 330418109, 3909969653, 916711438, 3709287944, 2455153252, 763050070, 1667025352, 3019273370, 3814458403, 1093369006, 3332713718, 752637853, 100085835, 523535862, 4068027345, 1845694557, 2754500540, 3395089568, 2675873208, 525907800, 937117572, 3313729567, 1112554253, 114888315, 619966459, 1641381760, 1017743298, 1178701646, 1581336326, 362103885, 3516308826, 869224156, 376989708, 633412018, 1074308065, 3818889570, 4249601414, 2417156426, 2229939059, 1313267093, 2929434755, 783116601, 1643811645, 996372459, 3352907069, 953035592, 1641549976, 2112115418, 1350813227, 3528081888, 1136982588, 1390912242, 2659886726, 1031606598, 2617877628]
b'\x04\xd6k\xe5:\x9a\xabu\xb3\r\x06\xd9\x8e\x04\x87\xc7\x10\xecv\x0bG,\x9c\xb5\xb5q\xd6\x9c\xb8\xb7\xb1d'
b'CT\x1a>\x12\x8ff"\x89\xde\x9a\x0f\xf4\xac\xa2\xe7\xd2%\x15\xdd`\x03\xf4?u\x07#\xf9\x03\xde\xd4\x97'

def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 用于初始化伪随机数生成器的类的构造函数
    # 根据seed初始化624的state
    def __init__(self, seed):
   #创建一个名为 mt 的列表，包含624个元素，初始值都为0。这是用于存储生成器状态的主要数据结构。
        self.mt = [0] * 624
   #将输入参数 seed 的值赋给 mt 列表的第一个元素。它用于初始化生成器的种子。
        self.mt[0] = seed
   #mti 是用于追踪 mt 列表中当前使用的元素的索引。
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

import hashlib
from randcrack import RandCrack
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

l = 
c = 
Num = 624

rc = RandCrack()
for i in l:
    rc.submit(i)
cal = 0
for i in range(Num):
    cal += rc.predict_getrandbits(32)

key = hashlib.sha256(str(cal).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag1 = unpad(A.decrypt(c), 16)
print(flag1)

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from extend_mt19937_predictor import ExtendMT19937Predictor

L = 
c = 
Num = 624

predictor = ExtendMT19937Predictor()
for i in L:
    predictor.setrandbits(i, 32)
cal = 0
for i in range(Num):
    cal += predictor.predict_getrandbits(32)

key = hashlib.sha256(str(cal).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag1 = unpad(A.decrypt(c), 16)
print(flag1)

def twist(self):
    for i in range(0, 624):
        y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
        self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df

from randcrack import RandCrack
from Crypto.Cipher import AES
import hashlib

rc2 = RandCrack()
num1 = 553
for i in range(num1):
    rc2.submit(t2[i])
for i in range(624-num1):
    rc2.submit(getrandbits(32))
 
cal = 0
for i in range(624//4):
    cal += rc2.predict_getrandbits(32)
key = hashlib.sha256(str(cal).encode()).digest()
A = AES.new(key, AES.MODE_ECB)
flag2 = A.decrypt(c2)
print(flag2)

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

FLAG = b"SHCTF{XXX_FAKE_FLAG_XXX}"
p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
G = [random_matrix(GF(p), 2) for _ in range(64)]
I = identity_matrix(GF(p), 2)
save(G, "G.sobj")
key = os.urandom(8)

H = lambda m: prod([G[i%64] if int(j) else I for i,j in enumerate(bin(int(m.hex(), 16))[2:])])
Q = list(H(key))
c = AES.new(2*key, AES.MODE_ECB).encrypt(pad(FLAG,16)).hex()
print(f"{Q = }")
print(f"{c = }")
"""
Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'
"""

from Crypto.Cipher import AES
from Crypto.Util.number import *

p = 334641907675981737343904379204876337859127829299172648068105540032137951559908027120450949854596026146898543
F = GF(p)
Q = [(92408373140638310582912266568541040708090711689280871505631689622417484347016487049244869849344848494009962, 53959869712387349430336059834241967356744173550876450413296700728311848545577500067458604734684838108665050), (252347024205859090718692136370078190718071419535216876332667850755617010322625175614169994287981074023442001, 248109129148524862390611680382928105844063942809716627922076622327580907465285046951446750474905265881834033)]
c = 'bbf4e7820865cc2fa3739a1d86006d83015180776a3285d4c14f5ee95685ac1ef64122e0f3603a794b4f170ec827dbb1'

G = load("G.sobj")
delta = []
for g in G:
    delta.append(g.det())

target = matrix(F, Q).det()
q = 1327433362304639193864290941923656426545922990449
qs = factor((p-1)//q)

def dlog(y, g):
    y, g = pow(y, q, p), pow(g, q, p)
    return log(F(y), F(g))

ds = []
for i in delta:
    ds.append(dlog(i, 5))

e = dlog(target, 5)
w = 2**128
A = matrix(ZZ, 64+2, 64+2)
A[:64,:64] = identity_matrix(64)*2
A[64,:65] = matrix(ZZ, 1, 65, [1]*65)
A[:65,65] = matrix(ZZ, 65, 1, ds+[e])*w
A[-1,-1] = (p-1)//q*w
AL = A.LLL()
key = int(''.join(['0' if i == 1 else '1' for i in AL[0][:-2]]), 2)
print(AES.new(2*long_to_bytes(key), AES.MODE_ECB).decrypt(bytes.fromhex(c)))

FLAG = "SHCTF{XXX_FAKE_FLAG_XXX}"
p = 1167195242552699154956050457
A = matrix(Zmod(p), [[1, 1], [0, 1]])
B = matrix(Zmod(p), [[1, 0], [1, 1]])

H = lambda m: prod([A if int(i) else B for i in bin(int(m.hex(), 16))[2:]])
msg = bytes.fromhex(input("msg > "))
assert msg != b"$ Welcome to SHCTF!!! :)"
if H(msg) == H(b"$ Welcome to SHCTF!!! :)") and len(msg) < 100:
    print("Congrats", FLAG)

from Crypto.Util.number import *

def solver(p):
    for c in range(1, 2**15):
        p_ = random_prime(2**90)
        PR.<x> = PolynomialRing(GF(p_))
        f = x**2-c*p*x-c
        root = f.roots()
        if root:
            k1 = ZZ(root[0][0])
            k4 = c*p-k1
            k2 = -(k1**2-c*p*k1-c)//p_
            return (k1, k2, p_, k4)

def gcd(a, b, q):
    r = a%b
    q.append(int(a//b))
    if r: return gcd(b,r,q)
    else: return b
        
def Fac(I):
    q = []
    gcd(I[0,0], I[0,1], q)
    m = ''
    if len(q) %2 == 0:
        for i in range(len(q)):
            if i%2: I *= A^-q[i]; m += '1'*q[i]
            else: I *= B^-q[i]; m += '0'*q[i]
        alpha = int(I[1,0])
        m += '0'*alpha
        return m

p = 1167195242552699154956050457
msg = b"$ Welcome to SHCTF!!! :)"
A = matrix(ZZ, [[1, 1], [0, 1]])
B = matrix(ZZ, [[1, 0], [1, 1]])

while True:
    k1, k2, k3, k4 = solver(p)
    I_ = matrix(ZZ, [[1+k1*p, k2*p],
                    [k3*p, 1+k4*p]])
    pad = Fac(I_)
    if pad:
        if len(pad)%8 == 0 and len(pad) < 100*8-24*8:
            print(msg.hex()+long_to_bytes(int(pad, 2)).hex())
            break

#!/usr/bin/env sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag

def gen_param(B):
 while True:
  a = randint(B >> 1, B)
  b = randint(B >> 2, B >> 1)
  p = 2**a * 3**b - 1
  if is_prime(p):
   return a, b

def gen_dmap(E):
 return E.isogeny(E.lift_x(ZZ(1)), codomain = E)

def gen_tpt(E, a, b):
 P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
 R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
 return P, Q, R, S

def keygen(EC, b, P, Q, R, S):
 skey = randint(1, 3**b)
 T = R + skey * S
 phi = EC.isogeny(T, algorithm = "factored")
 _phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
 return skey, _phi_dom, _phi_P, _phi_Q


a1,b1 = gen_param(350)
p1 = 2**a1 * 3**b1 - 1
F1.<x> = GF(p1^2, modulus = x**2 + 1)
EC1 = EllipticCurve(F1, [0, 6, 0, 1, 0])
P1, Q1, R1, S1 = gen_tpt(EC, a1, b1)
print(f'P1={P1.xy()}')
print(f'Q1={Q1.xy()}')
print(f'R1={R1.xy()}')
print(f'S1={S1.xy()}')

sk1, _phi1_dom, _phi1_P, _phi1_Q = keygen(EC, b1, P1, Q1, R1, S1)
print(f'EC1:{_phi1_dom}')
print(f'PB1={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

a2,b2 = gen_param(610)
p2 = 2**a2 * 3**b2 - 1
F2.<x> = GF(p2^2, modulus = x**2 + 1)
EC2 = EllipticCurve(F2, [0, 6, 0, 1, 0])
P2, Q2, R2, S2 = gen_tpt(EC, a2, b2)
print(f'P2={P2.xy()}')
print(f'Q2={Q2.xy()}')
print(f'R2={R2.xy()}')
print(f'S2={S2.xy()}')
sk2, _phi2_dom, _phi2_P, _phi2_Q = keygen(EC, b2, P2, Q2, R2, S2)
print(f'EC2:{_phi2_dom}')
print(f'PB2={_phi1_P.xy()}')
print(f'QB2={_phi1_Q.xy()}')

key = md5(long_to_bytes(sk1)).digest()
iv = md5(str(sk2).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

print(f'enc = {enc.hex()}')

P1=(3722377589495565619388409947786216655637784681305941494147641084588810631146007176891913880271007127410796381111369183814847421656105900790804342643108*x + 8802687499644901060050022727432797409089156524380319488542634490587555795650045132570968389279817924873049502727897060507742746276768059101617693509917 , 3719477936206364187390068985145413157800621156741491559595580900652585286439418248577575633342364501408686579893456793185782751143171546872666909621050*x + 11747436493943707843147767337329761069262174137296210697323632536020627422974942280457502098526627796314363833333722260721915312017545212458579310144482)
Q1=(12915018802277618444467947405666732828949451340216601075081682365787173754226880050603374384885896424371918951679575583901988634116566784032229862869167*x + 9007776929782360909455509476806206197092770009777355629134584109191428394613216631397127762352766433731005414625380856231942679613039804604556902750121 , 3337874847860908062006392359743970721822062807701776864258214454048414930046512179257997474360178458090070482273898812428917737854703385268693787730341*x + 2466887347330511324773080125454207491097000379360268269630202404092782122675750917288514012045044575681782320156449148824691799574240195537304046598804)
R1 =(5658557527226961352379349695298022272034591708614537846197946821664407815672677132716039709980366402273967153471450029112980202032504963557614554232081*x + 11551357271600404735819563619419067751607101807322269228277150670297507970164565732253196369722035427850219878923530600036342343824249401164519444699925 ,265897976893439254153074131180525503299599682872457003045711147421296792144844696453821448204074723372166153583764179699404006841669171292261372682675*x + 724107740695298992152442683362664457782010273239642672266143745994073399611599972677572553191510548840256649548349879064220814619385494208383928832803)
S1 = (4449849950679627875144313300296652171690240777751013993956114741413640793976703228710890484448481014950788184128005223666200974595989394007996227889227*x + 10221990584477216572376167606081943897583234679837301896971110421576150195418475700069646493255665879797854652838863654289069021445601907647135585418877 , 2307462255914883623706392794727437281947383985198148884124180699306428786822285241218884618081037544088797503669931959199490244566153811635971236094925*x + 12114989818233896956637793499130020016761661447768788981097230464243285295294294464715758630408703103345278454759389501739054553571870662915301521850727)



EB1:Elliptic Curve defined by y^2 = x^3 + 6*x^2 + (4189289089477997468544979453822695400500584265495091803346578638134562448932335970687326793676571649785862746844702037419185523428130990204162507604142*x+8453144899752979274082603184674998770084621842778345709593026085665609787243919407101520453085615209143595825360981888699031968367621444521989681207925)*x + (10876663327831437262436092946202594533286519870258843389665958485316202856443113411424811891669071467324995879309148604251803514827408043800152902428079*x+4101994484351838878118339435531362623951299298760741543454654959627592905764432016193446997841956209731202742983657859454109374390742351108699397540937) over Finite Field in i of size 13175843156907117380839252916199345042492186767578363998445663477035843932020761233518914911546024351608607150390087656982982306331019593961154237431807^2
PB1=(400743151686086340244873453949520840608574156208868642818110176396852951486095204394646889447695188912538995843668914636276137300969251924860731987594*x + 8066723303558125260716197269861828046216772084431033719257537396188532673015028142277860187197048570426361924628036485855109504692435989532466549892337 : 7857822094787553865337300888116802881139911120764957076597259295643802343603595437056405429678918577452653990040253270552510408546662517341930347472071*x + 10256174272055348496449952390378894222811363081031264681923652307005325570743231607657784873505317820364596562401946711140198577008958311498216702686123)
QB1=(11265527532569587904111577151486645315441536837729457283471778056974474854267045024868622287870300007236540035625960216806930485893214503444708227243383*x + 11572347052548869297030219234396257199641564118601390459458935400217229709294039384097088201478090062341631595370187207194936531910796633969532025890187 : 1238001162632333913423959416649793026045237600008578022715875560482397022195744581004778851687493893610142113162366180305156034033668836817430095906149*x + 9355808802624221590053977160056741459388657876928397271333623542173291286953283614788931011423156931539777202646167976404136542556319294668512474371234 )


P2 =(26532669647185534216919632454563012758176036840369727404445318596643186844961014237696589494044586519996222505129162421855623059726778064289730847721912630181732006537411094550079658466738877742707225452302161480055637595147605056943238961551962912726857744351864942655080809408252483764908*x + 5812125798407648530557806453276971100052617607817970289640758782839745787156978571675000742270104615849816276857241701143604798144853734688276746422525568056414894955227600694186327090639953921900591841375148784726343182974080826517494429823506784951108570345230509782432748957198973176557 , 18170912231945774226275509320755918597241684399013829358085583068620150918112942721642278196145025327426502604698222039788533590901192438632167767861918617714856305276236364591982716806931138652301078418873525926290927769922064835154806942253196121491744473872376873132890629881196649490629*x + 63449364629814972232211370797703143791798005155742711649921757750076247418977215094671070824854640922496466244527853596337389541043547252641029497892777720706149127263347252874027177102007048788926192874731602916383267663436392366016251960068968104701970215355153537253807070741855232748775)
Q2 =(42136584137812471055239712605979664248723194584329825504113325543473782453710246311097778204257972969988889548651858896024346287087771416233601557428774910464027636344801801157477551245445626845622940230448413907258474601435777417704217302132342224824779399945380325818482777959384425291202*x + 28296368679146068828136641681710295025336645284295264101756993260272669740048044336924939223851691772872478126511624718538627825216594660061759605074294632848971213782292601886969141003803207582527211891134999395005856333909777310102168312969406698423350527993168642419225166941765898216372 , 24252723040347680701413751304028021538994021203882796882406562234397335939592763757242534129915362456370369381794876781527365640074695381315843810927200394729665283960373930566280914193406969798955462142448747998461967647076878739164506097299031556840321385018392828143097654049003741477775*x + 33267720985746675210299288173839504448704818085049573573782475394127405092079693799437115220623519093827817268067436033899592961243028616775476581238880321680412934083591896010475885530871761321530855678932407897123073884230850264069659060055805157529775052479253840099694804476053775909667 )

R2 =(38436619031110865991923879368273825144591134194842250127138499745263028798151562949280051166055337764784928604655345143493484071370950291098970176327526604356876742861468639960728907306223619531997103795068973049143179040759482549370743939713683059322455935027250781363099017038267572070382*x + 41093937892203747071226497194460174684840688215389654564992940699770179304781361874671172244464825887258292329587141807444383894136057220808847808753364679351973663750364054669449905253193218352790909945369307367433850610807189354403253554148345197834701648188048050606356011567979827517009 , 9875876467935369638084938067896432182208690144531378403534745071976760997736224070951195614692508013003420177331978612557059092387961951203758997069353790956443826183851256825228023334285334341067097662506368272794278783481229345549459566223386198635792121370861583720130236996379339906174*x + 19447561977724594192572514756713004769718033798185884029348217371868425699196934174482768588729693090959863175090532851846013603063398325098484647069673894219675495546444516464516218477904028091215303855695854982251862178713199631677332189311907166991170300285734973720209408448016404386279 )

S2 =(71249861083363466146240185589742072416947001294427348758335822282789347285654895938446726327788096800499999553209177039582953195361659982428068926448233527913023420037219259936495112851482429822958147790870077230730091177257985429649031364838060427183913400513554819344862904827490880772682*x + 39578052854960012026255637126705373821483266678906490093269284444545750491201374187150247754423052586191953109246769525121762606083950469754696333553496751583744856481664734887761273029389862834902994256675947446700980363194864181267638836314434750455189422736876156451018780319594859427229 , 39197547329694719539529974714972757635993347219971485992350815969532199306333306049850413360278269128003596216529445446572820778213349500212847637573581492691769295796335260726180320712869520367834322990402467146959135659931987007965917989228442334598796126593765472147605031327475567701086*x + 78070033755581537489222113608059840236619421090183039048402466605471070294742099301510439400541337232022512116279912957923221843363406417706677109027135474092494932420033158293877172615616465938036108381979097606754379539534265853790205211707045379351990977911885255397786139615991362742209 )

EB2:Elliptic Curve defined by y^2 = x^3 + 6*x^2 + (59535702210902206632057724266122403485782121930269490904764357850731481931811358892291834226309250891450990328900036049280010419604141194291637296730727328703913164680567403783556426953678285004014585121686544887056773006148356101004676806983339649844157509652742849487058509475632164255987*x+64852232435177399443640158784531454040944394241934383260903245435876484235545723851033335774817478661385417394748201477353536461419931926490835275348734525706542632524107755972171394421922803412948624633078480838779833967459391738992623265735881364492275499237263259819337503800949666114300)*x + (61050690806389187934769383126786350986004548885068804715147802394614409167263078704960954888018441383310078678346054616498251041749628728818830924510356529523120808407048389377565446266649410216170097464816755297151018034985942268859099759375206161519933062527753348065060632492394513384086*x+8077074439258024172434168944099867368398890225954529153626574422394594541950204447361509876049948251527290252332533540126109187259353923004317852092303146292126930346834737856487032520566066787020590518347408517607586872466242304341998561230199735904938577495873392435708081679419091264767) over Finxte Field in x of size 82049429049937972170744454730593345160514304243739159904783417843550315750231928581899391756256783736403989271048847542926715937076900048775072545358407957727845645357780713979087402767756607414183416359287811818280895339396273490061030555956264309782382325666413874887621917291859821985791^2
PB2=(416996386611953912381825671411217896862273056276393640633857992847371853210568257096183885552618362723081850781382485053310040111838223298831389037016745104797263137119258673015585863160793951306139520262051168484452018201607146541321879548245965120060708406056548188263109428770184470679*x + 20592158493675665198495392336832601510295492846540435551041621150757189812529173392073328659255009380759876334891966292009700608091292588069484836373960820208560629600373809653827704658519366030767296831927997226766001416180323174025471476178795433544546769173932191085724053540646639944729 : 71934255319779473319456231037521357239577461842639834638995781561962276154205648471319881543016508220120521945006188958766711918515927736666300390531510013013219752222136876849357120821173182094753920757720079350217559660597480161836396311343966037676936442963053804573072914962152460674663*x + 79176415376881574459252426057416542844132750411766663750705407197328587941817178923562720329407116594864696212948749892818055154804078699130984677442760292980510087006005991843768472531019069389511942796903023273249068773581958501468457621161962887712050221461681839141585467402591793645894 )
QB2= (81399207896220104838523199229123942836223942998672721447617471088799933546789833887166127001116791183009155784956302068892276943497990222792723633019021458579696541635684638373573953057978849292600240170943085361633813448722609135351165092224283296296707819206674751128093132678767574518299*x + 59565272697509141787703630456883972192553675699784211987893422193583642170431575906952477269198392298815160807657217599332116732898901549042831683061911999197598082798698793498902676161570298508553574866686598052406458954435987817164049241700002339342165193999242704894297418052166335638731 : 21930351134214703951291759959503306221382335091685056420498342039206078305903361133512863350368812584471061688170029056369164678056492881926814997907481142982389978084439411052754236340914978327950474951824251797939798502875399920157660381059113442352137267881283959649753286318015289023163*x + 32177434323242823799795301005877693615760991886819458542076959058162762244773500905362804118528323187241784967539643917408903962138638896033673432863920521413676017199387780524917678271106039934571641676244524711655457465408480508716026824510901729812960266245895067755449573368867399411326 )

enc = 2ba4fd55c06bfcc9d253d3a60ec1eaaa82d482ff671d088b4f1354ebad2400d54a3bdd1dd1e38bf25a334f5fd3ec98ea89

p = 13175843156907117380839252916199345042492186767578363998445663477035843932020761233518914911546024351608607150390087656982982306331019593961154237431807

import public_values_aux
from public_values_aux import *

load('castryck_decru_shortcut.sage')
load('sandwich_attack.sage')

SIKE_parameters = {
    "SIKEp434" : (216, 137),
    "SIKEp503" : (250, 159),
    "SIKEp610" : (305, 192),
    "SIKEp751" : (372, 239),
    "SIKEp964" : (486, 301), # removed after NIST round 1
}

# Change me to attack different parameter sets
NIST_submission = "SIKEp503"
a, b = SIKE_parameters[NIST_submission]

print(f"Running the attack against {NIST_submission} parameters, which has a prime: 2^{a}*3^{b} - 1")

print(f"Generating public data for the attack...")
# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2, num_checks=0) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly


P =(3722377589495565619388409947786216655637784681305941494147641084588810631146007176891913880271007127410796381111369183814847421656105900790804342643108*i + 8802687499644901060050022727432797409089156524380319488542634490587555795650045132570968389279817924873049502727897060507742746276768059101617693509917 , 3719477936206364187390068985145413157800621156741491559595580900652585286439418248577575633342364501408686579893456793185782751143171546872666909621050*i + 11747436493943707843147767337329761069262174137296210697323632536020627422974942280457502098526627796314363833333722260721915312017545212458579310144482)
Q =(12915018802277618444467947405666732828949451340216601075081682365787173754226880050603374384885896424371918951679575583901988634116566784032229862869167*i + 9007776929782360909455509476806206197092770009777355629134584109191428394613216631397127762352766433731005414625380856231942679613039804604556902750121 , 3337874847860908062006392359743970721822062807701776864258214454048414930046512179257997474360178458090070482273898812428917737854703385268693787730341*i + 2466887347330511324773080125454207491097000379360268269630202404092782122675750917288514012045044575681782320156449148824691799574240195537304046598804)
R =(5658557527226961352379349695298022272034591708614537846197946821664407815672677132716039709980366402273967153471450029112980202032504963557614554232081*i + 11551357271600404735819563619419067751607101807322269228277150670297507970164565732253196369722035427850219878923530600036342343824249401164519444699925 ,265897976893439254153074131180525503299599682872457003045711147421296792144844696453821448204074723372166153583764179699404006841669171292261372682675*i + 724107740695298992152442683362664457782010273239642672266143745994073399611599972677572553191510548840256649548349879064220814619385494208383928832803)
S = (4449849950679627875144313300296652171690240777751013993956114741413640793976703228710890484448481014950788184128005223666200974595989394007996227889227*i + 10221990584477216572376167606081943897583234679837301896971110421576150195418475700069646493255665879797854652838863654289069021445601907647135585418877 , 2307462255914883623706392794727437281947383985198148884124180699306428786822285241218884618081037544088797503669931959199490244566153811635971236094925*i + 12114989818233896956637793499130020016761661447768788981097230464243285295294294464715758630408703103345278454759389501739054553571870662915301521850727)
P2, Q2, P3, Q3 = E_start(P), E_start(Q), E_start(R), E_start(S)
check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
EB = EllipticCurve(Fp2, [0,6,0,(4189289089477997468544979453822695400500584265495091803346578638134562448932335970687326793676571649785862746844702037419185523428130990204162507604142*i+8453144899752979274082603184674998770084621842778345709593026085665609787243919407101520453085615209143595825360981888699031968367621444521989681207925),(10876663327831437262436092946202594533286519870258843389665958485316202856443113411424811891669071467324995879309148604251803514827408043800152902428079*i+4101994484351838878118339435531362623951299298760741543454654959627592905764432016193446997841956209731202742983657859454109374390742351108699397540937)])
EB.set_order((p+1)**2, num_checks=0)
PB =EB(400743151686086340244873453949520840608574156208868642818110176396852951486095204394646889447695188912538995843668914636276137300969251924860731987594*i + 8066723303558125260716197269861828046216772084431033719257537396188532673015028142277860187197048570426361924628036485855109504692435989532466549892337 ,7857822094787553865337300888116802881139911120764957076597259295643802343603595437056405429678918577452653990040253270552510408546662517341930347472071*i + 10256174272055348496449952390378894222811363081031264681923652307005325570743231607657784873505317820364596562401946711140198577008958311498216702686123)
QB =EB(11265527532569587904111577151486645315441536837729457283471778056974474854267045024868622287870300007236540035625960216806930485893214503444708227243383*i + 11572347052548869297030219234396257199641564118601390459458935400217229709294039384097088201478090062341631595370187207194936531910796633969532025890187, 1238001162632333913423959416649793026045237600008578022715875560482397022195744581004778851687493893610142113162366180305156034033668836817430095906149*i + 9355808802624221590053977160056741459388657876928397271333623542173291286953283614788931011423156931539777202646167976404136542556319294668512474371234)


# ===================================
# =====  ATTACK  ====================
# ===================================

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1

    if '--sandwich' in sys.argv:
        # Use the fact that 2^a - 5*3^b is a sum of squares
        assert NIST_submission == "SIKEp964"
        assert two_squares(2^a - 5*3^b)
        recovered_key = SandwichAttack(E_start, P2, Q2, EB, PB, QB, two_i, k=5, alp=0)
    else:
        recovered_key = RunAttack(num_cores)

"""
Computing image of 3-adic torsion in split factor CB
Glue-and-split! These are most likely the secret digits.
Bob's secret key revealed as: 3599349351989826939257244168875987905412334469321466246296914822246846713144
In ternary, this is: [2, 1, 0, 2, 2, 1, 0, 1, 0, 1, 1, 1, 1, 2, 2, 0, 2, 2, 2, 0, 0, 2, 0, 2, 2, 1, 2, 0, 1, 2, 1, 2, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 0, 2, 2, 1, 1, 0, 1, 0, 0, 0, 2, 1, 1, 0, 0, 1, 2, 0, 2, 2, 2, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 2, 2, 1, 1, 1, 2, 2, 2, 0, 1, 0, 0, 1, 0, 0, 2, 1, 2, 1, 1, 2, 2, 1, 0, 0, 0, 2, 1, 2, 0, 2, 1, 0, 2, 2, 1, 1, 2, 1, 1, 1, 0, 0, 1, 2, 2, 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 1, 0, 1, 1, 2, 0, 2, 2, 0, 0, 0, 1, 1, 1, 1]
Altogether this took 20.913691997528076 seconds.
"""
#sk1 = 3599349351989826939257244168875987905412334469321466246296914822246846713144

import public_values_aux
from public_values_aux import *

load('castryck_decru_shortcut.sage')
load('sandwich_attack.sage')

SIKE_parameters = {
    "SIKEp434" : (216, 137),
    "SIKEp503" : (250, 159),
    "SIKEp610" : (305, 192),
    "SIKEp751" : (372, 239),
    "SIKEp964" : (486, 301), # removed after NIST round 1
}

# Change me to attack different parameter sets
NIST_submission = "SIKEp964"
a, b = SIKE_parameters[NIST_submission]

print(f"Running the attack against {NIST_submission} parameters, which has a prime: 2^{a}*3^{b} - 1")

print(f"Generating public data for the attack...")
# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2, num_checks=0) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly

P =(26532669647185534216919632454563012758176036840369727404445318596643186844961014237696589494044586519996222505129162421855623059726778064289730847721912630181732006537411094550079658466738877742707225452302161480055637595147605056943238961551962912726857744351864942655080809408252483764908*i + 5812125798407648530557806453276971100052617607817970289640758782839745787156978571675000742270104615849816276857241701143604798144853734688276746422525568056414894955227600694186327090639953921900591841375148784726343182974080826517494429823506784951108570345230509782432748957198973176557 , 18170912231945774226275509320755918597241684399013829358085583068620150918112942721642278196145025327426502604698222039788533590901192438632167767861918617714856305276236364591982716806931138652301078418873525926290927769922064835154806942253196121491744473872376873132890629881196649490629*i + 63449364629814972232211370797703143791798005155742711649921757750076247418977215094671070824854640922496466244527853596337389541043547252641029497892777720706149127263347252874027177102007048788926192874731602916383267663436392366016251960068968104701970215355153537253807070741855232748775)
Q =(42136584137812471055239712605979664248723194584329825504113325543473782453710246311097778204257972969988889548651858896024346287087771416233601557428774910464027636344801801157477551245445626845622940230448413907258474601435777417704217302132342224824779399945380325818482777959384425291202*i + 28296368679146068828136641681710295025336645284295264101756993260272669740048044336924939223851691772872478126511624718538627825216594660061759605074294632848971213782292601886969141003803207582527211891134999395005856333909777310102168312969406698423350527993168642419225166941765898216372 , 24252723040347680701413751304028021538994021203882796882406562234397335939592763757242534129915362456370369381794876781527365640074695381315843810927200394729665283960373930566280914193406969798955462142448747998461967647076878739164506097299031556840321385018392828143097654049003741477775*i + 33267720985746675210299288173839504448704818085049573573782475394127405092079693799437115220623519093827817268067436033899592961243028616775476581238880321680412934083591896010475885530871761321530855678932407897123073884230850264069659060055805157529775052479253840099694804476053775909667 )

R =(38436619031110865991923879368273825144591134194842250127138499745263028798151562949280051166055337764784928604655345143493484071370950291098970176327526604356876742861468639960728907306223619531997103795068973049143179040759482549370743939713683059322455935027250781363099017038267572070382*i + 41093937892203747071226497194460174684840688215389654564992940699770179304781361874671172244464825887258292329587141807444383894136057220808847808753364679351973663750364054669449905253193218352790909945369307367433850610807189354403253554148345197834701648188048050606356011567979827517009 , 9875876467935369638084938067896432182208690144531378403534745071976760997736224070951195614692508013003420177331978612557059092387961951203758997069353790956443826183851256825228023334285334341067097662506368272794278783481229345549459566223386198635792121370861583720130236996379339906174*i + 19447561977724594192572514756713004769718033798185884029348217371868425699196934174482768588729693090959863175090532851846013603063398325098484647069673894219675495546444516464516218477904028091215303855695854982251862178713199631677332189311907166991170300285734973720209408448016404386279 )

S =(71249861083363466146240185589742072416947001294427348758335822282789347285654895938446726327788096800499999553209177039582953195361659982428068926448233527913023420037219259936495112851482429822958147790870077230730091177257985429649031364838060427183913400513554819344862904827490880772682*i + 39578052854960012026255637126705373821483266678906490093269284444545750491201374187150247754423052586191953109246769525121762606083950469754696333553496751583744856481664734887761273029389862834902994256675947446700980363194864181267638836314434750455189422736876156451018780319594859427229 , 39197547329694719539529974714972757635993347219971485992350815969532199306333306049850413360278269128003596216529445446572820778213349500212847637573581492691769295796335260726180320712869520367834322990402467146959135659931987007965917989228442334598796126593765472147605031327475567701086*i + 78070033755581537489222113608059840236619421090183039048402466605471070294742099301510439400541337232022512116279912957923221843363406417706677109027135474092494932420033158293877172615616465938036108381979097606754379539534265853790205211707045379351990977911885255397786139615991362742209 )


P2, Q2, P3, Q3 = E_start(P), E_start(Q), E_start(R), E_start(S)
check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
EB = EllipticCurve(Fp2, [0,6,0,(59535702210902206632057724266122403485782121930269490904764357850731481931811358892291834226309250891450990328900036049280010419604141194291637296730727328703913164680567403783556426953678285004014585121686544887056773006148356101004676806983339649844157509652742849487058509475632164255987*i+64852232435177399443640158784531454040944394241934383260903245435876484235545723851033335774817478661385417394748201477353536461419931926490835275348734525706542632524107755972171394421922803412948624633078480838779833967459391738992623265735881364492275499237263259819337503800949666114300),(61050690806389187934769383126786350986004548885068804715147802394614409167263078704960954888018441383310078678346054616498251041749628728818830924510356529523120808407048389377565446266649410216170097464816755297151018034985942268859099759375206161519933062527753348065060632492394513384086*i+8077074439258024172434168944099867368398890225954529153626574422394594541950204447361509876049948251527290252332533540126109187259353923004317852092303146292126930346834737856487032520566066787020590518347408517607586872466242304341998561230199735904938577495873392435708081679419091264767)])
EB.set_order((p+1)**2, num_checks=0)
PB =EB(416996386611953912381825671411217896862273056276393640633857992847371853210568257096183885552618362723081850781382485053310040111838223298831389037016745104797263137119258673015585863160793951306139520262051168484452018201607146541321879548245965120060708406056548188263109428770184470679*i + 20592158493675665198495392336832601510295492846540435551041621150757189812529173392073328659255009380759876334891966292009700608091292588069484836373960820208560629600373809653827704658519366030767296831927997226766001416180323174025471476178795433544546769173932191085724053540646639944729 , 71934255319779473319456231037521357239577461842639834638995781561962276154205648471319881543016508220120521945006188958766711918515927736666300390531510013013219752222136876849357120821173182094753920757720079350217559660597480161836396311343966037676936442963053804573072914962152460674663*i + 79176415376881574459252426057416542844132750411766663750705407197328587941817178923562720329407116594864696212948749892818055154804078699130984677442760292980510087006005991843768472531019069389511942796903023273249068773581958501468457621161962887712050221461681839141585467402591793645894 )
QB =EB(81399207896220104838523199229123942836223942998672721447617471088799933546789833887166127001116791183009155784956302068892276943497990222792723633019021458579696541635684638373573953057978849292600240170943085361633813448722609135351165092224283296296707819206674751128093132678767574518299*i + 59565272697509141787703630456883972192553675699784211987893422193583642170431575906952477269198392298815160807657217599332116732898901549042831683061911999197598082798698793498902676161570298508553574866686598052406458954435987817164049241700002339342165193999242704894297418052166335638731 , 21930351134214703951291759959503306221382335091685056420498342039206078305903361133512863350368812584471061688170029056369164678056492881926814997907481142982389978084439411052754236340914978327950474951824251797939798502875399920157660381059113442352137267881283959649753286318015289023163*i + 32177434323242823799795301005877693615760991886819458542076959058162762244773500905362804118528323187241784967539643917408903962138638896033673432863920521413676017199387780524917678271106039934571641676244524711655457465408480508716026824510901729812960266245895067755449573368867399411326 )

# ===================================
# =====  ATTACK  ====================
# ===================================

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1

    if '--sandwich' in sys.argv:
        # Use the fact that 2^a - 5*3^b is a sum of squares
        assert NIST_submission == "SIKEp964"
        assert two_squares(2^a - 5*3^b)
        recovered_key = SandwichAttack(E_start, P2, Q2, EB, PB, QB, two_i, k=5, alp=0)
    else:
        recovered_key = RunAttack(num_cores)


"""
Running the attack against SIKEp964 parameters, which has a prime: 2^486*3^301 - 1
Generating public data for the attack...
Performing the attack in parallel using 14 cores
Computed image of 3-adic torsion in split factor C_B
Bob's secret key revealed as: 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624
In ternary, this is: [2, 0, 1, 1, 2, 2, 1, 1, 2, 1, 1, 0, 2, 0, 1, 2, 1, 1, 2, 2, 2, 2, 0, 0, 0, 1, 2, 1, 2, 0, 2, 1, 1, 2, 2, 2, 2, 2, 0, 0, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 0, 2, 1, 0, 1, 2, 0, 1, 1, 1, 2, 0, 1, 0, 2, 1, 0, 0, 0, 2, 0, 1, 2, 1, 2, 0, 1, 2, 2, 2, 1, 1, 2, 0, 0, 2, 1, 1, 2, 0, 0, 2, 2, 1, 1, 0, 0, 0, 1, 1, 2, 0, 2, 2, 1, 0, 0, 0, 2, 0, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 0, 1, 0, 2, 1, 1, 0, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 2, 2, 0, 0, 0, 1, 2, 0, 1, 2, 2, 2, 1, 0, 1, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 1, 0, 1, 0, 0, 0, 0, 2, 2, 1, 1, 2, 0, 2, 2, 2, 1, 1, 2, 0, 0, 1, 1, 1, 1, 0, 2, 1, 2, 1, 2, 2, 1, 1, 0, 1, 1, 2, 2, 2, 1, 1, 2, 2, 0, 2, 2, 1, 0, 1, 1, 1, 2, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 1, 1, 2, 2, 1, 0, 0, 1, 2, 1, 1, 1, 1, 2, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 2, 1, 1, 1, 0, 2, 2, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 2, 0, 1, 2, 2, 1]
Altogether this took 11.799392223358154 seconds.
"""

#sk2 = 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5


sk1 = 3599349351989826939257244168875987905412334469321466246296914822246846713144
sk2 = 265224889924040230352809890018188742288829460808797625767564487574491813646343173069577492003667305149036083853277964262066159526193356944364624
key = md5(long_to_bytes(sk1)).digest()
iv = md5(str(sk2).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)

enc = '2ba4fd55c06bfcc9d253d3a60ec1eaaa82d482ff671d088b4f1354ebad2400d54a3bdd1dd1e38bf25a334f5fd3ec98ea89'
enc = bytes.fromhex(enc)
dec = cipher.decrypt(enc)
print(f'flag = {dec}')

#https://github.com/jvdsn/crypto-attacks
n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39
d_zj=???

from Crypto.Util.number import *
from tqdm import *
import itertools

#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 149172698687247343307484774427463947040435385939538317995577802933708356659744781308849658149199463270402946054959026247011496643609722381036883462993606208405454448793748282856217226973570288117498818638210423816294135228225752144034736417495450129714250843040389723696691326017062575682989124677170212774709
e = 117932126002671581139669626170313849654365346787524775666511151162210096339679521576248537514813055641658722582914817481701142826861992970974206985137736311670025047752207632786439134855261541672012123572997654885689727972923659090161642085293034838535696206768459211817851404605357080649176502772728128885161
c = 5560665954852260703690321742771294743847646190564920056638605621636133720600072404637746086157764356927591996611862975162275415163691292729424412545560091018172812509230401361899309377868998693154480684535377865697939714965280441927137203589475324582174585416573174423912557361267766810988676863548944796515
dm = 0x2498aa4c85de5a33d5766f28d879f0df7175f43dd71cd4ab56ab67bf76334e6e3dcb
dl = 0x4c21c14305c34ed8f5e8879452c4ce569ce0789e6b39

leakh = 270
leakl = 175
dbits = 512
dh = dm * 2^(dbits-leakh)

k_ = e*dh // n

PR.<x,y> = PolynomialRing(Zmod(e*2^leakl))
f = 1 + (k_ + x) * ((n+1) - y) - e*dl

bounds = (2^(dbits - leakh),2^513)
res = small_roots(f,bounds,m=4,d=5)

from gmpy2 import *

pplusq = res[0][1]

pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p

d = inverse(e,(p-1)*(q-1))

print("d =",d)
print("p =",p)
print("q =",q)
assert p*q == n
print(long_to_bytes(int(pow(c,d,n))))