Số nguyên tố, RSA và JWT: vì sao 20 service kiểm tra được token mà không ai giả được

Hệ thống của bạn có một service đăng nhập và hai mươi service khác: đơn hàng, thanh toán, giỏ hàng, thông báo… Người dùng đăng nhập một lần, nhận về một token, rồi gửi token ấy kèm mọi request. Cả hai mươi service đều phải trả lời cùng một câu hỏi: token này có thật do service đăng nhập cấp không, hay ai đó tự viết ra?

Cách đơn giản nhất là dùng một khóa bí mật chung. Service đăng nhập dùng khóa để “đóng dấu” token, các service khác dùng đúng khóa đó để kiểm tra dấu. Cách này chạy được, nhưng nghĩa là bí mật quan trọng nhất của hệ thống phải nằm ở hai mươi mốt chỗ. Chỉ cần một service bị lộ cấu hình (một file .env bị commit nhầm, một container bị chiếm quyền), kẻ tấn công có thể tự in token cho bất kỳ ai, kể cả admin.

Điều ta thật sự muốn nghe có vẻ vô lý: ai cũng kiểm tra được con dấu, nhưng chỉ một nơi đóng được dấu. Câu trả lời cho mong muốn ấy đến từ một tính chất rất cũ của số nguyên tố.

Nhân thì dễ, tách thì khó

Hãy thử nhân hai số nguyên tố: $61 \times 53$. Mất vài giây với giấy bút, ra $3233$. Giờ làm ngược lại: $3233$ là tích của hai số nguyên tố nào? Bạn sẽ phải thử chia lần lượt cho $3, 5, 7, 11, \dots$ cho tới khi gặp $53$. Vẫn làm được, nhưng đã mệt hơn hẳn.

Bất đối xứng này lớn dần theo độ dài con số. Máy tính nhân hai số nguyên tố dài 300 chữ số trong chưa tới một phần nghìn giây. Còn tách ngược tích của chúng (một số dài khoảng 617 chữ số, tức 2048 bit) thì chưa ai làm được, kể cả với thuật toán tốt nhất và cả một trung tâm dữ liệu.

Để có cảm giác về độ chênh, hãy thử cách phá ngây thơ nhất là phép chia thử: chia $n$ cho từng số lẻ cho tới khi chia hết. Hình 1 đếm số phép chia cần dùng khi $n$ dài từ 16 tới 44 bit.

Các điểm nằm trên một đường thẳng trong thang log, tức là cứ thêm 2 bit thì công sức gấp đôi. Kéo đường ấy tới 2048 bit, ta được khoảng $10^{310}$ phép chia. Để so sánh, số nguyên tử trong vũ trụ quan sát được chỉ vào khoảng $10^{80}$.

Tất nhiên phép chia thử là cách tệ nhất. Thuật toán tốt nhất hiện nay (sàng trường số, general number field sieve) nhanh hơn rất nhiều, nhưng vẫn không đủ. Kỷ lục công khai là năm 2020, khi một nhóm sáu nhà nghiên cứu phân tích được RSA-250, một số dài 829 bit, sau khoảng 2.700 năm-lõi CPU chạy trên hàng chục nghìn máy[8]. Từ 829 bit lên 2048 bit còn một khoảng cách rất xa.

RSA: biến bất đối xứng thành ổ khóa

Năm 1977, ba nhà nghiên cứu ở MIT là Ron Rivest, Adi Shamir và Leonard Adleman tìm ra cách biến bất đối xứng “nhân dễ, tách khó” thành một hệ mật mã có hai chìa khác nhau[1]. Thuật toán mang tên viết tắt của ba người: RSA.

Toán học đứng sau dùng lại hai món đồ cũ. Món thứ nhất là số học đồng dư, phép tính “lấy phần dư” quen thuộc như kim đồng hồ: $10 + 5 = 3$ trên mặt đồng hồ 12 giờ, viết là $15 \equiv 3 \pmod{12}$. Món thứ hai là một định lý của Euler, mở rộng từ một phát hiện của Fermat hơn một thế kỷ trước đó.

Định lý Euler, phiên bản vừa đủ dùng

Gọi $\varphi(n)$ là số các số từ $1$ tới $n$ không có ước chung nào với $n$ (ngoài $1$). Euler chứng minh rằng với mọi $m$ nguyên tố cùng nhau với $n$:

Nói cách khác, cứ nâng lũy thừa lên đủ $\varphi(n)$ lần, ta quay về $1$, giống như kim đồng hồ quay đủ một vòng. Khi $p = n$ là số nguyên tố thì $\varphi(p) = p - 1$, và ta được định lý nhỏ Fermat: $m^{p-1} \equiv 1 \pmod{p}$.

Chi tiết quan trọng nhất: khi $n = p \cdot q$ với $p, q$ nguyên tố,

Tính $\varphi(n)$ rất dễ nếu biết $p$ và $q$. Nếu chỉ biết $n$ thì muốn tính $\varphi(n)$ cũng khó ngang với phân tích thừa số. Toàn bộ RSA dựa trên khe hở này.

Dựng một cặp khóa bằng tay

Ta làm với số nhỏ để thấy từng bước:

1. Chọn hai số nguyên tố: $p = 61$, $q = 53$.
2. Tính $n = 61 \times 53 = 3233$ và $\varphi(n) = 60 \times 52 = 3120$.
3. Chọn số mũ công khai $e = 17$ (cần nguyên tố cùng nhau với $3120$).
4. Tìm số mũ bí mật $d$ sao cho $e \cdot d \equiv 1 \pmod{3120}$. Ở đây $d = 2753$, vì $17 \times 2753 = 46801 = 15 \times 3120 + 1$.

Khóa công khai là cặp $(n, e) = (3233, 17)$: phát cho cả thế giới. Khóa bí mật là $d = 2753$: chỉ một người giữ. Sau bước 4, $p$, $q$ và $\varphi(n)$ bị xóa đi.

Với tin nhắn là số $m = 65$:

• Mã hóa bằng khóa công khai: $c = 65^{17} \bmod 3233 = 2790$.
• Giải mã bằng khóa bí mật: $2790^{2753} \bmod 3233 = 65$. Ra đúng tin nhắn ban đầu.

Vì sao lại quay về đúng $m$? Vì $e \cdot d = 1 + k \cdot \varphi(n)$ với một số nguyên $k$ nào đó, nên theo định lý Euler:

Muốn tìm $d$ từ khóa công khai, kẻ tấn công cần $\varphi(n)$, tức là cần tách được $n$ thành $p \cdot q$. Với $n = 3233$ thì một học sinh cũng làm được. Với $n$ dài 2048 bit thì như Hình 1 đã cho thấy, không ai làm được.

Từ mã hóa sang chữ ký số

Bài toán JWT của chúng ta không cần giấu nội dung. Thứ ta cần là chứng minh ai là người viết. RSA làm được việc này bằng cách đảo vai hai chiếc chìa:

• Ký (chỉ người giữ $d$ làm được): băm thông điệp thành một số $h$, rồi tính chữ ký $s = h^d \bmod n$.
• Kiểm tra (ai có $(n, e)$ cũng làm được): tính $s^e \bmod n$ rồi so với $h$. Bằng nhau thì chữ ký hợp lệ.

Với cặp khóa đồ chơi ở trên, ký lên $h = 65$ được $s = 65^{2753} \bmod 3233 = 588$. Ai cũng kiểm tra được: $588^{17} \bmod 3233 = 65$. Đúng bằng $h$.

Chỉ cần sửa một ký tự trong thông điệp, giá trị băm $h$ thay đổi hoàn toàn và chữ ký cũ không còn khớp. Muốn tạo chữ ký mới thì cần $d$, mà muốn có $d$ thì phải tách được $n$. Đây chính là thứ ta mong muốn từ đầu bài: ai cũng kiểm tra được con dấu, nhưng chỉ một nơi đóng được dấu.

JWT: chữ ký số trong system design

JWT (JSON Web Token) là một chuẩn của IETF[2] để đóng gói thông tin dưới dạng JSON kèm chữ ký. Một JWT gồm ba phần mã hóa base64url, nối bằng dấu chấm:

eyJhbGciOiJSUzI1NiIs...  .  eyJzdWIiOiJ1c2VyLTQy...  .  kX9bQ2...
       header                      payload               signature

Giải mã base64url hai phần đầu, ta thấy JSON bình thường:

{ "alg": "RS256", "typ": "JWT", "kid": "2026-10" }

{ "sub": "user-42", "role": "admin", "iss": "https://auth.example.com", "exp": 1790000000 }

Phần thứ ba là chữ ký trên chuỗi header.payload[3]. Với RS256, chữ ký chính là phép tính $h^d \bmod n$ ở mục trước: băm SHA-256, đệm theo PKCS#1 v1.5, rồi ký bằng khóa bí mật RSA[4].

