RSA and JWT: how 20 services trust a token nobody can forge

Multiplying primes is easy; splitting the product is nearly impossible. That gives RSA digital signatures, letting many services trust one token.

11 phút đọcTrung cấpEyeBlogs

Đọc bản tiếng Việt →

Diagram of a JSON Web Token on a dark background: three boxes HEADER, PAYLOAD and SIGNATURE inside a dashed frame, each with an arrow down to a matching string (aaaaa in red, bbbbbbbb in blue, cccccc in teal), the three strings joined by dots.
Mục lục

Your system has a login service and twenty other services: orders, payments, cart, notifications… A user logs in once, gets a token, and sends that token with every request. All twenty services must answer the same question: was this token really issued by the login service, or did someone write it themselves?

The simplest approach is a shared secret key. The login service uses the key to “stamp” the token, and the other services use the same key to check the stamp. It works, but it means the system’s most important secret lives in twenty-one places. If one service leaks its configuration (a .env file committed by mistake, a compromised container), the attacker can mint tokens for anyone, admins included.

What we really want sounds impossible: anyone can check the stamp, but only one place can apply it. The answer comes from a very old property of prime numbers.

Multiplying is easy, splitting is hard

Try multiplying two primes: 61×5361 \times 53. A few seconds with pen and paper gives 32333233. Now go backwards: 32333233 is the product of which two primes? You would have to try dividing by 3,5,7,11,…3, 5, 7, 11, \dots until you hit 5353. Still doable, but noticeably more tiring.

This asymmetry grows with the length of the numbers. A computer multiplies two 300-digit primes in under a millisecond. Splitting their product back apart (a number about 617 digits long, i.e. 2048 bits) has never been done, even with the best algorithm and an entire data center.

To get a feel for the gap, try the most naive attack, trial division: divide nn by each odd number until one divides it. Figure 1 counts the divisions needed when nn is 16 to 44 bits long.

Chart with a logarithmic vertical axis: divisions needed to find the prime factor p, against key length n from 16 to 44 bits. The measured points lie almost on a straight line, from about 70 divisions at 16 bits to about 1.4 million at 44 bits. A dashed trend line extends to 64 bits, reaching about a billion divisions.
Figure 1. Breaking toy RSA keys by trial division. The vertical axis is logarithmic, so a straight line means exponential growth: every 2 extra bits double the work. The figure is drawn by the code in the section Sign and break an RSA key yourself, near the end of the article.

The points lie on a straight line on a log scale, meaning every 2 extra bits double the work. Extend the line to 2048 bits and you get about 1031010^{310} divisions. For comparison, the number of atoms in the observable universe is only about 108010^{80}.

Trial division is, of course, the worst method. The best known algorithm today (the general number field sieve) is far faster, but still not enough. The public record dates from 2020, when a team of six researchers factored RSA-250, an 829-bit number, after about 2,700 CPU core-years spread over tens of thousands of machines[8]. From 829 bits to 2048 bits is still a very long way.

RSA: turning the asymmetry into a lock

In 1977, three MIT researchers, Ron Rivest, Adi Shamir and Leonard Adleman, found a way to turn “easy to multiply, hard to split” into a cryptosystem with two different keys[1]. The algorithm is named after their initials: RSA.

The mathematics reuses two old tools. The first is modular arithmetic, the familiar “take the remainder” of a clock face: 10+5=310 + 5 = 3 on a 12-hour clock, written 15≡3(mod12)15 \equiv 3 \pmod{12}. The second is a theorem of Euler, generalizing a discovery by Fermat more than a century earlier.

Euler’s theorem, just enough of it

Let φ(n)\varphi(n) be the number of integers from 11 to nn that share no divisor with nn (other than 11). Euler proved that for every mm coprime to nn:

mφ(n)≡1(modn)m^{\varphi(n)} \equiv 1 \pmod{n}

In other words, raise to the power φ(n)\varphi(n) and you are back at 11, like a clock hand completing a full turn. When p=np = n is prime, φ(p)=p−1\varphi(p) = p - 1, which gives Fermat’s little theorem: mp−1≡1(modp)m^{p-1} \equiv 1 \pmod{p}.

The crucial detail: when n=p⋅qn = p \cdot q with p,qp, q prime,

φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1)

Computing φ(n)\varphi(n) is easy if you know pp and qq. Knowing only nn, computing φ(n)\varphi(n) is as hard as factoring. All of RSA rests on that gap.

