# KCSC RECRUITMENT 2025
**By : AT21_Vũ Hoàng Linh**
## Crypto 1
Source code :

from Crypto.Util.number import *
from math import gcd

flag = b"KCSC{fake_flag}"

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)

print(f"n = {n}")
print(f"c = {c}")
print(13 * q ** 2 + 5*p * q + 2 * p ** 5)
print(7 * q ** 3 + p ** 3)

"""
n = 68288521803749096598885637638053621717196600162883393314204537792265324550130476000830582459892601191221713398147068471895218340440441520348186049243098557276069294337290348570168822004443403024217772173472817801983123070596861372926544266786307347422625999741472764054251261966242723803223755250857431959613
c = 51484360656675894405169578577777421818221080188874188339332704212766014455602299232733441854614491353614936672698767100621643701474052897096397257567627546370308824123953740553988694850896612092526733722171750215446879926157508653359056454370778767748861899945472045315573513667461778478951641271690253340703
k1 = 99070322718633589075437462797565157261778565342202176866775343970398558639214129862647491552411934954337080928975984888590350647667063750589996693551004764949048370796506334502440334616612079528441181921243264137829513725003752633040825654275249100544290948338516838946174770287568358642193272862193796894044937197882972942736350187023160283258646203934697126833099845086570117310993425665455046278368788256843647321433937611726466080931200057154600456738627871172358125025243308598393199170155505096434440339433895197600955266878886512068835988415711337072167542113641557473147599428014808952558696371214362762804029219711275834667722478355607836912560341298862576500518929722837267759516608623300378294362866958920710706131156072317563285732965572961520111862487408104
k2 = 4053829493753080394597319030520465552249075460276768487813206903952134102796024072650537404512981555893331018255239607908419904554570951529767887735220350920134963507895001907309725345634404748146887358629605419756823088475689769294303699918630919892363333011358649952996211367887394670736389996674537151867058156643368735877078538193576703224594833465330136899282032495128158051461158831558808541670885217172490157676355847572589184884710346372276161554121356404

 """

Đây là một dạng mã hóa RSA thông thường với Modulus $n = p.q$ ($n$ có độ dài là $1024bits$), $e = 65537$. Điều đặc biệt ở đây là đề còn cho ta thêm hai phương trình biểu thị mối quan hệ tuyến tính giữa $p, q$ như sau :
$$
13q^2 + 5pq + 2p^5 = k_1
$$

$$
7q^3 + p^3 = k_2
$$

Ở đây ta hoàn toàn có thể nhờ máy tính giải được hệ 2 phương trình 2 ẩn này :

from Crypto.Util.number import long_to_bytes
from sympy import symbols, Eq, solve
n = 68288521803749096598885637638053621717196600162883393314204537792265324550130476000830582459892601191221713398147068471895218340440441520348186049243098557276069294337290348570168822004443403024217772173472817801983123070596861372926544266786307347422625999741472764054251261966242723803223755250857431959613
c = 51484360656675894405169578577777421818221080188874188339332704212766014455602299232733441854614491353614936672698767100621643701474052897096397257567627546370308824123953740553988694850896612092526733722171750215446879926157508653359056454370778767748861899945472045315573513667461778478951641271690253340703
k1 = 99070322718633589075437462797565157261778565342202176866775343970398558639214129862647491552411934954337080928975984888590350647667063750589996693551004764949048370796506334502440334616612079528441181921243264137829513725003752633040825654275249100544290948338516838946174770287568358642193272862193796894044937197882972942736350187023160283258646203934697126833099845086570117310993425665455046278368788256843647321433937611726466080931200057154600456738627871172358125025243308598393199170155505096434440339433895197600955266878886512068835988415711337072167542113641557473147599428014808952558696371214362762804029219711275834667722478355607836912560341298862576500518929722837267759516608623300378294362866958920710706131156072317563285732965572961520111862487408104
k2 = 4053829493753080394597319030520465552249075460276768487813206903952134102796024072650537404512981555893331018255239607908419904554570951529767887735220350920134963507895001907309725345634404748146887358629605419756823088475689769294303699918630919892363333011358649952996211367887394670736389996674537151867058156643368735877078538193576703224594833465330136899282032495128158051461158831558808541670885217172490157676355847572589184884710346372276161554121356404

p, q = symbols('x y')
pt1 = Eq(13 * q ** 2 + 5*p * q + 2 * p ** 5, k1)
pt2 = Eq(7 * q ** 3 + p ** 3, k2)
ans = solve((pt1, pt2), (p, q))
print(ans)

Kết quả :
<details>
<summary> p, q</summary>
p = 8689258480041293041399692588225619010038848476267257938381460275743198990453994369612779146937153513711653259630205767165604759708511533570809422015015993

q = 7858958501534250170001079058548567119095298447303096624306620238200889907799594504500744606979019919987769516210910890173064701639496539849295859708642341
</details>

Có được $p, q$ ta dễ dàng giải mã được Ciphertext :

