<style>
img[alt=chall-sc] {
display: block;
margin: 0 auto;
width: 100em;
}
p {
text-align: justify;
}
p::first-line {
text-indent: 0;
}
</style>
# ITSEC ASIA FINAL 2025 WRITEUP
Last week, I had the opportunity to participate in the ITSEC Asia 2025 Final Round, held from Saturday, August 9th to Sunday, August 10th. The competition was organized by PT ITSEC Asia Tbk and brought together skilled cybersecurity enthusiasts from across the region. I joined the event as part of the team SNI - FLAREITO, where I focused on solving all of the cryptography challenges. After an intense and exciting competition, our team proudly finished in first place in the final round.
In this writeup, I documented all of the cryptography challenges that I personally solved during the final competition. Each solution offers insight into how I approached and overcame the problems during the qualification round. Hope you enjoy reading it!
# Venture Into the Dungeon
Given `chall.py` and `secrets.py`. The flag variable is defined in the `secrets.py`
## chall.py
```python
# !/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from secrets import FLAG
assert FLAG.startswith(b'ITSEC{') and FLAG.endswith(b'}')
class Dungeon:
def __init__(self, key_len: int = 1024):
while True:
try:
p,q = getPrime(key_len//2), getPrime(key_len//2)
self.n = p*q
self.e = 0x10001
et = (p-1)*(q-1)
self._d = inverse(self.e, et)
break
except ValueError:
continue
def sloth(self, m: int) -> int:
return pow(m, self.e, self.n)
def shadow(self, c: int) -> int:
p = pow(c, self._d, self.n)
total_bits = p.bit_length()
top_mask = ((1 << 128) - 1) << (total_bits - 128)
bottom_mask = (1 << 128) - 1
mask = top_mask | bottom_mask
return p & mask
if __name__ == '__main__':
Aid = Dungeon(1024)
mystery = Aid.sloth(bytes_to_long(FLAG))
print("""
You take your first cautious steps inside, and the echo of your boots fills the silence. The corridors twist like the roots of some massive, underground tree, until the path splits into a dimly lit chamber where two odd figures wait. There's a tablet between these to figures.
""")
print(f"mystery: {mystery}")
print(f"n: {Aid.n}")
for _ in range(2014):
print("What will you do")
print('1. speak "the weight of sloth"')
print('2. speak "the toll of secrets"')
print("3. turn back and run")
menu = ""
while menu not in ["1","2","3"]:
menu = input("(1|2|3): ")
if menu == "1":
userInput = ""
userInput = input("...: ")
if userInput.isdigit() and int(userInput) == bytes_to_long(FLAG):
print("...Huh. You're still alive. Figures.")
print("Well... guess you didn't really need me after all. Good job, I guess.")
break
print("...")
elif menu == "2":
userInput = ""
while not userInput.isdigit():
userInput = input("payment: ")
if int(userInput) < 1:
print("Coin? Trinkets? Do you take me for a merchant?")
print("Offer me coin again, and I will offer you silence.")
continue
if int(userInput) % mystery == 0:
print("Secrets weigh more than gold. They stain more than blood. I do not want your glittering junk-bring me something that whispers. Something that hurts to say.")
continue
decrypted = Aid.shadow(int(userInput))
print(f"(whisper): {decrypted}")
elif menu == "3":
print("Running already? How predictable...")
break
```
Given a challenge that implements RSA, the server generates a key and prints the modulus and the ciphertext. It exposes a decryption oracle that returns the top 128 bits and the bottom 128 bits, with the middle zeroed. Because the bottom window is preserved exactly, the oracle leaks the least significant bit (LSB) of the plaintext each time.
Using RSA malleability (multiplicative homomorphism), for any integer $m$:
$$
(mystery \times s^{e})^{d} \equiv m \times s \ (\text{mod}\ n)
$$
So by multiplying the known ciphertext by $s$ to the power $e$, we control how the decrypted value changes without knowing $d$. The oracle always preserves the bottom 128 bits of $p = c$ to the power $d$ mod $n$. In particular, it reveals the least significant bit $p \ \&\ 1$ (the parity of $p$) exactly.
For RSA moduli $n$ (odd), if we choose $s = 2$ to the power $i$ then:
$$
p_i = \left( mystery \times (2^{i})^{e} \right)^{d} \equiv 2^{i} \times m \ (\text{mod}\ n)
$$
Because $2$ to the power $i$ multiplied by $m$ equals $n$ multiplied by
$$
\text{floor} \left( \frac{2^{i} \times m}{n} \right)
$$
together with the remainder $2^{i} \times m \bmod n$, and $2^{i} \times m$ is even for $i \ge 1$ while $n$ is odd, we get:
$$
\text{parity}(p_i) = \text{parity} \left( (2^{i} \times m) - n \times \text{floor} \left( \frac{2^{i} \times m}{n} \right) \right)
$$
$$
= \text{parity} \left( -n \times \text{floor} \left( \frac{2^{i} \times m}{n} \right) \right)
$$
$$
= \text{parity} \left( \text{floor} \left( \frac{2^{i} \times m}{n} \right) \right)
$$
So the LSB tells us the parity of the integer:
$$
\text{floor} \left( \frac{2^{i} \times m}{n} \right)
$$
This is the classic parity (LSB) oracle for RSA: each query reveals one bit of information that allows us to halve the interval containing the unknown ratio $m/n$. I used a bisection attack on $m/n$ using only parity to retrieve the flag.
## Solver
```python
#!/usr/bin/env python3
from pwn import *
from fractions import Fraction
import re, math
context.log_level = 'debug'
host, port = "nc 52.77.234.0 20256".split(" ")[1:3]
e = 65537
def parse(io):
b = b""
b += io.recvuntil(b"mystery:"); b += io.recvline()
b += io.recvuntil(b"n:") ; b += io.recvline()
b += io.recvuntil(b"(1|2|3): ")
c = int(re.search(rb"mystery:\s*([0-9]+)", b).group(1))
n = int(re.search(rb"n:\s*([0-9]+)", b).group(1))
return c, n
def parity_oracle(io, payment: int) -> int:
io.sendline(b"2")
io.recvuntil(b"payment: ")
io.sendline(str(payment).encode())
while True:
line = io.recvline(timeout=20)
if not line: raise EOFError("server closed")
if b"(whisper):" in line:
v = int(line.split(b":", 1)[1].strip())
return v & 1 # lsb
if b"(1|2|3):" in line:
payment += 1
io.sendline(b"2")
io.recvuntil(b"payment: ")
io.sendline(str(payment).encode())
io = remote(host, port)
c, n = parse(io)
mystery = c
g = pow(2, e, n) # g = (2 ** e) % n
# interval for m/n (as rationals)
L, U = Fraction(0), Fraction(1)
steps = n.bit_length() + 4
for _ in range(steps):
c = (c * g) % n
p = parity_oracle(io, c) # parity of decrypted value
mid = (L + U) / 2
if p == 0: # even => value < n/2 => keep lower half
U = mid
else: # odd => value >= n/2 => keep upper half
L = mid
m = math.floor(U * n)
for cand in (m-2, m-1, m, m+1, m+2):
if pow(cand, e, n) == mystery:
m = cand
break
flag = m.to_bytes((m.bit_length() + 7)//8, "big")
print(flag)
io.close()
```
# Not So Simple RSA
Given `chal.py` and `output.txt` which is the output of the flag after the `chal.py` was run by the problem setter with the flag variable defined by him.
## chall.py
```python
import random
import gmpy2
import hashlib
def find_p(e: int, bits: int, max_attempts=1_000_000):
low_k = (1 << (bits - 1)) - 1
low_k = (low_k // e) + 1
high_k = (1 << bits) - 1
high_k = high_k // e
if low_k > high_k:
raise ValueError("Impossible: parameters give no k range")
k = random.randrange(low_k, high_k + 1)
for attempt in range(max_attempts):
p = k * e + 1
if p.bit_length() != bits:
k = low_k + ((k - low_k + 1) % (high_k - low_k + 1))
continue
if gmpy2.is_prime(p):
return int(p), int(k)
k += 1
if k > high_k:
k = low_k
raise RuntimeError(f"Failed to find p in {max_attempts} attempts")
def find_q_or_r(bits: int, e: int, max_attempts=10000):
lower = 1 << (bits - 1)
upper = (1 << bits) - 1
for _ in range(max_attempts):
q = gmpy2.next_prime(random.randrange(lower, upper))
if (q - 1) % e != 0:
return int(q)
raise RuntimeError("Failed to find q with (q-1)%e != 0 in budget")
def generate_challenge():
e = int(gmpy2.next_prime(2**28))
bits_p = 1024//3
bits_q = 1024//3
bits_r = 1024//3
p, k = find_p(e, bits_p)
q = find_q_or_r(bits_q, e)
r = find_q_or_r(bits_r, e)
n = p * q * r
phi_n = (p - 1) * (q - 1) * (r - 1)
subset_length = 40
max_value = phi_n // (subset_length // 2)
min_value = max_value // 100
values = []
solution_indices = set()
num_in_solution = random.randint(subset_length // 3, 2 * subset_length // 3)
solution_indices = set(random.sample(range(subset_length), num_in_solution))
remaining = phi_n
solution_list = sorted(list(solution_indices))
for i in range(subset_length):
if i in solution_indices:
if i == solution_list[-1]:
val = remaining
else:
num_remaining = len(solution_list) - solution_list.index(i)
max_for_this = remaining // num_remaining
val = random.randint(min_value, min(max_value, max_for_this))
remaining -= val
else:
val = random.randint(min_value, max_value)
values.append(val)
combined = list(zip(values, [1 if i in solution_indices else 0 for i in range(subset_length)]))
random.shuffle(combined)
values, solution = zip(*combined)
values = list(values)
solution = list(solution)
subset_sum = sum(v * s for v, s in zip(values, solution))
if subset_sum != phi_n:
diff = phi_n - subset_sum
for i in range(len(values)):
if solution[i] == 1:
values[i] += diff
break
moduli = [1000000007, 1000000009, 1000000021]
m = int.from_bytes(b"REDACTED_FLAG", "big")
c = pow(m, e, n)
print("n =", n)
print("e =", e)
print("e =", e)
print("values =", values)
print("size =", sum(solution))
print("phi_modular =", [(m, phi_n % m) for m in moduli])
print("phi_bits_high =", hex(phi_n >> (phi_n.bit_length() - 128)))
print("phi_bits_low =", hex(phi_n & ((1 << 128) - 1)))
print("verification_hash =", hashlib.sha256(str(phi_n).encode()).hexdigest())
if __name__ == "__main__":
generate_challenge()
```
## output.txt
```python
n = 60419902565764548844188543053799539736520575597932824532389761522643875892236763090936952699801022241009608452637384156029134178007050986959672545796812659544119079405754458335003514178145056915824767178945504412120793435627631704573586996782481630193258573823429410349772037605005907442534016230552638558203
e = 268435459
c = 42077426242195692288259542826753875723706187537047968345077398360129407326191750134323576198720474598541102760396899177709744067388778715704602945081394301040443564303932191107115332093409897959823980390797003657503917523358293660420758330312005347193969217945630493348089893460949825739139342103857726182647
values = [2006121808675033655629912205539451731968788048689055659997112288437921349871706616002370887120200272996176639502330512162087050079360893814704031582967569895118118013898018846387830801348517233180122509405830333820662044128151568318688530795042907395181846553870038715532769117226055221064455551490950410774, 732828375666091792035482464097098683081812325032273526754649019175538590561093891163942860721380022094311226260495976886071736080266650350355174200287631871127070124310732575730594810294112385558803754155074092119958373224323895618603355556955287554755519430206474930206279761890888936446145908613396143934, 532889160593473743158032230072735506005255409608069924504987746744938724818092572883460758004024799244096357677865546298528380398704360328635766829721484968015359353975907368728049568484129428576888199179017490661469115249897516263106048466929168405153122393852178479766668792505486780351734593310079320492, 1030264944408296642185556806491437633124025784602025323877006239522425666584766787922950566607522476893455386830554318666181265558244795659553367390633368065461281537186487340676370434121708201979771321791483650758940333329922611156326460165069909758107226376956121274429040707249960854172406330587994294353, 1335896378626534116986459113203290907572858006074102489413845619865986503384086403066246181138448587861431155916589465622667329499004866346710929883867591407340148859951242422352314889562357995469976289283945444026336324649156092316269445890379712677685628144872391464438193695231700003689558464947545067862, 1733337624422861630058816559767634943911487910943519314346202359909202958359957209774602445258433905173361042937888576917072110945871100270554564438327802223819475266679080707493942230613200968395790589197363352087794570880816625087046308981864482123285598860327188020623406125595477139463653980548341669393, 1712118521984373787984190214471893185899626741865136138457076334613025444431770957054892731372950299543941807442598680965448418792367431719332565016121291887805587417326073046959962924819635595643129218281051906400369743947301197574027760510525488628454401113736351471859327651680706188693681925199887487263, 1499735939960529860036928790576639812556654726793121787648367519328260934859008521579568361171641038091567842656853405473313800616130546203262540417551043440628247542775260266483441253985140025395290342730935784277120212893520390114470744811836532151844893966210338552670399770776545942069954713172366751354, 1913607523649527314705197237356999006414033820957149969404326981075572004246375366088602616980833189335395867234004310860320300824419040902138319156508878409141834481748369822406214632656504561469132609528061013752179827379079963934388552439087369413481257942606586453435714157061142217876959859484703177907, 26534797870276653852900122929036730877138814935286353786516964807939373038909235889043220230276055509158798892611176229823627440457599507963947042723857916618002680578678158045432064576712385822197972859101120055120293609893483670245242427874608988509274231221368812818485481079452384538691805599778452564528, 2163879814490791191142637542952198904137191495088175137999784482950200139352923732282737897683289098041082685772697632200453475228184661538056464673939140597669257561521106307793756891507120965722865224017052438804843260511235759572961618156868424037244036412612217711880125692833996353284835121958890493404, 2267797909614375525177596920022706441678332927021309551762061692437948198914328107460765986576474869689782807793535342716587087883230359861578783484673165869485942694243252438709061405022590279573487469882240648498613779331593505112588177642816410319434153199783076342198162552767827391907508848457206335434, 2257873971918662586355251641685854523138098623719692377104551938617631229736984651428301172660578587083528331182055750521207663613194978599474415304848209608983919864270292827671337872078286455643654566282933694206490937840392768431053129365259113765114206135166276387468316236530006800000231209826291861813, 394228353826392440284155018623206752379851301703655698141381529417397582775642198320659388233500243975584591683636719142301324444974101655759137692947637420775809443486337083243354769811657717651468168172441758392019863595924159031443822992716153917678054285570494586890596947227541216007648902886193332045, 1340312858171251060540574107472764544434572510310285384150564143136675036273927394913038217291370145557326975629261980462070547749669063792111974018224012606560634330297287049879887776882312936149939187151451738470273674008009270272948667540728858515883248846131115317191092605091645119772730608269047361618, 2619779902953282128243808782556463430170203648957681464775952445478269257099778352730144013337891943200335585462882767390240104010467069391727419665311309494704645350127371412478143121071465675314231910213427154236157478037775541293424798959225083965741092451656020204969780065767598830666393422165676083306, 1585808686745266881665668161447359413626732092473994604224812585387873398900715405233299083720399218441383266250402142673313956965421484920085981706340554293882691270878738828946639882142942653855807423720129058519944764858050743267930455181191175813334951913635442779241748517513919704501100921077733140416, 2818129461302877093027126464636730451885368102579325558630221030887230415294829869915866092137101788362338048332271147163903350711745993438814370874454291348480865221685615864328933475128360613552133262158753117578808025052586884129775612187024993730501801946902655061721082663208174182984189344997107158750, 1054407176599413787166398792292140295757940801679843054045887733053629199922657731014478061123773877561515598540056428056503561220354303615466483445852272544243755817903159065670989035959000677838201255601373918523037864395508991250918462164851394849818466093498965213465981168413433018716771202139663336228, 1338810440859849583467944323254056262731332563952140448343236534355682429588990169650547948327093998548990270212556607458393207631044785054012839926459715577634172470071268283912521886343746137763979907723928040263845656671180203524135887394471067141940892753984934748261196469611794356291556093620778244162, 2472499912476914517399274422036557205633428334583173335296564652270378142366825998058745495516160543621597127995280514556912849068652840324321633028654677610467794632900856529494191769954356614780740431563974390141324910466161728273418144612636820742914683911827230419884786016178041942595369934975670968791, 2743686548924733730740944092306868198727468405427576785739348929998779106784831331674845961268529437794178797480350514071524096857342210851935354954327692066701718547233301490192495278552958496491674510762194923592625077348859903411489987431960772977862930716353433899302769525241793801142127919782987843255, 2574559817199801908424116008094318451838088049594702267200851759127422903511714293952238014714750752457052382141972394360952181692361422399589663194329530351195346936761837754366616179270825540992265020567857767446551449249673062177371241850026020596275177768411357378286844788747829883032947952440286351020, 2706150821408267359841777068547710009348261984503186825318970607545907141578566006827403867360014141015171247975423370455794376885219889812010844858397110342594537140647188529710784352970491346019562272647192352372120551675413538057894757032214607027654992879687604742917484317056119133742357476603853001875, 1575222739086124202848070409742501093606055299693574123527293510619898520382728501334200102949437881936442231797976105718815603116761097215345747692286535420003141586589468225962932368926432467798910201327430889664756562747656619750862228652805337862518080721003987670356250705244525422049678847324918360345, 2296899187515959856682476463368411513164435438881598932288378431928557566342457066038509873722394968012502011510386865714416050544467011808612915772490457008871651141904708931366689314018934248270214019030206585181920575656027405651330155821614772732070724413122790860776692558729027259205647521262391789431, 618120550943427568042108853048928540406977929265292788929929232302673817538717718841254184771332277674433690803062512342709882726046535423509981778933076304102089834170781341133093250230757093921679842642253202858591286467194592193096463005177846707455419911946279009074468290528936157716103446017482479494, 2339160651886900591925623314001320481479073145553725509276306736737592699671185794594354569001993336056950864571821823129519206454618724536329202239951035386788357861663854970373018424983048237571688157895622009605082095330898134475482151306114866504942723953658112098168344124301956889573038069638671649584, 1787980697494771636063550532501107133030634631988974664974878114274511623053333303192703636444818653428345753887964019505612940881649800230905993342591138724533649233729369769535041048810844018706578315680030300052049943551621170026630841326363235251829117483929241725158104348343432260896042382577829688820, 417232524642445833843022621759007851468233549329897105246515833316757168925063387485331898800350393755694412761807955173725192932454006437958359609761209304289198341844853177830754415746222657817653115246753374340963275630932785162437778654527440578826876079554917301377922692446723918683271569955366442932, 1226489912213405655462825393585268481453124851498443282263759667409965163057624770363280089714871815596458671927102222887133987147461511243720363782767703015987411863706007673819998360558875758819348917416037785505659154640681364782316505917924414689731627028282309439591838178765814370579154997589950490573, 256111103981007551621677927829150614847290304466898859214333968724310379610402472083333264703578978763839759864394945385482115951764054572839204578891682271123051926402863909504442241018004258096490921445020452850412802600910090701089006447875715092717066115688298703080167139068242520413663166172247437997, 1718245258750852164670726725851519706399409559243640348091925977305688377573217461677440183495614711049705876318403403470938246132605222655150838637757016990172276538325952737283386384020449278260953395546420360692736251080405720501888527032382109981745279859584229383699507768528391913759030379675258783988, 105943004880333425615219901114283767701285111222501951601869975713322570920808124928559708613506711289143478445291227272883771549808909408473604057062780859260674234297248476627998590151388553470525248145026184624335729337214061383853094209051557077123876926829070973097603725534471972555512401585492216313, 1898724734343173094623662462148875382445097098880752001277864245286518187958263813789429447326782932651787998184847478149724128903635881073576527363403807241028287772273848512742894401639165220611722192239823984196630998904363650165103297124148253651606192852122245968463990830486981130570543343949648112139, 2587346975779885222612311889303881203206492747880508308420612731171850299406149775439023266596164860827086419698723475567067494628491222771314678042977241305516099834266701586385092690332562368268571193475607449262234494088523126229103753634136837937825238247518713243158644237945578351670768822288563937966, 2982041317246555112019664170454157759070309038214474509651562930181281589092030966060940190658848623233065655586494541321335755593065397549889309281596581539274251811164623055592603958594868116433245094560247537917911332759480920023089651692752381003796372790674128918800696211835991097418218212283762775208, 116703490885819703040500404265324782952304908687795473326935079637396611215134894675403609519711933598746452760352967180851327435292507625901248507533663492324426703446040748392413051573100306606527311831431480790135110568664510947551072761257904891241777388261834808856928902039659188690398438757067118549, 2755792470545369426645727938300512676365665051378704840733954601949693231010297975191298544786648533669876094486417460391873642025287697696994036525998531994367091474834868572289273847172323815098220119938769618494219451120173048760931334098453337815146485640655322484484340447816159306814188466386939437679, 443002664753715531972806486205089772634968518652989474506731159534967469758026320212794178326884071398682826364159425383042562980682387350170279880348871299411597684292427178702410274926298601966944046998106907689449758464027091517805285734443165218231288449618326236983827367861763131251970826346026472351]
size = 22
phi_modular = [[1000000007, 178665113], [1000000009, 220473329], [1000000021, 600707014]]
phi_bits_high_128 = 0xac14e3612f4408f33f6cb42a74deba17
phi_bits_low_128 = 0x6f7e9819bf986d14ec1471514d302f40
verification_hash = 3b4da3d329e974b94561514dd5740335a4c05933723a337259c24117a13b8aba
```
Given an RSA challenge, the generator picks a large prime exponent e near two to the power of twenty-eight. It then builds a triple modulus of 1023 bits n equal to p × q × r where each factor has 341 bits. The prime p is chosen so that p − 1 is divisible by e exactly once, while q and r are chosen so that neither q − 1 nor r − 1 has e as a factor.
## Factoring $n$ from a Multiset of Values
We are given a multiset of forty values that can be combined to reconstruct $\varphi(n)$.
The approach I used is a **meet-in-the-middle attack** ([this is the paper reference](https://drops.dagstuhl.de/storage/00lipics/lipics-vol275-approx-random2023/LIPIcs.APPROX-RANDOM.2023.39/LIPIcs.APPROX-RANDOM.2023.39.pdf)).
### Meet-in-the-Middle Reconstruction of $\varphi(n)$
1. **Split the forty values** into two halves of twenty values each.
2. For each half, compute all partial sums for every possible subset size, and for each sum store four fingerprints instead of the raw sum: the residues modulo each of three small moduli, and the low 64 bits of the sum.
3. **Join the two tables** by finding pairs of sums whose combined fingerprints match the public targets for $\varphi(n)$.
This produces the candidate for $\varphi(n)$.
### Exploiting the Structure of $e$
Given that $e$ is prime, we define:
$$
D = \frac{\varphi(n)}{e}
$$
We then pick a random $a$ from the multiplicative group modulo $n$ and compute:
$$
x = a^{D} \bmod n
$$
### Why This Works?
Notice that:
* $e \mid (p - 1)$
* $e \nmid (q - 1)$ and $e \nmid (r - 1)$
This means:
* Raising $a$ to $D$ **wipes out** the $q$ and $r$ components (so $x \equiv 1 \ (\text{mod}\ q)$ and $x \equiv 1 \ (\text{mod}\ r)$).
* However, $x \not\equiv 1 \ (\text{mod}\ p)$ in general.
Therefore:
$$
x - 1 \quad\text{shares the factors}\quad q \times r \quad\text{with}\quad n
$$
### Extracting the Factors
We compute:
$$
g = \gcd(x - 1, n)
$$
With high probability, $g = q \times r$.
From here:
* $p = \frac{n}{g}$
* We can also confirm $p$ as the unique prime factor such that $p - 1 \mid \varphi(n)$.
### Recovering $q$ and $r$
Let:
$$
n_1 = q \times r
$$
$$
\varphi_1 = (q - 1)(r - 1)
$$
From $\varphi_1$, we can compute:
$$
S = q + r = n_1 - \varphi_1 + 1
$$
We solve the quadratic equation:
$$
t^{2} - S t + n_1 = 0
$$
The two roots of this equation are $q$ and $r$.
## factorize.py
```python
#!/usr/bin/env python3
from pwn import *
import gmpy2
from hashlib import sha256
from math import prod
import random
n = 60419902565764548844188543053799539736520575597932824532389761522643875892236763090936952699801022241009608452637384156029134178007050986959672545796812659544119079405754458335003514178145056915824767178945504412120793435627631704573586996782481630193258573823429410349772037605005907442534016230552638558203
e = 268435459
c = 42077426242195692288259542826753875723706187537047968345077398360129407326191750134323576198720474598541102760396899177709744067388778715704602945081394301040443564303932191107115332093409897959823980390797003657503917523358293660420758330312005347193969217945630493348089893460949825739139342103857726182647
values = [2006121808675033655629912205539451731968788048689055659997112288437921349871706616002370887120200272996176639502330512162087050079360893814704031582967569895118118013898018846387830801348517233180122509405830333820662044128151568318688530795042907395181846553870038715532769117226055221064455551490950410774, 732828375666091792035482464097098683081812325032273526754649019175538590561093891163942860721380022094311226260495976886071736080266650350355174200287631871127070124310732575730594810294112385558803754155074092119958373224323895618603355556955287554755519430206474930206279761890888936446145908613396143934, 532889160593473743158032230072735506005255409608069924504987746744938724818092572883460758004024799244096357677865546298528380398704360328635766829721484968015359353975907368728049568484129428576888199179017490661469115249897516263106048466929168405153122393852178479766668792505486780351734593310079320492, 1030264944408296642185556806491437633124025784602025323877006239522425666584766787922950566607522476893455386830554318666181265558244795659553367390633368065461281537186487340676370434121708201979771321791483650758940333329922611156326460165069909758107226376956121274429040707249960854172406330587994294353, 1335896378626534116986459113203290907572858006074102489413845619865986503384086403066246181138448587861431155916589465622667329499004866346710929883867591407340148859951242422352314889562357995469976289283945444026336324649156092316269445890379712677685628144872391464438193695231700003689558464947545067862, 1733337624422861630058816559767634943911487910943519314346202359909202958359957209774602445258433905173361042937888576917072110945871100270554564438327802223819475266679080707493942230613200968395790589197363352087794570880816625087046308981864482123285598860327188020623406125595477139463653980548341669393, 1712118521984373787984190214471893185899626741865136138457076334613025444431770957054892731372950299543941807442598680965448418792367431719332565016121291887805587417326073046959962924819635595643129218281051906400369743947301197574027760510525488628454401113736351471859327651680706188693681925199887487263, 1499735939960529860036928790576639812556654726793121787648367519328260934859008521579568361171641038091567842656853405473313800616130546203262540417551043440628247542775260266483441253985140025395290342730935784277120212893520390114470744811836532151844893966210338552670399770776545942069954713172366751354, 1913607523649527314705197237356999006414033820957149969404326981075572004246375366088602616980833189335395867234004310860320300824419040902138319156508878409141834481748369822406214632656504561469132609528061013752179827379079963934388552439087369413481257942606586453435714157061142217876959859484703177907, 26534797870276653852900122929036730877138814935286353786516964807939373038909235889043220230276055509158798892611176229823627440457599507963947042723857916618002680578678158045432064576712385822197972859101120055120293609893483670245242427874608988509274231221368812818485481079452384538691805599778452564528, 2163879814490791191142637542952198904137191495088175137999784482950200139352923732282737897683289098041082685772697632200453475228184661538056464673939140597669257561521106307793756891507120965722865224017052438804843260511235759572961618156868424037244036412612217711880125692833996353284835121958890493404, 2267797909614375525177596920022706441678332927021309551762061692437948198914328107460765986576474869689782807793535342716587087883230359861578783484673165869485942694243252438709061405022590279573487469882240648498613779331593505112588177642816410319434153199783076342198162552767827391907508848457206335434, 2257873971918662586355251641685854523138098623719692377104551938617631229736984651428301172660578587083528331182055750521207663613194978599474415304848209608983919864270292827671337872078286455643654566282933694206490937840392768431053129365259113765114206135166276387468316236530006800000231209826291861813, 394228353826392440284155018623206752379851301703655698141381529417397582775642198320659388233500243975584591683636719142301324444974101655759137692947637420775809443486337083243354769811657717651468168172441758392019863595924159031443822992716153917678054285570494586890596947227541216007648902886193332045, 1340312858171251060540574107472764544434572510310285384150564143136675036273927394913038217291370145557326975629261980462070547749669063792111974018224012606560634330297287049879887776882312936149939187151451738470273674008009270272948667540728858515883248846131115317191092605091645119772730608269047361618, 2619779902953282128243808782556463430170203648957681464775952445478269257099778352730144013337891943200335585462882767390240104010467069391727419665311309494704645350127371412478143121071465675314231910213427154236157478037775541293424798959225083965741092451656020204969780065767598830666393422165676083306, 1585808686745266881665668161447359413626732092473994604224812585387873398900715405233299083720399218441383266250402142673313956965421484920085981706340554293882691270878738828946639882142942653855807423720129058519944764858050743267930455181191175813334951913635442779241748517513919704501100921077733140416, 2818129461302877093027126464636730451885368102579325558630221030887230415294829869915866092137101788362338048332271147163903350711745993438814370874454291348480865221685615864328933475128360613552133262158753117578808025052586884129775612187024993730501801946902655061721082663208174182984189344997107158750, 1054407176599413787166398792292140295757940801679843054045887733053629199922657731014478061123773877561515598540056428056503561220354303615466483445852272544243755817903159065670989035959000677838201255601373918523037864395508991250918462164851394849818466093498965213465981168413433018716771202139663336228, 1338810440859849583467944323254056262731332563952140448343236534355682429588990169650547948327093998548990270212556607458393207631044785054012839926459715577634172470071268283912521886343746137763979907723928040263845656671180203524135887394471067141940892753984934748261196469611794356291556093620778244162, 2472499912476914517399274422036557205633428334583173335296564652270378142366825998058745495516160543621597127995280514556912849068652840324321633028654677610467794632900856529494191769954356614780740431563974390141324910466161728273418144612636820742914683911827230419884786016178041942595369934975670968791, 2743686548924733730740944092306868198727468405427576785739348929998779106784831331674845961268529437794178797480350514071524096857342210851935354954327692066701718547233301490192495278552958496491674510762194923592625077348859903411489987431960772977862930716353433899302769525241793801142127919782987843255, 2574559817199801908424116008094318451838088049594702267200851759127422903511714293952238014714750752457052382141972394360952181692361422399589663194329530351195346936761837754366616179270825540992265020567857767446551449249673062177371241850026020596275177768411357378286844788747829883032947952440286351020, 2706150821408267359841777068547710009348261984503186825318970607545907141578566006827403867360014141015171247975423370455794376885219889812010844858397110342594537140647188529710784352970491346019562272647192352372120551675413538057894757032214607027654992879687604742917484317056119133742357476603853001875, 1575222739086124202848070409742501093606055299693574123527293510619898520382728501334200102949437881936442231797976105718815603116761097215345747692286535420003141586589468225962932368926432467798910201327430889664756562747656619750862228652805337862518080721003987670356250705244525422049678847324918360345, 2296899187515959856682476463368411513164435438881598932288378431928557566342457066038509873722394968012502011510386865714416050544467011808612915772490457008871651141904708931366689314018934248270214019030206585181920575656027405651330155821614772732070724413122790860776692558729027259205647521262391789431, 618120550943427568042108853048928540406977929265292788929929232302673817538717718841254184771332277674433690803062512342709882726046535423509981778933076304102089834170781341133093250230757093921679842642253202858591286467194592193096463005177846707455419911946279009074468290528936157716103446017482479494, 2339160651886900591925623314001320481479073145553725509276306736737592699671185794594354569001993336056950864571821823129519206454618724536329202239951035386788357861663854970373018424983048237571688157895622009605082095330898134475482151306114866504942723953658112098168344124301956889573038069638671649584, 1787980697494771636063550532501107133030634631988974664974878114274511623053333303192703636444818653428345753887964019505612940881649800230905993342591138724533649233729369769535041048810844018706578315680030300052049943551621170026630841326363235251829117483929241725158104348343432260896042382577829688820, 417232524642445833843022621759007851468233549329897105246515833316757168925063387485331898800350393755694412761807955173725192932454006437958359609761209304289198341844853177830754415746222657817653115246753374340963275630932785162437778654527440578826876079554917301377922692446723918683271569955366442932, 1226489912213405655462825393585268481453124851498443282263759667409965163057624770363280089714871815596458671927102222887133987147461511243720363782767703015987411863706007673819998360558875758819348917416037785505659154640681364782316505917924414689731627028282309439591838178765814370579154997589950490573, 256111103981007551621677927829150614847290304466898859214333968724310379610402472083333264703578978763839759864394945385482115951764054572839204578891682271123051926402863909504442241018004258096490921445020452850412802600910090701089006447875715092717066115688298703080167139068242520413663166172247437997, 1718245258750852164670726725851519706399409559243640348091925977305688377573217461677440183495614711049705876318403403470938246132605222655150838637757016990172276538325952737283386384020449278260953395546420360692736251080405720501888527032382109981745279859584229383699507768528391913759030379675258783988, 105943004880333425615219901114283767701285111222501951601869975713322570920808124928559708613506711289143478445291227272883771549808909408473604057062780859260674234297248476627998590151388553470525248145026184624335729337214061383853094209051557077123876926829070973097603725534471972555512401585492216313, 1898724734343173094623662462148875382445097098880752001277864245286518187958263813789429447326782932651787998184847478149724128903635881073576527363403807241028287772273848512742894401639165220611722192239823984196630998904363650165103297124148253651606192852122245968463990830486981130570543343949648112139, 2587346975779885222612311889303881203206492747880508308420612731171850299406149775439023266596164860827086419698723475567067494628491222771314678042977241305516099834266701586385092690332562368268571193475607449262234494088523126229103753634136837937825238247518713243158644237945578351670768822288563937966, 2982041317246555112019664170454157759070309038214474509651562930181281589092030966060940190658848623233065655586494541321335755593065397549889309281596581539274251811164623055592603958594868116433245094560247537917911332759480920023089651692752381003796372790674128918800696211835991097418218212283762775208, 116703490885819703040500404265324782952304908687795473326935079637396611215134894675403609519711933598746452760352967180851327435292507625901248507533663492324426703446040748392413051573100306606527311831431480790135110568664510947551072761257904891241777388261834808856928902039659188690398438757067118549, 2755792470545369426645727938300512676365665051378704840733954601949693231010297975191298544786648533669876094486417460391873642025287697696994036525998531994367091474834868572289273847172323815098220119938769618494219451120173048760931334098453337815146485640655322484484340447816159306814188466386939437679, 443002664753715531972806486205089772634968518652989474506731159534967469758026320212794178326884071398682826364159425383042562980682387350170279880348871299411597684292427178702410274926298601966944046998106907689449758464027091517805285734443165218231288449618326236983827367861763131251970826346026472351]
size = 22
phi_mods = [[1000000007, 178665113], [1000000009, 220473329], [1000000021, 600707014]]
phi_hi = int("ac14e3612f4408f33f6cb42a74deba17", 16)
phi_lo = int("6f7e9819bf986d14ec1471514d302f40", 16)
phi_sha = "3b4da3d329e974b94561514dd5740335a4c05933723a337259c24117a13b8aba"
import random
import time
import math
import gmpy2
from hashlib import sha256
from array import array
import random
def reconstruct_phi(values, size, phi_mods, phi_hi, phi_lo, phi_sha):
"""
Meet-in-the-middle with strong pruning:
- residues modulo 3 small moduli
- low 64 bits
"""
(m1, r1), (m2, r2), (m3, r3) = [(int(m), int(r)) for (m, r) in phi_mods]
MASK64 = (1 << 64) - 1
vals = []
for v in values:
v = int(v)
vals.append((v, v % m1, v % m2, v % m3, v & MASK64))
half = len(vals) // 2
L, R = vals[:half], vals[half:]
# mapsL[c][(m1,m2,m3,low64)] = sum
mapsL = [dict() for _ in range(half + 1)]
mapsL[0][(0, 0, 0, 0)] = 0
for v, vm1, vm2, vm3, vl in L:
for c in range(half - 1, -1, -1):
dct = mapsL[c]
if not dct:
continue
nd = mapsL[c + 1]
for (a1, a2, a3, a64), s in dct.items():
k = ((a1 + vm1) % m1, (a2 + vm2) % m2, (a3 + vm3) % m3, (a64 + vl) & MASK64)
if k not in nd:
nd[k] = s + v
mapsR = [dict() for _ in range(len(R) + 1)]
mapsR[0][(0, 0, 0, 0)] = 0
for v, vm1, vm2, vm3, vl in R:
for c in range(len(R) - 1, -1, -1):
dct = mapsR[c]
if not dct:
continue
nd = mapsR[c + 1]
for (a1, a2, a3, a64), s in dct.items():
k = ((a1 + vm1) % m1, (a2 + vm2) % m2, (a3 + vm3) % m3, (a64 + vl) & MASK64)
if k not in nd:
nd[k] = s + v
# join
for cR in range(0, min(len(R), size) + 1):
cL = size - cR
if cL < 0 or cL > half:
continue
left = mapsL[cL]
if not left:
continue
right = mapsR[cR]
for (b1, b2, b3, b64), sR in right.items():
need = ((r1 - b1) % m1, (r2 - b2) % m2, (r3 - b3) % m3, (phi_lo - b64) & MASK64)
sL = left.get(need)
if sL is None:
continue
phi = sL + sR
return int(phi)
# random-base order attack
def random_base_factor(n: int, e: int, phi: int, tries: int = 32) -> int:
"""
Try random a in Z_n* and compute g = gcd(a^{phi/e} - 1, n).
With overwhelming prob, g = q*r (nontrivial). Return g.
"""
D = phi // e
for _ in range(tries):
a = random.randrange(2, n - 1)
if gmpy2.gcd(a, n) != 1:
continue
x = int(gmpy2.powmod(a, D, n))
g = int(gmpy2.gcd(x - 1, n))
if 1 < g < n:
return g
def recover_qr(n: int, p: int, phi: int):
n1 = n // p
phi_n1 = phi // (p - 1) # = (q-1)(r-1)
S = n1 - phi_n1 + 1 # = q + r
disc = S * S - 4 * n1
D = gmpy2.isqrt(disc)
q = (S + D) // 2
r = (S - D) // 2
return int(q), int(r)
phi = reconstruct_phi(values, size, phi_mods, phi_hi, phi_lo, phi_sha)
log.info(f"φ(n) = {phi}")
assert phi % e == 0, "φ(n) must be divisible by e"
g = random_base_factor(n, e, phi, tries=64)
cand1, cand2 = int(g), int(n // g)
# p is the one with φ % (p-1) == 0
choose = []
for cand in (cand1, cand2):
if 1 < cand < n and phi % (cand - 1) == 0 and gmpy2.is_prime(cand):
choose.append(cand)
p = int(choose[0])
q, r = recover_qr(n, p, phi)
log.info(f"p = {p}")
log.info(f"q = {q}")
log.info(f"r = {r}")
```
## Recovering the Plaintext with Shumow’s Special Case
After obtaining the prime factors $p, q, r$, the challenge falls under the **single affected prime** structure:
* $e \mid (p - 1)$
* $e$ is coprime to $q - 1$ and $r - 1$
This matches **Shumow’s special case** ([this is the paper reference](https://eprint.iacr.org/2020/1059)), where:
$$
\gcd\left( \frac{\varphi(N)}{e}, e \right) = 1
$$
$$
\varphi(N) = (p - 1)(q - 1)(r - 1)
$$
---
### Reduced Totient and Inverse Exponent
We compute:
$$
\tilde{\varphi} = \frac{\varphi(N)}{e}
$$
and confirm $\gcd(\tilde{\varphi}, e) = 1$.
Then:
$$
d = e^{-1} \bmod \tilde{\varphi}
$$
---
### Roots Per Prime
From the ciphertext $c$:
* **Modulo $p$**:
Since $e \mid (p - 1)$, the $e$-th roots are not unique:
$$
a_p = c^{d} \bmod p
$$
* **Modulo $q$ and $r$**:
Since $e$ is coprime to $q - 1$ and $r - 1$, the $e$-th root is unique:
$$
a_q = c^{e^{-1} \bmod (q - 1)} \bmod q
$$
$$
a_r = c^{e^{-1} \bmod (r - 1)} \bmod r
$$
---
### Generator of Exact Order $e$ (mod $p$)
Find $g_E$ such that:
$$
g_E = g^{\tilde{\varphi}} \bmod p
$$
with:
$$
g_E^e \equiv 1 \ (\bmod\ p) \quad\text{and}\quad g_E \not\equiv 1 \ (\bmod\ p)
$$
This gives a generator of the subgroup of order $e$ modulo $p$.
---
### Enumerating Candidates
Given an initial exponent $i$ such that $a_p \cdot g_E^i$ is a promising candidate start point, iterate $k$ from $i$ to $e-1$:
1. Compute:
$$
m_p = a_p \cdot g_E^k \bmod p
$$
2. Use **CRT** to combine:
$$
m_k = \text{CRT}(m_p, a_q, a_r)
$$
3. Check if it starts with `ITSEC{}`
## Solver
```python
#!/usr/bin/env python3
import math
from hashlib import sha256
from tqdm import tqdm
N = 60419902565764548844188543053799539736520575597932824532389761522643875892236763090936952699801022241009608452637384156029134178007050986959672545796812659544119079405754458335003514178145056915824767178945504412120793435627631704573586996782481630193258573823429410349772037605005907442534016230552638558203
e = 268435459
c = 42077426242195692288259542826753875723706187537047968345077398360129407326191750134323576198720474598541102760396899177709744067388778715704602945081394301040443564303932191107115332093409897959823980390797003657503917523358293660420758330312005347193969217945630493348089893460949825739139342103857726182647
p = 4466054086694205224060229493741618510822562767362299820045196957222381007815796096595501338871401718569
q = 4230817059039673574688898677053507572161261199083369921571579034080470278052948429785264270802981855581
r = 3197656400540271876542568319421192210490384740990543931526314714177621097079511045918579371468320101727
phi = 60419902565764548844188543053799539736520575597932824532389761522643875892236763090936952699801022240962903789136974518188761097556289389575127026002954879057305475324383545234245465589206481151570914285906250106656186512023735391121198807841933514848680339770734949294557341480916358076784744828741530693440
def crt3(mp, mq, mr, p, q, r):
N = p*q*r
Np, Nq, Nr = N//p, N//q, N//r
return (mp*pow(Np,-1,p)*Np + mq*pow(Nq,-1,q)*Nq + mr*pow(Nr,-1,r)*Nr) % N
phi = (p-1)*(q-1)*(r-1)
phi_red = phi // e
assert phi % e == 0 and math.gcd(phi_red, e) == 1
# find element of exact order e mod p
g = 1
while True:
g += 1
gE_p = pow(g, phi_red, p)
if gE_p != 1 and pow(gE_p, e, p) == 1:
break
# roots per-prime
d = pow(e, -1, phi_red) # inverse modulo phi/e
a_p = pow(c, d, p) # one of the e roots mod p
a_q = pow(c, pow(e, -1, q-1), q) # unique root mod q
a_r = pow(c, pow(e, -1, r-1), r) # unique root mod r
# i = 1 (initial)
i = 246_492_539 # sekitar 28 menit dapet i yang memenuhi
gi_p = pow(gE_p, i, p)
bar = tqdm(range(i, e), total=e-i, desc="Shumow Attack", dynamic_ncols=True, leave=False)
for k in bar:
mp = (a_p * gi_p) % p
cand = crt3(mp, a_q, a_r, p, q, r)
s = cand.to_bytes((cand.bit_length()+7)//8, "big")
if s.startswith(b"ITSEC{"):
print(s)
break
gi_p = (gi_p * gE_p) % p
```
Sign in with Wallet
Connect another wallet