# Mini RSA
## Description

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

Ở challenge này, $flag$ được chia thành 4 phần và mỗi phần được mã hoá một cách khác nhau:
- Ở `phase 1`, ta có `c = flag1^7 mod n` nên ta có thể suy ra `flag1^7 = c + k.n` và ta có thể thấy được `flag1^7 > n` khoảng $24$ bits nên ta có thể brute force $k$ trong khoảng từ $[0, 2^{24}]$ và kiểm tra xem giá trị nào cho phép ta tính căn của `c + k.n` ra số nguyên.
- Ở `phase 2`, giá trị `flag2` được mã hoá bằng nhiều giá trị modulo khác nhau nên ở đây ta sẽ áp dụng **Hastad's Broadcast Attack** rồi làm tương tự `phase 1` là done.
- Ở `phase 3`, giá trị `flag3` được mã hoá theo RSA thông thường nhưng vấn đề ở đây là ta không được cho giá trị private key $d_3$ ứng với $e_3$ mà ta được cung cấp 1 cặp khoá $(d_{E}, E)$. Từ mối quan hệ của 2 giá trị này ,$E.d_{E} - 1 = k.phi_3$, ta có thể tìm lại giá trị $phi_3$ để từ đó tìm ngược lại $d_3$.
- Ở `phase 4`, ta chỉ biết được giá trị băm của `flag4` nhưng do độ dài của `flag4` chỉ có 7 kí tự tức 7 ví trí chưa biết mà ta có 16 khả năng là `0123456789abcdef` nên ta sẽ brute và so sánh với hash có được cho đến khi trùng khớp hoàn toàn.

## Solution

import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from hashlib import sha256
import itertools

n1 = 24768551472661189646803798025735994729675923012939876254832364742560290611235358539402960915109731271068761785643095443054780548009656705453830110379444700418833089171817064649224391362714139414078789526050887157582406524961283991222714583389641534201051586959980157906704312629985265485739450352043789888921235279589151315468070396525574513463528110969355058846977730601522857753194783784154604698121483122903344163960138046879651018970211352779930792196553883676319989732719640639947477887444507816814644473808320811170489238150100695729301133978725734344966342539008392521368848055667562401810828901055904263751087
c1 = 18095221808696767364482784106578665305597072892957003660200677125082480938590759416561596931362184836970227059449018023231775268023936196618166559695219893530882687916034256857200503922379924700258829452303164421775991854747192890323693977001251087329555558918620707751930767202265420598175188863386691087599780498257684594011697328525563218286665773793900960107693859824245088548197358663304146296383128902903029994359803481927306296829608298387122321098870479487155445811455194372706211665184810020606934406988332111485009183488421535000282713153719587883866210474448900196771807191538210239194200766493898209050827

ns2 = [5776746251180954410501143373555071446651309076079023801239927839678110284298053445067843385733923949632510804583576555583870535387441316658685840687689240200699587579390668561563937127040444465254726625310777306158594065224927251973217783491441064524351035802071558210418452732784328906404928346757561, 6676568530944751773705274371029619538616953853214731842955709009914939432096974301535527889053677971564433108995378797418249594276219798862529871540959246847221996855818534102541008885671426716581485932426758973143450314953430892380665585863829711961246704347425347121483579347058369739426135845646693, 4192125436309381894285355753973720387617056931265026941800223776464084287332759678003685944684491135983930538940594703444960195450172411842880979937537165579234724095471901440019430531228826628339513666609406387657919179589286169600368614047778141005381080248940651068046222358006840623976659320922801]
cs2 = [4162314281829070969983785868478817487122811901286983843325224202348302016796815815333452464672872912888701572281242789929104022254953168740731678111433971515437492093542686431714890537676381271531800973763109092820046704937574547000215411647046072684054960320518397352086234888330336947666810104929210, 50764199787126347289275452914702574991784396905310732416007230764340015964909418575803553215557208257135086801048181610281948813886172483845338416063595514468150336763299168160503561124717579857540938345665633478359717032027020484374804577083335729646127615429489801214833042281198632815600258496021, 2226866454269961169554477487076928558283277297558185848127271094461892302315098156482036398655353603737228883411877291393627455878900738358485648657420475192577890517627929950639476113316539806453385202418270139866437710517550467476876937820556775982947361645302515541452549533744585394098458949714224]

n3 = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e3 = 65537
E_val = 39119
d_E = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c3 = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342
target_hash = "6c65e2cc4142210eac7503a24a2d48205aeaf8686407c70fde01478336853281"

def get_k_range(length, n, c, e=7):
    m_min = bytes_to_long(b'0' * length)
    m_max = bytes_to_long(b'f' * length)
    k_min = (pow(m_min, e) - c) // n
    k_max = (pow(m_max, e) - c) // n
    return k_min, k_max
def solve_crt(remainders, moduli):
    M = 1
    for m in moduli: M *= m
    res = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        res += r * Mi * inverse(Mi, m)
    return res % M
p1 = b""
k_min, k_max = get_k_range(37, n1, c1)
for k in range(k_min, k_max + 2):
    val = c1 + k * n1
    root, exact = gmpy2.iroot(val, 7)
    if exact:
        p1 = long_to_bytes(root)
        print(f"Found: {p1}")
        break
p2 = b""
N2 = ns2[0] * ns2[1] * ns2[2]
C2 = solve_crt(cs2, ns2)
k_min, k_max = get_k_range(54, N2, C2)
for k in range(k_min, k_max + 2):
    val = C2 + k * N2
    root, exact = gmpy2.iroot(val, 7)
    if exact:
        p2 = long_to_bytes(root)
        print(f"Found: {p2}")
        break
p3 = b""
K = E_val * d_E - 1
k_approx = K // n3
for k in range(k_approx, k_approx + 100):
    if k == 0: continue
    if K % k == 0:
        phi = K // k
        if pow(2, phi, n3) == 1:
            d3 = inverse(e3, phi)
            p3 = long_to_bytes(pow(c3, d3, n3))
            print(f"Found: {p3}")
            break
final= ""
if p1 and p2 and p3:
    prefix = p1 + p2 + p3
    charset = "0123456789abcdef"
    for p in itertools.product(charset, repeat=7):
        suffix = "".join(p).encode()
        cand = prefix + suffix
        if sha256(cand).hexdigest() == target_hash:
            final = cand.decode()
            print(f"FLAG: KCSC{{{final}}}")
            break
else:
    print("Previous phases failed.")

## Flag

KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}

# Lost
## Description

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

Trong challenge này, vẫn là mã hoá RSA nhưng giá trị $phi$ đã bị truncated và ta nhận lại giá trị $HINT$ chính là 445 bit thấp của giá trị $phi$. Mục tiêu bây giờ là tìm lại $phi$ là done.

Ta có:
$$
\phi(n) = (p-1).(q-1)
$$

$$
p + q = n + 1 - \phi(n)
$$

$$
p + q \equiv (n + 1 - \phi(n)_{low}) \pmod{2^{445}}
$$
Ngoài ra ta có:
$$
p + q \equiv n \pmod{2^{445}}
$$
Từ đó ta có thể giải ptrinh bậc 2 trên vành $2^{445}$ và tìm lại được giá trị bit thấp của $p, q$.

Sau đó ta sẽ đi tìm lại $67$ bits còn thiếu bằng cách sử dụng Coppersmith với phương trình $f(y) = y^{445} + p_{low}$ với $y$ là ẩn cho $67$ bits cần tìm.

## Solution

