Challenge Files


Alibos

	c = (pkey + d ** 2 * m) % (10 ** d)

Rearranging for m:

from Crypto.Util.number import *

pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc  = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336

d = len(str(pkey))
m = ((enc-pkey) * pow(d**2, -1, 10**d)) % 10**d
print(m)
print(long_to_bytes(int(str(m)[:108])))

# 6170704326493336128242608193100736601774626903966803036318189045381903593682775829229200905376968543264526051111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
# CCTF{h0M3_m4De_cRyp70_5ySTeM_1N_CryptoCTF!!!}


Beheaded

This was like the famous ECB penguin, you could rescale it in gimp or use a block where all pixels are the same colour without needing to find the key.


Mashy

Guessy trash, had to guess that sh was a483b30944cbf762d4a3afc154aad825.

Then you can just send a bunch of md5 collisions, so that xor(h1, h2) is b’\x00\x00 …’


Forghan

n = (p^2 - 1)(q^2 - 1) = (p-1)(p+1)(q-1)(q+1)

I think intended is find primes that are both p-1 and p+1 smooth.

But the flag is small enough that you don’t need to.

Let’s decrypt just mod p+1. So we need phi(p+1).

We can choose a p such that p+1 = 2*p_, then phi(p+1) is (p-1)/2.

