Giải thích RSA

Mỗi khi trình duyệt hiện biểu tượng ổ khóa, một thông điệp được ký hay phần mềm kiểm tra một bản cập nhật, mật mã khóa công khai đang hoạt động, và RSA là dạng nổi tiếng nhất của nó. Ý tưởng của nó là chiếc khóa dùng để khóa thông điệp có thể công bố, trong khi chiếc khóa dùng để mở thì được giữ kín. Điều đáng chú ý là cả hệ thống dựa trên số học được dạy ở trường: số nguyên tố, phép nhân và số dư.

Hai số nguyên tố bí mật 61 và 53 cho mô-đun công khai 3233. Các chữ cái của HELLO trở thành 3000, 28, 2726, 2726 và 1307 với số mũ công khai 17, và số mũ riêng 2753 đưa 3000 trở lại 72
Hai số nguyên tố bí mật 61 và 53 cho mô-đun công khai 3233. Các chữ cái của HELLO trở thành 3000, 28, 2726, 2726 và 1307 với số mũ công khai 17, và số mũ riêng 2753 đưa 3000 trở lại 72

Vấn đề mà RSA giải quyết

Các thuật toán mã hóa truyền thống, từ phép dịch của Caesar đến AES hiện đại, dùng cùng một khóa để khóa và mở, nên hai bên trước hết phải chia sẻ riêng với nhau một khóa bí mật. Mật mã khóa công khai loại bỏ bước đó. Mỗi người có hai khóa: một khóa công khai mà bất kỳ ai cũng có thể dùng để mã hóa thông điệp gửi cho họ, và một khóa riêng chỉ họ nắm giữ và là thứ duy nhất giải mã được thông điệp đó. Whitfield Diffie và Martin Hellman mô tả ý tưởng này năm 1976, và một năm sau Ron Rivest, Adi Shamir và Leonard Adleman ở MIT tìm ra cách hiện thực hóa nó, được đặt tên RSA theo chữ cái đầu tên họ.

Martin Hellman (trái) và Whitfield Diffie (phải), 1977
Martin Hellman (trái) và Whitfield Diffie (phải), 1977

Tạo khóa

Chọn hai số nguyên tố lớn, p và q, rồi nhân chúng: n = p × q. Tính φ(n) = (p − 1)(q − 1), hàm phi Euler, đếm các số nhỏ hơn n không có ước chung nào với n. Chọn một số mũ công khai e không có ước chung với φ(n); 65537 là lựa chọn thông thường. Sau đó tìm số mũ riêng d sao cho e × d chia cho φ(n) dư 1. Thuật toán Euclid mở rộng làm việc này rất nhanh. Khóa công khai là cặp (e, n); khóa riêng là d. Với p = 61 và q = 53, ta được n = 3233, φ(n) = 3120, e = 17 và d = 2753.

Mã hóa và giải mã

Trước hết, thông điệp được chuyển thành một số m nhỏ hơn n. Để mã hóa, tính c = mᵉ mod n, tức số dư của mᵉ khi chia cho n. Để giải mã, tính cᵈ mod n. Định lý Euler bảo đảm rằng kết quả là m, vì e × d lớn hơn một bội của φ(n) đúng 1 đơn vị. Với các khóa ở trên, chữ A, mã 65, trở thành 65¹⁷ mod 3233 = 2790, và 2790²⁷⁵³ mod 3233 lại bằng 65. Những lũy thừa lớn như vậy không bao giờ được viết ra đầy đủ: bình phương liên tiếp tính chúng với một phép bình phương cho mỗi bit của số mũ, lấy số dư ở mỗi bước.

Chữ ký số

RSA cũng hoạt động theo chiều ngược lại. Nâng một thông điệp lên số mũ riêng, s = mᵈ mod n, tạo ra một chữ ký mà chỉ chủ của khóa mới tạo được. Ai cũng có thể kiểm tra nó bằng khóa công khai: nếu sᵉ mod n cho lại m, thông điệp đến từ người giữ d và không bị thay đổi trên đường đi. Trong thực tế, thứ được ký là một giá trị băm ngắn của thông điệp chứ không phải bản thân thông điệp. Những chữ ký như thế bảo vệ các bản cập nhật phần mềm, các trang web bảo mật và tài liệu điện tử.

Vì sao nó an toàn