from sage.all import *
from Crypto.Util.number import long_to_bytes
n = 112654267531053465556136674746878649082311939063806818924462933263741875629394889661682552659024091908172480343659015574843946862042743125008337388884333221729927034358266152309599465123544533344748189013549990570426711270722167349548299576309337189468190071950365811726840694954345965264584467524018296958753
e = 65537
c = 8002944762099258567457615206256772306393999363093971354996328677238641774654391571386887016848224899250762255275947356988416616247761892841611709100843880889058667475786184996217958354468257211905339362523859724316921413272443004897703998073112581860169711839608791480826283429489201512747250548419782502867
HINT = 58568716757057749176579698947278522097247638230381142002077590687430267388214398988361849858546815254992223558816558004613328562794052

"""
hint = phi & ((1 << (445)) - 1) tức là 445 bit thấp của phi
phi = n + 1 - (p + q) --> p + q = n + 1 - phi --> p + q (mod 2^445) = n + 1 - hint (mod 2^445)
"""
mod = 2**445
sum_low = (n + 1 - HINT) % mod

R = Zmod(mod)
P = PolynomialRing(R, 'x')
x = P.gen()
"""
p + q = sum_low (mod 2^445)
p.q = n (mod 2^445)
"""
f = x**2 - sum_low * x + n
roots = f.roots(multiplicities=False)
print(f"Found {len(roots)} candidates for p_low.")

# tim not 67 bit con thieu cua p
Q = PolynomialRing(Zmod(n), 'y')
y = Q.gen()
for i, r in enumerate(roots):
    plow_cand = Integer(r)
    # y * 2^445 + p_low = 0 (mod p)
    f1 = y*mod + plow_cand 
    f1 = f1.monic()
    try:
        res = f1.small_roots(X=2**72, beta=0.45, epsilon=0.02)
    except Exception as e:
        print(f"Error in small_roots: {e}")
        continue
    if res:
        # phigh = y, 67 bit con thieu
        phigh = res[0]
        p = Integer(phigh * mod + plow_cand)
        if n % p == 0:
            q = n // p
            print(f"Found factors p and q:\np = {p}\nq = {q}")
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = pow(c, d, n)
            flag = long_to_bytes(m)
            print(f"Flag: {flag.decode()}")
            break

## Flag

KCSC{i_hope_you_used_coppersmith_method_to_solve_this_challenge_not_bruteforce}

# rsabcde
## Description

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 này, để tìm lại được $flag$ ta cần nhập các giá trị $a,b,c,d,e$ sao cho nó thoả mãn các phần `assert` phía dưới cùng với đó là ta phải tìm $a$ sao cho độ dài của $a$ là nhỏ hơn $234$ bits để tránh rơi vào nhánh else.

Nhánh else sẽ trả về cho ta là 1 fake flag k có giá trị gì bruh :skull:

Để tìm lại $a,b,c,d,e$ ta sẽ làm như sau:
- Từ phương trình `9999999999999999961 * b == 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 * a`,ta đặt hệ số của $b$ là $D$ và hệ số của $a$ là $K$, ta có thể thấy được để $a$ hoặc $b$ nguyên thì $a$ phải chia hết cho hệ số của $b$ và ngược lại vì $gcd(D,K) = 1$, ta có $a = D.t$ và $b = K.t$.
- Từ đó ta có $d^2 = (D+K).t$ mà khi factor $(D+K)$ ta có thể thấy được
mà để $d$ nguyên thì vế phải phải là số chính phương nên ta lụm luôn $t$ bằng `7946201234653.....`.
- Có được $t$ rồi ta có thể tìm lại $a,b,d$, chọn $e$ bằng 1 và tìm nốt $c$ là done.

## Solution

from pwn import *
io = remote('67.223.119.69', 5010)
D = 9999999999999999961
K = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
t =  79462012346534541362149890632590776427112926556773
a = D * t
b = K * t
import math
d = int(math.isqrt(a + b))
e = 1
c = 1111111111111111111 * a - 8888888888888888881 * e
assert a > 0 
assert a.bit_length() < 234
assert 1111111111111111111 * a == c + 8888888888888888881 * e
assert 9999999999999999961 * b == 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 * a
assert d ** 2 == a + b
#print(a)
#print(b)
#print(c)
#print(d)
#print(e)
io.sendlineafter("a = ", str(a).encode())
io.sendlineafter("b = ", str(b).encode())
io.sendlineafter("c = ", str(c).encode())
io.sendlineafter("d = ", str(d).encode())
io.sendlineafter("e = ", str(e).encode())
n = int(io.recvline_contains("n = ").decode().split(" = ")[1])
ct = int(io.recvline_contains("ct = ").decode().split(" = ")[1])
#n = 12320222556311401102317714656097092658636171981645765394633139479293730378437659897174632226191446615456259306749993521599085120751680800240762530799065169
#ct = 120942960753267661356522390923886601053741122704643466174341501
from Crypto.Util.number import long_to_bytes, inverse
flag = long_to_bytes(pow(ct, e, n))
print(flag.decode())

## Flag

KCSC{f4c70rDB_15_4m4z1ng!}

# to be continued
## Description

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)

Welcome to KCSC's Recruiment
Gifts: 
a =  6304481321164246906567222989658765688045165275851071395205832715763220356466821410282955969161802841176445527338207576132114860045401544497249828909351039182182945402547214970223049123104061910807236829237608274748829008054249852723406591298824990323104235785926710097065678
b =  7999870125267969613672395287537327380867912777324346722357132031560297200201104156928904801090149293190711356687508094555199353750034650890008720565018729206913224039530232660373275511417192954417706309710650228654070214795786233986152367508554076009075490479812207855618459
n =  24081889277572802503659605826689926230027830719582767936363743502766482776099705960338212287859025560531973656731556156751481186678406820240771044210411774957806232749249860957895878890504459213322156810941197881824455880823042317347404688417969955356521338121436115650468863788924858088914981935069815044937563145675179199447446041774547448145057112430800054972872605835633576747583883285674457706771762988370139582185793239931790092003815695676798947934482380916291980085009315441662093814772584956990759521338343380951529181900596763825803370008245419318846198328641690031150992032307428945203841914049392112787033
e =  11050153015839883993161510135885787976039008082822382585575804877332676017418571820857988290309334210537161314550427816879212068985637953060885871602432684485487034375509379619789469792410393103838136020388501433382319198496971044588509979747359924647890043201124870325113772613514847295817375395027727381107822005050762060213230125451000959649050975147498113813336975434470468048553590716535948897232799351608157501900913776026264449516627219354423799349366099044820589167149211092110282765816684408405978492422462190786538301825408257216631933494464394828382376899323287315287973243876381980994428110571165021205398217777278825313093011741550183549639331123929016611159546502516316408659104164833466844920816898591821437607508224932520567325077419433023709911572576434857365505993059307741933102205523954940790045708534454784363255787058750009662319556437924605424640852945028220937879047842631235735134418121924586228479500537071667681030781582209438915903316316707019251330858088692416367956113483887988023423235436487473600194187120044620497634702200482106887128671850087321490311974939050362444303066126795966145296397377016134943620623131647797749418767732449622636419543202865842408588889412853603641329368785426334703041533454162178415167229266747016833148542628025339647321049686300229145201077528532971910019089492280243517721296838530796949829055923578715584168667973195521740594813691640838622696677680794584011285459260694486228084639063968847084787567170479050268786820660369450450781882574775405028286616546053143903706294406042325054355735859552547343917756174444977124800496069647281726872919803779970204586930394689812769802828483192801474434935520732430489482223645633398359373531176141794910809378994196853254737150627130658758517463777199549229895016654293830684067419466384677596715428945933720138801803468247516077733284618675
c =  8902578232624984411383722754874619024953250279805891829357397047274881749749711693192596092307853528587730589177614481442983584423981140117572924003770429665495872100397271876729790318687547951882889699514674500967917264418934982857003875266311412832039100198151364992410275296218572639061633726848133865363024117479523168920494186373486638535334075708542302849581459206163514282261518703853945190442837360895855359460519949894401579887910940646553403081219671212007000929291008947704019546704637268666663086394541789152216744224799090091941962088879750154156402189632368378336651988960439661260683085234566808439757

