# Write up KCSC Recruiment 2026
#### **AT21N0240-Nguyễn Hoàng Vinh**
## Crypto
### 1. Mini RSA
* Source code challenge.

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

Đây là một challenge kết hợp của nhiều challenge nhỏ. Flag của bài này là một chuỗi hex, đã được cắt ra làm 4 phần. Mỗi phần sẽ được mã hóa khác nhau. Để giải được bài này, mình cần phải giải các phase của flag trong source code sau đó ghép các phase lại thành một flag hoàn chỉnh.
* Bắt đầu với phase 1 và 2.

# 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 1, độ dài của Flag là 37 bytes, số mũ e = 7. Khi chuyển flag sang số nguyên, Thì số nguyên đó sẽ nhỏ hơn rất nhiều so với n, như vậy $m^7 \approx n$.
Sau khi mô phỏng để kiểm tra giá trị của n so với $flag^7$, suy ra được phase này có thể brute-force.
$c1 = flag^7 \bmod n \implies flag^7 = kn + c1$ brute-force k để tìm cân bậc 7 thật sự của flag.
Tiếp theo đến phase 2. Ở phase 2 này, flag2 được mã hóa 3 lần với cùng một số mũ e và khác số moduli. Để tìm được phase 2, sử dụng Hastad's Broadcast Attack. Sau khi dùng CRT để tìm được X và N, phần còn lại sẽ thực hiện như phase 1.

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

#phase 1
c = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827
n = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
e = 7

#phase 2
ns = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
cs = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]

def solve_small_e(e, n, c):
    k = 1
    while True:
        flag, exact = gmpy2.iroot(k*n + c, e)
        if exact:
            return f"phase = {long_to_bytes(flag)}"
        k += 1

flag1 = solve_small_e(e, n, c)
print(flag1)
# phase = b'f8fc7143e81ab9e2a4b8cd7b5893504c68619'

X = crt(cs, ns)
N = ns[0]*ns[1]*ns[2]
flag2 = solve_small_e(e, N, X)
print(flag2)
# phase = b'9fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e957040'

* Tiếp theo đến 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    

Phase 3 được mã hóa RSA rất chắn chắn không có lỗ hỏng để khai khác. Điểm mấu chốt nằm ở biến $d3$ và đề cho biết cả $d3$ và $E$, trong khi flag mã hóa bằng $e3$. Như vậy, từ $E$ và $d3$ có thể brute-force để tìm phi sau đó tìm ra $d$ và giải mã flag3.
$d_3 \equiv e^{-1} \bmod \phi \iff d_e.E \equiv 1 \bmod \phi$
$\implies d_3.E - 1 = k.\phi$ và $k$ là ước của $d_3.E$

from Crypto.Util.number import long_to_bytes, inverse

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

def solve_phi(E,d):
    num = E*d - 1
    for k in range(1, E + 1):
        if num % k == 0:
            phi = num // k
            return phi
        k += 1

Phi = solve_phi(E,d)
d = inverse(e, Phi)
print(f"phase 3 = {long_to_bytes(pow(c, d, n))}")
# phase 3 = b'3504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50e'

* Cuối cùng là 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

Phase 4 đã mã toàn bộ flag bằng thuật toán sha256. Dựa vào các dữ liệu đề bài như đã biết được phase 1,2,3 các kí tự của flag là hex từ 0-9 từ a-f, và phase 4 có 7 kí tự.
Dựa vào các dữ liệu trên, mình sẽ tạo charset = "0123456789abcdef". sau đó tạo ra các tổ hợp có lặp 7 kí tự từ charset sau đó ghép nó vào phase1,2,3 và tính hash của nó sau đó so sánh với hash đã cho trong để bài.

import itertools
from hashlib import sha256

phase1 = b'f8fc7143e81ab9e2a4b8cd7b5893504c68619'
phase2 = b'9fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e957040'
phase3 = b'3504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50e'

Flag_hash = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"

knownPhase = (phase1 + phase2 + phase3).decode()
charset = "0123456789abcdef"

for suf in itertools.product(charset, repeat=7):
    cand = knownPhase + "".join(suf)
    if sha256(cand.encode()).hexdigest() == Flag_hash:
        FLAG = f"KCSC{{{cand}}}"
        print("FLAG:", FLAG)
        # FLAG: KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}
        break

> Flag: KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}

### 2. to be continued
* source code của challenge

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)

Nhìn vào source code của challenge có những dấu hiệu như số d 1024 bit so với N 2048 bit, có khả năng $d < \frac{1}{3}N^{\frac{1}{4}}$. Và challenge này lại chọn d trước rồi mới tính e, hàm phi đã được custom khác so với RSA chuẩn. Có thể thấy được biến phi sẽ là một số rất lớn, khi tính $e = d^{-1} \bmod \phi$, e cũng sẽ là một số rất lớn. Bài này thuộc dạng low private exponent sử dụng kĩ thuật Wiener's attack.
Tuy nhiên do hàm phi được custom khác đi so với RSA chuẩn, nên cần phải phân tích hàm phi.
$Phi = (p^3 - a)(q^3 - b) = p^3q^3 - p^3b - aq^3 + ab = N^3 - p^3b - aq^3 + ab$
$\implies Phi \approx N^3$
Ta có biểu thức của Wiener: $\cfrac{e}{Phi} \approx \cfrac{k}{d}$ thay $Phi = N^3$ ta được $\cfrac{e}{N^3} \approx \cfrac{k}{d}$
Tiếp theo, thực hiện tìm phân số liên tục của $\cfrac{e}{N^3}$, một trong số đó sẽ là $\cfrac{k}{d}$ với $d$ là một số lẻ và $ed - 1$ chia hết cho $k$.
Sau khi tìm được 2 số $k$ và $d$, ta sẽ cần phải tìm nghiệm của phương trình bậc 2 theo hàm $phi$ đã được custom.
$Phi = N^3 - (p^3b + aq^3) + ab$
$\implies p^3b + aq^3 = N^3 - Phi + ab$
Ta có: $(x-p^3b)(x-aq^3)=0$
$\implies x^2 - (aq^3 + p^3b)x + abp^3q^3=0 \iff x^2 - (N^3 - Phi + ab) + abN^3 = 0$
Tiếp theo, tính delta của phương trình bậc 2 và tìm 2 nghiệm nguyên của phương trình.
2 nghiệm của phương trình sẽ có dạng: $X_1 = bp^3$ và $X_2 = aq^3$
Sau khi đã tìm được nghiệm, tính $\sqrt[3]{\frac{X_1}{b}}$ để tìm p và q, sau khi đã có p và q thì sẽ thực hiện giải mã RSA.
* script giải

from sympy import continued_fraction, continued_fraction_convergents, Rational, integer_nthroot
from Crypto.Util.number import long_to_bytes, inverse
import sys

sys.set_int_max_str_digits(100000)

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

def solve_challenge(e, N, a, b, c):

    x = Rational(e, pow(N, 3))
    c_f = continued_fraction(x)
    convergents = continued_fraction_convergents(c_f)
    
    for k_d in convergents:
        k = k_d.numerator
        d_guess = k_d.denominator

        if k == 0 or d_guess % 2 == 0: continue
            
        if (e*d_guess - 1) % k != 0:
            continue

        phi = (e*d_guess - 1) // k
        
        S = pow(N, 3) + a*b - phi
        P_val = a * b * pow(N, 3)
        delta = S**2 - 4*P_val
        
        if delta >= 0:
            sqrt_delta, is_exact = integer_nthroot(delta, 2)
            if is_exact:
                Z1 = (S + sqrt_delta) // 2
                
                if Z1 % b == 0:
                    p3 = Z1 // b
                    p, exact_cube = integer_nthroot(p3, 3)
                    
                    if exact_cube and N % p == 0:
                        q = N // p
                        print(f"Found p: {p}")
                        
                        phi_real = (p - 1) * (q - 1)
                        d_real = inverse(e, phi_real)
                        m = pow(c, d_real, N)
                        flag = long_to_bytes(m)
                        return flag
    
    return None