HS256, RS256 hay ES256?

Trường alg trong header cho biết token được ký bằng cách nào. Ba lựa chọn phổ biến khác nhau ở đúng câu hỏi đầu bài:

HS256 không liên quan gì tới số nguyên tố. Nó nhanh và đơn giản, hoàn toàn ổn khi chỉ một service vừa cấp vừa kiểm tra token, ví dụ session của một ứng dụng monolith. Khi nhiều service cần kiểm tra, mỗi service giữ secret đều có thể giả token, đúng tình huống ta muốn tránh.

RS256 và ES256 giải quyết chuyện đó: service đăng nhập giữ khóa bí mật, hai mươi service kia chỉ cần khóa công khai. Một service bị chiếm thì kẻ tấn công chỉ lấy được thứ vốn đã công khai. ES256 dùng đường cong elliptic thay cho số nguyên tố lớn, cho chữ ký nhỏ hơn nhiều với cùng mức an toàn. Nhưng RS256 vẫn là thuật toán được hỗ trợ rộng rãi nhất, và nhiều hệ thống OpenID Connect dùng nó làm mặc định.

Phát khóa công khai: JWKS

Hai mươi service lấy khóa công khai ở đâu? Thông thường, service đăng nhập công bố một JWK Set (JWKS)[5], ví dụ tại https://auth.example.com/.well-known/jwks.json:

{
  "keys": [
    { "kty": "RSA", "kid": "2026-10", "alg": "RS256", "use": "sig", "n": "0vx7agoebGcQSuu...", "e": "AQAB" }
  ]
}

Trường n và e chính là cặp $(n, e)$ ở mục trước, viết bằng base64url (AQAB là $65537$, số mũ công khai gần như ai cũng dùng). Mỗi service tải JWKS, cache lại, rồi tự kiểm tra chữ ký ngay trong bộ nhớ, không cần gọi về service đăng nhập cho mỗi request. Đây là lý do JWT hợp với hệ phân tán: phần việc xác thực được chia ra cho từng nơi mà không cần chia sẻ bí mật.

Xoay khóa bằng kid

Khóa bí mật nên được thay định kỳ, và phải thay ngay nếu nghi bị lộ. Trường kid (key ID) trong header cho phép làm việc này mà không làm ai bị đăng xuất:

1. Sinh cặp khóa mới, thêm khóa công khai mới vào JWKS bên cạnh khóa cũ.
2. Chờ cache JWKS ở các service hết hạn, rồi bắt đầu ký token mới bằng khóa mới (kid mới).
3. Token cũ vẫn kiểm tra được bằng khóa cũ cho tới khi hết hạn.
4. Khi token ký bằng khóa cũ đã hết hạn hết, gỡ khóa cũ khỏi JWKS.

Khi gặp một kid lạ, service nên tải lại JWKS (có giới hạn tần suất, để kẻ tấn công không thể gửi kid rác liên tục khiến service dội request vào endpoint JWKS).

Thu hồi token: cái giá của sự phi trạng thái

Điểm mạnh nhất của JWT cũng là điểm yếu lớn nhất: service kiểm tra token mà không hỏi ai, nên cũng không biết token đã bị thu hồi. Người dùng bấm đăng xuất, hoặc admin khóa một tài khoản bị xâm nhập, thì token đã phát ra vẫn hợp lệ tới exp.

Cách xử lý phổ biến là:

• Access token sống ngắn (vài phút tới khoảng mười lăm phút), kèm refresh token sống lâu hơn. Refresh token được lưu ở server nên thu hồi được.
• Với các thao tác nhạy cảm, kiểm tra thêm một danh sách chặn theo jti (ID của token) trong cache như Redis. Làm vậy là chấp nhận quay lại một phần trạng thái, nhưng chỉ cho số ít request cần thiết.

Không có lựa chọn nào miễn phí. Token sống càng lâu thì càng ít phải refresh, nhưng cửa sổ rủi ro khi token bị lộ cũng càng lớn.

Những lỗi kinh điển

Toán của RSA rất vững. Hầu hết các sự cố JWT ngoài đời đến từ cách dùng sai, không phải từ ai đó phân tích được thừa số. Năm 2015, Tim McLean công bố hai lỗ hổng xuất hiện cùng lúc trong nhiều thư viện JWT phổ biến[7]:

• alg: none. Chuẩn JWS cho phép một “thuật toán” tên là none, tức token không có chữ ký. Một số thư viện đọc alg từ header rồi làm theo, nên kẻ tấn công chỉ cần sửa payload, đặt "alg": "none" và bỏ phần chữ ký là token được chấp nhận.
• Nhầm thuật toán. Server dùng RS256 và có khóa công khai trong tay. Kẻ tấn công tạo token với "alg": "HS256" và ký HMAC bằng chính khóa công khai đó (thứ ai cũng tải được). Thư viện thấy HS256 nên dùng “khóa” mà server đưa cho (vốn là khóa công khai) làm secret HMAC, và chữ ký khớp.

Cả hai lỗi có chung một gốc: để token tự quyết định cách kiểm tra chính nó. RFC 8725 tổng hợp các bài học này thành khuyến nghị[6]. Phần cốt lõi gồm:

• Server cố định danh sách thuật toán được chấp nhận (ví dụ chỉ RS256). Không bao giờ tin trường alg trong token.
• Luôn kiểm tra exp, iss (ai phát) và aud (phát cho ai), không chỉ kiểm tra chữ ký.
• Khóa RSA tối thiểu 2048 bit (RFC 7518 bắt buộc điều này cho RS256[4]), secret HMAC tối thiểu 256 bit ngẫu nhiên thật.

Tự tay ký và phá một khóa RSA

Đoạn Python dưới đây làm ba việc: sinh khóa RSA 1024 bit từ đầu bằng phép thử nguyên tố Miller–Rabin, ký rồi kiểm tra một payload kiểu JWT, và phá các khóa đồ chơi (16 tới 44 bit) bằng phép chia thử để vẽ ra Hình 1. Chỉ cần cài numpy và matplotlib. Hình đếm số phép chia chứ không đo thời gian, nên chạy trên máy nào cũng ra cùng một kết quả.

Đây là RSA “sách giáo khoa”, không có padding, chỉ để học. Đừng dùng nó cho việc gì khác.

import hashlib
import random

import matplotlib.pyplot as plt
import numpy as np

plt.rcParams.update({"figure.facecolor": "#16181c", "axes.facecolor": "#16181c", "text.color": "#d4d7dc",
                     "axes.edgecolor": "#2a2e35", "xtick.color": "#878d97", "ytick.color": "#878d97", "font.size": 12})
random.seed(1977)  # Cố định seed để chạy lại ra cùng kết quả.


def is_prime(n):
    """Kiểm tra Miller–Rabin (20 vòng): nhanh kể cả với số hàng trăm chữ số."""
    if n < 4:
        return n in (2, 3)
    d, s = n - 1, 0
    while d % 2 == 0:
        d, s = d // 2, s + 1
    for _ in range(20):
        x = pow(random.randrange(2, n - 1), d, n)
        if x in (1, n - 1):
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def random_prime(bits):
    while True:
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1   # đủ số bit và là số lẻ
        if is_prime(p):
            return p


