<center>
<h1>KCSC Recruitment 2026 </h1>
</center>


# Mini RSA
Bài khởi động

chall.py:

from Crypto.Util.number import getPrime, bytes_to_long
from hashlib import sha256

# fake flag, complete 4 phases below to get the real one
FLAG = b"KCSC{676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767}"
FLAG = FLAG[5:-1]  
assert all(c in b"0123456789abcdef" for c in FLAG) # hex-only
assert len(FLAG) == 162

part1 = FLAG[0  : 37]
part2 = FLAG[37 : 91]
part3 = FLAG[91 : 155]
part4 = FLAG[155: 162]
assert part1 + part2 + part3 + part4 == FLAG




# Phase 1:
assert len(part1) == 37

n1 = getPrime(1024) * getPrime(1024)
flag1 = bytes_to_long(part1)
assert flag1 < n1
e1 = 7
c1 = pow(flag1, e1, n1)

print("Phase 1:")
print(f"n = {n1}")
print(f"e = {e1}")
print(f"c = {c1}\n")
# n = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
# e = 7
# c = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827




# Phase 2:
assert len(part2) == 54

moduli = [getPrime(500) * getPrime(500) for _ in range(3)]
flag2 = bytes_to_long(part2)
assert flag2 < min(moduli)
e2 = 7
ciphertexts = [pow(flag2, e2, moduli[i]) for i in range(3)]

print("Phase 2:")
print(f"ns = {moduli}")
print(f"e  = {e2}")
print(f"cs = {ciphertexts}\n")
# ns = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
# e  = 7
# cs = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]




# Phase 3:
assert len(part3) == 64

p3 = getPrime(512)
q3 = getPrime(512)
n3 = p3 * q3

flag3 = bytes_to_long(part3)
assert flag3 < n3

phi3 = (p3 - 1) * (q3 - 1)
e3 = 0x10001
E = getPrime(16)

assert e3 != E
d3 = pow(E, -1, phi3) # I'm so generous that I will give you d directly :)
c3 = pow(flag3, e3, n3)

print("Phase 3:")
print(f"n = {n3}")
print(f"e = {e3}")
print(f"E = {E}")
print(f"d = {d3}")
print(f"c = {c3}\n")
# n = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
# e = 65537
# E = 39119
# d = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
# c = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342    




# Phase 4:
assert len(part4) == 7

# hash of the flag
Flag_hash = sha256(FLAG).hexdigest()
print("Phase 4:")
print(f"{Flag_hash = }")
# Flag_hash = 6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281

Một bài RSA gồm nhiều lỗ hỏng khác nhau với flag được chia ra thành 4 phần khác nhau, nên ta sẽ đi tìm từng phần để thu được flag hoàn chỉnh.

Phase 1:

assert len(part1) == 37

n1 = getPrime(1024) * getPrime(1024)
flag1 = bytes_to_long(part1)
assert flag1 < n1
e1 = 7
c1 = pow(flag1, e1, n1)

print("Phase 1:")
print(f"n = {n1}")
print(f"e = {e1}")
print(f"c = {c1}\n")
# n = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
# e = 7
# c = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827

$part_1$ được mã hóa theo công thức:
$$C \equiv part_1^{e_1} \pmod {N_1}$$
Độ dài của $part_1$ là 37 byte, vậy nó sẽ có 296 bit, khi mũ 7 lên thì sẽ có giá trị khoảng từ 2066 đến 2072 bit. Còn $N_1$ giá trị là 2048 bit.
Vậy ta có thể hoàn toàn brute-force tìm được k sao cho:
$$C_1 + k.N_1 = part_1^{e_1}$$
Tương đương
$$part_1 = \sqrt [e_1] {C_1 + k.N_1}$$
Ta sẽ brute-force với k bắt đầu là 1 và cứ tăng giá trị lên cho đến khi $part_1$ là một số nguyên.

#part 1
n1 = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
c1 = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827
e1 = 7
k = 0
check_part1 = iroot(c1 + k*n1, e1)[1]
part1 = 0

while (check_part1 == False):
    check_part1 = iroot(c1 + k*n1, e1)[1]
    part1 = iroot(c1 + k*n1, e1)[0]
    k += 1

Phase 2:

# Phase 2:
assert len(part2) == 54

moduli = [getPrime(500) * getPrime(500) for _ in range(3)]
flag2 = bytes_to_long(part2)
assert flag2 < min(moduli)
e2 = 7
ciphertexts = [pow(flag2, e2, moduli[i]) for i in range(3)]

print("Phase 2:")
print(f"ns = {moduli}")
print(f"e  = {e2}")
print(f"cs = {ciphertexts}\n")
# ns = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
# e  = 7
# cs = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]

$part_2$ được mã hóa cùng 1 e nhưng với nhiều modulo $N$ khác nhau (cụ thể là 3) , vậy ta có thể lập được hệ phương trình đồng dư như sau:
\begin{cases}
part_2^{e} \equiv C_1 \pmod{N_1}\\
part_2^{e} \equiv C_2 \pmod{N_2}\\
part_2^{e} \equiv C_3 \pmod{N_3}
\end{cases}
Giải hệ trên bằng thuật toán CRT (Chinese Remainder Theorem) sẽ thu được:
$$M \equiv part_2^e \pmod N$$
- với $N = N_1.N_2.N_3$

Nếu $part_2^e < N$ thì đến đây ta có thể rút căn 2 vế để thu được $part_2 = \sqrt[e]{M}$
Nhưng trong challenge này $part_2^e$ sẽ khoảng 3024 bit, lớn hơn $N$ (khoảng 3000 bit) nên vẫn phải áp dụng kỹ thuật brute-force tìm k thỏa $M + k.N = part_2^{e}$ như Phase 1 để tìm được $part_2$.

# part 2
ns2 = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
cs2 = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]
e2 = 7
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342 
N = 1

for n in ns2:
    N *= n
M = crt(ns2, cs2)[0]
k2 = 0
check_part1 = iroot(M + k2*N, e2)[1]
part2 = 0
while (check_part1 == False):
    check_part1 = iroot(M + k2*N, e2)[1]
    part2 = iroot(M + k2*N, e2)[0]
    k2 += 1

Phase 3:

# Phase 3:
assert len(part3) == 64

p3 = getPrime(512)
q3 = getPrime(512)
n3 = p3 * q3

flag3 = bytes_to_long(part3)
assert flag3 < n3

phi3 = (p3 - 1) * (q3 - 1)
e3 = 0x10001
E = getPrime(16)

assert e3 != E
d3 = pow(E, -1, phi3) # I'm so generous that I will give you d directly :)
c3 = pow(flag3, e3, n3)

print("Phase 3:")
print(f"n = {n3}")
print(f"e = {e3}")
print(f"E = {E}")
print(f"d = {d3}")
print(f"c = {c3}\n")
# n = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
# e = 65537
# E = 39119
# d = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
# c = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342    

Ta được cho khóa bí mật $d$ luôn, nhưng đừng nhầm lẫn, đó không phải là khóa bí mật thật sự, khóa $d$ thật sự là nghịch đảo của $e$ trong modulo $\phi(n)$, còn ở đây $d$ là nghịch đảo của $E$ trong $\phi(n)$.
Vậy ta phải tính được khóa $d$ thật sự từ giá trị $d$ fake này.
Ta biết rằng:
$$E.d_{fake} \equiv 1 \pmod{\phi(n)}$$
Vậy
$$E.d_{fake} - 1 = k \cdot \phi(n)$$
Do đó ta sẽ có thể tính được $\phi(n)$:
$$\phi(n) = \frac{E.d_{fake} - 1}{k}$$
Nhưng ta không biết $k$ nên chưa tính được (lúc diễn ra giải thì mình đi brute-force $k$ luôn)
Cụ thể là ta có thể tính $k$ như sau:
$$k = \frac{d_{fake} \cdot E - 1}{\phi(n)}$$
Vì $d_{fake}$ là nghịch đảo modulo $\phi(n)$, nên $d_{fake} < \phi(n)$.
Vậy thì $$k < \frac{\phi(n) \cdot E}{\phi(n)} $$
Do đó: $k < E$
Mà bài này cho $E = 39119$. Rất nhỏ nên brute-force bình thường.
Sau đó mình ngỗi ngẫm lại thì nhận ra có 1 cách tính trực tiếp, cụ thể:
Ta có:
$$\phi(n) = (p-1)(q-1) = n - p - q + 1$$
Vì $p, q \approx \sqrt{n}$, nên $p+q$ rất nhỏ so với $n$. Do đó:$$\phi(n) \approx n$$
Nên phương trình $E.d_{fake} - 1 = k \cdot \phi(n)$ sẽ trở thành:
$$E.d_{fake} - 1 \approx k \cdot n$$
Vậy ta có thể tính $k$ bằng phép chia nguyên: $$k = (E.d_{fake}) // n$$
Vì sai số rất nhỏ nên chỉ cần kiểm tra vài giá trị xung quanh $k$

# part 3
n3 = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e3 = 65537
E = 39119
d_fake = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342    

k_fake = (d_fake*E - 1) // n3
phi = (d_fake * E - 1) // k_fake
for k in range(k_fake - 2, k_fake + 3):
    if k == 0: continue
    if (d_fake * E - 1) % k == 0:
        phi = (d_fake * E - 1) // k
d = pow(e3, -1, phi)
part3 = long_to_bytes(pow(c3, d, n3))

Phase 4:

# Phase 4:
assert len(part4) == 7

# hash of the flag
Flag_hash = sha256(FLAG).hexdigest()
print("Phase 4:")
print(f"{Flag_hash = }")
# Flag_hash = 6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281

Ta được biết giá trị của $part_4$ sau khi đi qua hàm băm `sha256`
Hàm này đương nhiên không có cách nào tính ngược lại rồi nên phải đi brute-force, vì $part_4$ chỉ dài 7 byte mà ta biết flag chỉ chứa các ký tự `0123456789abcdef` nên ta sẽ phải duyệt khoảng $16^7$ trường hợp (vẫn khả thi)

# part 4
hash = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"
chars = "0123456789abcdef"

for p in product(chars, repeat=7):
    flag = b"KCSC{" + part1 + part2 + part3 + "".join(p).encode() + b"}"
    if(sha256(flag).hexdigest() == hash):
        print(flag.decode())
        break

Vậy ta đã tìm được đầy đủ flag, ghép chúng lại là có flag hoàn chỉnh.

full solve:

from Crypto.Util.number import *
from sympy.ntheory.modular import crt
from gmpy2 import iroot
from hashlib import sha256
from itertools import product
from tqdm import tqdm

#part 1
n1 = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
c1 = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827
e1 = 7
k1 = 0
check_part1 = iroot(c1 + k1*n1, e1)[1]
part1 = 0

while (check_part1 == False):
    check_part1 = iroot(c1 + k1*n1, e1)[1]
    part1 = long_to_bytes(iroot(c1 + k1*n1, e1)[0])
    k1 += 1


# part 2
ns2 = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
cs2 = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]
e2 = 7
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342 
N = 1

for n in ns2:
    N *= n
M = crt(ns2, cs2)[0]
k2 = 0
check_part1 = iroot(M + k2*N, e2)[1]
part2 = 0
while (check_part1 == False):
    check_part1 = iroot(M + k2*N, e2)[1]
    part2 = long_to_bytes(iroot(M + k2*N, e2)[0])
    k2 += 1


# part 3
n3 = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e3 = 65537
E = 39119
d_fake = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342    

k_fake = (d_fake*E - 1) // n3
phi = (d_fake * E - 1) // k_fake
for k in range(k_fake - 2, k_fake + 3):
    if k == 0: continue
    if (d_fake * E - 1) % k == 0:
        phi = (d_fake * E - 1) // k
d = pow(e3, -1, phi)
part3 = long_to_bytes(pow(c3, d, n3))

#print(part1, part2, part3)
# part 4
hash = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"
chars = "0123456789abcdef"

for p in tqdm(product(chars, repeat=7)):
    flag = b"KCSC{" + part1 + part2 + part3 + "".join(p).encode() + b"}"
    if(sha256(flag).hexdigest() == hash):
        print(flag.decode())
        break