flag = solve_challenge(e, n, a, b, c)
if flag:
    print(f"\nFlag: {flag.decode()}")
else:
    print("\nCould not find solution.")

> Flag: KCSC{Be_water!My_friend}

### 3. rsabcde
* source code challenge

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

Khi kết nối đến sever, sever sẽ yêu cầu chọn các số a, b, c, d, e. Các số ấy phải thỏa mãn các điều kiện trong source code.
* Điều kiện đầu tiên:
$1111111111111111111 \times a = c + 8888888888888888881 \times e$
$\implies c = 1111111111111111111 \times a − 8888888888888888881 \times e$
có thể chọn a và e sau đó suy ra c.
* điều kiện tiếp theo:
$9999999999999999961 \times b = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 \times a$
đặt $X = 9999999999999999961$ và $K = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876$
Ta có: $X \times b = K \times a$
Đây là dạng phương trình Diophantine tuyến tính.
đặt: g = GCD(K,X)
Ngiệm tổng quát của phương trình là: $a = \frac{X}{g}k$ và $b = \frac{K}{g}k$ với $k \in Z.$
* Điều kiện cuối:
$d^2 = a + b$
thay $a + b = (\frac{X}{g}+\frac{K}{g})k$
Đặt $S = \frac{X}{g}+\frac{K}{g}$
bài toán trở thành: $S.k = d^2$, ta cần tìm k sao cho S.k là số chính phương. Một số chỉ là chính phương nếu trong phân tích thừa số nguyên tố, mọi số mũ đều là số chẵn. Vì vậy, ta cần phân tích thừa số nguyên tố.

from math import gcd, isqrt

X  = 9999999999999999961
K  = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876

g = gcd(X, K)

base_a = X // g
base_b = K // g

S = base_a + base_b
print(S)
# 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988797986574538026426837

Đã có được S là một số lớn, sử dụng factordb.com để phân tích.
Công việc tiếp theo là tìm k, sau đó chọn e = 1, vì trong source code của challenge flag nhỏ hơn n và không có điều kiện nào cho việc chọn e, nên nếu chọn e = 1 thì ciphertext cũng chính là plaintext.
* Script giải.

from pwn import remote
from Crypto.Util.number import long_to_bytes
from math import gcd, isqrt
import sys

HOST = "67.223.119.69"
PORT = 5010

sys.set_int_max_str_digits(100000)

X  = 9999999999999999961
K  = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
C1 = 1111111111111111111
C2 = 8888888888888888881

g = gcd(X, K)
base_a = X // g
base_b = K // g

S = base_a + base_b

temp = S
k = 1

factors = [
    125846296924748283658579137337,
    79462012346534541362149890632590776427112926556773
]

for p in factors:
    cnt = 0
    while temp % p == 0:
        temp //= p
        cnt += 1
    if cnt % 2 == 1:
        k *= p

small_primes = [2,3,5,7,11,13,17,19,23,29,31]
for p in small_primes:
    while temp % (p*p) == 0:
        temp //= p*p

k *= temp

a = base_a * k
b = base_b * k
d = isqrt(a + b)

assert d * d == a + b
assert a.bit_length() < 234

e = 1
c = C1 * a - C2 * e

payload = [a, b, c, d, e]

print("bit_length(a) = ", a.bit_length())

r = remote(HOST, PORT)

for val, name in zip(payload, "abcde"):
    r.recvuntil(f"{name} = ".encode())
    r.sendline(str(val).encode())

line = r.recvline().decode()
if "fake_flag" in line or "Nope" in line:
    print("[-] Server reject")
    r.close()
    exit()

if "n =" not in line:
    r.recvuntil(b"n = ")
    n = int(r.recvline().strip())
else:
    n = int(line.strip().split(" = ")[1])

r.recvuntil(b"ct = ")
ct = int(r.recvline().strip())

flag = long_to_bytes(ct)

print("\nFLAG:", flag.decode())

r.close()

> FLAG: KCSC{f4c70rDB_15_4m4z1ng!}