Skip to content

RSA

RSA là thuật toán mật mã khóa công khai (public-key cryptography): mỗi bên có một cặp khóa, khóa công khai (public key) được phát cho mọi người, còn khóa bí mật (private key) chỉ chủ sở hữu giữ. RSA dùng được cho cả mã hóa lẫn chữ ký số, và hiện là thuật toán ký phổ biến trong chứng chỉ X.509, secure boot và ký firmware. Trang này trình bày lần lượt nền toán học, cách sinh khóa, mã hóa và chữ ký, các chế độ padding, độ dài khóa, các tấn công thường gặp, và cách dùng RSA trên thiết bị nhúng.

Thuật toán do Ron Rivest, Adi Shamir và Leonard Adleman công bố năm 1978; tên RSA ghép từ chữ cái đầu họ của ba tác giả. Chuẩn được dùng trong thực tế là PKCS #1, phiên bản hiện hành 2.2 (RFC 8017).

Nền toán học

RSA dựa trên số học modulo (modular arithmetic): mọi phép tính được thực hiện trên phần dư khi chia cho một số nguyên \(n\). Phần khái niệm đồng dư và số nguyên tố có ở trang Discrete Math & Boolean.

Độ an toàn của RSA dựa trên bài toán phân tích thừa số nguyên tố: nhân hai số nguyên tố lớn \(p\) và \(q\) thành \(n = p \cdot q\) thì nhanh, còn tìm lại \(p\) và \(q\) khi chỉ biết \(n\) thì với kích thước 2048 bit trở lên chưa có thuật toán cổ điển nào làm được trong thời gian khả thi. Ai biết \(p\) và \(q\) thì tính được khóa bí mật, nên \(p\), \(q\) phải được giữ bí mật như chính khóa.

Thuật toán dùng hàm Carmichael \(\lambda(n)\). Với \(n = p \cdot q\):

\[ \lambda(n) = \operatorname{lcm}(p-1,\ q-1) \]

Tính chất cần dùng là: với mọi \(m\), nếu \(e \cdot d \equiv 1 \pmod{\lambda(n)}\) thì

\[ (m^e)^d \equiv m \pmod{n} \]

Nghĩa là lũy thừa \(e\) và lũy thừa \(d\) là hai phép ngược nhau trên modulo \(n\). Bài báo gốc và nhiều giáo trình dùng hàm Euler \(\varphi(n) = (p-1)(q-1)\) thay cho \(\lambda(n)\); cả hai đều cho kết quả đúng, \(\lambda(n)\) là ước của \(\varphi(n)\) nên cho \(d\) nhỏ hơn. RFC 8017 dùng \(\lambda(n)\).

Sinh khóa

  1. Chọn ngẫu nhiên hai số nguyên tố lớn \(p\) và \(q\) có cùng độ dài, ví dụ mỗi số 1536 bit cho khóa 3072 bit.
  2. Tính modulus \(n = p \cdot q\). Độ dài khóa RSA là độ dài bit của \(n\).
  3. Tính \(\lambda(n) = \operatorname{lcm}(p-1, q-1)\).
  4. Chọn public exponent \(e\) nguyên tố cùng nhau với \(\lambda(n)\). Giá trị thường dùng là \(e = 65537 = 2^{16} + 1\).
  5. Tính private exponent \(d = e^{-1} \bmod \lambda(n)\) bằng thuật toán Euclid mở rộng.

Khóa công khai là cặp \((n, e)\), khóa bí mật là \(d\) (kèm \(p\), \(q\) và các giá trị phụ cho CRT, xem mục Tăng tốc bằng CRT).

Chọn \(e = 65537\) vì số này chỉ có hai bit 1 trong biểu diễn nhị phân, nên phép lũy thừa \(m^e\) chỉ cần 17 phép nhân modulo. Nhờ đó mã hóa và verify chữ ký nhanh hơn nhiều so với giải mã và ký. FIPS 186-5 yêu cầu \(2^{16} < e < 2^{256}\), nên các giá trị nhỏ như \(e = 3\) không được dùng trong hệ thống tuân thủ FIPS.

