Chi tiết các bước tính toán:

• Bước 1: Chọn 2 số nguyên tố $p$ và $q$

  • Giả sử chọn: $p = 61$ và $q = 53$.

• Bước 2: Tính Modulus $n$ và Hàm Euler $\phi(n)$

  • $n = p \times q = 61 \times 53 = 3233$

  • $\phi(n) = (p - 1) \times (q - 1) = (61 - 1) \times (53 - 1) = 60 \times 52 = 3120$

• Bước 3: Chọn Khóa công khai $e$ (Public Exponent)

  • Chọn $e$ sao cho $1 < e < \phi(n)$ và $e$ nguyên tố cùng nhau với $\phi(n)$ (tức là $\gcd(e, \phi(n)) = 1$).

  • Chọn $e = 17$ (Vì $17$ là số nguyên tố và không phải là ước của $3120$).

  • 🔑 Public Key thu được: $(e, n) = (17, 3233)$

• Bước 4: Tính Khóa bí mật $d$ (Private Exponent)

  • Tìm $d$ là Nghịch đảo mô-đun của $e$ theo mô-đun $\phi(n)$:

    $$(d \times e) \equiv 1 \pmod{\phi(n)} \quad \Leftrightarrow \quad (d \times 17) \pmod{3120} = 1$$

  • Áp dụng Thuật toán Euclid mở rộng, ta tìm được $d = 2753$.

  • Kiểm tra lại: $17 \times 2753 = 46801 = 15 \times 3120 + 1$ (Chuẩn xác!).

  • 🔒 Private Key thu được: $(d, n) = (2753, 3233)$

3. CHỨNG MINH TOÁN HỌC: QUY TRÌNH KÝ & XÁC MINH

Giả sử ta có mã băm của một văn bản (sau khi nén về số nhỏ) là $H = 65$.

✍️ Phía người ký (Dùng Private Key $(d, n) = (2753, 3233)$):

Người ký tính Chữ ký số $S$:

Bằng thuật toán bình phương và nhân liên tiếp (Fast Exponentiation), máy tính tính ra:

🔍 Phía người nhận (Dùng Public Key $(e, n) = (17, 3233)$):

Người nhận giải mã chữ ký $S = 2790$ để tìm lại mã băm ban đầu $H'$:

Máy tính thực hiện phép tính số dư:

👉 Kết quả: $H' = H = 65$. Bản chất toán học hoàn toàn khớp!

❓ TẠI SAO $(H^d)^e \pmod n$ LẠI BẰNG $H$? (BỐC TÁCH CÔNG THỨC)

Theo quy tắc lũy thừa:

Vì ở Bước 4 ta đã chọn $d$ sao cho $d \cdot e \equiv 1 \pmod{\phi(n)}$, nghĩa là tồn tại một số nguyên $k$ sao cho:

Thay vào biểu thức trên:

Theo Định lý Euler, với mọi $H$ nguyên tố cùng nhau với $n$, ta luôn có:

Thế $1$ vào công thức:

💡 Kết luận toán học: Việc ký bằng $d$ rồi mở bằng $e$ chính là đưa số $H$ mũ lên một số dạng $k \cdot \phi(n) + 1$, và nhờ định lý Euler, phần $k \cdot \phi(n)$ sẽ tự động biến thành $1$, chỉ còn lại chính số $H$ ban đầu!

4. BÀI TẬP BẰNG PYTHON THỦ CÔNG (KHÔNG DÙNG HÀM CÓ SẴN)

Dưới đây là đoạn code minh họa từng bước phép nhân và phép lấy dư từng bước nhỏ để sinh viên thấy rõ dòng chảy toán học:

# =====================================================================
# BÀI 5: MINH HỌA BẢN CHẤT TOÁN HỌC RSA BẰNG PYTHON
# =====================================================================

# 1. Khởi tạo số liệu toán học
p, q = 61, 53
n = p * q            # 3233
phi_n = (p - 1) * (q - 1) # 3120
e = 17
d = 2753             # d = pow(e, -1, phi_n)

print(f"1. Khởi tạo: n = {n}, Phi(n) = {phi_n}")
print(f"   Public Key  (e, n): ({e}, {n})")
print(f"   Private Key (d, n): ({d}, {n})\n")

# 2. Giả sử Mã băm văn bản H = 65
H = 65
print(f"2. Mã băm ban đầu (H): {H}")

# 3. Ký số bằng Private Key: S = (H^d) mod n
# Dùng hàm pow(base, exp, mod) thực hiện thuật toán Bình phương & Nhân
S = pow(H, d, n)
print(f"3. Chữ ký số tạo ra (S) = ({H}^{d}) mod {n} = {S}")

# 4. Xác minh bằng Public Key: H_prime = (S^e) mod n
H_prime = pow(S, e, n)
print(f"4. Giải mã chữ ký (H') = ({S}^{e}) mod {n} = {H_prime}\n")

# 5. So sánh toán học
print(f"📊 So sánh H và H': {H} == {H_prime} => {'CHÍNH XÁC 100%' if H == H_prime else 'SAI'}")