Kiến thức nền

Liên quan

Bản thiết kế · 1.970 từ · 8 phút đọc

Toán học RSA, từng dòng

Định lý Euler, nghịch đảo modular, và tại sao `(m^e)^d ≡ m (mod n)` thực sự hoạt động — hướng dẫn về toán học mà bài viết RSA lướt qua trong một khối code.

Mục lục
  1. TL;DR
  2. Thiết lập: Số học modular
  3. Định lý nhỏ Fermat
  4. Hàm totient Euler và định lý Euler
  5. Đồng nhất thức RSA: Tại sao (m^e)^d ≡ m (mod n)
  6. Tìm d: Thuật toán Euclid mở rộng
  7. Tại sao e = 65537
  8. Các số nguyên tố p và q
  9. Đệm: Phần toán học bỏ qua
  10. Điều toán học thực sự chứng minh

#TL;DR

Việc tạo khóa RSA chỉ tốn tám dòng Python. Tám dòng đó mã hóa 200 năm lý thuyết số: định lý nhỏ Fermat, hàm totient Euler, định lý Euler, đồng nhất thức Bézout, và thuật toán Euclid mở rộng. Bài viết này đi qua toán học đằng sau phương trình (m^e)^d ≡ m (mod n) — tại sao nó hoạt động, mỗi phần đang làm gì, và tại sao e = 65537 là số mũ công khai tiêu chuẩn ngành. Không phần nào yêu cầu toán học vượt quá đại số trung học. Tất cả đều cần thiết để RSA không chỉ là đoán mò.

#Thiết lập: Số học modular

Mọi thứ trong RSA xảy ra modulo một số. Làm việc modulo n nghĩa là bạn chỉ quan tâm đến phần dư khi chia cho n. Hai số “giống nhau mod n” nếu hiệu của chúng là bội của n:

17 ≡ 5 (mod 12)          vì 17 - 5 = 12
100 ≡ 4 (mod 12)         vì 100 - 4 = 96 = 8 × 12
-1 ≡ 11 (mod 12)         vì -1 - 11 = -12

Số học modular bảo tồn phép cộng và nhân. Nếu a ≡ b (mod n) và c ≡ d (mod n), thì a + c ≡ b + d (mod n) và a × c ≡ b × d (mod n). Điều này có nghĩa là bạn có thể giảm tại bất kỳ điểm nào — bạn không phải tính các giá trị trung gian khổng lồ miễn là bạn tiếp tục lấy mod n dọc đường.

Lũy thừa cũng giảm: a^k mod n có thể được tính mà không bao giờ để a^k lớn. Lũy thừa bằng bình phương tính nó trong khoảng log(k) bước:

