Thuật toán RSA là thuật toán chữ ký khóa công khai do Ron Rivest, Adi Shamir và Leonard Adleman sáng lập. RSA cũng có thể mã hóa/giải mã dữ liệu chung để trao đổi thông tin an toàn cùng với xác thực chữ ký số.
RSA dựa trên độ phức tạp của việc phân tích thừa số các số lớn. Không có phương pháp hiệu quả để phân tích số rất lớn, do đó suy ra khóa RSA tốn rất nhiều thời gian và sức mạnh xử lý.
RSA là thuật toán mật mã bất đối xứng sử dụng hai khóa khác nhau: khóa công khai và khóa riêng. Khóa công khai công khai cho mọi người, khóa riêng giữ bí mật. Khóa công khai chứa hai số, trong đó một số là tích của hai số nguyên tố lớn.
Trong mã hóa RSA, tin nhắn được mã hóa bằng khóa công khai (không cần giấu kín). Nhờ tính chất toán học của RSA, tin nhắn mã hóa bằng khóa công khai chỉ có thể giải mã bằng khóa riêng. Do đó cần một cặp khóa (công khai và riêng) để đọc tin nhắn.
Các bước trong thuật toán RSA
- 1. Sinh khóa
- Chọn hai số nguyên tố lớn P, Q (phải đủ lớn để khó đoán).
- Tính N = P × Q.
- Chọn khóa công khai (khóa mã hóa) E sao cho E không phải ước của (P−1) và (Q−1).
- Chọn khóa riêng (khóa giải mã) D thỏa mãn: (D × E) mod (P−1)×(Q−1) = 1.
- Mã hóa: CT = PTE mod N.
- Gửi CT đến người nhận.
- Giải mã: PT = CTD mod N.
- 2. Hàm Mã hóa/Giải mã: Sau khi có khóa, truyền tham số vào hàm tính ciphertext/plaintext bằng khóa tương ứng.
- Nếu bản rõ là m, bản mã c = me mod n.
- Nếu bản mã là c, bản rõ m = cd mod n.
- 3. Ví dụ: p = 17, q = 13. e = 5 (thỏa 1 < e < (p−1)(q−1)).
N = 17×13 = 91.
D = e−1 mod (p−1)(q−1) = 29.
Khóa công khai = (91, 5).
Khóa riêng = (91, 29).
Bản rõ m = 10 → bản mã = 105 mod 91 = 82.
Giải mã: 8229 mod 91 = 10 (khôi phục đúng).