from Crypto.Util.number import long_to_bytes
n = 68288521803749096598885637638053621717196600162883393314204537792265324550130476000830582459892601191221713398147068471895218340440441520348186049243098557276069294337290348570168822004443403024217772173472817801983123070596861372926544266786307347422625999741472764054251261966242723803223755250857431959613
c = 51484360656675894405169578577777421818221080188874188339332704212766014455602299232733441854614491353614936672698767100621643701474052897096397257567627546370308824123953740553988694850896612092526733722171750215446879926157508653359056454370778767748861899945472045315573513667461778478951641271690253340703
e = 65537
p = 8689258480041293041399692588225619010038848476267257938381460275743198990453994369612779146937153513711653259630205767165604759708511533570809422015015993
q = 7858958501534250170001079058548567119095298447303096624306620238200889907799594504500744606979019919987769516210910890173064701639496539849295859708642341

phi_N = (p-1)*(q-1)
d = pow(e, -1, phi_N)
ct = pow(c, d, n)
print(long_to_bytes(ct).decode())

<details>
<summary> Flag</summary>
KCSC{solv1ng_equ4ti0ns_with_r3sult4nts_is_f4n}
</details>

## Và đó là những gì mình làm được trong thời gian diễn ra cuộc thi. Sau đây là cách giải những bài khác mà mình giải được sau khi kì thi kết thúc.

## Zoltraak
Source code :

from Crypto.Util.number import *

FLAG = b'KCSC{???????????????????????????????????????}'
m = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
n = p * p * q
e = 0x10001
d = inverse(e, p * (p-1) * (q-1))
assert m < n
c = pow(m, e, n)
hint = pow(d, e, n)
print(f'c = {c}')
print(f'hint = {hint}')
print(f'n = {n}')

Ở đây, Modulus $N$ của chúng ta cho khá là dị, $N = p.p.q$. Điều này dẫn đến $\phi(N)$ của chúng ta sẽ có dạng :
$$
\phi(N) = N.(1 - \frac{1}{p}).(1-\frac{1}{q})
$$

$$
\Leftrightarrow \phi(N) = p.p.q.(\frac{p-1}{p})(\frac{q-1}{q})
$$

$$
\Leftrightarrow \phi(N) = p.(p-1).(q-1)
$$

Có thể thấy rằng, cả $N$ và $\phi(N)$ đều nhân với $p$, nên ta sẽ có tính chất :
$$
gcd(N, \phi(N)) = p
$$

Hãy bắt đầu với công thức tính khóa bí mật $d$
$$
d \equiv e^{-1} \pmod{\phi(N)}
$$

Mũ $e$ 2 vế, đồng thời lấy modulo $N$ ta có :
$$
d^e \mod(N) \equiv e^{-e} \mod(N) \pmod{\phi(N)}
$$

Đến đây ta có $Hint = d^e \mod(N)$, thế **Hint** vào và chuyển $e^{-e} \mod(N)$ sang vế trái ta có :
$$
Hint - e^{-e} \mod(N) \equiv 0 \pmod{\phi(N)}
$$

$$
\Leftrightarrow Hint - e^{-e} \mod(N) = k.\phi(N)
$$

Đến đây ta hoàn toàn có thể tính được $gcd(N, \phi(N))$ để tìm ra $p$
>$gcd(N, \phi(N)) = gcd(N, k.\phi(N))$. Dù có nhân thêm hằng số $k$ vào thì kết quả cũng không thay đổi.

Code :

from Crypto.Util.number import *
import math

hint = 119347490709709918515362500613767389632792382149593771026067086829182731765211255478693659388705133600879844115195595226603111752985962235917359759090718061734175658693105117154525703606445141788266279862259884063386378441258483507592794727728695131221071650602175884547070684687593047276747070248401583807925835550653444240529379502255688396376354105756898403267623695663194584556369065618489842778593026855625193720218739585629291162493093893452796713107895772  # Thay thế với giá trị hint thật sự
e = 65537
n = 947166029378215681573685007119017666168984033297752775080286377779867377305545634376587741948207865073328277940177160532951778642727687102119230712410226086882346969888194915073996590482747649286982920772432363906920327921033567974712097884396540431297147440251083706325071265030933645087536778803607268099965990824052754448809778996696907531977479093847266964842017321766588821529580218132015882438704409614373340861025360688571007185362228026637160817305181421
c = 216895836421936226664808806038131495725544658675106485670550453429609078893908601117272164909327632048129546753076380379045793859323244310633521321055388974634549104918284811813205866773238823220320222756056839297144222443834324484452750837978501262424186119512949111339142374067658940576220209924539508684423305539352188419127746551691195133913843198343764965016833190033138825402951884225991852311634388045499747652928427089105006744062452013466170009819761589

a = pow(e, -e, n)
b = hint - a
print(math.gcd(n,b)) #tìm p

p = 11154464433950896603539006848385997575762599678689916911564485722248359271231121825209554641104139016472716859893559760086095492396005986190538643135184309
q = n //p**2

d = pow(e, -1, p*(p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m).decode())

