Thuật toán mã hóa RSA?

Thuật toán mã hóa RSA (Rivest–Shamir–Adleman) là một thuật toán mã hóa bất đối xứng, nghĩa là sử dụng hai khóa khác nhau: một khóa công khai (public key) để mã hóa và một khóa bí mật (private key) để giải mã. Dưới đây là tóm tắt nguyên lý hoạt động của RSA:

---

🔐 BƯỚC 1: KHỞI TẠO KHÓA

1. Chọn hai số nguyên tố lớn:
   $p$ và $q$

2. Tính tích của chúng:
   n=p×q
   → Đây là một phần của khóa công khai.

3. Tính totient (phi hàm Euler):
   $\varphi (n)=(p-1)(q-1)$

4. Chọn số nguyên e sao cho:

   • $1<e<\varphi (n)$

   • gcd⁡(e,ϕ(n))=1
     (e và phi(n) nguyên tố cùng nhau)

5. Tính d sao cho:
   d≡e−1mod  ϕ(n)
   (Tức là d là nghịch đảo modular của e mod phi(n))

➡️ Khi đó:

• Khóa công khai: (e,n)

• Khóa bí mật: (d,n)

---

📨 BƯỚC 2: MÃ HÓA THÔNG ĐIỆP

Giả sử người gửi muốn gửi một thông điệp $M$, mã hóa như sau:

• C=Memod  nC = M^e \mod nC=Memodn

Trong đó:

• $M$ là bản rõ (plaintext)

• $C$ là bản mã (ciphertext)

• Dùng khóa công khai để mã hóa

---

📬 BƯỚC 3: GIẢI MÃ

Người nhận sử dụng khóa bí mật để giải mã:

• M=Cdmod  nM = C^d 

---

🧠 VÍ DỤ MINH HỌA ĐƠN GIẢN (với số nhỏ)

Chọn:

• p=5, q=11

• n=5×11=55

• ϕ(n)=(5−1)(11−1)=4×10=40

• Chọn e=3 vì gcd⁡(3,40)=1

• Tìm d≡e−1mod  40:
  → d=27 (vì 3×27=81≡1mod  40

Vậy:

• Khóa công khai: $(3,55)$

• Khóa bí mật: $(27,55)$

Mã hóa thông điệp M=9:

• C=93mod  55=729mod  55=14

Giải mã:

• M=1427mod  55=9

---

✅ ĐẶC ĐIỂM CỦA RSA

• Bảo mật dựa trên độ khó của phân tích số nguyên lớn (tách n thành p và q)

• Dễ sinh khóa, dễ mã hóa/giải mã với máy tính

• Được dùng trong: SSL/TLS, xác thực chữ ký số, giao tiếp an toàn