II. Hệ bảo mật khóa công khai và hệ bảo mật RSA
Một hệ f= trong đó:
M là một tập các không gian bản rõ.
C là tập các không gian bản rõ.
K là tập hợp các không gian khóa.
Được gọi là một hệ mã mật nếu thỏa mãn 3 tính chất sau:
- Với mỗi kẻ K cho ta hai ánh xạ E_k: M → C (gọi là ánh xạ m ã hóa với khóa k) và ánh xạ Dk: C → M được gọi là ánh xạ giải mã.
- Hai cặp ánh xạ trên thỏa mãn tính chất D_k (E_k(M)) = M.
Người ta chia các hệ mã làm hai loại chính là hệ mã cổ điển và hệ mã hiện đại (hay hệ mã hóa công khai). Các hệ mã cổ điển thực hiện việc bảo mật đều dựa trên cơ sở là có một khóa dùng chung cho cả việc lập mã và việc giải mã.
Các hệ mã hóa công khai được nghiên cứu và phát triển từ những năm 1970. Ý tưởng cơ bản của các hệ mã này là xây dựng những hệ thống sao cho mỗi người tham gia vào quá trình truyền tin (người nhận tin và người gửi tin) sẽ có hai khóa khác nhau: Một khóa công khai dùng để lập mã và một khóa bảo mật dùng để giải mã. Khóa công khai được công khai hóa cho mội người, còn khóa bảo mật của mỗi người thì được giữ bí mật.
Thông tin trước khi được gửi đi được mã hóa bằng khóa công khai của người nhận. Chỉ có người nhận mới có khả năng giải mã bản mã bằng khóa bí mật của mình, bởi vì thời gian giải mã sẽ tốn hàng tỉ năm nếu chỉ biết khóa công khai. Độ bảo mật của các hệ mã công khai được bảo đảm bằng độ phức tạp tính toán rất cao của thao tác tìm số nguyên tố lớn nhất và phân tích một số nguyên tố lớn thành tích các thừa số. Ta giả sử trong hệ mã mật khóa công khai, khóa mã hóa là E và khóa giải mã là D, thông điệp cần gửi là M. Để hệ thống mã hóa hoạt động được , các điều kiện sau đây phải được thõa mãn:
- Dk(Ek(M)) = M đối với mọi thông điệp M
- Tất cả các cặp (D,E) là phân biệt.
- Việc phát sinh D từ E là khó ngang với việc đọc M.
- Cả D và E đều được tính dễ dàng.
Điều kiện đầu tiên là tính chất mật mã căn bản, hai điều kiện sau cung cấp tính an toàn và điều kiện cuối cùng làm cho hệ thống trở nên dễ dùng.
Hệ bảo mật khóa công khai RSA được đưa ra bởi ca tác giả R.Rivest, A.Shamir và L. Adleman thỏa mãn được các điều kiện trên và đã được ứng dụng nhiều vào việc mã hóa và mật dữ liệu do tính năng vượt trội của nó về mã hóa bảo mật dữ liệu so với nhiều thuật toán khác.

III. Thuật toán RSA
1. Bước khởi đầu của thuật toán
a. Chọn hai số nguyên tố ngẫu nhiên p và q có hàng trăm chữ số và tính tích n = p*q. Sau đó tính PHI(n) = (p-1)(q-1).
b. Tìm số d sao cho d và PHI(n) là nguyên tố cùng nhau (d,PHI(n)) = 1.
c. Tìm số e thõa mãn d*e = =1 (Mod n)
Trong đó d và e lần lượt là các khóa giải mã và khóa công khai. Hàm mã hóa là E_k = M_e mod n.
Hàm giải mã là: Dk = (E_k)d mod n.
2. Mô tả thuật toán:
Bước 1: Chọn p,q là hai số nguyên tố và tính n=p*q.
Số n được gọi là Modul của hệ mã.
Bước 2: Tìm ngẫu nhiên số e thỏa mãn các điều kiện sau đây:
a) 1 < e < n.
b) Tính f(n) = (p-1)* (q-1). e và f(n) nguyên tố cùng nhau, số e tìm được gọi là số mũ mã hóa.
Bước 3: Tính d sao cho d*e mod f(n) = 1;
Với 1 < d < n. d được gọi là số mũ giải mã.
Khi đó khóa công khai là cặp (e,n) và khóa mật là cặp số (d,e).
3. Cách mã hóa và giải mã mã.
Gọi x thuộc [0,…, n-1] là số cần mã hóa; E và D lần lượt là các hàm mã hóa và hàm giải mã.
Thao tác mã hóa:
Người gửi sử dụng khóa công khai (e,n) của người nhận để mã hóa thông tin x cần gửi đi. Như vậy, người gửi sẽ gửi cho người nhận một thông điệp dưới dạng mã hóa là: c = E(x) = x^e % n
Thao tác giải mã:
Người nhận sử dụng khóa mã mật của mình để giải mã bản mã vừa nhận được thành bản rõ của nó. Tức là tính: x = D(c) = c^d % n.

IV. Thuật toán tính xe mod n
Trong hệ RSA khi mã hóa hoặc giải mã ta phải tính c = x^e % n và x = c^d % n.
Trong đó e, n, d là những số có hàng trăm chữ số. Các vấn đề nảy sinh mã hóa và giải mã là phải giảm thiểu được việc tính tính toán và không gian bộ nhớ. Sau đây tôi sẽ trình bày một thuật toán giải quyết cả hai vấn đề trên. Ý tưởng của thuật toán là đưa xe thành x^2*k * x^j, j = 0 hoặc 1. Nếu j = 0 thì tính x = x* x mod n; Nếu j = 1 thì tính y = x * y mod n; Sau mỗi bước e = e2 hoặc e = e -1 tương ứng với j =0 hay 1; Sau đây là cài đặt một hàm của thuật toán:
Function PowerMod(x: SoLon; e: SoLon; N:SoLon): SoLon
Var y: SoLon;
Begin
Y:=1;
While (e mod 2 = 0) do
Begin
While (e mod 2) do
Begin
x:=x*x mod N;
e:=e2;
End;
y:=x*y mod N;
e:=e-1;
end;
PowerMod:=y;
End;
Chú ý rằng mỗi phép toán “gán”, “trừ”… sử dụng trong thuật toán đều phải được xây dựng trước trên cấu trúc “SoLon” biểu diễn các số có hàng trăm chữ số.