prime (YCEP CCTF 2025)

2025-09-03

Made this for YCEP CCTF 2025, we are given the 2 files prime.py, and prime.txt as shown below

# prime.py

from sympy import nextprime, randprime
from Cryptodome.Util.number import *

flag = b"CCTF25{REDACTED}"  # Replace with actual flag

def rsa_encrypt(plaintext, e, N):
    pt_int = int.from_bytes(plaintext, 'big')
    ciphertext = pow(pt_int, e, N)
    return ciphertext

base_prime1 = randprime(2**511, 2**512)

p1 = base_prime1
p2 = nextprime(p1)
p3 = nextprime(p1*p2)
p4 = nextprime(p1*p2*p3)
p5 = nextprime(p1*p2*p3*p4)



N = p1 * p2 * p3 * p4 * p5
e = 65537

ct = rsa_encrypt(flag, e, N)
print(ct)
print(N)

# prime.txt

N =  7765845103312156732325002162236941884419768431980372761161805621622910722883546382024980557773627411739011590898207999509671310973000176455787037848371494539567119629515710474018441066515260809653090909414963087993902936563647001295928327618956999652403150575805223459850935352047346880231113846191370191939923380804121869269658408511861717885549300700552273388870017433988809846875054392890855789921728868098221800988307002224892400131658389479711746321845875538490252338817027658006136767952450782983023642113528327155365364225286521270598193433376806016209659843672969063507606708242153599493195117568117125143225712419179125986772120642228677024234807656555826814272197256036459180208741849234486883347187413504058983949761905013996466602463978310696402344102711397138808529821350317724086062526205066083610928595051062934383536707122339619758590162639779152198259989888442173968557636048614631091396116620785570806899351816139237525203536543956652509661586423431783478575066751759368910862159976278335987302176947398875760836809967379384853631164055875396944992368640150742141186277727217195772341592359359987718933671493125729883685427781166717475425308610703340573718477179518842054111546012421568110269174731592078666494926968485296605717562838747842527876115478254654233857508304298756311542886581002982649663925825860091632783224825231522663436588300071842033953885577911504147231307440253292815786966661854914580554056709659060350598147177774724323028551267790811094504894410385560411325678626632145522991636363121815662471841674737566596704487109676947924678138705921815773931365086606606348703886623495564880287228920539007782761460177860437768330827239760146393471927212278428798652858616052175934042210889437909811413238058455044357947628780670853611943332665686278204044683994686597905943255238064232842685220800042117412794114418990285059781925690055706487482571944326612400990032244301279888230277437776051158777728678754536353074065665925640212912928324944654005835667469479105845356624684104260161303702790828070832146932484023448798469569752456181769525739348160954852097416993138011821449533624407792223021801981736561395659017624155422992673340298690960911813922268715967468433022176325181619253582219441573358746309911896342052632447911074326953810398248649282712892310929238914391082234952158525663631113101003268332446230184479327363591885541954733599341268162520446787933734980382691871456884087003300924359511573536829858730660965464303
Cipher text =  4585750358494646313063299769349680478835287601582954741920929418032062124392298938837905756462603285921233839070405022198943112112806608429427641132617892131655760424929106664607726580603763334315025550376124694791474607323506741811756940340370387073734267960606846858847945124743549017071628208595829802276114218442414697051691835645446552668726419729458895310209932105340275344220661534022921894271499433400653558072359220219310839753770927271960421863785201388256745355549960991852580198589290272307364352064597949354570175158180921625687036842735141735153828264204748678843664241835637758826052184046881226048715032591006520671036622820676334833459077719016461087774023086412226453257665685648585791636336782758458846969141539952201444160663532715890058318576442458570340213752632247977504076389428214270979776930827408694821854236194606667192092387305978941625741895689195176313933737189257467676792705063658896419266709984463279878301729472307182844293750425818505979464075088089875468516864678411038481312517098647650582298729338384301444057751000259242292498822199607702728328327505928572621087499991069768117757974579847289879422581548443919685064827329833268190849242329963620629892502274724567066660178120130131520326057283193554740800956084488712229892758058357765868566571616772624529804988879196093234091660574064840549911102856700715636962709884836997296485614893630553932986153642941861659215707058149069881804508484978432529824071766954615689412215282790488424353578958032072832083842151968809818187269674655834543790350841915705839139615110055870024324237916412992498645578897332934360017455119128236636060529675256100944524258110073369670029748228866846396871048787304024635710757866141080764702639081477591013492108682549931943714684231849940440160636467573522063690487656654763424960634005886124063632183027748330462876190551803041375753160660443563109583659268986369478682250092122040446751644173029855022227281662171854127158169146450339010150429468161398994486234933648167659343958702341882552435426200024108976980053991608466980940476587849725371520744777691478019262305976542622265797627098807364999993496630610721533282446446549748888342157372160353883209010014458100568788805541462006259492084961374317501930433967713034138691136602114323523241145973664571713102587997541474675237242486422933769109818011013498773894768447557317456666768283010713810874159811052036495041404920068878753266474422997607914146339527710511577217611854530969

From the code in prime.py, we can see that the modulus ( N ) is generated using 5 primes ( p1, p2, p3, p4, p5 ) where:

