So sánh RSA và DSA

1. Tổng quan

A. Định nghĩa

RSA (Rivest–Shamir–Adleman) là thuật toán mật mã khóa công khai dựa trên tính khó về mặt tính toán của việc phân tích số lớn ra thừa số nguyên tố, là thuật toán đa dụng có thể thực hiện cả mã hóa (bí mật) lẫn chữ ký điện tử (xác thực·toàn vẹn·chống chối bỏ).

DSA (Digital Signature Algorithm) là thuật toán chỉ dùng cho chữ ký điện tử, được chấp nhận làm tiêu chuẩn liên bang Hoa Kỳ (DSS, Digital Signature Standard), dựa trên độ khó của bài toán logarit rời rạc (Discrete Logarithm Problem) trên trường hữu hạn.

Lý do căn bản để so sánh hai thuật toán cùng nhau là cả hai thuộc cùng phạm trù "mật mã bất đối xứng dùng một cặp khóa công khai/khóa riêng", nhưng bài toán khó toán học mà chúng dựa vào và mục đích thiết kế khác nhau. Mật mã khóa công khai tận dụng tính chất khóa công khai và khóa riêng ghép cặp về mặt toán học, cái được biến đổi bằng một khóa chỉ có thể được đảo ngược bằng khóa còn lại. Tính chất của thuật toán phân hóa tùy vào việc tính chất này được xây dựng trên "hàm một chiều (one-way function)" nào. RSA xây dựng nguyên lý này trên độ khó của phân tích thừa số nguyên tố, còn DSA xây dựng trên độ khó của logarit rời rạc.

B. Bối cảnh ra đời và sự cần thiết

RSA được công bố năm 1977, là mật mã khóa công khai gần như đầu tiên được đưa vào thực tiễn, và nhờ tính đa dụng "vừa mã hóa vừa ký được" đã trở thành tiêu chuẩn của hạ tầng tin cậy Internet như SSL/TLS, S/MIME, ký mã, chứng thư số công nhận. Tuy nhiên, RSA đi kèm tranh cãi về bằng sáng chế·hiệu năng cùng nhận thức vấn đề "chính phủ khó kiểm soát tiêu chuẩn chữ ký", nên NIST Hoa Kỳ năm 1991 đã đề xuất DSA làm tiêu chuẩn chỉ dành cho chữ ký và năm 1994 xác lập thành FIPS 186 (DSS). Tức là DSA ngay từ đầu được thiết kế với tư cách tiêu chuẩn quốc gia cho mục đích duy nhất là chữ ký điện tử, và chức năng mã hóa bị loại bỏ có chủ đích.

Khác biệt bối cảnh này ảnh hưởng trực tiếp tới lựa chọn thực tiễn. RSA phù hợp với hệ thống đa dụng muốn "giải quyết cả tính bí mật và toàn vẹn bằng một thuật toán", còn DSA phù hợp với lĩnh vực "chỉ cần chữ ký nhưng coi trọng tuân thủ tiêu chuẩn·tốc độ tạo chữ ký". Tuy nhiên, như sẽ trình bày sau, ngày nay DSA trên thực tế đã bị thay thế bởi ECDSA và EdDSA dựa trên đường cong elliptic, và trong tiêu chuẩn Hoa Kỳ mới nhất (FIPS 186-5, 2023), việc tạo chữ ký mới bằng DSA đã bị loại bỏ (deprecated).

C. Nền tảng toán học của hai thuật toán

Cả hai bài toán khó đều cung cấp tính một chiều "tính xuôi dễ nhưng tính ngược khó theo hàm mũ". Phân tích thừa số dựa vào tính chất phép nhân dễ nhưng phân tích thừa số khó, còn logarit rời rạc dựa vào tính chất lũy thừa dễ nhưng tìm lại số mũ đó khó.

2. So sánh cấu trúc tổng thể RSA·DSA

Sơ đồ khái niệm dưới đây cho thấy bố cục tổng thể: hai thuật toán xuất phát từ cùng gốc "mật mã bất đối xứng" nhưng trên các bài toán khó khác nhau nên có phạm vi chức năng khác nhau.

