# 2025 Crypto CTF - writeup
> Author : 堇姬 Naup
> Team: NullCipher
> Rank: All 23rd & Taiwan 2nd
## Silky
```py
#!/usr/bin/env sage
import sys
from Crypto.Util.number import *
from flag import flag
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.buffer.readline()
def randroad(B):
return vector(ZZ,[randint(-B, B) for _ in range(n)])
def roadband():
return randroad(B * (D + 1))
def silky(key):
while True:
R = roadband()
_R = R - key
if min(_R) >= - B * D and max(_R) <= B * D:
return R
def main():
border = "┃"
pr( "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
pr(border, ".::: Welcome to the Silky cryptography oracle task! :::.", border)
pr(border, "Your mission is to find flag by analyzing this weird oracle! :-) ", border)
pr( "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
global flag, B, n, D, t
B, n = 5, 19
D, t = 110, 128
l = int(4 * D * B / t) # 17
c, key = 0, randroad(B)
while True:
c += 1
if c >= 12:
die(border, "My brain is fried, quitting...")
pr(f"{border} Options: \n{border}\t[G]et flag! \n{border}\t[M]ake Silky! \n{border}\t[Q]uit")
ans = sc().decode().strip().lower()
if ans == 'm':
R = [silky(key) for _ in range(int(l * t // 2))]
for i in range(len(R) // 16):
pr(border, f"{str(R[16 * i:16 * (i + 1)]).replace(',', '')}")
elif ans == 'g':
pr(border, f'Please submit the secret key: ')
inp = sc().decode().strip()
try:
_key = vector(ZZ, [int(_) for _ in inp.split(',')])
except:
die(border, f'The input you provided is not valid! Bye!!')
if _key == key:
die(border, f'Congrats! You got the flag: {flag}')
else:
die(border, f'Your key is incorrect!')
elif ans == 'q':
die(border, "Quitting...")
else:
die(border, "Bye...")
if __name__ == '__main__':
main()
```
他會先生成一個長度為 19，元素介於 5~-5 之間的 key
如果能夠猜到這個 key，那就可以拿到 flag
他允許我們操作 11 次
並且有另一項操作，他做了 1088 次這件事
他會去生成 R (元素 555~-555，向量維度 19)，然後去減掉 key，並確保算出來的 `_R` 會落在 `550~-550` 中，沒有的話就重新生成 R
所以總共可以拿到 $1088\times10=10880$ 個這種向量
這邊其實很明顯就可以拿到 key 對應的上下界
$\_R \in [550,-550]=R-key$
$R+550 \geq key \geq R-550$
現在有 $R$，通過 oracle 就可以簡單拿到上下界了，因為給的組數夠多，就可以篩出一個唯一的 key，最後拿到 flag
### exploit
```py
from pwn import *
import re
key_con = [[i for i in range(-5,6)] for j in range(0,19)]
oracle_vector = []
def handle_vector_fmt(data):
text = data.decode()
pattern = r'\((.*?)\)'
matches = re.findall(pattern, text)
vectors = [list(map(int, m.split())) for m in matches]
return vectors
def oracle():
r.sendlineafter(b"[Q]uit", b"M")
r.recvline()
lines = r.recvlines(68)
for i in lines:
i = i.split(b"\xe2\x94\x83 ")[1]
some_vec = handle_vector_fmt(i)
for j in some_vec:
oracle_vector.append(j)
r = remote("91.107.132.34", 31131)
for i in range(10):
oracle()
for idx in range(0,19):
for vec in oracle_vector:
_R = vec[idx]
low = _R - 550
high = _R + 550
key_con[idx] = [k for k in key_con[idx] if low <= k <= high]
ans = b""
for i in range(0,19):
ans += str(key_con[i][0]).encode() + b","
r.sendlineafter(b"[Q]uit", b"G")
r.sendline(ans[:-1])
r.interactive()
# CCTF{k3Y_R3c0vEry_4TtaCk_On_A_l3AkY_5e4Si9n!}
```
## Mancity
```py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def man(n):
B = bin(n)[2:]
M = ''
for b in B:
if b == '0':
M += '01'
else:
M += '11'
return int(M, 2)
def keygen(nbit):
while True:
p = getPrime(nbit)
r = man(p)
B = bin(p)[2:] + '1' * nbit
q = int(B, 2)
if isPrime(q) and isPrime(r):
return q, r
nbit = 256
p, q = keygen(nbit)
m = bytes_to_long(flag)
assert m < n
e, n = 1234567891, p * q
c = pow(m, e, n)
print(f'n = {n}')
print(f'c = {c}')
```
他通過一種特殊的方式去生成質數，這邊記為 P (256 bits)
首先他會先生成一個質數，然後把這個質數通過映射
把 0 映射成 01
把 1 映射成 11
確保他是質數後生成他作為 q (512 bits)
在拿 P 去生成
把這個質數低位先補上 256 bits 的 1
若他是質數，他就做為 p (512 bits)
n 是 pq
e 是 1234567891
去加密 flag
我們有 n、e、c
$n=p \times q=(P \times {2^{256}}+2^{256}-1)\times q=(P-1) \times 2^{256}-q$
$n \pmod {2^{256}}=-q$
所以可以用 $-n \pmod {2^{256}}$ 拿到 $q$ 的低 256 bits
$q$ 的 256 bits 通過 man 映射，可以映射出 $P$ 的 128 bits
$P$ 128 bits 是 $p$ 的 256~384 bits
所以現在未知
未知 q 高 256 bits
未知 p 高 128 bits
未知 P 高 128 bits
$p=(x \times 2^{128}+p_{low})\times 2^{256}+2^{256}-1$
$p=x \times 2^{384}+b$ (b 為已知)
估一下
$x=128 bits$
$n=1024 bits$
$2^{128}<2^{1024/1}$
然後做 coppersmith
### exploit
```py
from Crypto.Util.number import long_to_bytes
def man(n):
B = bin(n)[2:]
M = ''
for b in B:
if b == '0':
M += '01'
else:
M += '11'
return int(M, 2)
def recover_plow(r_low, bits=128):
bin_r_low = bin(r_low)[2:].zfill(256)
plow_bin = ''
for i in range(0, 256, 2):
two_bits = bin_r_low[i:i+2]
if two_bits == '01':
plow_bin += '0'
elif two_bits == '11':
plow_bin += '1'
else:
raise ValueError("Invalid bit pattern")
return int(plow_bin, 2)
n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537
r_low = (-n) % (2**256)
p0_low = recover_plow(r_low)
b = p0_low * (2**256) + (2**256 - 1)
F = Zmod(n)
PR.<x> = PolynomialRing(F)
f = x * (2**384) + b
f = f.monic()
roots = f.small_roots(X=2**128, beta=0.4, epsilon=0.02)
x0 = int(roots[0])
Q = (x0 << 384) + b
if n % Q == 0:
q = Q
p = n // q
d = inverse_mod(1234567891, (p-1)*(q-1))
m = pow(c, d, n)
flag = long_to_bytes(int(m))
print("Flag:", flag)
# CCTF{M4nch3sReR_c0D!ng_wI7H_RSA}
```
## Matemith
需要逆推出 (u, v, w, x, y, z)
總之就是方程消一消，求解就可以算出來了
感覺是非預期解
### exploit
```py
from Crypto.Util.number import long_to_bytes
p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261
Fp = GF(p)
f = [8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483,
8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397,
9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387,
5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117]
h = [6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258,
3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491,
5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566,
1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741]
j = [1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379,
6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212,
4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048,
973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820]
a0, a1, a2, a3 = [x % p for x in f]
c0, c1, c2, c3 = [x % p for x in h]
e0, e1, e2, e3 = [x % p for x in j]
b = [7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641,
3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860,
6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752,
2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563]
d = [7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472,
8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224,
3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117,
6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760,
4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040]
g = [1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038,
784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109,
7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778,
4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409,
7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790]
A1 = (-a2 * c0 + a0 * c2) % p
A2 = (-a2 * c1 + a0 * c3) % p
B1 = (-a3 * c0 + a1 * c2) % p
B2 = (-a3 * c1 + a1 * c3) % p
A = (-e2 * A1 + B1 * e0) % p
B = (-e2 * A2 - e3 * A1 + B1 * e1 + B2 * e0) % p
C = (-e3 * A2 + B2 * e1) % p
R.<w> = PolynomialRing(Fp)
poly = A*w^2 + B*w + C
roots = poly.roots()
ans = []
for w0, _ in roots:
v0 = (-e2*w0 - e3) * pow(e0*w0 + e1, -1, p) % p
u1 = (-a2*v0 - a3) * pow(a0*v0 + a1, -1, p) % p
u2 = (-c2*w0 - c3) * pow(c0*w0 + c1, -1, p) % p
u0 = u1
Rz.<z> = PolynomialRing(Fp)
N1 = -d[2]*z - d[3]*w0 - d[4]
D1 = d[0]*v0*z + d[1]
N2 = -b[1]*N1 - (b[2]*v0 + b[3])*D1
D2 = b[0]*(u0*N1 + D1)
poly2 = g[0]*w0*N2*z + g[2]*N2 + (g[3]*z + g[1]*u0 + g[4])*D2
for z0, _ in poly2.roots():
y0 = (-d[2]*z0 - d[3]*w0 - d[4]) * pow(d[0]*v0*z0 + d[1], -1, p) % p
x0 = (-b[1]*y0 - b[2]*v0 - b[3]) * pow(b[0]*(u0*y0 + 1), -1, p) % p
ans.append((u0, v0, w0, x0, y0, z0))
for tup in ans:
parts = [long_to_bytes(int(x)) for x in tup]
print("CCTF{" + b''.join(parts).decode() + "}")
# CCTF{50lv!n6_7H3_H1dD3n__num8Ers_Pr08l3m_f0r_C51dH_4nd_C5uRf_v14_4uT0m473d_C0pp3r5m17h!!?}
```
## Phoney
```py
#!/usr/bin/env python3
import sys, os
from Crypto.Util.number import *
from flag import flag
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.buffer.readline()
def keygen(nbit):
p, q, r = [getPrime(nbit + (nbit >> 3) * _) for _ in range(3)]
return p, q, r
def main():
border = "┃"
pr( "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
pr(border, " Welcome to the Phoney crypto-system task, a nice cryptosystem ", border)
pr(border, " that's so good, it's theoretically unbreakable because it exists", border)
pr(border, " only in the realm of imagination!! Try the get the long flag :-)", border)
pr( "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
global flag
m = bytes_to_long(os.urandom(len(flag)) + flag + os.urandom(len(flag)))
nbit = 512
p, q, r = keygen(nbit)
n, s, e = p * q * r, inverse(p, q * r) + p, 1234567891
while True:
pr(f"{border} Options: \n{border}\t[E]ncrypt the flag! \n{border}\t[P]ublic information \n{border}\t[Q]uit")
ans = sc().decode().strip().lower()
if ans == 'e':
assert m < n
c = pow(m, e, n)
pr(f'{c = }')
elif ans == 'p':
pr(border, f'{n = }')
pr(border, f'{s = }')
pr(border, f'{q % p = }')
elif ans == 'q':
die(border, "Quitting...")
else:
die(border, "Bye...")
if __name__ == '__main__':
main()
```
不知道為啥這題要用遠端的XD
總之他是一題 RSA，會去生成三個 prime，分別是 512、576、640 bits
$n=pqr$
$s=p^{-1} \pmod {qr} +p$
$e = 1234567891$
我們可以拿到 $n,s,q\pmod p,c$
這邊先整理
$s=p^{-1} \pmod {qr} +p=p^{-1}+p \pmod {qr}$
$sp \equiv 1+p^2 \pmod {qr}$
$sp-p^2-1 \equiv 0 \pmod {qr}$
$sp-p^2-1 = kqr$
$sp-p^2-1 = k \times \frac{n}{p}$
$sp^2-p^3-p-kn=0$
$p^3-sp^2+p=0 \pmod n$
稍微估計一下
$n$ 是 1728 bits
$2^{512}<2^{1728/3}=2^{576}$
對他 coppersmith
就可以算出 $p$ 了
這邊 beta 設 1 ($x<N^{\beta^2/d}$)，微調下 epsilon 就可以算出來了
接下來要算出 $q$
$q=qmodp+xp\pmod {qr}$
$2^{64}<2^{1216}$
直接 coppersmith
這樣就分解開 n 了，就可以拿到 flag 了~
### exploit
```py
from Crypto.Util.number import long_to_bytes
n = 2558035556695475709032040331521355197476522299617845925698968281016249703243151647922124540670935080518748202939594480280292216898828943067801728906396652170316648544836795919279110133715614609048396848322530441713671072739549366681229876645318544568210401180374531524716432800887977536327214645552865209445577330546047288405443848110231737390394210240136242435300878094705778721727621798393321430205811113775821273820784626337378392832565403181927392448125231771678902379598107575467034577515459979744923531786502254417
c = 840511306923732744838897191449302243631582186794297476586226263955580082979643814367575741284084902689169799293436701296817765995419783346761567445277858297589753150726609277016417648733466835390955338349842407172938570516834407121618408363393502453021864778090234902680425870554199854585004650558349607544126694671802767392588485481558710195747781804512196572802494504451623056249663486308106419881186476160738607600693002241109901196300085568118266663761889254087132096878027390496310785830915437914555877600931519448
s = 42232722417149874921403143383006935454821569574127211713248915741530856324578541176192907900846816231780539915041418424207197455154285119396183169973932930501400778220542539943963742927972297762460743988343784012752312654237184182861181062288407051180649161581485083155821796107052904243611250969961583168988395599551404512274570924861635837494947854251970954923049
q_mod_p = 5838076379030626193818995408888160221457593029979837485436932795852910877130845393522721108280267112327300232994749017518857895105782094872212016155562840
e = 1234567891
F = Zmod(n)
PR.<x> = PolynomialRing(F)
f = x**3-s*(x**2)+x
f = f.monic()
roots = f.small_roots(X=2**512, beta=1, epsilon=1/20)[1]
p = int(roots)
qr = n // int(p)
F = Zmod(qr)
PR.<x> = PolynomialRing(F)
f = q_mod_p + x*p
f = f.monic()
roots = f.small_roots(X=2**65, beta=0.25)[0]
q = int(q_mod_p + int(roots) * p)
r = int(qr // int(q))
phi = (p-1)*(q-1)*(r-1)
d = inverse_mod(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))
# CCTF{c0UlD_b3_ReCoVEr3d_v!4_Coppersmiths_m3ThOd?}
```
## after all
比去年進步，好耶~
Sign in with Wallet
Connect another wallet