for p in range(100):
    if is_prime(p):
        print(is_prime((p+1)//2), euler_phi(p+1) == (p-1)//2)

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

def get_pr():
    while True:
        p = getPrime(256)
        if isPrime((p+1)//2):
            return p


def solve():
    #p = get_pr()
    #q = get_pr()
    p = 103324310827731387858898612794187090070009196324984411183894052950789734406661
    q = 110770244583604777325663981197391176452423648810117191163122603417313145192501

    io = remote('00.cr.yp.toc.tf', 13337)
    io.read()
    io.sendline(b'S')
    io.read()
    io.sendline(f'{p},{q}'.encode())

    io.read()
    io.sendline(b'G')
    cp = int(io.readline().decode().split()[-1])
    cq = int(io.readline().decode().split()[-1])

    io.read()
    io.sendline(b'P')
    gp = int(io.readline().decode().split()[-1])
    gq = int(io.readline().decode().split()[-1])
    yp = int(io.readline().decode().split()[-1])
    yq = int(io.readline().decode().split()[-1])
    io.close()

    try:
        phip = (p-1)//2
        dp = pow(yp, -1, phip)
        flagp = pow(cp, dp, p+1)

        phiq = (q-1)//2
        dq = pow(yq, -1, phiq)
        flagq = pow(cq, dq, q+1)
    except ZeroDivisionError:
        return False

    print(long_to_bytes(flagp) + long_to_bytes(flagq))
    return True

while True:
    if solve():
        break

...::::: CCTF{f!nD1N9_7wIn_5m0OtH_1nT3GErS!!!} :::::...


RM2

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

io = remote('01.cr.yp.toc.tf', 13371)
io.read()

def get_super_safe_prime():
    while True:
        x = generate(1024)
        if isPrime(2*x+1):
            return x

#p = get_super_safe_prime()
#q = get_super_safe_prime()
p = 176190361114405660140775371642244103546320715334539918001492645857771593552107955448402648350633693638480545186750598651678784235721661177218038230550079910726963779269165803404500415338229375745350440434088252741915552117559295023850055262211395546349293984582637753204891730267351496766430177371001101202579
q = 174673912453530565721373096945468158471423845542688334400192438665743138238497195281153045123700977896509756132766346293652660746134615199680910832008097698850013139496501456054035329932355735673848807210672424697329408424184179185667926436594508177456167574196681896497806043904509301791431726034346952707019

io.sendline(f'{p},{q}'.encode())
c1 = int(io.readline().decode().split('= ')[1])
c2 = int(io.readline().decode().split('= ')[1])

# 	c1, c2 = pow(m1, e, (p - 1) * (q - 1)), pow(m2, e, (2*p + 1) * (2*q + 1))
e = 65537
m1=pow(c1, pow(e, -1, ((p-1)//2-1) * ((q-1)//2-1)), (p-1)*(q-1))
m2=pow(c2, pow(e, -1, 4*p*q), (2*p+1)*(2*q+1))

secret_string = long_to_bytes(m1) + long_to_bytes(m2)
io.read()
io.sendline(secret_string)
print(io.read().decode())

# CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}


Alilbols

First find f, g same as ‘Find the Lattice’ from cryptohack:

    M = Matrix([
        [1, h],
        [0, q]
    ])
    f, g = M.LLL()[0]

Then decryption:

    assert c == (r * h + m + r) % q

    assert (c*f) % q == (f*r*h + f*m + f*r) % q  # *f
    assert (c*f) % q == (g*r + f*m + f*r) % q # sub g=hf
    assert g*r + f*m + f*r < q
    assert (c*f) % q == g*r + f*m + f*r # m and r are unknown
    assert (c*f) % q == r*(g+f) + f*m # factor
    assert (c*f) % q % (g+f) == f*m % (g+f) # get rid of r
    assert m == ((c*f) % q * pow(f, -1, g+f)) % (g+f) # /f

Just have to brute d:

h = 1051643987107349427988807326909852110640860009433515828832892541964729933410444984350917250524103015414239941369074041041830326426044333499878031164851095096864048639115431370526747014210332286314344073411522846701723463410585601251886732229726828022089809603850477551571014006202841406236367999378786782206165205893353928598469661871284779486855440579818275314024966224282757807716013799903830828885606714972634243850947534165272668985513949964901606268939300116019465522042467054120201087606016018354238401711720121586874288767235317479748890350702705575809130664969776549574720593740409234863974057904204809404816059921579771581800937241591669455683460570640868196509926763901079838233646036933530095891316054589051458146768287967886035091641162494322987627448810201550901588438560433001422233269632915351406169253963308421081459981594969405377353502889363324282815864766827664453823780238352371809048289845094882346227809082005375092441877966603138648719670349093616548820955566204871333952902983753935678447080673827214244142614295192263451840766771122229866931492260663320087497820892824540996643905125018452302747847009
c = 11913143174789215053772744981113562063689725867199301496294410323568897757042952642806438602327917861884988292757318755590132189620231444302311290566584065812614959093870787195145654508262419270742989923415342357807325941686508030706603920412262004324188375072184983301522882728578077572816154054220606088703932092256905881975876112779175003897105313776239681492514925430817300633974666123599685062340158348009344351002327049272743679109535286730751345284084148118733529966364414749672437370878526710641430471595906340522772252875146681541656231708112317601000655090279925720590940060372738708208419449824043905057860829031242339842131799965043031307394209699264362321397162645220002253271689678364848888381499587038475895945238726252440250183268252483198408039250213490525880829604473555612305513974817850974135874728084839426045420913060975464553734293001460752648937744531874552694145500413222582269910431269597066268600572899619407093373565994271589940926018891922169454906132284552523035481664164354874071831210264979733079749696197917769435226866441989054017071332158916586376454753209296136133271926449919437888563234409

for d in range(1000):
    try:
        q = 4 * 100 ** d

        M = Matrix([
            [1, h],
            [0, q]
        ])
        f, g = -M.LLL()[0]

        m = ((c*f) % q * pow(f, -1, g+f)) % (g+f)
        flag = bytes.fromhex(f'{m:02x}')
        if b'CCTF{' in flag:
            print(flag)
    except:
        pass

# CCTF{4_c0N9rU3n7!aL_Pu81iC_k3Y_cRyp70_5ySTeM_1N_CCTF!!}


Joe-19

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

resp = requests.get('https://zacharyratliff.org/files/eMillionDigits.txt')
e_digits = resp.content.decode().split('\n')[4][2:]
n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433
c = 7109666883988892105091816608945789114105575520302872143453259352879355990908149124303310269223886289484842913063773914475282456079383409262649058768777227206800315566373109284537693635270488429501591721126853086090237488579840160957328710017268493911400151764046320861154478494943928510792105098343926542515526432005970840321142196894715037239909959538873866099850417570975505565638622448664580282210383639403173773002795595142150433695880167315674091756597784809792396452578104130341085213443116999368555639128246707794076354522200892568943534878523445909591352323861659891882091917178199085781803940677425823784662

for i in trange(len(e_digits)-154):
    for k in [154,155]:
        p = int(e_digits[i:i+k])
        if isPrime(p) and p.bit_length() == 512 and n%p == 0:
            d = pow(65537, -1, p-1)
            print(long_to_bytes(pow(c, d, p)))

# CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}


Honey

load('https://gist.githubusercontent.com/Connor-McCartney/952583ecac836f843f50b785c7cb283d/raw/5718ebd8c9b4f9a549746094877a97e7796752eb/solvelinmod.py')

p = 10580731215444436219213907263947534038012197972307836319229421193761088798378768844649759133142120180834573817149711299466707823017636232456526471274387917
Q = [6718668664591596190749745980002066645380242844394957953766947533978323053938214647829798301606252456858132121628517723050462291300790766055200866765561610, 8738840830394886495658505803088103824478963010774845789433253508554356383249611502157307334585157729703873877797759121271071421201959116272886732798936523, 4388762712805764363921857352899834586382140923234814556069490536704913653848525595836491615636446563386705915348021173847271741862809075809151508973332816, 3663706247989213864330218414789109172658418861584264092087052781618522795676355371739296186667918464732397854703792563460353675590182379535358561615166754, 10397730940373180549512945920847346184926672474430866208628825035104473525758952069910968144296138220861205803231072660136999110567752870928953292888013817, 7950983396364741732874562189206547723862955251595526752956177377987683115942827501152009639962778147887569469649852864894630521759276627026901168996371682, 4533165373271154956275563812280832107592547920299130443910706773435844651231402604986107252454770256826684895729900344877444002682896222483157835711226276, 234527648838985018479849393379369972316648524004050156622962478277970628212208049885578895953447529009579881605066831810617219492342569126524704457098602, 870946394610707169333783318085559836426827503011955242395779894700298192587685130680102208909573921059078858816359885827349281892186755920839352494224983, 5025393101560564396356619431938053414422489109406396725377683594254768077793838379117179092536396259414266971990125716674162127500490058572594571364978294, 5914192169617888877888201158713062853387719050723973971874176184801960297380845845091259990664210178355882621876155306106794686897854891414999449337977781, 2315609284318723939818174971181608382568372323836754133265010413836452399043354382657889810068171230196496294710150903020084150025606782486579490225752163, 7278167622527482910919537896950398911672667355929695202886784227621290914468002099686668156909569183497765732237075799745632960354306268680765408194219074, 3334584846711780119716613440720851482199838919351927489954344426327712973616885459737471991960238971274273643566666607141850753561424427088261862873317161, 10418397794302836806813296591826255845845380563102199636140458670781241436466478273414138749593148481207713557016996462238845705251702717702279222414513227, 8928267741189301140931758366885435860144549752680480164627323600501278650103818630920534258909582593266779000356145650416276415560226176904904552964196921, 3371514716248416335324237152123624115597170761078576760713238311485522010416246207731778456501311675041827750001670698984335573888627309609534659722697174, 3802217515688979225517388823688564230191961273039428065604146662684362686419670392762755984078261072614619934671572327384351597903233780846163893180876244, 2363399549320749312563257796730356164186914867645487733176402567625567991193120859507532138374793392237469893062402307645814490930874653088116729203724851, 10221767730316631512882371487958453352895713655492241322139865275323706929127996334620105099751973217983332705204535216804829987329684674632121801754529472, 2309440702968799222696132507585555901684240893289264193546892279919675495689944211715270510347394465285317239758024734161176699837687742722383530547735726, 5768185970426887633783322939933762164095055854707759575404348181421158843802654199133776622565384843677610666356549368021172121302926969754865633752131083, 3229518654067354667224244723968136366109210341994628338992752927462431316675552817799465987425719486448276862390918033544772400219803600904202906882850710, 9261930571620802581580992489567043178258044978932724785185749415955521702331959591680386023118398455066896674799447994060060156036800986190467008880726445, 2202162000802916921896507108984564185119471354726317829850206292755815439071735424116041491064894922930900262540589602333676063925873357256494020426758849, 1449198886322850923273373987785167865779477069790726992542423846556138762913056524689998313112599261515223680429584445016474216381861998363527368722991846, 8372052560034461177472546395510480308837387803551378399004608402463282066003862653368875671946863748209051044725913651881213858335224750549176875818647614, 1554572177534183877889322947083536921680809086638640689433294150868422460719624621258231995856944045776876555664816113444481761122803489100212103150005950, 10304720995101153898600333216365877709018991122985401884049110267116778080162237155472336396606109372189653686733770775660895990549286854727042270667997449, 9702831715765050072649082617719386580543641764650576307262259428035281535816750758018451681417440458250169771442858047124693499821240155899358663466925522, 4983986466837077050816175727911146971276599399191126236666755181304580074902883995859030897874305902445659355326021836801836996577665092276845357389900055, 983210432268706135181772492997088637756153310076409721616450343187239073604891492532080986521255675448499887782529162112441952861587689660048849369850769]
R = [8922553268219903948421811612403588317187402276064169063400419617931637566221670948925221403527928336656976084021780421068421112325215152715630319708159148, 1960697234007608888633325436691320507012497445090151112947144246088597317322303593936974554881161091213718329061011703885436579261559669838148253146762736, 5876944865176517279136475269375710514719489457672467542904948332791352244229042691977616905122711469012731652511966060550749288338599104284986451669586397, 10560136356360422684127995001096871178761635291417665630629868184624616925939841693017240341233504589896610287855672892399213367967385666891688408976236926, 477096251733995832965266836067676961413182629438628989729801411920869543083075545758386996801847267554704996660190900105380190625423846876906822024677634, 7001514955678391252130680521301315254365131738168087539892724691183104608345983375763663321467662055864103520121513349630333839818372656472731157470876337, 3894488356665934776074291789545516608573077899099880057920210752197885106521699021123658077208789295954145485399473386424677782787720074605813565437678385, 6084641463140385894120457093933350076091808742065950836200598466936433741373700151235571333073965513559605688011967994215074945374832957951384088589789549, 6429023674027239778212676334778900557043774851747196071499704016422574667955121145943674677254291410204037372996870181094090300709994594837656541352954321, 974464046378184190666336249935678253753198649184272269465353741281529523364289314148552833155935080422698020734516538377662137879089845095565536185765703, 5275384626572520577089146723078373110279682903874445477027602487061203157331398955233780208890725281673434536867800450553737656852356536771518379108118530, 7195767683001605593626199889963767438584070902169912442665828755648712278523740276132000225353756257232761885567134364203207306842108602537457408438487869, 1960155276835684836483043402384876176138942980630724993481564836712252228823186653467973806509964860286129730847244573674203959835565358735171611743573721, 6414607819273473402861616605113355396690170400984793217629732347141796693554056264547151212348354332930126795040213921009711560216969452391748438893237750, 3344964019305423035551401397282638905496921053458747459062023331678484337724980196690184898986671355848101101352105363764794975082772539709853216580762130, 5599385562588302350377616767130563945375472947459594912838322011021483641484084692396462025157944023828872267520122213089523093591160284337483108416804096, 9490045098551912983475126253859124028793327975874647810947095579199208473971726763051464010595903748080632329362605820021188148160826282120484098519748832, 980400922804123638777377509067942595214234592161404114303498013065244168965487370334832921426484278913774963761155003569793282819717667783351454812080994, 2772369382727364487748752144766350276094463435156818133766210304998890765120785013435379746537938377688617479112518505844159436213691418873590807740501183, 2338271137215119073302625621754099128003710500967811947590498668688826448575898279561111743087002717955161536157254689000474464404087443266193145449601031, 11773104862539842923315548180471993854469651503131148446111338098437913152663007837927793233931818835121946274135336436554801339749906320765919816150768, 7022131435585860015767289025786078578929344550873832550705723505006303288639135070849692494020122369694090619694760175970759059981608871097298624956669246, 9062158671807923729547552523768819638817707994079942965412925347441853183471973898478745711676153003756450481351777543455041815438536630317647408008349357, 641428039466528875429106458292463262780539744201857515833377175893334510962304373010401729801987725599439620073783868719664061882399367340158128062151780, 9636846145225909579086917154824161374486916920345217833190333031690359415616710658317308376119096253360425924297858397657697468296746934075225665559206030, 480796179229094678008918831581475398488769027287954488301969143979307355466114726392701279092691566949082439457297527772794149828193400419285116237063338, 7726757640854263742178678415761753342099387727318458723726925176786999799204056696883433346568600944559959849253863013300907357120126559055735593380638961, 551534415366550033034654093228329954588738781407008585088422737955391043381667720876717529438845777841508116853874405455280903517864352822604194884203656, 2135598634800053933515509095633720732412542790075717247869348997292949946344227105219967710854885153055617943193159899627517699960920415492992774438014041, 1680242449902645450228202409049382139482100876672724104665964994414865664877710770701122475977142858601068246748276652246938681740022531970523695731126206, 436320498659370791836085607479390848415464961245449366885835640616716752879866126057724425537944356751844317980881005608075886211154052092270888058429787, 4102523817041969170017113001399252035243358293719837916039521471412151711746047572340376418109842112515873700164747338421862615679590520014959369523777063]
S = [4389820170235953517860364281419052587762385444517203945856665517072263529411621622474249480804818285716662154444854074939122170918939074730520091008754679, 10274488321950407401790238304858775303749809597573328350457719402010568443492374388509295355784873292280254116167747959663379913408799485392015111636115272, 7413556897779783875511997253964328306011661062497568739340607424890313315434489440969977560260194970241163209968988660276109536299848001455072705137702052, 10385679419514177727801069016719283683697529805734389950368725106396939072509839502286093730172215158898251533786500497578747904349856564856054102927847131, 6386209810414906928429352824399745808560059492214757951425372272591372428785367326567204502131184260857447725722068674542931096991341451850846209503213310, 699060860182347708294712482476262878008951502586470987307146194685783850677219935862211847525612405824474382122868643521962157410369483858428437433802395, 3482063900392942412450041046839813864192488604261419419162091087116878838189062406913587662602295096636481252242577251563441565388543873530900962308450590, 5752782775722534186844731777766684686828626762801341093006843547008915880093927377014105260314050196609699164926717998841388194942556402699285523644651583, 4477944786670422304592908174461368396168580171651041832449759231077050962444090886920563302603784981035116689839335069690875797644553684152368376089740517, 5663531682848751034979876476955107364567717396957230368140915480695954150088052156264521615690161327525898382714131905580517915060427960250740110846321921, 5343294510843224726960051115907810365241970373986845465490090821566645536683695042467985025063439338770116316455211944030125820601506874250685838077414765, 8432688027895892738831218358369397874948328355540048945541749304849571948638169902486647265119397307193449002927427840453857643697175667051504836511635801, 8974418251288081645329898313903422373193272601106837017923535786950979222125740970411725976034947989767143786286397290996756916960291029965672692318584390, 3367471493907450997862234076499110882206518716388236141312548251406626961838619595519805436447472248133422979102036617759221276869918910189482246041609756, 9787518698663334219763616437865759554315749369906898604904977007297368987715422535407542350049111845605011307829034744443271718643291528381794716569586150, 7423298611637442306439453382713995476685370148677494272333567929180589186347708172471032286209947149761644993151042408431548488945145292037694546868884030, 5591656321514817104832226351286824953278894430528912246855770091334337189386156994498331013600732669813560603667226878637404391237947398475280409452591013, 6425108527382412819259579180312607504985609322110590326058191420486308943785080395001318724782575187718535133704219706236946232717333616646838328259100174, 1986072520726417425427679478185786673218113837249425820170849864471171328875606626923270664642579676457285438864056080352157246995774517812392120146048999, 5085759490547346080963649291763871068034757573012867868532204864022791365366745839456310985148663327808561601274994541505734129506831803550600738607170703, 6883330982174382523423400136207766091739299571009207949454774998664997037115272990237878573502506026799645646664956134682833693219974019271740996314084220, 3008412285222633004812698063455902388460013611944185187747762649311442328686187279186972723448077521425052318221865300502697494418867793831761784796146329, 9547325670583212399117684599284936334790443591395268814958834705867928621240882386996085347052830889322724160452729359284992294890584292625829913315628265, 1387461799657365419593288084566026147529011675413652640829187706708872066267641962620159408303872024421411747751690792902149761832079721583778430712988299, 2093635222672050417361673475374966389314266702410603863643637918543784930893405832179904330416148995313591588929177333026382745340633946128791737631559286, 8413424329301946557805781268429552577339778139904799140486659388945506980343653897206690153402822892272378378085908749995513711021119914769801970795906117, 6743445162380434316634371637355512041805280159276931422012464596435558338432827675791139455542184532473287436049595748235961499758716697674776760822162391, 1706184129470213725753097073154985919221181897433450716898208607625832464228411992900434982560203334218404626447424408012817411257665032706434306723906871, 1188503046129710474378492502021666062040985983530761819828342979325166292485440608536173516789179154601587903599847267180858095017007891547798890802090080, 6398862094282462456834873185064362330936738060688527379705123125559724680574585721467123968313071365176318010618981170019917278363707049487278610027058585, 1827205671808118170959457466922915851906256049105694256301380823860317738339383848734269783842511423911532135506082729000044271560428423457063013176002958, 4296939764995860347968082436772567300063081379392577066061720737920992283479200350022263164173968370055486217109628430523063986426005741344085155171587948]
C = [2312453804397990204892582347458673184184584053391181580849656202381982276483135032773767708029907426388840618138608941250788745829088238589339462137662516, 10523194306636352419831471584744199603299973937259007033119401866043123235256118686290774285411893111835433604432082195914308420845569896693674208644701928, 8625321422409900297730698589684636810222608572364004227411854906715574297306124060030713845833976664653817196364988412308992879167741430256046508164902265, 2203036357494864574281685606458518951592160562338358743010726696365683441724958156704554110208947394458113054047499157258753175446414976136008162642109757, 7440676439428237992864596387460092947449968530635365999432104198675297081825315672568959667296286389774687367936168132053293001589687795737604457160906082, 2264157050840270501520646271743213633490605461967539030408028006097728678459599299655371587125945029431528702214373899493252891890106222569122603386717360, 6089828885562252420652081197249651438359320954630388805129416420415135298321118452771481678140904854945253504361325478946359729157231808943846058944117026, 10539688120079451218718476929576210805778407047878263373562960368159158621424931104363627052374700437454925765616146962059684388174993415278124860987310938, 6303692164422236243124789748609418445914012315334563733630138248326249660310698584154622748275297380026916444293448955157206727703202478794453250926439643, 881942845076614931271891025655927553295291244201690295230440723375006916146507322259936249039275621554840488955637696630030022348109669072833863866985225, 10106348190249831893088197931090851286229747534150777530156601113972916238286905365616240501204440809598108220364456446320022747806334510176621958436096123, 8324531392881516178541244041903222514911964835924579628962940318936570586739198442236357026438613345385230182029810965182157993322744038688573053225547374, 5078708553426349749719952343873018594648548601008242439539543130067536764970709366523519348572603124221309659983256536103306454063139670063244331611755453, 8542547993117228744822361667182819410791296436924016725757178153507707272004493213120780743910507865839367749205817741703451968423781285521621014600059589, 3073352723766074586873446203285051955281142348730058300259816322651361605792426446390729367386148254808552616968786890277451301146248756651016086606742804, 5269945451683706496607356863109615383647000556701922770404180133092195426319754674753614204346587769298246334991876508268642550219392732660290378353338400, 6262348731181694593163187372863680743743096474259867989757989072530511417286900866334036812204673457159090130621478933266270029789176903023636735673595513, 3297899863181037954379261853482229450757449782777910450819629975965660022355584717412057615899333569245281976118829898854119850433763380827003244277020101, 7487260566995972228255217362172107520309457024141075543923988636564806307827017535285595701845830793533604534902349660541692391232785351590333159515799384, 10324279404125558600858330541468243667961239247663241031255287540601841176203292036413076990028875224629890818418992943759206077129550049357885152924273782, 8044925106089251438446731137002808317322635126054485149617494154471416674741758172633019611642437845768869330746423337854351186668227486117398013073824286, 4234270952814400783009242730655483882561531800274439758860142245952005010632014464198770218689605527760730047723966950012227395838571254801244673898812828, 638896609043108497262778277770178050665854883307447937008504779907661322405672174519391657570064336725509768185637608044022219246206471015980252602095129, 5180216795602211214280366461349507739255238657924206736673167715462995927060334503420979145327254053283011116720223275075476559911219732336496503542596869, 4889582376915206124736222022750168286228699065224704085027955184917144323557844593386817223260498520607466742269645929630472738644444652704289510157100913, 5012604326308554636339480431591200785633930724891396744558818436357664982175033998281443810436271724799610836412819040278374041390604150781759163613994682, 3219038638665180576932584279254771209098300305384572525709292133614238552451580810601286362213655499134538083785424726484119059950676285763438331520089227, 6419694420004223063062285264931096360778228156157853232796125041025067958687740255716444718822744614217377927689465894996156144384079594697465808095114901, 9910546009146267464166501179537825349776178695164070160517872596078275117785713000045215455672195660329319962408970209137481672915542900445933477806115760, 1420603945244588398788478464408905133932325733716125030735921688979482121297328679317495694245547716568441401137633433150951713462958551532394178628021900, 6208847506587273852328049116772424002595270959861992270025537759079430511161476024600259347318966551584005222005704567718008394909230998308545154993159673, 10385926333158107236552504228168776101396372491461292301486697050842973861408756486936932908479675556344542947425765714101814836237112561730341100901890350]
d = int(sqrt(512 << 1))

var('r0 r1 s0 s1')
eq = r0*R[0]*Q[1] + s0*S[0]*Q[1] - r1*R[1]*Q[0] - s1*S[1]*Q[0] + Q[0]*C[1] - Q[1]*C[0]
bounds = {v:2**d for v in [r0, r1, s0, s1]}
sol = solve_linear_mod([(eq==0, p)], bounds)
r0, r1, s0, s1 = sol.values()

m = (C[0] - r0 * R[0] - s0 * S[0]) * pow(Q[0], -1, p) % p
print(bytes.fromhex(f'{m:02x}'))

# CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}


Ahoo

(No source provided.)

$ nc 00.cr.yp.toc.tf 17371
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Welcome to Ahoo task! Given integer n, find the smallest positive   ┃
┃ integer c such that n * c has the minimum number of 1 bits in its   ┃
┃ binary representation. Completing all steps will reveal the flag :) ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ Please send the number of 1 bits in n * c and the integer c for
┃ n = 3823, separated by comma:

Had to pass several rounds of this.

Check:

https://arxiv.org/pdf/2002.02731

https://github.com/FinnLidbetter/sturdy-numbers


Vantuk

To solve a (using A):

assert A == a + Rational((5 * a - 4*a)/(a ** 2 + (4*a)**2))
assert An * (a ** 2 + (4*a)**2) == Ad * a * (a ** 2 + (4*a)**2) + Ad*(5 * a - 4*a)

To solve m1 and m2 (using U and V):

from Crypto.Util.number import *

A = 6080057478320734754578252336954411086329731226445881868123716230995225973869803901199434606333357820515656618869146654158788168766842914410452961599054518002813068771365518772891986864276289860125347726759503163130747954047189098354503529975642910040243893426023284760560550058749486622149336255123273699589/10166660077500992696786674322778747305573988490459101951030888617339232488971703619809763229396514541455656973227690713112602531083990085142454453827397614
U = 3225614773582213369706292127090052479554140270383744354251548034114969532022146352828696162628127070196943244336606099417210627640399143341122777407316956319347428454301338989662689983156270502206905873768685192940264891098471650041034871787036353839986435/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
V = 1971582892158351181843851788527088806814104010680626247728311504906886858748378948163011806974145871263749452213375101951129675358232283650086419295655854343862361076089682606804214329522917382524296561295274823374483828323983651110722084223144007926678084087/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609

An = A.numerator()
Ad = A.denominator()
Un = U.numerator()
Ud = U.denominator()
Vn = V.numerator()
Vd = V.denominator()

var('a')
f = Ad * a * (a ** 2 + (4*a)**2) + Ad*(5 * a - 4*a) - An * (a ** 2 + (4*a)**2) 
for a, _ in f.roots():
    if a.is_integer():
        break


R.<x, y> = ZZ[]
f = Ud*x*(x ** 2 + y ** 2) + Ud*(a * x - y) - Un*(x ** 2 + y ** 2)
g = Vd*y*(x ** 2 + y ** 2) - Vd*(x + a * y) - Vn*(x ** 2 + y ** 2)
for m1, _ in f.resultant(g, y).roots():
    if m1.is_integer() and m1 != 0:
        break
for m2, _ in f.resultant(g, x).roots():
    if m2.is_integer() and m2 != 0:
        break

print(long_to_bytes(int(m1)).decode() + long_to_bytes(int(m2)).decode())


# .:: CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?} ::.


Ally

Credit @ctfguy

https://www.imo-official.org/problems/IMO2012SL.pdf

Check N4^

from pwn import remote
from Crypto.Util.number import getPrime

def get_special_prime(nbit):
    while True:
        p = getPrime(nbit)
        if p%4 == 1:
            return p

io = remote('01.cr.yp.toc.tf', '13777')
for _ in range(20):
    io.recvuntil(b'your ')
    nbit = int(io.recvuntil(b'-').decode()[:-1])
    p = get_special_prime(nbit)
    io.sendline(str(p).encode())
    k = (p-1)//4
    x, y = 2*k+1, k
    io.sendline(f"{x},{y}".encode())
io.interactive()

# CCTF{Di0phaNtinE_eQuaT1on_iZ_4n_equ4tion_wiTh_int3ger_solu7Ions_0nly!}


Soufia

(No source provided.)

Credit @ctfguy

We are given a function $f: \mathbb{Z} \to \mathbb{Z} $ and the functional equation: \(f(t \cdot x) + t \cdot f(y) = f(f(x + y))\) for all integers $ x $ and $ y $, where $ t $ is a constant integer. We are provided with $ f(0) $ and some $ f(a) $, and we are asked to determine $ f(b) $.

Let’s solve this step by step:

  1. Interchanging $ x $ and $ y $: By swapping $ x $ and $ y $, we obtain: \(f(t \cdot y) + t \cdot f(x) = f(f(x + y))\)

  2. Equating the two equations: From the original and swapped equations, we have: \(f(t \cdot x) + t \cdot f(y) = f(t \cdot y) + t \cdot f(x)\) This simplifies to: \(f(t \cdot x) - t \cdot f(x) = f(t \cdot y) - t \cdot f(y)\) Let this be some constant $ c $: \(f(t \cdot x) - t \cdot f(x) = c\)

  3. Expressing $ f(t \cdot x) $ in terms of $ f(x) $: Rearrange the above equation: \(f(t \cdot x) = t \cdot f(x) + c\)

  4. Substituting back into the original equation: Replace $ f(t \cdot x) $ in the original equation: \(f(f(x + y)) = t \cdot f(x) + t \cdot f(y) + c\) By setting $ y = 0 $, we get: \(f(f(x)) = t \cdot f(x) + t \cdot f(0) + c\)

  5. Substituting $ f(f(x)) $ into the equation: Replace $ f(f(x)) $ back into the equation: \(t \cdot f(x + y) + t \cdot f(0) + c = t \cdot f(x) + t \cdot f(y) + c\) Simplify this to: \(f(x + y) = f(x) + f(y)\)

  6. Conclusion: Since $ f $ satisfies the Cauchy functional equation $ f(x + y) = f(x) + f(y) $ over the integers, $ f $ must be a linear function. Therefore, $ f(x) $ is of the form: \(f(x) = kx + c\) where $ k $ and $ c $ are an integer constant.

Thus, $ f $ is a linear function in $ \mathbb{Z} $.

from pwn import *

conn = remote('03.cr.yp.toc.tf', 13377)

def read_val(conn):
    for _ in range(4):
        print(conn.recvline().decode())

    s=conn.recvline().decode()
    print(s)
    y1 = int(s.split('=')[1].split(',')[0].strip())
    s=conn.recvline().decode()
    print(s)
    x2 = int(s.split('(')[1].split(')')[0])
    y2 = int(s.split('=')[1].split('┃')[0].strip())
    conn.recvline().decode()
    return int(0),int(x2),int(y1),int(y2)

def cal(val):
    a = (y2 - y1) // (x2 - x1)
    b = y1 - a * x1
    return (a * val) + b

x1,x2,y1,y2 = read_val(conn)
print(x1,x2,y1,y2)

s=conn.recvline().decode()
val = int(s.split('(')[1].split(')')[0])
ans=cal(val)
conn.sendline(str(ans).encode())
print(conn.recvline().decode())
def conti():
        s=conn.recvline().decode()
        print(s)
        val = int(s.split('(')[1].split(')')[0])
        ans=cal(val)
        conn.sendline(str(ans).encode())
        print(conn.recvline())

while True:
    conti()

[+] Opening connection to 03.cr.yp.toc.tf on port 13377: Done
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓

┃ .::   Soufia is a random oracle, your mission is to break it   ::. ┃

┃ We know that f: Z → Z and for all integers `x' and `y' we have:    ┃

┃     f(t * x) + t * f(y) = f(f(x + y)) for constant integer `t'.    ┃

┃ Also, f(0) = 209907020941535864741588746126965728575,              ┃

┃ and   f(91) = 1369168415328908069957513174528303837593             ┃

0 91 209907020941535864741588746126965728575 1369168415328908069957513174528303837593
┃ Good job, try the next step 2

┃ Please send the f(45):

b'\xe2\x94\x83 Good job, try the next step 3\n'
┃ Please send the f(32):

b'\xe2\x94\x83 Good job, try the next step 4\n'
┃ Please send the f(155):

b'\xe2\x94\x83 Good job, try the next step 5\n'
┃ Please send the f(356):

...

b'\xe2\x94\x83 Good job, try the next step 18\n'
┃ Please send the f(3910397):

b'\xe2\x94\x83 Good job, try the next step 19\n'
┃ Please send the f(2008442):

b'\xe2\x94\x83 Good job, try the next step 20\n'
┃ Please send the f(14329881):

b"\xe2\x94\x83 Congratz! You got the flag: b'CCTF{A_funCti0nal_3qu4tiOn_iZ_4_7yPe_oF_EquAtioN_tHaT_inv0lVe5_an_unKnOwn_funCt!on_r4tH3r_thAn_juS7_vArIabl3s!!}'\n"


Melek

enc = ...
e, p, pts = enc
F.<x> = PolynomialRing(GF(p))
flag = GF(p)(F.lagrange_polynomial(pts)(0)).nth_root(e)
print(bytes.fromhex(f'{int(flag):02x}'))

# CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}


Tesvir

def solve_subset_mod(arr, target, m):
    M = (identity_matrix(QQ, len(arr)+1)
         .augment(vector(arr + [-target]))
         .stack(vector([0 for _ in range(len(arr)+1)] + [m]))
    )

    for row in M.LLL():
        for row in (row, -row):
            sol = [i for i in row][:-2]
            if not all([i in (0, 1) for i in sol]):
                continue
            subset = [xx for xx, k in zip(arr, sol) if k]
            if sum(subset) % m == target:
                return sol

pubkey  = [92886066988388680173329582741273638432560905105902914844, 210751255343870357476757616218088120348848008067778344395, 74425909117669424902415608182276534435650370104873725226, 99181044682023732918695417999410594327236962612004062203, 184660845741344564288628118584866122028435601898518289311, 86293719592435824002495406220960151634808851208991382274, 220299683035630760097249864519724170956397691396674502351, 218079912870288780369679822368500969128910276003151222237, 14778352954258397714469938718275182936354922505384292383, 132130835649873192456001750484927359136237453044816907309, 25137623946868522616211722412394033705360632773617668353, 79901378033903357591915996829748292103112792449008643158, 57127051781577974272533361891913780075063000327051256185, 139480489738918831641105138243203041849604902804230325307, 6636221692280612206143039499477440633937028618222805297, 3772467192534577746336251743661505830547482255151794293, 12837754032587248352593907834250831316657535088858254316, 55294249969720105731143033962876859344291619766399258586, 143240945985012003565090193408824643640779930841340941384, 207298521840013369619959675764264366982562750013000422761, 19802061697642727591519306605507839521117935001927582613, 44527192516622631241657701198320138966998880114399361795, 70009063969035941644329825318467700094581525801204727181, 142703058408732671528984569801750559471281159651241652062, 172304085921330629492232337636466212102117319007604950025, 155475843345826385265987350725039300934780724029883949772, 169347599331405990514138585112678993084330188820253643457, 215416121704488916458382565818438348592001566447832598904, 188187731496431295706540560463195397867635095489841015153, 193876498460423248024056843990730327032814452611339372095, 110910914198523905354564616742390233111344563838133902268, 63827772029857861463577163755389830442651373015537598853, 201568856761103641300623283313375294858797054395206451738, 111796178976077921895334684539179530199231221192025576010, 132026503336520784756207274656596057456804846250284032339, 84285587542526127248440670614024679598468422343813253605, 159428417414783869527317183833025274975479739383901448874, 64428339570057766343470883789790396681811345808506430155, 17773178194543385480117432315047762917045147297455059068, 89512728697279216167516727754431756792239260101851927048, 190427317516825752974680525260842202533545330049265484685, 157295297961778042328619944993793385674269977225614543409, 4974170892150975824988854099057751873407321899766994340, 76151972747505832903312296911458066375836111785170954818, 12780621873862922185963594441840408184697766338606725088, 215891915752015869692717275983217322389954147748038149913, 84672037040784935027771519744002727929035411856418295454, 173377172838515603000763109043635713007444376906312785659, 78825027684341059289379270568982587949492842296580685210, 196319411406577160369249468485354959923499881172752370432, 149632537749145022633698878910422597383394761669508775150, 61215274442358408619312704383732009988429752954976434510, 121617939993268547670556056131391352859594688618055273649, 92683023247453538925416294521734179142466406393402165284, 179081918128905986721209486399492233572685281618904277134, 128127945519288006079855900928579345964821914461244666859, 16867099283533376487721035923318497964272934855546093439, 154997822809931133447394923168284413679035824785745194730, 173682328462179058005003161191680769654245300801521009879, 130155296795876399873497236725802378282692937340062237935, 6671586303725645410980753139195927682320190581348797818, 152943065825990505253224485604590561843118102831476724085, 76097330619185109304052467189304594887923532251137153504, 185135141194334724407844282883457326900162249009549345831, 10921483287230916182817512596921390357752886208282706876, 151271927039684184070498738116172072543518713480677091079, 136298030618749815703864675278527025088371447385571482978, 4758776794002838133449795605623779838661247306079090347, 19981114149609902678102199302508388417345988817824030366, 73938677992611844289158171248381726517745556187533617067, 154379344389348822626282095279797153064835052505876799368, 213360480891633535236181458572407095838836152782860588104, 198510199654805189509342596145689894869725018759903041507, 14267132365366134640075375788531621241572826565872424420, 125322641872109533742616867834123368413937890142250166210, 27761695413361618125181147472312882304612603261326567738, 176074098184367588496084722561712203577297987249156695996, 184825512648696203391868022338025767151276944108604105240, 76445117428817751907469654995811477620910303139855603430, 82665582153218489938826943118869996114191197883710823609, 146938316278530866657441207271230294849424101841476702684, 175735365800930965503156619292636366172726729000960012747, 76108412191983352914624831771577340649664462133681354257, 51216505200491353565628514314075841932869368671909611422, 204239406328039235742654863605657881024731770195373503166, 35077608369166363077290419165539308358044372399596051949, 141346950768818454305723443861759686267961194829785415155, 172150098196192354246034454655216693215452009432898901427, 82990067238658606054849825844886372090364773033126485587, 112038315092606359027221487184783803870421704581266936708, 58914659964881731037335471016191730563863425144352336943, 128457823796249561970005313037687944811941419913016496383, 213337871687450072917189488472078380744945853754387250512, 191892726995974949469114178871749804387259634590458908936, 176112380139134647655398805139300913670784775509195354445, 144740992869587974310090799803527129516554701599543463160, 111678206994513803125019555945498901679134121690878426828, 212378272583651446176097053495838205426261001439753481779, 30270421099323796173018087600030956325784109844975963318, 24667784976110977811287463198349391182061026177610928267, 58648685934430390399131245710068712256688250896733427433, 226288351225600375693429144741635573530336955157491657406, 2234225503811661632319718142798855751866036485696580852, 121797356235039478737766390441090317882711507703565373226, 101297006853275402861966500913834813565543444865413634087, 162579081001936368615348051777628179506904525245133047164, 25157488109407946030153114849594555538316839672959711563, 88061984254829379097942516994529815597150987399072364336, 42688530758895174674193186730994655264010420201719243433, 4460090661692805202749850983805143841415378613652836846, 30088825985014846600387007682131860206839260053034513849, 200054261203129307816182870092417959615219353804985049450, 140849799897717905135153922792539839975896769827334038275, 98760545087771244563146940499391962327892043011670296574, 25180075852456461545668509099653490611752856235335415515, 157279073723626343268408966659119242174681449600046327491, 211533443731232207958382797927578368253470063323385415305, 194524863955971259753051926427267579197016195487315353155, 83751248535513145355660506770897482801030224059963389408, 115138349873074658192267411096122845105999530350763854655, 215600522608166725448707314656579650654515052268673308760, 10796034267879362998642448011756079795116267404224800855, 111832068852177640954078305890771947542980712902669315475, 200469150388653842509392959061011176435466551051326498668, 30726612920161727945717775737198729041541528543188078985, 47239465143611863240261597547409077261966220932690083608, 172702523884923029857632413645581266015574385393550030383, 160627476423178758050783866311020106650977166828135718677, 128551461965426470262450322709691684846516421067158247593, 149070893501618995889804678789784488223110157086998320190, 195544453239680309080864718376343768660793419344309015371, 77811783271576363509563966728389456349963507382460515159, 174278317100602890982289959796479144491641180003422318402, 73378410370770578287641255812076589713277634648053702393, 141743373303620859387809446917135848276524237197935139251, 107180666443942227975559795572883017760896436280408642836, 204466619320963270815953280672596862351439649087459080330, 54607085224440389336692259961948432872409040643712187196, 90892438801687444302363910922001469380485547602072056312, 116495323168693640880821115186026787669589735848974550271, 150401470283271988559117977784854104521296931907607110486, 154090517125971562516821679404817371275277406532781405647, 104678342752350974596101104366129755083070849881860226748, 157978012412333596540548315887518551041118501217715507693, 163303626174887158945343733366789836669913574237379259572, 181001953193184678814047746174416210735032292122737633102, 28520747201490566067980511495227121600982304748050536315, 202299150875669157121378795139833033891742976498092748326, 970899112734507435107978511253698562255021879789329622, 146598329156514558782950920101145863079889367928807975977, 161170854382197314019269906577394809052106378415918331111, 59062428764150593381983742288693555245406391510971163517, 76915433679990371556167855027708867665365400330733169618, 89501651017657171486735552504919601126514100477053545598, 155730958643627207880319610446663976356182855717274760915, 153319504596278295124327612654967413427190499811068175141, 55143199482129353190020980489571171227799463580932543507, 65867578091352179883803350861852268522863534472063121536, 185253942450370609764295976829306672581940464194975155370, 45998515564234600522974603054023511905075650998614365022, 202037532932391272684290723543081742411941903511422568693, 193437603469571773588721936014856408564274364378112176998, 40966814823621126092043598001247946528303483900490631243, 96180297695543903574648581153841041196995524933892692619, 7434236946247395721737460702125068355596232961041228531, 184321353327002489735745646530281708427284036005568776658, 140177181342986706305442328349507660746632700762773335854, 62185321216695795974582214400857301435242625860427058504, 76430389183686943120515253756245781025593330606869771215, 78619517512809385276713151495590149773001915050796364065, 79421522371486140966131803689265908515929863724624939864, 22129537950071912479413632578731336002900774566274025350, 197085073703705733810640962347618181728732561497159780282, 181724715254608855641693163729986494116649983589787609407, 124597957745948567633299678917630875794686726927368990429, 27273213841358296776578768184430928671018080941174807840, 152776522190630131246760748430764619655533175607985589836, 48681268809666830266159835476955141416750705899024875974, 89317244917173433349320258645687517717239384663894566278, 201257702236516361405257981510601612114484277702528603943, 87519410092330942709078977446738925665582243816920367744, 177787387494070159450445481317677026153613266023935751281, 24643205402954723090911892051677522488215459066647382714, 56590062223369038528065649254743241674141446454079839579, 179396400905232822865797012959623450133279154279097379051, 30025313395744011254406844462499704950426511512721337841, 83276838850321885112545153165158569714460607766826121135, 68646151543586256303371147554134648353111280212178713752, 87495786295097875957094843643092630530679785357906500378, 222465857206064556670796535989384593676021996740717427241, 110523306528201080754549704134151152305839064772192522439, 26464048540106421248631062043107233895602381285227483920, 145627987132012795205161372829205758041070489765824489859, 193297733586259333458497049150053222412825014105379541387, 26111736920859807974906629858040408870103481081762161325, 55771701249405168670677160717676511083556774856113587797, 189736239093660724751567045325664782250505266726265886301, 161804560602042832539413084827420388198122805811609462668, 203009995021523304957205919345868213530963925564563615473, 90774798965018540890715656649222210633732452506467954902, 225895202989665665828020049279241974570875711586953870572, 218526549874566716275818926298716226779897994684061293418, 131530479475390722696235276845265596381662910299437131301, 72620232900742232429463502446535378811959678254536979604, 37546163510027376473170898762960473894255918124633338415, 143001879280256363624803066346210337300340423105921577120, 165329409306715276877210964642484011103648994170410031402, 4814907793328147487310168483966089518302106121666337453, 51312524070257917838368408186468441732503299101638317043, 86662571838604232113504553386409229105778273252765707836, 62213997296769879553198182504582088960032151319109241629, 200406934649320768037667962927866428421277977046695072270, 92470224199301497961555930909174852382352507364774469356, 21594911171913776918052060504197855262578419645616335604, 29011150339088209488103721928958817626907010842053899941, 8372898414227573449442990910059289890284123168261547531, 169961592178907939509522133503409794844895818074560168428, 173004823566201448576476592934121715356651376842721997619, 169157072568524836382074106405055305528383450896499626160, 186490359160732656419875466468508581711232527708974028426, 12660075658562618970962317520287968826117547712067755493, 86613911921221949822767544058543773067024167756340760277, 25878398193015129175197412426814597205797037745809900508]
enc = [187335580574061707931829069116893046450217737977325200745, 23044036808650474215359961752968190941949563626346145378, 15472607588253013011000486526821636805918664553516618358, 220564948069930322910342336229099484559121538170035160014, 74457707396243578866974467699987135325106221370053143511, 191844788154252149258813565888783499484598821383178275043, 59281299146214117805262571323958482102338248792701470905, 58087015188935841816071445240786563506121906740551194689, 130642627083773736940245456608059246927502638073319678670, 225120950466145061336433324767380851216550581530569663094, 115988089900656782972089910677319239346851295885744890049, 82861550277425149901583976607081827058011437360125240204, 157911333117268625551061805625122605155252264343038082111, 70418826087219797756008213894640219758929295365347469130, 149526656617309347299553804390924844369186967346096045202, 196748731334848074105092056876949001467041097522100070418, 209630245143058356288710962132847621537804601934377712911, 214956094413732365297703489096292627646807106134017187223]
p, h = 223, 24
q = p**h - 1
pubkeys = pubkey[:h] + pubkey[-h:]

flag = ""
for e in enc:
    sol = solve_subset_mod(pubkeys, e, q)
    flag += "".join(str(_) for _ in sol[:h])
print(bytes.fromhex(f'{int(flag, 2):02x}'))

# CCTF{9j_h0W_dO_yUo_5oLvE_tH!s_m1X3D_5eMi_H4rD_T4Sk!!!?}


Solmaz

px, py = (1338, 9218578132576071095213927906233283616907115389852794510465118810355739314264)
qx, qy = (3454561753909947353764378180794889923919743476068813953002808647958908878895, 17267599534808803050751150297274989016063324917454246976792837120400888025519)
A = qx*(py^2-px^3) - px*(qy^2-qx^3)
p = 30126567747372029007183424263223733382328264316268541293679065617875255137317
assert A%p == 0

c = (py^2 - px^3) * pow(px, -1, p) % p
E = EllipticCurve(GF(p), [c, 0])
P = E(px, py)
Q = E(qx, qy)
m = Q.log(P)
print(bytes.fromhex(f'{m:02x}'))
# 3cC_d1ViSibil!7Y


Rehawk

https://gitlab.inria.fr/capsule/code-for-module-lip/-/blob/main/attack/attack_Hawk_totally_real.sage


Chochol

assert 0 == (Gpx**3 + a*Gpx - Gpy**2) % p
assert 0 == (Hpx**3 + a*Hpx - Hpy**2) % p

# eliminate a
assert 0 == (Gpx**3*Hpx - Hpx**3*Gpx + Hpy**2*Gpx - Gpy**2*Hpx) % p



Gpx, Gpy = (2024, 77522466419731346352388161327659294096)
Hpx, Hpy = (187001239996895215821259450553198409012, 158495938026527642884038157170741730943)
Gqx, Gqy = (2024, 92609909821520263487623088269239797003)
Hqx, Hqy = (191534442430060308634251661645421139195, 102273233384427938890774177710170123915)
c  = 15084463560924811262750235394027264639346464192638172940901706702947534963652

# solve p
A = Gpx**3*Hpx - Hpx**3*Gpx + Hpy**2*Gpx - Gpy**2*Hpx
p = 243678574849421895808521345944938402807
assert A % p == 0

# solve q
B = Gqx**3*Hqx - Hqx**3*Gqx + Hqy**2*Gqx - Gqy**2*Hqx
q = 278451262698064898668334196027031252819
assert B % q == 0

# solve a
a = (Gpy^2 - Gpx^3) * pow(Gpx, -1, p) % p

Ep = EllipticCurve(GF(p), [a, 0])
Eq = EllipticCurve(GF(q), [a, 0])
Gp = Ep(Gpx, Gpy)
Gq = Eq(Gqx, Gqy)
Hp = Ep(Hpx, Hpy)
Hq = Eq(Hqx, Hqy)

print(factor(Ep.order()))
print(factor(Eq.order()))
s = Hp.log(Gp)
print(f'{s = }')
assert Hp == s*Gp
print(Hq == s*Gq)



2^3 * 439 * 2609 * 462181063 * 228465631117 * 251857991531
2^2 * 5 * 11 * 233 * 331 * 503 * 101385043 * 321810878759529563693
s = 50295274560999838770579032062844522666
False

Sooo we’ve solved p, q, a, and looking at the order factorisations you can see Ep is smooth enough to solve the discrete log.

However, the s we get doesn’t solve the other log, Hq == s*Gq

What’s going on?

We can try add + k*Gp.order(), turns out we find k=2 works.

Then another problem, gcd(ss, p-1) != 1 and gcd(ss, q-1) != 1 so we solve like this chall

...
for k in range(1, 99999):
    ss = s + k*Gp.order()
    assert Hp == ss*Gp
    if Hq == ss*Gq:
        print(f'{k = }')
        break

print(gcd(ss, p-1), gcd(ss, q-1))
p_roots = mod(c, p).nth_root(ss, all=True)
q_roots = mod(c, q).nth_root(ss, all=True)
for pp in p_roots:
    for qq in q_roots:
        flag = crt([Integer(pp), Integer(qq)], [p,q])
        try:
            print(bytes.fromhex(f'{int(flag):02x}').decode())
        except:
            pass

# CCTF{m1X!n9__3cC__&_R54_!}


O7R

credit @alvin09041

I uploaded the images with the challenge pdf

from collections import defaultdict
from Crypto.Util.number import long_to_bytes
import numpy as np
from PIL import Image

num_map = {
    0: [0,1,2,4,5,6],
    1: [2,5],
    2: [0,2,3,4,6],
    3: [0,2,3,5,6],
    4: [1,2,3,5],
    5: [0,1,3,5,6],
    6: [0,1,3,4,5,6],
    7: [0,2,5],
    8: [0,1,2,3,4,5,6],
    9: [0,1,2,3,5,6],
}

assert len(set([tuple(d) for d in num_map.values()])) == 10

possible_nums = defaultdict(list)
for k,v in num_map.items():
    if k not in possible_nums[tuple(v)]:
        possible_nums[tuple(v)].append(k)
    for i in v:
        new = v[:]
        new.remove(i)
        if k in possible_nums[tuple(sorted(new))]:
            continue
        possible_nums[tuple(sorted(new))].append(k)

def parse_image(im_p, n_rows=4, n_digits=40):
    height = im_p.shape[0]
    width = im_p.shape[1]
    n_digits = 40
    #n_rows = 4
    numblock_width = (width+3.5)/40
    numblock_width
    num_left_offset = 2
    num_right_offset = 29
    numblock_height = (height+37)/n_rows
    numblock_width, numblock_height
    num_top_offset = 2
    num_middle_offset = 29
    num_bottom_offset = 56
    
    
    p_nums = []
    for i in range(n_rows):
        for j in range(n_digits):
            index0 = im_p[round(i*numblock_height) + num_top_offset, round(j*numblock_width) + round(numblock_width/2)][0] == 0
            index1 = im_p[round(i*numblock_height) + (num_top_offset + num_middle_offset)//2, round(j*numblock_width) + num_left_offset][0] == 0
            index2 = im_p[round(i*numblock_height) + (num_top_offset + num_middle_offset)//2, round(j*numblock_width) + num_right_offset][0] == 0
            index3 = im_p[round(i*numblock_height) + num_middle_offset, round(j*numblock_width) + round(numblock_width/2)][0] == 0
            index4 = im_p[round(i*numblock_height) + (num_middle_offset + num_bottom_offset)//2, round(j*numblock_width) + num_left_offset][0] == 0
            index5 = im_p[round(i*numblock_height) + (num_middle_offset + num_bottom_offset)//2, round(j*numblock_width) + num_right_offset][0] == 0
            index6 = im_p[round(i*numblock_height) + num_bottom_offset, round(j*numblock_width) + round(numblock_width/2)][0] == 0
            res = [index0, index1, index2, index3, index4, index5, index6]
            res = [idx for idx, boolean in enumerate(res) if boolean]
            p_nums.append(res)
    #p_nums = p_nums[:-6]
    #len(p_nums)
    return p_nums

p_nums = parse_image(np.array(Image.open('p.png')))
q_nums = parse_image(np.array(Image.open('q.png')))
n_nums = parse_image(np.array(Image.open('n.png')), n_rows=8)
n_sq_1_nums = parse_image(np.array(Image.open('n_sq_1.png')), n_rows=9)
n_sq_2_nums = parse_image(np.array(Image.open('n_sq_2.png')), n_rows=7)
c_nums = parse_image(np.array(Image.open('c.png')), n_rows=8)

p_nums = p_nums[:-6]
q_nums = q_nums[:-6]
c_nums = c_nums[:-13]
n_nums = n_nums[:-12]
n_sq_nums = n_sq_1_nums + n_sq_2_nums[:-24]

print('calculating n...')
queue = ['273']
while queue:
    n = queue.pop()
    if len(n) == 40*8-12:
        n = int(n)
        print('n = ', n)
        break
    n_idx = len(n)
    #print('n_idx', n_idx)
    n_cands = possible_nums[tuple(n_nums[-(n_idx+1)])]
    if len(n_cands) == 1:
        n = str(n_cands[0]) + n
        queue.append(n)
        continue
    nsq = (int(n) ** 2) % (10 ** n_idx)
    nsq_cands = possible_nums[tuple(n_sq_nums[-(n_idx+1)])]

    for n_digit in n_cands:
        for n_sq_digit in nsq_cands:
            n_test = str(n_digit) + n
            if (int(n_test) ** 2) % (10 ** (n_idx+1)) == nsq + n_sq_digit * 10 ** n_idx:
                queue.append(n_test)


#p = '7'
#q = '9'
queue = [('7', '9')]
while queue:
    p,q = queue.pop()
    if len(p) == 154:
        p,q = int(p), int(q)
        print('p,q are', p, q)
        break
    p_idx = len(p)
    p_cands = possible_nums[tuple(p_nums[-(p_idx+1)])]
    q_cands = possible_nums[tuple(q_nums[-(p_idx+1)])]
    if len(p_cands) == 1 and len(q_cands) == 1:
        p = str(p_cands[0]) + p
        q = str(q_cands[0]) + q
        queue.append((p, q))
        continue
    n_temp = (int(p) * int(q)) % (10 ** p_idx)
    n_required = n % (10 ** (p_idx+1))
    for p_digit in p_cands:
        for q_digit in q_cands:
            p_test = str(p_digit) + p
            q_test = str(q_digit) + q
            n_test = int(p_test) * int(q_test)
            if n_test % (10 ** (p_idx+1)) == n_required:
                queue.append((p_test, q_test))

assert n % p == 0 and n % q == 0
num_map_inv = {tuple(v):k for k,v in num_map.items()}
c = int(''.join([str(num_map_inv[tuple(cc)]) for cc in c_nums]))
e = 65537
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))

# CCTF{5eVEn_S39Men7_RSA_w!Th_k3Y_rEc0v3Ry!!!}