Bài 12: Chữ ký số (Digital Signature)

1. Động lực (Motivations)

Vấn đề với MAC/HMAC

Giả sử Alice muốn gửi tin nhắn cho Bob và đảm bảo tính xác thực + toàn vẹn. Với MAC/HMAC, họ cần chia sẻ trước một khóa bí mật $K$:

Alice                              Bob
  |  ── (M, tag = HMAC(K, M)) ──>   |
  |                                 |  kiểm tra HMAC(K, M') == tag?

Hạn chế: Nếu Alice và Bob không thể thỏa thuận khóa phiên $K$ trước (ví dụ: không có kênh bảo mật, hoặc Bob là người lạ), thì MAC không dùng được.

Ngoài ra, MAC/HMAC không có tính chối bỏ — vì cả Alice lẫn Bob đều biết $K$, Bob không thể chứng minh với bên thứ ba rằng chữ ký đến từ Alice.

Giải pháp: Chữ ký số (Digital Signature)

Alice (có cặp khóa PK_A, SK_A)           Bob, Carol, Dave, ...
  |                                              |
  |  ── (M, sig = sign(SK_A, M)) ──────────>     |
  |                                              |  verify(PK_A, M', sig)?

• Alice ký bằng khóa bí mật $SK_A$ (chỉ mình Alice biết).
• Bất kỳ ai có khóa công khai $PK_A$ đều có thể xác minh.
• Không cần chia sẻ bí mật trước → phù hợp với môi trường mở.

2. Tính chất của chữ ký số

3. Quy trình tổng quát của chữ ký số

Bốn bước cụ thể:

4. ElGamal Digital Signature

4.1 Tham số hệ thống

• $p$: số nguyên tố $\lambda$-bit
• $g$: generator của nhóm nhân $\mathbb{Z}_p^*$
• $H: {0,1}^* \to {0,1}^L$ với $L \geq \lambda$

Public parameters: $(p, g, H)$

4.2 Sinh khóa

• Khóa bí mật: $x \xleftarrow{R} \mathbb{Z}_p^*$
• Khóa công khai: $y = g^x \mod p$

4.3 Ký (Signing)

Để ký thông điệp $m$:

1. Chọn ngẫu nhiên $k \xleftarrow{R} \mathbb{Z}_p^*$ (khóa tạm, dùng một lần)
2. Tính $r = g^k \mod p$
3. Tính $s = (H(m) - x \cdot r) \cdot k^{-1} \mod (p-1)$
4. Chữ ký: $(r, s)$, gửi $(m, (r, s))$

4.4 Xác minh (Verifying)

Nhận $(m’, r, s)$:

1. Kiểm tra $0 < r < p$ và $0 < s < p-1$
2. Kiểm tra:

$$y^r \cdot r^s \mod p \stackrel{?}{=} g^{H(m’)}$$

Chứng minh tính đúng đắn (correctness):

$$y^r \cdot r^s = g^{xr} \cdot g^{ks} = g^{xr + k \cdot (H(m) - xr) \cdot k^{-1}} = g^{H(m)}$$

Nếu $m’ = m$ thì $g^{H(m)} = g^{H(m’)}$ → xác minh thành công.

5. Schnorr Digital Signature

5.1 Tham số hệ thống

• Hai số nguyên tố $p, q$ sao cho $p = qr + 1$ (tức $q \mid p-1$)
• $g$: generator của nhóm con bậc $q$ trong $\mathbb{Z}_p^*$
• $H: {0,1}^* \to \mathbb{Z}_q$

Public parameters: $(p, q, g, H)$

5.2 Sinh khóa

• Khóa bí mật: $x \xleftarrow{R} \mathbb{Z}_p^*$
• Khóa công khai: $y = g^x \mod p$

5.3 Ký

1. Chọn ngẫu nhiên $k \xleftarrow{R} \mathbb{Z}_p^*$
2. Tính $r = g^k$
3. Tính $e = H(r | m) \in \mathbb{Z}_q$ ← đây là “challenge”
4. Tính $s = k - x \cdot e \mod q$
5. Chữ ký: $(s, e)$

5.4 Xác minh

Nhận $(m’, s, e)$:

1. Tính $r_v = g^s \cdot y^e \mod p$

$$= g^{k - xe} \cdot g^{xe} = g^k = r$$

2. Kiểm tra: $e \stackrel{?}{=} H(r_v | m’)$

6. NIST Digital Signature Schemes

6.1 Lịch sử chuẩn hóa

6.2 Hai hướng tiếp cận

7. RSASSA Signatures

7.1 Nguyên lý cơ bản

• Public key: $(n, e)$; Private key: $d$
• Ký: $s = H(m)^d \mod n$
• Xác minh: $s^e \mod n = H(m)^{de} \mod n = H(m) \stackrel{?}{=} H(m’)$

7.2 RSASSA-PKCS1-v1_5

Định dạng bản tin được mã hóa (Encoded Message - EM):

EM = 0x00 || 0x01 || 0xFF...0xFF || 0x00 || DigestInfo || H(M)

Trong đó DigestInfo xác định thuật toán băm:

Quy trình:

M ──hash──> H(M) ──prepend DigestInfo──> EM ──RSA encrypt──> s (signature)

7.3 RSASSA-PSS (Probabilistic Signature Scheme)

PSS dùng salt ngẫu nhiên để đảm bảo tính probabilistic (cùng $m$ ký hai lần → chữ ký khác nhau).

Quy trình encoding (PSS-Encode):

M ──hash──> mHash
mHash + salt ──hash──> H' (8 bytes 0x00 || mHash || salt)

DB = padding2 || salt
dbMask = MGF(H')       ← MGF = Mask Generation Function (cũng dùng hash)
maskedDB = DB XOR dbMask

EM = maskedDB || H' || 0xBC

Quy trình ký:

EM ──RSA encrypt với SK──> s

Quy trình xác minh:

s ──RSA decrypt với PK──> EM ──PSS-Decode──> kiểm tra H(M*) == mHash

8. DSA (Digital Signature Algorithm)

8.1 Tham số hệ thống

Kích thước khóa được NIST chuẩn hóa:

8.2 Sinh khóa

• Khóa bí mật: $x \xleftarrow{R} [1, q-1]$
• Khóa công khai: $y = g^x \mod p$

8.3 Ký

1. Chọn ngẫu nhiên $k \xleftarrow{R} [1, q-1]$ (mỗi thông điệp một $k$ khác nhau!)
2. Tính $r = (g^k \mod p) \mod q$
3. Tính $s = k^{-1}(H(m) + x \cdot r) \mod q$
4. Chữ ký: $(r, s)$

8.4 Xác minh

Nhận $(m’, r, s)$:

$$w = s^{-1} \mod q$$

$$u_1 = H(m’) \cdot w \mod q$$

$$u_2 = r \cdot w \mod q$$

$$v = (g^{u_1} \cdot y^{u_2} \mod p) \mod q$$

Kiểm tra: $v \stackrel{?}{=} r$

Chứng minh correctness: Nếu $m’ = m$:

$$g^{u_1} \cdot y^{u_2} = g^{u_1 + x \cdot u_2} = g^{k(H(m)+xr)(H(m)+xr)^{-1}} = g^k$$

Do đó $(g^k \mod p) \mod q = r$ ✓

9. ECDSA (Elliptic Curve DSA)

9.1 Tham số hệ thống

Bảng mức bảo mật theo FIPS 186-5:

9.2 Sinh khóa

• Khóa bí mật: $d \xleftarrow{R} [1, n-1]$
• Khóa công khai: $Q = d \cdot G \in E(\mathbb{Z}_p)$ (phép nhân vô hướng trên đường cong)

9.3 Ký

1. Chọn $k \xleftarrow{R} [1, n-1]$
2. Tính $R = k \cdot G = (x_1, y_1)$, đặt $r = x_1 \mod n$
3. Tính $s = k^{-1}(H(m) + d \cdot r) \mod n$
4. Chữ ký: $(r, s)$

9.4 Xác minh

Nhận $(m’, r, s)$:

$$w = s^{-1} \mod n$$

$$u_1 = H(m’) \cdot w \mod n, \quad u_2 = r \cdot w \mod n$$

$$X = u_1 G + u_2 Q = (x_1’, y_1’)$$

$$v_x = x_1’ \mod n \stackrel{?}{=} r$$

10. X.509 Digital Certificates

10.1 Vấn đề phân phối khóa công khai

Giải pháp: Chứng chỉ số X.509

$$\text{Certificate} = (M = {\text{user}, \text{publickey}, \ldots},\ s = \text{sign}(SK_{CA}, M))$$

Trong đó $CA$ (Certificate Authority) là bên thứ ba đáng tin cậy.

10.2 Cấu trúc chứng chỉ X.509

10.3 Kiểm tra chứng chỉ thực tế với OpenSSL

# Xem chứng chỉ server của facebook.com
echo | openssl s_client -servername www.facebook.com \
    -connect www.facebook.com:443 2>/dev/null \
    | openssl x509 -text

# Tải về file .cer
echo | openssl s_client -servername www.facebook.com \
    -connect www.facebook.com:443 2>/dev/null \
    | openssl x509 -out facebook.cer

# Đọc file cert đã tải
openssl x509 -in facebook.cer -inform pem -text -noout

# Xem toàn bộ chuỗi chứng chỉ (chain)
openssl s_client -connect facebook.com:443 -showcerts

10.4 PKI (Public Key Infrastructure)

PKI là hệ thống quản lý toàn bộ vòng đời của chứng chỉ số:

Chức năng của PKI:

• Xác định tính hợp lệ của người dùng
• Phát hành / gia hạn / thu hồi chứng chỉ
• Lưu trữ và quản lý chứng chỉ
• Ngăn chặn người ký chối bỏ chữ ký (non-repudiation)
• Hỗ trợ cross-certification giữa các PKI khác nhau

10.5 PKIX (X.509 PKI theo IETF RFC 5280)

Bốn thành phần cơ bản:

Các giao dịch được quản lý:

• Registration, Initialization
• Certificate Issuing & Publication
• Key Recovery, Key Generation
• Certificate Revocation
• Cross-certification

11. Tấn công vào chữ ký số

11.1 Phân loại theo khả năng của kẻ tấn công

Từ trên xuống dưới: năng lực kẻ tấn công tăng dần. Một sơ đồ an toàn phải chống được adaptive chosen message attack (mô hình EUF-CMA).

11.2 Phân loại theo mức độ giả mạo

12. Yêu cầu của chữ ký số

Một sơ đồ chữ ký số phải thỏa mãn đồng thời:

1. Chữ ký là một bit pattern phụ thuộc vào thông điệp được ký.
2. Chữ ký sử dụng thông tin duy nhất của người ký (khóa bí mật) để ngăn giả mạo và chối bỏ.
3. Dễ tạo chữ ký — người có $SK$ ký nhanh.
4. Dễ xác minh — người có $PK$ kiểm tra nhanh.
5. Không thể giả mạo về mặt tính toán — không thể tạo chữ ký hợp lệ cho thông điệp mới, hay tạo chữ ký giả cho thông điệp cho trước.
6. Có thể lưu trữ — chữ ký có kích thước thực tế.

13. Direct Digital Signature

Direct Digital Signature = sơ đồ chữ ký số chỉ có hai bên tham gia (Alice và Bob), không có bên thứ ba online.

Giả định: Bob biết $PK_A$ của Alice trước.

Bảo mật: Để thêm tính bảo mật, toàn bộ $(M, s)$ được mã hóa bằng khóa phiên chung.

14. Tóm tắt so sánh các sơ đồ