::: spoiler Flag
KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}
:::
# Lost

Mình khá thích bài này

chall.py:

from Crypto.Util.number import getPrime, bytes_to_long

flag = "KCSC{████████████████████████████████████████l█e███████ha█████████████████████}"
assert len(flag) == 79
flag = bytes_to_long(flag.encode())

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
phi = (p-1) * (q-1)

# how many bits of phi do you want me to truncate <(") ?
HINT = phi & ((1 << (445)) - 1)

assert flag < n
c = pow(flag, e, n)

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

# n = 112654267531053465556136674746878649082311939063806818924462933263741875629394889661682552659024091908172480343659015574843946862042743125008337388884333221729927034358266152309599465123544533344748189013549990570426711270722167349548299576309337189468190071950365811726840694954345965264584467524018296958753
# e = 65537
# c = 8002944762099258567457615206256772306393999363093971354996328677238641774654391571386887016848224899250762255275947356988416616247761892841611709100843880889058667475786184996217958354468257211905339362523859724316921413272443004897703998073112581860169711839608791480826283429489201512747250548419782502867
# HINT = 58568716757057749176579698947278522097247638230381142002077590687430267388214398988361849858546815254992223558816558004613328562794052

Mình đọc qua thì chắc chắc 1000% là Coppersmith.
Vì dòng code:

HINT = phi & ((1 << (445)) - 1)

Nó tương đương với lấy $\phi(n)$ mod cho $2^{445}$. Tức là lấy 445 bit thấp nhất của $\phi(n)$. Do đó ta sẽ cố gắng liên hệ điều này với việc tìm bit của $p$ (hoặc $q$).
Ta có công thức:
$$\phi(n) = (p-1)(q-1) = p. q - (p + q) + 1 = n - (p + q) + 1$$
Vậy suy ra $$p + q = n + 1 - \phi(n)$$
Vì ta biết 445 bit thấp của $\phi(n)$ (thông qua `HINT`), ta có thể tính được 445 bit thấp của $(p+q)$:
Gọi $$S \equiv p + q \pmod{2^{445}} =n + 1 - \phi(n) \pmod{2^{445}}$$
Mà HINT $\equiv \phi(n) \pmod{2^{445}}$.
Nên:
$$S \equiv n + 1 - \text{HINT} \pmod{2^{445}}$$
Đến đây ta phải tinh ý nhận ra $S$ được biểu diễn theo các thành phần $p+q$ và $n = p.q$,
Nên ta sẽ lập phương trình:
$$x^2 - (p+q)x + (p \cdot q) = 0$$
Vì theo định lý Viet, $p$ và $q$ là hai nghiệm của phương trình đó.
Tới đây ta thay $S$ vào:
$$x^2 - S \cdot x + n \equiv 0 \pmod{2^{445}}$$
Giải phương trình này ta sẽ thu được 1 nghiệm x nằm trong khoảng $[0, 2^{445}-1]$, và nghiệm $x$ đó cũng là 445 bit thấp của $p$ luôn (gọi là $p_{low}$).

Giờ ta biết $p = 512$ bit, ta vừa tìm được $445$ bit thấp của nó, vậy thì còn thiếu $67$ bit.
Ta có thể biễu diễn $p$ như sau:
$$p = x \cdot 2^{445} + p_{low}$$
- Với x là $67$ bit cao của $p$

Phương trình trên tương đương với:
$$x \cdot 2^{445} + p_{low} \equiv 0 \pmod p$$
Đến đây ta tìm ra được phương trình chuẩn để dùng Coppersmith (mình sẽ dùng hàm `small_roots` trong Sage).
Ta xét đa thức $$f(x) = x \cdot 2^{445} + p_{low}$$
Mặc dù ta cần giải $f(x) \equiv 0 \pmod p$, nhưng vì chưa biết $p$, ta sẽ khởi tạo đa thức này trên modulo $n$ (ta làm được vì $n$ là bội của $p$). Thuật toán Coppersmith cho phép tìm nghiệm modulo ước số $p$ ngay cả khi ta tính toán trên vành $\mathbb{Z}_n$."
> Lưu ý là: Điều kiện Coppersmith cho bài toán tìm $p$ như thế này chỉ có thể tìm được nếu ta biết khoảng 50% số bit của $p$. Ở đây ta biết $445/512 \approx 86\%$, nên chắc chắn tìm được.

Và quan trọng là ở bài này nên đặt `multiplicities = False` ở hàm `.roots`. Vì nếu để `multiplicities=True` (mặc định): ngoài việc tìm nghiệm ra thì nó còn phải xác định xem nghiệm đó là nghiệm đơn hay nghiệm kép. Trong bài này khi tính nghiệm trên một vành số dư hợp số $\mathbb{Z}_M$ (như $\mathbb{Z}_{2^{445}}$), việc xác định nghiệm đó là nghiệm đơn hay kiếp trở nên phức tạp nên khi chạy sẽ báo lỗi nên tốt nhất là đặt nó = False.

solve.sage:

from Crypto.Util.number import long_to_bytes
from sage.all import *
import sys 

n = 112654267531053465556136674746878649082311939063806818924462933263741875629394889661682552659024091908172480343659015574843946862042743125008337388884333221729927034358266152309599465123544533344748189013549990570426711270722167349548299576309337189468190071950365811726840694954345965264584467524018296958753
e = 65537
c = 8002944762099258567457615206256772306393999363093971354996328677238641774654391571386887016848224899250762255275947356988416616247761892841611709100843880889058667475786184996217958354468257211905339362523859724316921413272443004897703998073112581860169711839608791480826283429489201512747250548419782502867
HINT = 58568716757057749176579698947278522097247638230381142002077590687430267388214398988361849858546815254992223558816558004613328562794052
bit = 445

P = PolynomialRing(Zmod(2**bit), 'x')
x = P.gen()
S = (n + 1 - HINT)
roots = (x^2 - S*x + n).roots(multiplicities=False)

for r in roots:
    p_low = Integer(r)
    P2 = PolynomialRing(Zmod(n), 'y')
    y = P2.gen()
    f = y * (2**bit) + p_low
    res = f.monic().small_roots(X=2**72, beta=0.45)
    if res:
        p_high = res[0]
        p = int(p_high * (2**bit) + p_low)
        if n % p == 0:
            q = n // p
            phi = (p - 1) * (q - 1)
            d = pow(e, -1,  phi)
            flag = long_to_bytes(pow(c, d, n))
            print(flag.decode())

# Multi RSA
Một bài khá khó vì phải biết cách DLP và có kiến thức cơ bản về đại số tuyến tính.
chall.py:

from Crypto.Util.number import *
from random import randint

flag = b'KCSC{??????????????????????????????????????????????????????????????????????????????????????????}'
assert flag.startswith(b"KCSC{") and len(flag) == 96

# my prime generator
def get_prime(factor_bits, nbits):
    while True:
        p = 2
        while p.bit_length() + factor_bits < nbits:
            p *= getPrime(factor_bits)
        current_len = p.bit_length()
        needed_bits = nbits - current_len
        
        if needed_bits < 2:
            continue
        try:
            last_prime = getPrime(needed_bits)
        except ValueError:
            continue
        
        p = p * last_prime + 1
        if p.bit_length() == nbits and isPrime(p):
            return p

p = get_prime(16, 128)
q = get_prime(16, 128)
n = p * q
phi = (p-1)*(q-1)

# 3 parts of the flag
m1, m2, m3 = [bytes_to_long(part) for part in [flag[i:i+32] for i in range(0, len(flag), 32)]]
assert all(part < n for part in [m1, m2, m3])

es = []
cs = []
for i in range(3):
    # rsa encryption
    e1, e2, e3 = [randint(1, phi-1) for _ in range(3)]
    
    c1 = pow(m1, e1, n)
    c2 = pow(m2, e2, n)
    c3 = pow(m3, e3, n)
    
    es.append((e1, e2, e3))
    # cs.append((c1, c2, c3)) # nah, too easy
    cs.append((c1 * c2 * c3) % n) # what if i multiply them together ?

# write outputs to file
with open("output.txt", "w") as f:
    f.write(str(n)  + "\n")
    f.write(str(es) + "\n")
    f.write(str(cs))

ouput.txt:

47671780042231704413040913594725353438536469505015682546574752585718301112921
[(23977172217622484168774759837385378732502237507920113310285233140285669132645, 7377494923066904273449829226282557300745689267275904429462158991949281414682, 18432112474217778047559883846454066035490987127796230294276735606306725549777), (3124743981175141708117586893234378699895764583129200589303495951740637999914, 22762044917281148499181453892958515527103600842740372832842228589873412009197, 17680895854953441923244596894140851738984314699825793211831691205085172067322), (37545236985478706251704483601220896064218212306586005333560412013908096438729, 20788835878098532955063747621021775806003893333625966206551591514326857932485, 32312926559646114857217655963694360470473973949883002194388252273197485497673)]
[42267207336603045334786451171189000378049455207827292631901571990305135126669, 33840845882520281865996502853093641414955191938495377599016576841954115079220, 18018251336838883503303580652480693144525524464022122529153696030852723761647]

Flag được chia thành 3 phần và được mã hóa bằng các e khác nhau. Nhưng ta không biết chính xác giá trị của ciphertext mà biết giá trị của các ciphertext đó nhân với nhau, tức là ta có hệ phương trình:
$$\begin{cases}
C_1 \equiv m_1^{e_{1,1}} \cdot m_2^{e_{1,2}} \cdot m_3^{e_{1,3}} \\
C_2 \equiv m_1^{e_{2,1}} \cdot m_2^{e_{2,2}} \cdot m_3^{e_{2,3}} \\
C_3 \equiv m_1^{e_{3,1}} \cdot m_2^{e_{3,2}} \cdot m_3^{e_{3,3}}
\end{cases} \pmod N$$
Trước khi giải cái hệ khủng bố này thì ta phân tính hàm sinh số nguyên tố trước:

def get_prime(factor_bits, nbits):
    while True:
        p = 2
        while p.bit_length() + factor_bits < nbits:
            p *= getPrime(factor_bits)
        current_len = p.bit_length()
        needed_bits = nbits - current_len
        
        if needed_bits < 2:
            continue
        try:
            last_prime = getPrime(needed_bits)
        except ValueError:
            continue
        
        p = p * last_prime + 1
        if p.bit_length() == nbits and isPrime(p):
            return p

p = get_prime(16, 128)
q = get_prime(16, 128)

Hàm này tạo ra số nguyên tố $p$ theo dạng $p = k \cdot \Pi(p_i) + 1$. Điều này có nghĩa là $p-1$ là một số "smooth". Và trong các bài toán DLP, nếu $p-1$ là số smooth, ta có thể dùng thuật toán Pohlig-Hellman để tính DLP cực nhanh.
$N = p \cdot q \approx 256$ bit nên mình đã factor dễ dàng được $p, q$

p, q = 208241528391730184734449228964657137983, 228925423331290125959230566821710134887

Ta không thể tính DLP trên $N$ (vì nhóm $\mathbb{Z}_N^*$ không phải là nhóm cyclic). Do đó ta phải giải riêng trên $\mathbb{F}_p$ và $\mathbb{F}_q$, vì $p$ là số nguyên tố nên nhóm nhân $\mathbb{F}_p^*$ là nhóm cyclic cấp $p-1$.
Ta chọn $g$ là một căn nguyên thủy (primitive root) của $p$. Khi đó, mọi phần tử trong $\mathbb{F}_p^*$ đều có thể viết dưới dạng lũy thừa của $g$.

Xét trên modulo $p$:$$C_i \equiv m_1^{e_{i,1}} \cdot m_2^{e_{i,2}} \cdot m_3^{e_{i,3}} \pmod p$$