Khi nhìn challenge này ta có thể thấy ở đây giá trị $d$ nhỏ và thoả mãn điều kiện của **Wiener's Attack**, b có thể xem code cho hàm `wiener` ở dưới đây:

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None

Tuy nhiên ở đây ta sẽ phải sửa lại một vài phần vì $\phi$ của ta không phải dạng thông thường là $(p-1).(q-1)$ mà là $(p^3 - a)(q^3 - b) = p^3q^3 - b p^3 - a q^3 + ab$.

Đặt $u = b p^3$ và $v = a q^3$, ta có thể dễ dàng suy ra được $u+v$ và $u.v$ nên ta sẽ giải ptrinh bậc 2 tìm $u,v$ từ đó tìm lại $p,q$

def wiener_variant(e, n, a, b):
    cf = continued_fraction(e / (n**3))
    convergents = cf.convergents()
    
    for kd in convergents:
        k = int(kd.numerator())
        d = int(kd.denominator())
        if k == 0: 
            continue
        if (e * d - 1) % k != 0:
            continue
            
        phi_fake = (e * d - 1) // k
        S = n**3 + a*b - phi_fake
        P = a * b * (n**3)
        x = PolynomialRing(ZZ, 'x').gen()
        f = x**2 - S*x + P
        roots = f.roots()
        if len(roots) > 0:
            val = Integer(roots[0][0])
            if val % b == 0:
                p3 = val // b
                try:
                    p = p3.nth_root(3)
                    if n % p == 0:
                        return int(p)  
                except:
                    continue
    return None

## Solution

from sage.all import *
from Crypto.Util.number import long_to_bytes, inverse
a =  6304481321164246906567222989658765688045165275851071395205832715763220356466821410282955969161802841176445527338207576132114860045401544497249828909351039182182945402547214970223049123104061910807236829237608274748829008054249852723406591298824990323104235785926710097065678
b =  7999870125267969613672395287537327380867912777324346722357132031560297200201104156928904801090149293190711356687508094555199353750034650890008720565018729206913224039530232660373275511417192954417706309710650228654070214795786233986152367508554076009075490479812207855618459
N =  24081889277572802503659605826689926230027830719582767936363743502766482776099705960338212287859025560531973656731556156751481186678406820240771044210411774957806232749249860957895878890504459213322156810941197881824455880823042317347404688417969955356521338121436115650468863788924858088914981935069815044937563145675179199447446041774547448145057112430800054972872605835633576747583883285674457706771762988370139582185793239931790092003815695676798947934482380916291980085009315441662093814772584956990759521338343380951529181900596763825803370008245419318846198328641690031150992032307428945203841914049392112787033
e =  11050153015839883993161510135885787976039008082822382585575804877332676017418571820857988290309334210537161314550427816879212068985637953060885871602432684485487034375509379619789469792410393103838136020388501433382319198496971044588509979747359924647890043201124870325113772613514847295817375395027727381107822005050762060213230125451000959649050975147498113813336975434470468048553590716535948897232799351608157501900913776026264449516627219354423799349366099044820589167149211092110282765816684408405978492422462190786538301825408257216631933494464394828382376899323287315287973243876381980994428110571165021205398217777278825313093011741550183549639331123929016611159546502516316408659104164833466844920816898591821437607508224932520567325077419433023709911572576434857365505993059307741933102205523954940790045708534454784363255787058750009662319556437924605424640852945028220937879047842631235735134418121924586228479500537071667681030781582209438915903316316707019251330858088692416367956113483887988023423235436487473600194187120044620497634702200482106887128671850087321490311974939050362444303066126795966145296397377016134943620623131647797749418767732449622636419543202865842408588889412853603641329368785426334703041533454162178415167229266747016833148542628025339647321049686300229145201077528532971910019089492280243517721296838530796949829055923578715584168667973195521740594813691640838622696677680794584011285459260694486228084639063968847084787567170479050268786820660369450450781882574775405028286616546053143903706294406042325054355735859552547343917756174444977124800496069647281726872919803779970204586930394689812769802828483192801474434935520732430489482223645633398359373531176141794910809378994196853254737150627130658758517463777199549229895016654293830684067419466384677596715428945933720138801803468247516077733284618675
c =  8902578232624984411383722754874619024953250279805891829357397047274881749749711693192596092307853528587730589177614481442983584423981140117572924003770429665495872100397271876729790318687547951882889699514674500967917264418934982857003875266311412832039100198151364992410275296218572639061633726848133865363024117479523168920494186373486638535334075708542302849581459206163514282261518703853945190442837360895855359460519949894401579887910940646553403081219671212007000929291008947704019546704637268666663086394541789152216744224799090091941962088879750154156402189632368378336651988960439661260683085234566808439757

def wiener_variant(e, n, a, b):
    cf = continued_fraction(e / (n**3))
    convergents = cf.convergents()
    
    for kd in convergents:
        k = int(kd.numerator())
        d = int(kd.denominator())
        if k == 0: 
            continue
        if (e * d - 1) % k != 0:
            continue
            
        phi_fake = (e * d - 1) // k
        S = n**3 + a*b - phi_fake
        P = a * b * (n**3)
        x = PolynomialRing(ZZ, 'x').gen()
        f = x**2 - S*x + P
        roots = f.roots()
        if len(roots) > 0:
            val = Integer(roots[0][0])
            if val % b == 0:
                p3 = val // b
                try:
                    p = p3.nth_root(3)
                    if n % p == 0:
                        return int(p)  
                except:
                    continue
    return None

p = wiener_variant(e, N, a, b)
q = N // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m).decode())

## Flag

KCSC{Be_water!My_friend}

# Sign v2
## Description

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

Với challenge này ta sẽ sử dụng kĩ thuật đó là **Nonce reused attack**, về cơ bản thì có 1 chữ kí gồm $(r,s)$ và nếu ta ký 2 thông điệp $(m1, m2)$ khác nhau nhưng dùng chung private key $d$ và cùng 1 nonce $k$ thì:
$$
\begin{aligned}
s_1 &= k^{-1}(m_1 + r \cdot d) \pmod n \\
s_2 &= k^{-1}(m_2 + r \cdot d) \pmod n
\end{aligned}
$$

Lấy hiệu 2 phương trình ta suy ra được $k$:
$$k = (m_1 - m_2)(s_1 - s_2)^{-1} \pmod n$$

Từ $k$ ta có thể tìm lại $d$:
$$d = r^{-1}(s_1 \cdot k - m_1) \pmod n$$

Ngoài ra ở trong challenge có phần check nonce để k cho bạn dùng trùng nonce:

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)

Trong base64, mỗi ký tự đại diện cho 6 bits. Khi số lượng bits của dữ liệu gốc không chia hết cho 6, các bits thừa ở ký tự cuối cùng thường bị bỏ qua bởi hàm `b64encode`.

