Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.
Mục lục
- 1 Lịch sử
- 2 Hoạt động
- 2.1 Mô tả sơ lược
- 2.2 Tạo khóa
- 2.3 Mã hóa
- 2.4 Giải mã
- 2.5 Ví dụ
- 2.6 Chuyển đổi văn bản rõ
- 2.7 Tạo chữ ký số cho văn bản
- 3 An ninh
- 4 Các vấn đề đặt ra trong thực tế
- 4.1 Quá trình tạo khóa
- 4.2 Tốc độ
- 4.3 Phân phối khóa
- 4.4 Tấn công dựa trên thời gian
- 4.5 Tấn công lựa chọn thích nghi bản mã
- 5 Xem thêm
- 6 Tham khảo
- 7 Liên kết ngoài
Lịch sửSửa đổi
Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts [MIT]. Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả.
Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh làm việc tại GCHQ, đã mô tả một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật.
Thuật toán RSA được MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983 [Số đăng ký 4.405.829]. Bằng sáng chế này hết hạn vào ngày 21 tháng 9 năm 2000. Tuy nhiên, do thuật toán đã được công bố trước khi có đăng ký bảo hộ nên sự bảo hộ hầu như không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu như công trình của Clifford Cocks đã được công bố trước đó thì bằng sáng chế RSA đã không thể được đăng ký.
Hoạt độngSửa đổi
Mô tả sơ lượcSửa đổi
Thuật toán RSA có hai khóa: khóa công khai [hay khóa công cộng] và khóa bí mật [hay khóa cá nhân]. Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân [bí mật] mới có thể giải mã được.
Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau: Bình muốn gửi cho An một thông tin mật mà Bình muốn duy nhất An có thể đọc được. Để làm được điều này, An gửi cho Bình một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bình nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại [như loại khoá thông thường chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bình cũng không thể mở lại được-không đọc lại hay sửa thông tin trong thư được nữa]. Sau đó Bình gửi chiếc hộp lại cho An. An mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật.
Tạo khóaSửa đổi
Giả sử An và Bình cần trao đổi thông tin bí mật thông qua một kênh không an toàn [ví dụ như Internet]. Với thuật toán RSA, An đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau:
- Chọn 2 số nguyên tố lớn p {\displaystyle p\,} và q {\displaystyle q\,} với p q {\displaystyle p\neq q} , lựa chọn ngẫu nhiên và độc lập.
- Tính: n = p q {\displaystyle n=pq\,} .
- Tính: giá trị hàm số Euler ϕ [ n ] = [ p 1 ] [ q 1 ] {\displaystyle \phi [n]=[p-1][q-1]\,} .
- Chọn một số tự nhiên
e
{\displaystyle e}
sao cho
1
<
e
<
ϕ
[
n
]
{\displaystyle 1