Từ đó ta đặt ẩn phụ cho các $m$ và $C$ theo cơ số $g$:
Đặt $x_1, x_2, x_3$ là logarit rời rạc của $m_1, m_2, m_3$:$$m_1 \equiv g^{x_1} \pmod p$$$$m_2 \equiv g^{x_2} \pmod p$$$$m_3 \equiv g^{x_3} \pmod p$$
Tính $Y_i$ là logarit rời rạc của $C_i$ (đây là giá trị ta có thể tính được vì $C_i, g, p$ đã biết):$$C_i \equiv g^{Y_i} \pmod p$$
Thay các giá trị $g$ vào phương trình ban đầu:$$g^{Y_i} \equiv (g^{x_1})^{e_{i,1}} \cdot (g^{x_2})^{e_{i,2}} \cdot (g^{x_3})^{e_{i,3}} \pmod p$$
Ta có thể thu gọn phương trình trên: $$g^{Y_i} \equiv g^{x_1 \cdot e_{i,1}} \cdot g^{x_2 \cdot e_{i,2}} \cdot g^{x_3 \cdot e_{i,3}} \pmod p$$$$g^{Y_i} \equiv g^{(e_{i,1}x_1 + e_{i,2}x_2 + e_{i,3}x_3)} \pmod p$$
Theo định lý Fermat nhỏ, nếu $g^A \equiv g^B \pmod p$, thì số mũ sẽ đồng dư theo modulo $\phi(p) = p-1$. Phương trình mũ trên trở thành phương trình tuyến tính bậc nhất:$$Y_i \equiv e_{i,1}x_1 + e_{i,2}x_2 + e_{i,3}x_3 \pmod{p-1}$$
Để tìm 3 ẩn số $x_1, x_2, x_3$, ta cần ít nhất 3 phương trình (tức là cần 3 cặp $C_i$ tương ứng với $i=1, 2, 3$).
Hệ phương trình sẽ có dạng ma trận:$$\begin{pmatrix}
Y_1 \\
Y_2 \\
Y_3
\end{pmatrix}
\equiv
\begin{pmatrix}
e_{1,1} & e_{1,2} & e_{1,3} \\
e_{2,1} & e_{2,2} & e_{2,3} \\
e_{3,1} & e_{3,2} & e_{3,3} \\
\end{pmatrix}
\cdot
\begin{pmatrix}
x_1 \\
x_2 \\
x_3
\end{pmatrix}
\pmod{p-1}$$Gọi ma trận các số mũ là $E$, vector của ciphertext là $Y$, và vector ẩn là $X$. Ta có:$$Y \equiv E \cdot X \pmod{p-1}$$
Thì lúc này ta giải hệ phương trình bằng cách tính $E^{-1} \pmod{p-1}$. (Điều kiện là định thức $\det(E)$ phải nguyên tố cùng nhau với $p-1$).
Tại sao lại phải như vậy? Vì trên trường số thực, nếu định thức $\det(E) \neq 0$ thì có 1 nghiệm duy nhất.
Nhưng trên vành modulo $p-1$. Để có nghiệm duy nhất thì: $\gcd(\det(E), p-1)$ phải bằng 1.
$p-1$ là số chẵn, và định thức của ma trận cũng thường chẵn (thưòng thôi).
Do đó có thể $\gcd(\det(E), p-1) > 1$. Nên hậu quả là hệ trên sẽ có nhiều nghiệm.
Do đó mình nghĩ ra giải pháp khác là thay vì tìm ma trận nghịch đảo, mình sử dụng phương pháp Khử Gauss, hàm `solve_right` trong SageMath. Cụ thể, nếu hệ có nghiệm, nghiệm tổng quát sẽ có dạng:$$X = X_{p} + K$$
Trong đó thì:
- $X_{p}$: Là một nghiệm riêng
- $K$: Là một vector thuộc không gian Kernel của ma trận $E$.

Nói cách khác, do $\gcd > 1$, ta sẽ tìm được một tập hợp các giá trị $x_j$. Từ mỗi $x_j$, ta tính lại được một tập hợp các giá trị cho $m_j \pmod p$:$$m_j^{(k)} \equiv g^{x_j + k \cdot \frac{p-1}{d}} \pmod p$$

Đó là lý thuyết mình đọc được chứ mình cũng không biết tìm Kernel trong không gian logarit kiểu gì, nên mình sẽ đi tìm cái gọi là "độ chêch lệnh" của nghiệm

Cụ thể:
Gọi $X_0$ là nghiệm riêng mà hàm `solve_right` tìm được. lúc này nghiệm tổng quát sẽ là:$$X = X_0 + \Delta x$$
Ta có công thức$m = g^x \pmod p$.
Vậy:$$m = g^{X} = g^{(X_0 + \Delta x)} = g^{X_0} \cdot g^{\Delta x} \pmod p$$

Vậy là ta vừa biến đổi phép cộng trong logarit trở thành phép nhân với một hệ số trong message thành công.
Giờ ta cứ đi tính xem cái $g^{\Delta x}$ này thực sự là gì.
Gọi số lượng nghiệm của hệ phương trình trên là $k$, và theo lý thuyết thì:
$$k = \gcd(\det(E), p-1)$$
Điều này có nghĩa là sẽ có đúng $k$ giá trị khác nhau của $g^{\Delta x}$ thỏa mãn phương trình. Tập hợp các giá trị này tạo thành một nhóm con cyclic cấp $k$ của $\mathbb{F}_p^*$.
Cụ thể, phần tử sinh của nhóm sai số này là:
$$u = g^{\frac{p-1}{k}} \pmod p$$
Khi đó, hệ số $g^{\Delta x}$ sẽ nằm trong tập hợp các lũy thừa của $u$, tức là thuộc {${ 1, u, u^2, \dots, u^{k-1}}$}
Như vậy, quy trình khôi phục message hoàn chỉnh sẽ là:
- Dùng `solve_right` của sage để tìm một nghiệm $X_0$ bất kỳ.
- Tính message cơ sở: $m_{0} \equiv g^{X_0} \pmod p$.
- Sinh tập hợp $k$ hệ số điều chỉnh (shifts)
- message thật sự $m$ sẽ là một trong các giá trị $m_{0}.\text{shift}[i] \pmod p$.

solve.sage:

from Crypto.Util.number import long_to_bytes
from sage.all import *

N = 47671780042231704413040913594725353438536469505015682546574752585718301112921
Es = [
    (23977172217622484168774759837385378732502237507920113310285233140285669132645, 7377494923066904273449829226282557300745689267275904429462158991949281414682, 18432112474217778047559883846454066035490987127796230294276735606306725549777),
    (3124743981175141708117586893234378699895764583129200589303495951740637999914, 22762044917281148499181453892958515527103600842740372832842228589873412009197, 17680895854953441923244596894140851738984314699825793211831691205085172067322),
    (37545236985478706251704483601220896064218212306586005333560412013908096438729, 20788835878098532955063747621021775806003893333625966206551591514326857932485, 32312926559646114857217655963694360470473973949883002194388252273197485497673)
]
Cs = [42267207336603045334786451171189000378049455207827292631901571990305135126669, 33840845882520281865996502853093641414955191938495377599016576841954115079220, 18018251336838883503303580652480693144525524464022122529153696030852723761647]

p, q = 208241528391730184734449228964657137983, 228925423331290125959230566821710134887

