<h1 style="text-align:center;">KCSC Recruitment 2025</h1>


# Crypto 1 (easy)

<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/S1yNVCsDJl.png"/>

- **Source:**

    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
    99070322718633589075437462797565157261778565342202176866775343970398558639214129862647491552411934954337080928975984888590350647667063750589996693551004764949048370796506334502440334616612079528441181921243264137829513725003752633040825654275249100544290948338516838946174770287568358642193272862193796894044937197882972942736350187023160283258646203934697126833099845086570117310993425665455046278368788256843647321433937611726466080931200057154600456738627871172358125025243308598393199170155505096434440339433895197600955266878886512068835988415711337072167542113641557473147599428014808952558696371214362762804029219711275834667722478355607836912560341298862576500518929722837267759516608623300378294362866958920710706131156072317563285732965572961520111862487408104
    4053829493753080394597319030520465552249075460276768487813206903952134102796024072650537404512981555893331018255239607908419904554570951529767887735220350920134963507895001907309725345634404748146887358629605419756823088475689769294303699918630919892363333011358649952996211367887394670736389996674537151867058156643368735877078538193576703224594833465330136899282032495128158051461158831558808541670885217172490157676355847572589184884710346372276161554121356404
     """

- **Flag** của ta được mã hóa **RSA** nên nếu ta tìm được giá trị $p$ và $q$ của modulus $n$ thì ta sẽ giải mã được **Ciphertext** rất dễ dàng.

- Nhận thấy rằng giá trị của $p$ và $q$ được biểu diễn qua một hệ phương trình như sau:

$$
\left\{\begin{matrix}
13 \times q ^ 2 + 5\times p \times q + 2 \times p ^ 5 = k_1\\
7 \times q ^ 3 + p ^ 3 = k_2
\end{matrix}\right.
$$

- Mình thấy hệ phương trình này giải tay khá là cực nhưng nếu dùng các thư viện toán học thì sẽ rất nhanh nên để tiết kiệm thời gian, mình sẽ dùng thư viện **Sympy** để giải. Có được $p,q$ thì bài toán kết thúc.

- **Script:**

    from sympy import var, Eq, solve
    e = 0x10001
    n = 68288521803749096598885637638053621717196600162883393314204537792265324550130476000830582459892601191221713398147068471895218340440441520348186049243098557276069294337290348570168822004443403024217772173472817801983123070596861372926544266786307347422625999741472764054251261966242723803223755250857431959613
    c = 51484360656675894405169578577777421818221080188874188339332704212766014455602299232733441854614491353614936672698767100621643701474052897096397257567627546370308824123953740553988694850896612092526733722171750215446879926157508653359056454370778767748861899945472045315573513667461778478951641271690253340703
    k1 = 99070322718633589075437462797565157261778565342202176866775343970398558639214129862647491552411934954337080928975984888590350647667063750589996693551004764949048370796506334502440334616612079528441181921243264137829513725003752633040825654275249100544290948338516838946174770287568358642193272862193796894044937197882972942736350187023160283258646203934697126833099845086570117310993425665455046278368788256843647321433937611726466080931200057154600456738627871172358125025243308598393199170155505096434440339433895197600955266878886512068835988415711337072167542113641557473147599428014808952558696371214362762804029219711275834667722478355607836912560341298862576500518929722837267759516608623300378294362866958920710706131156072317563285732965572961520111862487408104
    k2 = 4053829493753080394597319030520465552249075460276768487813206903952134102796024072650537404512981555893331018255239607908419904554570951529767887735220350920134963507895001907309725345634404748146887358629605419756823088475689769294303699918630919892363333011358649952996211367887394670736389996674537151867058156643368735877078538193576703224594833465330136899282032495128158051461158831558808541670885217172490157676355847572589184884710346372276161554121356404

    p, q = var("p, q")
    eq1 = Eq(13 * q ** 2 + 5*p * q + 2 * p ** 5, k1)
    eq2 = Eq(7 * q ** 3 + p ** 3, k2)

    solutions = solve([eq1, eq2])[0]

    p = int(solutions[p])
    q = int(solutions[q])
    d = pow(e, -1, n-p-q+1)

    print(pow(c, d, n).to_bytes(50))

:::spoiler Flag
**KCSC{solv1ng_equ4ti0ns_with_r3sult4nts_is_f4n}**
:::
# VlCG (easy)

<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/SkkL40iPyx.png"/>

- **Source:**

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

- Phân tích source, ta thấy rằng **key** của AES được tính thông qua `key = sha256(long_to_bytes(seed)).digest()`, tức nhiệm vụ của ta là phải tìm được **seed**.

- Công thức của $\text{seed}$ như sau:
$$\text{S} \equiv \text{a} \times \text{seed}^{65537} + \text{c} \pmod {\text{m}}$$

$$\Leftrightarrow \text{seed}^{65537} \equiv (\text{S} - \text{c}) \times \text{a}^{-1} \pmod {\text{m}}$$

- Giờ ta phải triệt tiêu đi số mũ $65537$ của $\text{seed}$ thì sẽ có được $\text{seed}$. Tương tự như **RSA**, ta sẽ đi tính $\text{d} = 65537^{-1} \pmod{\phi(m)}$ với $\phi(m) = m-1$ vì $m$ là số nguyên tố.
- Sau đó lấy $((\text{S} - \text{c}) \times \text{a}^{-1})^{d} \mod m$ là có được $\text{seed}$.

- Tuy nhiên để tăng độ khó thì Challenge tiếp tục bỏ đi $20$ bit cuối (khoảng 1 triệu) của $\text{S}$. Vì vậy ta cần thêm một bước là brute force $20$ bit cuối của $\text{S}$.
$$\text{S} = (\text{lcg.next()} << 20) + i \hspace{3mm} \{1 < i < 2^{20}\}$$

- **Script:**

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

    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
    next_seed = 241670272469283782290680

    e = pow(65537, -1, m-1)
    for i in trange(1, 2**20):

        S = (next_seed << 20) + i # nhớ thêm dấu ngoặc, thiếu là ăn đủ
        seed = (pow((S - c) * pow(a, -1, m), e, m)) % m
        key = sha256(long_to_bytes(seed)).digest()

        flag = AES.new(key, AES.MODE_ECB).decrypt(enc)
        if b"KCSC{" in flag:
            print(flag)
            break

:::spoiler Flag
seed = 504545958124800
**KCSC{linear_congruential_generator(LCG)}**
:::
# Zoltraak (easy)
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/rk0v40iPkl.png"/>

- **Source:**

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

    """
    c = 216895836421936226664808806038131495725544658675106485670550453429609078893908601117272164909327632048129546753076380379045793859323244310633521321055388974634549104918284811813205866773238823220320222756056839297144222443834324484452750837978501262424186119512949111339142374067658940576220209924539508684423305539352188419127746551691195133913843198343764965016833190033138825402951884225991852311634388045499747652928427089105006744062452013466170009819761589
    hint = 119347490709709918515362500613767389632792382149593771026067086829182731765211255478693659388705133600879844115195595226603111752985962235917359759090718061734175658693105117154525703606445141788266279862259884063386378441258483507592794727728695131221071650602175884547070684687593047276747070248401583807925835550653444240529379502255688396376354105756898403267623695663194584556369065618489842778593026855625193720218739585629291162493093893452796713107895772
    n = 947166029378215681573685007119017666168984033297752775080286377779867377305545634376587741948207865073328277940177160532951778642727687102119230712410226086882346969888194915073996590482747649286982920772432363906920327921033567974712097884396540431297147440251083706325071265030933645087536778803607268099965990824052754448809778996696907531977479093847266964842017321766588821529580218132015882438704409614373340861025360688571007185362228026637160817305181421
    """

- Challenge cho ta các công thức sau:
$$\text{d} \equiv e^{-1} \pmod {\phi(n)} \hspace{5mm} (1)$$

$$\text{hint} \equiv \text{d}^e \pmod n \hspace{5mm} (2)$$

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

$$n = p^2 \times q$$
- Từ $(1)$ ta mũ hai vế cho $e$ được:
$$\text{d}^e \equiv e^{-e} \pmod {\phi(n)}$$
- Vì $p | \phi(n)$ nên ta có thể viết phương trình trên thành:
$$\text{d}^e \equiv e^{-e} \pmod {p} \hspace{5mm} (*)$$

- Với phương trình $(2)$, ta nhân hai vế cho $e^e \mod n$ được:
$$\text{hint} \times (e^e \mod n) \equiv \text{d}^e \times (e^e \mod n) \pmod n$$

- Vì $p|n$ nên ta có thể viết lại phương trình trên như sau:
$$\text{hint} \times (e^e \mod n) \equiv \text{d}^e \times (e^e \mod p) \pmod p \hspace{5mm} (**)$$

- Thay $(*)$ vào $(**)$ được:
$$\text{hint} \times (e^e \mod n) \equiv (e^{-e} \mod p) \times (e^e \mod p) \pmod p$$

$$\Leftrightarrow \text{hint} \times (e^e \mod n) \equiv (e^{-e} \times e^e \mod p) \pmod p$$

$$\Leftrightarrow \text{hint} \times (e^e \mod n) \equiv 1 \pmod p$$

> $\Rightarrow \text{hint} \times (e^e \mod n) - 1 = k \times p$

- Giờ ta chỉ cần tính **GCD** của $\text{hint} \times (e^e \mod n) - 1$ và $n$ là có $p$, bài toán kết thúc.

- **Script:**

    from Crypto.Util.number import *
    e = 0x10001
    c = 216895836421936226664808806038131495725544658675106485670550453429609078893908601117272164909327632048129546753076380379045793859323244310633521321055388974634549104918284811813205866773238823220320222756056839297144222443834324484452750837978501262424186119512949111339142374067658940576220209924539508684423305539352188419127746551691195133913843198343764965016833190033138825402951884225991852311634388045499747652928427089105006744062452013466170009819761589
    hint = 119347490709709918515362500613767389632792382149593771026067086829182731765211255478693659388705133600879844115195595226603111752985962235917359759090718061734175658693105117154525703606445141788266279862259884063386378441258483507592794727728695131221071650602175884547070684687593047276747070248401583807925835550653444240529379502255688396376354105756898403267623695663194584556369065618489842778593026855625193720218739585629291162493093893452796713107895772
    n = 947166029378215681573685007119017666168984033297752775080286377779867377305545634376587741948207865073328277940177160532951778642727687102119230712410226086882346969888194915073996590482747649286982920772432363906920327921033567974712097884396540431297147440251083706325071265030933645087536778803607268099965990824052754448809778996696907531977479093847266964842017321766588821529580218132015882438704409614373340861025360688571007185362228026637160817305181421

    p = GCD(hint * pow(e, e, n) - 1, n)
    q = n // (p**2)

    phi = p * (p-1) * (q-1)
    d = pow(e, -1, phi)

    print(long_to_bytes(pow(c, d, n)))

:::spoiler Flag
**KCSC{0ne_p_1s_Enough_:vvvvv}**
:::

Ngoài cách giải trên ra thì còn một cách khác đơn giản hơn đó là sử dụng **Nhị thức Newton**

n = p*p*q
phi = p*(p-1)*(q-1)
h = d^e mod n

e^e*h = (e*d)^e mod n
e^e*h = (e*d)^e mod p
e^e*h = (1 + p*(p-1)*(q-1))^e mod p

khai triển nhị thức newton của (1 + p*(p-1)*(q-1))^e mod p ta được 1
vậy ta được phương trình mới là:
e^e*h = 1 mod p

=> e^e*h - 1 = k*p

=> gcd(e^e*h - 1, n) == p

# AESOS (easy/medium)

<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/r1_iNRswkg.png"/>

- **chal.py**

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

:::spoiler **aes.py**

#!/usr/bin/env python3
"""
This is an exercise in secure symmetric-key encryption, implemented in pure
Python (no external libraries needed).