<details>
<summary> Flag</summary>
KCSC{0ne_p_1s_Enough_:vvvvv}
</details>

## VEM
Source code :

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random
from secret import FLAG
FLAG = b'KCSC{?????????????????????????????????????????}'

G = getPrime(256)
p = getPrime(512)
q = getPrime(512)
N = p*q


b, c = [random.randint(0, 2**64) for _ in range(2)]

def P_x(x):
    return x**2 + b * x + c

def gift(a):
    return pow(G, P_x(a), N)

def encrypt_message(msg, key):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(msg).hex()

MSG1 = bytes_to_long(b"Make KCSC")
MSG2 = bytes_to_long(b"Great Again")

options = """
1. Get gift
2. Flag
"""

print("I want to see you in KCSC")
print(f"N = {N}")
print(f'P(x) = x^2 + bx + {c}')
print('pay for g :)))))')
print("Choose your option")
print(options)

for _ in range(5):
    try:
        option = int(input('> '))
        
        if option == 1:
            msg = int(input('Give me your msg: '))
            print(f'Your gift: {gift(msg)}')

        elif option == 2:
            key = pow(G, 2*MSG1 * MSG2, N)
            enc_flag = encrypt_message(pad(FLAG, 16), long_to_bytes(key)[:32])
            print(f'Here is your enc_flag: {enc_flag}')

        else:
            print('Invalid option :((')
            exit()

    except Exception as e:
        print('Error occurred :((')
        exit()

Connect at : **nc 36.50.177.41 50103**
Khi kết nối và yêu cầu server trả về **Gift** và **Flag** ta có được một số thông tin sau :

N = 66422851609829581908519894021405472532869493396012525148538772879660323772148073582794350059176514854153514269951182744569398516221951651286005410281746441634004391384001383352139871541277717007023912845114861230988125278571906161755725596429854210396650124406391056980322194191811457282852865741731535801767
#P(x) = x^2 + bx + 9332981177283725171
enc_flag = '71169608941912ab22da5611b7d25eca1416296d903071e2e4d13c536aefeb80a45f9b1a9112cfa05ef64b97a1824a9e338e8045d5fb7762ee59df4f175b36af'
gift0 = 53480554051287845430396777333742232648895950980797205604637000246445218673322848768813926432212253796983748388388635567841530000156942815533036153088166307578313500425924265258949040126557997058903116698486316848571253341170920668596778354232567775937606231102192932755149439798034284974131141678383759781933
gift1 = 36979168626622579522489352531605207514613749700107553667194010582169809559332767483143324156654632762274506536225993954817887553804987828783663298602895055505776089620336858202664801036746833096355585790189937572129970906436499972316643208272029455101278562051352749879561498978912182971271837534759968916494
gift_minus1 = 43824401464699253079537156125879149908412544741318519518614316648144372953314261570048804422874234090067516001846800267139990340716539411164637801437923502753943829112380330867453009636159540800976456774170525167603061029666711711959546456803812815924661061476308399245433750635306892540946781490886370573962 #gift(-1)
c = 9332981177283725171

Flag của chúng ta được mã hóa AES theo kiểu **ECB**, vốn là một chế độ mã hóa rất yếu, nên chúng ta chỉ cần tìm được key là xong. Mà key của chúng ta được cho bởi công thức :
$$
key = G^{2.MSG1.MSG2} \mod(N)
$$

Có thể thấy, để tìm được key thì ta phải có được hằng số $G$. Muốn tìm được $G$ thì ta phải xét đến phương trình :
$$
gift(a) = G^{P(a)} \mod(N)
$$
>Với $P(a) = a^2 + b.a + c$ và $c = 9332981177283725171$

Ở đây, khi tôi yêu cầu server trả về giá trị $gift(0)$ điều đó cho tôi thông tin là :
$$
gift(0) = G^c \mod(N)
$$
>$P(0) = 0^2 + b.0 + c = c$

Tương tự đối với $gift(1)$ và $gift(-1)$ ta có :
$$
gift(1) = G^{c + b + 1} \mod(N)
$$

$$
gift(-1) = G^{c - b + 1} \mod(N)
$$

Có thể thấy rằng, $gift(1)$ và $gift(-1)$ của chúng ta đang phụ thuộc vào hằng số $G^b$. Mà $G$ ít ra ta còn biết nó được cho ngẫu nhiên (`G = getPrime(256)`), chứ còn $b$ là chả cho thông tin gì cả. Nên hướng đi lúc này sẽ là tìm cách loại bỏ đi hằng số $G^b$.

Thật vậy, khi ta nhân $gift(1)$ và $gift(-1)$ với nhau thì ta có :
$$
gift(1).gift(-1) = G^{(2c + 2)} \mod(N)
$$

$$
\Leftrightarrow gift(1).gift(-1) = (G^{c + 1})^2 \mod(N)
$$

Khi này không còn giá trị $G^b$ nữa. Tuy nhiên, $(G^{c+1})^2$ vẫn còn khá là khó tính. Chính vì vậy, ta sẽ tiếp tục tìm cách loại bỏ $c$ ở trên mũ của $G$.

