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.

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: . A few seconds with pen and paper gives . Now go backwards: is the product of which two primes? You would have to try dividing by until you hit . 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 by each odd number until one divides it. Figure 1 counts the divisions needed when is 16 to 44 bits long.

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 divisions. For comparison, the number of atoms in the observable universe is only about .
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: on a 12-hour clock, written . 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 be the number of integers from to that share no divisor with (other than ). Euler proved that for every coprime to :
In other words, raise to the power and you are back at , like a clock hand completing a full turn. When is prime, , which gives Fermat’s little theorem: .
The crucial detail: when with prime,
Computing is easy if you know and . Knowing only , computing 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:
- Pick two primes: , .
- Compute and .
- Pick the public exponent (it must be coprime to ).
- Find the private exponent such that . Here , because .
The public key is the pair : give it to the whole world. The private key is : one person keeps it. After step 4, , and are deleted.
With the message as the number :
- Encrypt with the public key: .
- Decrypt with the private key: . The original message is back.
Why does it come back to exactly ? Because for some integer , so by Euler’s theorem:
To find from the public key, an attacker needs , which means splitting into . With a schoolchild could do it. With a 2048-bit , 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 can): hash the message into a number , then compute the signature .
- Verify (anyone with can): compute and compare it with . If they match, the signature is valid.
With the toy key pair above, signing gives . Anyone can check: . Exactly .
Change a single character in the message and the hash changes completely, so the old signature no longer matches. Making a new signature requires , and getting requires splitting . 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 signatureDecoding 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 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 pair from earlier, in base64url (AQAB is , 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:
- Generate a new key pair and add the new public key to the JWKS alongside the old one.
- Wait for the services’ JWKS caches to expire, then start signing new tokens with the new key (new
kid). - Old tokens still verify with the old key until they expire.
- 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” callednone, meaning an unsigned token. Some libraries readalgfrom 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
RS256and 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 seesHS256, 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 thealgfield in the token. - Always check
exp,iss(who issued it) andaud(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.
import hashlibimport random
import matplotlib.pyplot as pltimport 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 bitssignature valid: Truerole changed to 'root': Falsen 16 bits: found p = 137 after 68 divisionsn 20 bits: found p = 821 after 410 divisionsn 24 bits: found p = 2381 after 1,190 divisionsn 28 bits: found p = 8849 after 4,424 divisionsn 32 bits: found p = 47599 after 23,799 divisionsn 36 bits: found p = 149297 after 74,648 divisionsn 40 bits: found p = 663977 after 331,988 divisionsn 44 bits: found p = 2824853 after 1,412,426 divisionsextrapolated: a 2048-bit n needs about 10^310 divisionsThe 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 . 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 , 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.
Tài liệu tham khảo
- [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]M. Jones, J. Bradley and N. Sakimura. RFC 7519 — JSON Web Token (JWT). IETF, 2015.
- [3]M. Jones, J. Bradley and N. Sakimura. RFC 7515 — JSON Web Signature (JWS). IETF, 2015.
- [4]M. Jones. RFC 7518 — JSON Web Algorithms (JWA). IETF, 2015.
- [5]M. Jones. RFC 7517 — JSON Web Key (JWK). IETF, 2015.
- [6]Y. Sheffer, D. Hardt and M. Jones. RFC 8725 — JSON Web Token Best Current Practices. IETF, 2020.
- [7]Tim McLean. Critical vulnerabilities in JSON Web Token libraries. Auth0 Blog, 2015.
- [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]NIST IR 8547 (initial public draft) — Transition to Post-Quantum Cryptography Standards. NIST, 2024.


