RSA Signatures: The Version in Most Tutorials Is Forgeable

A digital signature proves a message came from the holder of a specific private key. The mechanism is elegant enough that it looks like a footnote to encryption:

Encrypt: c = m^e mod n     (public key)
Decrypt: m = c^d mod n     (private key)
 
Sign:    s = m^d mod n     (private key)
Verify:  m = s^e mod n     (public key)

Identical mathematics, keys swapped. That symmetry is genuinely beautiful, and it is also the reason a naive implementation is breakable — because the same algebraic structure that makes signing work lets an attacker manufacture signatures.

Two attacks below, both executed, both against code that appears in a great many tutorials including an earlier version of this one.

The Message Recovery Scheme Is Forgeable

Some signature schemes let you recover the message from the signature rather than transmitting both. The naive version looks like this:

def sign_with_recovery(self, message):
    message_int = int.from_bytes(message, byteorder='big')
    return pow(message_int, self.d, self.n)
 
def verify_with_recovery(self, signature):
    recovered_int = pow(signature, self.e, self.n)
    byte_length = (recovered_int.bit_length() + 7) // 8
    return recovered_int.to_bytes(byte_length, byteorder='big')

Read verify_with_recovery carefully. It takes a signature, raises it to e, and returns whatever comes out. There is no check. Anything that comes out is treated as a validly signed message.

So the attack is not an attack so much as running the algorithm backwards:

=== ATTACK 1: existential forgery on sign_with_recovery ===
  The attacker has ONLY the public key (e, n).
  attacker picks random s   = 3486635632218626486833836953412178755693...
  computes m = s^e mod n    = 6545999318039468329965289801290269417699...
  verify_with_recovery(s) recovers exactly that m: True
  -> a valid (message, signature) pair, forged with no private key

Pick any number, call it a signature, and compute what it signs. The result is a valid pair that verifies perfectly.

This is existential forgery, and the standard objection — "but the attacker doesn't control the message, it's random garbage" — is weaker than it sounds. It fails the moment the message space has structure the attacker can search, or the verifier accepts anything parseable, or the attacker can try many candidates and keep one that decodes to something useful. It is a real break, and it is why every real scheme checks structure before accepting.

Hashing Helps and Doesn't Finish the Job

The usual fix is to sign a hash rather than the message. That's correct and necessary, for reasons worth being precise about.

RSA can only sign numbers smaller than n. A SHA-256 digest is 256 bits, which fits under any usable modulus.

A hash is a fixed-size fingerprint, so signing cost is constant regardless of message size.

It's what the standards expect — PKCS#1 signs a hash wrapped in a structured DigestInfo, never a bare message.

One correction to a comparison that circulates with this advice: you'll see "hashing is O(n) and RSA is O(log³n), so hashing is cheaper." Those two ns are different things — message length in one, modulus size in the other — so the expressions aren't comparable as written. The real point is simpler: hashing throughput is measured in gigabytes per second, and a single RSA private-key operation costs milliseconds. Hashing a megabyte and signing the digest is enormously cheaper than any scheme that touches the whole message with modular exponentiation.

But hashing alone does not make the scheme safe, because RSA's algebraic structure survives it:

=== ATTACK 2: multiplicative forgery (works even WITH hashing) ===
  attacker has signatures for two messages, multiplies them
  forged signature verifies for m1*m2 mod n: True
  -> RSA's homomorphism: sign(a)*sign(b) = sign(a*b)

Given signatures on two messages, multiplying them yields a valid signature on the product of their hashes. That is RSA's homomorphic property, the same one that makes raw encryption malleable, and no amount of hashing removes it. It removes it only when the padding makes the signed value non-multiplicative — which is what PSS is for.

A Guard That Never Fires

One more detail worth flagging, because it looks like a safety check and isn't:

if hash_int >= self.n:
    raise ValueError(f"Hash too large for key size...")

A SHA-256 digest is at most 256 bits. Checked against every realistic modulus:

  SHA-256 digest as int: 254 bits
    n =  256 bits -> does "hash_int >= n" ever trigger? False
    n =  512 bits -> False
    n = 1024 bits -> False
    n = 2048 bits -> False

It can never fire on a key anyone would use. That's harmless in itself — but a check that cannot fail reads like protection while providing none, and it is exactly the sort of line that stops people asking whether the real problem has been handled.

And on key size: the demonstration used RSA(key_size=1024). NIST deprecated 1024-bit RSA in 2010 and disallowed it for federal use from 2013 — it's roughly 80-bit security. The cryptography library refuses anything below 1024 outright:

  cryptography refuses 512: ValueError key_size must be at least 1024-bits.

Use 2048 minimum, 3072 for anything new.

What PSS Actually Does

The Probabilistic Signature Scheme is the padding that turns the mathematics above into a signature scheme with a security proof.

from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives import hashes
 
key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                  salt_length=padding.PSS.MAX_LENGTH)
 
signature = key.sign(b"Transfer $1000 from Alice to Bob", pss, hashes.SHA256())
key.public_key().verify(signature, b"Transfer $1000 from Alice to Bob",
                        pss, hashes.SHA256())

Both attacks, run against it:

  signature: 256 bytes
  verifies: True
 
  Attack 1 (random signature) against PSS:
    rejected: InvalidSignature
 
  Attack 2 (tampered message):
    rejected: InvalidSignature

The random-signature forgery dies because PSS verification does not just exponentiate and return — it reconstructs an expected encoded message and checks its structure. Building that structure by hand shows what there is to check:

  encoded message: 256 bytes (must equal modulus size)
    maskedDB : 223 bytes
    H        : 32 bytes  (hash of 8 zeros + mHash + salt)
    trailer  : 0xbc   (fixed, always 0xbc)

Three things in there are doing work. The trailer byte is always 0xbc, so a random value fails immediately one time in 256. The 8 zero bytes prepended before hashing exist to domain-separate this from other uses of the same hash. And H is a hash of the message hash plus the salt, so an attacker cannot work backwards from a chosen signature to a chosen message — they'd have to invert SHA-256.

Empirically, across three thousand random 256-byte values:

  PSS      : 0/3000 random 256-byte values accepted
  PKCS1v15 : 0/3000 random 256-byte values accepted

Zero for both, which is what you'd expect — the trailer alone is a 1-in-256 filter and the rest of the structure makes success negligible. The interesting difference between the two paddings isn't random forgery, it's what a slightly wrong implementation lets through.

And the property that kills multiplicative forgery:

  PSS is randomised - two signatures of the SAME message differ: True
  both still verify: 2/2

PSS mixes a random salt into every signature. Sign the same message twice and get two different signatures, both valid. That randomisation breaks the algebraic relationship an attacker needs — you cannot multiply two signatures and get something whose padding is still well-formed.

Note also what verification returns. It returns nothing, and raises InvalidSignature on failure. There is no value to accidentally trust, which is a deliberate API decision and the opposite of verify_with_recovery returning bytes.

One parameter worth understanding rather than copying: salt_length=padding.PSS.MAX_LENGTH uses the largest salt the modulus allows — 222 bytes for SHA-256 at 2048 bits. PSS.DIGEST_LENGTH (32 bytes) is the other common choice and is what interoperates with most other implementations. Verification must know which was used, since the salt length is not recoverable from the signature alone.

The Attack Where One Bad Signature Loses Everything

Every attack so far assumed the signer behaves correctly. This one assumes it glitches once.

Real implementations don't compute s = m^d mod n directly — they use the Chinese Remainder Theorem, working modulo p and q separately and recombining, because it's several times faster:

def sign_crt(m):
    s1 = pow(m, dP, p)          # dP = d mod (p-1)
    s2 = pow(m, dQ, q)          # dQ = d mod (q-1)
    return (s2 + ((qInv * (s1 - s2)) % p) * q) % n

Now suppose a single bit flips during the mod-q half. Cosmic ray, voltage glitch, a laser aimed at a smartcard, an over-clocked CPU. The signature comes out wrong, which sounds like a correctness problem rather than a security one.

It is a total key compromise:

  correct signature verifies: True
  faulty  signature verifies: False
 
  The attacker has: the public key (e,n), the message, and ONE faulty signature.
  gcd(bad^e - m, n) = a 512-bit factor
  is it p? True   is it q? False
  full private key recovered: True

One faulty signature. One gcd. Entire key.

The mathematics is short enough to see. The faulty signature is correct modulo p but wrong modulo q. So bad^e - m is divisible by p and not by q — which makes gcd(bad^e - m, n) exactly p. Factor the modulus, derive d, done.

This is the Bellcore attack — Bellcore announced it by press release in 1996, and Boneh, DeMillo and Lipton published in 1997. It is why fault injection is a real discipline in smartcard and HSM security rather than a curiosity, and the modern attacks use laser fault injection against physical hardware.

The defence is one line, and it is why a signature implementation should verify its own output:

def sign_crt_checked(m):
    s = sign_crt(m)
    if pow(s, e, n) != m:
        raise ValueError("signature failed self-check; possible fault injection")
    return s

  clean   : returned a signature
  faulted : signature failed self-check; possible fault injection
 
  unchecked CRT sign: 1.480 ms
  checked   CRT sign: 1.469 ms   (0.99x)

The check is free. It costs one public-key operation, and e = 65537 has two set bits. Across repeated runs the checked version measured between 0.99x and 1.04x the unchecked one — the difference is entirely measurement noise.

But do not read that as "problem solved," because the literature has moved. Two things are worth knowing.

Modulus fault attacks inject faults into the public modulus before CRT interpolation rather than into either exponentiation, which renders a number of the standard countermeasures ineffective. Between 5 and 45 faults recover the factorisation in seconds, and the results were validated with real laser fault-injection equipment rather than simulated.

And verify-before-return has itself been broken. Recent work on improved PACD-based attacks against RSA-CRT states directly that countermeasures based on verifying the signature before returning it "are no longer efficient," demonstrated against instances up to 8192 bits.

So the honest position: the self-check is necessary, nearly free, and catches the classical attack — and it is not a complete defence. Real protection against fault injection is a hardware and implementation discipline involving redundant computation, invariant checking throughout the CRT steps, and physical countermeasures. That is a specialist field, and it is one more reason the answer to "should I implement RSA signing" stays no.

One connection worth drawing, because it ties back to the padding discussion. The Bellcore attack works against any deterministic padding — PKCS#1 v1.5 and Full-Domain Hash included. Probabilistic schemes where the randomness stays unknown to the attacker are considerably harder to attack this way. PSS's salt is not just about forgery resistance; it removes the attacker's ability to compute the expected μ(m) that the gcd step depends on.

The Parameters That Aren't in the Signature

Two things must match between signing and verification, and neither is recoverable from the signature itself.

The hash algorithm. For PKCS#1 v1.5 it's embedded in the DigestInfo, so a mismatch is caught:

  signed with SHA-256, verified with:
    sha256  : ACCEPTED
    sha1    : rejected
    sha384  : rejected
    sha512  : rejected

The MGF1 hash and salt length for PSS. Neither is encoded anywhere in the output:

  PSS with mismatched MGF1 hash: rejected

That's the correct behaviour, and it means a PSS signature is not self-describing. If you store signatures long-term, store the parameters alongside them — a signature that verified last year will fail after someone "modernises" a default.

PKCS#1 v1.5 Is Still Everywhere, and That's a Problem

You'll meet PKCS1v15 far more often than PSS, because it predates it and is baked into TLS certificates, JWTs (RS256), and code signing.

It is deterministic — the same message always produces the same signature — and it has no security proof. That determinism is exactly the property that made a class of implementation bugs exploitable: verification amounts to reconstructing an expected value and comparing, and parsers that were too permissive about what they reconstructed accepted forged signatures.

The Attack That Explains the CVE

A PKCS#1 v1.5 signature block is 00 01 FF..FF 00 <DigestInfo>, where DigestInfo is an ASN.1 structure naming the hash algorithm and carrying the digest. For SHA-256 it is 51 bytes.

Now consider a verifier that checks the prefix, finds DigestInfo, reads the hash, and stops — ignoring whatever follows. With a small public exponent, that permissiveness is fatal:

  If the verifier only checks the PREFIX and stops at DigestInfo,
  garbage after it is ignored. An attacker with e=3 can then
  construct a value whose cube root is an integer -- forging a
  signature with no private key at all.

This is Bleichenbacher's '06 forgery, presented at the CRYPTO 2006 rump session — an evening talk, not a paper — and documented afterwards by Hal Finney. The original attack exploited implementations that did not require the payload to be right-justified with adequate padding. At the time both OpenSSL and NSS were vulnerable.

e = 3 is the enabling condition, which is why 65537 is standard. Note that 65537 has the same number of set bits as 3 — two — so it costs essentially nothing extra while removing the cube-root shortcut entirely.

Twenty Years of the Same Bug

The reason to spend time on a 2006 attack is that it has never stopped working. The lineage:

Read the last two rows together. node-forge fixed this class of bug in 2022 by rejecting trailing bytes after the DigestInfo. The 2026 report is the same attack with the garbage moved inside an additional ASN.1 field rather than outside it — and the library accepted it again.

The general lesson: the defence is validating the entire structure, not a prefix, and not the parts you thought to check. Every entry in that table is an implementation that checked something and stopped.

That is not hypothetical. In April 2026, CERT/CC published VU#725167 covering CVE-2026-33894 in node-forge: RSASSA-PKCS#1 v1.5 verification accepted non-canonical ASN.1 DigestInfo encodings and undersized padding, so forged signatures passed. The advisory's own framing is that node-forge accepted signatures rejected by OpenSSL and Node's native crypto. There's more on that failure, and the JavaScript ecosystem's version of this problem, in RSA in JavaScript.

The obvious question is what PSS costs, and the answer removes the last excuse:

  algorithm                  sign   verify    sig
  RSA-2048 PSS              0.38ms   0.04ms    256
  RSA-2048 PKCS1v15         0.37ms   0.03ms    256
  RSA-3072 PSS              0.99ms   0.07ms    384
  ECDSA P-256               0.03ms   0.10ms     71
  Ed25519                   0.04ms   0.12ms     64

PSS and v1.5 are indistinguishable on cost — repeated runs put them within noise of each other, sometimes with v1.5 marginally slower — and both produce 256 bytes. There is no performance argument for the weaker padding — only compatibility.

Two other things fall out of that table. Going to 3072 bits roughly triples signing cost, which is the real price of the extra security margin. And RSA is the odd one out on shape: it signs slowly and verifies very fast, while the elliptic-curve options do the reverse. If you sign far more often than you verify, RSA is the wrong choice on performance alone — and Ed25519 signatures are 64 bytes against 256.

For anything where you control both ends, use PSS. Use v1.5 when a protocol requires it, and keep the library current.

The most common place you'll be forced into it is JWT — RS256 is PKCS#1 v1.5, and the algorithm-confusion attacks that turn token verification into an authentication bypass are covered in RSA in JavaScript Part 2.

What Signatures Actually Guarantee

Worth being precise, because signatures get credited with more than they deliver.

They prove possession of a private key, and nothing about who holds it. Binding a key to an identity is what certificate authorities and webs of trust exist for, and that binding is a separate, harder problem.

They prove the message wasn't modified, and say nothing about when it was signed. A signature has no timestamp; replay is a protocol concern, which is why JWTs carry exp and why code signing uses timestamping authorities.

They don't provide confidentiality. A signed message is readable by anyone. Signing and encryption are separate operations, and combining them naively has its own pitfalls — sign-then-encrypt and encrypt-then-sign have different failure modes.

And they don't prove intent. A key that signs whatever an API hands it will sign an attacker's payload too. Blind signature schemes exist precisely because "sign this" and "endorse this" are different actions.

The Practical Position

Understanding the mathematics is worth it, and it is not a licence to ship it. The two forgeries above took a dozen lines each and no private key.

For real work:

from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives import hashes

2048 bits minimum, PSS for new systems, PKCS#1 v1.5 only where a protocol forces it, and a maintained library rather than your own pow().

What you get from having read this is the ability to look at a signature API and know what each parameter is preventing. salt_length is what stops multiplicative forgery. The hash algorithm has to match on both sides because the padding embeds it. verify raises instead of returning because a scheme that hands back a value invites the caller to trust it.

None of that is obvious from the documentation. It's obvious once you've watched the naive version get forged.