Ta sẽ đem giá trị $gift(1).gift(-1)$ chia cho $gift(0)^2$ với mục đích loại bỏ $c$. Hãy nhớ rằng, trong trường hữu hạn $F_N$ thì việc chia cho số nào đó có nghĩa là **nhân nghịch đảo của số đó trong Modulo $N$**.
$$
\frac{gift(1).gift(-1)}{gift(0)^2} = \frac{(G^{c + 1})^2}{(G^{c})^2} \mod(N)
$$

$$
\Leftrightarrow gift(1).gift(-1).(gift(0)^{-2}\mod(N)) = G^2\mod(N)
$$

Như vậy, ta đã hoàn toàn loại bỏ được 2 hằng số $b,c$ ra khỏi phương trình tìm $G$. Việc còn lại là tính $G$ thôi, bằng cách tính giá trị vế trái, lấy Modulo $N$ và căn bậc 2 là ta sẽ có $G$.

from gmpy2 import iroot
gift0 = 53480554051287845430396777333742232648895950980797205604637000246445218673322848768813926432212253796983748388388635567841530000156942815533036153088166307578313500425924265258949040126557997058903116698486316848571253341170920668596778354232567775937606231102192932755149439798034284974131141678383759781933
gift1 = 36979168626622579522489352531605207514613749700107553667194010582169809559332767483143324156654632762274506536225993954817887553804987828783663298602895055505776089620336858202664801036746833096355585790189937572129970906436499972316643208272029455101278562051352749879561498978912182971271837534759968916494
gift_minus1 = 43824401464699253079537156125879149908412544741318519518614316648144372953314261570048804422874234090067516001846800267139990340716539411164637801437923502753943829112380330867453009636159540800976456774170525167603061029666711711959546456803812815924661061476308399245433750635306892540946781490886370573962
N = 66422851609829581908519894021405472532869493396012525148538772879660323772148073582794350059176514854153514269951182744569398516221951651286005410281746441634004391384001383352139871541277717007023912845114861230988125278571906161755725596429854210396650124406391056980322194191811457282852865741731535801767

VT = (gift1 * gift_minus1) * pow(gift0, -2, N)
G_bình = VT % N
G = iroot(G_bình, 2)
print(G)

<details>
<summary> G_value</summary>
(mpz(95833636607893153595899868495558756255023284827151623939362579569134227200097), True)
</details>

Và khi có được $G$ thì ta sẽ tính được key, và từ đó giải mã được **AES-ECB**

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from binascii import unhexlify
from Crypto.Util.number import bytes_to_long

enc_flag = '71169608941912ab22da5611b7d25eca1416296d903071e2e4d13c536aefeb80a45f9b1a9112cfa05ef64b97a1824a9e338e8045d5fb7762ee59df4f175b36af'
MSG1 = bytes_to_long(b"Make KCSC")
MSG2 = bytes_to_long(b"Great Again")
N = 66422851609829581908519894021405472532869493396012525148538772879660323772148073582794350059176514854153514269951182744569398516221951651286005410281746441634004391384001383352139871541277717007023912845114861230988125278571906161755725596429854210396650124406391056980322194191811457282852865741731535801767
G = 95833636607893153595899868495558756255023284827151623939362579569134227200097
key = pow(G, 2*MSG1*MSG2, N)

key_bytes = long_to_bytes(key)[:32]
enc_flag_bytes = unhexlify(enc_flag)

cipher = AES.new(key_bytes, AES.MODE_ECB)
flag = unpad(cipher.decrypt(enc_flag_bytes), AES.block_size)

print(flag.decode())

<details>
<summary> Flag</summary>
KCSC{Congr4tulati0n_to_you_0n_5olving_chall_lor:)))}
</details>

> Fact : Ở đây tôi chọn 3 giá trị $a = 0, 1, -1$ là bởi vì nó sẽ dễ dàng tính hơn so với chọn số khác. Ví dụ, nếu như chọn $a = 1, 2, 3$ thì ta sẽ có hệ 3 phương trình :
> $$
> gift(1) = G^{c + b + 1} \mod(N)
> $$
>
> $$
> gift(2) = G^{c + 2b + 4} \mod(N)
> $$
>
> $$
> gift(3) = G^{c + 3b + 9} \mod(N)
> $$
> Thật sự sẽ rất khó làm mất đi các hệ số $b, c$ ở mũ. Khi làm mất được $b$ thì ta vẫn còn $c$ và ngược lại. Chính vì vậy nên ở đây tôi chọn bộ 3 số $a = 0, 1, -1$ cho dễ dàng hơn.

## VICG
Source code :

from Crypto.Util.number import *
from hashlib import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import *
from secret import flag

class LCG():
    
    def __init__(self, seed, a, c, m):
        self.seed = seed
        self.a = a
        self.c = c
        self.m = m
        self.state = seed
        
    def next(self):
        
        self.seed = (self.a * self.seed ** 65537 + self.c) % m
        return self.seed >> 20
    