Building a key pair by hand

Let’s use small numbers to see each step:

  1. Pick two primes: p=61p = 61, q=53q = 53.
  2. Compute n=61×53=3233n = 61 \times 53 = 3233 and φ(n)=60×52=3120\varphi(n) = 60 \times 52 = 3120.
  3. Pick the public exponent e=17e = 17 (it must be coprime to 31203120).
  4. Find the private exponent dd such that e⋅d≡1(mod3120)e \cdot d \equiv 1 \pmod{3120}. Here d=2753d = 2753, because 17×2753=46801=15×3120+117 \times 2753 = 46801 = 15 \times 3120 + 1.

The public key is the pair (n,e)=(3233,17)(n, e) = (3233, 17): give it to the whole world. The private key is d=2753d = 2753: one person keeps it. After step 4, pp, qq and φ(n)\varphi(n) are deleted.

With the message as the number m=65m = 65:

  • Encrypt with the public key: c=6517 mod 3233=2790c = 65^{17} \bmod 3233 = 2790.
  • Decrypt with the private key: 27902753 mod 3233=652790^{2753} \bmod 3233 = 65. The original message is back.

Why does it come back to exactly mm? Because e⋅d=1+k⋅φ(n)e \cdot d = 1 + k \cdot \varphi(n) for some integer kk, so by Euler’s theorem:

med=m⋅(mφ(n))k≡m⋅1k=m(modn)m^{ed} = m \cdot \left(m^{\varphi(n)}\right)^k \equiv m \cdot 1^k = m \pmod{n}

To find dd from the public key, an attacker needs φ(n)\varphi(n), which means splitting nn into p⋅qp \cdot q. With n=3233n = 3233 a schoolchild could do it. With a 2048-bit nn, as Figure 1 showed, nobody can.

From encryption to digital signatures

Our JWT problem does not need to hide anything. What we need is to prove who wrote it. RSA does this by swapping the roles of the two keys:

  • Sign (only the holder of dd can): hash the message into a number hh, then compute the signature s=hd mod ns = h^d \bmod n.
  • Verify (anyone with (n,e)(n, e) can): compute se mod ns^e \bmod n and compare it with hh. If they match, the signature is valid.

With the toy key pair above, signing h=65h = 65 gives s=652753 mod 3233=588s = 65^{2753} \bmod 3233 = 588. Anyone can check: 58817 mod 3233=65588^{17} \bmod 3233 = 65. Exactly hh.

Change a single character in the message and the hash hh changes completely, so the old signature no longer matches. Making a new signature requires dd, and getting dd requires splitting nn. This is exactly what we wanted from the start: anyone can check the stamp, but only one place can apply it.

JWT: digital signatures in system design

JWT (JSON Web Token) is an IETF standard[2] for packaging information as JSON together with a signature. A JWT has three base64url-encoded parts joined by dots:

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

Decoding the first two parts from base64url shows ordinary JSON:

{ "alg": "RS256", "typ": "JWT", "kid": "2026-10" }
{ "sub": "user-42", "role": "admin", "iss": "https://auth.example.com", "exp": 1790000000 }

The third part is the signature over the string header.payload[3]. With RS256, the signature is exactly the hd mod nh^d \bmod n computation from the previous section: SHA-256 hash, PKCS#1 v1.5 padding, then a signature with the RSA private key[4].

HS256, RS256 or ES256?

The alg field in the header says how the token was signed. The three common choices differ on exactly the question this article started with:

Algorithm Mechanism Who can sign Who can verify Signature (minimum key)
HS256 HMAC-SHA256, symmetric key anyone with the secret anyone with the secret 32 bytes
RS256 RSA + SHA-256 only the private key holder anyone with the public key 256 bytes (2048-bit key)
ES256 ECDSA on the P-256 curve only the private key holder anyone with the public key 64 bytes

HS256 has nothing to do with primes. It is fast and simple, and perfectly fine when a single service both issues and verifies tokens, for example sessions in a monolithic app. When many services need to verify, every service holding the secret can also forge tokens, exactly the situation we want to avoid.

RS256 and ES256 solve that: the login service keeps the private key, and the twenty other services only need the public key. If a service is compromised, the attacker only gets what was already public. ES256 uses elliptic curves instead of large primes, giving much smaller signatures at the same security level. But RS256 is still the most widely supported algorithm, and many OpenID Connect systems use it by default.