Original AES-128 implementation by Bo Zhu (http://about.bozhu.me) at 
https://github.com/bozhu/AES-Python . PKCS#7 padding, CBC mode, PKBDF2, HMAC,
byte array and string support added by me at https://github.com/boppreh/aes. 
Other block modes contributed by @righthandabacus.


Although this is an exercise, the `encrypt` and `decrypt` functions should
provide reasonable security to encrypted messages.
"""


s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

inv_s_box = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)


def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]


def inv_sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = inv_s_box[s[i][j]]


def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


def inv_shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]


# learned from https://web.archive.org/web/20100626212235/http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


def mix_single_column(a):
    # see Sec 4.1.2 in The Design of Rijndael
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)


def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])


def inv_mix_columns(s):
    # see Sec 4.1.3 in The Design of Rijndael
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v

    mix_columns(s)


r_con = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)


def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    """ Converts a 4x4 matrix into a 16-byte array.  """
    return bytes(sum(matrix, []))

def xor_bytes(a, b):
    """ Returns a new byte array with the elements xor'ed. """
    return bytes(i^j for i, j in zip(a, b))

def inc_bytes(a):
    """ Returns a new byte array with the value increment by 1 """
    out = list(a)
    for i in reversed(range(len(out))):
        if out[i] == 0xFF:
            out[i] = 0
        else:
            out[i] += 1
            break
    return bytes(out)

def pad(plaintext):
    """
    Pads the given plaintext with PKCS#7 padding to a multiple of 16 bytes.
    Note that if the plaintext size is a multiple of 16,
    a whole block will be added.
    """
    padding_len = 16 - (len(plaintext) % 16)
    padding = bytes([padding_len] * padding_len)
    return plaintext + padding

def unpad(plaintext):
    """
    Removes a PKCS#7 padding, returning the unpadded text and ensuring the
    padding was correct.
    """
    padding_len = plaintext[-1]
    assert padding_len > 0
    message, padding = plaintext[:-padding_len], plaintext[-padding_len:]
    assert all(p == padding_len for p in padding)
    return message

def split_blocks(message, block_size=16, require_padding=True):
        assert len(message) % block_size == 0 or not require_padding
        return [message[i:i+16] for i in range(0, len(message), block_size)]


class AES:
    """
    Class for AES-128 encryption with CBC mode and PKCS#7.

    This is a raw implementation of AES, without key stretching or IV
    management. Unless you need that, please use `encrypt` and `decrypt`.
    """
    rounds_by_key_size = {16: 10, 24: 12, 32: 14}
    def __init__(self, master_key):
        """
        Initializes the object with a given key.
        """
        assert len(master_key) in AES.rounds_by_key_size
        self.n_rounds = AES.rounds_by_key_size[len(master_key)]
        self._key_matrices = self._expand_key(master_key)

    def _expand_key(self, master_key):
        """
        Expands and returns a list of key matrices for the given master_key.
        """
        # Initialize round keys with raw key material.
        key_columns = bytes2matrix(master_key)
        iteration_size = len(master_key) // 4

        i = 1
        while len(key_columns) < (self.n_rounds + 1) * 4:
            # Copy previous word.
            word = list(key_columns[-1])

            # Perform schedule_core once every "row".
            if len(key_columns) % iteration_size == 0:
                # Circular shift.
                word.append(word.pop(0))
                # Map to S-BOX.
                word = [s_box[b] for b in word]
                # XOR with first byte of R-CON, since the others bytes of R-CON are 0.
                word[0] ^= r_con[i]
                i += 1
            elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
                # Run word through S-box in the fourth iteration when using a
                # 256-bit key.
                word = [s_box[b] for b in word]

            # XOR with equivalent word from previous iteration.
            word = xor_bytes(word, key_columns[-iteration_size])
            key_columns.append(word)

        # Group key words in 4x4 byte matrices.
        return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]

    def encrypt_block(self, plaintext):
        assert len(plaintext) == 16

        plain_state = bytes2matrix(plaintext)

        add_round_key(plain_state, self._key_matrices[0])

        for i in range(1, self.n_rounds):
            sub_bytes(plain_state)
            shift_rows(plain_state)
            mix_columns(plain_state)
            add_round_key(plain_state, self._key_matrices[i])

        sub_bytes(plain_state)
        shift_rows(plain_state)
        add_round_key(plain_state, self._key_matrices[-1])

        return matrix2bytes(plain_state)

    def decrypt_block(self, ciphertext):
        assert len(ciphertext) == 16

        cipher_state = bytes2matrix(ciphertext)

        add_round_key(cipher_state, self._key_matrices[-1])
        inv_shift_rows(cipher_state)
        inv_sub_bytes(cipher_state)

        for i in range(self.n_rounds - 1, 0, -1):
            add_round_key(cipher_state, self._key_matrices[i])
            inv_mix_columns(cipher_state)
            inv_shift_rows(cipher_state)
            inv_sub_bytes(cipher_state)

        add_round_key(cipher_state, self._key_matrices[0])

        return matrix2bytes(cipher_state)

    def encrypt(self, plaintext, iv):
        assert len(iv) == 16
        plaintext = pad(plaintext)
        blocks = []
        prev_ciphertext = iv
        prev_plaintext = bytes(16)
        for plaintext_block in split_blocks(plaintext):
            ciphertext_block = self.encrypt_block(xor_bytes(plaintext_block, xor_bytes(prev_ciphertext, prev_plaintext)))
            blocks.append(ciphertext_block)
            prev_ciphertext = ciphertext_block
            prev_plaintext = plaintext_block
        return b''.join(blocks)

    def decrypt(self, ciphertext, iv):
        assert len(iv) == 16
        blocks = []
        previous = iv
        for ciphertext_block in split_blocks(ciphertext):
            blocks.append(xor_bytes(previous, self.decrypt_block(ciphertext_block)))
            previous = ciphertext_block
        return b''.join(blocks)

