RSA là một hệ thống mật mã để mã hóa khóa công khai và nó được sử dụng rộng rãi để bảo mật thông tin nhạy cảm, đặc biệt khi được gửi qua một mạng không an toàn bao gồm cả Internet.
Thuật toán RSA là thuật toán mật mã khóa bất đối xứng phổ biến nhất phụ thuộc vào thực tế toán học là nó chỉ đơn giản là khám phá và nhân các số nguyên tố lớn nhưng phức tạp để tính tích của chúng. Nó cần cả khóa riêng tư và khóa công khai.
Ví dụ về Thuật toán RSA
Hãy để chúng tôi lấy một ví dụ về quy trình này để tìm hiểu các khái niệm. Để dễ đọc, nó có thể viết các giá trị ví dụ cùng với các bước thuật toán.
-
Chọn hai số nguyên tố lớn P và Q
Cho P =47, Q =17
-
Tính N =P x Q
Ta có, N =7 x 17 =119.
-
Chọn khóa công khai (tức là khóa mã hóa) E sao cho nó không phải là phần tử của (P -1) x (Q - 1)
-
Hãy để chúng tôi tìm (7 - 1) x (17 -1) =6 x 16 =96
-
Các thừa số của 96 là 2, 2, 2, 2, 2 và 3 (vì 96 =2 x 2 x 2 x 2 x 2 x 3).
-
Do đó, nó có thể chọn E sao cho không có thừa số nào của E là 2 và 3. Chúng ta không thể chọn E là 4 (vì nó có 2 là thừa số), 15 (vì nó có 3 là thừa số) và 6 (vì nó có cả 2 và 3 là nhân tố).
-
Hãy để chúng tôi chọn E là 5 (nó có thể là bất kỳ số nào khác không phải là nhân tố của nó là 2 và 3).
-
-
Chọn khóa riêng tư (tức là khóa giải mã) D bao gồm các mã đúng sau:
(D x E) mod (P - 1) x (Q - 1) =1
-
Hãy để chúng tôi thay thế các giá trị của E, P và Q trong phương trình.
-
Ta có (D x 5) mod (7 - 1) x (17 - 1) =1.
-
Tức là, (D x 5) mod (6) x (16) =1.
-
Tức là, (D x 5) mod (96) =1
-
Sau một số phép tính, chúng ta hãy lấy D =77. Khi đó giá trị sau là đúng:(77 x 5) mod (96) =385 mod 96 =1, đó là những gì chúng ta muốn.
-
-
Để mã hóa, hãy tính toán văn bản mật mã (CT) từ văn bản thuần túy (PT) như sau:
CT =PT E mod N
Giả sử rằng chúng tôi muốn mã hóa văn bản thuần túy 10. Sau đó, chúng tôi có
CT =10 5 mod 119 =100000 mod 119 =40.
-
Gửi CT dưới dạng văn bản mật mã đến người nhận.
Gửi 40 dưới dạng văn bản mật mã đến người nhận.
-
Để giải mã, hãy tính toán văn bản thuần túy (PT) từ văn bản mật mã (CT) như sau:
PT =CT D mod N
Nó thực hiện những điều sau:
PT =CT D mod N
Đó là,
PT =40 77 mod 119 =10, là bản rõ ban đầu của bước 5.