Distributing public keys: JWKS

Where do the twenty services get the public key? Usually the login service publishes a JWK Set (JWKS)[5], for example at https://auth.example.com/.well-known/jwks.json:

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

The n and e fields are exactly the (n,e)(n, e) pair from earlier, in base64url (AQAB is 6553765537, the public exponent almost everyone uses). Each service downloads the JWKS, caches it, and verifies signatures entirely in memory, without calling the login service on every request. This is why JWT suits distributed systems: the work of authentication is spread out to every service without sharing a secret.

Rotating keys with kid

Private keys should be replaced periodically, and immediately if a leak is suspected. The kid (key ID) field in the header makes this possible without logging anyone out:

  1. Generate a new key pair and add the new public key to the JWKS alongside the old one.
  2. Wait for the services’ JWKS caches to expire, then start signing new tokens with the new key (new kid).
  3. Old tokens still verify with the old key until they expire.
  4. Once every token signed with the old key has expired, remove the old key from the JWKS.

On seeing an unknown kid, a service should reload the JWKS (rate-limited, so an attacker cannot send junk kids to make the service hammer the JWKS endpoint).

Revoking tokens: the price of statelessness

JWT’s greatest strength is also its biggest weakness: services verify tokens without asking anyone, so they also cannot know a token has been revoked. When a user logs out, or an admin locks a compromised account, tokens already issued stay valid until exp.

The common remedies are:

  • Short-lived access tokens (a few minutes up to about fifteen), paired with longer-lived refresh tokens. Refresh tokens are stored on the server, so they can be revoked.
  • For sensitive operations, also check a blocklist by jti (the token ID) in a cache such as Redis. This brings back some state, but only for the few requests that need it.

No option is free. The longer a token lives, the less often it needs refreshing, but the larger the risk window if it leaks.

Classic mistakes

RSA’s mathematics is solid. Almost every real-world JWT incident comes from misuse, not from someone factoring a number. In 2015, Tim McLean disclosed two vulnerabilities present at the same time in many popular JWT libraries[7]:

  • alg: none. The JWS standard allows an “algorithm” called none, meaning an unsigned token. Some libraries read alg from the header and obeyed it, so an attacker only had to edit the payload, set "alg": "none" and drop the signature for the token to be accepted.
  • Algorithm confusion. A server uses RS256 and holds the public key. The attacker creates a token with "alg": "HS256" and signs it with HMAC using that very public key (which anyone can download). The library sees HS256, uses the “key” the server provides (the public key) as the HMAC secret, and the signature matches.

Both bugs share one root: letting the token decide how to verify itself. RFC 8725 turns these lessons into recommendations[6]. The core of it:

  • The server fixes the list of accepted algorithms (for example only RS256). Never trust the alg field in the token.
  • Always check exp, iss (who issued it) and aud (who it was issued for), not just the signature.
  • RSA keys of at least 2048 bits (RFC 7518 requires this for RS256[4]), and HMAC secrets of at least 256 truly random bits.

Sign and break an RSA key yourself

The Python below does three things: generates a 1024-bit RSA key from scratch with the Miller–Rabin primality test, signs and verifies a JWT-style payload, and breaks toy keys (16 to 44 bits) by trial division to draw Figure 1. All you need is numpy and matplotlib. The figure counts divisions, not time, so it gives the same result on any machine.

This is “textbook” RSA without padding, for learning only. Do not use it for anything else.

