# Base64

source code:

b64 = {'000000': '/', '000001': '+', '000010': '0', '000011': '1', '000100': '2', '000101': '3', '000110': '4', '000111': '5', '001000': '6', '001001': '7', '001010': '8', '001011': '9', '001100': 'a', '001101': 'b', '001110': 'c', '001111': 'd', '010000': 'e', '010001': 'f', '010010': 'g', '010011': 'h', '010100': 'i', '010101': 'j', '010110': 'k', '010111': 'l', '011000': 'm', '011001': 'n', '011010': 'o', '011011': 'p', '011100': 'q', '011101': 'r', '011110': 's', '011111': 't', '100000': 'u', '100001': 'v', '100010': 'w', '100011': 'x', '100100': 'y', '100101': 'z', '100110': 'A', '100111': 'B', '101000': 'C', '101001': 'D', '101010': 'E', '101011': 'F', '101100': 'G', '101101': 'H', '101110': 'I', '101111': 'J', '110000': 'K', '110001': 'L', '110010': 'M', '110011': 'N', '110100': 'O', '110101': 'P', '110110': 'Q', '110111': 'R', '111000': 'S', '111001': 'T', '111010': 'U', '111011': 'V', '111100': 'W', '111101': 'X', '111110': 'Y', '111111': 'Z'}

def encode(string):
    s = ""
    for i in string:
        s += bin(ord(i))[2:].zfill(8)

    pad = ""
    if len(s) % 6 == 4:
        pad = "="
        s += "11"
    elif len(s) % 6 == 2:
        pad = "=="
        s += "1111"

    ret = ""
    for i in range(0,len(s),6):
        ret += b64[s[i:i+6]]
    return ret+pad

from secret import FLAG
print(encode(FLAG))
# gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR=

Đây là một bài tự custom Base64. Ta chỉ cần xây dựng một bảng Base64 đảo ngược từ bảng Base64 đã được cung cấp, rồi từ đó ánh xạ các bit trong ciphertext qua bảng Base64 đảo ngược đó sẽ tìm được plaintext ban đầu.

> Lưu ý là phải chú ý đến việc ciphertext đã được pad thêm 1 dấu "="

:::spoiler solve

ciphertext = "gObheRHIpN+wlQ7vqQiQb3XzpAbJn4iv6lR="
b64 = {'000000': '/', '000001': '+', '000010': '0', '000011': '1', '000100': '2', '000101': '3', '000110': '4', '000111': '5', '001000': '6', '001001': '7', '001010': '8', '001011': '9', '001100': 'a', '001101': 'b', '001110': 'c', '001111': 'd', '010000': 'e', '010001': 'f', '010010': 'g', '010011': 'h', '010100': 'i', '010101': 'j', '010110': 'k', '010111': 'l', '011000': 'm', '011001': 'n', '011010': 'o', '011011': 'p', '011100': 'q', '011101': 'r', '011110': 's', '011111': 't', '100000': 'u', '100001': 'v', '100010': 'w', '100011': 'x', '100100': 'y', '100101': 'z', '100110': 'A', '100111': 'B', '101000': 'C', '101001': 'D', '101010': 'E', '101011': 'F', '101100': 'G', '101101': 'H', '101110': 'I', '101111': 'J', '110000': 'K', '110001': 'L', '110010': 'M', '110011': 'N', '110100': 'O', '110101': 'P', '110110': 'Q', '110111': 'R', '111000': 'S', '111001': 'T', '111010': 'U', '111011': 'V', '111100': 'W', '111101': 'X', '111110': 'Y', '111111': 'Z'}


b64_decode = {}
for key in b64:
    b64_decode[b64[key]] = key


def decode(ciphertext):
    plaintext_bin = ""
    for i in range(0, len(ciphertext)):
        if(ciphertext[i] in b64_decode):
            plaintext_bin += b64_decode[ciphertext[i]]

    plaintext = ""
    for i in range(0, len(plaintext_bin), 8):
        char = plaintext_bin[i:i+8]
        if(len(char) == 8):
            plaintext += chr(int(char, 2))
    
    return plaintext


flag = decode(ciphertext)
print(flag)

:::
:::spoiler Flag
KCSC{no0b_base64_encode!!}
:::

---
# Baby RSA

soure code:

from Crypto.Util.number import *
from secret import flag 

# Params
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512) 
n = p*q
e1 , e2 = getPrime(15) , getPrime(15)

# Encrypt 
c1 , c2 = pow(m,e1,n) , pow(m,e2,n)

#Print
print(f'{c1 = }')
print(f'{c2 = }')
print(f'{n = }')
# c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
# c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
# n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733

Đây là một lổ hổng kinh điển liên quan đến việc dùng chung một modulus $N$ trong RSA.
Từ source code ta biết rằng $C_1, C_2$ được mã hóa như sau:
$$\begin{cases}
C_1 \equiv m^{e_1} \pmod N \\
C_2 \equiv m^{e_2} \pmod N
\end{cases}$$

Theo bổ đề Bézout, ta luôn tìm được nghiệm a, b của phương trình:
$$a \cdot e_1 + b \cdot e_2 = \gcd(e_1, e_2)$$

Vậy nếu ta tìm được $e_1, e_2$ sao cho $gcd(e_1, e_2) = 1$ thì ta suy ra được:
$$C_1^a \cdot C_2^b \equiv (m^{e_1})^a \cdot (m^{e_2})^b \equiv m^{a e_1 + b e_2} \equiv m^1 \equiv m \pmod N$$

Biết rằng $e_1, e_2$ là 2 số nguyên tố có 15 bit nên ta dùng hàm `primerange` để brute-force 2 giá tị này một cách nhanh chóng. Còn việc tìm $a, b$ thì có thể dùng thuật toán Euclid mở rộng để tính, mình sẽ dùng hàm `gcdext` có sẵn của thư viện `gmpy2` để tính .

::: spoiler solve

from Crypto.Util.number import long_to_bytes
from math import gcd
from sympy import primerange
from gmpy2 import gcdext

c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726
c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285
n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733

for e1 in primerange(2**14, 2**15):
    for e2 in primerange(2**14, 2**15):
        if(e1 != e2):
            g, a, b = gcdext(e1, e2)
            m = pow(c1, a, n) * pow(c2, b, n) % n
            flag = long_to_bytes(m)
            if(b'KCSC' in flag):
                print(flag.decode())
                exit()

:::

::: spoiler Flag
KCSC{3x73rn4l_4774ck_1n_r54}
:::
# Equation

source code:

from Crypto.Util.number import *
from secret import flag

def encrypt(key,m,p) :

    x = pow(key[0],key[1]*key[3])*m[0] + pow(key[1],key[0])*m[1] + key[3]*pow(key[0],key[2])
    y = pow(key[2],7)*m[0] - key[3]*m[1] - pow(key[1],key[2]) + pow(key[1],key[3])

    return x % p , y % p 