Mã hóa và chữ ký số

Thao tác Khóa dùng Phép tính Mục đích
Mã hóa Public key \((n, e)\) của người nhận \(c = m^e \bmod n\) Chỉ người giữ private key đọc được
Giải mã Private key \(d\) \(m = c^d \bmod n\) Lấy lại bản rõ
Ký Private key \(d\) của người ký \(s = h^d \bmod n\), với \(h\) là hash đã padding Chứng minh dữ liệu do chủ khóa tạo và không bị sửa
Verify Public key \((n, e)\) của người ký Kiểm tra \(s^e \bmod n\) khớp với \(h\) Ai có public key cũng kiểm tra được

Thông điệp \(m\) (và giá trị \(h\)) phải nhỏ hơn \(n\). Vì vậy RSA không mã hóa trực tiếp dữ liệu lớn: thực tế RSA chỉ mã hóa một khóa đối xứng (ví dụ khóa AES) rồi khóa đó mới mã hóa dữ liệu, và khi ký thì ký hash của dữ liệu chứ không ký bản thân dữ liệu.

Các công thức trong bảng là "textbook RSA", tức RSA chưa có padding. Textbook RSA không an toàn khi dùng trực tiếp, lý do trình bày ở mục Padding.

Ví dụ với số nhỏ

Ví dụ sau chỉ để minh họa phép tính; khóa thật dài hàng nghìn bit.

Bước Giá trị
Chọn \(p\), \(q\) \(p = 61\), \(q = 53\)
Modulus \(n = 61 \cdot 53 = 3233\)
\(\lambda(n)\) \(\operatorname{lcm}(60, 52) = 780\)
Public exponent \(e = 17\)
Private exponent \(d = 17^{-1} \bmod 780 = 413\), vì \(17 \cdot 413 = 7021 = 9 \cdot 780 + 1\)
Mã hóa \(m = 65\) \(c = 65^{17} \bmod 3233 = 2790\)
Giải mã \(m = 2790^{413} \bmod 3233 = 65\)
Ký \(h = 65\) \(s = 65^{413} \bmod 3233 = 588\)
Verify \(588^{17} \bmod 3233 = 65\), khớp với \(h\)

Nếu dùng \(\varphi(n) = 3120\) thì \(d = 2753\); giải mã bằng \(d = 2753\) cũng cho lại \(m = 65\).

Tăng tốc bằng CRT

Phép lũy thừa với \(d\) (dài xấp xỉ \(n\)) là phần tốn thời gian nhất. Định lý số dư Trung Hoa (Chinese Remainder Theorem, CRT) cho phép thay một phép lũy thừa modulo \(n\) bằng hai phép lũy thừa modulo \(p\) và modulo \(q\), mỗi phép trên số chỉ dài một nửa. Chi phí lũy thừa modulo tăng xấp xỉ theo lập phương độ dài số, nên mỗi phép chỉ tốn khoảng 1/8, và tổng hai phép giúp giải mã và ký nhanh hơn khoảng bốn lần theo ước lượng lý thuyết.

RFC 8017 lưu private key dạng CRT gồm \(p\), \(q\), \(d_P = d \bmod (p-1)\), \(d_Q = d \bmod (q-1)\) và \(q_{inv} = q^{-1} \bmod p\). Đây chính là các trường prime1, prime2, exponent1, exponent2, coefficient mà openssl pkey -text in ra. Giải mã theo CRT:

\[ m_1 = c^{d_P} \bmod p, \quad m_2 = c^{d_Q} \bmod q, \quad h = q_{inv}\,(m_1 - m_2) \bmod p, \quad m = m_2 + h \cdot q \]

Với ví dụ trên: \(d_P = 53\), \(d_Q = 49\), \(q_{inv} = 38\), \(m_1 = 4\), \(m_2 = 12\), \(h = 1\), và \(m = 12 + 1 \cdot 53 = 65\).

