Bài 8: Mật mã Bất đối xứng (Phần 3) — Elliptic Curve Cryptography

1. Ôn tập nhanh: Tại sao cần mật mã bất đối xứng?

2. Ôn tập RSA

2.1 Luồng hoạt động

flowchart LR A["Alice chọn p, q nguyên tố\nTính n = p×q\nTính φ(n) = (p-1)(q-1)\nChọn e: gcd(e, φ(n))=1\nTính d = e⁻¹ mod φ(n)"] --> B["Public Key PU = {e, n}\nPrivate Key PR = {d, n}"] B --> C["Bob mã hóa:\nC = Mᵉ mod n"] C --> D["Alice giải mã:\nM = Cᵈ mod n"]

2.2 Tại sao giải mã đúng?

Cần chứng minh: $C^d \mod n = M$

$$C^d = (M^e)^d = M^{ed} \mod n$$

Ta cần $ed \equiv 1 \pmod{\lambda(n)}$, trong đó:

Định lý Fermat nhỏ (với p nguyên tố): $a^{p-1} \equiv 1 \pmod{p}$
Định lý Carmichael: $\lambda(n) = \text{lcm}(p-1, q-1)$

Ví dụ cụ thể

Cho $n = 15 = 3 \times 5$:

$\varphi(15) = (3-1)(5-1) = 8$
$\lambda(15) = \text{lcm}(2, 4) = 4$

Với mọi $a$ thỏa $\gcd(a, 15) = 1$: $a^4 \mod 15 = 1$

a	a⁴ mod 15	a⁸ mod 15
1	1	1
2	1	1
4	1	1
7	1	1
11	1	1
13	1	1

2.3 Tối ưu hóa giải mã RSA bằng CRT

Thay vì tính $M = C^d \mod n$ trực tiếp (tốn kém với d lớn), ta dùng Chinese Remainder Theorem (CRT):

$$d_p = d \mod (p-1), \quad d_q = d \mod (q-1), \quad q_{inv} = q^{-1} \mod p$$

m₁ = C^(dp) mod p
m₂ = C^(dq) mod q
h  = q_inv × (m₁ - m₂) mod p
m  = m₂ + h × q

3. Mật mã ElGamal & Diffie-Hellman

3.1 ElGamal Cipher

Thiết lập: Chọn số nguyên tố $p$, generator $g$, khóa bí mật $x$, khóa công khai $h = g^x \mod p$.

Mã hóa thông điệp $m < p-1$:

Chọn số ngẫu nhiên $r \in_R [1, p-1]$
Tính $C_1 = g^r \mod p$
Tính $C_2 = m \cdot h^r \mod p = m \cdot g^{xr} \mod p$
Bản mã: $(C_1, C_2)$

Giải mã $(C_1, C_2)$ với khóa bí mật $x$:

$$\frac{C_2}{C_1^x} = \frac{m \cdot g^{xr}}{g^{rx}} = m$$

3.2 Diffie-Hellman Key Exchange (DHE)

sequenceDiagram participant Alice participant Bob Note over Alice,Bob: Công khai: p, g Alice->>Bob: gᵃ mod p (a bí mật) Bob->>Alice: gᵇ mod p (b bí mật) Note over Alice: K = (gᵇ)ᵃ = gᵃᵇ mod p Note over Bob: K = (gᵃ)ᵇ = gᵃᵇ mod p

3.3 Các bài toán khó nền tảng

Bài toán	Mô tả	Ứng dụng
IFP (Integer Factorization)	Cho $n = p \cdot q$, tìm $p, q$	RSA
DLP (Discrete Log)	Cho $g, p, y = g^x \mod p$, tìm $x$	ElGamal, DHE
DHP (Diffie-Hellman)	Cho $g^a \mod p$, $g^b \mod p$, tính $g^{ab} \mod p$	DHE

3.4 Tấn công Man-in-the-Middle vào DHE

4. Nền tảng Toán học cho ECC

4.1 Cấu trúc đại số

graph LR G["Group (G, +)\n+ và −"] --> R["Ring (R, +, ×)\n+, −, ×"] R --> F["Field (F, +, ×)\n+, −, ×, ÷"] F --> EC["Elliptic Curve Group (E, ⊕)\ndựa trên Field K"]

4.2 Phương trình đường cong Elliptic

Dạng Weierstrass (phổ biến nhất):

$$E/K: y^2 = x^3 + ax + b$$

Ví dụ trực quan

$E/\mathbb{R}: y^2 = x^3 + x + 1$ → đường cong trơn liên tục trên mặt phẳng thực
$E/\mathbb{Z}_7: y^2 = x^3 + x + 1 \pmod{7}$ → tập hữu hạn các điểm nguyên

Tính các điểm trên $E/\mathbb{Z}_7$:

x	x³+x+1 mod 7	y (nếu tồn tại)
0	1	1, 6
1	3	không có (3 không là QR mod 7)
2	4	2, 5
3	3	không có
4	6	không có
5	5	không có
6	6	không có

Dạng Montgomery:

$$E/K: By^2 = x^3 + Ax^2 + x$$

Dạng Twisted Edwards:

$$E/K: ax^2 + y^2 = 1 + dx^2y^2$$