Ví dụ như `a` có dạng bit là `01100001` thì sẽ được chia thành `011000` và `01`, phần thứ 2 sẽ được đệm thêm cho đủ $6$ bits. Lúc này ta có 2 phần đó là `011000` tương ứng với chữ `Y` và `010000` tương ứng với chữ `Q`. Khi encode thì sẽ padding thêm cho đủ $6$ bits thì khi decode sẽ làm ngược lại nên ở kí tự thứ 2 sẽ chỉ quan trong $2$ bits đầu, $4$ bits còn lại ta có thể thay đổi thành `0001` chẳng hạn, như thế thay vì là `Q` ta có được `R`.

from base64 import b64decode, b64encode
print(b64encode(b'a'))
print(b64decode(b'YQ=='))
print(b64decode(b'YR=='))
#b'YQ=='
#b'a'
#b'a'

Ta sẽ lợi dụng điều này để bypass phần check nonce và lụm flag.
## Solution

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

G = generator_256
n = G.order()
ip = '67.223.119.69'
port = 5009
io = remote(ip, port)
msg1 = "MQ=="
msg1_bytes = b64decode(msg1)
z1 = int(sha256(msg1_bytes).hexdigest(), 16)
nonce1 = "YQ=="
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg1.encode())
io.sendlineafter(b"Enter your nonce: ", nonce1.encode())
resp = io.recvuntil(b'}').decode()
sig1 = eval(resp[resp.find('{'):])
r1, s1 = int(sig1['r'], 16), int(sig1['s'], 16)
#print(r1)
#print(s1)

msg2 = "Mg=="
msg2_bytes = b64decode(msg2)
z2 = int(sha256(msg2_bytes).hexdigest(), 16)
nonce2 = "YR=="
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg2.encode())
io.sendlineafter(b"Enter your nonce: ", nonce2.encode())
resp = io.recvuntil(b'}').decode()
sig2 = eval(resp[resp.find('{'):])
r2, s2 = int(sig2['r'], 16), int(sig2['s'], 16)
#print(r2)
#print(s2)

if r1 != r2:
    print('error: r1 != r2')

diff_z = (z1 - z2) % n
diff_s = (s1 - s2) % n
inv_s = inverse(diff_s, n)

k = (diff_z * inv_s) % n

inv_r = inverse(r1, n)
d = (inv_r * (s1 * k - z1)) % n
io.sendlineafter(b"Option : ", b"2")
io.sendlineafter(b"Private key : ", str(d).encode())
flag = io.recvall().decode()
print(flag)

## Flag

KCSC{no_more_byte_\x00_today}

# Umama
## Description

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, phương thức mã hoá được sử dụng đó chính là thuật toán sinh số $LCG$ và ở đây $seed$ được sử dụng chính là `lcg_gen = LCG(seed=int(time.time() * 1000))` tức là thời gian của server hiện tại. Nên do đó việc khó nhất của phần giải mã $LCG$ là tìm $seed$ đã được xử lí.

Sử dụng $seed$ tìm được thì ta có thể dự đoán trước được con ngựa nào sẽ về nhất để có thể bet và kiểm về đủ số lượng tiền có thể để mua được $flag$.
## Solution

import socket
import time
import re
import sys
from dataclasses import dataclass
from typing import List
from pwn import remote

host = '67.223.119.69'
port = 5008
target = 1000000.0 

class LCG:
    def __init__(self, seed: int):
        self.M = 3287099835290195791649721107570004318267582246774226300213811649423225012170212287749142020192530464259481640735325781154239321190173754611921808393447501266888056440801327249770117062004226214495561535681369100056816111927528166402933420016083242583498654107351130511963025469986264222148916890724787070272803001
        self.A = 2894777803559679218352190554394546666288076241619396764815133803772055992385941101609673369526743001851311268818989398042025043757099501509707445437248873549911623395016719427960022056683203263457712425937702117698191301068614729419207159556006174347883149816514548460625672181804096655842375751872041822338728496
        self.C = 122
        self.seed = 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)

@dataclass
class Uma:
    name: str
    speed: float = 50.0
    stamina: float = 50.0
    skill_factor: float = 50.0
    current_pos: float = 0.0
    current_speed: float = 50.0

    def update_position(self, lcg: LCG, track_length: float) -> float:
        race_progress = self.current_pos / track_length
        stamina_drain = max(0.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.uniform(0.95, 1.05 + self.skill_factor * 0.01 * skill_multiplier)
        micro_random = lcg.uniform(0.99, 1.01)
        step_speed = self.current_speed * micro_random + random_boost
        self.current_pos += step_speed
        return step_speed

def get_uma_template() -> List[Uma]:
    names = ["Special Week", "Silence Suzuka", "Gold Ship", "Mejiro McQueen", 
             "Tokai Teio", "Rice Shower", "Symboli Rudolf", "Kitasan Black", 
             "Satono Diamond", "Daiwa Scarlet"]
    return [Uma(name) for name in names]

def consume_odds_rng(lcg: LCG):
    for _ in range(10):
        lcg.uniform(0.8, 1.2)

def calculate_local_odds(lcg: LCG) -> List[float]:
    umas = get_uma_template()
    total_power = sum(u.speed + u.stamina + u.skill_factor for u in umas)
    odds_list = []
    for u in umas:
        uma_power = u.speed + u.stamina + u.skill_factor
        base_odds = total_power / uma_power
        random_factor = lcg.uniform(0.8, 1.2) 
        final_odds = max(1.5, base_odds * random_factor * 0.5)
        odds_list.append(final_odds)
    return odds_list

def simulate_race(lcg: LCG) -> str:
    umas = get_uma_template()
    track_length = 500.0
    race_over = False
    step = 0
    while not race_over and step < 1000:
        step += 1
        for u in umas:
            u.update_position(lcg, track_length)
            if u.current_pos >= track_length:
                race_over = True
    results = sorted(umas, key=lambda x: x.current_pos, reverse=True)
    return results[0].name

def recv_until(s, string):
    buffer = ""
    while string not in buffer:
        chunk = s.recv(4096).decode()
        if not chunk: return buffer
        buffer += chunk
    return buffer

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((host, port))
connect_ts = int(time.time() * 1000)
print(f"[*] Connected. Base timestamp: {connect_ts}")
recv_until(s, "Exit Game")

current_balance = 10000.0
global_lcg = None 
round_count = 0
while True:
    round_count += 1
    print(f"\n--- ROUND {round_count} | Balance: {current_balance:,.2f} Yen ---")
    if current_balance >= target:
        print("[!!!] TARGET REACHED. BUYING FLAG.")
        s.sendall(b'2\n')
        final_res = ""
        while "}" not in final_res and "NOT ENOUGH" not in final_res:
            chunk = s.recv(4096).decode()
            if not chunk: break
            final_res += chunk
        print("\n" + "#"*50)
        print(final_res.strip())
        print("#"*50)
        break 

    s.sendall(b'1\n')
    odds_buffer = recv_until(s, "Uma Index")
    server_odds = [float(x) for x in re.findall(r"1 to\s+([0-9]+\.[0-9]+)\s*x", odds_buffer)]
    if global_lcg is None:
        print("[*] First round: Brute-forcing seed...")
        found = False
        for drift in range(-5000, 5000):
            cand_seed = connect_ts + drift
            test_lcg = LCG(cand_seed)
            local_odds = calculate_local_odds(test_lcg) 
            if all(abs(round(local_odds[i],2) - round(server_odds[i],2)) < 0.02 for i in range(10)):
                global_lcg = test_lcg 
                print(f"[+] SEED SYNCED: {cand_seed}")
                found = True
                break
        if not found:
            print("[-] Failed to find seed. Exiting.")
            s.close()
            sys.exit(1) 
    else:
        consume_odds_rng(global_lcg)
        print("[+] Seed synced from previous round.")

    winner_name = simulate_race(global_lcg)
    print(f"[!] PREDICTED WINNER: {winner_name}")
    
    winner_idx = -1
    template = get_uma_template()
    for i, u in enumerate(template):
        if u.name == winner_name:
            winner_idx = i + 1
            break
    
    bet_amount = int(current_balance)
    print(f"[*] Betting {bet_amount} on #{winner_idx}")

    s.sendall(f"{winner_idx}\n".encode())
    time.sleep(0.5)
    s.recv(4096) 
    s.sendall(f"{bet_amount}\n".encode())
    result = recv_until(s, "Exit Game")
    
    if "WINNER" in result and winner_name in result:
        print("[+] Win confirmed.")
        match = re.search(r"NEW BALANCE:\s+([\d,]+\.\d+)", result)
        if match:
            current_balance = float(match.group(1).replace(',', ''))
        else:
            current_balance *= 4 
    else:
        print("[-] Lost race or prediction error.")
        break

s.close()

## Flag

KCSC{3m4m4}

# Multi RSA
## Description

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

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

Ở challenge này, flag được chia thành 3 phần $m_1, m_2, m_3$ và ở mỗi round thì 3 giá trị $e_1, e_2, e_3$ được chọn ngẫu nhiên và sử dụng chúng để mã hoá:

c1 = m1^e1 mod n
c2 = m2^e2 mod n
c3 = m3^e3 mod n

Và ta có 1 hệ 3 phương trình tổng quát như sau: $C_i = m_{1}^{e_{i1}} . m_{2}^{e_{i2}}.m_{3}^{e_{i3}}\pmod{n}$

Để giải được hệ phương trình này ta sẽ đưa nó về phép cộng theo logarit vì phép nhân khá khó để giải:
$$
log_{g}(C) ≡ e_{1}.log_{g}(m1) + e_{1}.log_{g}(m1) + e_{1}.log_{g}(m1) \pmod{n}
$$
Khi đó nếu coi đây là không gian vector của các số mũ thì ta có thể đưa nó về dạng ma trận như sau:
$$
\begin{pmatrix} \log_{g} C_0 \\ \log_{g} C_1 \\ \log_{g} C_2 \end{pmatrix} =
\begin{pmatrix}
e_{0,1} & e_{0,2} & e_{0,3} \\
e_{1,1} & e_{1,2} & e_{1,3} \\
e_{2,1} & e_{2,2} & e_{2,3}
\end{pmatrix}
\times
\begin{pmatrix} \log_{g} m_1 \\ \log_{g} m_2 \\ \log_{g} m_3 \end{pmatrix}
$$

Lúc này ta có thể tính các logarit rời rác của các ciphertext $C_1, C_2, C_3$ trên trường $Z_p, Z_q$ rồi giải phương trình tuyến tính tìm lại $ln(m1), ln(m2), ln(m3)$. Tìm được rồi ra có thể tìm lại $m$ dễ dàng.

Có một điều ta cần lưu ý thêm đó chính là cách $p,q$ được tạo ra:

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)