rsa_toy.py
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) # Fixed seed: every run gives the same result.
def is_prime(n):
"""Miller–Rabin test (20 rounds): fast even for numbers hundreds of digits long."""
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 # full bit length, and odd
if is_prime(p):
return p
def keygen(bits):
"""Generate an RSA key: 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) # only the holder of d can do this
def verify(message, sig, n, e):
return pow(sig, e, n) == h(message, n) # anyone with (n, e) can do this
def trial_division(n):
"""Naive key breaking: try dividing n by 3, 5, 7, … Returns (factor, number of divisions)."""
k, steps = 3, 0
while n % k:
k, steps = k + 2, steps + 1
return k, steps + 1
# 1. Sign and verify a JWT-style payload with a 1024-bit key.
(n, e), d = keygen(1024)
payload = b'{"sub":"user-42","role":"admin","exp":1790000000}'
sig = sign(payload, n, d)
print("n has", n.bit_length(), "bits")
print("signature valid:", verify(payload, sig, n, e))
print("role changed to 'root':", verify(payload.replace(b"admin", b"root"), sig, n, e))
# 2. Break toy keys by trial division, with n from 16 to 44 bits.
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} bits: found p = {p} after {s:,} divisions")
# Plot: divisions vs bits (log vertical axis), extending the trend line.
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="trend: every 2 extra bits double the work")
ax.plot(bits, steps, "o", color="#8fa9c9", ms=8, label="divisions counted")
ax.set_yscale("log")
ax.set_xlabel("key length n (bits)", color="#a4a9b2")
ax.set_ylabel("divisions to find p", color="#a4a9b2")
ax.grid(color="#22262c")
ax.legend(frameon=False, labelcolor="#a4a9b2", fontsize=10, loc="upper left")
ax.set_title("Breaking toy RSA keys by trial division", color="#d4d7dc", fontsize=12)
fig.savefig("factoring-cost-en.png", dpi=150, bbox_inches="tight")
print(f"extrapolated: a 2048-bit n needs about 10^{icpt + slope * 2048:.0f} divisions")
n has 1024 bits
signature valid: True
role changed to 'root': False
n 16 bits: found p = 137 after 68 divisions
n 20 bits: found p = 821 after 410 divisions
n 24 bits: found p = 2381 after 1,190 divisions
n 28 bits: found p = 8849 after 4,424 divisions
n 32 bits: found p = 47599 after 23,799 divisions
n 36 bits: found p = 149297 after 74,648 divisions
n 40 bits: found p = 663977 after 331,988 divisions
n 44 bits: found p = 2824853 after 1,412,426 divisions
extrapolated: a 2048-bit n needs about 10^310 divisions

The third line of output is the whole point of JWT: change admin to root and the old signature is instantly invalid, and signing again requires dd. Try raising the limit in range(16, 45, 4) to 48 or 52 bits (52 bits takes a few minutes) to feel how steep the straight line in Figure 1 really is.

When does this lock stop being safe?

RSA has stood for nearly fifty years, but it has one known threat: Shor’s algorithm, running on a large enough quantum computer, could factor exponentially faster than classical computers. Such a machine does not exist yet, and when it might appear is still debated (see the article on quantum computing, in Vietnamese). Even so, NIST has proposed a roadmap: treat RSA and ECDSA at today’s security levels as deprecated after 2030, and disallowed in NIST-compliant systems after 2035[9]. ECDSA (the algorithm behind ES256) is also broken by Shor, so switching to elliptic curves does not solve this.

For system design, the practical lesson is don’t hard-wire your system to one algorithm. If the signing algorithm is configuration, keys are distributed through JWKS and rotated with kid, then the day you must move to post-quantum signatures is one big key rotation, not a rewrite of the whole system.

From the multiplication 61×5361 \times 53, through an 18th-century theorem of Euler, to a string in the Authorization header of billions of requests a day, the whole journey rests on one simple observation: some computations are easy forwards and nearly impossible backwards.

Phát video: Video: RSA and JWT: how 20 services trust a token nobody can forge
Video: RSA and JWT: how 20 services trust a token nobody can forgeVideo bằng tiếng Việt

Tài liệu tham khảo

  1. [1]R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126, 1978.
  2. [2]M. Jones, J. Bradley and N. Sakimura. RFC 7519 — JSON Web Token (JWT). IETF, 2015.
  3. [3]M. Jones, J. Bradley and N. Sakimura. RFC 7515 — JSON Web Signature (JWS). IETF, 2015.
  4. [4]M. Jones. RFC 7518 — JSON Web Algorithms (JWA). IETF, 2015.
  5. [5]M. Jones. RFC 7517 — JSON Web Key (JWK). IETF, 2015.
  6. [6]Y. Sheffer, D. Hardt and M. Jones. RFC 8725 — JSON Web Token Best Current Practices. IETF, 2020.
  7. [7]Tim McLean. Critical vulnerabilities in JSON Web Token libraries. Auth0 Blog, 2015.
  8. [8]F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann. Factorization of RSA-250. Announcement on the NMBRTHRY mailing list, 2020.
  9. [9]NIST IR 8547 (initial public draft) — Transition to Post-Quantum Cryptography Standards. NIST, 2024.