def mod_exp(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return result

mod_exp(65, 17, 3233)  # 65^17 mod 3233 = 2790

pow(base, exp, mod) có sẵn trong Python làm điều này cho bạn. Đó là engine làm cho RSA thực tế trên các kích thước khóa thực — nâng một số 2048-bit lên lũy thừa 2048-bit mà không có sự bùng nổ trung gian.

#Định lý nhỏ Fermat

Năm 1640, Pierre de Fermat tuyên bố một kết quả sẽ trở thành một trong những nền tảng của mật mã khóa công khai:

Nếu p là số nguyên tố và a không chia hết cho p, thì a^(p-1) ≡ 1 (mod p).

Ví dụ, với p = 7 và a = 3:

3^6 = 729 = 104 × 7 + 1
nên 3^6 ≡ 1 (mod 7)

Kiểm tra bất kỳ a nào từ 1 đến 6, và a^6 mod 7 luôn là 1. Đây không phải sự trùng hợp — nó phản ánh cấu trúc của nhóm nhân của các số nguyên mod p.

Định lý Fermat gần với điều RSA cần, nhưng không hoàn toàn. RSA không hoạt động modulo một số nguyên tố — nó hoạt động modulo n = pq, tích của hai số nguyên tố. Cho điều đó, chúng ta cần khái quát hóa.

#Hàm totient Euler và định lý Euler

Khái quát hóa đến từ Leonhard Euler một thế kỷ sau. Ông định nghĩa hàm totient φ(n) là số các số nguyên dương nhỏ hơn n nguyên tố cùng nhau với n (không chia sẻ thừa số nào với n ngoài 1):

φ(1) = 1
φ(7) = 6    (1, 2, 3, 4, 5, 6 đều nguyên tố cùng nhau với 7)
φ(12) = 4   (1, 5, 7, 11 nguyên tố cùng nhau với 12)

Khi p là số nguyên tố, mọi thứ từ 1 đến p-1 nguyên tố cùng nhau với p, nên φ(p) = p - 1. Điều này khôi phục Fermat.

Tính chất quan trọng cho RSA là cách φ cư xử trên các tích của các số nguyên tố cùng nhau:

φ(mn) = φ(m) × φ(n)        khi gcd(m, n) = 1

Đặc biệt, cho hai số nguyên tố khác nhau p và q:

φ(pq) = φ(p) × φ(q) = (p - 1)(q - 1)

Đây là công thức tạo khóa RSA sử dụng. Nếu bạn biết p và q, bạn có thể tính φ(n) trực tiếp. Nếu bạn chỉ biết n = pq, bạn sẽ phải phân tích n trước — và phân tích n lớn là vấn đề RSA giả định là khó.

Định lý Euler khái quát Fermat:

Nếu gcd(a, n) = 1, thì a^φ(n) ≡ 1 (mod n).

Cho n = pq với p và q là số nguyên tố khác nhau:

a^((p-1)(q-1)) ≡ 1 (mod pq)     khi gcd(a, pq) = 1

Đây là phương trình mọi thứ khác trong RSA được xây dựng trên.

#Đồng nhất thức RSA: Tại sao (m^e)^d ≡ m (mod n)

RSA chọn một số mũ công khai e và một số mũ riêng d sao cho:

e × d ≡ 1 (mod φ(n))

Tức là, d là nghịch đảo modular của e modulo φ(n). Nó tồn tại khi và chỉ khi gcd(e, φ(n)) = 1, đó là lý do e phải nguyên tố cùng nhau với φ(n).

Với mối quan hệ đó, đây là lý do mã-hóa-rồi-giải-mã đưa bạn trở lại thông điệp gốc. Cho bất kỳ thông điệp m nào:

(m^e)^d = m^(ed)                             theo quy tắc số mũ
        = m^(1 + k·φ(n))                     vì ed ≡ 1 (mod φ(n)), nên ed = 1 + k·φ(n) cho một số nguyên k
        = m · m^(k·φ(n))                     tách số mũ
        = m · (m^φ(n))^k                     lại theo quy tắc số mũ
        ≡ m · (1)^k  (mod n)                 theo định lý Euler, nếu gcd(m, n) = 1
        ≡ m (mod n)

Mã hóa xáo trộn với e. Giải mã hóa gỡ với d. Hai phép toán hủy bỏ nhau vì ed là “gần như 1” (cụ thể: 1 cộng với một bội của φ(n)), và định lý Euler nói nâng bất cứ thứ gì nguyên tố cùng nhau với n bởi một bội của φ(n) cho bạn 1.

Trường hợp biên — khi gcd(m, n) ≠ 1, tức là, m là bội của p hoặc q — thực sự vẫn hoạt động bởi một lập luận riêng sử dụng Định lý Phần Dư Trung Quốc. Nhưng trường hợp này không thú vị về mặt mật mã: nếu “thông điệp” của bạn tình cờ là một bội của một trong các thừa số nguyên tố của n, bạn đã vừa tiết lộ thừa số đó, điều nào dù sao cũng là thảm họa.

#Tìm d: Thuật toán Euclid mở rộng

Cho e và φ(n), làm thế nào để chúng ta tính d sao cho e × d ≡ 1 (mod φ(n))?

Công cụ là thuật toán Euclid mở rộng. Thuật toán Euclid chuẩn tìm gcd(a, b) bằng chia lặp đi lặp lại. Phiên bản mở rộng còn tính các số nguyên x và y sao cho:

a × x + b × y = gcd(a, b)                    đồng nhất thức Bézout

Nếu gcd(e, φ(n)) = 1, thì tồn tại các số nguyên x và y với:

e × x + φ(n) × y = 1

Lấy cả hai bên mod φ(n):

e × x ≡ 1 (mod φ(n))

Vậy d = x mod φ(n). Python có cái này được xây sẵn như pow(e, -1, phi) kể từ 3.8:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

phi = 3120
e = 17
g, d, _ = extended_gcd(e, phi)
d = d % phi   # chuẩn hóa về [0, phi)
# d = 2753, và thực sự 17 * 2753 = 46801 = 15 * 3120 + 1

Đây là cách con số thần kỳ d = 2753 trong bài RSA thực sự được tính. Không có đoán mò, không có tìm kiếm — đó là hệ quả xác định của thuật toán Euclid mở rộng chạy trên số mũ công khai và totient.

#Tại sao e = 65537

Trong thực tế, số mũ công khai e không được chọn ngẫu nhiên. Có một quy ước mạnh — gần như một quy ước phổ quát — rằng e = 65537. Tại sao con số cụ thể này?

65537 là 2^16 + 1. Nó có ba tính chất hữu ích:

  • Nó là số nguyên tố. Một e nguyên tố tự động nguyên tố cùng nhau với bất kỳ φ(n) nào (trừ khi φ(n) chia hết cho 65537, điều nào cực kỳ không có khả năng cho các số nguyên tố ngẫu nhiên p và q).
  • Biểu diễn nhị phân của nó thưa thớt. 65537 trong nhị phân là 10000000000000001. Lũy thừa bằng bình phương với một số mũ 17-bit chỉ yêu cầu 17 bình phương và 1 phép nhân, làm cho các phép toán khóa công khai (mã hóa và xác minh chữ ký) rất nhanh.
  • Nó đủ lớn để tránh các cuộc tấn công số mũ nhỏ. Các cuộc tấn công số mũ thấp khét tiếng trên RSA (đặc biệt với e = 3) khai thác sự thật rằng nếu thông điệp m đủ nhỏ, m^e có thể nhỏ hơn n, nghĩa là giảm modular không thực sự giảm gì. Một kẻ tấn công sau đó có thể chỉ tính căn bậc e của ciphertext trên các số nguyên. e = 65537 đủ lớn để m^e thực sự luôn vượt n cho bất kỳ thông điệp không-suy-biến nào, đóng cuộc tấn công này.

Bạn có thể chọn các giá trị khác của e, nhưng 65537 là lựa chọn Goldilocks: nguyên tố, nhanh để lũy thừa, và đủ lớn để an toàn. Mọi thư viện TLS bạn từng sử dụng có lẽ đang tạo khóa RSA với e = 65537.

#Các số nguyên tố p và q

Tạo khóa chọn hai số nguyên tố và nhân chúng. Một vài điều quan trọng về cách chúng được chọn:

  • p và q phải lớn. Bảo mật của RSA phụ thuộc vào phân tích n = pq là không khả thi. Các khóa hiện đại sử dụng các số nguyên tố 1024-bit, tạo ra n 2048-bit. Các khóa 4096-bit đang trở thành chuẩn cho các khóa dài hạn.
  • p và q phải có kích thước xấp xỉ nhau (trong vài bit). Nếu một cái nhỏ hơn nhiều so với cái kia, phương pháp phân tích Fermat hoặc phương pháp đường cong elliptic có thể tìm thấy thừa số nhỏ hơn nhanh chóng.
  • p - 1 và q - 1 không nên chỉ có các thừa số nhỏ. Nếu không thuật toán p-1 Pollard có thể phân tích n hiệu quả. “Số nguyên tố mạnh” được thiết kế để tránh điều này, mặc dù các triển khai RSA hiện đại nói chung coi điều này là một vấn đề đã-giải-quyết-không-phải-vấn-đề vì xác suất vô tình đánh trúng một số nguyên tố yếu với tạo ngẫu nhiên là cực kỳ nhỏ.
  • p và q phải được tạo độc lập và ngẫu nhiên. Nếu hai khóa RSA trong tự nhiên tình cờ chia sẻ một thừa số nguyên tố, gcd(n1, n2) ngay lập tức tiết lộ thừa số chia sẻ và phá cả hai khóa. Điều này đã xảy ra trong thực tế — năm 2012 các nhà nghiên cứu thấy rằng một phần không nhỏ các khóa HTTPS trên internet công cộng chia sẻ các thừa số với nhau do các RNG bị hỏng trong các thiết bị nhúng.

Các số nguyên tố được tạo bằng cách chọn một số lẻ ngẫu nhiên với độ dài bit đúng và chạy một kiểm tra tính nguyên tố xác suất (thường là Miller-Rabin) cho đến khi một số qua. Một số lẻ ngẫu nhiên 1024-bit có xác suất khoảng 1-trên-700 là số nguyên tố, nên bạn kiểm tra vài trăm ứng viên trước khi tìm thấy một.

#Đệm: Phần toán học bỏ qua

RSA toán học trần trụi được mô tả ở đây — “mã hóa m là m^e mod n” — được gọi là RSA sách giáo khoa, và nó không an toàn để sử dụng trong thực tế. Nó có một số điểm yếu:

  • Nó xác định. Mã hóa cùng thông điệp hai lần cho cùng ciphertext. Một kẻ tấn công có thể nói khi nào bạn đã gửi cùng thông điệp lần nữa, và có thể xây dựng từ điển.
  • Nó biến dạng được. Cho c = m^e mod n, một kẻ tấn công có thể tính c × 2^e mod n, giải mã thành 2m mod n — một ciphertext trông hợp pháp mà kẻ tấn công vừa xây dựng từ của bạn.
  • Các thông điệp ngắn dễ bị tấn công bởi tấn công số mũ nhỏ.
  • Các thông điệp giống hệt nhau được gửi đến nhiều người nhận (tấn công Håstad) đôi khi có thể được khôi phục.

RSA thực bọc thông điệp trong một phương án đệm ngẫu nhiên hóa và cấu trúc đầu vào trước lũy thừa. RSA hiện đại sử dụng OAEP (Optimal Asymmetric Encryption Padding) cho mã hóa và PSS (Probabilistic Signature Scheme) cho chữ ký. Các hệ thống cũ sử dụng đệm PKCS#1 v1.5, đã có nhiều cuộc tấn công chống lại nó (Bleichenbacher, 1998) tiếp tục được khám phá lại trong các triển khai mới.

Điểm mấu chốt: toán học chúng ta vừa đi qua là nguyên thủy. Hệ thống mật mã sử dụng nó cẩn thận hơn nhiều. Bài RSA âm thầm bỏ qua sự phân biệt này vì lý do rõ ràng; sự khác biệt thực sự giữa RSA sách giáo khoa và RSA-OAEP là các thập kỷ tấn công và bản vá.

#Điều toán học thực sự chứng minh

Nếu bạn đã theo dõi điều này: bảo mật của RSA phụ thuộc vào một phỏng đoán — rằng phân tích n lớn là không khả thi về mặt tính toán — cộng với một vài định lý khoảng 300 năm tuổi. Phỏng đoán là điều máy tính lượng tử sẽ phá. Các định lý là cùng các định lý Euler đã chứng minh vào thế kỷ 18 và sẽ không đi đâu.

Bài RSA mô tả việc tạo khóa là “toán học, bằng chứng, thuật toán” mà Rivest đã tính ra sau một seder Passover. Điều anh đã tập hợp đêm đó cụ thể là: định lý Euler từ 1761, thuật toán Euclid mở rộng từ 300 TCN, và một lựa chọn các số nguyên tố mà tích của chúng sẽ làm cho vấn đề phân tích khó. Sự xuất sắc nằm trong sự tổng hợp. Các mảnh ghép đã ở đó — anh chỉ phải thấy rằng chúng khớp với nhau thành một ổ khóa và chìa khóa.

Năm mươi năm sau, mọi người từng bảo mật một kết nối web đã sử dụng cùng tám dòng đó.