Padding

Textbook RSA có ba điểm yếu chính:

  • Tất định (deterministic): cùng một bản rõ luôn cho cùng bản mã, nên kẻ tấn công đoán được bản rõ chỉ bằng cách mã hóa thử các giá trị khả dĩ rồi so sánh.
  • Tính đồng cấu nhân (multiplicative homomorphism): \((m_1 m_2)^e = m_1^e \cdot m_2^e \pmod n\), nên kẻ tấn công biến đổi được bản mã hoặc ghép chữ ký mà không cần khóa.
  • Thông điệp nhỏ: với \(e\) nhỏ và \(m^e < n\), phép modulo không có tác dụng, bản rõ lấy lại được bằng phép khai căn thông thường.

PKCS #1 khắc phục bằng cách thêm padding có cấu trúc và thành phần ngẫu nhiên trước khi lũy thừa:

Scheme Dùng cho Trạng thái
RSAES-PKCS1-v1_5 Mã hóa Legacy. RFC 8017 chỉ giữ lại để tương thích, khuyến nghị dùng OAEP cho ứng dụng mới
RSAES-OAEP Mã hóa Khuyến nghị. Optimal Asymmetric Encryption Padding (OAEP) trộn bản rõ với chuỗi ngẫu nhiên qua hàm hash
RSASSA-PKCS1-v1_5 Chữ ký Chưa có tấn công thực tế, vẫn dùng rộng rãi trong chứng chỉ X.509
RSASSA-PSS Chữ ký Khuyến nghị cho ứng dụng mới. Probabilistic Signature Scheme (PSS) có salt ngẫu nhiên. TLS 1.3 bắt buộc dùng PSS khi ký CertificateVerify bằng khóa RSA

Độ dài khóa

Độ an toàn của mật mã được đo bằng "security strength" tính theo bit: \(k\) bit nghĩa là tấn công tốt nhất đã biết cần khoảng \(2^k\) phép tính. Bảng dưới lấy theo NIST SP 800-57 Part 1 Rev. 5.

Độ dài modulus RSA Security strength Khóa đối xứng tương đương
1024 bit ≤ 80 bit Không còn được chấp nhận
2048 bit 112 bit 3DES (3 khóa)
3072 bit 128 bit AES-128
7680 bit 192 bit AES-192
15360 bit 256 bit AES-256

NIST SP 800-131A Rev. 2 không cho phép dùng khóa RSA dưới 2048 bit để ký mới hoặc để vận chuyển khóa. Khóa 2048 bit vẫn được chấp nhận; khóa cần dùng lâu dài nên chọn 3072 bit. Khi so với ECC, khóa ECDSA P-256 đạt 128 bit security với khóa và chữ ký ngắn hơn nhiều, nên các hệ thống mới thường chọn ECDSA hoặc Ed25519, trừ khi phần cứng hoặc chuẩn yêu cầu RSA.

Tấn công thường gặp

Tấn công Nguyên nhân Biện pháp
Padding oracle (Bleichenbacher, 1998) Bên giải mã PKCS #1 v1.5 để lộ việc padding đúng hay sai (qua thông báo lỗi hoặc thời gian phản hồi); khoảng một triệu truy vấn đủ để giải mã một bản mã Dùng OAEP; không trả về lỗi phân biệt được. Biến thể ROBOT (2017) vẫn khai thác được nhiều server TLS dùng RSA key exchange
Timing attack (Kocher, 1996) Thời gian lũy thừa modulo phụ thuộc vào các bit của \(d\) Code constant-time, RSA blinding (nhân bản mã với một giá trị ngẫu nhiên trước khi giải mã)
Fault attack lên CRT (Boneh, DeMillo, Lipton, 1997) Lỗi phần cứng (do chèn glitch điện áp hoặc xung clock) làm sai một trong hai nửa CRT; một chữ ký sai đủ để tính ra \(p\) hoặc \(q\) Verify lại chữ ký trước khi xuất ra
Sinh số ngẫu nhiên kém Nhiều thiết bị sinh khóa ngay khi boot lần đầu, lúc entropy còn thấp, nên các khóa có chung thừa số nguyên tố; tính UCLN của hai modulus là lộ \(p\) Bảo đảm entropy đủ trước khi sinh khóa, dùng TRNG phần cứng
Máy tính lượng tử (thuật toán Shor, 1994) Phân tích thừa số trong thời gian đa thức Chuyển sang thuật toán hậu lượng tử (ML-DSA, ML-KEM)

