Hệ mật mã RSA là gì?
RSA là tên viết tắt của ba tác giả Rivest, Sharmir, Adleman của trường MIT đã đề ra hệ mật mã công khai. Hệ mật mã này được đề xuất năm 1977, dựa trên cơ sở tính các lũy thừa trong số học. Độ an toàn của hệ mật này dựa trên độ khó của việc phân tích thành thừa số nguyên tố của các số nguyên lớn.
Mã hóa:
- Chuyển đổi dữ liệu sang dạng số: Dữ liệu cần mã hóa (ví dụ như văn bản) được chuyển đổi thành dạng số, thường sử dụng mã ASCII.
- Chia nhỏ dữ liệu: Dữ liệu số được chia thành các khối nhỏ hơn để đảm bảo quá trình mã hóa hiệu quả.
- Mã hóa từng khối dữ liệu: Mỗi khối dữ liệu được mã hóa bằng cách sử dụng công thức RSA: c ≡ m^e (mod n)
- Gửi văn bản mã hóa: Văn bản mã hóa được gửi cho người nhận.
Giải mã:
- Nhận văn bản mã hóa: Người nhận nhận được văn bản mã hóa.
- Giải mã từng khối dữ liệu: Mỗi khối dữ liệu được giải mã bằng cách sử dụng công thức RSA: m ≡ c^d (mod n)
- Chuyển đổi dữ liệu số sang dạng ban đầu: Các khối dữ liệu đã giải mã được chuyển đổi thành dạng ban đầu (ví dụ như văn bản).
Cách xác định 2 số là số nguyên tố
- Kiểm tra từng số: Mỗi số cần được kiểm tra riêng lẻ để xác định xem nó có phải là số nguyên tố hay không.
- Sử dụng phương pháp chia thử: Bắt đầu từ 2 và chia thử cho tất cả các số nguyên dương nhỏ hơn số đó cho đến khi gặp số mà nó không chia hết. Nếu số đó chỉ chia hết cho 1 và chính nó, nó là số nguyên tố.
- Kiểm tra ước số: Nếu số đó không có ước số nào khác ngoài 1 và chính nó trong khoảng từ 2 đến căn bậc hai của số đó, thì đó là số nguyên tố.
Ví dụ, để kiểm tra xem số 7 có phải là số nguyên tố không, chúng ta sẽ kiểm tra xem nó có chia hết cho bất kỳ số nào từ 2 đến √7 không. Vì 7 chỉ chia hết cho 1 và chính nó, nên 7 là số nguyên tố.
Cách tạo public key và private key
- Chọn hai số nguyên tố (p và q)
- Tính toán modulus (n): n = p * q
- Tính toán hàm Euler phi (φ(n)): φ(n) = (p – 1) * (q – 1)
- Chọn số mũ công khai (e): Chọn e sao cho e<n, e phải thỏa gcd(e, φ)=1. Nghĩa là e là một số nguyên tố nhỏ hơn φ(n) và nguyên tố cùng với φ(n).
- Tính toán số mũ bí mật (d): Tìm d sao cho φ = [(e*d)-1]*k. k là 1 số nguyên dương chia hết cho φ.
- Tạo khóa: Khóa công khai: (n, e), Khóa bí mật: (n, d)
Cách mã hóa RSA
Công thức: c ≡ m^e (mod n). Trong đó:
- c là văn bản mã hóa.
- m là văn bản gốc.
- e là số mũ công khai.
- n là modulus.
Ví dụ: Giả sử có 1 tin nhắn cần mã hóa m=7, public key = (n, e) = (33, 3)
Ta có: c = m^e (mod n)
<=> c = 7^3 mod 33
<=> c = 343 mod 33
<=> c = 13
=> Ciphertext c = 13.
Cách giải mã RSA
m ≡ c^d (mod n). Trong đó:
- m là văn bản gốc.
- c là văn bản mã hóa.
- d là số mũ bí mật.
- n là modulus.
Ví dụ: Giả sử có 1 tin nhắn mã hóa c = 13, private key = (n,d) = (33,7)
Ta có: m ≡ c^d (mod n)
<=> m = 13^7 mod 33
<=> m = 62748517 mod 33
<=> m = 7
