Bài 6: Mật Mã Bất Đối Xứng Hiện Đại (Phần 1)

1. Ôn tập nhanh: Stream Cipher & AES

Stream Cipher

Mã hóa luồng hoạt động theo nguyên tắc XOR đơn giản:

C = M ⊕ K      # Mã hóa
M = C ⊕ K      # Giải mã (vì C ⊕ K = M ⊕ K ⊕ K = M)

Vấn đề cốt lõi: Làm sao hai bên thỏa thuận được khóa bí mật một cách an toàn mà không cần gặp nhau trước?

AES (Advanced Encryption Standard)

AES là mã khối (block cipher) với 4 phép biến đổi mỗi vòng:

2. Tại sao cần Mật Mã Bất Đối Xứng?

Mật mã đối xứng (AES, DES…) gặp hai vấn đề lớn:

2.1 Vấn đề phân phối khóa (Key Distribution)

Với n người dùng, cần n(n-1)/2 cặp khóa riêng — không thể mở rộng được.

2.2 Vấn đề chữ ký số (Digital Signatures)

Mật mã đối xứng không thể chứng minh ai là người gửi thật sự, vì cả hai bên đều biết cùng một khóa.

3. Nguyên lý Hệ Mật Mã Khóa Công Khai

3.1 Thành phần của hệ thống

Một hệ mật mã khóa công khai gồm 6 thành phần:

1. Plaintext (Bản rõ) — dữ liệu đầu vào
2. Thuật toán mã hóa — biến đổi plaintext
3. Khóa công khai (Public Key - PU) — dùng để mã hóa hoặc xác minh
4. Khóa riêng tư (Private Key - PR) — dùng để giải mã hoặc ký
5. Ciphertext (Bản mã) — kết quả đầu ra
6. Thuật toán giải mã — khôi phục plaintext từ ciphertext + khóa

3.2 Ba chế độ sử dụng

3.3 So sánh các thuật toán

4. Yêu cầu của Hệ Mật Mã Khóa Công Khai

4.1 Các điều kiện bắt buộc

1. Dễ tạo cặp khóa (PU, PR)
2. Biết PU và M → dễ tính C
3. Biết PR và C → dễ tính M
4. Biết PU → KHÔNG thể tìm ra PR (tính chất quan trọng nhất)
5. Biết PU và C → không thể tìm ra M
6. Hai khóa có thể dùng theo thứ tự bất kỳ

4.2 Hàm một chiều có cửa hậu (Trapdoor One-Way Function)

Đây là nền tảng toán học của mọi hệ mật khóa công khai:

Hàm thông thường:    Y = f(X)       → Dễ tính
Hàm một chiều:       X = f⁻¹(Y)    → Không thể tính ngược
Có cửa hậu k:        X = fk⁻¹(Y)   → Dễ tính nếu biết k

5. RSA — Rivest-Shamir-Adleman

5.1 Lịch sử & Tổng quan

• Phát triển năm 1977 tại MIT bởi Ron Rivest, Adi Shamir và Len Adleman
• Thuật toán khóa công khai phổ biến nhất hiện nay
• Plaintext và ciphertext là các số nguyên trong khoảng [0, n-1]
• Kích thước n điển hình: 3072 bits

5.2 Cơ sở toán học: Bài toán phân tích nhân tử nguyên tố

Cho: N = p × q  (p, q là số nguyên tố lớn)
Bài toán: Tìm lại p và q khi chỉ biết N

Không có thuật toán cổ điển nào giải được bài toán này trong thời gian đa thức (polynomial time) với đầu vào kích thước n-bit.

5.3 Sinh khóa RSA

5.4 Mã hóa và Giải mã

# Mã hóa (Bob dùng Public Key của Alice)
C = M^e mod n

# Giải mã (Alice dùng Private Key của mình)
M = C^d mod n

5.5 Tại sao hoạt động đúng?

C^d mod n = (M^e)^d mod n = M^(e·d) mod n

Vì: e · d ≡ 1 (mod φ(n))
→  e · d = 1 + k·φ(n)  với k nguyên nào đó

Theo Định lý Euler:
    M^φ(n) ≡ 1 (mod n)  khi gcd(M, n) = 1

Suy ra:
    M^(e·d) = M^(1 + k·φ(n)) = M · (M^φ(n))^k ≡ M · 1^k ≡ M (mod n)

5.6 Ví dụ số nhỏ

Chọn: p = 17, q = 11
→ n = 17 × 11 = 187
→ φ(n) = 16 × 10 = 160

