---
# System prepended metadata

title: '[Crypto] KMACTF 2025 đợt 2'

---

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

![image](https://hackmd.io/_uploads/B1zOOzt2ee.png)

## Chatgpt (500pts)
![image](https://hackmd.io/_uploads/rJwJJ0Lnlg.png)
:::spoiler **chall․py**
```python=
from Crypto.Cipher import AES
from Crypto.Util import Counter
import secrets, sys
import random
from hashlib import sha256 


BLOCK = 16  
R_POLY = 0xE1000000000000000000000000000000 
KEY_SIZE_BITS = 256
MAX_INT = 1 << KEY_SIZE_BITS
MOD = MAX_INT - 189  
SEED = MAX_INT // 6

def xor_bytes(a: bytes, b: bytes) -> bytes:
    assert len(a) == len(b)
    return bytes(x ^ y for x, y in zip(a, b))

def pad16(b: bytes) -> bytes:
    if len(b) % BLOCK == 0:
        return b
    return b + b"\x00" * (BLOCK - (len(b) % BLOCK))

def int_from_bytes(b: bytes) -> int:
    return int.from_bytes(b, "big")

def int_to_bytes(x: int) -> bytes:
    return x.to_bytes(16, "big")

def gf_mul(X: int, Y: int) -> int:
    Z = 0
    V = X
    for i in range(128):
        if (Y >> (127 - i)) & 1:
            Z ^= V
        lsb = V & 1
        V >>= 1
        if lsb:
            V ^= R_POLY
    return Z & ((1 << 128) - 1)

def ghash(H: bytes, data: bytes) -> bytes:
    assert len(H) == 16
    H_int = int_from_bytes(H)
    data = pad16(data)
    y = 0
    for i in range(0, len(data), BLOCK):
        Xi = int_from_bytes(data[i:i+BLOCK])
        y = gf_mul(y ^ Xi, H_int)
    return int_to_bytes(y)

class GHASH:
    def __init__(self, aes_key_for_H: bytes):
        cipher = AES.new(aes_key_for_H, AES.MODE_ECB)
        self.H = cipher.encrypt(b"\x00"*16) 
    def h(self, X: bytes, T: bytes) -> bytes:
        return ghash(self.H, pad16(X) + pad16(T))

class AESBlock:
    def __init__(self, key: bytes):
        self.key = key
    def enc(self, block: bytes) -> bytes:
        cipher = AES.new(self.key, AES.MODE_ECB)
        return cipher.encrypt(block)
    def dec(self, block: bytes) -> bytes:
        cipher = AES.new(self.key, AES.MODE_ECB)
        return cipher.decrypt(block)

class StreamAESCTR:
    def __init__(self, key: bytes):
        self.key = key
    def keystream(self, S: bytes, length: int) -> bytes:
        init_val = int.from_bytes(S, "big")
        ctr = Counter.new(128, initial_value=init_val)
        cipher = AES.new(self.key, AES.MODE_CTR, counter=ctr)
        return cipher.encrypt(b"\x00" * length)

class Encryptor:
    def __init__(self, key_e: bytes, key_d: bytes, key_c: bytes, key_for_H: bytes):
        self.e = AESBlock(key_e)
        self.d = AESBlock(key_d)
        self.h1 = GHASH(key_for_H)
        self.h2 = GHASH(key_for_H)
        self.c = StreamAESCTR(key_c)
        
    def encrypt(self, T: bytes, plaintext: bytes) -> bytes:
        assert len(T) == BLOCK and len(plaintext) >= BLOCK
        A = plaintext[:BLOCK]; B = plaintext[BLOCK:]
        U = self.e.enc(A)
        S = xor_bytes(U, self.h1.h(B, T))
        keystream = self.c.keystream(S, len(B))
        E = xor_bytes(B, keystream) if len(B) > 0 else b""
        V = xor_bytes(S, self.h2.h(E, T))
        G = self.d.enc(V)
        return G + E
    
    def decrypt(self, T: bytes, ciphertext: bytes) -> bytes:
        assert len(T) == BLOCK and len(ciphertext) >= BLOCK
        G = ciphertext[:BLOCK]; E = ciphertext[BLOCK:]
        V = self.d.dec(G)
        S = xor_bytes(V, self.h2.h(E, T))
        keystream = self.c.keystream(S, len(E))
        B = xor_bytes(E, keystream) if len(E) > 0 else b""
        U = xor_bytes(S, self.h1.h(B, T))
        A = self.e.dec(U)
        return A + B
    
class Newbie_Stager:
    def __init__(self, alice_private_key: int, bob_key_private: int):
        self.alice_private_key = alice_private_key
        self.bob_key_private = bob_key_private
        
    def key_exchange(self, seed, exponents):
        result = seed
        exp = 1
        while exponents > 0:
            if exponents % 2 == 1:
                mult = 1
                for i in range(exp):
                    result = (3 * result * mult) % MOD
                    mult <<= 1
            exponents >>= 1
            exp += 1
        return result
    
    def get_shared_key(self): 
        A = self.key_exchange(SEED, self.alice_private_key)
        B = self.key_exchange(SEED, self.bob_key_private)
        shared_key_A = self.key_exchange(B, self.alice_private_key)
        share_key_B = self.key_exchange(A, self.bob_key_private)
        assert shared_key_A == share_key_B
        return shared_key_A , A, B


# Setup
m_blocks = 12
key_e = secrets.token_bytes(16)
key_d = secrets.token_bytes(16)
key_c = secrets.token_bytes(16)
key_for_H = secrets.token_bytes(16)
encryptor = Encryptor(key_e, key_d, key_c, key_for_H)

# Encrypt 
total_len = m_blocks * BLOCK
plaintext = secrets.token_bytes(total_len)
T = secrets.token_bytes(BLOCK)
ciphertext = encryptor.encrypt(T, plaintext)

# Encrypt but for newbie
alice_private = random.getrandbits(256)
bob_private = random.getrandbits(256)
shared_key, A, B = Newbie_Stager(alice_private, bob_private).get_shared_key()
shared_key = sha256(str(shared_key).encode()).digest()[:16]
newbie_aes = AESBlock(shared_key) 
cipher_enc = newbie_aes.enc(ciphertext)

print("Newbie cant see my ciphertext !!!")
print("Here is your ciphertext:", cipher_enc.hex())
print("Here is your T (hex):", newbie_aes.enc(T).hex())
print("Here is your A:", A) 
print("Here is your B:", B)

coint = 10
menu = """
1) Decrypt
2) Encrypt
3) Get Flag
"""
while coint > 0: 
    
    print(menu)
    print(f"You have {coint} coins left")
    choice = input("Your choice: ").strip()
    
    if choice == "1": 
        try:
            hex_ct = input("Ciphertext (hex): ").strip()
            T = bytes.fromhex(input("T (hex): ").strip())
            
            if len(T) != BLOCK:
                print("Invalid T length")
                continue
            
            ciphertext_ = bytes.fromhex(hex_ct)
            if len(ciphertext_) < BLOCK:
                print("Ciphertext too short")
                continue
            
            control = 0
            for i in range(0, len(ciphertext_), BLOCK):
                block = ciphertext_[i:i+BLOCK]
                if block in ciphertext :
                    control +=1 
            
            if control > 2 :
                print("You are not allowed to repeat blocks more than 2 times")
                exit()
            
            pt = encryptor.decrypt(T, ciphertext_)
            print("Plaintext (hex):", pt.hex())
            coint -= 3
        except Exception as e:
            print("Error:", e)
            continue
                
    if choice == "2":
        try:
            hex_pt = input("Plaintext (hex): ").strip()
            T = bytes.fromhex(input("T (hex): ").strip())
            if len(T) != BLOCK:
                print("Invalid T length")
                continue
            plaintext_ = bytes.fromhex(hex_pt)
            
            if len(plaintext_) < BLOCK:
                print("Plaintext too short")
                continue
            
            control = 0
            for i in range(0, len(plaintext_), BLOCK):
                block = plaintext_[i:i+BLOCK]
                if block in ciphertext :
                    control +=1 
            
            if control > 2 :
                print("You are not allowed to repeat blocks more than 2 times")
                exit()
                
            ct = encryptor.encrypt(T, plaintext_)
            print("Ciphertext (hex):", ct.hex())
            coint -= 4
        except Exception as e:
            print("Error:", e)
            continue
        
    if choice == "3":
        
        plaintext_ = bytes.fromhex(input("Plaintext (hex): ").strip())
        if plaintext_ == plaintext[BLOCK:]:
            print("Here is your flag: KMACTF{????????????????????????????????}")
            exit()
        else:
            print("Nope")
           
            coint -= 5
```
:::

++**Mô tả:**++ Challenge này sử dụng hai lớp mã hóa là `Encryptor` và `Newbie_Stager` để mã hóa `Plaintext`, và nó yêu cầu ta phải giải mã được `Plaintext[16:]` (bỏ đi block đầu) để nhận `Flag`.

Bên cạnh đó Challenge còn cung cấp cho ta `10 coin` và cho phép dùng `3` option là `Decrypt` (3 coin), `Encrypt` (4 coin), `Get Flag` (5 coin) để tương tác với server. 

>Theo code thì ta có thể dùng được tối đa: 3 lần `Decrypt` 1 lần `Get Flag`, hoặc 1 lần `Decrypt` 1 lần `Encrypt` 1 lần `Get Flag`, hoặc 2 lần `Encrypt` 1 lần `Get Flag`.


---


Tiến hành phân tích class `Encryptor` và class `Newbie_Stager`.

1️⃣ Class `Encryptor` :
```python=
class Encryptor:
    def __init__(self, key_e: bytes, key_d: bytes, key_c: bytes, key_for_H: bytes):
        self.e = AESBlock(key_e)
        self.d = AESBlock(key_d)
        self.h1 = GHASH(key_for_H)
        self.h2 = GHASH(key_for_H)
        self.c = StreamAESCTR(key_c)
        
    def encrypt(self, T: bytes, plaintext: bytes) -> bytes:
        assert len(T) == BLOCK and len(plaintext) >= BLOCK
        A = plaintext[:BLOCK]; B = plaintext[BLOCK:]
        U = self.e.enc(A)
        S = xor_bytes(U, self.h1.h(B, T))
        keystream = self.c.keystream(S, len(B))
        E = xor_bytes(B, keystream) if len(B) > 0 else b""
        V = xor_bytes(S, self.h2.h(E, T))
        G = self.d.enc(V)
        return G + E
    
    def decrypt(self, T: bytes, ciphertext: bytes) -> bytes:
        assert len(T) == BLOCK and len(ciphertext) >= BLOCK
        G = ciphertext[:BLOCK]; E = ciphertext[BLOCK:]
        V = self.d.dec(G)
        S = xor_bytes(V, self.h2.h(E, T))
        keystream = self.c.keystream(S, len(E))
        B = xor_bytes(E, keystream) if len(E) > 0 else b""
        U = xor_bytes(S, self.h1.h(B, T))
        A = self.e.dec(U)
        return A + B
```

🔎 Class này kết hợp `3` cơ chế bảo mật là:
1. `AES ECB` (trong class `AESBlock`) để mã hóa và giải mã block đầu của `Plaintext`.
1. `GHASH` (trong class `GHASH`) để tạo hai đối tượng `h1, h2` sử dụng trong quá trình mã hóa và tạo `Keystream`. Nó sử dụng phép nhân trong trường `GF(2^128)` với đa thức bất khả quy là `x^128 + x^7 + x^2 + x + 1`.
1. `AES CTR` (trong class `StreamAESCTR`) để tạo Keystream cho phần đuôi của `Plaintext`.

🔎 Quy trình `encrypt` hoạt động như sau:
1. Chia `Plaintext` thành `A` (block đầu) dài `16 bytes` và `B` (phần còn lại).
2. Tính `U = ECB_e(A)`, sau đó tính `S = U ⊕ h1(B, T)`.
3. Dùng `S` làm `nonce` cho `CTR` để tạo keystream, sau đó xor với `B` → ta được phần  `E` của Ciphertext.
4.  Tiếp tục tính `V = S ⊕ h2(E, T)` rồi mã hóa bằng `ECB_d` để tạo block đầu `G`.
5. Kết quả `ciphertext = G || E`.

🔎 Khi giải mã (`decrypt`), ta đảo ngược quá trên trên.

>[!Important] Hint
Được hint rằng cơ chế mã hóa trên là một trong các [**Mode of operation**](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation) thì sau một hồi tìm kiếm và được hint thêm thì mình tìm được nó là mode `XCBv2fb` (một mode bị chứng minh là không an toàn và có thể bị bẻ gãy chỉ trong vài tương tác).
![image](https://hackmd.io/_uploads/Hy3rN3j2ll.png)


---

2️⃣ Class `Newbie_Stager` :
```python=
class Newbie_Stager:
    def __init__(self, alice_private_key: int, bob_key_private: int):
        self.alice_private_key = alice_private_key
        self.bob_key_private = bob_key_private
        
    def key_exchange(self, seed, exponents):
        result = seed
        exp = 1
        while exponents > 0:
            if exponents % 2 == 1:
                mult = 1
                for i in range(exp):
                    result = (3 * result * mult) % MOD
                    mult <<= 1
            exponents >>= 1
            exp += 1
        return result
    
    def get_shared_key(self): 
        A = self.key_exchange(SEED, self.alice_private_key)
        B = self.key_exchange(SEED, self.bob_key_private)
        shared_key_A = self.key_exchange(B, self.alice_private_key)
        share_key_B = self.key_exchange(A, self.bob_key_private)
        assert shared_key_A == share_key_B
        return shared_key_A , A, B
```

Mục đích của Class này là để tạo `shared_key` cho `newbie_aes` mã hóa `Token` và `Ciphertext`, vì vậy ta cần tìm lại `shared_key` thì mới giải mã cái `newbie_aes` được.

🔎 Ta có công thức của hàm `key_exchange` là:
$$\text{result} \equiv \text{SEED} \cdot \prod(3.2^k) \pmod {MOD}$$

> với `k` phụ thuộc vào giá trị của `exponents`.

🔎 Ta có thể viết lại công thức của `A,B` như sau:
$$A \equiv \text{SEED} \cdot a \pmod {MOD}$$


$$B \equiv \text{SEED} \cdot b \pmod {MOD}$$

>Trong đó `a, b` là giá trị của `∏(3.2^k)`.

🔎 Vì đã có `A,B` nên ta tính được `a,b`:

$$a \equiv \frac{A}{\text{SEED}} \pmod {MOD}$$

$$b \equiv \frac{B}{\text{SEED}} \pmod {MOD}$$

🔎 Có `a,b` ta thay vào công thức của `shared_key` là tính được `shared_key`:
$$\text{shared key} \equiv A.b \equiv \text{SEED}.a.b \pmod {MOD}$$

> Có `shared_key` thì có được `Token` và `Ciphertext` gốc.


---

❔Có `Ciphertext` và `Token`, giờ ta sử dụng `10 coin` và hai option `Decrypt` và `Encrypt` như thế nào để khôi phục `Plaintext[16:]`?

Ta không được phép gửi toàn bộ `Ciphertext` vào option `Decrypt` vì server có check như sau:
```python=
control = 0
for i in range(0, len(ciphertext_), BLOCK):
    block = ciphertext_[i:i+BLOCK]
    if block in ciphertext :
        control +=1 

if control > 2 :
    print("You are not allowed to repeat blocks more than 2 times")
    exit()
```

Biết rằng mode `XCBv2fb` là không an toàn, ta có thể dễ dàng tìm được các bài báo cáo nói về tính bảo mật của nó và mình tìm được bài báo cáo [**này**](https://eprint.iacr.org/2024/1527.pdf) hướng dẫn cách khôi phục `Plaintext[16:]` chỉ với 1 lần `Decrypt` và 1 lần `Encrypt` mà thôi.

>[!Important] 
Ở `trang 7`, tác giả có hướng dẫn như sau:
![image](https://hackmd.io/_uploads/rJx01Tohlg.png)

✅ Vậy ta thực hiện như sau:
1. Đặt `plaintext` cần tìm là `A||B`, `ciphertext` là `G||A` và Token là `T`. Khởi tạo một chuỗi bytes `△` ngẫu nhiên dài bằng `len(B)`.
2. Ta sử dụng option 1 `Decrypt` với `ciphertext = G||(E ⊕ △)` và nhận được `A1||B1`.
3. Còn `7 coin`, ta sử dụng option 2 `Encrypt` với `plaintext = A1||(B1 ⊕ △)` và được `G2||E2`.
4. Cuối cùng tính lại `B` bằng công thức `B = E ⊕ B1 ⊕ E2 ⊕ △`.
5. Gửi `B` đến server bằng option 3 và nhận `Flag.`

:::spoiler **Full Script**
```python=
from pwn import *
from Crypto.Cipher import AES
import secrets, sys
from hashlib import sha256 

BLOCK = 16  
R_POLY = 0xE1000000000000000000000000000000 
KEY_SIZE_BITS = 256
MAX_INT = 1 << KEY_SIZE_BITS
MOD = MAX_INT - 189  
SEED = MAX_INT // 6

class AESBlock:
    def __init__(self, key: bytes):
        self.key = key
    def enc(self, block: bytes) -> bytes:
        cipher = AES.new(self.key, AES.MODE_ECB)
        return cipher.encrypt(block)
    def dec(self, block: bytes) -> bytes:
        cipher = AES.new(self.key, AES.MODE_ECB)
        return cipher.decrypt(block)

io = remote("165.22.55.200", 30002)

def find_newbie_key(A, B):
    shared = (A * B) * pow(SEED, -1, MOD) % MOD
    key16 = sha256(str(shared).encode()).digest()[:16]
    return key16

# ciphertext và T bị mã hóa bằng newbie_aes
io.recvuntil(b"ciphertext:"); ct = bytes.fromhex(io.recvlineS())
io.recvuntil(b"T (hex): "); T = bytes.fromhex(io.recvlineS())
io.recvuntil(b"A: "); A = int(io.recvlineS())
io.recvuntil(b"B: "); B = int(io.recvlineS())

shared_key = find_newbie_key(A, B)
newbie_aes = AESBlock(shared_key) 

# Có T và ciphertext gốc, tiến hành khôi phục plaintext
T = newbie_aes.dec(T)
C = newbie_aes.dec(ct)
delta = secrets.token_bytes(16*11)

G = C[:16]
E = C[16:]

# round 1
C = G + xor(E, delta)
io.sendlineafter(b"Your choice: ", b"1")
io.sendlineafter(b"Ciphertext (hex): ", C.hex().encode())
io.sendlineafter(b"T (hex): ", T.hex().encode())
io.recvuntil(b"Plaintext (hex): "); P1 = bytes.fromhex(io.recvlineS())

A1 = P1[:16]
B1 = P1[16:]

# round 2
P1 = A1 + xor(B1, delta)
io.sendlineafter(b"Your choice: ", b"2")
io.sendlineafter(b"Plaintext (hex): ", P1.hex().encode())
io.sendlineafter(b"T (hex): ", T.hex().encode())
io.recvuntil(b"Ciphertext (hex): "); C2 = bytes.fromhex(io.recvlineS())

G2 = C2[:16]
E2 = C2[16:]

B = (xor(E, B1, E2, delta)).hex()
io.sendlineafter(b"Your choice: ", b"3")
io.sendlineafter(b"Plaintext (hex): ", B.encode())

io.interactive()
"""
[+] Opening connection to 165.22.55.200 on port 30002: Done
[*] Switching to interactive mode
Here is your flag: KMACTF{h0w_m4ny_qu3ri3s_d0_y0u_n33d_2_bre4k_m3?_i_know_2_4r3_3n0ugh}
[*] Got EOF while reading in interactive
"""
```
:::spoiler **Flag**
**KMACTF{h0w_m4ny_qu3ri3s_d0_y0u_n33d_2_bre4k_m3?_i_know_2_4r3_3n0ugh}**
:::

## RAS (500pts)
![image](https://hackmd.io/_uploads/BkcM1CI3gx.png)

:::spoiler **chall․py**
```python=
from Crypto.Util.number import *
from math import prod
import random

class RAS(object):
    def __init__(self, arr):
        self.n = prod(arr)*prod(arr)
        
    def generate_e(self):
        e = random.getrandbits(4048)
        return e
    
    def encrypt(self, pt):
        e = self.generate_e()
        assert self.n.bit_length() == 4048
        c = [pow(m, e, self.n) for m in pt]
        return  c
        
flag = b'KMACTF{???????????????????????????????}'
flag1, flag2, flag3 = bytes_to_long(flag[:len(flag)//3]), bytes_to_long(flag[len(flag)//3:2*len(flag)//3]), bytes_to_long(flag[2*len(flag)//3:])

# shuffle it
m1 = flag3
m2 = 65537*flag1**2 + flag3*flag2**2 

menu = '''
Welcome to my RAS stolen from tvd2004
1. Send primes
2. Get encrypted flag
'''

while True : 
    print(menu)
    choose = input('> ')
    if choose == '1':
        
        try:
            count = int(input(f"Not 1, not 2, you can choose number prime in RSA system : "))
        except :
            exit()
            
        arr = []
        for i in range(count) :
            p = int(input(f"Prime {i} : "))
            arr.append(p)
        
        ras =  RAS(arr)
        
    elif choose == '2':
        
        print("Here is ciphertext :")
        print(ras.encrypt([m1,m2]))
        
    else:
        raise Exception("Invalid choice!!!")
```
:::

++**Mô tả:**++ Một Challenge lấy ý tưởng từ Challenge `RAS` của giải `WannaGame Championship 2024` khi nó cho phép ta chọn modulus `n` để mã hóa `RSA`, sau đó nó trả về kết quả của:

$$
 \left\{\begin{matrix}
c_1 = m_1^e \pmod {n^2} \\
c_2 = m_2^e \pmod {n^2}
\end{matrix}\right.
$$

Trong đó:
$$
 \left\{\begin{align}
m_1 &= \text{Flag}_3 \\
m_2 &= 65537 \times \text{Flag}_1^2 + \text{Flag}_3\times \text{Flag}_2^2 
\end{align}\right.
$$

> Với `Flag1 Flag2 Flag3` là ba phần của `Flag` và `e` là một số ngẫu nhiên `4048` bit.

Nhưng Challenge này khó hơn hơn Challenge gốc của anh `tvdat` nhiều vì nó chỉ trả về giá trị của `(c1, c2)` chứ không trả về mũ `e`. Liệu ta có thể gửi vào một giá trị `n` mà khi không biết `e` nhưng vẫn khôi phục được khóa bí mật `d`?

---

>[!Important] Hint
Được `hint` là sử dụng [**Carmichael function**](https://en.wikipedia.org/wiki/Carmichael_function) và tìm cách để cho nó nhỏ nhất nên ta sẽ tiến hành tìm hiểu định nghĩa của nó như sau.

++**Định nghĩa**++: Hàm Carmichael `λ(n)` của một số nguyên dương `n` là giá trị `m` nhỏ nhất sao cho:
$$a^m \equiv 1 \pmod n$$

Với `a` là mọi số nguyên tố với `n` (tức `GCD(a,n)=1`).

Đôi lúc hàm Carmichael `λ(n)` được sử dụng để thay thế hàm Euler `φ(n)` vì nó có thể mang giá trị nhỏ hơn hàm Euler, giúp giảm chi phí tính toán, cụ thể là ở phép tính khóa bí mật `d`, ta có  công thức:

$$d \equiv e^{-1} \pmod {\varphi(n)}$$

Có thể được thay thế thành:
$$d \equiv e^{-1} \pmod {\lambda(n)}$$

Bời vì tính chất: $\lambda(n) | \varphi(n)$.
Điều này giúp khóa bí mật `d` nhỏ hơn (vì nó được tính dưới modulo `λ(n)`).

> `λ(n)` có tính chất giống với `φ(n)` nhưng điểm đặc biệt là nó có thể mang giá trị nhỏ hơn rất nhiều so với `φ(n)`:
![image](https://hackmd.io/_uploads/ryVfcrY3ex.png)

Công thức của hàm `λ(n)` có thể được biểu diễn dưới công thức của hàm `φ(n)` như sau:

$$
\lambda(n) =
\begin{cases}
\varphi(n), & \text{if } n \text{ is } 1, 2, 4, \text{ or an odd prime power}, \\[6pt]
\dfrac{1}{2}\varphi(n), & \text{if } n = 2^r,\; r \geq 3, \\[6pt]
\operatorname{lcm}\!\bigl(\lambda(n_1), \lambda(n_2), \ldots, \lambda(n_k)\bigr), 
& \text{if } n = n_1 n_2 \cdots n_k.
\end{cases}
$$

Trong đó công thức của $\varphi(p^r)$ với $p$ là số nguyên tố và $r \geq 1$ là:
$$\varphi(p^r) = p^{r-1}(p-1)$$

> Ta có công thức tính nhanh của `λ(2^r)` với `r≥3` là: `λ(2^r) = 2^(r-2)`.


---
>[!Important] question
Nắm được tính chất của hàm `Carmichael` rồi, giờ ta sẽ ứng dụng nó vào Challenge của ta như thế nào?

Để hiểu được độ nhỏ của `λ(n)` so với `φ(n)`, ta lấy một ví dụ sau. Giả sử ta có một modulus `n` có kích thước `769 bit` là:
```!
1803242098136617403627683032744086816519252253990109601462437157066086605676458401806269865232873095138146210634332410317591885037589708869541207369916371793985701096750146464842229232786571609836773779621227343176417379009783159710
```

Ta factor giá trị `n` trên và được các ước nhỏ như sau:
```!
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
```

Nếu như ta tính `φ(n)`, thì ta sẽ được một giá trị `766 bit` là:
```!
210156846527805359340602028013011250122036425319594741530754303546212895650172863606787491430002451850407734077095483694468155323926575925884187925175777901763375521410065105999673536985169920000000000000000000000000000000000000000
```

Nhưng nếu ta tính `λ(n)` thì ta sẽ được một giá trị rất nhỏ chỉ `20 bit` là:
```
720720
```

Mà ta có tính chất: `λ(n)`  là ước của `φ(n)`:
$$\lambda(n)|\varphi(n)$$

Nên công thức của khóa bí mật `d` sẽ từ:
$$d \equiv e^{-1} \pmod {\varphi(n)}$$

Trở thành:
$$d \equiv e^{-1} \pmod {\lambda(n)}$$

>[!Important]
Với một `λ(n)` nhỏ thì dù `e` có lớn đến đâu, `d` cũng không thể lớn hơn `λ(n)` được vì công thức của `d` là `d = e^-1 mod λ(n)` sẽ cho ra một giá trị bé hơn `λ(n)`, từ đó ta có thể dễ dàng brute force khóa bí mật `d` trong đoạn `[1, λ(n)-1]`.

++**Minh họa**++:
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
from math import prod, lcm, gcd

n = 1803242098136617403627683032744086816519252253990109601462437157066086605676458401806269865232873095138146210634332410317591885037589708869541207369916371793985701096750146464842229232786571609836773779621227343176417379009783159710
factors = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
assert all([isPrime(i) for i in factors])

phi = prod([p-1 for p in factors])
lam = 720720

e = 0x10001
m = bytes_to_long(b"AT20N0118")
c = pow(m, e, n)

d1 = pow(e, -1, phi) # một giá trị 765 bit
d2 = pow(e, -1, lam) # 554993
print(long_to_bytes(pow(c, d1, n)))
print(long_to_bytes(pow(c, d2, n)))

# b'AT20N0118'
# b'AT20N0118'
```

---
>[!Important]
Vậy hướng đi của ta là: Tìm `n` đủ lớn → `n` cho ra `λ(n)` đủ nhỏ → Gửi `n` đến server nhận `c1,c2` → brute force khóa bí mật `d` trong đoạn `[1, λ(n)-1]` → Giải mã được `m1,m2` → Có `m1,m2` thì giải được Flag 😎

✅ Vậy đầu tiên ta cần tìm `n` sao cho ra `λ(n)` là một giá trị nhỏ.

Giả sử ta cần tìm `n` dạng `n = n1 x n2 x ... x nk` với `n1, n2, nk` là các số `nguyên tố nhỏ`. Thì khi này công thức của `λ(n)` là: $$\operatorname{lcm}\!\bigl(n_1-1, n_2-1, \ldots, n_k-1\bigr)$$

Nên ta sẽ chọn trước một số `λ(n)` sao cho nó chứa các ước nhỏ là `n1-1, n2-1 ,..., nk-1`, sau đó nhân các giá trị `n1, n2,...,nk` lại là có được `n`. Thực hiện như sau:
```python=
from Crypto.Util.number import * 
from sage.all import *

def carmichael_lambda(n):
    factors = factor(n)
    lambdas = []
    for p, e in factors:
        if p == 2 and e >= 3:
            lambdas.append(2**(e-2))
        else:
            lambdas.append((p-1) * p**(e-1))
    return lcm(lambdas)

sample = 720720 
divisor = []

for i in range(1 , sample + 1) :
    if sample % i == 0 and isPrime(i+1) :
        divisor.append(i+1)

print(f"{divisor = }")

N = 1 
for i in divisor :
    N*=i

print("bit length of N =", N.bit_length())

assert carmichael_lambda(N) == sample
# divisor = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 113, 127, 131, 157, 181, 199, 211, 241, 281, 313, 331, 337, 397, 421, 463, 521, 547, 617, 631, 661, 859, 881, 911, 937, 991, 1009, 1093, 1171, 1321, 1873, 2003, 2311, 2341, 2521, 2731, 2861, 3121, 3433, 3697, 4621, 6007, 6553, 8009, 8191, 8581, 9241, 16381, 18481, 20021, 20593, 21841, 25741, 36037, 48049, 51481, 55441, 65521, 72073, 120121, 180181]
# bit length of N = 769
```

> Vậy là ta có thể tạo được một modulus `n` từ một `λ(n)` cho trước rồi.

✅ Vậy bây giờ độ lớn của `n` và `λ(n)` là bao nhiêu thì hợp lý?

Quan trọng nhất thì `λ(n)` không được quá lớn vì nếu quá lớn (hơn `10 triệu`) thì bước brute force `d` diễn ra rất lâu vì phép lũy thừa chạy rất chậm.

Tiếp theo, dựa vào format của `Flag` là `KMACTF{???????????????????????????????}` ta ước chừng được độ lớn của `m1,m2` sẽ là `103` và `309` bit nên ta tìm một giá trị `n` khoảng `500` bit là hợp lý. Sau đó ta sẽ nhân thêm `n` với một số `n1` nữa để kích thước đạt `2024` bit.

>[!Important] question
 Tại sao không cần tìm `λ(n)` cho ra `n` 2048 bit, lý do là vì `n` lớn thì `λ(n)` cũng có thể sẽ lớn theo, ảnh hưởng quá trình tìm `d`. Không phải lúc nào `d` cũng tồn tại vì `e` chưa chắc đã nguyên tố với `λ(n)` nên ta cần connect tới server nhiều lần đến khi `e` nguyên tố với `λ(n)` thì mới có `d` được, vì vậy `λ(n)` quá lớn sẽ không tốt.
Bên cạnh đó `n` quá to cũng không cần thiết vì khi ta gửi `N = n.n1` đến server (n1 là phần pad vào cho đủ 2024 bit), server sẽ thực hiện phép tính sau:
    $$c_1 = m_1^e \pmod {n.n.n_1.n_1}$$
Vì `n|N` nên ta chỉ cần mod hai vế cho `n` là phép tính trở thành:
$$c_1 = m_1^e \pmod {n}$$

Sau nhiều bước test và thử nghiệm thì giá trị `λ(n)` mình thấy hợp lý là:
$$\lambda(n) = 2^6 . 3^2 . 5 . 7 . 13 = 262080$$

Nó không quá lớn và cũng cho ra `n` 555 bit, khá vừa vặn với `m1,m2`:
```!
N = 
85217303986526089768208675693780350913114318459795065165687931019468545740678895390536616742913898903010234170773026814502401638427394841422684958144254198784116180310

factors = 
[2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
```

---

Có `n`, ta gửi đến server để nó tính `c1,c2`, sau đó brute force `d` trong khoảng `[1,λ(n)-1]` đến khi nào giải mã được `m1,m2` thì dừng:
```python=
from Crypto.Util.number import *
from math import prod
from pwn import *
from tqdm import *
from sage.all import *

carmichael = 2**6 * 3**2 * 5 * 7 * 13

Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)
# n1 là padding cho đủ 2024 bit
n1 = 16137065238548023209354216756994085116039071329741992404760044520469775763598604679740651617211548370722607323479545645549867358928555262389728162798543590988183336155777102822466433736318341045782578414126244103517499384317415648780840623744041560018889448526450175979862047825655610652640229808466274926539017341691446592144579795902560014607660916789992333812186930296354747949841511313853809884979361487225668820393379628401205576558482036
N = n*n1

assert (N**2).bit_length() == 4048

exit = False
while True:
    if exit:
        break
    print("Finding e such that gcd(e, lambda) == 1")
    
    io = remote("165.22.55.200", 30001)
    # io = process(["python3", "test.py"])

    io.sendlineafter(b"> ", b"1"); io.sendlineafter(b" : ", b"1"); io.sendlineafter(b" : ", str(N).encode())
    io.sendlineafter(b"> ", b"2"); io.recvuntil(b"ciphertext :\n")
    
    c1, c2 = eval(io.recvline())
    io.close()

    c1 = c1 % n
    c2 = c2 % n

    # không biết e nên ta sẽ brute force d
    print("finding d in range(1, lambda-1)")
    for d in trange(1, carmichael):
        m1 = pow(c1, d, n)
        if m1.bit_length() < 300 and m1.bit_length() != 1 and long_to_bytes(m1).endswith(b"}"):
            print("✅")
            print(f"{d = }")
            exit = True
            break
    io.close()

# có m1 là có flag3
m1 = int(m1)
m2 = pow(c2, d, n)

print(f"{m1 = }")
print(f"{m2 = }")
```
![image](https://hackmd.io/_uploads/SkhWEH5hxe.png)

Vậy là tìm được `m1,m2` rồi 😎
```!
m1 = 35689003380947478572094688521116102469800350398642557
m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838
```

> Mình thử giải mã `m1` thì được `_ch4113n93_15_50_345y}`, nó không dài `13` bytes như trong format của `Flag` mà dài `22` bytes 💀

---

Giờ ta cần giải phương trình:
$$m_2 = 65537 \times \text{Flag}_1^2 + m_1\times \text{Flag}_2^2$$

Để tìm lại nốt `Flag1` và `Flag2`.

Đây là phương trình bậc nhất hai ẩn nên nó sẽ có vô số nghiệm, mình thử `LLL` để giải phương trình `65537.a + m1.b = m2` nhưng mà không được vì `a,b` khá to.

Để giải nó thì ta cần triệt tiêu một ẩn đi, mẹo chính là mod phương trình trên cho `m1`, nó sẽ triệt tiêu đi phần `Flag2^2`, chỉ còn lại `Flag1^2` mà thôi, ta được một phương trình modulo bậc 2 là:
$$m_2 = 65537 \times \text{Flag}_1^2 \pmod {m_1}$$

Phương trình chỉ có một ẩn `Flag1` nên ta sẽ sử dụng phương thức `.roots(multiplicities = False)` của sagemath để giải, tìm được `Flag1` là `KMACTF{n07h1n_1d34_70_`:

```python=
from Crypto.Util.number import *
from sage.all import *

Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)

m1 = 35689003380947478572094688521116102469800350398642557
m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838

x = PolynomialRing(Zmod(m1), "x").gen()
f = 65537*x**2 - m2

for i in f.roots(multiplicities = False):
    print(i, long_to_bytes(int(i)))
```
![image](https://hackmd.io/_uploads/S1dJDH93gx.png)

> ++**Chú ý**++: Phương trình sẽ cho ra `2^3` nghiệm và trong số đó sẽ có `Flag1 mod m1`, ở đây vì `Flag1 < m1` nên nó tìm ra được `Flag1` luôn, còn nếu `Flag1 > m1` thì sẽ cho ra `Flag1 mod m1` chứ không phải `Flag1`, cũng không ảnh hưởng gì nhiều, ta chỉ cần brute force thêm một xíu thôi.

Có `Flag1`, thay ngược lại phương trình `m2` và tính được `flag2` là `7yp3_h323_83c4u53_7h15`:
```python=
from Crypto.Util.number import *
from sage.all import *

m2 = 15374382952448648386234156647364992061140979466732533176937863507778552068695153712875826599052803361828508498209602868391557371030313888768898114752847802838

x = PolynomialRing(ZZ, "x").gen()
f = 65537*bytes_to_long(b"KMACTF{n07h1n_1d34_70_")**2 + bytes_to_long(b"_ch4113n93_15_50_345y}")*x**2 - m2

print(long_to_bytes(int(f.roots()[0][0])))
```

Ta tìm được Flag hoàn chỉnh là: 
```
KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}
```
Kết thúc Challenge.

:::spoiler **Full script**
```python=
from Crypto.Util.number import *
from math import prod
from pwn import *
from tqdm import *
from sage.all import *

carmichael = 2**6 * 3**2 * 5 * 7 * 13

Q = [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 71, 73, 79, 97, 113, 127, 131, 157, 181, 193, 211, 241, 281, 313, 337, 421, 449, 521, 547, 577, 631, 673, 911, 937, 1009, 1093, 1171, 1249, 1873, 2017, 2081, 2341, 2521, 2731, 3121, 3361, 6553, 7489, 8191, 8737, 14561, 16381, 20161, 21841, 26209, 37441, 65521, 131041]
n = prod(Q)
# n1 là padding cho đủ 2024 bit
n1 = 16137065238548023209354216756994085116039071329741992404760044520469775763598604679740651617211548370722607323479545645549867358928555262389728162798543590988183336155777102822466433736318341045782578414126244103517499384317415648780840623744041560018889448526450175979862047825655610652640229808466274926539017341691446592144579795902560014607660916789992333812186930296354747949841511313853809884979361487225668820393379628401205576558482036
N = n*n1

assert (N**2).bit_length() == 4048

exit = False
while True:
    if exit:
        break
    print("Finding e such that gcd(e, lambda) == 1")
    
    io = remote("165.22.55.200", 30001)
    # io = process(["python3", "test.py"])

    io.sendlineafter(b"> ", b"1"); io.sendlineafter(b" : ", b"1"); io.sendlineafter(b" : ", str(N).encode())
    io.sendlineafter(b"> ", b"2"); io.recvuntil(b"ciphertext :\n")
    
    c1, c2 = eval(io.recvline())
    io.close()

    c1 = c1 % n
    c2 = c2 % n

    # không biết e nên ta sẽ brute force d
    print("finding d in range(1, lambda-1)")
    for d in trange(1, carmichael):
        m1 = pow(c1, d, n)
        if m1.bit_length() < 300 and m1.bit_length() != 1 and long_to_bytes(m1).endswith(b"}"):
            print("✅")
            print(f"{d = }")
            exit = True
            break
    io.close()

# có m1 là có flag3
m1 = int(m1)
m2 = pow(c2, d, n)

flag3 = long_to_bytes(m1)
print(f"{flag3 = }")

# credit: vanMjnh
# có flag3, ta mod m2 cho flag3
# được phương trình f = 65537*flag1**2 - m2
x = PolynomialRing(Zmod(m1), "x").gen()
f = 65537*x**2 - m2

# sẽ tìm ra nghiệm flag1 % flag3, xét luôn trường hợp flag1 > flag3
root = f.roots(multiplicities = False)
exit = False
for r in root:
    if exit:
        break
    flag1_mod = int(r)
    for k in range(100):
        flag1 = long_to_bytes(flag1_mod + k*m1) # flag1 = flag1_mod + k*m1
        if flag1.startswith(b"KMACTF{"):
            print(f"{flag1 = }")
            exit = True
            break

# có flag1 và flag3 ta thay vào pt m2 để tìm nốt flag2
x = PolynomialRing(ZZ, "x").gen()
f = 65537*bytes_to_long(flag1)**2 + bytes_to_long(flag3)*x**2 - m2

root = f.roots()
flag2 = long_to_bytes(int(root[0][0]))
print(f"{flag2 = }")

print("✅", flag1 + flag2 + flag3)
"""
Finding e such that gcd(e, lambda) == 1
[+] Opening connection to 165.22.55.200 on port 30001: Done
[*] Closed connection to 165.22.55.200 port 30001
finding d in range(1, lambda-1)
 61%|██████████████████████████████████████████████████████████▏                                     | 158761/262079 [00:04<00:03, 30791.95it/s]
✅ d = 159361
flag3 = b'_ch4113n93_15_50_345y}'
flag1 = b'KMACTF{n07h1n_1d34_70_'
flag2 = b'7yp3_h323_83c4u53_7h15'
✅ b'KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}'
"""
```
:::spoiler **Flag**
**KMACTF{n07h1n_1d34_70_7yp3_h323_83c4u53_7h15_ch4113n93_15_50_345y}**
:::

# End
:::spoiler
Lại một mùa KMACTF trôi qua, em xin lỗi anh Tuệ
![548276495_1336936471772963_3528833647013735909_n](https://hackmd.io/_uploads/rJJMoIY2ex.jpg)
:::