res = []
for prime in [p, q]:
    F = GF(prime)
    g = F.multiplicative_generator()
    R = Zmod(prime - 1)
    
    Y = vector(R, [discrete_log(F(c), g) for c in Cs])
    M = Matrix(R, Es)
    X = M.solve_right(Y)
    
    k = gcd(Integer(M.det()), prime - 1)
    shifts = [pow(pow(g, (prime - 1) // k, prime), i, prime) for i in range(k)]
    msgs = [pow(g, int(x), prime) for x in X]
    
    res.append((msgs, shifts))

(msgs_p, shifts_p), (msgs_q, shifts_q) = res

flag = []
for i in range(3):
    for sp in shifts_p:
        for sq in shifts_q:
            m = crt([int(msgs_p[i] * sp % p), int(msgs_q[i] * sq % q)], [p, q])
            b = long_to_bytes(m)
            if (i == 0 and b.startswith(b"KCSC")) or (idx > 0 and all(32 <= c <= 126 for c in b)):
                flag.append(b)
                break
        else:
            continue
        break

print(b"".join(flag).decode())

Phải xử lý đoạn cuối khá rườm rà khi tìm ra được các $m$ đúng nữa vì có khá nhiều nghiệm đúng format nhưng mà không phải flag.
:::spoiler Flag
KCSC{I_hope_you_used_factor_and_discrete_log_to_solve_this_challenge_9f72b5a7608c076684b6ca6157}
:::
# rsabcde
Một bài nhiều cảm xúc
chall.py:

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from secret import flag, f4k3_fl4g
import sys , random
sys.set_int_max_str_digits(678)

assert bytes_to_long(flag) < 2**456

try: 
    a, b, c, d, e = [ int(input(f"{x} = ")) for x in "abcde" ]
    assert a > 0 
    assert 1111111111111111111 * a == c + 8888888888888888881 * e
    assert 9999999999999999961 * b == 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 * a
    assert d ** 2 == a + b
    if a.bit_length() < 234:
        prime = getPrime(512)
        rand = random.choice([a, b, c, d, e])
        n = prime * rand
        ct = pow(bytes_to_long(flag), e, n)
        print(f"n = {n}")
        print(f"ct = {ct}")
    else:
        print("(👉ﾟヮﾟ)👉", f4k3_fl4g.decode())

except: print("Nope!")

Challenge cho phép ta nhập các giá trị a, b, c, d, e tùy ý. Sau đó đem flag đi mã hóa bằng RSA. Theo phản xạ thì mình thử nhập e = 1 ngay lập tức. Vì flag có giá trị nhỏ hơn $2^{456}$ nên chắc chắc nhỏ hơn $N$, vậy flag sẽ bằng ciphertext. Nên ta chỉ cần $a, b, c, d$ thỏa mãn điều kiện để server trả về flag là lụm.
Để gửi được $e=1$, ta phải vượt qua các `assert`.
Ta cần tìm $a, b, c, d$ nguyên dương thỏa mãng các ràng buộc
Ràng buộc 1: Phương trình: $999999...961.b = 12584629...76.a$.
- Đặt $K_3 = 99...961, K_4 = 125...76$.Ta sẽ có:$$b = a \cdot \frac{K_4}{K_3}$$

Ràng buộc 2:Phương trình: $d^2 = a + b$.
Để giải ta thay thế $b$ vào:$$d^2 = a + a .\frac{K_4}{K_3} = a \left( \frac{K_3 + K_4}{K_3} \right)$$

Mình sẽ gọi phân số rút gọn của $\frac{K_3 + K_4}{K_3}$ là $\frac{t}{m}$.
Ta có$$d^2 = a . \frac{t}{m}$$
Để $d^2$ là số nguyên, thì $a$ phải triệt tiêu được mẫu số $m$.
Đặt $a = k . m$ (với $k$ là số nguyên).
Thay vào phương trình:$$d^2 = k .m .\frac{t}{m} = k \cdot t$$
Vậy mục tiêu lúc này của ta là Tìm $k$ sao cho biểu thức $k .t$ là một số chính phương.
Nhưng cuộc đời nó đau đớn hơn nhiều... mình không brute-force ra $k$ thỏa mãn dù đã thử rất lâu. Sau đó mình tìm thấy ánh sáng. Cách đơn giản nhất để $k . t$ là số chính phương mà không cần suy nghĩ nhiều là chọn luôn $k = t$.
Khi đó: $d^2 = t . t = t^2$ (Luôn đúng!).
Nhưng làm gì dễ ăn vậy. Khi làm vậy thì nhận được fake flag:

(👉ﾟヮﾟ)👉 KCSC{if you_know: you_know; assert 125846296924748283658579137337_________________________________________11896691_36181988787986574538_26426876 == p*p*q}

Tại sao vậy? vì nếu chọn $k = t$:$$a = k .m = t . m$$Biến t có độ lớn xấp xỉ $K_4$ (~115 chữ số), nên a sẽ cực kỳ lớn, vượt xa giới hạn 234 bit. Server nhảy vào nhánh `else` và in ra Fake Flag
Nhưng cũng vì cái fake flag này mà mình lại nhìn ra hướng đi, cái chuỗi số `125...26876` trong đó chính là $K_4$. Vậy tức là $K_4 = p^2.q$
Mà $t \approx K_4$. Nên ta có thể viết $$t = p^2 . q$$ Vậy để $t$ chính phương thì chỉ cần chọn $k = q$ để nhân vô là ra một số chính phương có dạng $(p.q)^2$. sau khi factor thì $q$ khoảng 166 bit nên a = 166 + 64 = 230 bit. Vừa khớp!
solve.py:

from pwn import *
from Crypto.Util.number import long_to_bytes
import math
import sys
from sympy.ntheory import factorint
#sys.set_int_max_str_digits(10000)

r = remote("67.223.119.69", 5010)
K1 = 1111111111111111111
K2 = 8888888888888888881
K3 = 9999999999999999961

K4 = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
g = math.gcd(K3, K4)
tu = (K3 + K4) // g
mau = K3 // g
factors = factorint(tu)
k = 1
for q, e in factors.items():
    #print(q, e)
    if e % 2 != 0:
        k *= q
a = k * mau
e = 1
while (K1 * a - K2 * e) <= 0:
    a *= 4 
b = (K4 * a) // K3
c = K1 * a - K2 * e
d = math.isqrt(a + b)
for var, val in zip("abcde", [a, b, c, d, e]):
    r.sendlineafter(f"{var} = ".encode(), str(val).encode())

r.recvuntil(b"ct = ")
ct = int(r.recvline().strip())
flag = long_to_bytes(ct)
print(flag.decode())

r.close()

> Nhớ phải tính trường hợp $c$ âm nữa, lúc đó phải tăng $a$ lên một khoảng là số chính phương vì như vậy $d$ mới là số nguyên
:::spoiler Flag
KCSC{f4c70rDB_15_4m4z1ng!}
:::
# to be continued

from sage.all import *
from Crypto.Util.number import getPrime, bytes_to_long, GCD
import random

flag = bytes_to_long(b"KCSC{???????????????????????????}")
rbits = lambda x: random.getrandbits(x)
p, q = getPrime(1024), getPrime(1024)
N = p*q
a, b = rbits(910), rbits(910)
assert GCD(a, b) == 1
phi = (p**3 - a) * (q**3 - b)
d = getPrime(1024)
e = pow(d, -1, phi)
c = pow(flag, e, N)

print("Welcome to KCSC's Recruiment")
print("Gifts: ")
print("a = ", a)
print("b = ", b)
print("N = ", N)
print("e = ", e)
print("c = ", c)

Challenge tính $\phi(n)$ theo cách khá dị với $\phi = (p^3 - a)(q^3 - b)$, rồi từ đó tạo $e$ dựa trên cái phi này.
Vậy giờ để giải mã $c$, ta cần tìm lại $p$ và $q$. Khi có $p, q$, ta có thể tính $d$ chuẩn $d = e^{-1} \pmod{(p-1)(q-1)}$ để lấy flag.
Mà ta nhận ra rằng $d$ chỉ khoảng 1024 bit, còn $N \approx 2^{2048}$, cụ thể thì $d < N^{3 . \frac{1}{6}}$, nên ta có thể áp dụng kỹ thuật liên phân số (Continued Fractions) để tìm $k$ và $d$.
Ta có:
$$e \cdot d \equiv 1 \pmod \phi$$
Tương đương:
$$e . d = 1 + k . \phi$$
Vậy $$\frac{e}{\phi} - \frac{k}{d} = \frac{1}{d \phi}$$
Mà ta biết $\phi$ xấp xỉ $N^3$ nên ta dùng $N^3$ để xấp xỉ:$$\frac{e}{N^3} \approx \frac{k}{d}$$
Điều kiện để $\frac{k}{d}$ là một hội tụ (convergent) của khai triển liên phân số $\frac{e}{N^3}$ là sai số phải đủ nhỏ. Với các kích thước trên, điều kiện này thỏa mãn.
Mà $$\phi = (p^3 - a)(q^3 - b) = p^3q^3 - b p^3 - a q^3 + ab$$
Nên $$\phi = N^3 - (b p^3 + a q^3 - ab)$$
Vậy ta có phương trình:
$$e . d = 1 + k(N^3 - b p^3 - a q^3 + ab)$$
$$e . d - 1 - k N^3 - k a b = -k (b p^3 + a q^3)$$
Mà $q = N/p$, nên:
$$e . d - 1 - k N^3 - k a b = -k \left( b p^3 + a \frac{N^3}{p^3} \right)$$
Tương đương
$$(e d - 1 - k N^3 - k a b) p^3 = -k b (p^3)^2 - k a N^3$$
Chuyển vế rồi đặt $X = p^3$ để tạo phương trình bậc 2:$$(k b) X^2 + (e d - k N^3 - k a b - 1) X + (k a N^3) = 0$$
Giải phương trình này ta sẽ tìm được $p_3$, từ đó tính được $\phi(n)$, bài toán kết thúc.

from sage.all import *
from Crypto.Util.number import long_to_bytes

a = 6304481321164246906567222989658765688045165275851071395205832715763220356466821410282955969161802841176445527338207576132114860045401544497249828909351039182182945402547214970223049123104061910807236829237608274748829008054249852723406591298824990323104235785926710097065678
b = 7999870125267969613672395287537327380867912777324346722357132031560297200201104156928904801090149293190711356687508094555199353750034650890008720565018729206913224039530232660373275511417192954417706309710650228654070214795786233986152367508554076009075490479812207855618459
N = 24081889277572802503659605826689926230027830719582767936363743502766482776099705960338212287859025560531973656731556156751481186678406820240771044210411774957806232749249860957895878890504459213322156810941197881824455880823042317347404688417969955356521338121436115650468863788924858088914981935069815044937563145675179199447446041774547448145057112430800054972872605835633576747583883285674457706771762988370139582185793239931790092003815695676798947934482380916291980085009315441662093814772584956990759521338343380951529181900596763825803370008245419318846198328641690031150992032307428945203841914049392112787033
e = 11050153015839883993161510135885787976039008082822382585575804877332676017418571820857988290309334210537161314550427816879212068985637953060885871602432684485487034375509379619789469792410393103838136020388501433382319198496971044588509979747359924647890043201124870325113772613514847295817375395027727381107822005050762060213230125451000959649050975147498113813336975434470468048553590716535948897232799351608157501900913776026264449516627219354423799349366099044820589167149211092110282765816684408405978492422462190786538301825408257216631933494464394828382376899323287315287973243876381980994428110571165021205398217777278825313093011741550183549639331123929016611159546502516316408659104164833466844920816898591821437607508224932520567325077419433023709911572576434857365505993059307741933102205523954940790045708534454784363255787058750009662319556437924605424640852945028220937879047842631235735134418121924586228479500537071667681030781582209438915903316316707019251330858088692416367956113483887988023423235436487473600194187120044620497634702200482106887128671850087321490311974939050362444303066126795966145296397377016134943620623131647797749418767732449622636419543202865842408588889412853603641329368785426334703041533454162178415167229266747016833148542628025339647321049686300229145201077528532971910019089492280243517721296838530796949829055923578715584168667973195521740594813691640838622696677680794584011285459260694486228084639063968847084787567170479050268786820660369450450781882574775405028286616546053143903706294406042325054355735859552547343917756174444977124800496069647281726872919803779970204586930394689812769802828483192801474434935520732430489482223645633398359373531176141794910809378994196853254737150627130658758517463777199549229895016654293830684067419466384677596715428945933720138801803468247516077733284618675
c = 8902578232624984411383722754874619024953250279805891829357397047274881749749711693192596092307853528587730589177614481442983584423981140117572924003770429665495872100397271876729790318687547951882889699514674500967917264418934982857003875266311412832039100198151364992410275296218572639061633726848133865363024117479523168920494186373486638535334075708542302849581459206163514282261518703853945190442837360895855359460519949894401579887910940646553403081219671212007000929291008947704019546704637268666663086394541789152216744224799090091941962088879750154156402189632368378336651988960439661260683085234566808439757

R = PolynomialRing(ZZ, 'x')
x = R.gen()
frac = Integer(e) / Integer(N)**3
convergents = frac.continued_fraction().convergents()
for conv in convergents:
    k = int(conv.numerator())
    d_fake = int(conv.denominator())
    if k == 0: continue
    if (e * d_fake - 1) % k != 0: continue
    phi_fake = (e * d_fake - 1) // k
    f = b * x**2 + (phi_fake - N**3 - a * b) * x + a * N**3
    roots = f.roots()
    for X, _ in roots:
        p = X.nth_root(3)
        if p**3 == X:
            if N % p == 0:
                q = N // p
                phi_real = (p - 1) * (q - 1)
                d_real = inverse_mod(e, phi_real)
                m = power_mod(c, d_real, N)
                print(long_to_bytes(int(m)).decode())
                exit()

::: spoiler Flag
KCSC{Be_water!My_friend}
:::

# Sign v2
Trong lúc diễn ra giải thì mình thấy bài này quen quen, cảm giác như từng làm ở đâu đó, sau đó mới nhớ nó là ver 2 của câu trong đề TTV 2024
chall.py:

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from os import *
from random import randint
from pwn import xor
from flag import flag
from base64 import b64decode


secret = urandom(16)

G = generator_256
p = G.order()

def genKeyPair():
    d = randint(1,p-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(sha256(b64decode(nonce)).digest(), secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

def challenge() :
    pubkey , privkey = genKeyPair()
    
    print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
    print("1 : Sign msg ")
    print("2 : Submit private key")
    nonces = []
    for _ in range(3) :
        try : 
            option = int(input("Option : "))
            if option == 1 :
                
                msg = (input("Enter your message: ")).encode()
                nonce = (input("Enter your nonce: ")).encode()
                
                if nonce in nonces :
                    print('Nope')
                    exit()
                    
                if len(nonces) > 0 : 
                    
                    for i in nonces :
                        if nonce in i or i in nonce:
                            print('Nope')
                            exit()
                       
                nonces.append(nonce)
                print(ecdsa_sign(msg,nonce,privkey))
                    
                            
            if option == 2 :
                
                d = int(input("Private key : "))
                print(nonces)
                if d == int(privkey.secret_multiplier) :
                    print(f'Very nice , here is your flag : {flag}')
                    exit()
                
                else :
                   
                    print(f'Wrong key , correct is {privkey.secret_multiplier}')
                    exit()
                    
        except :
            
            print("Not legal option")
            exit()
    print("Out of attemps !! ")    
challenge()    

Đây là challenge khai thác lỗi Nonce Reuse Attack trong thuật toán chữ ký số ECDSA.
> Về ECDSA, vì chưa học đến Elliptic Curve nên bài này mình chỉ là sử dụng các công thức có sẵn để tính chứ không thể hiểu về bản chất toán học đằng sau, may mắn là challenge này không cần hiểu quá sâu.

Nôm na là trong ECDSA, nếu bạn ký hai tin nhắn khác nhau ($msg_1, msg_2$) nhưng sử dụng cùng một số ngẫu nhiên $k$ (nonce), kẻ tấn công có thể tính toán ngược lại được khóa riêng tư (Private Key - $d$).

Tước tiên ta chú ý hàm tạo nonce của challenge như sau:

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(sha256(b64decode(nonce)).digest(), secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

Tức là giá trị $k$ phụ thuộc vào kết quả của b64decode(nonce). Vậy ta hoàn toàn thao túng được $k$ bằng cách nhập nonce.

Nhưng ta không được phép nhập lại nonce cũ vì challenge có cơ chế kiểm tra:

for i in nonces :
    if nonce in i or i in nonce:
        print('Nope')
        exit()

Tuy nhiên có một điều thú vị về hàm `base64.b64decode` trong Python: nó sẽ **bỏ qua các ký tự khoảng trắng** khi giải mã.
Vậy chiến thuật tấn công là:
Chúng ta sẽ gửi 2 nonce dạng chuỗi khác nhau để qua mặt sever, nhưng khi b64decode thì ra cùng một giá trị byte, nếu như vậy thì mới cùng một $k$.
Cụ thể
- Lần 1: Nonce string = "DQ== "
- Lần 2: Nonce string = "D Q=="

Hai chuỗi này không phải là con của nhau (thỏa mãn điều kiện), nhưng đều decode ra byte b'r' (do bỏ qua space), dẫn đến tạo ra cùng một $k$.
Và từ đây ta tính toán như sau:
Ta có 2 chữ ký $(r, s_1)$ và $(r, s_2)$ (lưu ý $r$ giống nhau vì $k$ giống nhau, $r$ là toạ độ x của điểm $k \times G$).
Công thức tạo chữ ký:$$s = k^{-1}(z + r \cdot d) \pmod n$$
Với 2 chữ ký:
- (1) $s_1 \cdot k \equiv z_1 + r \cdot d \pmod n$
- (2) $s_2 \cdot k \equiv z_2 + r \cdot d \pmod n$

Trừ (1) cho (2): $k(s_1 - s_2) \equiv z_1 - z_2 \pmod n$

Từ đó tìm được $k$:$$k \equiv (z_1 - z_2) \cdot (s_1 - s_2)^{-1} \pmod n$$

Sau khi có $k$, ta tính lại $d$ (Private Key):$$d \equiv (s_1 \cdot k - z_1) \cdot r^{-1} \pmod n$$
Có $d$ rồi thì gửi nó đi sẽ có flag.

solve.py:

from pwn import *
from hashlib import sha256
from ecdsa.ecdsa import generator_256
from Crypto.Util.number import bytes_to_long, inverse
from base64 import b64decode

HOST = '67.223.119.69'
PORT = 5009

p = remote(HOST, PORT)

n = generator_256.order()

def parse_signature(response):
    start = response.find(b'{')
    end = response.find(b'}') + 1
    json = response[start:end].decode()
    data = eval(json)
    return int(data['r'], 16), int(data['s'], 16)


msg1 = "DQ=="
msg2 = "Dq=="
nonce1 = "DQ=="
nonce2 = "D Q=="
p.sendlineafter(b'Option : ', b'1')
p.sendlineafter(b'message: ', msg1.encode())
p.sendlineafter(b'nonce: ', nonce1.encode())
out1 = p.recvuntil(b'}')
r1, s1 = parse_signature(out1)
p.sendlineafter(b'Option : ', b'1')
p.sendlineafter(b'message: ', msg2.encode())
p.sendlineafter(b'nonce: ', nonce2.encode())
out2 = p.recvuntil(b'}')
r2, s2 = parse_signature(out2)
z1 = bytes_to_long(sha256(b64decode(msg1)).digest())
z2 = bytes_to_long(sha256(b64decode(msg2)).digest())
s = (s1 - s2) % n
z = (z1 - z2) % n
k = (z * inverse(s, n)) % n
d = ((s1 * k - z1) * inverse(r1, n)) % n
p.sendlineafter(b'Option : ', b'2')
p.sendlineafter(b'Private key : ', str(d).encode())
p.interactive()

::: spoiler Flag
KCSC{no_more_byte_\x00_today}
:::
# umama
Một challenge khá hàih

import socket
import threading
import time
import random
from flag import FLAG
# =========================================================================
# I. LCG - Linear Congruential Generator
# =========================================================================
class LCG:
    def __init__(self, seed=None):
        self.M = 3287099835290195791649721107570004318267582246774226300213811649423225012170212287749142020192530464259481640735325781154239321190173754611921808393447501266888056440801327249770117062004226214495561535681369100056816111927528166402933420016083242583498654107351130511963025469986264222148916890724787070272803001
        self.A = 2894777803559679218352190554394546666288076241619396764815133803772055992385941101609673369526743001851311268818989398042025043757099501509707445437248873549911623395016719427960022056683203263457712425937702117698191301068614729419207159556006174347883149816514548460625672181804096655842375751872041822338728496
        self.C = 122
        self.seed = int(random.getrandbits(512)) % self.M if seed is None else seed % self.M
        
    def _next_seed(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed

    def uniform(self, min_val, max_val):
        normalized = self._next_seed() / self.M
        return min_val + normalized * (max_val - min_val)

# =========================================================================
# II. Uma Musume - Race Stats
# =========================================================================
class UmaMusume:
    def __init__(self, name, speed=50, stamina=50, skill_factor=50):
        self.name = name
        self.speed = speed
        self.stamina = stamina
        self.skill_factor = skill_factor
        self.odds = 0.0
        self.current_pos = 0.0
        self.current_speed = speed

    def update_position(self, lcg_gen, track_length):
        race_progress = self.current_pos / track_length
        stamina_drain = max(0, race_progress - 0.7)
        drain_reduction = self.stamina / 100.0
        speed_modifier = 1 - (stamina_drain * (1.5 - drain_reduction))
        self.current_speed = max(self.speed * 0.4, self.speed * speed_modifier)
        skill_multiplier = 2.5 if race_progress > 0.7 else 1.0
        random_boost = lcg_gen.uniform(0.95, 1.05 + self.skill_factor * 0.01 * skill_multiplier)
        micro_random = lcg_gen.uniform(0.99, 1.01)
        step_speed = self.current_speed * micro_random + random_boost
        self.current_pos += step_speed
        return step_speed

# =========================================================================
# III. Race Engine
# =========================================================================
class Race:
    def __init__(self, uma_list, track_length, lcg_gen):
        self.umas = uma_list
        self.track_length = track_length
        self.lcg_gen = lcg_gen
        self.max_steps = 1000

    def start_race(self):
        for uma in self.umas:
            uma.current_pos = 0.0
        step_count = 0
        race_over = False
        while not race_over and step_count < self.max_steps:
            step_count += 1
            for uma in self.umas:
                uma.update_position(self.lcg_gen, self.track_length)
                if uma.current_pos >= self.track_length:
                    race_over = True
        results = sorted(self.umas, key=lambda uma: uma.current_pos, reverse=True)
        return results

# =========================================================================
# IV. Betting System
# =========================================================================
class Betting:
    INITIAL_BALANCE = 10000.0
    FLAG_PRICE = 100000.0

    def __init__(self, umas, lcg_gen):
        self.umas = umas
        self.lcg_gen = lcg_gen
        self.balance = self.INITIAL_BALANCE
        self.current_bets = {}
        self.current_odds = {}

    def _calculate_odds(self):
        total_power = sum(u.speed + u.stamina + u.skill_factor for u in self.umas)
        self.current_odds = {}
        for uma in self.umas:
            uma_power = uma.speed + uma.stamina + uma.skill_factor
            base_odds = total_power / uma_power
            random_factor = self.lcg_gen.uniform(0.8, 1.2)
            uma.odds = max(1.5, base_odds * random_factor * 0.5)
            self.current_odds[uma.name] = uma.odds

    def show_odds(self):
        self._calculate_odds()
        msg = "\n" + "="*60 + "\n"
        msg += f"💰 WALLET: {self.balance:,.2f} Yen\n"
        msg += "-"*60 + "\n"
        msg += "📊 CURRENT ODDS:\n"
        for i, uma in enumerate(self.umas):
            msg += f"  [{i + 1:2d}] {uma.name:25s} | 1 to {uma.odds:6.2f} x\n"
        msg += "="*60 + "\n"
        return msg

    def place_bet(self, uma_index, amount):
        self.current_bets = {}
        try:
            uma_index = int(uma_index) - 1
            amount = float(amount)
        except:
            return False, "Invalid input"

        if not (0 <= uma_index < len(self.umas)):
            return False, f"Index must be 1 to {len(self.umas)}"

        if amount <= 0 or amount > self.balance:
            return False, "Invalid bet amount"

        uma_name = self.umas[uma_index].name
        self.balance -= amount
        self.current_bets[uma_name] = amount
        msg = f"\n✅ BET PLACED: {amount:,.2f} Yen on {uma_name}\n"
        msg += f"📉 Remaining: {self.balance:,.2f} Yen\n"
        return True, msg

    def process_winnings(self, winning_uma_name):
        total_winnings = 0.0
        msg = "\n" + "="*60 + "\n"
        msg += "🏆 RACE RESULTS 🏆\n"
        msg += "-"*60 + "\n"

        for uma_name, bet_amount in self.current_bets.items():
            winning_odds = self.current_odds.get(uma_name, 0)
            if uma_name == winning_uma_name:
                winnings = bet_amount * winning_odds
                self.balance += winnings
                total_winnings += winnings
                msg += f"🎉 WINNER! {uma_name}\n"
                msg += f"   Bet: {bet_amount:,.2f} Yen × {winning_odds:.2f} = +{winnings:,.2f} Yen\n"
            else:
                msg += f"❌ LOST: {uma_name} - {bet_amount:,.2f} Yen\n"

        msg += "-"*60 + "\n"
        msg += f"💵 TOTAL RETURN: +{total_winnings:,.2f} Yen\n"
        msg += f"💰 NEW BALANCE: {self.balance:,.2f} Yen\n"
        msg += "="*60 + "\n"
        return msg

# =========================================================================
# V. Socket Server
# =========================================================================
class CTFServer:
    def __init__(self, host='0.0.0.0', port=1337):
        self.host = host
        self.port = port
        self.server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

    def send(self, conn, msg):
        try:
            conn.sendall((msg + '\n').encode())
        except:
            pass

    def recv(self, conn, timeout=30):
        conn.settimeout(timeout)
        try:
            return conn.recv(1024).decode().strip()
        except:
            return None

    def handle_client(self, conn, addr):
        print(f"[+] Client connected: {addr}")
        
        umas = [
            UmaMusume("Special Week"),
            UmaMusume("Silence Suzuka"),
            UmaMusume("Gold Ship"),
            UmaMusume("Mejiro McQueen"),
            UmaMusume("Tokai Teio"),
            UmaMusume("Rice Shower"),
            UmaMusume("Symboli Rudolf"),
            UmaMusume("Kitasan Black"),
            UmaMusume("Satono Diamond"),
            UmaMusume("Daiwa Scarlet"),
        ]

        lcg_gen = LCG(seed=int(time.time() * 1000))
        betting_system = Betting(umas, lcg_gen)
        track_length = 500.0

        self.send(conn, "="*60)
        self.send(conn, "🌸 UMA MUSUME - CTF BETTING GAME 🌸")
        self.send(conn, f"Goal: Earn {betting_system.FLAG_PRICE:,.2f} Yen to buy the FLAG")
        self.send(conn, f"Start: {betting_system.INITIAL_BALANCE:,.2f} Yen")
        self.send(conn, "="*60)

        while True:
            self.send(conn, "\n" + "="*60)
            self.send(conn, f"💰 CURRENT BALANCE: {betting_system.balance:,.2f} Yen")
            self.send(conn, "-"*60)
            self.send(conn, "[1] 🏇 Start Race (Place Bet)")
            self.send(conn, "[2] 🏳️ Buy CTF Flag (100,000 Yen)")
            self.send(conn, "[3] 🚪 Exit Game")
            self.send(conn, "="*60)

            choice = self.recv(conn)
            if not choice:
                break

            if choice == '1':
                self.send(conn, betting_system.show_odds())
                self.send(conn, f"Uma Index [1-10] or 0 to cancel: ")
                uma_index = self.recv(conn)
                if not uma_index or uma_index == '0':
                    continue

                self.send(conn, "Amount to bet: ")
                amount = self.recv(conn)
                if not amount:
                    continue

                success, msg = betting_system.place_bet(uma_index, amount)
                self.send(conn, msg)

                if success:
                    race = Race(umas, track_length, lcg_gen)
                    results = race.start_race()
                    winning_name = results[0].name

                    self.send(conn, "\n" + "="*60)
                    self.send(conn, f"🥇 WINNER: {winning_name}")
                    self.send(conn, "🏁 RACE FINISHED - STANDINGS 🏁")
                    for rank, uma in enumerate(results):
                        if rank == 0:
                            self.send(conn, f"  #{rank + 1}: **{uma.name}**")
                        else:
                            self.send(conn, f"  #{rank + 1}: {uma.name}")
                    self.send(conn, "="*60)

                    self.send(conn, betting_system.process_winnings(winning_name))

            elif choice == '2':
                if betting_system.balance >= betting_system.FLAG_PRICE:
                    betting_system.balance -= betting_system.FLAG_PRICE
                    self.send(conn, "\n" + "="*60)
                    self.send(conn, "🎉 CONGRATULATIONS! 🎉")
                    self.send(conn, "="*60)
                    self.send(conn, f"🚩 FLAG: {FLAG}")
                    self.send(conn, f"💰 Remaining Balance: {betting_system.balance:,.2f} Yen")
                    self.send(conn, "="*60 + "\n")
                    break
                else:
                    need = betting_system.FLAG_PRICE - betting_system.balance
                    self.send(conn, f"\n❌ NOT ENOUGH MONEY!")
                    self.send(conn, f"   You need: {need:,.2f} more Yen")
                    self.send(conn, f"   Current: {betting_system.balance:,.2f} Yen")
                    self.send(conn, f"   Target:  {betting_system.FLAG_PRICE:,.2f} Yen\n")

            elif choice == '3':
                self.send(conn, "\n👋 Thank you for playing! Sayonara!")
                break
            else:
                self.send(conn, "⚠️ Invalid choice! Please try again.")

        conn.close()
        print(f"[-] Client disconnected: {addr}")

    def start(self):
        self.server.bind((self.host, self.port))
        self.server.listen(5)
        print(f"[*] Server listening on {self.host}:{self.port}")

        try:
            while True:
                conn, addr = self.server.accept()
                thread = threading.Thread(target=self.handle_client, args=(conn, addr))
                thread.daemon = True
                thread.start()
        except KeyboardInterrupt:
            print("\n[*] Server shutting down...")
        finally:
            self.server.close()

if __name__ == "__main__":
    server = CTFServer(host='0.0.0.0', port=1337)
    server.start()

Challenge liên quan đến PRNG (Bộ sinh số giả ngẫu nhiên).

Máy tính là thiết bị logic, nó không biết cách tạo ra sự ngẫu nhiên thực sự. Nó dùng các thuật toán toán học để tạo ra các dãy số trông có vẻ ngẫu nhiên, gọi là PRNG (Pseudo-Random Number Generator).
PRNG cần một giá trị đầu vào gọi là Seed .Nếu Seed giống nhau thì giá trị các số sinh ra hoàn toàn giống nhau.
Ta chú ý rằng seed ở challenge này được chọn như sau:

lcg_gen = LCG(seed=int(time.time() * 1000))

Tức là sinh seed ngẫu nhiên dựa trên thời gian, và thời gian thì là một đại lượng mà ta hoàn toàn có thể đoán được, nó sẽ loanh quanh khoảng thời gian mà ta kết nói tới sever.
Challenge tự viết một class LCG. Công thức của nó là:$$X_{i+1} = (A \cdot X_{i} + C) \pmod M$$$A, C, M$: Là các hằng số công khai.
$X$: seed.
Vì $A, C, M$ đều lộ, nếu ta biết $X$ seed hiện tại thì ta tính được toàn bộ tương lai của dãy số. Chỉ cần brute-force khoảng thời gian xung quanh thời gian ta kết nói với sever.
Trước đó ta phải lấy danh sách (s_odds) rồi mới tìm seed. Vì odds là giá trị đầu tiên được sinh ra từ seed, ta sẽ phải dùng dữ liệu này để đối chiếu xem seed mình đoán có đúng không.
Khi tìm được seed thì ta chạy hàm Race() để cái seed nó biến đổi sang trạng thái mới, mà ta biết con ngựa nào thắng luôn rồi thì cứ all in thôi =))), cứ lập lại cho đến khi đủ 1000000 Yên (chắc là code lỗi vì mình thấy trong source sever thì 100000 Yên là đủ).
> Lưu ý là phải copy y nguyên các class LCG, Uma, Race qua để đúng logic code

from pwn import *
import re
import time

class LCG:
    def __init__(self, seed=None):
        self.M = 3287099835290195791649721107570004318267582246774226300213811649423225012170212287749142020192530464259481640735325781154239321190173754611921808393447501266888056440801327249770117062004226214495561535681369100056816111927528166402933420016083242583498654107351130511963025469986264222148916890724787070272803001
        self.A = 2894777803559679218352190554394546666288076241619396764815133803772055992385941101609673369526743001851311268818989398042025043757099501509707445437248873549911623395016719427960022056683203263457712425937702117698191301068614729419207159556006174347883149816514548460625672181804096655842375751872041822338728496
        self.C = 122
        self.seed = seed % self.M
    def _next(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed
    def uniform(self, min_v, max_v):
        return min_v + (self._next() / self.M) * (max_v - min_v)

class Uma:
    def __init__(self, name, spd=50, sta=50, sk=50):
        self.name, self.spd, self.sta, self.sk = name, spd, sta, sk
        self.pos, self.cur_spd = 0.0, spd
    def update(self, lcg, length):
        prog = self.pos / length
        drain = max(0, prog - 0.7)
        mod = 1 - (drain * (1.5 - self.sta / 100.0))
        self.cur_spd = max(self.spd * 0.4, self.spd * mod)
        sk_mul = 2.5 if prog > 0.7 else 1.0
        bst = lcg.uniform(0.95, 1.05 + self.sk * 0.01 * sk_mul)
        mic = lcg.uniform(0.99, 1.01)
        self.pos += self.cur_spd * mic + bst

class Race:
    def __init__(self, umas, length, lcg):
        self.umas, self.len, self.lcg = umas, length, lcg
    def run(self):
        for u in self.umas: u.pos = 0.0
        step = 0
        while step < 1000:
            step += 1
            done = False
            for u in self.umas:
                u.update(self.lcg, self.len)
                if u.pos >= self.len: done = True
            if done: break
        return sorted(self.umas, key=lambda x: x.pos, reverse=True)


r = remote('67.223.119.69', 5008)
NAMES = ["Special Week", "Silence Suzuka", "Gold Ship", "Mejiro McQueen", "Tokai Teio", "Rice Shower", "Symboli Rudolf", "Kitasan Black", "Satono Diamond", "Daiwa Scarlet"]
t0, gen = int(time.time()*1000), None

while True:
    buf = r.recvuntil(b"Exit Game").decode()
    bal = float(re.search(r"BALANCE:\s*([\d,]+\.\d+)", buf).group(1).replace(',', ''))
    
    if bal >= 1000000: 
        r.sendline(b'2')
        print(r.recvall().decode())
        break

    r.sendline(b'1')
    dat = r.recvuntil(b"cancel: ").decode()
    s_odds = re.findall(r"1 to\s+(\d+\.\d+)", dat)

    umas = [Uma(n) for n in NAMES]
    tot = sum(u.spd + u.sta + u.sk for u in umas)
    
    if not gen:
        for i in range(-5000, 5000):
            l = LCG(t0+i)
            if [f"{max(1.5, (tot/(u.spd+u.sta+u.sk))*l.uniform(0.8,1.2)*0.5):.2f}" for u in umas] == s_odds:
                gen = l
                break
    else: 
        [gen.uniform(0.8, 1.2) for _ in umas]
    win = Race([Uma(n) for n in NAMES], 500.0, gen).run()[0].name
    r.sendline(str(NAMES.index(win)+1).encode())
    r.sendlineafter(b"bet: ", str(int(bal)).encode())

:::spoiler Flag
KCSC{3m4m4}
:::
# theMidnIghTMan
chall.py:

from Crypto.Cipher import AES
import hashlib, os, time

class x3AES:
    def __init__(self, key1, key2, key3):
        self.key1 = hashlib.md5(key1).digest()
        self.key2 = hashlib.md5(key2).digest()
        self.key3 = hashlib.md5(key3).digest()
        self.secret = os.urandom(16)
    
    def pad(self, data, block_size):
        length = len(data)

        if length % block_size == 0:
            return data

        pad_len = block_size - (length % block_size)

        return data + bytes([pad_len]) * pad_len

    def encrypt(self, plaintext):
        padded_data = self.pad(plaintext, AES.block_size)
        iv = os.urandom(AES.block_size)              
                                    
        cipher1 = AES.new(self.key1, AES.MODE_OFB, iv)
        enc1 = cipher1.encrypt(padded_data)

        cipher2 = AES.new(self.key2, AES.MODE_CBC, self.secret)
        enc2 = cipher2.encrypt(enc1)

        cipher3 = AES.new(self.key3, AES.MODE_ECB)
        enc3 = cipher3.encrypt(enc2)

        return iv + enc3

    def decrypt(self, ciphertext):
        iv = ciphertext[:AES.block_size]
        enc3 = ciphertext[AES.block_size:]

        cipher3 = AES.new(self.key3, AES.MODE_ECB)
        dec3 = cipher3.decrypt(enc3)

        cipher2 = AES.new(self.key2, zAES.MODE_CBC, self.secret)
        dec2 = cipher2.decrypt(dec3)

        cipher1 = AES.new(self.key1, AES.MODE_OFB, iv)
        dec1 = cipher1.decrypt(dec2)

        return dec1

class Challenge:
    def __init__(self):
        self.flag = b"KCSC{??????????????????????????????????????????}"
        self.key = os.urandom(9)
        self.key1 = self.key[:3]
        self.key2 = self.key[3:6]
        self.key3 = self.key[6:]
        self.cipher = x3AES(self.key1, self.key2, self.key3)
        self.banner = """
                           ;                                                              
                           ED.                                                            
                           E#Wi        L.                                                 
                       t   E###G.      EW:        ,ft t           .Gt .    .              
            ..       : Ej  E#fD#W;     E##;       t#E Ej         j#W: Di   Dt    GEEEEEEEL
           ,W,     .Et E#, E#t t##L    E###t      t#E E#,      ;K#f   E#i  E#i   ,;;L#K;;.
          t##,    ,W#t E#t E#t  .E#K,  E#fE#f     t#E E#t    .G#D.    E#t  E#t      t#E   
         L###,   j###t E#t E#t    j##f E#t D#G    t#E E#t   j#K;      E#t  E#t      t#E   
       .E#j##,  G#fE#t E#t E#t    :E#K:E#t  f#E.  t#E E#t ,K#f   ,GD; E########f.   t#E   
      ;WW; ##,:K#i E#t E#t E#t   t##L  E#t   t#K: t#E E#t  j#Wi   E#t E#j..K#j...   t#E   
     j#E.  ##f#W,  E#t E#t E#t .D#W;   E#t    ;#W,t#E E#t   .G#D: E#t E#t  E#t      t#E   
   .D#L    ###K:   E#t E#t E#tiW#G.    E#t     :K#D#E E#t     ,K#fK#t E#t  E#t      t#E   
  :K#t     ##D.    E#t E#t E#K##i      E#t      .E##E E#t       j###t f#t  f#t      t#E   
  ...      #G      ..  E#t E##D.       ..         G#E E#t        .G#t  ii   ii       fE   
           j           ,;. E#t                     fE ,;.          ;;                 :   
                           L:                       ,                                     
"""

    def print_banner(self):
        for line in self.banner.split("\n"):
            print(line)
            time.sleep(0.1)
    
    def main(self):
        prefix = b'Midnight is coming. Stay awake!!'
        print(prefix)

        while True:
            option = input("Enter your option:\n1. Encrypt\n2. Decrypt\n3. Get Flag\n> ")
            try:
                if option == "1":
                    plaintext = bytes.fromhex(input("Enter plaintext (hex): "))
                    ciphertext = self.cipher.encrypt(plaintext)
                    print("Ciphertext: ", ciphertext.hex())
                elif option == "2":
                    iv = bytes.fromhex(input("Enter IV (hex): "))
                    assert len(iv) == 16
                    ciphertext = bytes.fromhex(input("Enter ciphertext (hex): "))
                    plaintext = self.cipher.decrypt(iv + prefix + ciphertext)
                    print("Plaintext: ", plaintext.hex())
                elif option == "3":
                    key_input = bytes.fromhex(input("Enter the key (hex): "))
                    if key_input == self.key:
                        print("Flag:", self.flag.decode())
                    else:
                        print("Wrong key!")
                        break
                else:
                    break
            except:
                print("Don't pwn me!")
                break

if __name__ == "__main__":
    challenge = Challenge()
    challenge.print_banner()
    challenge.main()

Một challenge liên quan đến AES, (cụ thể là về MITM) vì khóa quá nhỏ.
Quá trình giải mã của server: Nhận đầu vào: IV (16 bytes) và Ciphertext (do ta gửi). Server thực hiện giải mã chuỗi IV + Prefix + Ciphertext qua 3 lớp:
- Lớp 3 (Key3 - ECB): AES-ECB.
- Lớp 2 (Key2 - CBC): AES-CBC (dùng secret làm IV riêng).
- Lớp 1 (Key1 - OFB): AES-OFB (dùng IV ta gửi).
ta sẽ tấn công ngược từ lớp trong cùng ra, theo thứ tự: Key1 $\rightarrow$ Key3 $\rightarrow$ Key2.

Key1: OFB: Đặc điểm của OFB là nó tạo ra một dòng Keystream chỉ dựa vào Key và IV.
$$P = C \oplus Keystream(Key, IV)$$
Lỗ hổng ở đây là hàm `decrypt` của server trả về Plaintext cuối cùng.
Nếu ta gửi 2 yêu cầu giải mã với cùng một phần Ciphertext nhưng IV khác nhau:
=> Dữ liệu đi vào Lớp 2 và Lớp 3 là giống hệt nhau => Đầu ra sau khi qua Lớp 3 và Lớp 2 là một chuỗi cố định (gọi là Interm).Sự khác biệt ở Plaintext cuối cùng chỉ do Keystream của Key1 tạo ra.
Vậy khi gửi `IV_A`, thì nhận được `Plaintext_A`.
Gửi `IV_B`, nhận được `Plain_B`.
Lấy (1) XOR (2), ta sẽ thu được: $$Plain\_A \oplus Plain\_B = Keystream(K1, IV\_A) \oplus Keystream(K1, IV\_B)$$
Mà Ta biết `Plain_A`, `Plain_B`, `IV_A`, `IV_B`.
Do đó ta brute-force từ 0 đến $2^{24}$ để thử mọi $K_1$. Nếu $K_1$ nào sinh ra hai keystream thỏa mãn phương trình trên thì dó là Key1 đúng.

Key 3:
Sau khi có key1, ta loại bỏ được lớp OFB.Giờ ta tấn công vào ECB và CBC.Ta chọn payload sao cho input đầu vào có cấu trúc lặp lại: `Block1 | Block2 | Block2`.
- `Prefix` = `Midnight is coming. Stay awake!! `(32 bytes).
- `Block1` (Prefix[0:16]): `Midnight is comi`
-`Block2` (Prefix[16:32]): `ng. Stay awake!!`

Vậy ta gửi payload là Prefix[16:32] (chính là Block2).
Sẽ nhận được p3. Dùng key1 tìm được ở bước 1 để tính `W` (Đây là output của lớp CBC.
$$W = P_3 \oplus Keystream(K1, IV_3)$$
Xét 2 block của `W` là `W2` (ứng với Prefix Block 2) và `W3` (ứng với Payload ta gửi):
Gọi $v_1 = D_{K3}(Block1)$ và $v_2 = D_{K3}(Block2)$.
Theo quy tắc giải mã CBC:
- Tại vị trí 2: $W_2 = D_{K2}(v_2) \oplus v_1$
- Tại vị trí 3: $W_3 = D_{K2}(v_2) \oplus v_2$ (Vì input của block 3 là $v_2$, và block trước đó (ciphertext) cũng là $v_2$)

Vậy giờ ta lấy $W_2 \oplus W_3$:
$$(D_{K2}(v_2) \oplus v_1) \oplus (D_{K2}(v_2) \oplus v_2) = v_1 \oplus v_2$$$$W_2 \oplus W_3 = D_{K3}(Block1) \oplus D_{K3}(Block2)$$

Đến đây Brute-force key3 sao cho phương trình đó bằng thôi

Key2:
Ta đã có key1 và key3.Ta xét CBC tại Block 2 để tìm key2.
Dùng key3 đã tìm được, tính giá trị `v1` và `v2` (đầu ra của lớp ECB).
$$\begin{aligned}
v_1 &= D_{K_3}(B_1) \\
v_2 &= D_{K_3}(B_2)
\end{aligned}$$
Thì lúc này :$$W_2 = D_{K2}(v_2) \oplus v_1$$Suy ra:$$D_{K2}(v_2) = W_2 \oplus v_1$$
Rồi ta brute-force tìm key2 sao cho khi giải mã AES (ECB) khối $v_2$ thì kết quả bằng $W_2 \oplus v_1$.
solve.py:

from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor as xor
import hashlib, os
from tqdm import tqdm

r = remote('67.223.119.69', 5011)
PREFIX = b'Midnight is coming. Stay awake!!'
B1, B2 = PREFIX[:16], PREFIX[16:32]

def oracle(iv, ct=b''):
    r.sendlineafter(b'> ', b'2')
    r.sendline(iv.hex().encode())
    r.sendline(ct.hex().encode())
    r.recvuntil(b':  ')
    return bytes.fromhex(r.recvline().strip().decode())

def crypt(k_bytes, data, iv=None):
    key = hashlib.md5(k_bytes).digest()
    if iv: return AES.new(key, AES.MODE_OFB, iv).decrypt(b'\x00' * len(data))
    return AES.new(key, AES.MODE_ECB).decrypt(data)



iv1, iv2 = os.urandom(16), os.urandom(16)
p1, p2 = oracle(iv1), oracle(iv2)
tgt_k1 = xor(p1, p2)

k1 = next(k.to_bytes(3,'big') for k in tqdm(range(1<<24)) 
          if xor(crypt(k.to_bytes(3,'big'), p1, iv1), 
                 crypt(k.to_bytes(3,'big'), p2, iv2)) == tgt_k1)



iv3 = os.urandom(16)
p3 = oracle(iv3, B2) 
w = xor(p3, crypt(k1, p3, iv3))
w2, w3 = w[16:32], w[32:48]
tgt_k3 = xor(w2, w3)

k3 = next(k.to_bytes(3,'big') for k in tqdm(range(1<<24))
          if xor(crypt(k.to_bytes(3,'big'), B1), 
                 crypt(k.to_bytes(3,'big'), B2)) == tgt_k3)


v1 = crypt(k3, B1)
v2 = crypt(k3, B2)
tgt_k2 = xor(w2, v1)

k2 = next(k.to_bytes(3,'big') for k in tqdm(range(1<<24))
          if crypt(k.to_bytes(3,'big'), v2) == tgt_k2)

full_key = k1 + k2 + k3
print(f"[+] Full Key: {full_key.hex()}")
r.sendlineafter(b'> ', b'3')
r.sendline(full_key.hex().encode())
print(r.recvall().decode())

:::spoiler Flag
KCSC{a_formal_gift_to_honor_you_e5bb1bb281165c0}
:::
# 五六七
Một challenge quá ảo

chall.py:

from Crypto.Util.number import isPrime
import random

FLAG = open('flag.txt', 'rb').read()
p = int(input("Choose p > "))
if not isPrime(p) or p.bit_length() < 512:
    print("Fail")
    exit(1)
x = random.getrandbits(128)

def f(x):
    res = 0
    for i in range(7):
        if i==5: continue
        res += pow(i, x, p)
        res %= p
    return res

res = f(x)
print(res)
guess = int(input("guess x = "))
if guess == x:
    print(f"Here is your flag: {FLAG}")    
else:
    print('false')                                                                         

Ta được chọn một số nguyên tố $p$, ($p$ phải lớn hơn 512 bit)
Và ta có hàm số được định nghĩa là $f(x) = 1 + 2^x + 3^x + 4^x + 6^x \pmod p$.
Mục tiêu là tìm $x$ (128 bit) khi biết $f(x)$.
Ta sẽ dùng DLP để giải bài này:
Ta sẽ chọn số mũ $a$ sao cho $p = 2^a - 3$ là một số nguyên tố.Khi đó, ta có đẳng thức quan trọng:$$2^a \equiv 3 \pmod p$$
Điều này có nghĩa là trong trường $\mathbb{Z}_p$, số $3$ có thể được biểu diễn dưới dạng lũy thừa của $2$.
Nên ta thay $3 \equiv 2^a$ vào phương trình $f(x)$:
$$f(x) \equiv 1 + 2^x + (2^a)^x + (2^x)^2 + (2 \cdot 2^a)^x \pmod p$$
Đặt $Y = 2^x$, phương trình trở thành một đa thức theo biến $Y$:$$f(x) \equiv 1 + Y + Y^a + Y^2 + Y^{a+1} \pmod p$$
Hay:$$Y^{a+1} + Y^a + Y^2 + Y + (1 - \text{res}) \equiv 0 \pmod p$$.

Bậc của đa thức này chỉ khoảng 512. Nên có thể tìm nghiệm của đa thức này trong trường $\mathbb{Z}_p$ rất nhanh chóng.
Sau khi tìm được nghiệm $Y$, ta có bài toán Logarit rời rạc: $2^x \equiv Y \pmod p$.
Để giải bài toán này dễ dàng, ta cần $p-1$ có nhiều ước số nguyên tố nhỏ (smooth).
Ta có $p-1 = 2^a - 4 = 4(2^{a-2} - 1)$.
Dạng số $2^k - 1$ rất dễ phân tích thừa số. Nếu ta chọn $a-2$ là một số có nhiều ước số nhỏ, $p-1$ sẽ có nhiều thừa số nguyên tố nhỏ.
Ta các thừa số nguyên tố nhỏ sao cho tích của chúng lớn hơn $2^{128}$ (kích thước của $x$), sau đó dùng thuật toán Pohlig-Hellman và CRT để tìm $x$.
solve.py:

from pwn import *
from sage.all import *
HOST = '67.223.119.69'
PORT = 5012

def find_vulnerable_p():
    for u in range(512, 1200):
        target = 2**u - 3
        if not is_pseudoprime(target):
            continue
        if is_prime(target):
            p = target
            order = p - 1
            try:
                factors_small = factor(order, limit=1000000) 
                smooth_part = 1
                for f, e in factors_small:
                    smooth_part *= (f ** e)
                
                if smooth_part > 2**128:
                    return p, u
            except:
                continue
    exit(1)

def solve():
    p, u = find_vulnerable_p()
    r = remote(HOST, PORT)
    print(r.recvuntil(b"Choose p > ").decode())
    r.sendline(str(p).encode())

    res = None
    while True:
        line = r.recvline(timeout=5).strip()
        if not line:
            continue
        if b"Fail" in line:
            return
        if line.isdigit():
            res = int(line)
            break
    F = GF(p)
    P_ring = PolynomialRing(F, 'y')
    y = P_ring.gen()
    poly = y**(u+1) + y**u + y**2 + y + (1 - res)
    roots = poly.roots()
    real_x = None
    def check_x(x_val):
        ans = 0
        for i in [0, 1, 2, 3, 4, 6]:
            ans += pow(i, x_val, p)
        return ans % p == res

    for root, mult in roots:
        val_Y = root
        if val_Y == 0: continue
        try:
            x = discrete_log(val_Y, F(2))
            if check_x(x):
                real_x = x
                break
        except ValueError:
            continue
            
    if real_x is not None:
        r.sendlineafter(b"guess x = ", str(real_x).encode())
        print("\n" + r.recvall().decode())
if __name__ == "__main__":
    solve()

:::spoiler Flag
KCSC{why_do_you_choose_crypto?}
:::
# e
Do chưa học về Latice nên có lẽ những kiến thức mình viết dưới đây sẽ có nhiều sai sót

chall.py:

flag = ???


def hash(msg: bytes) -> bytes:
    msg = list( map( int, bin( int((msg).hex(), 16) )[2:] ) )
    g = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 
    n = 36
    for b in msg:
        n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)
    return (n)
print(hash(flag), len(flag))
# 4733050325257322080995332543647525767201053028813565191926008882515250832618947947748792937964480829322550895675027130098198538016461241391725598109040829 28

Một challenge quá ngắn gọn, nhưng độ khó thì là cao nhất, ta được cung cấp một hàm `hash`, và giá trị của flag sau khi đi qua hàm đó kèm theo với đó là ta biết độ dài flag = 28 byte.
Ta phân tích hàm `hash` trước:

def hash(msg: bytes) -> bytes:
    msg = list( map( int, bin( int((msg).hex(), 16) )[2:] ) )
    g = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 
    n = 36
    for b in msg:
        n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)
    return (n)

Đầu tiên flag của chúng ta sẽ được chuyển đổi thành một chuỗi nhị phân. Vậy theo lý thuyết thì nếu flag là 28 byte, thì nó sẽ được chuyển thành một chuỗi bit có độ dài $28.8 = 224$ bit.
Đúng không? Mình đã sai lầm khi nghĩ như vậy và đã thất bại trong việc giải bài này trong lúc diễn ra giải.
Thật sự thì chuỗi bit chúng ta chỉ có 223 bit thôi, vì hàm `bin`() trong python nó loại bỏ đi chữ số 0 ở đầu. Ví dụ như ta biết byte đầu flag là chữ `K`, thì nhị phân của nó là `01001011`, khi qua `int()`, `bin()`. Nó sẽ trở thành `1001011`. Đây là lý do độ dài chuỗi bit là 223 thay vì 224 =))).
Kết quả: Flag bây giờ không còn là chuỗi ký tự, mà là một vector các biến nhị phân $\vec{b} = [b_0, b_1, \dots, b_{L-1}]$.
Giờ hãy phân tích công thức biến đổi

n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)