Chọn e = 7  (vì gcd(7, 160) = 1)
→ d = 7⁻¹ mod 160 = 23  (vì 7 × 23 = 161 = 1 + 160)

Public Key:  PU = {7, 187}
Private Key: PR = {23, 187}

Mã hóa M = 88:
    C = 88^7 mod 187 = 11

Giải mã C = 11:
    M = 11^23 mod 187 = 88  ✅

6. Lũy thừa Modular Nhanh (Fast Modular Exponentiation)

6.1 Vấn đề

RSA cần tính M^e mod n với e có thể lên đến hàng nghìn bit — không thể nhân trực tiếp.

6.2 Thuật toán Square-and-Multiply

Ý tưởng: biểu diễn số mũ dưới dạng nhị phân và tính từng bước.

def fast_mod_exp(a, b, n):
    """Tính a^b mod n"""
    # Biểu diễn b dưới dạng nhị phân: b = b_k b_{k-1} ... b_0
    c = 0
    f = 1
    for bit in bin(b)[2:]:  # duyệt từ bit cao nhất
        c = 2 * c
        f = (f * f) % n
        if bit == '1':
            c = c + 1
            f = (f * a) % n
    return f

6.3 Ví dụ minh họa: 7^560 mod 561

560 = 1000110000 trong nhị phân

Kết quả: 7^560 mod 561 = 1

7. Hiệu quả trong thực tế

7.1 Khóa công khai (e)

Giá trị e phổ biến nhất là 65537 = 2^16 + 1 vì:

• Chỉ có 2 bit 1 trong biểu diễn nhị phân → ít phép nhân nhất
• Đủ lớn để tránh tấn công đơn giản
• e = 3 hoặc e = 17 cũng được dùng nhưng kém an toàn hơn

7.2 Khóa riêng (d) — Chinese Remainder Theorem

Dùng CRT (Định lý Phần dư Trung Hoa) để tăng tốc giải mã ~4 lần:

Thay vì tính: M = C^d mod n

Tính hai giá trị nhỏ hơn:
    M_p = C^(d mod p-1) mod p
    M_q = C^(d mod q-1) mod q

Rồi kết hợp M_p, M_q bằng CRT để ra M

8. Bảo mật của RSA — Các dạng tấn công

8.1 Brute Force

Thử toàn bộ khóa riêng tư. Đối phó: dùng khóa đủ lớn (≥ 2048 bit hiện tại, 3072 bit khuyến nghị).

8.2 Mathematical Attack — Phân tích nhân tử

Nếu kẻ tấn công phân tích được n = p × q → tính được φ(n) → tính được d.

Biết: n, e (public)
Mục tiêu: tìm d
Cách: n = p × q → φ(n) = (p-1)(q-1) → d = e⁻¹ mod φ(n)

Đây là lý do kích thước khóa RSA phải rất lớn.

8.3 Timing Attack ⚡

Biện pháp đối phó:

8.4 Fault-Based Attack

Cố tình gây lỗi phần cứng (giảm điện áp) trong quá trình tạo chữ ký số → chữ ký bị lỗi → phân tích để tìm khóa riêng.

8.5 Chosen Ciphertext Attack (CCA)

Kẻ tấn công chọn một số ciphertext và lấy được plaintext tương ứng → khai thác tính chất algebraic của RSA.

Ví dụ tấn công multiplicative:

RSA thuần: nếu biết D(C1) = M1 và D(C2) = M2
→ D(C1 · C2 mod n) = M1 · M2 mod n

Đối phó: OAEP (Optimal Asymmetric Encryption Padding)

OAEP thêm tính ngẫu nhiên vào quá trình mã hóa → cùng một M sẽ cho C khác nhau mỗi lần.

9. Sinh Số Nguyên Tố Lớn

Quy trình chọn số nguyên tố p, q

1. Chọn ngẫu nhiên một số lẻ n
2. Chọn ngẫu nhiên a < n
3. Thực hiện kiểm tra tính nguyên tố xác suất (Miller-Rabin) với tham số a
   - Nếu n không qua → quay lại bước 1
4. Nếu n đã qua đủ số lần kiểm tra → chấp nhận n là số nguyên tố
   - Nếu chưa đủ → quay lại bước 2

10. Câu hỏi từ Slide & Trả lời

11. Các Quan Niệm Sai về Mật Mã Khóa Công Khai

12. Thuật ngữ Quan trọng