I. Một số kiến thức cơ bản về module

1. Định nghĩa

Trong toán học, số học mô đun là một hệ thống số học dành cho số nguyên. Modular math đóng vai trò quan trọng trong mật mã học, giữa chúng tồn tại sự liên hệ mật thiết. Có thể coi phần lớn lý thuyết mật mã được xây dựng dựa trên cơ sở của số học module trong toán học, tiêu biểu có thể kể đến hệ mã hóa RSA làm việc trên các phép toán module.

Khái niệm module còn được gọi là đồng dư thức, xét tới hai số nguyên $a$ và $b$ có cùng số dư khi chia cho số nguyên $n$. Khi đó ta nói "$a$ đồng dư với $b$ theo mô đun $n$", ký hiệu:

$$a \equiv b \pmod {n}$$

Một số ví dụ:

$$19 \equiv 8 \pmod {11}\\ 25 \equiv 11 \pmod {7}\\ 8 \equiv -2 \pmod {5}\\$$

2. Tính chất và các phép toán trên module

Số học module cũng có các tính chất tương tự như phép toán thông thường:

Tính phản xạ:

$$a \equiv a \pmod {n}\\$$

Tính đối xứng:

$$a \equiv b \pmod {n} \leftrightarrow b \equiv a \pmod {n}$$

Tính bắc cầu:

$$\begin{cases} a \equiv b \pmod {n}\\ b \equiv c \pmod {n}\\ \end{cases} \rightarrow a \equiv c \pmod {n}$$

Phép cộng, trừ:

$$a \equiv b \pmod {n}\rightarrow a\pm c \equiv b\pm c \pmod {n}$$

Phép nhân:

$$a \equiv b \pmod {n}\rightarrow \begin{cases} a\times k \equiv b\times k \pmod {n}\text{ với }k\ne 0, k\in Z\\ a\times k \equiv b\times k \pmod {n\times k}\text{ với }k\in Z\\ \end{cases}$$

Lũy thừa:

$$a \equiv b \pmod {n}\rightarrow a^k \equiv b^k \pmod {n}\text{ với }k\in Z^+$$

Đa thức hệ số nguyên $P(x)$:

$$a \equiv b \pmod {n}\rightarrow P(a) \equiv P(b) \pmod {n}$$

3. Cài đặt trong Python

Để tìm số dư của phép chia $a$ cho $b$, chúng ta có thể sử dụng toán tử %:

Để tìm số dư của lũy thừa $a^b$ cho $n$, Python hỗ trợ hàm pow(base, exponent, modulus) (tham số modulus nếu không sử dụng thì hàm này chỉ đơn giản là tính phép tính lũy thừa). Ví dụ cần tìm $x$ trong phép tính $100^{13} \equiv x \pmod {31}$

II. Bài toán thặng dư bình phương (Quadratic Residues)

1. Lý thuyết

Bài toán thặng dư bình phương xoay quanh việc tìm nghiệm $x$ trong phương trình module:

$$x^2 \equiv a \pmod {n}$$

Ví dụ, $x=11$ là một nghiệm của phương trình $x^2 \equiv 5 \pmod {29}$ vì $121 \equiv 5 \pmod {29}$.

Dễ thấy một tính chất cơ bản: Nếu $x$ là nghiệm của phương trình thăng dư bình phương thì $-x$ cũng là một nghiệm thỏa mãn, vì $x^2 = (-x)^2$

Một ý tưởng đơn giản để tìm ra một nghiệm thỏa mãn phương trình là thực hiện vét cạn giá trị từ $0$ tới $n-1$, cài đặt như sau:

def brute_quadratic_residues(a, n):
	for x in range(n):
		if pow(x, 2, n) == a:
			return x

Trong trường hợp phương trình $x^2 \equiv a \pmod {n}$ có nghiệm, ta nói $a$ là số chính phương module $n$.

Chúng ta có thể sử dụng hàm gmpy2.jacobi(a, n) trong Python để kiểm tra số $a$ có phải là số chính phương module $n$ hay không, hàm trả về $1$ nếu đúng, ngược lại trả về $-1$. Ví dụ chương trình sau in ra các số chính phương module $11$ từ $1$ tới $10$:

def list_modular_square_num(n):
	res = []
	for x in range(1, n):
		if gmpy2.jacobi(x, n) == 1:
			res.append(x)
	return res

2. Bài toán thặng dư bình phương trên module số nguyên tố

Chúng ta thường xem xét bài toán thặng dư bình phương với module là số nguyên tố $p$. Một định lý thường được sử dụng: Nếu $p$ là một số nguyên tố lẻ thì trong các số $1,2,3,...,p-1$ có đúng $\frac{p-1}{2}$ số chính phương module $p$. Có thể chứng minh đơn giản:

Xét $a$ là một thặng dư bình phương module $p$, phương trình $x^2 \equiv a \pmod {p}$ có đúng hai nghiệm (khác module) trong $1,2,...,p-1$. Như vậy mỗi số $a$ sẽ tương ứng với hai số (là nghiệm phương trình thặng dư) trong $p-1$ số $1,2,...,p-1$. Suy ra số số $a$ như vậy là $\frac{p-1}{2}$, hay có đúng $\frac{p-1}{2}$ số chính phương module $p$.

Ngoài ra chúng ta có tiêu chuẩn Euler: Nếu $p$ là một số nguyên tố lẻ và $GCD(a, p)=1$, $a$ là số chính phương module $p$ khi và chỉ khi:

$$a^{\frac{p-1}{2}} \equiv 1 \pmod {p}$$

Chương trình kiểm tra đơn giản:

def check(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1

III. Legendre

1. Lý thuyết

Legendre thực chất là một ký hiệu bổ trợ cho thặng dư bình phương. Với $p$ là số nguyên tố lẻ và $a$ là số nguyên không chia hết cho $p$, ký hiệu Legendre $\left(\frac{a}{p}\right)$ được định nghĩa như sau:

$$\begin{cases} \left(\frac{a}{p}\right) = 1\text{ nếu }a\text{ là số chính phương module }p\\ \left(\frac{a}{p}\right) = -1\text{ nếu }a\text{ không là số chính phương module }p\\ \end{cases}$$

Ví dụ:

$$\left(\frac{1}{11}\right) = \left(\frac{3}{11}\right) = \left(\frac{4}{11}\right) = \left(\frac{5}{11}\right) = \left(\frac{9}{11}\right) = 1\\ \left(\frac{2}{11}\right) = \left(\frac{6}{11}\right) = \left(\frac{7}{11}\right) = \left(\frac{8}{11}\right) = \left(\frac{10}{11}\right) = -1$$

2. Một số tính chất

Cho $p$ là số nguyên tố lẻ và $a$, $b$ là các số nguyên không chia hết cho $p$, ta có:

$(i)\text{ Nếu }a\equiv b \pmod {p}\text{ thì }\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$

$(ii) \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$

$(iii) \left(\frac{a^2}{p}\right)=1$

IV. Challenge CTF

1. Challenge 1 - Adrien's Signs

File source.py có hàm encrypt_flag() thực hiện mã hóa flag:

def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

Hàm không quá phức tạp, trước hết, flag được chuyển sang dạng nhị phân, sau đó duyệt qua từng phần tử của chuỗi nhị phân này, nếu gặp bit $1$ thì in ra $n$, nếu gặp bit $0$ thì in ra $p-n$, trong đó n = pow(a, e, p) với $e$ là một số được sinh ngẫu nhiên trong đoạn $[1;p]$ trong mỗi lượt duyệt. Output được hiển thị trong file output.txt như sau:

Chúng ta cần xem xét điểm đặc biệt của các số $n$ được in ra. Chú ý cách tính n = pow(a, e, p) hoặc p - pow(a, e, p) (với $a,p$ được cho trước), chúng ta cố gắng suy nghĩ tới các tính chất liên quan tới kết quả của $a^x$ trong module $p$ (là số nguyên tố). Từ đó không khó để phát hiện ra rằng $a$ là một số chính phương module $p$ theo tiêu chuẩn Euler:

Lúc này, dễ dàng nhận ra pow(a, e, p) cũng là một số chính phương module $p$, theo tiêu chuẩn Euler lại có pow(pow(a, e, p), (p - 1) // 2, p) = 1. Như vậy, khi $b=1$ thì $n$ là một số chính phương module $p$. Trường hợp ngược lại thì $n$ không là số chính phương module $p$, tức $b=0$.

Bởi vậy, chúng ta chỉ cần duyệt qua từng phần tử của mảng trong file output, kiểm tra phần tử đó có phải số chính phương module $p$ hay không, từ đó tìm được từng ký tự nhị phân của flag. Lời giải tham khảo:

from Crypto.Util.number import long_to_bytes

p = 1007621497415251
ct = [...]
flag = ''

for n in ct:
    if pow(n, (p - 1) // 2, p) == 1:
        flag = flag + '1'
    else:
        flag = flag + '0'

flag = int(flag, 2)
flag = long_to_bytes(flag)

print(flag)

2. Challenge 2

2.1. Đề bài

Bạn đọc có thể tải xuống source code tại link. Challenge bao gồm hai file chall.py và output.txt. Trước khi đi tới phần phân tích đề bài, bạn đọc có thể thử dành thời gian đọc hiểu source code và tìm ra flag nhé!

File chall.py bao gồm một số hàm và sinh bản mã tại file output.txt chứa dãy chữ số lớn:

2.2. Phân tích source code

Trước hết chúng ta sẽ phân tích từng hàm được định nghĩa.

def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1

Hàm gmc() thực hiện kiểm tra số $a$ có phải là số chính phương module $p$ hay không (từ cách sử dụng hàm pow() có thể thấy đây chính là tiêu chuẩn Euler).

def gen_key():
    [gp,gq] = [getPrime(512) for i in range(2)]
    gN = gp * gq
    return gN, gq, gp

Hàm gen_key() sinh hai số nguyên tố gp, gq có độ dài $512$ bit và trả về cả số gN là tích của chúng (giống với số $N$ trong thuật toán RSA).

def gen_x(gq,gp):
    while True:
        x = getRandomNBitInteger(512)
        if gmc(x,gp) ^ gmc(x,gq) == -2:
            return x

Hàm gen_x() sinh ra số nguyên x ngẫu nhiên dài $512$ bit, điều kiện gmc(x,gp) ^ gmc(x,gq) == -2 cho thấy x chỉ có thể là số chính phương module gp hoặc gq (không xảy ra đồng thời).

def gen_y(gN):
    gy_list = []
    while len(gy_list) != F_LEN:
        ty = getRandomNBitInteger(768)
        if gcd(ty,gN) == 1:
            gy_list.append(ty)
    return gy_list

Hàm gen_y trả về một list gồm F_LEN số nguyên ngẫu nhiên ty thỏa mãn đồng thời:

• ty có độ dài $768$ bit.
• ty nguyên tố cùng nhay với gN.

if __name__ == '__main__':
    flag = bin(bytes_to_long(flag))[2:]
    F_LEN = len(flag)
    N, q, p = gen_key()
    x = gen_x(q, p)
    y_list = gen_y(N)
    ciphertext = []
 
    for i in range(F_LEN):
        tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N
        ciphertext.append(tc)
 
    with open('./output.txt','w') as f:
        f.write(str(N) + '\n')
        for i in range(F_LEN):
            f.write(str(ciphertext[i]) + '\n')

Cuối cùng là hàm main, flag ban đầu ở dạng byte được chuyển sang dạng nhị phân, F_LEN là độ dài của flag ở hệ nhị phân. List ciphertext gồm F_LEN số tc sinh bởi công thức pow(y_list[i],2) * pow(x,int(flag[i])) % N. Cuối cùng in ra file output.txt số N, và list ciphertext theo từng dòng.

2.3. Ý tưởng

Từ file output.txt chúng ta thu được số N, biết được giá trị của F_LEN và toàn bộ list ciphertext theo công thức pow(y_list[i],2) * pow(x,int(flag[i])) % N, đây là điểm then chốt của challenge.

Do flag ở hệ nhị phân, nên int(flag[i]) chỉ nhận giá trị $0$ hoặc $1$, từ đó pow(x,int(flag[i])) chỉ nhận giá trị $1$ hoặc $x$. Sử dụng ý tưởng số chính phương module $p$, ta suy luận:

• Khi vị trí $i$ của flag là $0$, thì ciphertext[i] = pow(y_list[i],2) % N là phép tính lấy số dư khi chia một số chính phương cho N, chính là một số chính phương module N (có nghiệm là y_list[i] theo module N).
• Khi vị trí $i$ của flag là $1$, do x chỉ có thể là số chính phương module $p$ hoặc module $q$, nên ciphertext[i] = pow(y_list[i],2) * x % N không là số chính phương module N. (*)

Chứng minh nhận xét (*): không mất tính tổng quát có thể coi $x$ là số chính phương module $p$, khi đó $x$ không là số chính phương module $q$, biểu diễn dưới dạng ký hiệu Legendre có:

$$\left(\frac{x}{p}\right)=1\text{ và }\left(\frac{x}{q}\right)=-1$$

Đặt pow(y_list[i],2)=y^2, giả sử ngược lại, $y^2x$ là số chính phương module $n$, suy ra $y^2x$ là số chính phương module $q$, hay $\left(\frac{y^2x}{q}\right)=1$.

Thực hiện biến đổi:

$$1=\left(\frac{y^2x}{q}\right)=\left(\frac{y^2}{q}\right)\left(\frac{x}{q}\right)=1.(-1)=-1$$

Mâu thuẫn, nên điều giả sử là sai. Do đó ciphertext[i] = pow(y_list[i],2) * x % N không là số chính phương module N.

Như vậy, chúng ta chỉ cần kiểm tra từng giá trị ciphertext[i] có phải số chính phương module N hay không bằng hàm gmpy2.jacobi(). Xin dành bạn đọc phần viết chương trình giải mã cho challenge.

Tài liệu tham khảo

• https://www.w3schools.com/python/ref_func_pow.asp
• https://manpages.ubuntu.com/manpages/impish/man3/gmpy2.3.html
• https://tailieukcblog.files.wordpress.com/2017/09/thang-du-binh-phuong1.pdf