a = getPrime(50)
c = getPrime(50)
m = getPrime(100)
seed = getRandomInteger(50)

lcg = LCG(seed, a, c, m)

key = sha256(long_to_bytes(seed)).digest()
enc = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16))

hint = []

print(f"{enc = }")
print(f"{a = }")
print(f"{c = }")
print(f"{m = }")
print(f"{lcg.next() = }")

"""
enc = b'\x17j\x1b\xb1(eWHD\x98\t\xfc\x04\x94(\x18\xeaxT\xa6B*\xa0E\xe92\xe36!3\xbc\x96[\xa5\x82eG\xc2\x00\x7fM\xf0\xcb@tN\xf8\x01'      
a = 758872855643059
c = 814446603569537
m = 984792769709730047935594905989
lcg.next() = 241670272469283782290680
"""

Challenge này giới thiệu cho ta về **Linear Congruential Generator (LCG)** là một thuật toán sinh số giả ngẫu nhiên được sử dụng trong nhiều ứng dụng, theo đó nó sẽ là một dãy số có công thức truy hồi là :

$$
x_{n+1} = (a.x_{n} + c) \mod(N)
$$

Tuy nhiên, trong challenge này có sự khác biệt, ở đây $x_n$ của chúng ta còn có thêm số mũ $65537$. Đây là một số mũ khá là phổ biến trong mật mã RSA. Phải chăng nó sẽ có liên quan đến RSA?? Khi này ta sẽ viết lại công thức source code cho thành :
$$
seed_{n+1} = (a.seed_n^{65537} + c) \mod(m)
$$
>Ta có thể hiểu $seed_n$ ở đây đại diện cho giá trị đầu tiên của dãy số, cũng giống như $x_0$ trong dãy số vậy.

Nhiệm vụ của chúng ta là phải tìm cách tìm được giá trị của $seed_n$, vì nó được dùng để tạo ra key mã hóa **AES mode ECB**. ECB là chế độ mã hóa AES rất yếu nên ta chỉ cần tìm được key là sẽ giải mã được.

Ở đây, source code đã cho ta các giá trị của $a, c, m, seed_{n+1}$

Một điều đáng lưu ý là $seed_{n+1}$ của chúng ta đã được **dịch phải 20bits** tạo thành giá trị `lcg.next()` như trong source code. Ta sẽ phải đảo ngược giá trị của `lcg.next()` rồi từ đó giải phương trình tìm $seed_n$.

Hãy bắt đầu biến đổi phương trình với mục đích là cô lập $seed_n$, ta có :
$$
seed_{n+1} = (a.seed_n^{65537} + c) \mod(m)
$$

$$
\Leftrightarrow (a.seed_n^{65537} + c) \equiv seed_{n+1} \mod(m)
$$

$$
\Leftrightarrow (a.seed_n^{65537}) \equiv seed_{n+1} - c \mod(m)
$$

$$
\Leftrightarrow seed_n^{65537} \equiv (seed_{n+1} - c) \times (a^{-1} \mod(m)) \mod(m)
$$
>Đặt $g = (seed_{n+1} - c).(a^{-1} \mod(m))$

$$
\Leftrightarrow seed_n^{65537} \equiv g \mod(m)
$$

$$
\Leftrightarrow seed_n^{65537} \mod(m) = g
$$

Tới đây ta dễ dàng nhận ra đây là một kiểu mã hóa RSA, với số mũ $e = 65537$, modulus $m$, giá trị mã hóa $g$. Bây giờ ta sẽ giải mã nó bằng cách đi tìm nghịch đảo của số mũ $e$ trong modulus $\phi(m)$.

Modulus $m$ ở đây là một số nguyên tố (m = `getPrime(100)`) nên không khó để nhận ra $\phi(m) = m - 1$. Từ đây ta có :
$$
d = e^{-1} \mod(\phi(m))
$$
>Hay code trong python là : $d = pow(e, -1, m-1)$

Bây giờ ta chỉ cần đi mũ $d$ lên là sẽ làm mất đi số mũ $e = 65537$, từ đó có được $seed_n$. Ấy tuy nhiên, ta vẫn còn một vấn đề nữa. Đó là về vấn đề dịch bit phải của $seed_{n+1}$. Khi ta dịch bit trái lại thì đó chưa chắc là giá trị của $seed_{n+1}$ mà nó lại phải cộng thêm hằng số $k$, với k thuộc đoạn từ $[0, 2^{20} - 1]$. Ta có $seed_{n+1}$ như sau:
$$
seed_{n+1} = lcg.next() \times 2^{20} + k
$$
> với k thuộc đoạn từ $[0, 2^{20} - 1]$

$2^{20} - 1$ cũng không phải là giá trị quá lớn ($= 1048575$) nên ta có thể brute-force để tìm $seed_n$ được. Phương trình của ta lúc này :
$$
seed_n = (((lcg.next << 20) + k - c).(a^{-1} \mod(m)))^d \mod(m)
$$
>Phương trình hơi dài một tí nhưng không sao, ra được tới đây là ok rồi :>