:::

- Ngồi phân tích file `chal.py` thì thấy nó khá bình thường, có hàm encrypt **plaintext**, có hàm decrypt để giải mã **ciphertext** và có cả option để trả về ciphertext của **Flag**.

- Mình thử bỏ **Flag** hàm decrypt thử thì như dự đoán là nó không trả về toàn bộ Flag mà chỉ có 16 bytes đầu của Flag là đúng, nên chắc chắc là hàm **encrypt** hoặc hàm **decrypt** có vấn đề. Nên chúng ta tiến hành đi khám file `aes.py`.

- Phân tích hai hàm `encrypt()` và `decrypt()` của file `aes.py`:

    def encrypt(self, plaintext, iv):
        assert len(iv) == 16
        plaintext = pad(plaintext)
        blocks = []
        prev_ciphertext = iv
        prev_plaintext = bytes(16)
        for plaintext_block in split_blocks(plaintext):
            ciphertext_block = self.encrypt_block(xor_bytes(plaintext_block, xor_bytes(prev_ciphertext, prev_plaintext)))
            blocks.append(ciphertext_block)
            prev_ciphertext = ciphertext_block
            prev_plaintext = plaintext_block
        return b''.join(blocks)

    def decrypt(self, ciphertext, iv):
        assert len(iv) == 16
        blocks = []
        previous = iv
        for ciphertext_block in split_blocks(ciphertext):
            blocks.append(xor_bytes(previous, self.decrypt_block(ciphertext_block)))
            previous = ciphertext_block
        return b''.join(blocks)

- Nhận thấy rằng **Flag** của ta được encrypt bằng mode **PCBC** nhưng hàm decrypt lại là mode **CBC** nên khi ta đưa ciphertext vào thì chỉ có **16 bytes** đầu tiên của plaintext là đúng.

- Vì hàm decrypt là mode **CBC** nên nó đã có bước $\oplus$ với **IV** (ciphertxt trước đó), để biến hàm decrypt thành mode **PCBC** thì thứ còn thiếu là $\oplus$ với **plaintext** trước đó thôi.
- Nhận Ciphertext của **Flag** (option 3):

    bd1f37f09f2d51f0af5526862aacaa49978c6ec9d8ff8a1f1da21641fab8d49f45fd3bf409c2bfe61c7dba5b43e32e4618daf4c150a8962bf416fac9f58e6359abc1da5949259468ee2d1cfc3a043eee7abf310cc158078f6a42f59f70d1671cfa3969b1f99422a520bafd676941422787a6f96d5ee3c860f3638f87c77426ae48f8af7a9a64f3fc7759140ba9a44b7675509036cc976e35dcd4ad86caeb21cd100996b444a688608c3563e859fc2fc69054af99a0221e138b3b0ab449e01f62668f47531d396d5fc5cd972e2fe14c0413045fc349435789b6823e2645424157e4f556349f810b5c3937150b8b55b70077cc8713baecceabe1037cd1f56b9ee45a654528c87c3cf093e79dbdb0769652a20c88ec8a781381cebf3a766f5be2a2c67d48c7b1096e39818ea7e54d98cdec413073351bffcaaa6fd741a1106bc7798d81d6f0efc4eb8a3f5dbe474f19c01af6225dbd2746e800ce15a61ef086df12ee4c89a9b92505802a68d29f669611eab805bd7620ae57d7ee4b23cfd5b4b44014487aa3a8abab03435bf0399041a958c9b1f39643926554f4b816868d3df0d2d52dbdfee5fe9d0221cbc2a4665ccaa7a378f7e4155b2244adb189a1e966c2021aab4d7ac67b77c4e95ba05ac9c58d2f27e927530cb62d32c018c2fa3ab07360734aa6b29582b744fd53c8a556b75781d208e994e7022d8752687431175f79e4e139c3da765cbd79c400fa6f7fad47d41c42ab414dcc1de485e269d86c29112a55bfffaf8e4fd7aa9e7dec7a8d06d5b6ed4840772c2fd281ad2f6e893bf1132d5c01e92823abe29bdac8379806aafb869584b4e1c1b6ccb32f8405d580a84868