flowchart TB
  PKC["Mật mã khóa công khai (bất đối xứng)"] --> RSA["RSA (dựa trên phân tích thừa số)"]
  PKC --> DSA["DSA (dựa trên logarit rời rạc)"]
  RSA --> RE["Mã hóa/giải mã (bí mật)"]
  RSA --> RS["Chữ ký điện tử (xác thực·toàn vẹn)"]
  DSA --> DS["Chỉ dùng cho chữ ký điện tử"]
  DSA -. tiến hóa .-> ECDSA["ECDSA (đường cong elliptic)"]
  RSA -. mối đe dọa lượng tử .-> PQC["PQC (mật mã kháng lượng tử)"]
  DSA -. mối đe dọa lượng tử .-> PQC
  style RSA fill:#e8f0fe,stroke:#2f6fed
  style DSA fill:#e8f0fe,stroke:#2f6fed
  style PQC fill:#fde8e8,stroke:#d33

RSA từ một thuật toán vươn ra hai nhánh (mã hóa·chữ ký), trong khi DSA hội tụ vào một chức năng duy nhất là chữ ký, và rốt cuộc cả hai thuật toán đều nằm dưới mối đe dọa của máy tính lượng tử và chịu áp lực chuyển đổi sang PQC.

A. Nguyên lý hoạt động của RSA

Cốt lõi của RSA nằm ở sinh khóa. Chọn hai số nguyên tố lớn p, q để tạo modulus n=p·q, và tính hàm Euler φ(n)=(p−1)(q−1). Chọn số mũ công khai e nguyên tố cùng nhau với φ(n), rồi tìm số mũ riêng d thỏa mãn e·d≡1 (mod φ(n)). Khóa công khai tạo ra như vậy là (n, e), khóa riêng là (n, d). Bản chất an toàn ở đây là dù kẻ tấn công biết n, nếu không phân tích được thành p·q thì không tính được φ(n), do đó không suy ra được d.

Mã hóa được thực hiện với bản rõ m bằng c=mᵉ mod n, giải mã đảo lại bằng m=cᵈ mod n. Chữ ký điện tử dùng quan hệ này theo chiều ngược lại: ký hash thông điệp H(m) bằng khóa riêng S=H(m)ᵈ mod n, bên nhận tính Sᵉ mod n bằng khóa công khai và kiểm tra có khớp với H(m) không. Tức là nhờ cấu trúc đối xứng "cái khóa bằng khóa riêng chỉ mở được bằng khóa công khai", một thuật toán đảm nhận được cả tính bí mật lẫn xác thực. Trong thực tiễn, vì an toàn người ta không dùng nguyên RSA thô mà bắt buộc áp dụng padding (OAEP cho mã hóa, PSS cho chữ ký).

B. Nguyên lý hoạt động của DSA

DSA có thủ tục tạo chữ ký khác căn bản với RSA. Trước hết, tham số hệ thống gồm số nguyên tố lớn p, số nguyên tố q chia hết p−1, phần tử sinh g có cấp (order) q. Khóa riêng x được chọn ngẫu nhiên, khóa công khai được định nghĩa là y=gˣ mod p. Khi ký, mỗi chữ ký rút một số ngẫu nhiên tạm thời k mới, tính r=(gᵏ mod p) mod q, s=k⁻¹(H(m)+x·r) mod q, và gửi giá trị chữ ký (r, s). Bên xác minh tính w=s⁻¹ mod q, u₁=H(m)·w mod q, u₂=r·w mod q rồi kiểm tra v=((g^{u₁}·y^{u₂}) mod p) mod q có bằng r không.

Cạm bẫy thực tiễn nhất định phải nhấn mạnh ở đây là quản lý số ngẫu nhiên tạm thời k. Nếu tái sử dụng k hoặc sinh k có thể dự đoán, khóa riêng x sẽ được khôi phục nguyên vẹn từ hệ phương trình của hai chữ ký. Thực tế, sự kiện khóa ký mã của Sony PlayStation 3 bị lộ năm 2010 do lỗ hổng này là trường hợp tiêu biểu, và cùng rủi ro áp dụng nguyên vẹn cho chữ ký đường cong elliptic (ECDSA). Vì vậy ngày nay khuyến nghị RFC 6979 (Deterministic DSA/ECDSA) dẫn xuất k một cách tất định từ thông điệp và khóa riêng.

C. Quy trình xử lý chung của chữ ký điện tử

Dù RSA hay DSA, chữ ký điện tử đều tuân theo thủ tục chung "ký lên giá trị hash của văn bản gốc chứ không phải toàn bộ văn bản gốc". Biểu đồ tuần tự dưới đây cho thấy luồng từ tạo chữ ký tới xác minh.

