I. Kiến Thức Cơ Bản Về Môđun

1. Định Nghĩa

Toán học môđun, hay số học môđun, là lĩnh vực nghiên cứu các phép toán với số nguyên. Đây là một phần quan trọng trong mật mã học, đóng vai trò then chốt trong nhiều phương pháp mã hóa, đặc biệt là mã hóa RSA. Trong số học môđun, hai số nguyên a và b được xem là đồng dư theo môđun n nếu chúng có cùng số dư khi chia cho n, ký hiệu là:

a ≡ b (mod n)

Ví dụ:

• 19 ≡ 8 (mod 11)
• 25 ≡ 11 (mod 7)
• 8 ≡ -2 (mod 5)

2. Tính Chất và Phép Toán Trên Môđun

Số học môđun có các tính chất tương tự như số học thông thường:

• Tính Phản Xạ: a ≡ a (mod n)
• Tính Đối Xứng: a ≡ b (mod n) ↔ b ≡ a (mod n)
• Tính Bắc Cầu: Nếu a ≡ b (mod n) và b ≡ c (mod n) thì a ≡ c (mod n)
• Phép Cộng và Trừ: Nếu a ≡ b (mod n) thì a ± c ≡ b ± c (mod n)
• Phép Nhân: Nếu a ≡ b (mod n), thì a × k ≡ b × k (mod n) với k ≠ 0
• Lũy Thừa: Nếu a ≡ b (mod n), thì a^k ≡ b^k (mod n) với k là số nguyên dương.
• Đa Thức với Hệ Số Nguyên: Nếu a ≡ b (mod n), thì P(a) ≡ P(b) (mod n) cho mọi đa thức P.

3. Cài Đặt Trong Python

Để tìm số dư của phép chia a cho b, ta dùng toán tử %:

Ví dụ, để tìm số dư của lũy thừa a^b cho n, Python hỗ trợ hàm pow(base, exponent, modulus). Ví dụ để tính 100^13 ≡ x (mod 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 liên quan đến việc tìm nghiệm x cho phương trình:

x² ≡ a (mod n)

Ví dụ, x = 11 là một nghiệm của phương trình x² ≡ 5 (mod 29) vì 121 ≡ 5 (mod 29). Nếu x là nghiệm, thì -x cũng là một nghiệm.

Một phương pháp đơn giản để tìm nghiệm là sử dụng phép duyệt từ 0 đến n-1:

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

Nếu x² ≡ a (mod n) có nghiệm, ta nói a là số chính phương môđun n.

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 môđun n hay không, kết quả trả về là 1 nếu đúng, và -1 nếu không.

2. Bài Toán Thặng Dư Bình Phương Với Môđun Số Nguyên Tố

Chúng ta thường xét bài toán thặng dư bình phương với môđun là số nguyên tố p. Định lý nói rằng, nếu p là số nguyên tố lẻ, thì có đúng (p-1)/2 số chính phương môđun p. Thật vậy, với a là thặng dư bình phương, phương trình x² ≡ a (mod p) sẽ có hai nghiệm khác nhau trong 1, 2, ..., p-1.

Tiêu chuẩn Euler cũng cho biết rằng, nếu GCD(a, p) = 1, a là số chính phương môđun p khi và chỉ khi:

a^(p-1)/2 ≡ 1 (mod p)

Kiểm tra đơn giản:

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

III. Ký Hiệu Legendre

1. Lý Thuyết

Ký hiệu Legendre (a/p) dùng để xác định một số a có phải là số chính phương môđun p hay không, với p là số nguyên tố lẻ và a là số nguyên không chia hết cho p:

• (a/p) = 1 nếu a là số chính phương môđun p
• (a/p) = -1 nếu a không là số chính phương môđun p

2. Một Số Tính Chất

• Nếu a ≡ b (mod p), thì (a/p) = (b/p)
• (a/p)(b/p) = (ab/p)
• (a²/p) = 1

IV. Thử Thách CTF

1. Thử Thách 1 - Dấu Hiệu Adrien

Hàm encrypt_flag() mã hóa flag bằng cách:

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

Chúng ta phân tích và sử dụng kiến thức về số chính phương môđun để giải mã flag.

2. Thử Thách 2

File chall.py sinh bản mã và lưu vào output.txt. Phân tích source code để tìm ra flag.

Tài Liệu Tham Khảo

• Python pow() Function
• GMPY2 Documentation
• Thặng Dư Bình Phương
  source: viblo