Bây giờ ta chỉ cần brute-force $k$ là ra :
Code :

from Crypto.Util.number import *
from hashlib import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import *

a = 758872855643059
c = 814446603569537
m = 984792769709730047935594905989
e = 65537
lcgnext= 241670272469283782290680
e = 65537

d = pow(e, -1, m-1) #tính nghịch đảo của e trong modulus phi_m

def decrypt_aes_ecb(ciphertext, key):
    cipher = AES.new(key, AES.MODE_ECB)
    decrypted = cipher.decrypt(ciphertext)
    return unpad(decrypted, AES.block_size)

#brute-force k
for k in range(0, 2**20 - 1):
    seed = pow(((lcgnext << 20) + k - c) * pow(a, -1, m), d, m)
    key = sha256(long_to_bytes(seed)).digest()
    try:
        enc = b'\x17j\x1b\xb1(eWHD\x98\t\xfc\x04\x94(\x18\xeaxT\xa6B*\xa0E\xe92\xe36!3\xbc\x96[\xa5\x82eG\xc2\x00\x7fM\xf0\xcb@tN\xf8\x01'      
        flag = decrypt_aes_ecb(enc, key)
        if flag.startswith(b'KCSC{'):
            print("k =", k) 
            print("Flag :", flag.decode())
            break
    except ValueError:
        continue

<details>
<summary> Flag</summary>
KCSC{linear_congruential_generator(LCG)}
</details>

## AESOS
Source code :

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from aes import *
import os
from pwn import xor
from secret import flag

cipher = AES(os.urandom(16))

def encrypt(msg: bytes) -> bytes:
    iv = os.urandom(16)
    return iv + cipher.encrypt(msg, iv)

def decrypt(c: bytes) -> bytes:
    return cipher.decrypt(c[16:], c[:16])

while True:

    print("1. Encrypt")
    print("2. Decrypt")
    print("3. Flag")
    
    otp = int(input(">> "))
    
    if otp == 1:
        
        msg = bytes.fromhex(input("Enter your message: "))
        print(encrypt(msg).hex())
    
    elif otp == 2:
        
        msg = bytes.fromhex(input("Enter the ciphertext: "))
        print(decrypt(msg).hex())
        
    elif otp == 3:
        
        print(encrypt(flag).hex())
        
    else:
        exit()

Connect at : **nc 36.50.177.41 50101**

Ở đây challenge cho ta 3 option để tương tác với server. Khi nhìn vào source code, ta có thể thấy flag của chúng ta được mã hóa ở chế độ **PCBC**, và được giải mã ở chế độ **CBC**. Điều này có thể dẫn đến một lỗ hỏng bảo mật lớn mà ta sẽ khai thác.

Hãy bắt đầu thao tác với server. Khi chọn option3, server sẽ trả cho ta flag đã được mã hóa dưới chế độ **PCBC**.

enc_pcbc = '323eaa80f217bd129db30f0e06e6691561d3221eeceedf18499f3b5ac1ffb7b5c1d9b6a9eaf806e64167b808c3fccdf653206dce0748956f2ce3aff88115ce559b2b6dcdb59bda945064edad364b6f24cda39ab0f3d9b2f8e7a81973d12c7edd8a5a8a265f0c53bdaac60ac4ec07e38094214a222b8b237eded6f426fc405139e85563e9817f2ba79561a62ac2bd71493b84c9e5684021029a49842fe4de238689920f08df775d051aee77628b84b29b1c0491a347ec15d93220d881ad15b932175041d0c74d6447e030e2d51b662c76a56f52602230fed074c22324141dc26ae6327e73286c673b509a6024c2b1e89122bc4bfd1663d930fe1395de720aa8c93edc802c8116a5428e3d31a6b4fc94580a4688ebe0dbc887400a9cd1e0e71fe9065b2ff9957cd2b9f8ff2a9f8c9c31b689bda25e417f935c1e2a1d0f5a3ff915159d3466ac51feb8ada5833afdf2528432a2ddd71a9aa30c529d8c8cd22aeec5e85245950454a8e94311e9db18284304cef50503145877b214c3f0600404858ce3d16f86cb7f4bc672f04115a911c0ea4433b3070335e31d15d661e3b445b65a02069e67fa271e1c0a330c3bc12c986218ca8fc945183797011bb3ddfc9a008cdcfff0dd68c02fd3a92d06a9158e6214432921dc27c64aabb2cb18b82cfdf9906c855c0a40342e4270025203b696141478a15eacf1bf3b671877957ad26ab932e2b1cda811340f7441eddbb46b1d1f4308d1c942949ec5b3a093e9d64769301ebc22bd07096a1d9601ab80b8551a8b58131015c3dbf1d33e7d00c8d47d14fad6bf038a9d12de3bdea4415891dbdf05834001def8585b56e005df7468d94352a5'

Và khi ta dùng `enc_pcbc` đưa vào hàm giải mã (option2) thì server sẽ trả về cho ta flag đã được giải mã ở mode **CBC** :

