Bài 2 cho anh cỗ máy nén tài liệu về 32 byte. Bài này cho anh cỗ máy biến 32 byte đó thành một thứ mà chỉ người giữ khóa bí mật tạo được, nhưng ai cũng kiểm tra được. Ghép hai cỗ máy lại ở Bài 4 là ra chữ ký số hoàn chỉnh.
RSA nổi tiếng khó, nhưng cái khó nằm ở chỗ người ta thường giảng công thức trước, trực giác sau. Ta làm ngược lại. Tôi sẽ dẫn anh qua đúng bốn viên gạch số học, mỗi viên đều chạy được bằng số cụ thể, rồi RSA sẽ tự lắp ráp thành hình.
3.1. Toàn bộ RSA nằm trên một câu hỏi
Trước khi có công thức nào, hãy nắm ý tưởng cốt lõi. RSA đi tìm một cặp phép toán thỏa mãn:
Có hai thao tác
EvàD. Bất kỳ ai cũng làm đượcE. Chỉ người giữ bí mật làm đượcD. VàD(E(x)) = x— chúng khử nhau.
Nếu tìm được cặp như vậy, chữ ký số xuất hiện gần như miễn phí: người ký dùng D (chỉ mình làm được) để tạo chữ ký, cả thế giới dùng E (ai cũng làm được) để kiểm tra.
Câu hỏi là: cặp phép toán đó lấy đâu ra? RSA trả lời: từ số học modulo. Ta xây dần.
3.2. Viên gạch 1 — Số học modulo, hay "toán học của mặt đồng hồ"
Anh đã quen modulo mà không gọi tên nó. Đồng hồ 12 giờ: 10 giờ cộng 5 tiếng ra 3 giờ, không phải 15. Ta viết 10 + 5 ≡ 3 (mod 12).
Số học modulo n là làm toán rồi luôn lấy phần dư khi chia cho n. Nó có một tính chất quý: phép nhân và lũy thừa vẫn chạy bình thường bên trong. Anh có thể lấy dư ở bất kỳ bước nào mà kết quả không đổi:
(a · b) mod n = ((a mod n) · (b mod n)) mod nĐiều này khiến ta tính được m^d mod n với d khổng lồ mà không bao giờ phải giữ con số m^d thật (nó có thể dài hàng nghìn chữ số). Cứ nhân từng bước rồi lấy dư ngay. Đây là lý do RSA khả thi về mặt tính toán — ta sẽ đo tốc độ ở mục 3.8.
Không gian ta làm việc là tập {0, 1, 2, ..., n-1} — mọi số đều "quấn vòng" trong đó. Chữ ký RSA-2048 là một số nằm đâu đó trong tập {0, ..., n-1} với n dài 617 chữ số thập phân.
3.3. Viên gạch 2 — Hàm Euler φ(n)
Định nghĩa: φ(n) là số các số trong khoảng 1 đến n mà nguyên tố cùng nhau với n (tức ước chung lớn nhất với n bằng 1).
Nói chung φ(n) khó tính, vì phải biết cấu trúc của n. Nhưng có một trường hợp đặc biệt dễ đến bất ngờ — và RSA sống nhờ đúng trường hợp này:
Nếu
n = p · qvớip, qlà hai số nguyên tố, thìφ(n) = (p−1)(q−1).
Vì sao? Trong {1, ..., n}, những số không nguyên tố cùng nhau với n chỉ có thể là bội của p (có q cái) hoặc bội của q (có p cái), trừ đi số n bị đếm hai lần. Lấy n trừ đi phần đó ra đúng (p−1)(q−1).
Đây là chỗ cửa sập đầu tiên xuất hiện, và tôi muốn anh dừng lại thấy nó:
- Ai biết
pvàq→ tính φ(n) tức thì. - Ai chỉ biết
n→ muốn tính φ(n) phải phân tíchnrap·qtrước. Mà việc đó, vớinđủ lớn, là bất khả thi.
Cùng một số φ(n), người trong cuộc tính trong một phép nhân, người ngoài cuộc phải trả giá bằng tuổi thọ vũ trụ. Sự bất đối xứng này chính là RSA.
3.4. Viên gạch 3 — Định lý Euler, trái tim của cỗ máy
Đây là mệnh đề làm mọi thứ khớp vào nhau:
Với mọi
anguyên tố cùng nhau vớin:a^φ(n) ≡ 1 (mod n)
Nghĩa là nâng a lên lũy thừa φ(n) thì luôn quay về 1, bất kể a là gì (miễn nguyên tố cùng nhau với n). Nó là dạng tổng quát của định lý nhỏ Fermat mà anh có thể đã gặp.
Kiểm chứng bằng số, với n = 3233, φ(n) = 3120:
2^3120 mod 3233 = 1
7^3120 mod 3233 = 1
65^3120 mod 3233 = 1Ba số khác hẳn nhau, cùng cho ra 1. Không phải trùng hợp — đó là định lý.
Vì sao định lý này là chìa khóa? Vì nó cho ta biết chính xác lũy thừa nào là "vô hại". Nâng lên bội của φ(n) rồi thêm 1 thì số không đổi:
a^(k·φ(n) + 1) = (a^φ(n))^k · a = 1^k · a = a (mod n)Giữ chặt dòng này. Toàn bộ phép giải mã/verify của RSA chỉ là dòng này.
3.5. Viên gạch 4 — Nghịch đảo modulo, cách tạo cặp khóa
Ta muốn hai số e và d sao cho ghép lại thành "lũy thừa vô hại". Từ mục 3.4, điều đó nghĩa là:
e · d ≡ 1 (mod φ(n))Tức e·d = k·φ(n) + 1 với k nguyên nào đó. Khi ấy (x^e)^d = x^(ed) = x^(kφ+1) = x. Hai phép lũy thừa khử nhau — đúng cặp E, D mà mục 3.1 đi tìm.
Cho trước e, tìm d gọi là tìm nghịch đảo modulo. Giải bằng thuật toán Euclid mở rộng, rất nhanh. Trong Python đúng một dòng: pow(e, -1, phi).
Và đây là điểm mấu chốt của bảo mật: tìm d cần biết φ(n). Người ngoài không biết φ(n) (vì không phân tích được n), nên không tính được d. Khóa bí mật d được bảo vệ bởi đúng cửa sập ở mục 3.3.
3.6. Lắp ráp — RSA hoàn chỉnh, chạy tay từng số
Giờ bốn viên gạch tự lắp thành cỗ máy. Tôi dùng ví dụ kinh điển p=61, q=53 để anh theo được bằng máy tính cầm tay.
Bước sinh khóa:
p = 61, q = 53
n = p·q = 3233
φ(n) = (p−1)(q−1) = 60·52 = 3120
chọn e = 17 (nguyên tố cùng nhau với 3120)
tính d = 17⁻¹ mod 3120 = 2753Kiểm tra điều kiện cốt lõi:
e·d = 17 · 2753 = 46801 = 15·3120 + 1 = 15·φ(n) + 1 ✓Đúng dạng "bội của φ cộng 1". Vậy e và d sẽ khử nhau.
- Khóa công khai:
(n=3233, e=17)— công bố cho cả thế giới - Khóa bí mật:
(n=3233, d=2753)— giữ kín p, q, φ(n)— hủy sau khi sinh khóa, vì ai có chúng sẽ tính đượcd
Bước ký một giá trị m = 65 (hình dung đây là hash đã rút gọn):
s = m^d mod n = 65^2753 mod 3233 = 588588 là chữ ký. Nó là một con số, không có nghĩa gì với người ngoài.
Bước verify:
m = s^e mod n = 588^17 mod 3233 = 65 ✓ khớp với hash gốcNgười kiểm tra chỉ dùng khóa công khai (n, e), dựng lại được 65, so với hash tài liệu. Khớp → chữ ký thật.
Vì sao nó hoạt động — ghép mục 3.4:
s^e = (m^d)^e = m^(d·e) = m^(15·φ(n)+1) = m = 65 (mod 3233)Chỉ là định lý Euler mặc áo mới. Không có phép màu nào cả.
3.7. Cửa sập nữa: tính nhân — và mối liên hệ với Bài 2
Nhớ ở phần trước tôi có nhắc RSA "thô" không an toàn vì tính nhân? Giờ ta thấy nó bằng số.
Với n=3233, d=2753:
chữ ký của 9 là 9^d mod n = 2071
chữ ký của 10 là 10^d mod n = 969
2071 · 969 mod 3233 = 2339
chữ ký của (9·10=90) = 90^d mod n = 2339 ← trùng khítKẻ tấn công nhân hai chữ ký hợp lệ để bịa ra chữ ký của một số thứ ba mà chưa từng được ký. Đây chính là lỗ hổng ở phần trước, giờ hiện ra bằng con số.
Và đây là chỗ hai bài nối vào nhau: hàm băm ở Bài 2 vô hiệu hóa đòn này. Kẻ tấn công tính ra chữ ký của số 90, nhưng để lợi dụng, hắn cần một tài liệu thật băm ra đúng 90. Tính kháng ảnh gốc của SHA-256 chặn hắn ở đó. Ba viên gạch — hàm băm, tính nhân, cửa sập phân tích — khóa vào nhau thành một hệ an toàn.
(Ghi chú: đây là lý do RSA thực tế không ký thẳng, mà bọc hash trong một lớp đệm PKCS#1 v1.5 hoặc PSS trước. Ta mổ lớp đệm đó ở Bài 5.)
3.8. Vì sao 2048 bit là đủ — đo bằng hai phép đo đối nghịch
Toàn bộ an toàn RSA nằm ở một bất đối xứng: dùng khóa thì nhanh, phá khóa thì chậm. Ta đo cả hai vế.
Vế nhanh — lũy thừa modulo (thao tác hợp pháp mỗi lần ký/verify):
RSA-512 : 0.016 ms
RSA-1024: 0.083 ms
RSA-2048: 0.186 ms
RSA-4096: 0.679 msNgay cả RSA-4096 cũng dưới một phần nghìn giây. Tăng kích thước khóa gần như miễn phí cho người dùng hợp pháp.
Vế chậm — phân tích thừa số (việc kẻ tấn công phải làm để lấy d):
bit n giây phân tích
30 811082989 0.0009
40 358284054113 0.0008
50 370319181540643 0.0009
60 995950942571488049 0.0380
70 524843017644846995183 0.2328Nhìn hai cột cạnh nhau. Với việc hợp pháp, mỗi lần nhân đôi bit chỉ tốn thêm ~4 lần thời gian — tăng tuyến tính-ish. Với việc phá, mỗi lần thêm 10 bit thời gian tăng mạnh, và độ khó tăng gần như hàm mũ theo số bit.
Đây là chiếc kéo mở rộng: người dùng hợp pháp và kẻ tấn công cùng leo thang theo số bit, nhưng kẻ tấn công leo dốc đứng hơn nhiều. Ngoại suy lên 2048 bit: thuật toán phân tích tốt nhất hiện nay (General Number Field Sieve) cần số phép toán vượt xa số nguyên tử trong vũ trụ quan sát được. Kỷ lục phân tích công khai mới đạt tới RSA-829 bit (năm 2020), tiêu tốn khoảng 2.700 năm CPU quy đổi.
Đó là nền tảng định lượng cho quy định độ dài khóa: RSA-1024 đã bị coi là không an toàn cho dài hạn, RSA-2048 là sàn hiện hành, RSA-3072/4096 cho nhu cầu bảo mật cao và dài hạn.
3.9. Nối vào PKI và đặc tả eSign
Giờ ráp mọi thứ vào ngữ cảnh công việc của anh.
Chữ ký anh thấy trong lab dài 256 byte — đó chính là 2048 bit, tức con số s nằm trong {0, ..., n-1} với n là RSA-2048. Khi verify PDF ở Bài 2 in ra Chữ ký raw: 256 byte, anh đang nhìn đúng con số s của mục 3.6, chỉ khác quy mô.
e = 65537 xuất hiện khắp nơi. Trong mọi chứng thư X.509 anh mở ra, số mũ công khai gần như luôn là 65537. Đây là số e ở mục 3.6, chọn giá trị này vì nó là số nguyên tố, dạng nhị phân 10000000000000001 chỉ có hai bit 1 nên verify rất nhanh, và đủ lớn để tránh vài đòn tấn công với e nhỏ.
Trong đặc tả eSign, ai giữ gì:
- Khóa bí mật
dnằm trong HSM của CA công cộng — không bao giờ rời ra. Đây là điều Bài 1 đã dự báo và giờ anh biếtdcụ thể là gì. - Khi người dùng bấm duyệt, HSM tính
s = (hash)^d mod n— đúng phép ký ở mục 3.6. - API 2.2 trả về chứng thư chứa khóa công khai
(n, e), để HTTT và cả bên thứ ba verify được.
Một điểm để thẩm định hệ thống: khi anh mở một chứng thư và thấy khóa công khai, hãy nhìn ba thứ — độ dài n (phải ≥ 2048 bit), giá trị e (nên là 65537), và thuật toán ký của chứng thư (không được là SHA-1, nối lại Bài 2). Ba con số đó nói cho anh biết chứng thư này còn giá trị bảo mật hay đã lỗi thời.
3.10. Một lời cảnh báo thẳng thắn
Mọi thứ tôi vừa giảng là để anh hiểu bản chất, tuyệt đối không phải để tự cài RSA dùng thật.
RSA sách giáo khoa như mục 3.6 — gọi là "textbook RSA" — mất an toàn khi dùng trực tiếp: nó tất định, có tính nhân, lộ thông tin qua nhiều kênh phụ. RSA thật cần lớp đệm chuẩn hóa (OAEP cho mã hóa, PSS hoặc PKCS#1 v1.5 cho ký), sinh số nguyên tố an toàn, chống tấn công thời gian (timing attack), và nhiều lớp phòng thủ khác mà thư viện như cryptography đã cài đúng.
Nguyên tắc từ Bài 2 vẫn nguyên giá trị: hiểu để thẩm định, không phải để tự chế. Anh học cơ chế bên trong để biết một hệ thống làm đúng hay sai — chứ việc cài đặt luôn giao cho thư viện đã được kiểm định.
3.11. Tự kiểm tra
- Vì sao
φ(n) = (p−1)(q−1)chỉ tính dễ khi biếtp, q? Người chỉ biếtnvướng ở đâu? - Định lý Euler nói
a^φ(n) ≡ 1 (mod n). Dòng này được dùng chính xác ở bước nào của phép verify? p, q, φ(n)phải hủy sau khi sinh khóa. Nếu lộ φ(n) thì kẻ tấn công làm được gì, và vì sao?- Textbook RSA có tính nhân (mục 3.7). Vì sao thêm hàm băm vào lại vô hiệu hóa được đòn khai thác tính nhân đó?
- Verify nhanh gấp bội nhờ
e = 65537. Nhìn dạng nhị phân của 65537, giải thích vì sao.