Về lộ trình hậu lượng tử, bản thảo công khai NIST IR 8547 (tháng 11/2024) đề xuất ngừng khuyến nghị (deprecate) RSA mức 112 bit sau năm 2030 và cấm hoàn toàn RSA sau năm 2035.

Chưa kiểm chứng

Chưa đối chiếu với bản chính thức của NIST IR 8547, nếu đã phát hành; các mốc 2030 và 2035 lấy từ bản thảo công khai đầu tiên.

RSA trong các giao thức

  • TLS 1.3: bỏ hẳn RSA key exchange (static RSA), vì không có forward secrecy: lộ private key của server là giải mã được toàn bộ traffic cũ đã ghi lại. RSA chỉ còn dùng để ký, xem TLS.
  • SSH: RSA là một trong các loại host key và user key. Từ bản 8.8, OpenSSH mặc định tắt chữ ký ssh-rsa (dùng SHA-1) và chỉ dùng rsa-sha2-256, rsa-sha2-512. Xem SSH.
  • Chứng chỉ X.509: nhiều CA vẫn ký chứng chỉ bằng RSA (PKCS #1 v1.5 với SHA-256), dùng trong HTTPS.
  • Secure boot: ROM code của SoC verify chữ ký RSA của bootloader bằng public key có hash lưu trong eFuse, xem Secure boot và TrustZone. U-Boot verified boot dùng chữ ký sha256,rsa2048 hoặc rsa4096 trong FIT image, xem U-Boot.

RSA trên thiết bị nhúng

Verify nhanh, ký chậm: với \(e = 65537\), verify chữ ký chỉ tốn vài chục phép nhân modulo, nên phù hợp cho bootloader và ROM code tài nguyên hạn chế. Ký và giải mã cần một phép lũy thừa đầy đủ với \(d\), nên thường được làm trên máy build hoặc trong HSM, không làm trên thiết bị.

Khóa RSA tốn bộ nhớ: public key 3072 bit chiếm 384 byte cho riêng modulus, và mỗi chữ ký cũng dài bằng modulus. Đây là lý do SoC thường chỉ lưu hash của public key trong eFuse, còn public key đầy đủ nằm trong image.

Private key dùng để ký firmware phải được bảo vệ trên máy build (HSM hoặc ít nhất là máy tách biệt). Khi public key đã ghi vào eFuse thì không thay được, nên lộ private key đồng nghĩa với việc kẻ tấn công ký được firmware hợp lệ cho mọi thiết bị đã xuất xưởng.

Thao tác với OpenSSL

Các lệnh sau đã chạy thử với OpenSSL 3.0.

Sinh cặp khóa 3072 bit và tách public key:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out key.pem
openssl pkey -in key.pem -pubout -out pub.pem
openssl pkey -in key.pem -text -noout   # xem n, e, d, p, q và các tham số CRT

Ký và verify một file bằng RSA-PSS với SHA-256:

openssl dgst -sha256 -sign key.pem \
    -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:digest \
    -out firmware.sig firmware.bin
openssl dgst -sha256 -verify pub.pem \
    -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:digest \
    -signature firmware.sig firmware.bin

Mã hóa và giải mã một khóa đối xứng ngắn bằng RSA-OAEP:

openssl pkeyutl -encrypt -pubin -inkey pub.pem \
    -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
    -in aes.key -out aes.key.enc
openssl pkeyutl -decrypt -inkey key.pem \
    -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
    -in aes.key.enc -out aes.key

Liên quan

Tài liệu tham khảo