l = len(flag)
m = [bytes_to_long(flag[:l//2]) , bytes_to_long(flag[l//2:])]
key = [getPrime(512) for _ in range(4)]
p = getPrime(513)

assert m[0] < p and m[1] < p

print(f'{p = }')
print(f'{key = }')
print(f'enc = {encrypt(key,m,p)}')

# p = 20750581162356901822371358081190571328015802896649862988773357210365403451164295986427869541008180700500353488943618054413871626104729648400643237412907397
# key = [10615429627321757928177738179133185296570017221477669072758978616664228021845901597204223511408890540624134699383980095897619794674624492632667368475358259, 8098501561956901533078786276609230622379951738654895152558539730068867983865132393839072902654774417952229287146962827464998772217889942772581719194190131, 9269375490983296814341239266604470459081391713689916499923163097001047076919399181791596915795736751249702479913935198254324261729115107153324477349756427, 12874926087069061223584117322772472091608363055078190028227481439885266810498837550235424358641464176775190647579561772510312989190222563737455288997494613]
# enc = (5309143145537110495610885061155974900644691542339737247048051865028676282189484534760797421532227725431411920294833901798304659011582328440228296618492754, 12319093933825845906195612210823362436789866252839892395323597642449461144960813359448423496536622280247713676669361185330767001694340173433507185981408484)

Ta source code ta rút ra được hệ phương trình như sau

$$\begin{cases}
c_1 \equiv k_0^{k_1 k_3} \cdot m_1 + k_1^{k_0}\cdot m_2 + k_3 \cdot k_0^{k_2} \pmod p\\
\\
c_2 = k_2^7 \cdot m_1 - k_3\cdot m_2 - k_1^{k_2} + k_1^{k_3} \pmod p
\end{cases}$$

Nhìn hệ này có vẻ phức tạp nhưng thật ra nó chỉ là hệ phương trình tuyến tính bậc nhất 2 ẩn, nên hoàn toàn có thể cô lập 1 ẩn rồi thay vào giải ra ẩn còn lại, mình khá lười nên sẽ ma trận hóa hệ phương trinh này rồi dùng Sage để giải.
Đầu tiên ta nên đặt các hệ số gọn hơn:
$$\begin{cases}
c_1 = A \cdot m_1 + B \cdot m_2 + C \\
c_2 = X \cdot m_1 + Y \cdot m_2 + Z
\end{cases}$$

Chuyển các hằng số tự do $C, Z$ sang vế trái :$$\begin{cases}
A \cdot m_1 + B \cdot m_2 = c_1 - C \\
X \cdot m_1 + Y \cdot m_2 = c_2 - Z
\end{cases}$$

Đây là dạng phương trình ma trận $\mathbf{M} \times \mathbf{m} = \mathbf{V}$
$$\begin{pmatrix} A & B \\ X & Y \end{pmatrix}\times \begin{pmatrix} m_1 \\ m_2\end{pmatrix} = \begin{pmatrix} c_1 - C \\ c_2 - Z \end{pmatrix}$$
Để giải thì có thể dùng hàm `M.solve_right(V)`.

>Khi code thì nên lấy $A$ % $p$ luôn để tránh tràn số trong Sage

:::spoiler solve

from Crypto.Util.number import long_to_bytes


p = 20750581162356901822371358081190571328015802896649862988773357210365403451164295986427869541008180700500353488943618054413871626104729648400643237412907397
key = [10615429627321757928177738179133185296570017221477669072758978616664228021845901597204223511408890540624134699383980095897619794674624492632667368475358259, 8098501561956901533078786276609230622379951738654895152558539730068867983865132393839072902654774417952229287146962827464998772217889942772581719194190131, 9269375490983296814341239266604470459081391713689916499923163097001047076919399181791596915795736751249702479913935198254324261729115107153324477349756427, 12874926087069061223584117322772472091608363055078190028227481439885266810498837550235424358641464176775190647579561772510312989190222563737455288997494613]
enc = (5309143145537110495610885061155974900644691542339737247048051865028676282189484534760797421532227725431411920294833901798304659011582328440228296618492754, 12319093933825845906195612210823362436789866252839892395323597642449461144960813359448423496536622280247713676669361185330767001694340173433507185981408484)

c1, c2 = enc[0], enc[1]
A = pow(key[0],key[1]*key[3], p)
B = pow(key[1],key[0], p)
C = key[3]*pow(key[0],key[2], p)
X = pow(key[2],7, p)
Y = -key[3]
Z = -pow(key[1],key[2], p) + pow(key[1],key[3], p)

R = GF(p)
M = matrix(R, [[A, B], [X, Y]])
V = vector(R, [c1 - C, c2 - Z])

sol = M.solve_right(V)
m1, m2 = int(sol[0]), int(sol[1])
flag = long_to_bytes(m1) + long_to_bytes(m2)
print(flag.decode())

:::
:::spoiler Flag
KCSC{b4by_3qu4710n_l34rn1n6}
:::
# Caesar Starter
source code:

import random
from secret import flag


def generate_key():
    return [random.randint(0, len(words)) for _ in range(4)]


def encrypted(key,flag) :
    data = [printable.index(i) for i in flag]
    encrypted = ''

    for i in range(len(flag)) :
        encrypted += words[(data[i] + key[i%4]) % 96]

    return encrypted


words = r"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"



random.seed(random.randrange(0,2**20))

printable_characters = list(words)
printable = ''


for i in range(len(printable_characters)) :
    chosen_char = random.choice(printable_characters)
    if chosen_char != ' ' : 
        printable += chosen_char
        printable_characters.remove(chosen_char)


key = generate_key()
ct = encrypted(key,flag)

print(ct)

# -}Pnr<U5bYw}p.UU5JM5S[Z[*nT]SY6~

Một bài tự custom mã hóa Caesar với việc dùng một seed ngẫu nhiên có giá trị từ $0$ đến $2^{20}$ để sinh ra các `key`, chuỗi `printable` ngẫu nhiên

Trong thư viện random của Python, số ngẫu nhiên thực chất là giả ngẫu nhiên (Pseudo-random). Nó hoạt động dựa trên một thuật toán toán học (thường là Mersenne Twister) bắt đầu từ một con số khởi đầu gọi là **Seed**. Nó có một đặc điểm thú vị là ví dụ nếu bạn chọn **Seed** là 123, máy tính sẽ luôn đọc ra dãy số: 5, 92, 11, 4... Nếu bạn chạy lại chương trình và vẫn chọn Seed là 123, máy tính vẫn đọc y chang: 5, 92, 11, 4...
Vậy nên ta hoàn toàn có thể brute-force tìm seed mà challenge đã dùng ($2^{20}$ không phải là một con số quá lớn). Với mỗi seed thì ta sinh ra 4 giá trị key và chuỗi printable theo đúng cái cách mà challenge sinh ra, từ đó xây dựng một hàm giải mã dùng các giá trị đó để giải mã ra flag

Ta xây dựng hàm giải mã như sau:
- Với hàm mã hóa:
+ Lấy vị trí của ký tự Flag trong printable
+ Cộng với Key.
+ Lấy ký tự tại vị trí mới trong words
- Vậy nên thứ tự hàm giải mã sẽ là:
+ Lấy vị trí kí tự của Ciphertext trong words.
+ Trừ giá trị đó với Key.
+ Ánh xạ giá trị đó qua chuỗi printable để thu được Plaintext ban đầu.
::: spoiler solve

import random

ciphertext = "-}Pnr<U5bYw}p.UU5JM5S[Z[*nT]SY6~"
words = r"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"


def generate_key():
    return [random.randint(0, len(words)) for _ in range(4)]


def decrypted(key,ciphertext):
    plaintext = ""
    for i in range(len(ciphertext)):
        plaintext += printable[(words.index(ciphertext[i]) - key[i%4]) % 96]

    return plaintext


for seed in range(2**20):
    random.seed(seed)

    printable_characters = list(words)
    printable = ''

    for i in range(len(printable_characters)):
        chosen_char = random.choice(printable_characters)
        if chosen_char != ' ' : 
            printable += chosen_char
            printable_characters.remove(chosen_char)
    
    key = generate_key()

    flag = decrypted(key,ciphertext)
    if "KCSC" in flag:
        print(flag)
        break

:::
::: spoiler Flag
KCSC{345y_c4354r_cu570m_r16h7_?}
:::
# 43S

source code:

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


def encrypt(key: bytes, msg: bytes) -> bytes:

    iv = os.urandom(16)
    plaintext = [msg[i:i + 16] for i in range(0, len(msg), 16)]

    blocks = []
    prev_ciphertext = iv
    prev_plaintext = bytes(16)

    for plaintext_block in plaintext:
        c = AES.new(key, AES.MODE_ECB)
        ciphertext_block = c.encrypt(xor(plaintext_block,prev_ciphertext, prev_plaintext))
        blocks.append(ciphertext_block)
        prev_ciphertext = ciphertext_block
        prev_plaintext = plaintext_block

    return iv + b''.join(blocks)

def decrypt(key: bytes, msg: bytes) -> bytes:

    c = AES.new(key, AES.MODE_ECB)
    return c.decrypt(msg[16:])


key = os.urandom(16)
ciphertext = encrypt(key, pad(flag, 16))

print(f'Here is my gift for you , good luck : {ciphertext.hex()}')

while True:

    print("1. Encrypt")
    print("2. Decrypt")

    otp = int(input(">> "))

    if otp == 1:

        msg = bytes.fromhex(input("Enter your message: "))
        ciphertext = encrypt(key, pad(msg, 16))
        print(f'Ciphertext : {ciphertext.hex()}')

    elif otp == 2:

        msg = bytes.fromhex(input("Enter the ciphertext: "))
        plaintext = decrypt(key, msg)
        print(f'Plaintext : {plaintext.hex()}')

    else:
        exit()

Đây là một bài AES dùng mode PCBC cơ bản, từ hàm `encrypt` ta có:
$$C_i = D_K(P_i \oplus C_{i-1} \oplus P_{i-1})$$
Server cung cấp cho bạn hàm `decrypt`. Nhưng hãy xem kỹ code của nó:

def decrypt(key: bytes, msg: bytes) -> bytes:
    c = AES.new(key, AES.MODE_ECB)
    return c.decrypt(msg[16:])

Lỗ hổng ở đây là gì?
=> Hàm này KHÔNG thực hiện bước XOR với $C_{i-1}$ và $P_{i-1}$. Nó chỉ thuần túy chạy lệnh AES Decrypt với khối plaintext bạn gửi.
Nghĩa là, giá trị mà server trả về cho bạn (tạm gọi là $O$) với: $$O_i = D_K(C_i)$$
Mà theo công thức PCBC ở rên, ta biết:$$D_K(C_i) = P_i \oplus C_{i-1} \oplus P_{i-1}$$
Nên:$$O_i = P_i \oplus C_{i-1} \oplus P_{i-1}$$

Vậy chiến thuật tấn công của ta là sẽ tìm plaintext theo phương trình:
$$P_i = O_i \oplus C_{i-1} \oplus P_{i-1}$$
Cụ thể:
- Giả sử Ciphertext đề bài cho là chuỗi: `IV | C1 | C2 | C3 ...`
- Ta tìm $P_1$ như sau:
+ Gửi lên server: 16 bytes ngẫu nhiên + C1. (Vì hàm decrypt có lệnh msg[16:] cắt bỏ 16 byte đầu).
+ Server trả về: $O_1$.
+ Tính $P_1$ bằng cách: $P_1 = O_1 \oplus IV \oplus P_0$.
- Tương tự với $P_2$:
+ Gửi lên server: 16 bytes rác + $C_2$.
+ Server trả về: $O_2$.
+ Tính toán: $P_2 = O_2 \oplus C_1 \oplus P_1$ (ta đã có $C_1, P_1$ từ bước trước.

- Cứ tiếp tục quá trình đó cho đến khi thu được đầy đủ Plaintext

:::spoiler solve

from pwn import *
from Crypto.Util.Padding import unpad
import sys

p = process(['python', 'chall.py'])

p.recvuntil(b'good luck : ')

full_ciphertext = bytes.fromhex(p.recvline().strip().decode())
iv = full_ciphertext[:16]
ciphertext = full_ciphertext[16:]
blocks = [ciphertext[i:i+16] for i in range(0, len(ciphertext), 16)]
plaintext = b""
prev_ciphertext = iv
prev_plaintext = bytes(16)
for i, block in enumerate(blocks):
    p.sendlineafter(b'>> ', b'2')
    pad = b'\x00' * 16
    payload = (pad + block).hex().encode()
    p.sendlineafter(b'ciphertext: ', payload)
    p.recvuntil(b'Plaintext : ')
    DK = bytes.fromhex(p.recvline().strip().decode())
    pt = xor(DK, prev_ciphertext, prev_plaintext)
    plaintext += pt
    prev_ciphertext = block
    prev_plaintext = pt
flag = unpad(plaintext, 16)
print(flag.decode())
p.close()

:::
::: spoiler Flag
KCSC{50m3_p30pl3_d0n7_7h1nk_1v_15_1mp0r74n7_1n_pcbc_m0d3?}
:::
# Heoman

source code:

from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES 
from hashlib import sha256 
from random import randint
from secret import flag 


# Params 
p = getPrime(512)
a = randint(2**33,2**35)
g = 2050493


# Exchange 
gA = pow(g,a,p)
r = randint(0,p-1)
B = pow(r,(p-1)//g,p)
gB = pow(B,a,p)


# Encrypt 
key = sha256(str(gB).encode()).digest()[:16]
cipher = AES.new(key,AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag,16))


# Print
print(f'{ciphertext = }')
print(f'{p = }')
print(f'{B = }')

# ciphertext = b'\xe6\xcb\xc6\x1d\xb19\xa4\xb8)V\x95u\xf8\x1b\x139 PI8\xa3\xcb\xb3\x85\x1ap\xbai.\xea\x1d\xab\x9a\x90\x82\x1a3\x91_;\xa5\x0e \x05\xf7\xf58%'
# p = 12373179506263461354514623365077132800661338897023082048202681278072369025695953393083636918398048660173612137128780210954723129668855320275665251703736793
# B = 12000841720785201162570293150131106089496068719117766176856306894850593806350814073092246930470170348368143014207968119599751108320780548445547875340920785

Thật sự thì tại thời điểm mà giải bài này thì mình chưa biết tới khái niệm Diffie-Hellman là gì, chỉ đơn thuần là suy nghĩ xem Flag được mã hóa kiểu gì, cần giá trị gì để giải mã ra Flag, đây là lời giải của mình lúc đó:

Nhận thấy rằng Flag được mã hóa bằng AES với mode ECB. Còn key thì được mã hóa bằng hàm băm `sha256` với giá trị đầu vào là $g_B$
Vậy nếu ta tìm được $g_B$, ta sẽ tìm được Flag.
Từ source code thấy rằng $g_B$ được tính theo công thức:
$$g_B \equiv B^a \pmod p$$
Ta đã có $B, p$, nhưng chưa có $a$, và $a$ thì được sinh ngẫu nhiên trong khoảng $[2^{33}, 2^{35}]$ nên không thể brute-force được.
Sau đó mình để ý đến cách họ tính $B$:
$$B \equiv r^{\frac{p-1}{g}} \pmod p$$
Lấy mũ $g$ hai vế ta sẽ được
$$B^g \equiv (r^{\frac{p-1}{g}})^g \equiv r^{p-1} \pmod p$$
Đến đây mình thấy được ánh sáng rồi, đó chính là định lý Fermat nhỏ.
Theo định lý Fermat nhỏ, ta biết rằng với mọi số nguyên $r$, ta luôn có:$$r^{p-1} \equiv 1 \pmod p$$
Vậy thì:
$$B^g \equiv 1 \pmod p$$
> Nhưng điều này có ý nghĩa gì?

Chúng ta hãy thử phân tích $a$ ra, theo lý thuyết số thì mọi số nguyên $a$ đều có thể được biễu diễn thông qua phép chia cho một só $g$ nào đó như sau:
$$a = k.g + r$$
- Với $k$ là thương số
- $r$ là số dư (hay nói cách khác là $a \pmod g$)

Vậy biến đổi phương trình $g_B$ lại:
$$g_B \equiv B^a \equiv B^{k.g + r} \equiv B^{k.g} . B^r \equiv \ 1.B^r \equiv B^{a \pmod g} \pmod p$$

Số mũ $a \pmod g$ nó sẽ chỉ có giá trị từ 0 đến $g-1$. Và $g$ thì chỉ = $2050493$, vậy là hoàn toàn có thể brute-force $a$ được rồi.
Ta sẽ thử tính $g_B$ theo từng $a$ rồi băm nó bằng `sha256` để thành key rồi tìm Flag.
:::spoiler solve

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES 
from hashlib import sha256 

ciphertext = b'\xe6\xcb\xc6\x1d\xb19\xa4\xb8)V\x95u\xf8\x1b\x139 PI8\xa3\xcb\xb3\x85\x1ap\xbai.\xea\x1d\xab\x9a\x90\x82\x1a3\x91_;\xa5\x0e \x05\xf7\xf58%'
p = 12373179506263461354514623365077132800661338897023082048202681278072369025695953393083636918398048660173612137128780210954723129668855320275665251703736793
B = 12000841720785201162570293150131106089496068719117766176856306894850593806350814073092246930470170348368143014207968119599751108320780548445547875340920785
g = 2050493


for a in range(g):
    g_B = pow(B, a, p)
    key = sha256(str(g_B).encode()).digest()[:16]
    cipher = AES.new(key,AES.MODE_ECB)
    plaintext = cipher.decrypt(ciphertext)
    if(b'KCSC{' in plaintext):
        print(plaintext.decode())
        break

:::
:::spoiler Flag
KCSC{5m4ll_5ub_6r0up_4774ck_1n_p0hl16_h3llm4n}
:::

> Có cái khá là vui là nếu để điều kiện là `if(b'KCSC' in plaintext)` thì sẽ gặp cái chuỗi b'\xa6\xc6K`\x17&\xf7W\x8d|7D:2\xb7\n\xff\xfbO\xd5d|w\xb9\xb4\xb9\xe9X\x9cU\x06\x07\x00+B\xd02=KCSC4\xf1\xfc\xb2\xdd\x84'

# Sign
chall.py:

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from os import *
from random import randint
from pwn import xor
from base64 import b64decode
flag = "KCSC{???????????????}"

secret = urandom(16)

G = generator_256
p = G.order()

def genKeyPair():
    d = randint(1,p-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(b64decode(nonce),secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

def challenge() :
    pubkey , privkey = genKeyPair()

    print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
    print("1 : Sign msg ")
    print("2 : Submit private key")
    nonces = []
    for _ in range(3) :
        try : 
            option = int(input("Option : "))
            if option == 1 :

                msg = (input("Enter your message: ")).encode()
                nonce = (input("Enter your nonce: ")).encode()

                if nonce in nonces :
                    print('Nope')
                    exit()

                if len(nonces) > 0 : 

                    for i in nonces :
                        if nonce in i or i in nonce:
                            print('Nope')
                            exit()

                nonces.append(nonce)
                print(ecdsa_sign(msg,nonce,privkey))


            if option == 2 :

                d = int(input("Private key : "))
                print(nonces)
                if d == int(privkey.secret_multiplier) :
                    print(f'Very nice , here is your flag : {flag}')
                    exit()

                else :

                    print(f'Wrong key , correct is {privkey.secret_multiplier}')
                    exit()

        except :

            print("Not legal option")
            exit()
    print("Out of attemps !! ")    
challenge()

Đây là một bài toán khai thác lỗi mật mã ECDSA cổ điển: **Nonce Reuse Attack**, ta sẽ tận dụng một cái quy tắc của `base64` để lách luật đầu vào.

Trong thuật toán chữ ký số ECDSA, mỗi lần ký một tin nhắn, ta cần một số ngẫu nhiên bí mật $k$ (nonce). Chữ ký $(r, s)$ được tính như sau:
$$r = (k \times G).x \pmod n$$$$s = k^{-1} (z + r \cdot d) \pmod n$$
Trong đó:
- $z$: Hash của tin nhắn.
- $d$: Khóa bí mật (Private Key).
- $n$: Bậc của đường cong (Order).

Vậy vấn đề là gì?. Hãy thử chuyện gì xảy ra nếu ta tìm được hai tin nhắn khác nhau ($z_1, z_2$) được ký bởi cùng một $k$
Tin nhắn 1:
$$s_1 \cdot k \equiv z_1 + r \cdot d \pmod n$$
Tin nhắn 2:
$$s_2 \cdot k \equiv z_2 + r \cdot d \pmod n$$
Giờ ta rút $k$ ra:
$$k \equiv s_1^{-1} \cdot (z_1 + r \cdot d) \pmod n$$
và
$$k \equiv s_2^{-1} \cdot (z_2 + r \cdot d) \pmod n$$
Vậy thì:
$$s_1^{-1} \cdot (z_1 + r \cdot d) \equiv s_2^{-1} \cdot (z_2 + r \cdot d) \pmod n$$
$$s_2 \cdot (z_1 + r \cdot d) \equiv s_1 \cdot (z_2 + r \cdot d) \pmod n$$
$$s_2 \cdot z_1 + s_2 \cdot r \cdot d \equiv s_1 \cdot z_2 + s_1 \cdot r \cdot d \pmod n$$
$$s_2 \cdot z_1 - s_1 \cdot z_2 \equiv s_1 \cdot r \cdot d - s_2 \cdot r \cdot d \pmod n$$
$$s_2 \cdot z_1 - s_1 \cdot z_2 \equiv d \cdot r \cdot (s_1 - s_2) \pmod n$$
Bùm, ta đã tìm được $d$:

$$d \equiv \frac{s_2 \cdot z_1 - s_1 \cdot z_2}{r \cdot (s_1 - s_2)} \pmod n$$
Rồi vậy ta có cách tìm được $d$ khi gửi 2 $k$ giống nhau, nhưng $k$ được tính như thế nào
Phân tích code:

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(b64decode(nonce),secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

À vậy là $k$ dựa trên nonce mà ta nhập vào, vậy ta nhập 2 nonce giống nhau là được nhỉ
Nhưng challenge đã ngăn chặn chúng ta làm việc đó:

 if len(nonces) > 0 : 

                    for i in nonces :
                        if nonce in i or i in nonce:
                            print('Nope')
                            exit()

Vậy ta không nhập 2 nonce giống nhau được rồi
Nhưng chúng ta có thể lợi dụng một tính chất thú vị của hàm `base64.b64decode()`, hàm này nó sẽ **bỏ qua các ký tự không thuộc bảng mã Base64 (như khoảng trắng, xuống dòng)**
Ví dụ:
- `AAAA` thì decode nó ra `\x00\x00\x00`
- "AA AA" vẫn ra `\x00\x00\x00`
Rồi vậy ta đã lách luật thành công, dù nhập 2 nonce khác nhau nhưng ra cùng $k$ giống nhau
Vậy giờ ta cứ gửi 2 messages tùy ý, chỉ cần gửi 2 nonce lách luật như vậy, sau đó ta đi tính $d$, rồi gửi $d$ lên sever để nhận flag.

solve.py

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


p = process(["python", "chall.py"])

n = generator_256.order()

def get_signature(msg_b64, nonce_b64):
    p.recvuntil(b"Option : ")
    p.sendline(b"1")
    p.sendlineafter(b"message: ", msg_b64)
    p.sendlineafter(b"nonce: ", nonce_b64)
    resp = p.recvuntil(b"}")
    sig_dict = ast.literal_eval(resp.decode().strip())
    return int(sig_dict['r'], 16), int(sig_dict['s'], 16)


msg1 = b"DQ=="
nonce1 = b"AAAA" 
r1, s1 = get_signature(msg1, nonce1)

msg2 = b"DQcute=="
nonce2 = b"AA AA"
r2, s2 = get_signature(msg2, nonce2)

z1 = bytes_to_long(sha256(b64decode(msg1)).digest())
z2 = bytes_to_long(sha256(b64decode(msg2)).digest())

d = (((s1 * z2 - s2 * z1) % n) * (inverse((r1 * (s2 - s1)) % n, n))) % n


p.recvuntil(b"Option : ")
p.sendline(b"2")
p.sendlineafter(b"Private key : ", str(d).encode())

p.interactive()

::: spoiler Flag
KCSC{https://youtu.be/IzSYlr3VI1A}
:::
# Adult RSA

from Crypto.Util.number import *
import random
from secret import flag 

def gen_prime_rsa_p(nbits,e):
    while True:
        p = getPrime(nbits)
        if (p-1) % e == 0 and (p-1) % e**2 != 0:
            return p 

def gen_prime_rsa_q_z(nbits,e):
    while True:
        q = getPrime(nbits)
        if (q-1) % e != 0:
            return q 



e = 71
nbits = 64
p = gen_prime_rsa_p(256,e)
q = gen_prime_rsa_q_z(256,e)
z = gen_prime_rsa_q_z(256,e)
N = p * q * z


cipher = pow(bytes_to_long(flag), e, N)
x_random = []
x_result = []


for i in range(16):

    x = random.getrandbits(nbits)
    x_random.append(x)
    r = (q * x + z) % p  + random.randint(-2**32 + 1, 2**32)
    x_result.append(r)

a = (q-1)*(z-1)

d = inverse(e,a) 

print(long_to_bytes(pow(cipher,d,q*z)))

print(f'{x_random = }')
print(f'{x_result = }')
print(f"n = {N}")
print(f"p = {p}")
print(f"e = {e}")
print(f"C = {cipher}")

# x_random = [8643291332705198277, 17174614327362281726, 15517127706104132406, 9995477138511354306, 13056359184422157742, 7587016065185392284, 9920196087957288832, 4952856612988664544, 5400203381242752352, 16576729197299286985, 3973228161970229092, 1766627902400563838, 11348902064522144204, 16275357069408139519, 13702106965727543557, 4703399577523548417]
# x_result = [104769762949973515003186398069307441812047659769870223704600152813608642465924, 19240036943626126268867100328802805554153842788101708322529920247684682326111, 12872167480066142198055220003342391658416424740122512375229591959608296202631, 45245681900612751628524950620689624320206486801875865224835291789607248539141, 89174302840170283311531755935367036323146884100751346415988392131733295994022, 93558762831267599991524549218850060166785794865518267150157882124236756776229, 35334857205000198530989566036180247858527073565848690385874491796896655487832, 48582907639890216074557704293111289752104462411913600690382605831588458449292, 2016756199999958140783087348943917358308350962876495006453605085056481261346, 27769515582048691173698542555157381741265320283349469274846441026970926086274, 2509804360455560909035722789851300261852699570010154269398229008039953894020, 52048088979121750160075716905451109678634402978216783809835560945560954214895, 98161921782416668850151589231441352837262317193409143953232303925375964152202, 103908881452290364956007856502624631194187804940528712150623661515672853059255, 2441158614263009247426256779029825410595899337637342611525937734371617282258, 2459264866325694410614372765423053147832404738353976083506075134734276029099]
# n = 609105711554562987480385746218512529022252330552247630394781811768956681666381155442184196776297236078736773335862755588901545589600370539269710342801857148190223818733295279783258645163683394386497845747001139631409101743225988501
# p = 106426942433971470657898579372762947809790292384453810719107482848817482215411
# e = 71
# C = 110684508716853838208041576724352556783516725281742611028522115035500008314350404208335808630949265486412535388862401924455351546168798205658188240618862927337867580712334009503358702013924669467798852160329991510793706397540234731

Đây là một bài toán liên quan đến Lattice, cụ thể là giải quyết bài toán Hidden Number Problem (HNP) (và ở một góc độ nào đó, mình thấy nó khá giống Knapsack/CVP).
Ta phân thích bài toán:
Ta có modulus $N = p.q. z$ với $p, q, z$ là các số nguyên tố 256-bit. Trong đó $p$ là số nguyên tố đặc biệt sao cho $(p-1) \vdots e$.
Và chúng ta biết $N, p, e$ và $C$.

Vậy thì mục tiêu là tìm $q$ hoặc $z$ để giải mã.

Ta có 16 cặp giá trị $(x_i, r_i)$ được tạo ra bởi:$$r_i = ((q \cdot x_i + z) \pmod p) + \text{e}_i$$Trong đó $x_i$ là số ngẫu nhiên 64-bit, và $\text{e}_i$ là một số nguyên ngẫu nhiên trong khoảng $[-2^{32}+1, 2^{32}]$.
Ta có thể viết lại phương trình dưới dạng:$$r_i - \epsilon_i \equiv q \cdot x_i + z \pmod p$$
Thay vì giải hệ phương trình chứa cả $q$ và $z$, ta sẽ tìm cách loại bỏ $z$
Ta sẽ xét hai trạng thái liên tiếp nhau như sau:
$$r_i \approx qx_i + z \pmod p$$

$$r_{i+1} \approx qx_{i+1} + z \pmod p$$
(bởi vì $\epsilon_i$ khá nhỏ, ta có thể bỏ qua nó)
Trừ cho nhau ta được:
$$(r_i - r_{i+1}) \approx q(x_i - x_{i+1}) \pmod p$$
Đặt $\Delta r_i = r_i - r_{i+1}$, $\Delta x_i = x_i - x_{i+1}$ và $\Delta e_i = e_i - e_{i+1}$.
Ta có phương trình mới:$$\Delta r_i - q .\Delta x_i - \Delta e_i \equiv 0 \pmod p$$
$$ q \cdot \Delta x_i - \Delta r_i \equiv -\Delta e_i \pmod p$$
Quá ngon, phương trình chỉ còn ẩn $z$, và kích thước ma trận giảm đi một nửa (chỉ cần dùng 8 cặp hiệu số thay vì 16), giúp LLL chạy cực nhanh.

Chúng ta muốn tìm vector ngắn chứa các sai số $\Delta e_i$. Ta dựng một Lattice để tìm vector đích:$$\vec{v} = (\Delta e_0, \Delta e_1, \dots, \Delta e_7, \text{val}_q, \text{val}_{\text{const}})$$
Vấn đề nảy sinh:
- Sai số $\Delta e_i \approx 2^{33}$ (do hiệu của 2 số 32-bit).
- Biến $q \approx 2^{256}$ (rất lớn).

Nếu ta đưa trực tiếp $q$ vào ma trận, vector kết quả sẽ có thành phần chứa $q$ rất lớn, làm mất cân bằng Lattice, khiến LLL thất bại.

Vậy giải pháp là: Ta nhân cột tương ứng với $q$ một hệ số tỷ lệ (scaling factor) là $W = \frac{B}{p}$ (với $B = 2^{32}$).
Khi đó, thành phần của vector tại cột này sẽ là:$$q \times W = q \times \frac{B}{p} \approx p \times \frac{B}{p} = B$$Lúc này, độ lớn của thành phần chứa $q$ đã được kéo xuống ngang bằng với độ lớn của sai số ($\approx B$). Lattice trở nên cân bằng.
Vậy ma trận của chúng ta là:
$$M = \begin{pmatrix}
p & 0 & \dots & 0 & 0 & 0 \\
0 & p & \dots & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & \dots & p & 0 & 0 \\
\Delta x_0 & \Delta x_1 & \dots & \Delta x_7 & \frac{B}{p} & 0 \\
-\Delta r_0 & -\Delta r_1 & \dots & -\Delta r_7 & 0 & B
\end{pmatrix}$$
Kết quả sẽ là vector:$$\vec{V} = (q\Delta x - \Delta r \pmod p, \dots, q \frac{B}{p}, B)$$$$\vec{V} = (-\Delta e_0, \dots, -\Delta e_7, \approx B, B)$$
Sau khi tìm được $q$, ta tính $z = N / (pq)$.
Vấn đề tiếp theo là giải mã RSA với $e=71$.
Trong RSA thông thường thì $gcd(e, p -1 ) = 1$, bài này lại chọn $e \mid (p-1)$, nên là ta phải giải phương trình $x^e \equiv c \pmod p$ để tìm tập hợp 71 nghiệm $\{m_p^{(1)}, \dots, m_p^{(71)}\}$.

solve.sage:

from Crypto.Util.number import long_to_bytes, inverse
from sage.all import *


x_random = [8643291332705198277, 17174614327362281726, 15517127706104132406, 9995477138511354306, 13056359184422157742, 7587016065185392284, 9920196087957288832, 4952856612988664544, 5400203381242752352, 16576729197299286985, 3973228161970229092, 1766627902400563838, 11348902064522144204, 16275357069408139519, 13702106965727543557, 4703399577523548417]
x_result = [104769762949973515003186398069307441812047659769870223704600152813608642465924, 19240036943626126268867100328802805554153842788101708322529920247684682326111, 12872167480066142198055220003342391658416424740122512375229591959608296202631, 45245681900612751628524950620689624320206486801875865224835291789607248539141, 89174302840170283311531755935367036323146884100751346415988392131733295994022, 93558762831267599991524549218850060166785794865518267150157882124236756776229, 35334857205000198530989566036180247858527073565848690385874491796896655487832, 48582907639890216074557704293111289752104462411913600690382605831588458449292, 2016756199999958140783087348943917358308350962876495006453605085056481261346, 27769515582048691173698542555157381741265320283349469274846441026970926086274, 2509804360455560909035722789851300261852699570010154269398229008039953894020, 52048088979121750160075716905451109678634402978216783809835560945560954214895, 98161921782416668850151589231441352837262317193409143953232303925375964152202, 103908881452290364956007856502624631194187804940528712150623661515672853059255, 2441158614263009247426256779029825410595899337637342611525937734371617282258, 2459264866325694410614372765423053147832404738353976083506075134734276029099]
n = 609105711554562987480385746218512529022252330552247630394781811768956681666381155442184196776297236078736773335862755588901545589600370539269710342801857148190223818733295279783258645163683394386497845747001139631409101743225988501
p = 106426942433971470657898579372762947809790292384453810719107482848817482215411
e = 71
C = 110684508716853838208041576724352556783516725281742611028522115035500008314350404208335808630949265486412535388862401924455351546168798205658188240618862927337867580712334009503358702013924669467798852160329991510793706397540234731


dim = len(x_random) - 1  
diff_x = [x_random[i] - x_random[0] for i in range(1, len(x_random))]
diff_r = [x_result[i] - x_result[0] for i in range(1, len(x_result))]


K = 2**33 
M = Matrix(ZZ, dim + 2, dim + 1)


for i in range(dim):
    M[i, i] = p                     
    M[dim, i] = -diff_x[i]          
    M[dim + 1, i] = diff_r[i]       

M[dim + 1, dim] = K                

L = M.LLL()


diff_errors = []
for row in L:
    if abs(row[-1]) == K:
        sign = 1 if row[-1] == K else -1
        diff_errors = [sign * val for val in row[:-1]]
        break


R_ring = Zmod(p)
q_c = int((R_ring(diff_r[0]) - R_ring(diff_errors[0])) / (R_ring(diff_x[0])))


real_q = 0
for k in range(200):
    test_q = q_c + k * p
    if test_q > 1 and n % test_q == 0:
        real_q = test_q
        break


z = n // (p * real_q)
d_q = inverse_mod(e, real_q - 1)
m_q = power_mod(C, d_q, real_q)
d_z = inverse_mod(e, z - 1)
m_z = power_mod(C, d_z, z)



Fp = GF(p)
c_poly = Fp(C)
m_p_c = c_poly.nth_root(e, all=True)

for m_p in m_p_c:
    val = crt([Integer(m_p), m_q, m_z], [p, real_q, z])
    flag = long_to_bytes(val)
    if b"KCSC" in flag:
        print(flag.decode())

::: spoiler Flag
KCSC{U_Should_Choose_e_reasonable}
:::