- Sau đó đưa qua hàm **decrypt** (option 2), ta được output giải mã bằng **CBC** như sau:

    4b4353437b50726f7061676174696e6714203a3313350030120d08021f360d0f3e0a071906022d77322f2d20420b0b0d3e191c061e063849242a2c247637011537150030120d08021f360d0f3e0a071906022d3010331f0f0a360d1c04111a360d0e2f07172d5d0e0d060d1f3a1b1c3e0a07190602291f5431300e043b063716081d360a02285b51333a0930100a001400062c013a00040602093b3c1c0e310404062c0c312c190909333c0a18090b151116271d312b1b37152d0c19110f0406113a111a3b1109361e1b1b150d1e3e030d3a07310000051b1719000c021e73280916312801090f2d18032b1e06024200041d3c051c1c18360f147128210b310f262c202d141f100c42384b3e2a0600322f2d20343200023a5c3304080d1c3a1a18300a180037290d15083e1e07000d2716301d1b002c27373a142d121f1d072a113004043e1d06113a08063a140500161800110205361a1c0027042d071a060c1e2c3e0d0d2f1c0d172b150a11290b031a10343c0b150e0a00113a1a11360c0b3006053c101c161b1701713d29000502001207171a263336263b4330280c473a3e19361d0636372b22330415051145300f31290c0d1d1b1b3e051a2514070c0b3136183a171c0a2d3900012c012c0708300a05712b3d0b330f02172c371d214030070e4d2d2c1e18000502001301016f00130c171a26041c0c310e31332c30313a141d2b21092b400c31001a0a0e1e1b1f0200362638005e0c0d1d1b1b48330a1b14070c1c313e1a093c16031d4a34103e1a153a03330005022b07141b3c1f1c000d03001303131b1b041156095c776c

- Sau đó tiến hành $\oplus$ block **hiện tại** (bắt đầu từ block 2 vì block 1 đã đúng rồi) với **plaintext** trước đó và lặp lại đến hết tất cả các khối của output là ta sẽ có được **Flag** ban đầu:
- **Script:**

    from pwn import xor

    ct = bytes.fromhex("4b4353437b50726f7061676174696e6714203a3313350030120d08021f360d0f3e0a071906022d77322f2d20420b0b0d3e191c061e063849242a2c247637011537150030120d08021f360d0f3e0a071906022d3010331f0f0a360d1c04111a360d0e2f07172d5d0e0d060d1f3a1b1c3e0a07190602291f5431300e043b063716081d360a02285b51333a0930100a001400062c013a00040602093b3c1c0e310404062c0c312c190909333c0a18090b151116271d312b1b37152d0c19110f0406113a111a3b1109361e1b1b150d1e3e030d3a07310000051b1719000c021e73280916312801090f2d18032b1e06024200041d3c051c1c18360f147128210b310f262c202d141f100c42384b3e2a0600322f2d20343200023a5c3304080d1c3a1a18300a180037290d15083e1e07000d2716301d1b002c27373a142d121f1d072a113004043e1d06113a08063a140500161800110205361a1c0027042d071a060c1e2c3e0d0d2f1c0d172b150a11290b031a10343c0b150e0a00113a1a11360c0b3006053c101c161b1701713d29000502001207171a263336263b4330280c473a3e19361d0636372b22330415051145300f31290c0d1d1b1b3e051a2514070c0b3136183a171c0a2d3900012c012c0708300a05712b3d0b330f02172c371d214030070e4d2d2c1e18000502001301016f00130c171a26041c0c310e31332c30313a141d2b21092b400c31001a0a0e1e1b1f0200362638005e0c0d1d1b1b48330a1b14070c1c313e1a093c16031d4a34103e1a153a03330005022b07141b3c1f1c000d03001303131b1b041156095c776c")

    # 4b4353437b50726f7061676174696e67 là KCSC{Propagating
    flag = ct[:16]
    current_xor = ct[:16]

    # bỏ khối đầu tiên
    for i in range(16, len(ct), 16):
        current_xor = xor(current_xor, ct[i:i+16])
        flag += current_xor

    print(flag)
    # b'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.}\x03\x03\x03'

# vem (medium)
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/HJW9V0sDye.png"/>

- **Source:**

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

- Phân tích Source ta thấy rằng **key** được mã hóa bằng cách tính `pow(G, 2*MSG1 * MSG2, N)`, với giá trị **MSG1** và **MSG2** đã có, mục tiêu của ta là tìm được **G**.

- Challenge cũng cho ta nhập vào một giá trị $x$ bất kì để tính giá trị của $\text{Gift}$, trong đó:
$$\text{Gift} \equiv G^{x^2 + bx + c} \pmod N$$

- Vì thế ta sẽ lợi dụng giá trị $x$ này để tính lại giá trị $G$ ban đầu.
- Challenge chưa cho ta giá trị $b$ nên ta sẽ tìm cách để triệt tiêu nó. Đầu tiên ta gửi ba giá trị $x$ là $-1, 1$ và $0$, được ba kết quả như sau:
$$\text{Gift}_{-1} = \text{G}^{-b + c + 1}$$

$$\text{Gift}_1 =\text{G}^{b +c + 1}$$

$$\text{Gift}_0 = \text{G}^{c}$$

- Lấy $\text{Gift}_{-1}$ nhân với $\text{Gift}_1$ được:
$$\text{G}^{-b + c + 1} \times \text{G}^{b +c + 1} = \text{G}^{2c + 2} = \text{G}^{2c} \times \text{G}^{2} = \text{Gift}_0^2 \times \text{G}^{2}$$

- Vậy ta tính được giá trị của $\text{G}^{2}$ là:
$$\text{G}^{2} \equiv \text{Gift}_{-1} \times \text{Gift}_1 \times \text{Gift}_0^{-2} \pmod N$$

- Vì $\text{G}$ chỉ lớn $256$ bit nên $\text{G}^2$ sẽ bé hơn $N$ (1024 bit), ta chỉ cần tính căn bậc hai của $\text{G}^2$ trên trường số thực là sẽ có được $\text{G}$.

- **Script:**

    from Crypto.Util.number import *
    from Crypto.Cipher import AES
    from Crypto.Util.Padding import pad
    from gmpy2 import iroot

    g0 = 68709246753718708670434009468603812974169730880153372110182606027552206350317791358757202779168733600759215556114409595644777258807639505704788072606532821696532807121688324431031050041320682016561540194647870403534914783447479491524407581399830011189381812922803275186625229630192946937561415007763234855418
    g1 = 34912588211485487865266218601704066950383917642724347506083898462113941064077455705169681005963342375593688421399108198203498076409644237969447450208571854706415271918417061971940103387042750662416626209121400964110421639401854909795659178421492644182031211590672462202637945253500739318723159856916161975048
    g_1 = 11186741340123775362088539391154861118292423476007589818009758364041151686393407198862771587531612692555053653337196730852015297901445970353774615829133233790769710578342099928560157910124055319112487021351081043889989246091356061788284924405098962070739530308884383115967974725358199407010468585449409245067
    N = 106204527447305751846882251060475772730437136941185872213298995208525994414059793295374996918284654725292034949561262467748493471889227649964473617275415214227226870761256042534830419906951817128862859251725033489046287902825423970540811544802157468312878182813317947896749764084503149466587697826296781850847
    ct = bytes.fromhex("6eef3cb780a4caae1efc2ad63a78f3709f73957299908d8992cad9de3ddb081a7fab79e52816f10ce689a6c645965fba44ce2b2ddba4d0e51a222b062b4b97c9")

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

    G2 = (g1 * g_1 * pow(g0, -2, N)) % N
    G = iroot(G2, 2)[0]

    key = long_to_bytes(pow(G, 2*MSG1 * MSG2, N))[:32]

    cipher = AES.new(key, AES.MODE_ECB)
    print(cipher.decrypt(ct))

:::spoiler Flag
**KCSC{Congr4tulati0n_to_you_0n_5olving_chall_lor:)))}**
:::
# Simple lath (medium)
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/By934Cow1g.png"/>