5. Phép toán trên nhóm Elliptic

5.1 Cộng hai điểm phân biệt P₁ + P₂

Công thức đại số (trên trường $\mathbb{Z}_p$):

$$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \mod p$$

$$x_3 = \lambda^2 - x_1 - x_2 \mod p$$

$$y_3 = \lambda(x_1 - x_3) - y_1 \mod p$$

5.2 Nhân đôi điểm (Point Doubling): P + P = 2P

Công thức:

$$\lambda = \frac{3x_1^2 + a}{2y_1} \mod p$$

$$x_3 = \lambda^2 - 2x_1 \mod p, \quad y_3 = \lambda(x_1 - x_3) - y_1 \mod p$$

5.3 Điểm đối và điểm vô cực

$$P + (-P) = \mathcal{O} \quad \text{(điểm vô cực — phần tử trung hòa)}$$

$$P + \mathcal{O} = \mathcal{O} + P = P$$

Điểm đối của $P = (x, y)$ là $-P = (x, -y)$ (trên $\mathbb{Z}_p$: $-P = (x, p-y)$).

5.4 Tính chất nhóm

5.5 Nhân vô hướng (Scalar Multiplication)

$$kG = \underbrace{G + G + \cdots + G}_{k \text{ lần}}$$

Tính hiệu quả: Double-and-Add

Tương tự “Square-and-Multiply” trong RSA. Với k có n bit, cần tối đa $2n$ phép toán thay vì k phép cộng:

Q = O
for bit in bits(k) từ cao xuống thấp:
    Q = 2Q          # Point Doubling
    if bit == 1:
        Q = Q + G   # Point Addition
return Q

6. Tham số nhóm ECC

Một đường cong ECC được xác định bởi bộ tham số:

Tham số	Ý nghĩa
Phương trình	Dạng Weierstrass/Montgomery/Edwards và hệ số $a, b$
Modulo	Số nguyên tố $p$ hoặc đa thức $f(x)$
Generator point G	Điểm cơ sở công khai
Order n	$n = \langle G \rangle$ = số điểm trong subgroup sinh bởi G
Cofactor h	$h = \|E/K\| / n$ (lý tưởng $h = 1$ hoặc $h = 4$)

7. Bài toán khó của ECC: ECDLP

So sánh với DLP thông thường:

	DLP (mod p)	ECDLP
Bài toán	$g^x \equiv y \pmod{p}$, tìm $x$	$dG = Q$, tìm $d$
Thuật toán tốt nhất	Index calculus (sub-exponential)	Baby-step giant-step, Pollard’s rho (fully exponential)
→ Kích thước khóa cần thiết	Lớn hơn nhiều	Nhỏ hơn nhiều

8. Hệ mật ECC

8.1 Thiết lập chung

Cả hai bên đồng thuận công khai:

Đường cong $E/K$, điểm sinh $G$
Mỗi người tự tạo cặp khóa:
- Khóa bí mật: $d \in [1, n-1]$ (chọn ngẫu nhiên)
- Khóa công khai: $Q = d \cdot G$

8.2 ECC Cipher (Mã hóa ElGamal trên đường cong)

sequenceDiagram participant Alice participant Bob Note over Bob: SK = b, PK_B = bG Note over Alice: Muốn gửi M ∈ E/K Alice->>Alice: Chọn ngẫu nhiên k ∈ [1,n-1] Alice->>Alice: R = kG Alice->>Alice: C = M + k·PK_B Alice->>Bob: (R, C) Bob->>Bob: Giải mã: C - b·R Note over Bob: C - bR = M + k·bG - b·kG = M ✓

8.3 ECDHE — Trao đổi khóa Diffie-Hellman trên đường cong

sequenceDiagram participant Alice as Alice (bí mật: a) participant Bob as Bob (bí mật: b) Note over Alice,Bob: Công khai: E/K, G Alice->>Bob: Q_A = a·G Bob->>Alice: Q_B = b·G Note over Alice: K_A = a·Q_B = ab·G Note over Bob: K_B = b·Q_A = ba·G Note over Alice,Bob: K_A = K_B = abG ✓ (khóa phiên chung)

8.4 Bảng so sánh các hệ mật

Thuật toán	Mã hóa/Giải mã	Chữ ký số	Trao đổi khóa
RSA	✅	✅	✅
Elliptic Curve (ECC)	✅	✅	✅
Diffie-Hellman	❌	❌	✅
DSS	❌	✅	❌

9. Tại sao dùng ECC? So sánh kích thước khóa

AES (bit)	RSA/DH (bit)	ECC (bit)
56	512	112
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	512

Nguồn: NIST SP 800-57

10. Ứng dụng ECC

11. Tóm tắt toàn bộ

graph TD A[Bài toán khó: ECDLP] --> B[ECC Public-Key Cryptosystem] B --> C[ECC Cipher\nMã hóa/Giải mã] B --> D[ECDSA\nChữ ký số] B --> E[ECDHE\nTrao đổi khóa] E --> F[Dễ bị MITM\n→ Cần xác thực PKI] B --> G[Ưu điểm:\nKhóa ngắn, nhanh, nhẹ] G --> H[Ứng dụng:\nTLS, SSH, Bitcoin, IoT...]