sequenceDiagram
  participant S as Người ký (khóa riêng)
  participant N as Mạng
  participant V as Người xác minh (khóa công khai)
  S->>S: Tính hash văn bản gốc H(m) (SHA-256...)
  S->>S: Ký H(m) bằng khóa riêng
  S->>N: Gửi văn bản gốc + giá trị chữ ký
  N->>V: Nhận văn bản gốc + giá trị chữ ký
  V->>V: Tính lại hash văn bản gốc H'(m)
  V->>V: Xác minh chữ ký bằng khóa công khai rồi so sánh với H(m)
  V-->>V: Khi khớp, xác lập toàn vẹn·xác thực·chống chối bỏ

Ký lên hash như vậy (1) nén tài liệu độ dài tùy ý thành độ dài cố định để giảm khối lượng phép toán ký, (2) chỉ cần văn bản gốc thay đổi một bit thì hash khác đi nên phát hiện ngay giả mạo·sửa đổi, và (3) chỉ người giữ khóa riêng mới ký được nên xác thực người ký và cung cấp chống chối bỏ.

3. So sánh chi tiết và hàm ý thực tiễn

Khác biệt giữa hai thuật toán phải được hiểu qua "vì sao sinh ra hồ sơ tốc độ·mục đích sử dụng như vậy" chứ không phải liệt kê chức năng đơn thuần. RSA khi xác minh lấy lũy thừa với số mũ công khai nhỏ (ví dụ: e=65537) nên xác minh rất nhanh, trong khi số mũ riêng d lớn nên tạo chữ ký chậm. DSA ngược lại, tạo chữ ký nhanh nhưng xác minh cần hai phép lũy thừa nên tương đối chậm. Chữ ký điện tử thường "ký một lần và xác minh nhiều lần" (ví dụ: một chứng chỉ được vô số client xác minh), nên việc RSA xác minh nhanh được dùng rộng rãi cho chứng chỉ máy chủ TLS là hệ quả tự nhiên của hồ sơ tốc độ này.

Quan hệ giữa độ dài khóa và độ an toàn cũng là cốt lõi của phán đoán thực tiễn. Theo NIST SP 800-57, mức an toàn 112 bit tương ứng RSA 2048 bit, mức an toàn 128 bit tương ứng RSA 3072 bit. Trong khi đó, cùng mức an toàn 128 bit thì đường cong elliptic (ECDSA) đạt được chỉ với khóa 256 bit. Tức là RSA càng nâng độ an toàn thì chi phí khóa·chữ ký·phép toán tăng vọt (3072→7680→15360 bit), trong khi đường cong elliptic tăng khóa từ từ. Khoảng cách về khả năng mở rộng này là lý do quyết định thúc đẩy chuyển đổi sang ECDSA·EdDSA trong môi trường hạn chế tài nguyên như di động·IoT.

Tổng hợp khác biệt bằng ba tình huống cụ thể như sau. Thứ nhất, chứng chỉ TLS của máy chủ web có tần suất xác minh áp đảo nên RSA-2048/3072 hoặc ECDSA-P256 xác minh nhanh được dùng làm chuẩn. Thứ hai, blockchain như Bitcoin·Ethereum coi trọng kích thước chữ ký và hiệu năng xác minh nên dùng ECDSA (secp256k1) chứ không phải DSA. Thứ ba, chữ ký điện tử dài hạn cho văn bản chính phủ·công coi trọng tuân thủ tiêu chuẩn nên trước đây dùng DSA, nhưng hiện đang chuyển sang RSA-PSS hoặc ECDSA.

4. Chuyên sâu — xu hướng tiêu chuẩn mới nhất và chuyển đổi sang mật mã kháng lượng tử

Lựa chọn thuật toán chữ ký điện tử gần đây đang được tái cấu trúc mạnh mẽ bởi hai thay đổi tiêu chuẩn, nhất định phải được chỉ ra từ góc nhìn Kỹ sư chuyên nghiệp.

Thứ nhất, trong FIPS 186-5 (sửa đổi năm 2023), NIST Hoa Kỳ đã loại bỏ (deprecated) DSA thuần cho việc tạo chữ ký mới, và sắp xếp lại các thuật toán chữ ký được phê duyệt thành RSA·ECDSA·EdDSA (Ed25519/Ed448). Tức là DSA giờ chỉ được cho phép có giới hạn cho "xác minh chữ ký cũ (legacy)", và khuyến nghị tiêu chuẩn là không dùng trong hệ thống mới. Điều này có nghĩa DSA vẫn được học như một chủ đề nhưng phải loại khỏi đối tượng áp dụng mới trong thực tiễn.