Đoạn code này tạo ra 2 giá trị $p,q$ sao cho $p-1, q-1$ smooth nên ta sẽ sử dụng điều này cùng với thuật toán Pollard p-1 để factor $n$ và tìm lại $p,q$

def pollard(n, B=1000000):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
        g = gcd(a - 1, n)
        if 1 < g < n:
            return g
    return None

## Solution

import ast
from math import gcd
from itertools import product
import sympy as sp
from sympy import Matrix, primitive_root
from sympy.ntheory.modular import crt
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Util.number import long_to_bytes

def pollard_p1_stage1(n, B, a=2):
    a %= n
    for p in sp.primerange(2, B + 1):
        pk = p
        while pk * p <= B:
            pk *= p
        a = pow(a, pk, n)
    return gcd(a - 1, n)

def factor_with_pollard_p1(n):
    for B in [5000, 10000, 20000, 30000, 40000, 50000, 60000, 65000, 70000]:
        g = pollard_p1_stage1(n, B, a=2)
        if 1 < g < n:
            return g, n // g
    raise RuntimeError("pollard p-1 failed")

def solve_linear_mod_prime(A, b, mod):
    A = [[int(x) % mod for x in row] for row in A.tolist()]
    b = [int(x) % mod for x in b]
    m, n = len(A), len(A[0])
    aug = [A[i] + [b[i]] for i in range(m)]
    row, pivots = 0, []

    for col in range(n):
        pivot = None
        for r in range(row, m):
            if aug[r][col] % mod != 0:
                pivot = r
                break
        if pivot is None:
            continue

        aug[row], aug[pivot] = aug[pivot], aug[row]
        inv = pow(aug[row][col], -1, mod)

        for c in range(col, n + 1):
            aug[row][c] = (aug[row][c] * inv) % mod

        for r in range(m):
            if r == row:
                continue
            factor = aug[r][col] % mod
            if factor:
                for c in range(col, n + 1):
                    aug[r][c] = (aug[r][c] - factor * aug[row][c]) % mod

        pivots.append((row, col))
        row += 1
        if row == m:
            break

    for r in range(m):
        if all(aug[r][c] % mod == 0 for c in range(n)) and aug[r][n] % mod != 0:
            raise ValueError("no solution")

    x = [0] * n
    for r, c in pivots:
        x[c] = aug[r][n] % mod
    return x

def brute_solutions_mod_r(E, Lc, r):
    Er = [[int(x) % r for x in row] for row in E.tolist()]
    L = [int(x) % r for x in Lc]
    sols = []
    for x in product(range(r), repeat=3):
        ok = True
        for i in range(3):
            s = (Er[i][0]*x[0] + Er[i][1]*x[1] + Er[i][2]*x[2]) % r
            if s != L[i]:
                ok = False
                break
        if ok:
            sols.append(list(x))
    return sols

def all_log_solutions_over_prime(p, E, Cs):
    g = primitive_root(p)
    Lc = [int(discrete_log(p, int(C) % p, g)) for C in Cs]

    mod = p - 1
    fac = sp.factorint(mod)
    primes = [int(r) for r in fac.keys()]
    det = int(E.det())

    per_prime_sols = []
    for r in primes:
        if det % r != 0:
            per_prime_sols.append((r, [solve_linear_mod_prime(E, Lc, r)]))
        else:
            per_prime_sols.append((r, brute_solutions_mod_r(E, Lc, r)))

    partial = [([0, 0, 0], 1)]
    for r, sols in per_prime_sols:
        new = []
        for vec, M in partial:
            for svec in sols:
                merged = []
                ok = True
                for j in range(3):
                    xj, _ = crt([M, r], [vec[j], svec[j]])
                    if xj is None:
                        ok = False
                        break
                    merged.append(int(xj) % (M * r))
                if ok:
                    new.append((merged, M * r))
        partial = new

    out = [[v % mod for v in vec] for vec, _ in partial]
    return g, mod, out

def to32(x):
    return long_to_bytes(int(x)).rjust(32, b"\x00")

