<h1 style="text-align:center; font-size: 2.5em">KCSC Recruitment 2026</h1>


# [Crypto] Mini RSA

**Source code:**

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

---

## 📖 Description
- Từ source code, nhận thấy rằng flag được chia làm 4 part tương ứng 4 phase và không bao gồm phần "KCSC{" "}"

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

- Phase 1: (Small Exponent Attack): $c \equiv m^{e} \pmod{n}$
Có $e_1$ = 7 nhỏ chính là dấu hiệu của loại hình tấn công này (RSA với $e$ nhỏ, $m^e < n$ hoặc lớn hơn một chút)
Part1 = FLAG[0 : 37] cho thấy giá trị $m_1$ có 37 bytes = 296 bits, $n_1$ có 2048 bits, thấy $m_1^7 \approx (2^{296})^7 = 2^{2072} > 2^{2048} = n_1$ một khoảng $2^{24}$, đủ để dùng Small Exponent Attack từ phương trình sau
$$m_1^e = c + k \cdot n_1$$
Duyệt $k$ lần lượt từ 0,1,2,... cho đến khi khi $m_1= \sqrt[e]{c + k \cdot n_1}$ là một số nguyên, khi đó $m_1$ là flag, ta kết thúc part 1

- Phase 2 (Håstad's Broadcast Attack - CRT):
3 public key khác nhau nhưng có cùng chỉ số e, mã hóa flag để cho ra 3 ciphertexts, đây là dấu hiệu của loại hình tấn công này
$$c_1 \equiv m^e \pmod{n_1}$$$$c_2 \equiv m^e \pmod{n_2}$$$$c_3 \equiv m^e \pmod{n_3}$$
Áp dụng CRT cho cả 3 phương trình trên, ta cần tìm được một giá trị $X$ duy nhất sao cho:$$X \equiv c_1 \pmod{n_1}$$$$X \equiv c_2 \pmod{n_2}$$$$X \equiv c_3 \pmod{n_3}$$Và điều quan trọng là:$$X \equiv m_2^7 \pmod{N}$$
Trong đó: $N = n_1.n_2.n_3$
Sau khi có N và X, nhận thấy $m$ dài 54bytes = 432bit, $e$ = 7 thì $m^e$ sẽ có 3024bit. Quay ra phân tích $N = n_1.n_2.n_3$, với mỗi $n$ là tích của hai prime giá trị 512bit, $N$ sẽ có 512.2.3 = 3072bit, tức lớn hơn $m^e$ một chút xíu, đây lại là kiểu tấn công như bên phase 1

- Phase 3: (Leaked Partial Private Key)
Đề bài cho thêm dữ kiện là một giá trị $d'$ được tính từ số mũ $E$ (không phải $e$) theo $phi3$: $$d' \equiv E^{-1} \pmod{phi3}$$ Tương đương phương trình: $$d' \cdot E = 1 + k \cdot phi3$$ Từ đây có thể khôi phục $phi3$ để tính được $d \equiv e_3^{-1} \pmod{phi3}$, giải mã $m_3$.
Vấn đề ở đây là cách ta duyệt $k$:
$$k = \frac{d' \cdot E - 1}{phi3} = 1024 + 16 - 1024 = 16bit = 65536$$
Hoàn toàn có thể brute được $k$ và tìm ra $phi3$, nhiệm vụ còn lại là tìm $d$, giải mã $m_3$ theo RSA thuần túy

- Phase 4: (Brute-force Hash)
Dữ liệu đề bài là toàn bộ SHA-256 của toàn bộ nội dung Hex của FLAG, khi đã biết được part1 + part2 + part3, nhiệm vụ của ta là tìm ra part4 với độ dài 7 kí tự
$$ \quad \text{SHA-256}(\text{part1} + \text{part2} + \text{part3} + \text{part4}) = Flaghash$$
Brute-force Hash với 7 kí tự Hex sẽ có không gian mẫu là $16^7$, thoải mái cho việc brute.
Vì phase4 cần brute $16^7$ khả năng nên có thể sẽ chờ từ 3-5p tùy khả năng CPU của máy bạn

## 💻 Solve Script
- Mô tả ý tưởng cho AI, tự động hóa việc viết script (Một số lib được viết trong script yêu cầu phải tải thêm)

import math
import hashlib
import itertools
from Crypto.Util.number import long_to_bytes, inverse
import gmpy2
from multiprocessing import Pool, cpu_count
import time

# ============================ KHÔI PHỤC DỮ LIỆU TỪ SOURCE CODE ============================

# Phase 1 Data
n1 = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
e1 = 7
c1 = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827

# Phase 2 Data
ns_p2 = [
    5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561,
    6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693,
    4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801
]
e2 = 7
cs_p2 = [
    4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210,
    50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021,
    2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224
]

# Phase 3 Data
n3 = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e3 = 65537
E_p3 = 39119
d_fake_p3 = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342

# Phase 4 Hash
TARGET_HASH = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"
MISSING_LEN = 7
CHARSET = "0123456789abcdef"


# ============================ SOLVER FUNCTIONS ============================

def solve_phase1(n, e, c):
    """Giải Phase 1: Small Exponent Attack"""
    k = 0
    # m^e = c + k*n. Ta duyệt k nhỏ
    while True:
        val = c + k * n
        m, exact = gmpy2.iroot(val, e)
        if exact:
            print(f"[+] Phase 1 Solved (k={k})")
            return long_to_bytes(m)
        k += 1

def chinese_remainder_theorem(moduli, remainders):
    """Tính toán CRT"""
    sum_prod = 0
    prod = 1
    for n_i in moduli:
        prod *= n_i
    
    for n_i, r_i in zip(moduli, remainders):
        p = prod // n_i
        # Cần dùng gmpy2.invert cho số lớn
        sum_prod = (sum_prod + r_i * gmpy2.invert(p, n_i) * p) % prod
    return sum_prod, prod

def solve_phase2(ns, e, cs):
    """Giải Phase 2: Håstad's Broadcast Attack (dùng CRT)"""
    # 1. Tính X và N bằng CRT
    X, N = chinese_remainder_theorem(ns, cs)
    
    # 2. Khai căn bậc e
    k = 0
    while True:
        val = X + k * N
        m, exact = gmpy2.iroot(val, e)
        if exact:
            print(f"[+] Phase 2 Solved (k={k})")
            return long_to_bytes(m)
        k += 1
        # Giới hạn k để tránh vòng lặp vô tận (thường k < 1000 là đủ)
        if k > 5000000:
             raise Exception("K too large, CRT failed or padding is complex")

def solve_phase3(n, e, E, d_fake, c):
    """Giải Phase 3: Leaked Partial Private Key"""
    # Phương trình: d_fake * E = 1 + k * phi
    numerator = d_fake * E - 1
    k_est = numerator // n
    
    # Brute-force k < 16bits
    for k in range(0, 65537):
        if k == 0: continue
        if numerator % k == 0:
            phi_candidate = numerator // k
            # Kiểm tra GCD(e, phi)
            if math.gcd(e, phi_candidate) == 1:
                # Tính d thực sự
                d_real = gmpy2.invert(e, phi_candidate)
                m = pow(c, d_real, n)
                # Kiểm tra kết quả
                flag_part = long_to_bytes(m)
                if flag_part[0] in b"0123456789abcdef":
                    print(f"[+] Phase 3 Solved (k={k})")
                    return flag_part
    return None

def worker_task(prefix_char, known_part, target_hash):
    """Hàm worker cho Brute-force đa luồng"""
    for suffix_tuple in itertools.product(CHARSET, repeat=MISSING_LEN - 1):
        suffix_str = prefix_char + "".join(suffix_tuple)
        candidate = known_part + suffix_str.encode()
        
        if hashlib.sha256(candidate).hexdigest() == target_hash:
            return suffix_str
    return None

def solve_phase4(known_part, target_hash):
    """Giải Phase 4: Brute-force Hash đa luồng"""
    print(f"[*] Starting Phase 4 Brute-force on {cpu_count()} cores...")
    
    prefixes = list(CHARSET)
    
    # Sử dụng Pool để chạy song song
    with Pool(processes=cpu_count()) as pool:
        # Cung cấp các tham số cố định cho hàm worker
        args = [(p, known_part, target_hash) for p in prefixes]
        
        # imap_unordered trả về kết quả ngay khi có (không cần chờ thứ tự)
        for result in pool.starmap(worker_task, args):
            if result:
                print(f"[+] Phase 4 Solved (Suffix: {result})")
                pool.terminate()
                return result
    return None

# ============================ MAIN EXECUTION ============================

def solve_full_challenge():
    print("=== STARTING KCSC MINI RSA CHALLENGE ===")
    
    # --- PHASE 1 ---
    print("\n[+] PHASE 1: Small Exponent Attack")
    p1 = solve_phase1(n1, e1, c1)
    
    # --- PHASE 2 ---
    print("\n[+] PHASE 2: Broadcast Attack (CRT)")
    p2 = solve_phase2(ns_p2, e2, cs_p2)

    # --- PHASE 3 ---
    print("\n[+] PHASE 3: Leaked Partial Private Key")
    p3 = solve_phase3(n3, e3, E_p3, d_fake_p3, c3)
    
    if not p1 or not p2 or not p3:
        print("[!] Lỗi giải mã Phase 1, 2, hoặc 3.")
        return

    known_flag_content = p1 + p2 + p3
    print(f"\n[*] Known Flag Content (155 bytes): {known_flag_content.decode()}")

    # --- PHASE 4 ---
    print("\n[+] PHASE 4: Brute-force Hash")
    start_time = time.time()
    p4 = solve_phase4(known_flag_content, TARGET_HASH)
    end_time = time.time()
    
    if p4:
        full_flag_content = known_flag_content + p4.encode()
        print(f"[*] Time elapsed for Brute-force: {end_time - start_time:.2f} seconds")
        print("\n" + "="*50)
        print(f"!!! FULL FLAG !!!")
        print(f"KCSC{{{full_flag_content.decode()}}}")
        print("="*50)
    else:
        print("[!] Lỗi: Không tìm thấy Part 4.")

if __name__ == '__main__':
    solve_full_challenge()

<details>
<summary><b>🚩Flag</b></summary>
<p style="font-size: 1.2em; font-family: monospace;"><b>KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}</b></p>
</details>

# [Crypto] rsabcde
**Source code:**

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

## 📖 Description
- Bài này chia ra làm 2 giai đoạn:
- Bước 1: Giải $a,b,c,d,e$ để vượt assert, nhận $n$ và $ct$ <br>
Từ source code có thể thấy được $a$ và $b$ là hai ẩn tác động đến tất cả các ẩn còn lại, nên ta ưu tiên tìm $a, b$ trước<br>
Bắt đầu từ lúc này:
Gọi A = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
B = 9999999999999999961
Điều kiện trở thành $B\cdot b = A \cdot a$
$a$ và $b$ đều là số nguyên và $a$ dương, nên ta có tỉ số
$$\frac{a}{b} = \frac{B}{A} = \frac{a'}{b'}$$
Với $a', b'$ là tử và mẫu của phân số tối giản tính toán từ $\frac{B}{A}$, từ đó tính toán được $a = a'\cdot k$ và $b = b'\cdot k$<br>
Có thể tìm $a'$ và $b'$ như sau
$$a' = B/GDC(A,B)$$ $$b' = A/GDC(A,B)$$
Để thỏa mãn điều kiện $d^2 = a + b$, hay $k \cdot (a' + b')$ là một số chính phương, ta khai thác việc phân tích $(a' + b')$ thành tích các thừa số nguyên tố, mục đích là để $k$ làm nhiệm vụ triệt tiêu các thừa số có mũ lẻ, từ đó $k \cdot (a' + b')$ sẽ là tích của các thừa số mũ chẵn, thỏa mãn điều kiện số chính phương<br>
Cần chú ý rằng phải tìm ra $k_{min}$ để thỏa tiếp dòng lệnh <b>if a.bit_length() < 234</b> (tức là $k_{min}$ bằng tích của các thừa số có mũ lẻ trong $(a' + b')$)<br>
Trình bày ý tưởng với AI để tự động hóa việc viết script giải phần này<br>

import sys
from math import gcd
from functools import reduce
from operator import mul
from sympy import integer_nthroot # Dùng để kiểm tra căn bậc 2 số nguyên

# Cho phép xử lý số lớn
sys.set_int_max_str_digits(0)

# ====================================================
# HẰNG SỐ CỐ ĐỊNH TỪ SOURCE CODE
# ====================================================
A = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
B = 9999999999999999961
C1 = 1111111111111111111
C2 = 8888888888888888881
E_VAL  = 65537 

def calculate_full_abcde_manual_k():
    print("==================================================")
    print("BƯỚC 1: TÍNH TOÁN CÁC THÀNH PHẦN CƠ SỞ (a', b', S)")
    print("==================================================")
    
    # 1. Rút gọn phân số a/b = B/A
    common = gcd(A, B)
    a_prime = B // common
    b_prime = A // common
    S = a_prime + b_prime
    
    print(f"[*] S (Số cần phân tích) có {len(str(S))} chữ số: \n\n{S}\n")
    
    print("="*70)
    print("BƯỚC 2: XÁC ĐỊNH HỆ SỐ K BẰNG FACTORDB (THỦ CÔNG)")
    print("==================================================")
    print("Vui lòng tra cứu số S trên https://factordb.com/ và tìm k (tích các thừa số mũ lẻ).")
    print("---------------------------------------------------------------")
    
    # Khu vực người dùng nhập liệu thủ công (k)
    k_min_factors = []
    
    while True:
        user_input = input("Nhập thừa số nguyên tố có mũ lẻ (hoặc gõ 'xong' nếu đã nhập hết): ")
        if user_input.lower() == 'xong':
            break
        try:
            factor = int(user_input)
            k_min_factors.append(factor)
        except ValueError:
            print("Lỗi: Vui lòng nhập số nguyên hợp lệ hoặc 'xong'.")

    # Tính k_min
    if not k_min_factors:
        # Nếu k không có thừa số mũ lẻ, k = 1.
        k_min = 1
    else:
        k_min = reduce(mul, k_min_factors)
        
    print(f"[*] Hệ số k_min (phần Square-Free) được chọn: {k_min}")

    # 3. Tính toán a, b, d, c cuối cùng
    real_a = a_prime * k_min
    real_b = b_prime * k_min
    
    # Tính d
    sum_val = real_a + real_b
    root, is_sq = integer_nthroot(sum_val, 2)
    
    if not is_sq:
        print("\n[!!! THẤT BẠI KÉP !!!]")
        print("Lý do: a + b không phải số chính phương. Hệ số k_min sai.")
        return
        
    real_d = root
    
    # Tính c: c = C1 * a - C2 * e
    real_c = C1 * real_a - C2 * E_VAL

    # 4. Kiểm tra ràng buộc
    bit_len = real_a.bit_length()
    
    print("\n" + "="*70)
    print("BƯỚC 3: KẾT QUẢ CUỐI CÙNG VÀ KIỂM TRA ĐIỀU KIỆN")
    print("="*70)
    
    if bit_len < 234:
        print(f"[SUCCESS] Điều kiện a < 234 bits ({bit_len} bits) THỎA MÃN.")
        
        print("\n" + "="*70)
        print("BỘ SỐ HOÀN CHỈNH (Sẵn sàng gửi lên server):")
        print("="*70)
        print(f"a = {real_a}")
        print(f"b = {real_b}")
        print(f"c = {real_c}")
        print(f"d = {real_d}")
        print(f"e = {E_VAL}")
        print("="*70)
        print("Gợi ý: Dùng `ncat` hoặc `pwntools` để gửi bộ số này.")
    else:
        print("\n[!!! THẤT BẠI KÉP !!!]")
        print(f"Lý do: a có độ dài {bit_len} bits, vượt quá giới hạn 234 bits. FactorDB bị thiếu thừa số.")

if __name__ == "__main__":
    calculate_full_abcde_manual_k()

- Sau khi chạy hoàn chỉnh, ta sẽ có bộ số như ảnh sau:
a = 794620123465345410522480424811060651147283530896689719342595864285853
b = 100000000000000000000000000000000000000000000000000000000000000000000001890670019999999999205379876534654589477519575188939348852716469103310289593986947031148
c = 882911248294828233825576013849473455661150542683981838030963900746542253406378237818586
d = 10000000000000000000000000000000000000000000000000000000000000000000000094533501
e = 65537

- Kết nối tới server và submit, ta được bộ số như ảnh:
n = 701455700888568388840791677751967544943062300756793050609618545753605660564498752227318192524235290226248673475648037884463529583884820619172777998876337691652939867212345998237296456545737571016270920663608606801676866579625214034378352586241630027870614304068601840400982878552086440093436244055895798923221388
ct = 566265984378794259352489351595426835537402781369263264258498958310658949018411345232411760573632532951441774110579374720370899032193624205883705940296732884074679353732284237802645965759063189654688973998723392456401646939275545321613642191622471005013669844768791877961615642120842042348409285374453456703943921
- Bước 2: Từ dữ kiện vừa nhận được, tiến hành RSA<br>
Tiếp tục đọc lại source, nhận thấy rằng $n$ được lấy từ tích của một số nguyên tố 512bits với 1 giá trị trong bộ $[a, b, c, d, e]$, rõ ràng ta thấy số $b$ rất lớn, mình đã cố tình tìm ra bộ số mà $n$ được tính từ $b$ từ ảnh trên, và nếu giải sẽ mất khoảng thời gian rất lâu.<br>
Cách khắc phục là chỉ cần nộp lại bộ $[a, b, c, d, e]$ lên server, để server thực hiện random lại và ta sẽ giải lại với bộ $n$ và $ct$ mới, nếu may mắn thì server sẽ chọn $e$ để tính $n$, từ đó tìm flag rất nhanh
n = 596878961599165893930180111028279295415589540928205562674847704451248443476880194016265604043556912286788926846604954242823845959637389966751301086117197981979
ct = 11742715901656474986786112641552133809286064713315946195882654058610809907963487087546394526974856501324423652479560180556055091800549285208419516126498135553
<br>
Tiếp tục cho AI viết script, nếu n được tính từ b thì hãy chạy kết nối lại với server để lấy bộ $n$ và $ct$ mới nhé

import sys
from Crypto.Util.number import long_to_bytes, inverse
from sympy import totient
import time

# Cho phép xử lý số lớn
sys.set_int_max_str_digits(0)

# ====================================================
# DỮ LIỆU
# ====================================================
a = 794620123465345410522480424811060651147283530896689719342595864285853
b = 100000000000000000000000000000000000000000000000000000000000000000000001890670019999999999205379876534654589477519575188939348852716469103310289593986947031148
c = 882911248294828233825576013849473455661150542683981838030963900746542253406378237818586
d = 10000000000000000000000000000000000000000000000000000000000000000000000094533501
e = 65537

# N và Ct
n = 596878961599165893930180111028279295415589540928205562674847704451248443476880194016265604043556912286788926846604954242823845959637389966751301086117197981979
ct = 11742715901656474986786112641552133809286064713315946195882654058610809907963487087546394526974856501324423652479560180556055091800549285208419516126498135553
# Thử nghiệm với các biến nhỏ trước (A, C, D, E), nếu không được thì thử B
inputs_to_check = {
    'a': a, 
    'c': c, 
    'd': d, 
    'e': e,
    'b': b 
}

def force_decrypt_from_image_data():
    print("[*] Bắt đầu rà soát từng biến để tìm nhân tử của N...")
    
    found = False
    for name, val in inputs_to_check.items():
        val_int = int(val)
        n_int = int(n)
        ct_int = int(ct)
        e_int = int(e)

        if n_int % val_int == 0:
            print(f"\n[+] BINGO! Server đã chọn biến '{name}' làm nhân tử (rand).")
            
            if name == 'b':
                print("\n[!!! CẢNH BÁO: ĐANG TÍNH BIẾN 'B' (157 chữ số) !!!]")
                print("Quá trình này có thể mất RẤT LÂU (vài phút đến vài giờ) do phải phân tích thừa số...")
            
            p = n_int // val_int
            print(f"[*] Đang tính Euler Totient phi({name})...")
            start_time = time.time()
            
            try:
                # Ép kiểu từ SymPy Integer về int thường
                phi_rand = int(totient(val_int)) 
                phi_n = (p - 1) * phi_rand
                
                # Giải mã
                d_priv = inverse(e_int, phi_n)
                m = pow(ct_int, d_priv, n_int)
                flag = long_to_bytes(m)
                
                end_time = time.time()
                
                print(f"[*] Giải mã thành công sau {end_time - start_time:.2f} giây.")
                print("\n" + "="*40)
                print(f"FLAG TÌM THẤY VỚI BIẾN {name}:")
                try:
                    print(flag.decode('ascii', errors='ignore')) 
                except:
                    print(flag) 
                print("="*40)
                found = True
                break
            except Exception as ex:
                print(f"[-] Lỗi tính toán với biến {name}: {ex}")

    if not found:
        print("\n[-] Rất tiếc, n không chia hết cho bất kỳ số nào (A, B, C, D, E).")
        print("Xin lỗi, có thể bộ số ban đầu A-E đã bị thay đổi, hoặc server không chạy đúng logic.")


if __name__ == "__main__":
    force_decrypt_from_image_data()

<details>
<summary><b>🚩Flag</b></summary>
<p style="font-size: 1.2em; font-family: monospace;"><b>KCSC{f4c70rDB_15_4m4z1ng!}</b></p>
</details>
<!--
# [Crypto] Multi RSA


**Source code:**

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

<!--
## 📖 Description
- Bài này là tìm 3 mảnh flag bị mã hóa RSA.
- Bước 1: Factoring $N$ <br>
Nhìn qua hàm <b>get_prime</b> của source, có thể thấy output là số nguyên tố $p$ được tạo từ tích các thừa số nguyên tố cộng thêm 1, từ đó suy vào công thức tính $phi$, $(p-1)$ và $(q-1)$ đều bằng tích các thừa số nguyên tố bé hơn hoặc bằng <b>factor_bits</b> = 16bit <br>
Nhận ra việc phân tích $N$ sử dụng <b>Thuật toán p − 1 của Pollard</b> với $(p-1)$ và $(q-1)$ đều là B-smooth và B = $2^{16} \approx 65.536$ bytes. Kết quả sau khi dùng thuật toán là là tìm được $p, q$ và tính được $phi$

- Bước 2: Giải Hệ Phương trình <br>
Source code đã tạo ra 3 ciphertext ($C_1, C_2, C_3$) bằng cách trộn 3 mảnh Flag ($m_1, m_2, m_3$) với các số mũ ngẫu nhiên $E_{j,i}$ <br>
Để giải nó mà không cần tính logarit (quá khó khăn), ta sử dụng công cụ từ đại số tuyến tính là ma trận nghịch đảo, nghịch đảo ma trận trên số mũ
$$D \equiv E^{-1} \pmod{\phi(n)}$$
Trong đó $E$ là ma trận $3 \times 3$ chứa các số mũ đã cho.
...
-->

<hr>
<h1 style="text-align:center; font-size: 2.5em">COMMING SOON</h1>
<hr>