Challenge

2026年もRSAと親しみましょう！

import math
import os
import random
import sys
from Crypto.Util.number import isPrime

sys.set_int_max_str_digits(20 << 26)

flag = os.environ.get("FLAG", "Alpaca{****** REDACTED ******}").encode()
m = int(flag.hex(), 16)

primes = [x for x in range(2026) if isPrime(x) and m % x != 0]
ps = random.choices(primes, k=2026)
n = math.prod(ps)
assert m < n

e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

Solution

Multi prime RSA with a “tiny-primes product”

Since primes are chosen with replacement, n is generally not squarefree:

$n=\prod p_i^{k_i}$

Euler’s totient for prime powers:

$φ(p^k) = p^{k-1}(p-1)$

So:

$φ(n)=\prod p_i^{k_i-1}(p_i-1)$

Then compute:

$d\equiv e^{-1} \pmod{\varphi(n)}$

and decrypt:

$m\equiv c^d \pmod{n}$

Final Script

sagemath has euler_phi

n = ZZ("3771033181350829263969576074431524897790249654166659626333690350859549513817343981885990499054739593171678912013538556571770554517866862929432402001311344182641933296967882577363994855942277696939929528638972399672632063694379166898343501542737619668785866527199995618662554403775664282306752403598710714884457362322677784383534780581685708326467529715142085821713412738610022402177496282248106476099261643696212137965188239604830158515605325885632207098277165666536783838567916738591656211053731455036993421922917409027025992853540879665106689371260845780753850909903932411851040311800795262672250420479935370286463183345914684186858728381654849781460166481468395417213222301074806410131454383917074496942234723528062589275223937018370786595093873449822004298450021836619634197406036406904749317443672868302523380470753793032087570180685858573018046362702833286828940432356641209553550548978770999973102985374123443789897472980448705203718515844825626137003479567309249346700900418508852228378497614359648766247521094823050038958828236671777963042854217583873527032484378715985874302439844773949964273808179415451456378923216339501003228107526259087903292498598374365460141373763453403120517004722105186233350563191815822137006948576925421172833821619894865245693872875810020665173293854476266686967632722910475541249724515850144050141349793598295427362210425410015933170620917716241562741052135950855979455618922668860831543099607637318975402969615454694043683274573180010354717953384524456892897366492249464258581035135384440469227512886885501099433801659531512831581902510717108944111333120093377782555513953792305761795859275842014117009759044930801307317820299353807204275106525961968896103165013797627272660872718308423504881666234747443493157490489640395650257806194169197204797698004472769125311780890262077657470998167428254621315224880983960711739787540790618879781811122206500378252231606108818459573821503496827814901379475602027223655345635646431891065763372882513351332285000146973084936970792384340484771996944571117564913554703128311608123126202328201015717238606440251241050537705323586581644184673125847589423775285178334252863740135393169854220556879096114988226084762513025394012418333605574165235060562658256990379490118923315883927933223843683082463071770378000856180823564038956429627480502551351671582018451136304021047716030109131282576807784221731760897529179000173187814259071487022662129325111457874849100021688975212722695195942604629140828503697143652643313257422462637326865249801122300199360144410329766038372660129932010407959403447146459060513815645727154808726308246896489510008201560988874733175984173003092213484860092046938225468193485668589510506365739090836485312586074687793558818192284381958493011774770846686625072494438912759469514643584901472990472258658569227918231654888430048040997737167191406443896290156344797480705404292122158244250419620744656349887825982771508695923860048387172752289248959714895826803534772704760031560886735699959704136967992294316602982814466319905798471720918788480156140580065202032405927054241284870086916847465497738245621779305607390074626231634141360628841938021816142193796477000565499595546647138917425437591559453767175527192539298054518410796706869723822002959199843791590305346901500441815895373040126424562222304225037567969736225448696647688346368414657405315555794547807895367706660948265502770125758028403138971573035724602805685720723545632988712110504882808298907739906086884010542994687553114287948381552064834376116151436256698225212911397128048385398300152818302406370256191658052684840725502829990562869128665308819028347039926455538394931862770160184714441021020293133341713676103980013136247794772821039683222221765632083275078723713949041970597531101364176606819318431510268976468573781172699507410104142111470680421136792500120822904956269784695036867890334314681671717445733532405892366350757980643846317431424234432373586296547747738801054488773686211737358575462465746204187455185118422001168744259126597378400650165078060387799924535711498000849587136540146994300705617619706868859088312603708370937497704315019126702491487734386341465563662342863258994632491267479319067220502938421735104000205426397758895319372934828977313983564720952232622591399826764903509038893439504424635502388946037764523731463486707980069120681576770365938359337262673661885401445180825563837112128061752580845733747089633326992634431246044272640085620090780461025287025880552903904449912145348621380348106539471860871754040011663599329150633652618732989362141894762327738235160638860843749391248598582426501242146150693037432108183640997512243927419580311225870040524317236140759209960654118387714092048299294924777645882478978543740646919468666267319453328691565932818168428734597700064990304043050840889400731478543210779140248088804887606364895315955764560617654810210771634787134469704153185702721617420030148862975915264778249976140737511452146443124246533186259896143508803052247894217460442201677013571376363276564162058454791514329540480971660998486073026970461177437632079576890634778791517940599002024552980186062069631332156682337473761144757656287953550203131048507601391226411829251085975278398491360510995506953183668920183966685245988457836354890537881402481081482893407506476860737356959502654731397385147209718059124074179035529121726991159923200270156525241903668361141784074675760793176041596652092953117487887115982311139405726978480295415214552980797677234317698104233105723868101162828721737447814335534574364252992577626861165364756221881797372518633798091066082435336403669570287851371082030814643596590472621641030531918808211171050234690392854448645170248003102859250000")
e = 65537
c = ZZ("1006624791493872428156013132059185769577908890685123588860265413284478464254081606554860552210162863617331555371407971112094881854682477696890143480660423446044879444417008769393551070479173256026444705522057313119317241134128056357856043702961942412317803244514905039381718005782757349223826371540863367884775322082571267626664637500353551029720919459564387412660827208292073532971906715818309760944558550028133605741467426684234633972800537234131209999677914376654373116301044586417380632098476979662901970486535512852275787807129053088109817051758957834342989399592121031376276455845110587077114823835770421749166841305733752044998141378948381464573574560515067220937615508014293148511132957173450923901104844962138071222321820132628437648595228819330349109864446780227763426619303986119229621458207511566668158113715592217919871458036544480027682786078776299592553428087955730410568687275539001478443127352388636719649371746991122841977313995301415814024795136453165946378547065993744458062283486073631304755589979680730794020405323329572961253293360513577338700402651103937763697025892349782709902651770736554098240800500905352177960476592380369757239571883253918139455129374959646800171920297714760947729609320603546587712893608811362635798112501347980735882977738892418203192714895095519940298016722620347929443068372813626511662321887474180748198509299589935045699388809030159788261027807313438412841025239120319789278300516865858359230937403655095545329741087715157395889411181656651431755356910802969116255660852026337232679971520612901985681150276612893468647847587680964094708278602943783754648995818234717511489996143840093503781390350945079961559647051120428390455592205721145790870564395659275761821735768348924691948924001584139013711717688721975276464445626460541472341584910015010294143221065039454929377920080964431493187025998698909062992018091025228637414578641083916317310127675988536433848182962264124689344803104794244977847730417665697613020580762276541180971639068306892008943748634947095804119231041511841161479207569737310938418455233204854211483863685429302869985400525105382306880318651887244853417524930678891244022252161339631314110650641551571747024730760363332459523871513220109586935132987835373286917661742301433236538485386215340959957194127460536298034016006134576599342774727510302306416124407356913070780661214510985298250048979789686131767482733919681070659684053736571095855834449965474750177878817656873656038737978064455651478016298030019265498584151329188704586240839041740808954415008339104552984969183387391975456318773864286787943031697213698996686946255718107336538134926303263597905318748419638890179539866151284431768322967558139969106836646864556735333036359093383385959996772752989168252014861238699338662994031669081399864374189877145752269437866314973447041167696543603845305033030714223885878865956724181394844676959585621512069847970955085021589628226610853109174370995911017065603884114070642701735919588167686139654362927933822938764802556055195568144057238705624269185944850716827815554482849355496624961694074052845915719970017838529897878451863537557483363155373695535010460614331502651047864280269291926105518969254360574019457618325324082957037366298643610879096374226875910736589808410833279550396688820112283278208192991766623258627578107830413797764710756715821439048302883130479030406039841125110866364087037092015956975765428225817051792222804866800514366895524551288821443922687782466711259163390753629516336747278600690220615246778329521485601887038323999632165619512484034270407598276771121269934821431430437751648524773488609977866454583501659378004048126708051934746811216528607605028495167001434044862816418060096489517127198528350180417612314639917948400514051465212264142225429422722794174197508664645132263432630798277466878138853812019581873744554476068771729959532923958292171564541468330490903970968262341611203482886526713457747342028423402540955860518912987342766394604241558554587187353160264098489837231496398170333459351127747345598896769081384584750430787836162551966994024722915321926840046946020177323250760936043053489784314710450045451400762557398691999969341391393667389764442133223968166420049321213369846281125972240109111927147479718196686775120968421731108267716504745749378607555160261913878972583437778409498078989352239814566971242742322579712446494860316601866751613941041827582079819595283367380330325548333015225385899095588166546738126699274135900008035777385020676563990834349232478916414853491568719444728035175916532996340297113692229019744894058969659382966820585926314563300800010086673046048874454860811145174154648865245690685938795590645994627666499023763011229154846306115598926149462227441554939820818508788777720370390824600073699685626392863302263500449059401165519243659474462247408799410026810438586759098812732411632772090332727345225549303454806184596881818414587804540759689170633889674995333226769497114494058588499691691065203524494128977027892609849802035234747074885030411841630615900522898984642948949181689470204596007143211275742464512506843889642600891097868562702744643405087386398328865820103876272587774375387015341065359130872818632759717848940107656765204322687313649525128470167246554491048891165634572344021214815159719241398084512753372214338006468069715823289367786004767028451422319583347230601902836402419482529964001695177744851966732250172653996454063182619802500001204199261556722125827672017589040667096105930732416489917034594598879454961594924688367124617812256762524631356182661634533531847507911310449089359427390844904145102779246503313737115696547458402528704634576385425637883925074328602417237203731223574073513231367722733229")

m = power_mod(c, inverse_mod(e, euler_phi(n)), n)
from Crypto.Util.number import *
print(long_to_bytes(m))