Cách tính toán thuật toán RSA bằng ví dụ minh họa

RSA là hệ mã khóa công khai phổ biến để bảo mật thông tin nhạy cảm khi truyền qua mạng không an toàn như Internet.

RSA là thuật toán mật mã khóa bất đối xứng phổ biến nhất, dựa trên thực tế toán học: dễ dàng tìm và nhân các số nguyên tố lớn nhưng rất khó phân tích tích của chúng. RSA cần cả khóa riêng và khóa công khai.

Ví dụ minh họa thuật toán RSA

Để dễ hiểu, chúng ta sẽ viết giá trị ví dụ song song với các bước thuật toán.

1. Chọn hai số nguyên tố lớn P và Q
   P = 7, Q = 17 (Lưu ý: bài gốc viết P=47 nhưng tính toán dùng 7).
2. Tính N = P × Q
   N = 7 × 17 = 119.
3. Chọn khóa công khai (khóa mã hóa) E sao cho E không chia hết cho bất kỳ ước số nào của (P−1)×(Q−1).
   
   • (7−1)×(17−1) = 6×16 = 96.
   • Ước số của 96: 2, 2, 2, 2, 2, 3 (96 = 2⁵ × 3).
   • E không được có ước 2 hoặc 3. Loại bỏ 4 (có 2), 15 (có 3), 6 (có cả 2 và 3).
   • Chọn E = 5 (số không có ước 2, 3).
4. Chọn khóa riêng (khóa giải mã) D thỏa mãn: (D × E) mod [(P−1)×(Q−1)] = 1.
   
   • (D × 5) mod 96 = 1.
   • Thử D = 77: (77 × 5) mod 96 = 385 mod 96 = 1 → Đúng.
5. Mã hóa: Ciphertext CT = PT^E mod N.
   Giả sử bản rõ PT = 10.
   CT = 10⁵ mod 119 = 100000 mod 119 = 40.
6. Gửi CT = 40 đến người nhận.
7. Giải mã: Plaintext PT = CT^D mod N.
   PT = 40⁷⁷ mod 119 = 10 → Khôi phục đúng bản rõ ban đầu.