Thứ hai là mối đe dọa máy tính lượng tử và chuyển đổi PQC. Thuật toán Shor, nếu có máy tính lượng tử đủ lớn, có thể giải cả phân tích thừa số lẫn logarit rời rạc trong thời gian đa thức, nên RSA·DSA·ECDSA về nguyên lý đều bị vô hiệu hóa. Vì vậy tháng 8 năm 2024 NIST đã xác lập các tiêu chuẩn mật mã kháng lượng tử đầu tiên; trong lĩnh vực chữ ký chọn ML-DSA (FIPS 204, CRYSTALS-Dilithium) dựa trên lưới và SLH-DSA (FIPS 205, SPHINCS+) dựa trên hash, còn cho trao đổi khóa chọn ML-KEM (FIPS 203, Kyber). Đặc biệt, do mô hình tấn công "thu thập bây giờ, giải mã sau (Harvest Now, Decrypt Later)", khuyến nghị bắt đầu chuyển đổi trước bằng phương thức lai (dùng song song cũ+PQC) cho chữ ký·dữ liệu bí mật cần lưu giữ dài hạn.

5. Lưu ý và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)

1. Chiến lược lựa chọn theo mục đích sử dụng: Nếu cần cả tính bí mật và chữ ký thì chọn RSA (với điều kiện bắt buộc padding OAEP·PSS), nếu chỉ cần chữ ký và coi trọng hiệu năng·kích thước chữ ký thì chọn ECDSA/EdDSA. Tránh áp dụng mới DSA thuần và chỉ giới hạn cho mục đích tương thích hệ thống cũ.

2. Đánh đổi về an toàn hiện thực: Độ an toàn của DSA·ECDSA phụ thuộc quyết định vào chất lượng số ngẫu nhiên tạm thời k, nên bắt buộc phải dùng CSPRNG đã kiểm chứng hoặc chữ ký tất định RFC 6979. RSA ít phụ thuộc số ngẫu nhiên nhưng có thể dễ bị tấn công padding oracle, nên kiểm chứng hiện thực (mô-đun FIPS 140-3) là quan trọng.

3. Quản lý độ dài·vòng đời khóa (Crypto-agility): Theo khuyến nghị của NIST, nếu nhắm tới sau năm 2030 thì RSA phải bảo đảm từ 3072 bit trở lên, nhưng xét chi phí mở rộng thì hệ thống mới nên được thiết kế dựa trên đường cong elliptic, và phải có kiến trúc tính linh hoạt mật mã (crypto-agility) cho phép thay thế thuật toán dễ dàng.

4. Lập lộ trình chuyển đổi kháng lượng tử: RSA·DSA·ECDSA đều dễ bị thuật toán Shor tấn công, nên phải chuẩn bị ngay từ bây giờ kế hoạch di trú PQC theo từng bước: kiểm kê tài sản (xác định mật mã nào được dùng ở đâu)→xếp thứ tự ưu tiên (ưu tiên dữ liệu lưu giữ dài hạn)→áp dụng lai→chuyển đổi toàn diện.

5. Tích hợp công nghệ liên kết: Chữ ký điện tử chỉ có hiệu lực thực tế khi kết hợp với PKI (chuỗi tin cậy chứng chỉ), dấu thời gian (TSA), xác minh dài hạn (LTV)..., nên phải thiết kế đồng thời chính sách vận hành·gia hạn của toàn bộ hạ tầng tin cậy chứ không chỉ bản thân thuật toán.

Tài liệu tham khảo

• NIST, FIPS 186-5 Digital Signature Standard (2023): https://csrc.nist.gov/pubs/fips/186-5/final
• NIST, SP 800-57 Part 1 Rev.5 Key Management: https://csrc.nist.gov/pubs/sp/800/57/pt1/r5/final
• NIST, Post-Quantum Cryptography Standards (FIPS 203/204/205, 2024): https://csrc.nist.gov/news/2024/postquantum-cryptography-fips-approved
• IETF, RFC 6979 Deterministic DSA/ECDSA: https://datatracker.ietf.org/doc/html/rfc6979

Tóm tắt một câu: RSA là thuật toán đa dụng dựa trên phân tích thừa số nguyên tố, làm được cả mã hóa·chữ ký, DSA là thuật toán chỉ dùng cho chữ ký dựa trên logarit rời rạc, chúng khác nhau về tốc độ tạo·xác minh chữ ký và phạm vi ứng dụng; DSA đã bị loại bỏ việc tạo chữ ký mới trong FIPS 186-5 và được thay thế bởi ECDSA·EdDSA, còn cả hai thuật toán đều dễ bị thuật toán Shor tấn công nên cần chuyển đổi sang mật mã kháng lượng tử (PQC) như ML-DSA.