Hi Everyone ! Welcome back
Recently I participated in live CTF called CSCG CTF 2026,
In that I solved 2 out of 3 crypto challenges , So here are the writeups for them .
CHALLENGE 1
Name : RSA
Description : I can’t quite get my head around this RSA implementation…
Note: The flag is embedded in one of the prime factors of the RSA modulus.
Flag format: dach2026{…}.
And I was given two files
Challenge.py
import random
from functools import reduce
from math import floor, log2
from params import a, b, c, d, e, f, g, h, i, j, k, m, n, o, p, q, r, u, v, w
def wut(a, b, c):
def wuuuuut(z):
if z <= b:
return z
x, y = divmod(z, b)
return wuuuuut(x * c + y)
return wuuuuut(a)
def wutwut(a, b, c, d):
return reduce(
lambda x, y: (
wut(x * x, c, d) if not (b >> y) & 1 else wut(wut(x * x, c, d) * a, c, d)
),
reversed(range(floor(log2(b)))),
wut(a, c, d),
)
def rsa_decrypt(ciphertext):
s = wutwut(wut(ciphertext, o, p), a * b + c * d, o, p)
t = wutwut(wut(ciphertext, q, r), f * g + h * i, q, r)
x = s - t
y = (x * j + x * k) * u
x = y * r
y = t + v + y * m
return (y - x - w) % n
# check if the code works correctly :)
for _ in range(1000):
# encrypt 100 random plaintexts with public key
random_plaintext = random.randint(0, n - 1)
# verify that the decryption works correctly
assert rsa_decrypt(pow(random_plaintext, e, n)) == random_plaintext
and ,
params.py
e=65537
n=523444229865334823295982383639695013418641329204866720631674367185922596015918077243068490837625320300674560504387827264320304527605870098182833209269822990985914285820222611175268806564233698873437195249223957011558886959242144918325815246221876554613354421003704398712977270561341140818060708867226337609852676788212056171805928276100379858202272309835331367703927890752997038542892034490693633084218714559181735453896675673522918661815485506696376692550576640245892894247928088886013068655264245329947103009638581622375361885294441552617777977362517690444439739712896712919329735060843260632586474934170610258035203305005368304933557155887350856013195494745330993891336458662075475573171480028859675892164900634471524806982923120994323467322120529319585536498803430691541728033777788343380210014233212125979391100746323113638056658841130155968310348614184238553170026071346230433361826676139075295644710871986546367483899628150824047842251722048510491527687601033529170958978241935441354292055771830745084515264191301451256614460139926324134165731179266926934245716892220779015917646956344517315286011965218089214017474289229821252407455653951748471311242154288770655415878947492671144412766751805282400067134929615064180343241973
a=20045782872370609593425765135166996245156320698166240686467620052369606597450977685893519858986173729306745409669867245443501903741100715899047366900061455676428095345373619185401802801331820904355165013892257188252619952290755897947206805631903811865744701037612326275482599764898302321247712331967553606774820054140194523123377518011758766555372284036045671880680961800772428457653528619532021689457875632755863354572289232347730408224509068108260109796584308185036166175136761517627171489724867127500480033004963545175281906264883896156053039864694898281022039316111799596727953866204050352861396734528099422992599
b=3991317400352180668131118990500492864538989918334256805111957153676967592474614067537041576908330289592662053821055185621053856842474808885045257399678301867636854687554633393657843301157924850249778856942685739064492562510080395398345140310525891670283697316044889964463165439066692956772449116432757386223880298595908773969310721920820582523419701077947044021470188715035460694723817738932777053406359305397593981364815574147247379762542829446682327267721002653745218286938109609699643123843476084391057928286411714421592834620403865920808881070418209158634191939626774994712418500805783717160949298717025834269847
c=10772063914118401564933690698429707094848607954081305535486024537730947585882198641738492434706793510193910026342906369312672116706808782963276175225952160280318488726405889999246501987088921092243074225040779220756083674303895148713402851691249971230355550223620423198589658598719841297941535141775756191559400969522954370077445002977243854858496370690476362142716568535188135035941667285602450155545818692334843511438811506252295777781697617473156851503395416721139575198451030451357942200184672087110724394335122835300247488492818611154031098836109287745280741057614295603753525139581560206512548912069336344953805
d=18511777890976860607714549484324024380631048805979275425373942384683876094094531952296797233867476898621003327993938577699126214964635267537893258792515754688517842253471702965032761610375294066334426186301485836834014595663623299884958793557499999531617057999573332831949368142089861979780942793826556639593979843404728782758112590150902572170274664389920355759874175256581303542786446615469760749399594337766245501122757187243508157718676573376764045187180122787076716553112906015107093004574285693493024448219002739481291589701263031093845557123324774111551909280260529829327074260249001403038248158125696253201104
f=15630380746954635344891447578898683631979554150832681106286951845431957710616119762475194141912807535862826796850882350038344870407397204643082283681372976944765264935435360826238259772032331888691449224883494417932040080744147125538457226560308981426928298630583379908350926524200303763564745601400365731628429078721854604763246965867704111094956724069356583541029497162186582628978661483551376167375919682866316578710724884243280825776188200491193612466826494681495676792441336296747254584324978561099363934719845096082455874369811674454863418119477130205177928192902460762880097352394295052618183546878533531385523
g=16574041711383307212640527514590483662011830451007841750859295758949538299503026876766373420140556200355715413633598342333763718162977706087056199120642925523536881555559556306794631427291685987774555460434873231952102290914182233498171061299611417739642751608017399341988513313755505553865064601823818684017629356396218710778202725605675787509584731031288830233397650206769590050584936971045406981718866232563907359541719266091126976214551762289244070105210204103858523636808717857727944445611385114608694445156212726080592314563390522513158453310226991414484422313126304472427471603683910182707786996498300919842740
h=20301144682774982565863365107778541246831657115614906946849900162967272947071033544640987548160249232739881221518446600555379959532816713480700876802649776596872690564159447301048159448395577619677081149533294192678943119962564512987719553744528461160817085951540518692548340327162851052986073124246211416259520411240562287411856863478448289925302564391242786209320009664778858162276587076142759615262912384339358662917599393369465962425106342285314888063320186605373932176711655940031636733521709998220623692233741065360813296091175376856874130302272930174445642835578177582296749250532068621504428584884896507121131
i=6459673495992527338723594980162715362354910312581043823717781916296652655307347271401132938542297280618141345180470215565674856947042363154080731748606464278611795696524601687202872948998725696183292512823009244343339372500294931022360484067360571715451072517258660606878898407277159664155462761043390414336979293217562490868011680459700145477404261816374845642820951769695808999376639270095540385927666989770421362978449529995877190579463824878885515453363054543569132617971725648460701595588456561240275595219291523185458869527545425024834502981762960300648752341892942256266719164152816096575663536307990185678263
o=783222371316554985968119335248696135906688108153975683588481010619132563076036603072761911621110925085922891635023121754732843821440869017550437422743319165066307300031230532541530803968382501116469737929209047848285152109888424216360960542517074037067921388291778084250245646867937916963474291972805271791515775598651203498325056996801107602504073691955422726116809037685884374209428467808898720077090455398640024162979797118868740427784759898284236759383683026100505828112016714456275539252555022100288726442020005969355562960496668060885167582180812296731377889044495423789558851069069159796938881720257245115443337
p=154708624396238079756864834283936723144821773719105375178316843010174160524451360426423771630296971710860902910975858538746971948328436586171044251092596015253381266656121140701217557080365046165708088461128018458245297577545282557732631081926443427037739357420949781238126112311350560296701816383076457131483
q=2209470371774375764456432806918718509162816263445752956980073216716357010111163706733607376876833906302845221575581037180362015246569740045439507352095249087323452905146091254735353586852122251415640071298813884917090733773781756368611172456553436895915983014467768585459193125991149278799249702282745103420848522411140983931377467754220505920062731290434822077763979772966569802480905802372646637947505692927918769371170156641196297439844994670534989022462890969727100796574453972690528256176847849525142396331102534860374512389623350341404938304652593829196176163963552888107895829078877102137136183287794607866183837
r=93211526531545092156852576014813844920005867545410518968887383855339652871284296450719496591277996077476299145592855191947666634039355641631541952021797228149816856094729490310008500699331982898726428834072441376362577160261613996183745001073455638305948514501240961677097961909797841294275992693687114817390
m=25396211169820411085706124217456534588078347855698309850345669157659275978289238008432268699733723060952243926156103875636345002834134943051028820139025851578430493162598750054429351573012899441559081279296711320886100388204388004236910028236246401102482563384686995235163139379208612399991375888307414981848925731062329848382792610066181378284205193046479625085003495264116425432503864963993201317866156328627376219513691289513836744487038842019716110693526040590206724668949433435140103301574602299476239875986583503663697632475929300518123452583274839242419399266789190928875014411530111683775217455855766663683671
j=31641472742934134143509208935563999095331351390621217100485714702652930415446967160971267981875549167349111514530562304785278655275986444287800184325458046710879996257762447665794912238430387016605941408797352891138944451486001872145610665409914073001044636399833818000446450861498769581346596925003526681499403169204439648930816014890957956168234620674609034528679878476969859870893001037781000618261234077592608705977206603728561329450505551454709713999937076000700019400023703377064022345420684653145433259181854644098166309007694053214132551972830541729588140194443935900871784345345926215716684534961355487462942
k=31900775338146313184945883617105110982514243222052616262166526476812305298424573398680716094761506527253681276269844895337325317903556956078345195421976169297780492200500657593960751650167158126796877567647826857699039497215457671159304510855476857632533606284554609864061711872090997545904868047343082832714239860028415512281506301779377847739286547808465484199949624774361467023462791754080709325485020335824632666991410790321016844513683900333908608491148054529744124678820152400986374265108657302555781450322913170737222379065198972039862181397407808132595351785173260446927199032071701930219604251324268884891760
u=13929781390027196740722002507426848433691095519396684211799242877040532576684519406813865569773757515990953941722823288261830374501353930886420309166439377234373251301024415764413630233044149167559733830565918865786587884893058172139396752327221836031087192845821911917183986482768671105704149119593518302623360894327889948413404682403698652726310578920304505423871056753717094119108375697883150737313804089728241709975167419019555131802803404232352341851152032352584511091591134487899745105351591260118285471500939105320463385970035481060107184368415045970088177321919228641215397494182671268233686927125161288863558
v=305022237644970351963225436241818954869774522328053788647321143282834512740169162063725579769489304756156114219922427023262622810478249636443641315847165782473583768609948714441821580607997637085306469573910992878297828582253662360332269984418533485732908649970408004201474361658292633622030514418308754849829280883011080956048518407610806441189958118864425656170419461140538721456964005218933028246435535481695739596355857047689039995923989692195544679165182699950177325907927304896845944062612686112387419213193147747868655498674931106883594110052589914019317156074052447448254826334006412174044896729318538486512604264741668977320693441844481775551620710347928518749624228381124840956391082958208268805748440555969249819867609305752065676726565868244700720060083815640732904264761284340331267198695957408564158371523953573092799721888755852206871982430790834681492128677332868680557739338395193993770088323276704134107024300907305102389080250409699969797597845627843562107078222296901864081163066665671937713781570438935407852346894379702791824899446821894414269734935651141825514034032426812299745637205356811185205503592513367285280036121641943274452827923376526358996251643743056545780131970756422278583025775401180135249133282
w=828466467510305175259207819881513968288415851532920509278995510468757108756087239306794070607114625056830674724310254287582927338084119734626474525116988773459498054430171325617090387172231335958743664823134949889856715541495807278658085230640410040346263070974112402914451632219633774440091223285535092459681957671223137127854446683711186299392230428699757023874347351893535759999856039709626661330654250040877475050252532721211958657739475198891921371715759340196070220155855393782859012717876931442334522222831729370244017383969372659501372087415107604463756895786949160367584561394849672806631371663489148744547807569747037282254250597731832631564816205093259512640960687043200316529562562987067944697913341190440774626850532426746389144048686397564286256558887246332274632298539072683711477212929169534543549472270276686730856380729886008175182331044975073234662154748679099113919566014534269289414799195263250501590923929058129150231331972458210461325285446661372733066056464232343218373218838496417022229045761740386664466807034306026925990630626088821348515451827871920841431680988771329615031649170574900399222977881743188537687491775593691745764070077665297014412130591235727690192898722561704678650160705016244315592375255
Solution
I was given an RSA implementation with a public modulus n and four unusual parameters: o, p, q, r
The challenge hint states:
The flag is embedded in one of the prime factors of the RSA modulus.
So instead of decrypting ciphertext, the goal is to recover one of the RSA primes and extract the flag directly from it.
Observation
Inside the code, values are always used in pairs:
owithpqwithr
These pairs are never mixed.
In secure RSA, this is already suspicious — multiple values derived from the same prime must never exist, as they can leak the prime via shared factors.
Key
If two numbers share a secret prime factor, the Greatest Common Divisor (GCD) will reveal it.
Example:
n = P × Q
x = k × P
Then : gcd(x, n) = P
Applying the Attack
From experimentation, we find:
o - p → multiple of P
q - r → multiple of Q
So we compute:
from params import n, o, p, q, r
from Crypto.Util.number import GCD
P = GCD(abs(o - p), n)
Q = GCD(abs(q - r), n)
assert P * Q == n
This successfully factors the RSA modulus.
Extracting the Flag
The flag is embedded directly inside one of the primes. We convert each prime to bytes and search for the flag format:
from Crypto.Util.number import long_to_bytes
for prime in (P, Q):
data = long_to_bytes(prime)
if b"dach2026{" in data:
start = data.index(b"dach2026{")
end = data.index(b"}", start) + 1
print(data[start:end].decode())
Result dach2026{4dv4Nc3D_pR1v4T3_k3Y_h4RdC0d1NG_th4T_5uR3lY_15_V3rY_54F3}
CHALLENGE 2
Name : 🦕 DINO VAULT
Description : Do you have a park with dinosaurs of your own? Then make sure back your dinos up regularly! You never know when the next mass extinction event will happen, so better safe than sorry.
We encrypt all your dinosaur data so that you need not worry that anyone is able to copy your designs. Our encrypted designs are uploaded as well for anyone to verify that we use dinosaur-grade cryptography!
Given files :
Dockerfile
FROM python:3.14.2-alpine3.23@sha256:7af51ebeb83610fb69d633d5c61a2efb87efa4caf66b59862d624bb6ef788345
RUN pip install pycryptodome
RUN mkdir /app
WORKDIR /app
COPY app.py .
ENTRYPOINT [ "python3", "/app/app.py" ]
app.py
import os
import socketserver
from dataclasses import dataclass
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
FLAG = os.getenv("FLAG", "fake_flag")
print(FLAG)
primesize = 2048
@dataclass
class Dino:
name: str
dna: str
vault_key: int
@staticmethod
def to_dna(dinosaur_information: str):
lookup = ["A", "T", "G", "C"]
dna = []
for c in dinosaur_information:
c = ord(c)
for _ in range(4):
dna.append(lookup[c & 3])
c >>= 2
return "".join(dna)
def get_encrypted_dna(self):
transmission_key = getPrime(primesize)
dinosaur_modulation_index = transmission_key * self.vault_key
evergreen_number = 2**16 + 1
resampled_dna = pow(bytes_to_long(self.dna.encode()), evergreen_number, dinosaur_modulation_index)
encrypted_dna = long_to_bytes(resampled_dna).hex()
return encrypted_dna, dinosaur_modulation_index
class DinoVaultServer(socketserver.StreamRequestHandler):
def write(self, string):
self.wfile.write(f"{string}\n".encode())
def read(self):
return self.rfile.readline().rstrip().decode("utf-8")
def read_int(self):
line = self.read()
try:
ret = int(line)
return ret
except ValueError:
return 0
return 0
def prepare_dinos(self):
self.dinos = [
Dino(name="Vexillum Rex", dna=Dino.to_dna(f"Has a crown and {FLAG} written on its back"), vault_key=getPrime(primesize)),
Dino(name="Pedosaurus", dna=Dino.to_dna("Has giant feet"), vault_key=getPrime(primesize)),
Dino(name="Despotiraptor", dna=Dino.to_dna("Slightly sus ethics"), vault_key=getPrime(primesize)),
Dino(name="Planosaurus", dna=Dino.to_dna("Is floored when nothing goes to plan"), vault_key=getPrime(primesize)),
]
def create(self):
self.write("What is your dinosaur called?")
name = self.read()
self.write(f"Please give me all the information about {name}")
info = self.read()
self.write("Thanks, we have now sequenced your dinosaur.")
vault_key = getPrime(primesize)
self.write(f"To access your dino, you will need this key: {vault_key}")
self.dinos.append(Dino(name=name, dna=Dino.to_dna(info), vault_key=vault_key))
def view(self):
self.write("We have the following selection of dinosaurs available:")
for dino in self.dinos:
self.write(f"- {dino.name}")
def download(self):
self.write("Which encrypted dinosaur-DNA do you want to download?")
name = self.read()
for dino in self.dinos:
if name == dino.name:
break
else:
self.write("Could not find the dino you were looking for")
return
self.write("Here is the encrypted DNA you wanted:")
enc_dna, mod_index = dino.get_encrypted_dna()
self.write(enc_dna)
self.write("Use your vault key alongside the modulation index to access the DNA:")
self.write(mod_index)
def menu(self):
self.write("")
self.write("You can:")
self.write(" 1. Create your own Dino")
self.write(" 2. View all available dinos")
self.write(" 3. Download the DNA of a dino")
self.write(" 4. Exit")
def welcome(self):
self.write("Hello and welcome to the")
self.banner()
self.write("")
self.write("Here, you can give us your 🦕 and we extract and store DNA samples for all your cloning needs.")
self.write("Make sure to back up your creations before the next apocalypse!")
def banner(self):
self.write("""
🌋🌋🌋🌋🌋🦕🦕🦕🌋🌋🌋🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🦕🌋🌋🌋🦕🦕🦕🦕🌋🌋🌋🦕🦕🦕🦕🦕🌋🌋🦕🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🌋🌋🌋🦕
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🌋🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🌋🌋🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🌋🌋🌋🦕
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🦕🦕🦕🌋🦕🦕🌋🌋🌋🌋🌋🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🌋🦕🦕🦕
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🌋🦕🦕
🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🌋🦕🦕🦕🌋🦕🦕🌋🦕🦕🌋🦕
🌋🌋🌋🌋🌋🦕🦕🦕🌋🌋🌋🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🦕🌋🌋🌋🦕🦕🦕🦕🌋🌋🌋🦕🦕🦕🌋🦕🦕🦕🦕🌋🦕🦕🦕🌋🌋🌋🦕🦕🦕🌋🦕🦕🦕🌋
""")
self.write("Vault")
def handle_choice(self, choice):
match choice:
case 1:
self.create()
return True
case 2:
self.view()
return True
case 3:
self.download()
return True
case 4:
self.write("See you soon at the")
self.banner()
return False
case _:
self.menu()
return True
def handle(self):
self.prepare_dinos()
self.banner()
self.menu()
choice = self.read_int()
while self.handle_choice(choice):
self.write("What do you want to do now?")
choice = self.read_int()
if __name__ == "__main__":
HOST, PORT = "0.0.0.0", 5000
with socketserver.ThreadingTCPServer((HOST, PORT), DinoVaultServer) as server:
server.serve_forever()
Solution
Challenge Overview
We are given a network service called Dino Vault.
- The server stores dinosaur DNA.
- DNA is “encrypted” using something that looks like RSA.
- We can download encrypted DNA for the same dinosaur multiple times.
Our goal:
Recover the hidden flag from the encrypted DNA.
When downloading DNA for a dinosaur, the server prints two values:
- Encrypted DNA (a large hex string)
- Modulation index (a huge number)
Example output:
Here is the encrypted DNA you wanted:
<hex ciphertext>
Use your vault key alongside the modulation index to access the DNA:
<big number>
That “modulation index” is actually the RSA modulus.
What the Code Really Does
Looking at app.py, the encryption happens here:
transmission_key = getPrime(2048)
dinosaur_modulation_index = transmission_key * self.vault_key
resampled_dna = pow(
bytes_to_long(self.dna.encode()),
65537,
dinosaur_modulation_index
)
This tells us:
-
vault_keyis a prime -
transmission_keyis a new prime generated every time -
The modulus is:
n = vault_key × transmission_key
This already looks suspicious.
The Mistake
Each dinosaur has a fixed vault_key.
But every time we download DNA:
-
a new
transmission_keyis generated -
the same
vault_keyis reused
So if we download the same dinosaur twice, we get:
n1 = vault_key × t1
n2 = vault_key × t2
Where:
-
vault_keyis the same prime -
t1,t2are different primes
This Completely Breaks RSA
Now forget RSA for a moment.
Let’s say:
n1 = 17 × 101
n2 = 17 × 113
What number divides both?
gcd(n1, n2) = 17
So in the challenge:
vault_key = gcd(n1, n2)
That’s the entire break.
This attack is called a GCD attack due to prime reuse.
What We Actually Did (Flow)
-
Connect to the server
-
Download DNA for Vexillum Rex
-
Save (ciphertext1, n1)
-
Download DNA for Vexillum Rex again
-
Save (ciphertext2, n2)
-
Compute:
from Crypto.Util.number import GCD
vault_key = GCD(n1, n2)
No interaction with the “vault key” menu option is needed. No custom dino creation is required.
Recovering the Private Key
Once we know vault_key:
transmission_key = n1 // vault_key
Now we have both RSA primes:
p = vault_key
q = transmission_key
We can compute:
-
φ(n) = (p − 1)(q − 1)
-
private exponent d
This allows full decryption.
Decrypting the DNA
We decrypt the ciphertext using standard RSA math.
The decrypted data is not plain text — it is DNA-encoded data.
Inside the decrypted bytes we find text like:
Has a crown and dach2026{4dv4Nc3D_pR1v4T3_k3Y_h4RdC0d1NG_th4T_5uR3lY_15_V3rY_54F3} written on its back
So the flag is dach2026{4dv4Nc3D_pR1v4T3_k3Y_h4RdC0d1NG_th4T_5uR3lY_15_V3rY_54F3}