dec_cbc = '4b4353437b50726f7061676174696e6714203a3313350030120d08021f360d0f3e0a071906022d77322f2d20420b0b0d3e191c061e063849242a2c247637011537150030120d08021f360d0f3e0a071906022d3010331f0f0a360d1c04111a360d0e2f07172d5d0e0d060d1f3a1b1c3e0a07190602291f5431300e043b063716081d360a02285b51333a0930100a001400062c013a00040602093b3c1c0e310404062c0c312c190909333c0a18090b151116271d312b1b37152d0c19110f0406113a111a3b1109361e1b1b150d1e3e030d3a07310000051b1719000c021e73280916312801090f2d18032b1e06024200041d3c051c1c18360f147128210b310f262c202d141f100c42384b3e2a0600322f2d20343200023a5c3304080d1c3a1a18300a180037290d15083e1e07000d2716301d1b002c27373a142d121f1d072a113004043e1d06113a08063a140500161800110205361a1c0027042d071a060c1e2c3e0d0d2f1c0d172b150a11290b031a10343c0b150e0a00113a1a11360c0b3006053c101c161b1701713d29000502001207171a263336263b4330280c473a3e19361d0636372b22330415051145300f31290c0d1d1b1b3e051a2514070c0b3136183a171c0a2d3900012c012c0708300a05712b3d0b330f02172c371d214030070e4d2d2c1e18000502001301016f00130c171a26041c0c310e31332c30313a141d2b21092b400c31001a0a0e1e1b1f0200362638005e0c0d1d1b1b48330a1b14070c1c313e1a093c16031d4a34103e1a153a03330005022b07141b3c1f1c000d03001303131b1b041156095c776c'

Nếu đọc kĩ code thì ở `enc_pcbc` nó dài hơn so với `dec_cbc` vì 16bytes đầu của `enc_pcbc` là **IV (Initialization Vector)**. Bây giờ ta sẽ phân tích để giải mã.

Ta sẽ chia `enc_pcbc` và `dec_cbc` thành các **blockFlag** có độ dài là 16bytes. Nếu để ý kĩ thì **blockFlag** đầu tiên của `dec_cbc` là văn bản có nghĩa : `KCSC{Propagating`. Bởi vì quá trình giải mã block đầu tiên của PCBC giống với block CBC nên ta có ngay được Plaintext của **blockFlag1**.
$$
FLag1 \oplus IV -> AES = Ct1
$$

$$
Ct1 -> AES \oplus IV = Flag1
$$

Bắt đầu với **blockFlag2**. Ở đây nó được encrypt bằng cách :
$$
Flag2 \oplus Flag1 \oplus Ct1 -> AES = Ct2
$$

Và khi bỏ vào hàm **decrypt CBC** thì ta chỉ còn : Flag2 XOR plaintext vì mode CBC nó XOR với ciphertext trước rồi vì đã mất ciphertext nên công việc của ta bây giờ là đem **blockFlag2** của `dec_cbc` XOR với blockFlag1 là `KCSC{Propagating` là ra **blockFlag2**.

Ví dụ code minh họa :

from pwn import xor
dec_cbc = '4b4353437b50726f7061676174696e6714203a3313350030120d08021f360d0f3e0a071906022d77322f2d20420b0b0d3e191c061e063849242a2c247637011537150030120d08021f360d0f3e0a071906022d3010331f0f0a360d1c04111a360d0e2f07172d5d0e0d060d1f3a1b1c3e0a07190602291f5431300e043b063716081d360a02285b51333a0930100a001400062c013a00040602093b3c1c0e310404062c0c312c190909333c0a18090b151116271d312b1b37152d0c19110f0406113a111a3b1109361e1b1b150d1e3e030d3a07310000051b1719000c021e73280916312801090f2d18032b1e06024200041d3c051c1c18360f147128210b310f262c202d141f100c42384b3e2a0600322f2d20343200023a5c3304080d1c3a1a18300a180037290d15083e1e07000d2716301d1b002c27373a142d121f1d072a113004043e1d06113a08063a140500161800110205361a1c0027042d071a060c1e2c3e0d0d2f1c0d172b150a11290b031a10343c0b150e0a00113a1a11360c0b3006053c101c161b1701713d29000502001207171a263336263b4330280c473a3e19361d0636372b22330415051145300f31290c0d1d1b1b3e051a2514070c0b3136183a171c0a2d3900012c012c0708300a05712b3d0b330f02172c371d214030070e4d2d2c1e18000502001301016f00130c171a26041c0c310e31332c30313a141d2b21092b400c31001a0a0e1e1b1f0200362638005e0c0d1d1b1b48330a1b14070c1c313e1a093c16031d4a34103e1a153a03330005022b07141b3c1f1c000d03001303131b1b041156095c776c'

byte1 = bytes.fromhex(dec_cbc[:32])
byte2 = bytes.fromhex(dec_cbc[32:64])
flag2 = xor(byte1, byte2)
print(flag2)
#output : b'_cipher_block_ch'

Và cũng tương tự như vậy, ta suy ra công thức tổng quát ở đây là :
$$
blockFlag_n = blockFlag_{n-1} \oplus decCBC_n
$$

