thuật toán RSA

chưa kịp đọc các bác đọc bản tiếng việt này nhé cho nó dễ làm ka ka.
Mô tả sơ lược
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 : Bob muốn gửi cho Alice một thông tin mật mà Bob muốn duy nhất Alice có thể đọc được. Để làm được điều này, Alice gửi cho Bob một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bob 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ả Bob 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 đó Bob gửi chiếc hộp lại cho Alice. Alice 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.
[sửa]Tạo khóa
Giả sử Alice và Bob 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, Alice đầ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 và với , lựa chọn ngẫu nhiên và độc lập.
Tính: .
Tính: giá trị hàm số Ơle .
Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với .
Tính: d sao cho .
Một số lưu ý:
Các số nguyên tố thường được chọn bằng phương pháp thử xác suất.
Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
Bước 5 có thể viết cách khác: Tìm số tự nhiên sao cho cũng là số tự nhiên. Khi đó sử dụng giá trị .
Từ bước 3, PKCS#1 v2.1 sử dụng thay cho ).
Khóa công khai bao gồm:
n, môđun, và
e, số mũ công khai (cũng gọi là số mũ mã hóa).
Khóa bí mật bao gồm:
n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
d, số mũ bí mật (cũng gọi là số mũ giải mã).
Một dạng khác của khóa bí mật bao gồm:
p and q, hai số nguyên tố chọn ban đầu,
d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1),
(1/q) mod p (thường được gọi là iqmp)
Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.
Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.
[sửa]Mã hóa
Giả sử Bob muốn gửi đoạn thông tin M cho Alice. Đầu tiên Bob chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ.
Lúc này Bob có m và biết n cũng như e do Alice gửi. Bob sẽ tính c là bản mã hóa của m theo công thức:

Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bob gửi c cho Alice.
[sửa]Giải mã
Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm được m từ c theo công thức sau:

Biết m, Alice tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có
.
Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên:

và

Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có:
.
hay:
.
[sửa]Ví dụ
Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn.
Lấy:
p = 61 — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa)
q = 53 — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa)
n = pq = 3233 — môđun (công bố công khai)
e = 17 — số mũ công khai
d = 2753 — số mũ bí mật
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
encrypt(m) = me mod n = m17 mod 3233
với m là văn bản rõ. Hàm giải mã là:
decrypt(c) = cd mod n = c2753 mod 3233
với c là văn bản mã.
Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
encrypt(123) = 12317 mod 3233 = 855
Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
decrypt(855) = 8552753 mod 3233 = 123
Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân.