RS256: RSA Asymmetric Signing

HS256 has one key that both signs and verifies — a problem the moment more than one party is involved: to let someone check your tokens you must hand them the power to mint their own. RS256 splits those abilities apart.

• The private key signs. The issuer holds it, and nobody else.
• The public key verifies. Publish it on the open internet if you like.

This is why every identity provider uses an asymmetric algorithm. Google publishes its verification keys at a public URL: anyone can confirm a Google-issued token is genuine, nobody can manufacture one. Inside a company it means a hundred verifying services without a hundred copies of a forgeable secret.

The two operations

RSA uses a modulus $n$, a public exponent $e$ (almost always 65537), and a private exponent $d$. Signing is the private-key operation on the padded hash $m$; verification is the public-key operation on the signature $s$:

$s = m^{d} \bmod n \qquad\qquad m' = s^{e} \bmod n$

The verifier then rebuilds the padded hash from the token it received and checks that $m'$ matches it byte for byte.

A signature is not encryption. It is easy to find RS256 described as "encrypting the hash with the private key", and the arithmetic does look symmetric — but nothing is being concealed, and the two operations have different security requirements and different padding schemes. Call it a private-key operation and you will not confuse yourself later.

Why the hash gets padded first

Signing the bare SHA-256 hash — a 32-byte number as $m$ — is broken. Small values behave badly under exponentiation, and an attacker choosing messages can combine signatures into new valid ones, since $s_1 s_2 = (m_1 m_2)^d \bmod n$. PKCS#1 v1.5 destroys that structure by widening the hash to the full modulus:

00 01 FF FF FF ... FF 00 <DigestInfo>
|  |  |                | |
|  |  |                | └─ DER: "this is a SHA-256 digest" + the 32 hash bytes
|  |  └─ at least 8 filler bytes ─┘
|  └──── block type 01
└─────── leading zero, keeps the integer smaller than n

For a 2048-bit key that block is exactly 256 bytes. The DigestInfo prefix names the hash algorithm, which is why a verifier expecting SHA-256 rejects a signature built over SHA-1 even if the arithmetic checks out.

What this costs you

An RS256 signature is roughly eight times the rest of a small token. That is the price of asymmetry, and why ES256 — same trust model, elliptic curves instead of big integers — is the usual choice for new systems. 2048 bits is the floor; use 3072 or 4096 for long-lived keys.

The catch that makes this a security lesson

Look again at the row that says the RS256 verifier cannot forge. It holds only a public key — a value the attacker also has, by design.

Now imagine that verifier is written to read alg out of the header and pick its algorithm accordingly. Hand it a token whose header says HS256 and it will faithfully treat the RSA public key as an HMAC secret — a secret the attacker already knows. Publishing the verification key is safe; letting the token choose how that key is used is not. The lesson on known JWT attacks builds this forgery step by step.

Your exercise

Real RSA — Miller-Rabin primes, modular exponentiation, DER parsing — is a course of its own, so the exercise stubs out the arithmetic and drills the half that JWT libraries actually get wrong: pulling the signature segment out of the token and decoding it correctly. You read VERIFY <jwt>|<expected_sig_hex>, base64url-decode the third segment, and hex-compare.

The hidden case that catches people is the signature 3q2-7w, expecting deadbeef. Two ways to fail it:

• Not re-padding. It is 6 characters, so it needs two = before decoding; without them you get binascii.Error: Incorrect padding.
• Using the standard alphabet. base64.b64decode("3q2-7w==") throws away the - as a non-alphabet character and then complains that 5 data characters cannot be one more than a multiple of 4. Only urlsafe_b64decode maps - back to byte value 62 and yields deadbeef.

The visible case AQID needs zero padding characters, so a solution that skips re-padding passes it and then fails the hidden ones.