Code :

from pwn import xor

enc_pcbc = '323eaa80f217bd129db30f0e06e6691561d3221eeceedf18499f3b5ac1ffb7b5c1d9b6a9eaf806e64167b808c3fccdf653206dce0748956f2ce3aff88115ce559b2b6dcdb59bda945064edad364b6f24cda39ab0f3d9b2f8e7a81973d12c7edd8a5a8a265f0c53bdaac60ac4ec07e38094214a222b8b237eded6f426fc405139e85563e9817f2ba79561a62ac2bd71493b84c9e5684021029a49842fe4de238689920f08df775d051aee77628b84b29b1c0491a347ec15d93220d881ad15b932175041d0c74d6447e030e2d51b662c76a56f52602230fed074c22324141dc26ae6327e73286c673b509a6024c2b1e89122bc4bfd1663d930fe1395de720aa8c93edc802c8116a5428e3d31a6b4fc94580a4688ebe0dbc887400a9cd1e0e71fe9065b2ff9957cd2b9f8ff2a9f8c9c31b689bda25e417f935c1e2a1d0f5a3ff915159d3466ac51feb8ada5833afdf2528432a2ddd71a9aa30c529d8c8cd22aeec5e85245950454a8e94311e9db18284304cef50503145877b214c3f0600404858ce3d16f86cb7f4bc672f04115a911c0ea4433b3070335e31d15d661e3b445b65a02069e67fa271e1c0a330c3bc12c986218ca8fc945183797011bb3ddfc9a008cdcfff0dd68c02fd3a92d06a9158e6214432921dc27c64aabb2cb18b82cfdf9906c855c0a40342e4270025203b696141478a15eacf1bf3b671877957ad26ab932e2b1cda811340f7441eddbb46b1d1f4308d1c942949ec5b3a093e9d64769301ebc22bd07096a1d9601ab80b8551a8b58131015c3dbf1d33e7d00c8d47d14fad6bf038a9d12de3bdea4415891dbdf05834001def8585b56e005df7468d94352a5'
dec_cbc = '4b4353437b50726f7061676174696e6714203a3313350030120d08021f360d0f3e0a071906022d77322f2d20420b0b0d3e191c061e063849242a2c247637011537150030120d08021f360d0f3e0a071906022d3010331f0f0a360d1c04111a360d0e2f07172d5d0e0d060d1f3a1b1c3e0a07190602291f5431300e043b063716081d360a02285b51333a0930100a001400062c013a00040602093b3c1c0e310404062c0c312c190909333c0a18090b151116271d312b1b37152d0c19110f0406113a111a3b1109361e1b1b150d1e3e030d3a07310000051b1719000c021e73280916312801090f2d18032b1e06024200041d3c051c1c18360f147128210b310f262c202d141f100c42384b3e2a0600322f2d20343200023a5c3304080d1c3a1a18300a180037290d15083e1e07000d2716301d1b002c27373a142d121f1d072a113004043e1d06113a08063a140500161800110205361a1c0027042d071a060c1e2c3e0d0d2f1c0d172b150a11290b031a10343c0b150e0a00113a1a11360c0b3006053c101c161b1701713d29000502001207171a263336263b4330280c473a3e19361d0636372b22330415051145300f31290c0d1d1b1b3e051a2514070c0b3136183a171c0a2d3900012c012c0708300a05712b3d0b330f02172c371d214030070e4d2d2c1e18000502001301016f00130c171a26041c0c310e31332c30313a141d2b21092b400c31001a0a0e1e1b1f0200362638005e0c0d1d1b1b48330a1b14070c1c313e1a093c16031d4a34103e1a153a03330005022b07141b3c1f1c000d03001303131b1b041156095c776c'

blocks = [bytes.fromhex(dec_cbc[i:i+32]) for i in range(0, len(dec_cbc), 32)]

result = blocks[0]
final_result = result  
for block in blocks[1:]:
    result = xor(result, block)
    final_result += result

print(final_result.decode(errors='ignore'))

<details>
<summary> Flag</summary>
KCSC{Propagating_cipher_block_chaining_(PCBC)The_propagating_cipher_block_chaining_or_plaintext_cipher-block_chaining[26]_mode_was_designed_to_cause_small_changes_in_the_ciphertext_to_propagate_indefinitely_when_decrypting,_as_well_as_when_encrypting._In_PCBC_mode,_each_block_of_plaintext_is_XORed_with_both_the_previous_plaintext_block_and_the_previous_ciphertext_block_before_being_encrypted._Like_with_CBC_mode,_an_initialization_vector_is_used_in_the_first_block._Unlike_CBC,_decrypting_PCBC_with_the_incorrect_IV_(initialization_vector)_causes_all_blocks_of_plaintext_to_be_corrupt.}
</details>

>**Fun Fact** : Dưới đây là hình ảnh 1 phần flag tôi có được do thao tác Decrypt, Encrypt flag liên tục với server. Tôi cũng quên mất mình làm như nào rồi =)))