Ai cũng thấy được n và e. Để tìm d, kẻ tấn công cần φ(n), và để tìm φ(n) họ cần p và q, nên phá RSA quy về việc phân tích n ra thừa số. Nhân hai số nguyên tố chỉ tốn của máy tính một phần nhỏ của một micro giây; tách tích đó trở lại thành hai số ban đầu được cho là cực kỳ khó. Số thử thách RSA lớn nhất được phân tích cho đến nay, RSA-250 năm 2020, có 829 bit và mất khoảng 2700 năm thời gian máy tính. Các khóa đang được dùng ngày nay có ít nhất 2048 bit, khoảng 617 chữ số.

Một bí mật được khám phá hai lần

Năm 1973, bốn năm trước RSA, nhà toán học người Anh Clifford Cocks đã tìm ra cùng một sơ đồ khi làm việc tại cơ quan tình báo GCHQ, dựa trên một ý tưởng của đồng nghiệp James Ellis. Công trình này được xếp vào loại tuyệt mật và chỉ được công bố năm 1997. Bản thân RSA được cấp bằng sáng chế ở Hoa Kỳ năm 1983; bằng sáng chế hết hạn vào tháng 9 năm 2000, hai tuần sau khi thuật toán được đưa vào phạm vi công cộng.

Ron Rivest, Adi Shamir và Len Adleman (từ trái sang phải)
Ron Rivest, Adi Shamir và Len Adleman (từ trái sang phải)

RSA trong thực tế

RSA thật không bao giờ mã hóa văn bản trực tiếp. Thông điệp được đệm bằng các byte ngẫu nhiên, theo một sơ đồ như OAEP, để cùng một thông điệp được mã hóa khác nhau mỗi lần và không để lộ quy luật nào. Vì RSA chậm, nó chủ yếu được dùng để trao đổi hoặc bảo vệ một khóa ngắn cho một thuật toán mã hóa đối xứng nhanh như AES, hoặc để ký. Những máy tính lượng tử đủ lớn có thể phân tích n ra thừa số rất nhanh bằng thuật toán Shor năm 1994, đó là lý do các phương pháp hậu lượng tử mới đang được đưa vào song song với RSA.

Tự khám phá

Hãy mở bản minh họa mã hóa RSA để tạo khóa từ các số nguyên tố của riêng bạn hoặc các số ngẫu nhiên có từ 2 đến 8 chữ số, xem thuật toán Euclid mở rộng tìm ra d từng hàng một, mã hóa hoặc ký một thông điệp từng ký tự một, và theo dõi phép bình phương liên tiếp cho bất kỳ ký tự nào. Sau đó để Eve phân tích n ra thừa số và xem thời gian cô ấy cần tăng lên thế nào theo độ lớn của các số nguyên tố.

Câu hỏi thường gặp

Vì sao RSA cần số nguyên tố?

Vì φ(n) chỉ dễ tính khi bạn biết n phân tích thành các số nguyên tố ra sao. Với n = p × q, trong đó p và q là số nguyên tố, φ(n) = (p − 1)(q − 1). Số nguyên tố cũng làm cho n khó phân tích nhất có thể so với độ lớn của nó, vì n hoàn toàn không có ước nhỏ nào.

Vì sao e thường là 65537?

65537 = 2¹⁶ + 1 là số nguyên tố và chỉ có hai chữ số 1 trong hệ nhị phân, nên mã hóa với nó chỉ cần 16 phép bình phương và một phép nhân. Nó cũng đủ lớn để tránh các điểm yếu của những số mũ rất nhỏ như 3.

RSA và Diffie–Hellman khác nhau thế nào?

Diffie–Hellman cho phép hai người thống nhất một khóa bí mật chung qua một kênh mở; tự nó không mã hóa hay ký bất cứ thứ gì. RSA mã hóa và ký trực tiếp bằng một cặp khóa. Cả hai đều dựa trên những bài toán dễ theo một chiều và khó theo chiều kia: phân tích thừa số với RSA, logarit rời rạc với Diffie–Hellman.

Có thể dùng các khóa của bản minh họa để mã hóa thật không?

Không. Các số nguyên tố của nó có nhiều nhất mười hai chữ số, nên bất kỳ khóa nào nó tạo ra đều có thể bị phân tích ra thừa số trong vài giây hoặc nhanh hơn, và nó mã hóa từng ký tự riêng lẻ mà không đệm. Nó được tạo ra để xem RSA hoạt động thế nào, không phải để bảo vệ bất cứ thứ gì.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở bản minh họa mã hóa RSA