Đoạn `int(3 if b else 6)` nó quyết định giá trị cộng thêm dựa trên bit $b$. Tức là:
- Nếu $b=1 \rightarrow$ cộng 3.
- Nếu $b=0 \rightarrow$ cộng 6.
Còn `& ((1 << 512) - 1)` tức là giữ lại 512 bit thấp, nó tương đương với việc đem mod cho $2^{512}$
Gọi:
- $n_k$: Giá trị hash ở bước thứ $k$.
- $b_k$: Bit thứ $k$ của input ($b_k \in \{0, 1\}$).
- $M = 2^{512}$: Modulo của phép toán.
- $\Delta_k$: Giá trị được cộng vào $n$.
- Nếu $b_k = 1 \implies \Delta_k = 3$.
- Nếu $b_k = 0 \implies \Delta_k = 6$.

Để tấn công bằng toán học, ta không thể dùng câu lệnh if/else. Ta phải chuyển nó một cái công thức chung tổng quát nào đó, sau khi mò mẫm, mình tìm ra được công thức tương đương:
$$\Delta_k = 6 - 3b_k$$
Thử lại:
$b=1: 6 - 3.1 = 3$ (Đúng).
$b=0: 6 - 3.0 = 6$ (Đúng).
Giờ ta phân tích xem trạng thái $n$ thay đổi thế nào qua từng vòng lặp. Gọi $L$ là tổng số bit.

