# Write up KCSC Recruitment 2026
## MiniRSA
Đề bài cho source code như sau:

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

Đọc source thì thấy flag cần tìm là dãy byte độ dài 162 được ghép từ 4 phase đề bài

**Phase 1**
part1 là 1 chuỗi byte có độ dài là 37. Do đề cho e khá nhỏ, nên ta có thể lấy căn để tìm m(part1).
Có $c = m^e \bmod n$, hay $m^e - c$ chia hết cho $n$. Vậy, ta có $m^e = c +k.n$ với $k \in \mathbb{Z}$. Vậy chỉ cần tìm k sao cho $\sqrt[7]{c +k.n}$ là một số nguyên. Code như sau:

from Crypto.Util.number import  long_to_bytes
from gmpy2 import *

n1 = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
e1 = 7
c1 = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827

for k in range(10000000):
    thu = k*n1 + c1
    can, so = iroot(thu, e1)
    if so:
        print(long_to_bytes(can).decode())
        break

được part1 là `f8fc7143e81ab9e2a4b8cd7b5893504c68619`

**Phase 2**

part2 là chuỗi byte có độ dài 54. Đề cho list ns và cs gồm 3n và 3c, thêm số mũ e nhỏ là 7, nên mình nghĩ đến dùng crt để giải. Sau khi đã giải và tìm được nghiệm của crt, mình tiếp tục dùng phương pháp như phase 1 để tìm ra m chính xác, sau đó long_to_bytes và tìm được part2 đúng bằng độ dài ban đầu. Code như sau:

from Crypto.Util.number import  long_to_bytes
from gmpy2 import *
import libnum

N = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
e  = 7
C = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]
n=1
for i in N: n*=i
m = libnum.solve_crt(C,N)
for k in range(10000000):
    thu = k*n + m
    can, so = iroot(thu, 7)
    if so:
        print(long_to_bytes(can).decode())
        break

part2: `9fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e957040`

**Phase 3**

part3 là chuỗi byte có độ dài 64. Ngoài các giá trị n, e, c thì phần này đề cung cấp thêm E, và d sao cho $E.d \equiv 1 \bmod \phi(n)$. Có $k = E \cdot d - 1 = m \cdot \phi(n)$ => $k = 2^s \cdot r$. Ta cần tìm $g$ thõa mãn $g^r \not\equiv \pm 1 \pmod{N}$ và tồn tại $x = g^{2^i r} \pmod{N}$ sao cho $x \not\equiv \pm 1 \pmod{N}$ nhưng $x^2 \equiv 1 \pmod{N}$. Sau đó tính $p = \gcd(x - 1, N)$, có được p, ta giải như bình thường và tìm được part3. Code như sau:

from Crypto.Util.number import  long_to_bytes, inverse
from gmpy2 import *

N = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e = 65537
E = 39119
d = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342

k = E*d-1
s = 0
r = k
while r % 2 == 0:
    r //= 2
    s += 1
p=q=0

for g in range(2, 10):
    x=pow(g, r, N)
    for i in range(s):
        y = pow(x, 2, N)
        if y == 1:
            p = gcd(x - 1, N)
            if p>1 and p<N:
                q = N // p
                break
            else:
                break
        x = y
    if p!=0 and p!=1: break
q=N//p
phi = (p-1)*(q-1)
D=inverse(e, phi)
part3=long_to_bytes(pow(c,D,N)).decode()
print(part3)

part 3: `3504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50e`

**Phase 4**
part4 là chuỗi byte có độ dài là 7. Sau khi ghép với part1, part2, part3 và được băm bằng hàm sha256, sẽ có được Flag_hash đề cho. Để tìm lại part 4, cần duyệt qua tất cả các chuỗi byte có độ dài là 7 và chỉ chứa các ký tự hex, sau đó băm bằng hàm sha256, nếu ra được Flag_hash đề cho, thì đó chính là part4 cần tìm. Code như sau:

import hashlib
import itertools
TARGET_HASH = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"
FLAG_LEN = 7
CHARSET_DIGITS = "fedcba9876543210"
CHARSET_BYTES = CHARSET_DIGITS.encode('ascii')
FLAG_PREFIX = b"f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50e"

found = False
for suffix_tuple in itertools.product(CHARSET_BYTES, repeat=FLAG_LEN):
    suffix_bytes = bytes(suffix_tuple)
    flag_candidate = FLAG_PREFIX + suffix_bytes
    hash_hex = hashlib.sha256(flag_candidate).hexdigest()
    if hash_hex == TARGET_HASH:
        print(flag_candidate)
        found = True
        break

flag: `KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}`

## Rsabcde (giải sau khi hết thời gian làm bài)
Đề bài cung cấp file source:

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!")

và server `nc 67.223.119.69 5010`

Đề cho các biến $a, b, c, d, e$ là số nguyên dương ($a > 0$). Các ràng buộc là:
* $1111111111111111111 \cdot a = c + 8888888888888888881 \cdot e$
* $9999999999999999961 \cdot b = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 \cdot a$
* $d^2 = a + b$
* $\text{a.bit_length()} < 234$

Ký hiệu:
* $K_1 = 1111111111111111111$
* $K_2 = 8888888888888888881$
* $K_3 = 9999999999999999961$
* $K_4 = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876$
Chọn e là 1, cần tìm a, b sao cho a+b là một số chính phương và $$\frac{b}{a} = \frac{K_4}{K_3}$$
Vậy, $a$ và $b$ phải có dạng:$$a = k \cdot K_3$$$$b = k \cdot K_4$$ với $k \in \mathbb{N^*}$
Thay $a$ và $b$ vào điều kiện (3):$$d^2 = k \cdot K_3 + k \cdot K_4 = k \cdot (K_3 + K_4)$$Đặt $s = K_3 + K_4$, cần tìm $k$ sao cho:$$d^2 = k \cdot s$$

Do $k.s$ phải là số chính phương, nên k phải chứa tất cả các thừa số nguyên tố của y với số mũ lẻ, ta nhân thêm các thừa số nguyên tố có số mũ lẻ vào k. Sau đó

from math import gcd, isqrt
from sympy.ntheory import factorint

k1 = 1111111111111111111
k2 = 8888888888888888881
k3 = 9999999999999999961
k4 = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
s = (k3+k4)
k = 1
for p, cnt in factorint(s).items():
    if cnt%2!=0: k *= p
a = k * k3
while k1 * a <= k2:
    a <<= 2
b = a*k4//k3
c = k1*a-k2
d = isqrt(a + b)
print(a)
print(b)
print(c)
print(d)

Nộp a,b,c,d,e lên server được n và ct, long to byte ct ta được flag `KCSC{f4c70rDB_15_4m4z1ng!}`