1. Giao thức ba bước Shamir

Tìm hiểu các giao thức, các thuật toán thật là hay, nhưng điều mình thường thắc mắc là tại sao người ta lại nghĩ ra nó nhỉ? Tại sao người ta lại nghĩ ra các phát minh, điều này còn thú vị hơn cả chính phát minh đó, vì nó chính là thực tiễn, nó là nơi vấn đề được đặt ra, nơi bài toán được đặt ra, là nền tảng của tri thức.

RSA không phải là một giao thức, nó là một thuật toán mã hoá, nhưng nó lại chứa đựng một giao thức rất thú vị. Mình thấy một số thuật toán mã hoá làm tối giản giao thức nhờ toán học như vậy, và nó thực sự là điều kỳ diệu của toán học.

Thuật toán RSA đượ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ả.

Chữ S lấy từ tên của nhà mật mã học người Israel - Adi Shamir, và Shamir cũng là tên của giao thức sơ khai của thuật toán mã hoá RSA. Mình sẽ mô tả nó ngay sau đây bằng một câu chuyện lãng mạn:
Bob yêu Alice và muốn gửi thư cho cô mà không bị bố cô, ông Mallory đọc trộm, chỉnh sửa bức thư hay mạo danh Bob bằng một bức thư tồi tệ, ông Mallory không ủng hộ đôi trẻ, rất hay soi xét và khó tính.

Bob và Alice đã giải quyết vấn đề như sau:
- Bước 1: Bob viết thư cho Alice rồi đặt bức thư vào một chiếc hộp có 2 ổ khoá, anh ta dùng khoá e của mình để khoá một ổ khoá lại. Chiếc hộp chỉ có thể mở ra nếu 2 bên ổ khoá đều được mở, vì thế Bob yên tâm gửi chiếc hộp đến cho Alice.
- Bước 2: Alice nhận được chiếc hộp trong đó có bức thư của người yêu gửi cho. Nhưng cô ấy không có chìa khoá của Bob để có thể mở bức thư, cô ấy lại lấy thêm khoá k của mình để khoá vào ổ khoá còn lại của chiếc hộp. Sau đó Alice gửi chiếc hộp lại cho Bob.
- Bước 3: Bob nhận lại chiếc hộp, anh ta dùng khoá e của mình để mở ổ khoá mà mình đã khoá. Sau đó gửi lại chiếc hộp cho Alice. Vậy là chiếc hộp chỉ còn lại ổ khoá của Alice, và khi cô ấy nhận được, cô có thể dùng khoá k của mình để mở chiếc hộp và xem bức thư người yêu gửi cho mình.
Ông Mallory trong cả 3 lần đôi trẻ gửi đi gửi lại nếu có bắt được chiếc hộp thì cũng không mở ra được, vì nó luôn được khoá.

2. Thuật toán RSA

Như đã nói ở trên, thuật toán RSA thực hiện giao thức ba bước Shamir, nhưng nó chỉ cần 1 bước thay vì 3 nhờ sức mạnh của toán học.
Trước hết chúng ta công thức hoá giao thức 3 bước Shamir đã nhé:
D(d,E(k,E(e,m))) = E(k,m)
Trong đó:

• m (message) là văn bản rõ thông điệp Bob cần gửi cho Alice
• e là chìa khoá của Bob
• k là chìa khoá của Alice
• E là thuật toán mã hoá
• D là thuật toán giải mã Kết quả của công thức trên là những gì Alice nhận được E(k,m), Alice chỉ cần dùng chìa khoá k của mình để giải mã thông điệp: D(k,E(k,m))=m

Vậy đấy, họ cứ phải gửi đi, gửi lại đến 3 lượt Bob mới gửi được thư cho người yêu. Thật tốt biết bao nếu chỉ cần gửi thư một lần mà vẫn qua mặt được ông Mallory nhỉ? Alice không thể đưa cho Bob khoá k của mình dù gần gũi đến mấy, ai cũng có bí mật riêng của mình, đó là nguyên tắc bảo mật cơ bản. Ngược lại Bob cũng không thể trao khoá e của mình cho Alice.
Họ đã phát minh ra một điều tuyệt vời, Alice sẽ trao cho Bob chìa khoá kp tương ứng với chìa khoá k của mình, đây là chiếc chìa khoá đặc biệt, chỉ dùng để mã hoá mà không dùng để giải mã được, những gì được mã hoá bằng kp thì có thể được giải mã bằng k.

Vậy thì Bob chỉ cần:
E(kp,m)
Rồi gửi cho Alice, thế là xong. Alice sẽ dùng khoá k của mình để giải mã:
D(k,E(kp,m))

Alice gửi message cho Bob cũng theo cách tương tự

Bạn có thể ko quan tâm đến cơ sở toán học phức tạp của cơ chế mã hoá bất đối xứng, nhưng cách hoạt động của thuật toán RSA chỉ đơn giản như vậy thôi.
Tham khảo:
https://en.wikipedia.org/wiki/Three-pass_protocol
https://en.wikipedia.org/wiki/RSA_(cryptosystem)