III. Mật mã RSA - Thực hiện
1. Kiến thức chuẩn bị
1.1. Số nguyên tố
Số nguyên tố là khái niệm cơ bản trong toán học mà chúng ta đã học từ những năm lớp 8. Một số tự nhiên lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai ước dương duy nhất là 1 và chính nó. Chẳng hạn, số 2, 3, 5, 7 là các số nguyên tố, trong khi số 4 (có ước là 1, 2, và 4) và số 6 (có ước là 1, 2, 3, 6) không phải là số nguyên tố.
Định lý vô hạn số nguyên tố: Euclid, một nhà toán học vĩ đại thời cổ đại, đã chỉ ra rằng có vô hạn số nguyên tố. Chứng minh có thể dựa vào cách lập luận mâu thuẫn:
Giả sử tập hợp số nguyên tố là hữu hạn với các số p1, p2, ..., pn. Xét số A = p1 × p2 × ... × pn + 1. Thì A phải có ít nhất một ước nguyên tố, nhưng A không thể chia hết cho bất kỳ số nguyên tố nào trong tập hợp đã giả định, gây ra sự mâu thuẫn. Do đó, tập hợp số nguyên tố là vô hạn.
1.2. Hai số nguyên tố cùng nhau
Hai số tự nhiên được gọi là nguyên tố cùng nhau nếu chúng chỉ có số 1 là ước chung duy nhất. Ví dụ, 8 và 15 là hai số nguyên tố cùng nhau, nhưng 12 và 18 không phải vì cả hai đều chia hết cho 6.
1.3. Hàm số Ơ-le (Euler) ϕ(n)
Hàm số Euler ϕ(n) đại diện cho số các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n. Chẳng hạn: ϕ(9) = 6, vì có 6 số từ 1 đến 9 là nguyên tố cùng nhau với 9: 1, 2, 4, 5, 7, 8. Công thức tính hàm số này là:
ϕ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)
1.4. Đồng dư Modular
Hai số a và b được gọi là đồng dư với nhau theo module n nếu hiệu của chúng chia hết cho n. Ký hiệu là:
a ≡ b (mod n)
1.5. Định lý Fermat nhỏ
Định lý Fermat nhỏ phát biểu rằng: Nếu p là số nguyên tố, thì với một số nguyên a bất kỳ, a^p ≡ a (mod p). Hệ quả là nếu a không chia hết cho p, thì a^(p-1) ≡ 1 (mod p).
2. Sinh khóa RSA
Để mã hóa và giải mã thông tin bằng thuật toán RSA, trước tiên chúng ta cần tạo cặp khóa bao gồm khóa công khai (public key) và khóa bí mật (private key). Quy trình sinh khóa như sau:
- Chọn hai số nguyên tố p và q.
- Tính n = p × q.
- Tính giá trị hàm Euler ϕ(n) = (p - 1) × (q - 1).
- Chọn số tự nhiên e sao cho 1 < e < ϕ(n) và e nguyên tố cùng nhau với ϕ(n).
- Tính d sao cho d × e ≡ 1 (mod ϕ(n)).
Sau khi hoàn tất các bước trên, chúng ta sẽ có khóa công khai (n, e) và khóa bí mật (n, d).
3. Mã hóa RSA
Thuật toán mã hóa RSA thực hiện mã hóa thông điệp dưới dạng số nguyên. Nếu A muốn gửi thông điệp cho B, A sẽ chuyển thông điệp thành số m, rồi sử dụng khóa công khai (n, e) để tính số c:
c = m^e mod n
Khi B nhận được c, B sử dụng khóa bí mật (n, d) để tính lại m:
m = c^d mod n
Chứng minh rằng m = c^d mod n sẽ luôn đúng thông qua định lý Fermat nhỏ và tính chất của các số nguyên tố.
Ví dụ: Giả sử chọn (p, q) = (61, 53), ta có n = 3233; ϕ(n) = 3120; chọn e = 17, d = 2753, thông điệp m = 1289. Vậy c được tính là:
c = 1289^17 mod 3233 = 272
Khi nhận c, B có thể giải mã:
m = 272^2753 mod 3233 = 1289
Bài tập thực hành
- Với khóa công khai n = 943 và e = 7, thông điệp mã hóa c = 545, hãy xác định thông điệp gốc m.
- Với khóa công khai n = 943 và e = 7, thông điệp mã hóa c = 545, tìm ra thông điệp gốc m.