- **Source:**

    from hashlib import sha256
    from Crypto.Util.number import bytes_to_long , getPrime
    from math import prod
    from random import choice ,randint
    from secret import  *

    array = [i for i in range(1,1000,2)]
    n = prod([i for i in array if choice([0,1])])


    def sha256_(plaintext) :
        return bytes_to_long(sha256(plaintext).digest())

    def sign(x,m,g) :

        k = randint(1,2**18)
        r = pow(g,k,n)
        s = ((m-x*r)*k)%n

        return r,s,get_chances(k,n) # from secret

    def main() :

        print("Welcom to my easy sign channel")
        print("Can you guess my  private key ???")
        private_key = randint(2**32,2**128)
        print(f'Public key : {hex(n)}')


        while True : 

            g = getPrime(128)
            plaintext =  bytes.fromhex(input("Input your plaintext :  "))
            m = sha256_(plaintext)
            while True : 

                r,s ,num_rounds = sign(private_key,m,g)
                if num_rounds > 150 and num_rounds < 999:
                    break

            print(f'g : {hex(g)}')
            print(f'r : {hex(r)}')
            print(f's : {hex(s)}')

            inp = int(input("Do you want sign more (0/1)  "))
            if inp == 0 :
                break

        print(f'You have {num_rounds} chances ~.~  ')
        for _ in range(num_rounds) :

            private_user = int(input(f'Submit you private key : '))
            if private_user == private_key : 
                print(f'Here is your flag , cheater : {flag}')
                exit()

        print(f'Did you get what you wanted? ')
        print(f'If not, here is my gift for your : {f1ag}')

    main()

- Quan sát source, ta biết rằng để có **Flag** thì phải gửi cho server giá trị đúng của khóa bí mật **d**, ta có công thức của khóa bí mật **d** như sau:
$$s \equiv ((m-d\times r)\times k) \pmod n \hspace{3mm} (1)$$

$$\Leftrightarrow d \times k \equiv (s - m \times k) \times (-r)^{-1} \pmod n \hspace{3mm} (2)$$

- Lý do mình không nhân hai vế phương trình $(1)$ cho $k^{-1}$ là vì $n$ có rất nhiều ước, nên giá trị $\text{GCD(k, n)}$ thường không phải $1$ nên không thể triệt tiêu $k$ được.

- Giờ ta có phương trình $(2)$ là phương trình **linear Congruence**, tức là phương trình dạng $A \times x \equiv B \pmod N$, nói sơ qua thì phương trình này có nghiệm khi và chỉ khi $B$ chia hết cho $\text{GCD(A, N)}$.

- Bổ sung thêm là phương trình $A \times x \equiv B \pmod N$ có $1$ nghiệm khi $\text{GCD(A, N) = 1}$, và có $\text{K}$ nghiệm khi $\text{GCD(A, N) = K}$, có thể xem cách giải ở [đây](https://youtu.be/ViqgSWoSxN8). Ở Challenge này thì $\text{GCD(A, N)}$ thường khác $1$ nên phương trình sẽ có kha khá nghiệm.

- Quay trở lại với Challenge thì phương trình $(2)$ của ta chưa có giá trị $k$ vì vậy ta sẽ tiến hành brute force $k$ để tìm lại giá trị $k$ ban đầu của server. Mình thấy rằng trong $\text{GCD(k, N)}$ nghiệm của phương trình $(2)$ thì tất cả đều cho số rất lớn (xấp xỉ giá trị bit của $n$) trừ giá trị $d$ vì nó vẫn có kích thước $128$ bit.

- Vì thế khi ta **brute force** trúng giá trị $k$ của Challenge thì ta sẽ lọc ra trong $\text{GCD(k, N)}$ nghiệm đó giá trị nào $128$ bit thì đó sẽ là giá trị $d$ của ta. Có $d$ thì gửi cho server và bài toán kết thúc.

- **Script:**

    from Crypto.Util.number import GCD
    from tqdm import trange

    # nhận các tham số của Challenge, m là hash của 01
    n = 0x255601e1de9c4aa1c5d7ed41d6ba8084c3a4f9f18169ce7dfed3833f787cbed3ec7cc2225d0f6b49f0fe28b2fd159105f513a10013696501e487ac6221b6dd8fc45b8fc313608227c381430524a27301c90751d616d52d4b720400994d8bde35703207f22cdf18f8f89e17c8421daef31e43f1ae99a77687c25dee9405a4c205dace678a9b2de1d49b818e7b78cb68bafbd48d4c781d6b98bac90e002c08f8c578aceff78c4296deb7aa6e3a03a8790813b27b67b33288a2998adc24c3b0c7f14da0c00b9ff397463c5a2f64e98688635a344ab0f3b2795e20f8ff1e53c6f82f72a14ccca3182a2146919bde3a6b169342b0fb6be1632286d4e1070dcf4e6b0f
    m = 34356466678672179216206944866734405838331831190171667647615530531663699592602
    g = 0x902bf7a457553a6244bd9389ac2b48b9
    r = 0x17bd57cb11862d85c09f1ab44734f7184ac5909ba3eeeb18c439833ebeeed43b711c75fcf302e31c18303daaa34a889c0005ad445e3822f75a151be3f9b0ee0691bad93efcd9741cb60fbea3b496cb321490fe696805abf958cb13b28429489214eeb2550b12876512dbc4fc20ee7ed72da896eca35e19fab9f6f45c8a46f8eedc50aea293ab1caac85a559804855aaa4a89a696225de33f099bdb7c67944e4ecb2e2d36427011f353acf2e21ad49f30519717fb373c819c0670e14d252570bd5e8ec454a861fe516bbcaee8664a61f0540f8068b5e9d427a7b34e191f4c3aa4d3bc05426f00a4fb4cf3d74afa8ad6f70797b9d01923b939ea1fc8d7fd8ca1f7
    s = 0xd56b8e0333b99b04cab487c1f54b1c8d4737b7ad1b1a2a19d972dc5cbca018596a6d529c5b07bf5dbd1c4eca998a26fa464c5f83eee7b50fc5bb6338633f9cca9e12fd53b6976f4394ceee049f2548f8be0679436ba2a4d845d5dbebfb0b16d2b97aad64d189dbd0a1197b6e6f0535b09641a9f1c6e950a12e0503090d170988204b806db26947fc3a652ebc45af35d4d2a8484ef90182638983cabbec2ad2eb85eefc6488630d27d3751802c7ee37bd6faa69686f85fc7a02844f421ee2bf60d5aff06c554c959d3b6eb30063ebca2edb149330fc04cfe7c7789f3a36ecc31cd985d0b7b1f78eea2f2b78c0b6ff30f68162c8073fd04ac88547fcf8610095f

    # https://www.geeksforgeeks.org/solve-linear-congruences-ax-b-mod-n-for-values-of-x-in-range-0-n-1/
    def ExtendedEuclidAlgo(a, b):

        # Base Case
        if a == 0 : 
            return b, 0, 1

        gcd, x1, y1 = ExtendedEuclidAlgo(b % a, a)

        # Update x and y using results of recursive
        # call
        x = y1 - (b // a) * x1
        y = x1

        return gcd, x, y

    def linearCongruence(A, B, N):

        A = A % N
        B = B % N
        u = 0
        v = 0

        # Function Call to find
        # the value of d and u
        d, u, v = ExtendedEuclidAlgo(A, N)

        # No solution exists
        if (B % d != 0):
            print("B mod gcd(k, n) != 0")
            exit()

        # Else, initialize the value of x0
        x0 = (u * (B // d)) % N
        if (x0 < 0):
            x0 += N

        # Pr all the answers
        for i in range(d):
            solutions.append((x0 + i * (N // d)) % N)

    # phương trình của ta là:
    # x*k = ((s - m*k) * pow(-r, -1, n)) % n

    found_d = False
    for k in trange(1, 2**20):
        if found_d: break
        solutions = []
        B = ((s - m*k) * pow(-r, -1, n)) % n

        if B % GCD(k, n) == 0:
            linearCongruence(k, B, n) # giải pt
            for i in set(solutions):
                if i.bit_length() <= 129:
                    print(f"{k = }")
                    print("d =", i)
                    found_d = True
                    break
    # k = 41600 
    # d = 299333094175056122872226309457434950402

- **Flag** của ta:

# Icecream but easier (easy/medium)
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/ryC64RsvJx.png"/>

- **Source:**

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

    # Copy from Wannagame Championship 2024
    class IceCream:
        def __init__(self, nbit: int):
            self.p = getPrime(nbit//2)
            self.q = getPrime(nbit//2)
            self.n = self.p * self.q
            self.phi = (self.p - 1) * (self.q - 1)
            # self.e = getPrime(16) # a harder version
            self.e = 10001
            self.secret1 = getPrime(384)
            self.secret2 = getPrime(384)
            self.d = inverse(self.e, self.phi)

        def wrap(self):
            c = pow(self.secret1, self.e, self.n)
            c += self.secret2
            self.secret1 = c 
            return c 


    def main() :

        cart = IceCream(512)
        for _ in range(4) :
            print(cart.wrap())

        key = sha256(str(cart.wrap()).encode()).digest()[:16]
        cipher = AES.new(key,AES.MODE_ECB)

        print(cipher.encrypt(pad(flag,16)).hex())


    main()

    """
    983988808468238406815261032742287398509539527772118186899154605157252213084385662543553125083212552614855410938487363846612472902230851873122019688775351 
    411920476721397965776323967885506259683504493586810231951685564745710311651646483406456114404428768195904417807999931167817184410508419226228074455888655
    4698285906809496129283017525468414276062165111247080417389967682278838749600348577192449627647158658589122409242574072399131912703350920146158705409829488
    2355255751438494111558900855149710130746636811000805924350928855795353027981395558758632216685403335142820213370399046347758646897427052652845539550759589
    b83519144a6ec70cf1d97e7b2bb952036e77260cac361ed742a190b3dddd1954717c41c8d8baaff729245b9a80e70e52d13150d59e12b6840f590102cb8a0891
    """

- Quan sát source thì mình thấy rằng **Flag** của ta được mã hóa bằng AES và **key** của ta được tính từ `key = sha256(str(cart.wrap()).encode()).digest()[:16]`, vậy ta sẽ tiến hành đi phân tích hàm **wrap()** của class **IceCream**.

- Gọi **secret1** là ${s_1}$, **secret2** là $s_2$, hàm `wrap()` của ta có chức năng tính toán một giá trị $\text{c}$ như sau:
$$c = (s_1^e \mod n) + s_2$$

- Và sau đó nó gán giá trị của $c$ vừa tính được cho $s_1$ và lặp lại quá trình tính toán trên. Vì Challenge lặp hàm `wrap()` $4$ lần nên ta có $4$ phương trình như sau:

$$c_1 = (s_1^e \mod n) + s_2 \hspace{5mm} (1)$$

$$c_2 = (c_1^e \mod n) + s_2 \hspace{5mm} (2)$$

$$c_3 = (c_2^e \mod n) + s_2 \hspace{5mm} (3)$$

$$c_4 = (c_3^e \mod n) + s_2 \hspace{5mm} (4)$$

- Bây giờ yêu cầu của Challenge chính là tính được chính xác giá trị tiếp theo là $c_5$, công thức như sau:
$$c_5 = (c_4^e \mod n) + s_2$$

- Ta cần tìm $s_2$, đã có giá trị của $c_4$, $c_3$ và $e$,tính giá trị của $s_2$ như sau:
$$s_2 = c_4 - (c_3^e \mod n)$$

- Có được $s_2$ thì ta thay vào phương trình $(1)$ là có $c_5$, bài toán kết thúc. Nhưng mà chúng ta chưa có modulus $n$. Vậy việc cần làm đầu tiên là tìm lại modulus $n$.

- Đầu tiên ta lấy phương trình $(3)$ trừ phương trình $(2)$ và lấy phương trình $(4)$ trừ phương trình $(3)$ được hai phương trình như sau:

$$c_3 - c_2 = c_2^e - c_1^e \mod n$$

$$c_4 - c_3 = c_3^e - c_2^e \mod n$$

- Chuyển vế phải sang và bỏ phép $\mod n$ ta được hai phương trình sau:
$$c_3 - c_2 - (c_2^e - c_1^e) = 0 + k_1 \times n \hspace{5mm} (*)$$

$$c_4 - c_3 - (c_3^e - c_2^e) = 0 + k_2 \times n \hspace{5mm} (**)$$

- Vì đã có các giá trị $c_2, c_3, c_4$ nên khi ta tính $\text{GCD}$ của biểu thức $(*)$ và $(**)$ thì ta sẽ có ước chung là giá trị $n$, bài toán kết thúc.
- **Script:**

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

    e = 10001
    c1 = 983988808468238406815261032742287398509539527772118186899154605157252213084385662543553125083212552614855410938487363846612472902230851873122019688775351 
    c2 = 411920476721397965776323967885506259683504493586810231951685564745710311651646483406456114404428768195904417807999931167817184410508419226228074455888655
    c3 = 4698285906809496129283017525468414276062165111247080417389967682278838749600348577192449627647158658589122409242574072399131912703350920146158705409829488
    c4 = 2355255751438494111558900855149710130746636811000805924350928855795353027981395558758632216685403335142820213370399046347758646897427052652845539550759589
    ct = "b83519144a6ec70cf1d97e7b2bb952036e77260cac361ed742a190b3dddd1954717c41c8d8baaff729245b9a80e70e52d13150d59e12b6840f590102cb8a0891"

    n1 = c3 - c2 - (pow(c2, e) - pow(c1, e))
    n2 = c4 - c3 - (pow(c3, e) - pow(c2, e))

    n = GCD(n1, n2)
    s2 = (c4 - pow(c3, e, n)) % n
    c5 = pow(c4, e, n) + s2
    key = sha256(str(c5).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    print(cipher.decrypt(bytes.fromhex(ct)))

:::spoiler Flag
**KCSC{1_607_570m4ch4ch3_b34c4u53_347_700_much_1c3cr34m}**
:::
# Crypto 2 (hard)
<img style="display: block; margin: auto;" width="500" src="https://hackmd.io/_uploads/Sy-1HAswkl.png"/>

- **Source:**

    from Crypto.Util.number import *
    from os import urandom

    flag = b"KCSC{fake_flag}"
    padding = urandom(1000 - len(flag))
    flag = padding[: (1000 - len(flag))//2] + flag + padding[(1000 - len(flag))//2 :]

    p = getPrime(1024)
    q = getPrime(512)
    e = 0x10001

    n = p * q
    c = pow(bytes_to_long(flag), e, n)

    key = q
    ks = []
    noises = []

    for i in range(15):
        noise = key + 3*i + 5
        noise_inv = inverse(noise, p)
        k = (noise_inv * noise - 1) // p

        ks.append(k)
        noises.append(noise_inv % 2**562)

    with open("data.txt","w") as f:
        f.write(f"{n = }\n{noises = }\n{ks = }\n")

- **data.txt**

    c = 958390793518378697087296421800510334363447372842473258361270888061359845988062617160847787493538009149015476122598987518417419094843072448103313497164473296044057151262149271633030868336861854949936583056107714557666720454320727670426024759878104055294508600827276053390768097909341499650595336630811407938767958056612000718155852086280949620705266088823405319610741770144481342370840316322962959361700770145395482234905665577476137556580613854059161166908076563
    noises = [7855711876569802238862413165275600906813725762035718788939102158061380227877261762058163252276012974919613869744386471326379360599551714048814350682844653203632596811700, 11016762668854429203921748552171961540330601718050664348323205797201647566906360457303813510699134610808048666995818660000595371281648507789977635794049527374670915074820, 11546537801915447264802137334545592446958309083548637512152243512181257950929398818955898367116157381845553377528332628838810077828034595899755565832327915425781910578439, 14830729778111523754153466930320460677549254575098428551135275406990012856666239121852688775241624133868906117915735977555517436901488865149110824895148729747382400302735, 12907187256704172729107731584833713827465378465099977282577640066526827100848547817920519272964340115432388355503430889687196818282392932653498115462633041044503277974348, 12138846625255592521563612083084082981604248578123108209967521720915214134631110004822440010797002143437417645081236617079726153719130327393125423457708193164785079343086, 739523797727999924234547033495024454536077879042322224023692246011372669433295815544499023380041352962654821966906221244535621757121658976493022103991684410944260441162, 10912720975459354397739596143674407139194119895970368719866752943212477569655440757739848406867091021804581233694510089684679552007293849432444225461324183971137511847850, 5808807130421099726863129210954911380673640771955929374201995801529194903892832719794393448564558695251305267337407921976623897457446026039650140168312597722101737867377, 6870714010059053187003558056421661621211755459105144640275368103761664542845966933600910306834129475974876509027992589543452526949905158943937805162971925181177623545706, 14001977026303213753344771778959822998356523953467938417570588825474587458038917314981845799115762940916991783878210493664223158815126302912780685563402149348230275770190, 2703973027755031256526864275850359824471693408893668839490715558453757417896110268005975650433171168484478679910175856477619764900062649145928051355223654355802268429828, 2197799411096076134244174423868396977861502716614420367844698041028287534815946837970931537722713608970852047499736568341768228551190841854816687141278293724986033804833, 6075559627298470723737160139773692997034806166978942024860600924417526676075369730013184451780131430065519578644230326849609926904745308079312413920535221565905507405787, 6192265537641579777321105222372552667784798470028740666393274098101434097162631461434169230747053524655097972801202035288143826479354640729278654236265719132207498664412]
    ks = [188342419899480149536884744017610449040092383019272248788959474691994413969719059118388685743603155504636227720165256840721069157015807449049211460253193, 2524032492075863404568209983324668522574966560976022920474303041695931745292134024805133065252540879869398798070277250051370058237130781549140268588979741, 3668089499830133831067934187396832654741712179290611321105361394043708714207354289456329073317267896181461996357656482682562832756019136386463281668147597, 787787910858589886444577841106414412143077182871445558404189242413347285556605603096222171073736492222727597718358413446678740896394491930381038665121984, 5969746486150167662037133056426653272095571564362080467447908647771862414810883039477641097271866604770772719228490891456621179456874478543312762101011945, 3953217233915265744392631383349005252504986319285163722465977735607534480220118278786439611479721354895554188803942058684275260525947213712273507161369083, 4703008646650559151263915675980342869678582333983285387772678033375440253018051362888097872035173512023181428217784439917007569473323902339013784947548817, 4501690793684706714453057890878006909948693156550389759496860753395691942571265613093123643690372231103171045523407714153581252263042363624513611315744787, 2874911234935885776724870513977581714604232366383062929938550655871436461399856184577119939177694657465354516516047758735724966092696982807333754161121763, 6807368946443140675648934273041372592283914654163350087761898286033102359032462642892185826153908771772176615450328348070881136865613927396914213307028823, 278211494072033197885754804219785966600017003124368934336640552995267695544391267083052940908660042483493904705872074416528235534610757303534430447847433, 1558365191956305255182334966416705368442755011866281958336373678292946152152443736046507333024441976071233683858273758166768326012234742351338218885065893, 3485367897376122736793872341240247397026215356530797459918379349421401150937114097374676678036857389576159611944092267415794839255765051218093322919755447, 2515456897351178494301823923332414671089420746643455306358829413922283380911750878593348268259769997426299206977825772717836168569349433038297458642933154, 4092447245860483948794687799772397211468262697039308695517969469204107269630882626451514975266106190665554492836842864230426192321181584429136242874419201]

- Một Challenge khó về Lattice, mình cũng chưa thể hiểu tường tận Lattice nên nếu bên dưới mình có nhầm lần hay ghi gì chưa đúng thì các bạn nhắc mình nha.

- Trong khi giải diễn ra thì mình không làm được bài này nên sau khi giải kết thúc mình có thao khảo [**Wu**](@nomorecaffeine) của anh **@nomorecaffeine** để làm theo, anh giải thích rất chi tiết nên mình thấy bài này rất hay và dễ hiểu, sau đây là wu của mình về những gì mình hiểu.

- Đọc sơ qua **source** thì mình thấy rằng **Flag** được mã hóa bằng **RSA** với mũ $\text{e = 65537}$ nên ta phải tìm được hai số nguyên tố $\text{p,q}$ thì mới giải mã $\text{c}$ được.

:::info
:pencil: Note
$\text{noise}_{\mathbf{i}} = \text{q} + 3 \times \mathbf{i} + 5 \hspace{5mm} \forall \mathbf{i} \in \left\{ 0,1,2,\cdots 14\right\}$
$\text{noise}_{\text{inv_i}} \equiv \text{noise}_{\mathbf{i}}^{-1} \pmod {\text{p}}$
$\text{noise}_{\text{inv256_i}} \equiv \text{noise}_{\text{inv_i}} \pmod {2^{562}}$
:::

- Source cho ta các dữ kiện sau:
$$
\begin{split}
\text{noises} &= [\text{noise}_{\text{inv256_0}}, \text{noise}_{\text{inv256_1}},\text{noise}_{\text{inv256_2}}, \dots, \text{noise}_{\text{inv256_14}}]\\
\text{ks} &= [\text{k}_0,\text{k}_1, \text{k}_2, \dots, \text{k}_{14}]
\end{split}
$$
- Phân tích đoạn sau:

    key = q
    ks = []
    noises = []

    for i in range(15):
        noise = key + 3*i + 5
        noise_inv = inverse(noise, p)
        k = (noise_inv * noise - 1) // p

        ks.append(k)
        noises.append(noise_inv % 2**562)

- Biết được công thức của $\text{noise}_{\text{inv256_i}}$ là:
$$\text{noise}_{\text{inv256_i}} \equiv \text{noise}_{\text{inv_i}} \pmod {2^{562}} \hspace{5mm} (*)$$

- Giá trị $\text{k}_{\mathbf{i}}$ là:

$$\text{noise}_{\text{inv_i}} \times \text{noise}_{\mathbf{i}}= 1 + \text{k}_{{\mathbf{i}}} \times \text{p} \hspace{5mm} \forall \mathbf{i} \in \left\{ 0,1,2,\cdots 14\right\} \hspace{5mm} (**)$$

- Ý tưởng của tác giả là phải tìm được $\text{p}$ và $\text{q}$ thông qua các phương trình $(**)$
- Có hai mục tiêu ta cần phải làm đó là tìm **p** và tìm **q**, phải tìm cả hai vì Challenge chưa cho **n**. Ta sẽ dựa vào phương trình $(**)$ để đi tìm **q** trước.

- Đầu tiên, từ $(*)$ Ta biến đổi giá trị của $\text{noise}_{\text{inv}}$ thành:
$$\text{noise}_{\text{inv_i}} = \text{noise}_{\text{inv256_i}} + \text{a}_{\mathbf{i}} \times 2^{562} \hspace{5mm} \forall \mathbf{i} \in \left\{ 0,1,2,\cdots 14\right\} \hspace{5mm} (1)$$

- Tiếp theo **mod** giá trị của $\text{p}$ với $2^{562}$ và bỏ phép mod, ta được:
$$\text{p} = \text{p'} + \text{b} \times 2^{562} \hspace{5mm} (2)$$

- Thể cả $(1)$ và $(2)$ vào phương trình $(**)$ được:
$$(\text{noise}_{\text{inv256_i}} + \text{a}_{\mathbf{i}} \times 2^{562}) \times \text{noise}_{\mathbf{i}} = 1 + \text{k}_{{\mathbf{i}}} \times (\text{p'} + \text{b} \times 2^{562})$$

- Phân phối, chuyển vế các giá trị chứa $2^{562}$ sang bên trái, ta được:
$$\text{a}_{\mathbf{i}} \times \text{noise}_{\mathbf{i}} \times 2^{562} - \text{k}_{{\mathbf{i}}} \times \text{b} \times 2^{562} = 1 - \text{noise}_{\text{inv256_i}} \times \text{noise}_{\mathbf{i}} + \text{k}_{{\mathbf{i}}} \times\text{p'} \hspace{5mm} (***)$$

- Sau đó ta **mod** hai vế cho $2^{562}$ và được phương trình mới:
$$1 - \text{noise}_{\text{inv256_i}} \times \text{noise}_{\mathbf{i}} + \text{k}_{{\mathbf{i}}} \times\text{p'} \equiv 0 \pmod {2^{562}}$$

$$\Leftrightarrow 1 - \text{noise}_{\text{inv256_i}} \times (\text{q} + 3 \times \mathbf{i} + 5) + \text{k}_{{\mathbf{i}}} \times\text{p'} \equiv 0 \pmod {2^{562}} \hspace{5mm} \forall \mathbf{i} \in \left\{ 0,1,2,\cdots 14\right\}$$

- Đây là một phương trình modulo có **hai** ẩn là $\text{q}$ và $\text{p'}$, và có đến $15$ phương trình nên việc giải hệ này là khả thi.

- Có nhiều cách giải hệ nhưng mình sẽ thử cách mới mà hồi giờ chưa dùng đó là sử dụng phương thức **groebner_basis()** của thư viện `sagemath`, dùng để đơn giản tập sinh của một **Ideal** trong vành đa thức. Hay có thể hiểu là nó giúp đơn giản hóa phương trình ban đầu và biến nó thành một phương trình đơn giản, dễ giải hơn.

- **Code**:

    from sage.all import *
    x, y = PolynomialRing(Zmod(2**562), ["x", "y"]).gens()

    I = Ideal([
        1 - noises[0] * (x + 5) + ks[0] * y,
        1 - noises[1] * (x + 8) + ks[1] * y,
        1 - noises[2] * (x + 11) + ks[2] * y
    ])
    print(I.groebner_basis())
    #[x + 15095849699286157176165192141574519938693899918427427740708979667686108913040888895928594081761428218515984585906870777122468994835321959450919640276403457857023062016735, y + 8046359343118037782228277823598020857453001371030183803247456593467443731321455063833959619491793509652535546439016536857407146846080157709770883346704338364262578059073]

- Có thể thấy là hệ phương trình của ta đã được đơn giản hóa thành dạng $x + a \equiv 0 \pmod {2^{562}}$ và $y + b \equiv 0 \pmod {2^{562}}$ để có $\text{q}$ và $\text{p'}$ ta chỉ cần tính:

$$
\left\{\begin{matrix}
\text{q} = 2^{562} - a \\
\text{p'} = 2^{562} - b
\end{matrix}\right.
$$
> Vậy là tính được $q$ rồi, mục tiêu tiếp theo là tìm $p$
- Có $\text{q}$ và $\text{p'}$ thì ta sẽ đi tìm $\text{b}$, vì $\text{p} = \text{p'} + \text{b} \times 2^{562}$ nên ta chỉ cần đi tìm $\text{b}$ là có $\text{p}$.

- Đặt $\text{noise}_{\mathbf{i}} = n_{\mathbf{i}}$. Dựa vào phương trình $(***)$ ta lập được một cơ sở **Lattice** như sau:
$$
M = \begin{pmatrix}
-k_0 \cdot 2^{562} &-k_1 \cdot 2^{562} &\cdots &-k_{14} \cdot 2^{562} &1 & & & & &\\
n_0 \cdot 2^{562} &0 &\cdots &0 & &1 & & & &\\
& n_1 \cdot 2^{562} &\cdots &0 & & &1 & & &\\
\vdots &\vdots &\ddots &\vdots & & & & \ddots & &\\
& &\cdots &n_{14} \cdot 2^{562} & & & & &1 & \\
-v_0 &-v_1 &\cdots &-v_{14} & & & & & &1 \end{pmatrix}
$$
> Với $v_i$ là vế phải của phương trình $(***)$.

- Sau khi áp dụng **LLL** với ma trận **M**, ta sẽ được một vector chứa $32$ phần tử như sau:
$$[0, 0, \dots, 0, \text{b}, a_0, a_1, \dots, a_{14}, 1]$$

> Giá trị $\text{b}$ sẽ nằm ở **index** thứ 15.
- **Code:**

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

    M = []
    vs = []

    q = 8232801026182378555624973784963238333972795845533296387736527706512415912818949206851649888914216184602476613343684377211079326096729327326317574519291169
    p_ = 7049490356168127626737940500355054706214683510635577910257368607515052918247140344510547281218841560513337953684038842741675191673619012820474853659026445810335003248831

    assert is_prime(q)

    M.append([-ks[i] * 2**562 for i in range(15)])

    for i in range(15):
        d = q + 3 * i + 5
        v = -(1 - d * noises[i] + ks[i] * p_)
        vs.append(v)

        row = [0]*(15)
        row[i] = d * 2**562
        M.append(row)

    M.append(vs)

    M = matrix(M)
    M = M.augment(identity_matrix(17))
    L = M.LLL()

    print(L[0][15])

- Giá trị $\text{b}$:
- Có $\text{b}$ là có được $\text{p}$ rồi, ta sẽ tính được khóa bí mật $\text{d}$ và bài toán kết thúc:

    from Crypto.Util.number import *
    b = 9973918226342931101713742759510102202832949751016016433335951379486864420606419272916855340660179601297616652770791167118160222182913331004
    p_ = 7049490356168127626737940500355054706214683510635577910257368607515052918247140344510547281218841560513337953684038842741675191673619012820474853659026445810335003248831
    q = 8232801026182378555624973784963238333972795845533296387736527706512415912818949206851649888914216184602476613343684377211079326096729327326317574519291169
    c = 958390793518378697087296421800510334363447372842473258361270888061359845988062617160847787493538009149015476122598987518417419094843072448103313497164473296044057151262149271633030868336861854949936583056107714557666720454320727670426024759878104055294508600827276053390768097909341499650595336630811407938767958056612000718155852086280949620705266088823405319610741770144481342370840316322962959361700770145395482234905665577476137556580613854059161166908076563
    e = 65537

    p = p_ + 2**562 * b
    assert isPrime(p) and isPrime(q)

    n = p*q
    d = pow(e, -1, n-p-q+1)

    print(long_to_bytes(pow(c, d, n)))

- **Flag:**

<h1 style="text-align:center;">END</h1>