CyberSci Regionals 2024: parts

We’ve intercepted this high profile message. Can you find anything of value?

We’re given an RSA encryption script and its output:

encrypt.py

from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Util.Padding import pad
from secret import MESSAGE

p = getPrime(512)
q = getPrime(512)

n = p * q
e = 0x10001

pt = pad(MESSAGE, 4)
ct = []

for i in range(0, len(pt), 4):
    pt_block = bytes_to_long(pt[i:i+4])
    ct_block = pow(pt_block, e, n)
    ct.append(ct_block)

print(f'{n = }')
print(f'{e = }')
print(f'{ct = }')

output.txt

n = 129188764973868707864770736177471107876487158035886844731538044191358383480443858654931305408247655967312211127935963074884444629300271383546207583975928023710403014302957303471768382855545942309377643623957507465446856649361655072910341876465023123798730372677831976338830883873611866793894401881589343775251
e = 65537
ct = [57161731618375166377653170640412672416455711429270252268625292976102447485222717066509315322132210512622383461153075582234230107558301863257074089930999420793664828666191937894660967895253338617132321975095006204511202985363536862860319490224450319648640020335562846250523110928763166211973461459200210561508, 52282904109128160619921955698653444296100584871011695670558893340353242273303615305558046930284711705772811883927806987230548090426212685545501626682120263411396698640674231099272682511315628659487952331088925271001446356174740575584739601303002116872289753012601355938723616277639340708793916929275992757858, 57152148643975820547504691259106856248019230519708779953130749180221465730549934621176299146372203129638571957417039831661819658127768565853265431736261278885958127055922051675341904501780282260159129548433179919905651991538949665798433184785725794683459717217219784984312186547771696187855679362823616903673, 31014162528093200054056556872703736797712001870832747095050879917657612065172713349221727348827598690495554777988292249014543701980165071784254559910706950003899825905183433123543757455145344286407661629757366425955490539700536490999279048287656612880426994375125865174811897553732817009073366041261606567050, 82726003862724851464926784028707038924678810589538432328795870605251646978561157469292392437739083650680691359369050494191502598402940768564500290097740819966804440095261680710118478791849052928044038256175292521965519890958452266651166679774122765735504427492930106745013676398555149545138764484568260824030, 26126660140204468052761415806526648085526958491564293015908869962278605874517304308048507622791422188315753639697716379462123951203471632063170508684286422370931373114275593928465835280698493901852970451852852984400219717830394268848260203245082464202290824276073192822263527456400374645650523863826036313812, 76920017006711763257468183879405052561057689723898907023946619927118526321345855586779062840468483427501794634238692370009451886703429995414822291477105415851280401011710344483647376264018328770503608819883586750211584023246468342162143248301236849064282569144151423498550698172028870834812948691717610460112, 114651902099337028611627032290900770889544779267978658206981903054346968371562940484416276098514739503122418084074448483210585445002770130952442209516595231242765850345533961657682330478159168114226136857026896051240014221239920081353356495114441584208902897256443482807273762633623584457683314292700436948106, 32697844382359021316850224297656127439339116969025362516339084269219626924813323501043296591487811104308844771832322301531716285827640613657904598912815399014084525407240678496757686522337013808410146656569764579003388801809751945117432011199208946911044605419029544008944908828369980868985921203042067815993, 31448462645057996158527806957738849029736681407788410660911114911302711972632254321195805062207482777577677087651286841830189511429142287786972389867897707294355791264404337028315904979515988154328453672970642697170726993297391568659537208562315286817508655997644575423749791152356744879018140135170195362041, 115977945039237589563940484573582993606130683465961834213938064357514265863776346385773404158908750666460827042128301951506348028592671626220139953439731266071572529793198961984170533390307285520522167847584801115888700629255508745861899300348691175585678955599469544521932565265398940768862209139366225584937, 7343555121716635726106826503305011525221792633393142407881430099132790107114705856977933483011320589407493309130322059044089580985449086368581038407559628658214140766474396006289098772140056460782296786508270827837494528420404019036471065647034450152772135637573635577192014704678089878639440604735404062678, 17458763615495247335917723168132312672922971837519731911561796300828027684348021047637750466188551886866388209109873695320266918480240820398268593963731356523697971223786362330553469784536003932046769769617799103246207413185468175486135985232163407997125329709038603706895210816476460872169153238450703381423, 22619086296137020630313416352090073562512863718970219664112884707141933466648471409542253426002920318800389794410917613618034900551618024356605460175614306359546024916775068960006016152176852644764168308673688942913715613729811195294989782220176908382454523791586741979439930849432673178216217220021022069099, 81105101436892464042334861747957148623647885080655533265317156314563725184619792168610157176312361502314445334718879431084319895874035503278076754542676100695058891420513283400050379433809413518090299690278936031769359990210987463612635791260992848870586281527481873778354611079935998341818848367638579407064, 50503971518111680039465543346013957554795314651319576508372668393455540131970868348799344277309943553606084778236092225028981668791057897217400146663173068118954962121270971225687188553025414954752153448607657750435279469206781480109686680017815593291694791916133655286976815110293925816118123527589508199952, 120742178782748495741413197644148039351982643239391267874861365587920396486992488955755730123702293718760443314606335489488521673888246183194551969142197637944821733918924196823341338183423777074999431931999963693321147722193275553262901239788451891202260077200759277950974159520168425731903678841189471583264, 32339084982484907469518429216441415747913124689444635480262096471945072305292617661457239269161490980178099492485044168461632528730358454458961123471301123223944945776935792919493240703649552710092797661077165468289689864389870054589301923064269030231431510273222982558420327308426491477388376506253531060218, 52401859514239389661316873358781204809934249684340730977205832257331743100550115050549420153308295480454123120419061264034725999705870982135814582198718506206779741635320349483410417249664322099521691359920080493485619370050030567302397792695547074729167737216356860793511182830643851657451254575027693829603, 32971454695482541388621766287922881015711296235424642454780477257130105922756854956440763688676509235619014807408084521296079572184846165923194127060978289587192322366720149389322936175221635584615605794834241680528924889201572714216354059663002362825550874270351168748949683176825275019317468844864026833920, 94548780254003859553683162104827360036818697951541474675186613317456891505725469071596693218727130391295843160377978042853509642840692106713852670250970319474382641425553042543730562890457721477070522100796160477343776717204258576666020896142031263494368800095251264156994384970067912441912932618767614411915, 60491611219114688852570799302042011487142079338082303011102416443011597481969369926518059200730429283106805788655430571195171337173049858052595106661134618586416511229655890502629793942581746519991159107376711169710749626252935091577596899334730184240674248972841327870369650902145900588315981806059229166172, 118657887982828964504228138052473613713536489470880421299847433061337608001851421164815195938743609279463926672441814259477516653229715996984413251798279094745309481126525017075459692595212578460567055020462303967549342652820211374756793326344637772529989363047555683589529866554193749689462726382226850714750]

This is textbook RSA, nothing too weird. But… a block size of 4 bytes? That’s not much. Assuming only printable characters are used, of which there are 96, that’s only $96^4 = 84934656$ possible block values. That’s well within what I can bruteforce on my laptop.

No smart tricks, just 4 for loops, calculate the block, encrypt it, check if it’s part of the ciphertext.

sct = set(ct)

for a in range(127,31,-1):
    for b in range(127,31,-1):
        for c in range(127,31,-1):
            for d in range(127,31,-1):
                pt_block = d
                pt_block = 256*pt_block + c
                pt_block = 256*pt_block + b
                pt_block = 256*pt_block + a
                ct_block = pow(pt_block, e, n)
                if ct_block in sct:
                    print(chr(d),chr(c),chr(b),chr(a), ct_block)

Then just match the script’s output which looks like this, plaintext and ciphertext, until we have everything:

s c i { 31448462645057996158527...very long number...2356744879018140135170195362041

Final reconstructed plaintext:

Let the President know there's cybersci{no_need_to_worry}. The election is under control

Home About Contact