def main():
    with open("output.txt", "r") as f:
        lines = f.read().splitlines()
    n = int(lines[0].strip())
    es = ast.literal_eval(lines[1].strip())
    cs = ast.literal_eval(lines[2].strip())

    p, q = factor_with_pollard_p1(n)
    if p > q:
        p, q = q, p

    E = Matrix(es)

    gp, modp, logs_p_list = all_log_solutions_over_prime(p, E, cs)
    gq, modq, logs_q_list = all_log_solutions_over_prime(q, E, cs)

    for logs_p in logs_p_list:
        ms_p = [pow(gp, lp, p) for lp in logs_p]
        for logs_q in logs_q_list:
            ms_q = [pow(gq, lq, q) for lq in logs_q]

            parts = []
            ok = True
            for mp, mq in zip(ms_p, ms_q):
                x, _ = crt([p, q], [mp, mq])
                if x is None:
                    ok = False
                    break
                parts.append(to32(x))
            if not ok:
                continue

            flag = b"".join(parts)
            if flag.startswith(b"KCSC{") and flag.endswith(b"}"):
                print(flag.decode(errors="replace"))
                return

    raise RuntimeError("no valid flag found")

if __name__ == "__main__":
    main()

## Flag

KCSC{I_hope_you_used_factor_and_discrete_log_to_solve_this_challenge_9f72b5a7608c076684b6ca6157}

# theMidnIghTMan
## Description

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, AES.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()

Challenge này sử dụng 3 lớp mã hoá $AES$ lồng nhau gồm có $ECB, CBC, OFB$ với 3 khoá $key_1, key_2, key_3$ khác nhau, mỗi key có độ dài là 3 bytes.

Để giải mã thì ta sẽ thực hiện các bước sau:
**Bước 1**
Lớp ngoài cùng là OFB, hoạt động như một Stream Cipher: $Plaintext = Ciphertext \oplus Keystream$.

Vì $Keystream$ chỉ phụ thuộc vào `key1` và `iv`, ta sẽ lợi dụng điều này để tìm lại `key1` đúng bằng cách:
- Gửi reques gồm `iv1` và ciphertext rỗng. Server giải mã prefix và ta nhhận được `pt1`.
- Gửi reques gồm `iv2` và ciphertext rỗng. Server giải mã prefix và ta nhhận được `pt2`.

Ta có:
$pt1 = Decrypt_{L2+L3}(prefix) \oplus Keystream(key1, iv1)$
$pt2 = Decrypt_{L2+L3}(prefix) \oplus Keystream(key1, iv2)$

Bằng cách xor `pt1` và `pt2` ta có được:
$pt1 \oplus pt2 = Keystream(key1, iv1) \oplus Keystream(key1, iv2)$

Chính vì $Keystream$ chỉ phụ thuộc vào `key1` và `iv` mà ta đã biết `iv` rồi nên ta có thể brute tìm `key1` sao cho thoả mãn phương trình trên.

**Bước 2**
Sau khi có được `key1`, ta sẽ đi tìm `key3` trước. Tuy nhiên ở đây do chưa biết `key2` nên ta cần biến đổi 1 chút để làm mất đi giá trị này trong phương trình tìm `key3`.

Ta có:
$$
O = Dec_{CBC, key2}(Dec_{ECB, key3}(Input))
$$

Ở đây ta biết server sẽ tự động thêm prefix là ` b'Midnight is coming. Stay awake!!'` nên ta sẽ chia prefĩ có độ dài $32$ bytes này thành 2 block $P1, P2$ sau đó ta sẽ gửi $P2$ lên cho server, lúc này dữ liệu được giải mã sẽ có dạng: $P_1 \ || \ P_2 \ || \ P_2$.

Vì phương thức mã hoá ở đây là $ECB$ tức là input giống nhau thì sẽ cho ra output giống nhau nên output ta có được sẽ là $I_1 \ || \ I_2 \ || \ I_2$, với $I_i = Dec_{Key3}(P_i)$

Tiếp theo output này sẽ tiếp tục được giải mã theo phương thức đó là $CBC$, công thức giải mã của $CBC$ như sau:
$$Plaintext_i = Decrypt_{Key}(Ciphertext_i) \oplus Ciphertext_{i-1}$$

Do đó ta sẽ có:
$O_2 = Dec_{Key2}(I_2) \oplus I_1$
$O_3 = Dec_{Key2}(I_2) \oplus I_2$

Bằng cách xor $O_2$ với $O_3$ ta sẽ có:
$$
O_2 \oplus O_3 = (Dec_{Key2}(I_2) \oplus I_1) \oplus (Dec_{Key2}(I_2) \oplus I_2) = O_2 \oplus O_3 = I_1 \oplus I_2
$$

$$O_2 \oplus O_3 = Dec_{ECB, k3}(P_1) \oplus Dec_{ECB, k3}(P_2)$$

Lúc này ta chỉ cần brute force `key 3` sao cho nó thoả mãn phương trình trên vì các dữ liệu khác như vế trái phương trình và $P_1, P_2$ ta đều đã biết.

**Bước 3**
Do đã có `key 3`, ta có thể tìm lại chính xác $I_1, I_2$.

Ta có: $Dec_{k2}(I_2) = O_2 \oplus I_1$.

Lúc này ta sẽ brute tiếp `key 2` sao cho thoả mãn phương trình trên.

**Bước 4**
Tìm được `key 1,2,3` rồi thì là done

## Solution

from pwn import *
from Crypto.Cipher import AES
import hashlib
from tqdm import tqdm
import itertools

context.log_level = 'debug'

HOST = '67.223.119.69'
PORT = 5011

def get_md5_key(key_bytes):
    return hashlib.md5(key_bytes).digest()