def keygen(bits):
    """Sinh khoá RSA: n = p·q, e = 65537, d = e⁻¹ mod φ(n)."""
    e = 65537
    while True:
        p, q = random_prime(bits // 2), random_prime(bits // 2)
        phi = (p - 1) * (q - 1)
        if p != q and phi % e != 0:
            return (p * q, e), pow(e, -1, phi)


def h(message, n):
    return int.from_bytes(hashlib.sha256(message).digest(), "big") % n


def sign(message, n, d):
    return pow(h(message, n), d, n)            # chỉ người giữ d làm được


def verify(message, sig, n, e):
    return pow(sig, e, n) == h(message, n)     # ai có (n, e) cũng làm được


def trial_division(n):
    """Phá khoá kiểu ngây thơ: thử chia n cho 3, 5, 7, … Trả về (thừa số, số phép chia)."""
    k, steps = 3, 0
    while n % k:
        k, steps = k + 2, steps + 1
    return k, steps + 1


# 1. Ký và kiểm tra một payload kiểu JWT bằng khoá 1024 bit.
(n, e), d = keygen(1024)
payload = b'{"sub":"user-42","role":"admin","exp":1790000000}'
sig = sign(payload, n, d)
print("n có", n.bit_length(), "bit")
print("chữ ký hợp lệ:", verify(payload, sig, n, e))
print("sửa role thành 'root':", verify(payload.replace(b"admin", b"root"), sig, n, e))

# 2. Phá khoá đồ chơi bằng phép chia thử, với n từ 16 đến 44 bit.
bits = list(range(16, 45, 4))
steps = []
for b in bits:
    (n_small, _), _ = keygen(b)
    p, s = trial_division(n_small)
    steps.append(s)
    print(f"n {b:>2} bit: tìm ra p = {p} sau {s:,} phép chia")

# Vẽ: số phép chia theo số bit (trục dọc thang log), kéo dài đường xu hướng.
slope, icpt = np.polyfit(bits, np.log10(steps), 1)
xs = np.array([16, 64])
fig, ax = plt.subplots(figsize=(8, 4.8))
ax.plot(xs, 10 ** (icpt + slope * xs), color="#878d97", lw=1, ls="--", label="xu hướng: mỗi 2 bit thêm vào, gấp đôi công sức")
ax.plot(bits, steps, "o", color="#8fa9c9", ms=8, label="số phép chia đếm được")
ax.set_yscale("log")
ax.set_xlabel("độ dài khoá n (bit)", color="#a4a9b2")
ax.set_ylabel("số phép chia để tìm ra p", color="#a4a9b2")
ax.grid(color="#22262c")
ax.legend(frameon=False, labelcolor="#a4a9b2", fontsize=10, loc="upper left")
ax.set_title("Phá khoá RSA đồ chơi bằng phép chia thử", color="#d4d7dc", fontsize=12)
fig.savefig("factoring-cost.png", dpi=150, bbox_inches="tight")
print(f"ngoại suy: n 2048 bit cần khoảng 10^{icpt + slope * 2048:.0f} phép chia")

n có 1024 bit
chữ ký hợp lệ: True
sửa role thành 'root': False
n 16 bit: tìm ra p = 137 sau 68 phép chia
n 20 bit: tìm ra p = 821 sau 410 phép chia
n 24 bit: tìm ra p = 2381 sau 1,190 phép chia
n 28 bit: tìm ra p = 8849 sau 4,424 phép chia
n 32 bit: tìm ra p = 47599 sau 23,799 phép chia
n 36 bit: tìm ra p = 149297 sau 74,648 phép chia
n 40 bit: tìm ra p = 663977 sau 331,988 phép chia
n 44 bit: tìm ra p = 2824853 sau 1,412,426 phép chia
ngoại suy: n 2048 bit cần khoảng 10^310 phép chia

Dòng thứ ba của kết quả là toàn bộ ý nghĩa của JWT: đổi admin thành root thì chữ ký cũ lập tức không còn hợp lệ, và muốn ký lại thì phải có $d$. Bạn có thể thử tăng giới hạn range(16, 45, 4) lên 48 hay 52 bit (52 bit sẽ chạy mất vài phút) để tự cảm nhận đường thẳng trong Hình 1 dốc tới mức nào.

Khi nào ổ khóa này hết an toàn?

RSA đã đứng vững gần năm mươi năm, nhưng nó có một mối đe dọa đã biết tên: thuật toán Shor chạy trên máy tính lượng tử đủ lớn có thể phân tích thừa số nhanh hơn theo cấp số mũ so với máy tính thường. Máy như vậy chưa tồn tại, và chuyện nó bao giờ xuất hiện vẫn đang được tranh luận (xem bài máy tính lượng tử). Dù vậy, NIST đã đề xuất lộ trình: coi RSA và ECDSA với mức an toàn hiện nay là lỗi thời sau năm 2030, và cấm hẳn trong các hệ thống tuân thủ chuẩn NIST sau năm 2035[9]. ECDSA (thuật toán đứng sau ES256) cũng bị Shor phá, nên đổi sang đường cong elliptic không giải quyết được vấn đề này.

Với system design, bài học thực tế là đừng gắn chết hệ thống vào một thuật toán. Nếu thuật toán ký là cấu hình, khóa được phát qua JWKS và xoay được bằng kid, thì ngày phải chuyển sang chữ ký hậu lượng tử chỉ là một lần xoay khóa lớn, không phải một lần viết lại toàn bộ hệ thống.

Từ phép nhân $61 \times 53$, qua định lý Euler thế kỷ 18, tới một chuỗi ký tự trong header Authorization của hàng tỷ request mỗi ngày, toàn bộ hành trình dựa trên một quan sát đơn giản: có những phép tính làm xuôi thì dễ mà làm ngược thì gần như không thể.