• ( p1 ) is a random prime between ( 2^{511} ) and ( 2^{512} )
• ( p2 ) is the next prime after ( p1 )
• ( p3 ) is the next prime after ( p1 \times p2 )
• and so on until ( p5 )

The ciphertext is generated by encrypting the flag using RSA with public exponent ( e = 65537 ) and modulus
( N ).

This is very weak because the primes are generated in a predictable manner. We can exploit this to factor ( N ) and retrieve the private key, which will allow us to decrypt the ciphertext and recover the flag.

# solve.py

from sympy import factorint
from Cryptodome.Util.number import *
# Given values from challenge
N = 7765845103312156732325002162236941884419768431980372761161805621622910722883546382024980557773627411739011590898207999509671310973000176455787037848371494539567119629515710474018441066515260809653090909414963087993902936563647001295928327618956999652403150575805223459850935352047346880231113846191370191939923380804121869269658408511861717885549300700552273388870017433988809846875054392890855789921728868098221800988307002224892400131658389479711746321845875538490252338817027658006136767952450782983023642113528327155365364225286521270598193433376806016209659843672969063507606708242153599493195117568117125143225712419179125986772120642228677024234807656555826814272197256036459180208741849234486883347187413504058983949761905013996466602463978310696402344102711397138808529821350317724086062526205066083610928595051062934383536707122339619758590162639779152198259989888442173968557636048614631091396116620785570806899351816139237525203536543956652509661586423431783478575066751759368910862159976278335987302176947398875760836809967379384853631164055875396944992368640150742141186277727217195772341592359359987718933671493125729883685427781166717475425308610703340573718477179518842054111546012421568110269174731592078666494926968485296605717562838747842527876115478254654233857508304298756311542886581002982649663925825860091632783224825231522663436588300071842033953885577911504147231307440253292815786966661854914580554056709659060350598147177774724323028551267790811094504894410385560411325678626632145522991636363121815662471841674737566596704487109676947924678138705921815773931365086606606348703886623495564880287228920539007782761460177860437768330827239760146393471927212278428798652858616052175934042210889437909811413238058455044357947628780670853611943332665686278204044683994686597905943255238064232842685220800042117412794114418990285059781925690055706487482571944326612400990032244301279888230277437776051158777728678754536353074065665925640212912928324944654005835667469479105845356624684104260161303702790828070832146932484023448798469569752456181769525739348160954852097416993138011821449533624407792223021801981736561395659017624155422992673340298690960911813922268715967468433022176325181619253582219441573358746309911896342052632447911074326953810398248649282712892310929238914391082234952158525663631113101003268332446230184479327363591885541954733599341268162520446787933734980382691871456884087003300924359511573536829858730660965464303
e = 65537
ct = 4585750358494646313063299769349680478835287601582954741920929418032062124392298938837905756462603285921233839070405022198943112112806608429427641132617892131655760424929106664607726580603763334315025550376124694791474607323506741811756940340370387073734267960606846858847945124743549017071628208595829802276114218442414697051691835645446552668726419729458895310209932105340275344220661534022921894271499433400653558072359220219310839753770927271960421863785201388256745355549960991852580198589290272307364352064597949354570175158180921625687036842735141735153828264204748678843664241835637758826052184046881226048715032591006520671036622820676334833459077719016461087774023086412226453257665685648585791636336782758458846969141539952201444160663532715890058318576442458570340213752632247977504076389428214270979776930827408694821854236194606667192092387305978941625741895689195176313933737189257467676792705063658896419266709984463279878301729472307182844293750425818505979464075088089875468516864678411038481312517098647650582298729338384301444057751000259242292498822199607702728328327505928572621087499991069768117757974579847289879422581548443919685064827329833268190849242329963620629892502274724567066660178120130131520326057283193554740800956084488712229892758058357765868566571616772624529804988879196093234091660574064840549911102856700715636962709884836997296485614893630553932986153642941861659215707058149069881804508484978432529824071766954615689412215282790488424353578958032072832083842151968809818187269674655834543790350841915705839139615110055870024324237916412992498645578897332934360017455119128236636060529675256100944524258110073369670029748228866846396871048787304024635710757866141080764702639081477591013492108682549931943714684231849940440160636467573522063690487656654763424960634005886124063632183027748330462876190551803041375753160660443563109583659268986369478682250092122040446751644173029855022227281662171854127158169146450339010150429468161398994486234933648167659343958702341882552435426200024108976980053991608466980940476587849725371520744777691478019262305976542622265797627098807364999993496630610721533282446446549748888342157372160353883209010014458100568788805541462006259492084961374317501930433967713034138691136602114323523241145973664571713102587997541474675237242486422933769109818011013498773894768447557317456666768283010713810874159811052036495041404920068878753266474422997607914146339527710511577217611854530969

# Step 1: Factorizing N
factors = factorint(N)  # Returns a dictionary of prime factors
primes = sorted(factors.keys())  # Extract the primes in sorted order

# Step 2: Compute phi(N)
phi = 1
for p in primes:
    phi *= (p - 1)

# Step 3: Compute modular inverse of e (private key d)
d = pow(e, -1, phi)

# Step 4: Decrypt the ciphertext
pt_int = pow(ct, d, N)
flag = long_to_bytes(pt_int).decode()

print(f"Recovered flag: {flag}")

we will get the flag, CCTF25{pr1m35_c4nt_b3_t00_W34K_83503}