def xor_bytes(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


r = remote(HOST, PORT)

r.recvuntil(b'Stay awake!!')
r.recvline()

prefix = b'Midnight is coming. Stay awake!!'
p1 = prefix[:16]
p2 = prefix[16:]

def oracle_decrypt(iv, ciphertext):
    r.sendlineafter(b'> ', b'2')
    r.sendlineafter(b'(hex): ', iv.hex().encode())
    r.sendlineafter(b'(hex): ', ciphertext.hex().encode())
    try:
        r.recvuntil(b'Plaintext:  ', timeout=2)
        line = r.recvline()
        if not line:
            return None
        return bytes.fromhex(line.strip().decode())
    except:
        return None

def get_flag(key):
    r.sendlineafter(b'> ', b'3')
    r.sendlineafter(b'(hex): ', key.hex().encode())
    result = r.recvall(timeout=2).decode()
    return result

iv_a = b'\x00' * 16
iv_b = b'\x11' * 16

pt_a = oracle_decrypt(iv_a, b'')
pt_b = oracle_decrypt(iv_b, b'')

target_xor = xor_bytes(pt_a[:32], pt_b[:32])

found_key1 = None

pbar = tqdm(itertools.product(range(256), repeat=3), total=256**3, desc="Finding K1")
for k in pbar:
    k_bytes = bytes(k)
    k_md5 = get_md5_key(k_bytes)

    c_temp = AES.new(k_md5, AES.MODE_ECB)

    ks_a = c_temp.encrypt(iv_a)
    ks_a += c_temp.encrypt(ks_a)

    ks_b = c_temp.encrypt(iv_b)
    ks_b += c_temp.encrypt(ks_b)

    if xor_bytes(ks_a, ks_b) == target_xor:
        found_key1 = k_bytes
        pbar.close()
        print(f"[+] Found Key 1: {found_key1.hex()}")
        break

if not found_key1:
    print("[-] Failed to find Key 1")
    exit()

iv_ph2 = b'\x22' * 16
pt_ph2 = oracle_decrypt(iv_ph2, p2)

k1_md5 = get_md5_key(found_key1)
cipher_ofb = AES.new(k1_md5, AES.MODE_OFB, iv_ph2)
layer2_out = cipher_ofb.encrypt(pt_ph2)

O2 = layer2_out[16:32]
O3 = layer2_out[32:48]

target_ecb_diff = xor_bytes(O2, O3)
found_key3 = None

pbar = tqdm(itertools.product(range(256), repeat=3), total=256**3, desc="Finding K3")
for k in pbar:
    k_bytes = bytes(k)
    k_md5 = get_md5_key(k_bytes)
    cipher_ecb = AES.new(k_md5, AES.MODE_ECB)

    dec_p1 = cipher_ecb.decrypt(p1)
    dec_p2 = cipher_ecb.decrypt(p2)

    if xor_bytes(dec_p1, dec_p2) == target_ecb_diff:
        found_key3 = k_bytes
        pbar.close()
        print(f"[+] Found Key 3: {found_key3.hex()}")
        break

if not found_key3:
    print("[-] Failed to find Key 3")
    exit()

k3_md5 = get_md5_key(found_key3)
cipher_k3 = AES.new(k3_md5, AES.MODE_ECB)
I1 = cipher_k3.decrypt(p1)
I2 = cipher_k3.decrypt(p2)

target_block = xor_bytes(O2, I1)
found_key2 = None

pbar = tqdm(itertools.product(range(256), repeat=3), total=256**3, desc="Finding K2")
for k in pbar:
    k_bytes = bytes(k)
    k_md5 = get_md5_key(k_bytes)

    cipher_core = AES.new(k_md5, AES.MODE_ECB)
    if cipher_core.decrypt(I2) == target_block:
        found_key2 = k_bytes
        pbar.close()
        print(f"[+] Found Key 2: {found_key2.hex()}")
        break

if not found_key2:
    print("[-] Failed to find Key 2")
    exit()

full_key = found_key1 + found_key2 + found_key3
print(f"\n[!] Full Key recovered: {full_key.hex()}")

r.sendlineafter(b'> ', b'3')
r.sendlineafter(b'(hex): ', full_key.hex().encode())
flag = r.recvline().strip()
print(flag.decode())

## Flag

KCSC{a_formal_gift_to_honor_you_e5bb1bb281165c0}

# 五六七
## Description

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

Ở challenge này, để tìm được $flag$ ta cần tìm đúng giá trị `x = random.getrandbits(128)` thoả mãn phương trình sau:
$$
res \equiv 1 + 2^x + 3^x + 4^x + 6^x \pmod p
$$
Trong đó $res$ là giá trị server trả về khi ta gửi $p$.

Giờ thì ta cùng xem xét phương trình trên để tìm ra phương hướng tìm $x$ thoả mãn, có thể thấy các cơ số có thể đưa về $2^x$ và $3^x:
$$
res \equiv 1 + 2^x + 3^x + 2^{2x} + 2^x.3^x \pmod p
$$

Nếu ta đặt $u = 2^x$ và $v = 3^x$ thì lúc này phương trình trở thành:
$$
res \equiv (1 + u + u^2) + v(1 + u) \pmod p
$$
Lúc này ta có được phương trình 2 ẩn nhưng để dễ dàng hơn thì ta có thể tìm cách khác để sao cho 2 giá trị $2^x$ và $3^x$ có quan hệ với nhau.

Mà ta lại được chọn $p$ để gửi cho server nên ta sẽ có như sau:
$$
3 \equiv 2^k \pmod p
$$

$$
2^k - 3 \equiv 0 \pmod p
$$

Từ đây ta có thể thấy $p$ là 1 ước của $2^k - 3$ nên ta sẽ chọn luôn $p = 2^k - 3$ với điều kiện $p$ là số nguyên tố và phải có độ dài lớn hơn $512$ bits

Sau khi chọn được $p$ rồi ta có thể đưa phương trình về dạng sau:
$$
res \equiv 1 + 2^x + (2^x)^k + 2^{2x} + 2^x.(2^x)^k \pmod p
$$
Đặt $u = 2^x$ ta có:
$$
res \equiv 1 + u + (u)^k + u^2 + u.(u)^k \pmod p
$$

$$
f(x) = 1 + u + (u)^k + u^2 + u.(u)^k - res
$$
Giải phương trình tìm nghiệm bằng cách sử dụng `f.roots()` ta tìm được nghiệm $u = 2^x \mod p$.

Giờ thì quay về bài toán **Discrete Logarithm Problem**, để giải bài toán thì ta cần order là $p-1$ smooth để có thể thực hiện **Pohlig Hellman**.

Vì $p$ có độ dài khá lớn là $512$ bits và $x$ của ta có độ dài $128$ bits, tức là ta sẽ có $0 < x < 2^{128}$, thay vì thực hiện dlp với $p-1$ thì ta sẽ factor nó và lấy các ước sao cho tích của chúng lớn hơn $2^{128}$. Bằng cách này thì khi thực hiện **định lý phần dư Trung Hoa (CRT)** và tìm được $X$ sao cho $X \equiv x \pmod M$ thì ta sẽ có $X = x$ do $x < M$ :broccoli:

Gửi $X$ cho server và lụm flag thôi hehe.

## Solution

import os
os.environ.setdefault('TERM', 'xterm')
from pwn import *
from Crypto.Util.number import isPrime
# nc 67.223.119.69 5012
io = remote('67.223.119.69', 5012)
def gen_p():
    k = 600
    while True:
        p = (1 << k) - 3
        if isPrime(p) and p.bit_length() >= 512:
            return p, k
        k += 1
            
p, k = gen_p()
#k = 689
io.sendlineafter(b'Choose p > ', str(p).encode())
res = int(io.recvline().decode().strip())
# factor p-1 = 2^2 * 7 * 6871 * 1504073 * 20492753 * 2104809991 * 59833457464970183 * 175932323679511304414371921 * 467795120187583723534280000348743236593 * ...
F = GF(p)
a = PolynomialRing(F, "a").gen()
f = a**(k+1) + a**k + a**2 + a + 1 - res
roots = f.roots()
print(f"[+] Found {len(roots)} roots.")

def solve_dlp_crt(g, h, p, factors_list):
    order = p - 1
    moduli = []
    remainders = []
    for pe in factors_list:
        if order % pe != 0:
            continue
        exponent = order // pe
        g_sub = pow(g, exponent, p)
        h_sub = pow(h, exponent, p)
        try:
            if pe > 10**10: 
                val = int(pari(h_sub).znlog(pari(g_sub), pari(pe)))
            else:
                val = discrete_log(h_sub, g_sub, ord=pe)
            moduli.append(pe)
            remainders.append(val)
        except ValueError:
            print(f"[-] Failed to solve for factor {pe}")
            continue
        except Exception as e:
            print(f"[-] Error on factor {pe}: {e}")
            continue            
    if not moduli:
        return None
    try:
        x = crt(remainders, moduli)
        return x
    except Exception:
        return None

factors = [4, 7, 6871, 1504073, 20492753, 2104809991, 59833457464970183]
for r, _ in roots:
    base = F(2)
    cand = r
    print(f"\n[*] Trying root r = {r}")
    x_cand = solve_dlp_crt(base, cand, p, factors)
    if x_cand is not None:
        if x_cand.bit_length() > 128:
            print("[-] x too large, skipping...")
            continue
        check = pow(2, x_cand, p)
        if check == cand:
            print(f"[+] Found x: {x_cand}")
            x = x_cand
            break
if x is not None:
    io.sendlineafter(b'guess x = ', str(x).encode())
    flag = io.recvall(timeout=2).decode().strip()
    print(flag)

## Flag

KCSC{why_do_you_choose_crypto?}

> Tuy nhiên có 1 vấn đề mình chưa fix được đó là mặc dù theo lý thuyết như mình nói thì X tìm ra sẽ chắc chắn bằng x nhưng khi gửi cho server thì không phải lúc nào cũng sẽ nhận lại flag ... (luck issue)
>
> Mình tìm ra cách fix r nma sẽ update sau he
# e
## Description

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

> cái gì càng ngắn thì càng khó hsy ...

Trông ngắn ngắn thế này đọc không thì sẽ khá khó hiểu nên ta sẽ bắt đầu phân tích source code luôn để hiểu rõ hơn cách hoạt động.

Với hàm `hash(msg)` hoạt động như sau:
1. Chuyển `msg` input sang dạng nhị phân
2. Với $n = 36$ và với mỗi bit $b$ của `msg` thì $n$ sẽ được cập nhật dựa theo công thức sau: `n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)`
$$
n_{new} = (g \cdot (n_{old} + \delta)) \pmod{2^{512}}
$$
Nếu $b = 1$ thì $\delta=3$.
Nếu $b = 0$ thì $\delta=6$.
Ta có thể suy ra $\delta=6-3b$.

Nhìn như này có lẽ vẫn chưa suy ra được điều gì nên ta sẽ đưa nó về dạng 1 đa thức tuyến tính như sau:
$$
H = 36 \cdot g^L + \sum_{i=0}^{L-1} \delta_i \cdot g^{L-i} \pmod{M}
$$
> Trong đó $L$ là độ dài của chuỗi bit `msg`.

Thay $\delta_{i}=6-3b_{i}$, ta có:
$$
H = 36 \cdot g^L + \sum_{i=0}^{L-1} (6-3b_{i}) \cdot g^{L-i} \pmod{M}
$$

$$
\sum_{i=0}^{L-1} b_i \cdot (3g^{L-i}) \equiv 36 \cdot g^L + \sum_{i=0}^{L-1} 6g^{L-i} - H \pmod{M}
$$

$$
\sum_{i=0}^{L-1} b_i \cdot (3g^{L-i}) \equiv (36 \cdot g^L + \sum_{i=0}^{L-1} 6g^{L-i} - H)\pmod{M}
$$

Đặt vế phải $(36 \cdot g^L + \sum_{i=0}^{L-1} 6g^{L-i} - H)$ là $s$ và vế trái $(3g^{L-i})$ là $w_i$, ta sẽ đưa nó về bài toán **subset sum problem**: $\sum_{i=0}^{L-1} b_i \cdot w_{i} \equiv s \pmod{M}$

Và nhiệm vụ của ta là đi tìm các bit ẩn $b_i$.
> Để hiểu rõ hơn về subset sum problem, bạn có thể đọc thêm ở [032.pdf](https://eprint.iacr.org/2023/032.pdf) và [doc](https://informatika.stei.itb.ac.id/~rinaldi.munir/Kriptografi/2022-2023/Makalah2/Makalah2-Kriptografi-2023%20(25).pdf)

Đề giải quyết được bài toán này ta sẽ xây dựng ma trận có dạng như sau:

Cụ thể hơn ở bài này thì sẽ là:

$$
\mathbf{B} = \begin{pmatrix}
1 & 0 & \cdots & 0 & 0 & N \cdot w_1 \\
0 & 1 & \cdots & 0 & 0 & N \cdot w_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & 0 & N \cdot w_L \\
0 & 0 & \cdots & 0 & 0 & N \cdot 2^{512} \\
\frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & \frac{1}{2} & N \cdot s
\end{pmatrix}_{(L+2)\times(L+2)}
$$

Mặc dù đã xây dựng được ma trận để giải quyết vấn đề nhưng chưa dừng lại ở đó vì lúc này với $L = 223$ thì ma trận $B$ là 1 ma trận vô cùng lớn để $LLL$ hay $BKZ$ có thể xử lí.

Tuy nhiên với các dữ liệu đã biết đó là flag format là `KCSC{` và `}` ta có thể giảm đi tổng là $47$ bits cần giải quyết (do hàm `bin()` làm mất bit $0$ của byte đầu tiên). Như vậy ta còn $176$ bit ẩn cần tìm.

Tiếp theo, như ta đã biết trong máy tính, 1 ký tự (character) thường được biểu diễn bằng $1$ Byte = $8$ Bits. Tuy nhiên, bảng mã ASCII chuẩn (các ký tự in được như: `a-z, A-Z, 0-9, _, {, })` chỉ sử dụng $7$ bit thấp để định nghĩa giá trị (từ 0 đến 127). Như vậy một kí tự ASCII ở dạng nhị phân sẽ có dạng `0xxxxxxx`. Vậy thì với $22$ kí tự còn lại ta biết được cứ $7$ bit ẩn thì sẽ có 1 bit $0$ nên ta sẽ có thể giảm số bit cần tìm xuống còn $154$.

Như vậy ta đã có thể đưa về kích thước mà $LLL$ hay $BKZ$ có thể xử lí được nên là lụm thoi.

## Solution

import binascii

target_hash = 4733050325257322080995332543647525767201053028813565191926008882515250832618947947748792937964480829322550895675027130098198538016461241391725598109040829 
len_flag = 28
M = 1 << 512
g = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 

L = (len_flag * 8) - 1
known = [None] * L
def set_bits(indices, values):
    for i, bit in zip(indices, values):
        known[i] = int(bit)
prefix = "KCSC{"
prefix = bin(int(binascii.hexlify(prefix.encode()).decode(), 16))[2:]
for i in range(len(prefix)):
    known[i] = int(prefix[i])
suffix = "01111101" # '}'
for i in range(8):
    known[L-8 + i] = int(suffix[i])

cur = 39
end = L - 8
count = 0
while cur < end:
    known[cur] = 0
    count += 1
    cur += 8

ww = [(3 * pow(g, L - i, M)) % M for i in range(L)]
t1 = (36 * pow(g, L, M)) % M # 36*g^L
t2 = sum(6 * pow(g, L - i, M) for i in range(L)) % M # sum(6*g^(L-i))
s = (t1 + t2 - target_hash) % M
# loai bo cac bit da biet 
s1 = s
for i in range(L):
    if known[i] is not None:
        val = (known[i] * ww[i]) % M
        s1 = (s1 - val) % M

unknown_indices = [i for i, x in enumerate(known) if x is None]
unknown_weights = [ww[i] for i in unknown_indices]

dim = len(unknown_weights) + 2
B = Matrix(ZZ, dim, dim)
scale = 2**512

for i in range(len(unknown_weights)):
    B[i, i] = 1
    B[i, dim-2] = unknown_weights[i] * scale

B[dim-2, dim-2] = -s1 * scale
B[dim-2, dim-1] = 1

B[dim-1, dim-2] = M * scale

print(f"[*] Đang chạy BKZ (block_size=20) trên ma trận {dim}x{dim}...")
B_reduced = B.BKZ(block_size=20)

for row in B_reduced:
    if row[dim-2] != 0: continue
    
    vec = list(row[:-2])
    
    if vec[-1] == -1:
         pass
    
    candidates = []
    if all(x in [0, 1] for x in vec): candidates.append(vec)
    if all(x in [0, -1] for x in vec): candidates.append([-x for x in vec])
    
    for cand in candidates:
        full_bits = known[:]
        for i, val in enumerate(cand):
            idx = unknown_indices[i]
            full_bits[idx] = val
            
        try:
            bit_str = "0" + "".join(str(x) for x in full_bits)
            n = int(bit_str, 2)
            flag = n.to_bytes(len_flag, 'big')
            if b'KCSC{' in flag:
                print(f"\n[SUCCESS] FLAG: {flag.decode()}")
                exit()
        except:
            pass

## Flag

KCSC{Th1s_1s_4_fl4g_f0r_y0u}