Lần 1 ($b_0$):$$n_1 = g \cdot (n_0 + \Delta_0)$$
Lần 2 ($b_1$):$$n_2 = g \cdot (n_1 + \Delta_1)$$
Ta thay $n_1$ vào:$$n_2 = g \cdot ( [g(n_0 + \Delta_0)] + \Delta_1 ) = g^2 n_0 + g^2 \Delta_0 + g^1 \Delta_1$$
Và tương tự như vậy lần 3 sẽ là:
$$n_3 = g \cdot (n_2 + \Delta_2) = g^3 n_0 + g^3 \Delta_0 + g^2 \Delta_1 + g^1 \Delta_2$$
Tổng quát lên $L$ vòng:
$$H \equiv n_0 \cdot g^L + \sum_{i=0}^{L-1} \Delta_i \cdot g^{L-i} \pmod M$$
Giờ thay $\Delta_i = 6 - 3b_i$ vào:$$H \equiv n_0 \cdot g^L + \sum_{i=0}^{L-1} (6 - 3b_i) \cdot g^{L-i} \pmod M$$
Ta cần phải tách ẩn qua một bên, hằng số qua một bên:
$$H \equiv n_0 g^L + \sum_{i=0}^{L-1} 6 \cdot g^{L-i} - \sum_{i=0}^{L-1} 3 \cdot g^{L-i} \cdot b_i \pmod M$$
$$\sum_{i=0}^{L-1} (3 \cdot g^{L-i}) \cdot b_i \equiv C - H \pmod M$$
Đặt hệ số $c_i = 3 \cdot g^{L-i}$ và $Target = (C - H) \pmod M$, ta có phương trình tuyến tính có 2 nghiệm $0/1$:$$\sum_{i=0}^{L-1} c_i \cdot b_i \equiv Target \pmod M$$.
Và sau khi tham khảo wu của anh [Le Ha](https://hackmd.io/@at20n0118/Hy5LBsS51l#Knapsack-Problem) và anh [@nomorecaffeine](https://hackmd.io/@nomorecaffeine/r1xstVfxC#II-Knapsack-Problem), mình biết rằng. Phương trình trên chính là bài toán Knapsack (The Subset Sum Problem).
Tức là:
- Ta có một tập hợp các số $c_0, c_1, \dots, c_{222}$.
- Ta cần tìm cách chọn một số phần tử trong đó (tương ứng $b_i=1$ là chọn, $b_i=0$ là không chọn).
- Sao cho tổng của chúng bằng $Target$ (theo modulo $M$).

Bài toán này về lý thuyết là NP-Hard. Tuy nhiên, trong mật mã học, nó dễ bị giải nếu mật độ (density) thấp.
Mật độ được tính bằng:$$d = \frac{N}{\log_2(M)}$$
Trong bài này: $N = 223$, $\log_2(M) = 512$.

Thì cái mật độ này quá lớn rồi, phải tìm cách giảm số ẩn lại. Sau khi được các anh hint, thì có 2 cách để giảm số lượng ẩn lại, đầu tiên là biết format của flag là "KCSC{}" thì ta đã giảm được $47$ ẩn. Và chúng ta còn giảm thêm được 22 ẩn nữa nhờ giả định bit đầu của các byte ẩn là 0, vì nó là ký tự Ascii in được, ta đã đưa được tổng số ẩn xuống 154.
Vậy lúc này mật độ là 154/512 thì $d \approx 0.3$. Với mật độ này, thuật toán Lattice Reduction (LLL/BKZ) giải rất tốt.

Để giải bài toán Knapsack, ta chuyển nó về bài toán tìm vector ngắn nhất (Shortest Vector Problem - SVP) trong lưới.
Ta xây dựng một ma trận cơ sở $B$ để biểu diễn mối quan hệ tuyến tính này. Mục tiêu là tìm một vector $\mathbf{v}$ là tổ hợp tuyến tính của các hàng trong $B$, sao cho $\mathbf{v}$ thật ngắn.

Ma trận $B$ có kích thước $(N+2) \times (N+2)$:$$B = \begin{bmatrix}
1 & 0 & \dots & 0 & K \cdot c_0 \\
0 & 1 & \dots & 0 & K \cdot c_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \dots & 1 & K \cdot c_{N-1} \\
0 & 0 & \dots & 0 & K \cdot M \\
0 & 0 & \dots & 0 & -K \cdot Target
\end{bmatrix}$$
Trọng số $K$ ở đây Là một số lớn (ví dụ $2^{256}$). Ta nhân cột này với $K$ để ép nặng bất kỳ vector nào không thỏa mãn phương trình tổng. Nếu tổng $\sum c_i b_i - Target \neq 0$, thì giá trị ở cột cuối sẽ rất lớn (do nhân $K$), vector sẽ rất dài và thuật toán BKZ sẽ bỏ qua nó.

Khi nhân ma trận $B$ với vector nghiệm $\mathbf{x} = (b_0, b_1, \dots, b_{N-1}, k, 1)$, ta mong muốn thu được vector kết quả $\mathbf{v}_{short}$:$$\mathbf{v}_{short} = (b_0, b_1, \dots, b_{N-1}, 0)$$Phần đầu: Các bit $0$ hoặc $1$ của Flag.
Phần cuối: Số $0$ (Nghĩa là $\sum c_i b_i + kM - Target = 0$).
Và mình được hint là đùng BKZ để giải, vì BKZ mạnh hơn LLL. Nó chia lưới thành các khối nhỏ (blocks) kích thước $\beta$ và thực hiện tìm kiếm vector ngắn nhất (SVP) trên khối đó, sau khi chạy thử với nhiều trường hợp, mình thấy đặt block_size là 22 thì lý tưởng nhất (mình nghĩ vậy)
solve.sage:

from sage.all import *
from Crypto.Util.number import *
import binascii
import time

F = Zmod(2**512)
h_val = F(4733050325257322080995332543647525767201053028813565191926008882515250832618947947748792937964480829322550895675027130098198538016461241391725598109040829)
g = F(35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759)
n0 = F(36)
M = 2**512
total_bits = 223 

PR = PolynomialRing(F, 'b', total_bits, implementation='generic')
VARS = PR.gens()
n = n0

for i in range(total_bits):
    n = g * (n + (6 - 3*VARS[i]))

f = n - h_val 
known_bits_format = bin(bytes_to_long(b"KCSC{"))[2:] 
known_bits_end = bin(bytes_to_long(b"}"))[2:].zfill(8)
values = {}


for i in range(len(known_bits_format)):
    values[VARS[i]] = int(known_bits_format[i])


for i in range(len(known_bits_end)):
    values[VARS[-(i+1)]] = int(known_bits_end[-(i+1)])


start_unknown = len(known_bits_format)
len_unknown = total_bits - len(known_bits_format) - len(known_bits_end)


for i in range(0, len_unknown, 8):
    values[VARS[start_unknown + i]] = 0
f_subs = f.subs(values)

unknown_vars = [v for v in VARS if v not in values]
poly_coeffs = [f_subs.coefficient(v) for v in unknown_vars]
constant_term = f_subs.constant_coefficient()

coeffs_int = [c.constant_coefficient().lift() for c in poly_coeffs]
target = (-constant_term).lift() % M
num_vars = len(coeffs_int)

B = Matrix(ZZ, num_vars + 2, num_vars + 2)
N = 2**256
lattice_target = target * N

for i in range(num_vars):
    B[i, i] = 1
    B[i, num_vars + 1] = coeffs_int[i] * N

B[num_vars, num_vars + 1] = M * N           
B[num_vars+1, num_vars] = 1                 
B[num_vars+1, num_vars+1] = -lattice_target 


bs = 22 

B = B.BKZ(block_size=bs)

found_flag = False
for row in B:
    vec = list(row)
    if vec[-1] == 0: 
        potential_sol = vec[:num_vars]
        solution_bits = []
        is_valid = False
        if all(x in [0, 1] for x in potential_sol):
            solution_bits = potential_sol
            is_valid = True
        elif all(x in [0, -1] for x in potential_sol):
            solution_bits = [-x for x in potential_sol]
            is_valid = True
        
        if is_valid:
            final_bits = [0] * total_bits
            for v, val in values.items():
                idx = VARS.index(v)
                final_bits[idx] = val
            for i, val in enumerate(solution_bits):
                var_name = unknown_vars[i]
                idx = VARS.index(var_name)
                final_bits[idx] = val
            bit_str = "0" + "".join(str(b) for b in final_bits)
            try:
                flag_int = int(bit_str, 2)
                flag_bytes = long_to_bytes(flag_int)
                
                if b"KCSC" in flag_bytes:
                    print(flag_bytes.decode())
                    found_flag = True
                    break
            except:
                pass

:::spoiler Flag
KCSC{Th1s_1s_4_fl4g_f0r_y0u}
:::

---
# END

Em xin gửi lời cảm ơn đến anh Hào, anh Linh, anh Quân cũng như các anh chị trong clb thời gian qua đã training, hỗ trợ em.