Cairn
algorithms · cryptography · O(log n) time to sign/verify, one modular exponentiation each, the same cost as RSA Encryption's own encrypt/decrypt; forging a signature without the private key is exactly as hard as breaking RSA itself

↩ back to Cryptography

RSA Digital Signature

The site's fifth Cryptography entry, closing a forward reference Diffie–Hellman Key Exchange's own Pitfalls section left named but unbuilt: that page's man-in-the-middle weakness can't be fixed by its own arithmetic, because "real systems (TLS, for instance) layer authentication — certificates, digital signatures — on top of this exact exchange rather than changing it." A signature answers a different question than RSA Encryption does. Encryption asks "can only the intended recipient read this?" A signature asks "could only the claimed sender have produced this?" RSA answers both questions with the exact same trapdoor, just with the two exponents' roles swapped: encryption's secrecy comes from only the private-key holder being able to undo the public operation; a signature's authenticity comes from only the private-key holder being able to produce something the public operation can check.

It also completes a set with this category's other two authentication-shaped entries. HMAC already proves a message came from whoever holds a shared secret — but both signer and checker need that same secret in advance, which only works between parties who already trust each other with it. A signature trades the shared secret for a key pair: anyone holding only the public key can verify, without that ability ever letting them forge one themselves. That asymmetry is structurally unavailable to a symmetric MAC like HMAC — it's the whole reason a certificate authority can hand out a public key to the entire internet without handing out the power to impersonate anyone.

Try it

Same three (p, q) presets as RSA Encryption's own page, since this page reuses that page's keygen/modpow/modinv verbatim (see Reference implementation) — only the direction each exponent is applied in changes. Type a message and click Sign: this page's own SHA-256 implementation hashes it, reduces the digest modulo n, and raises that to the private exponent d. The message and signature below are filled in automatically; try editing either one and clicking Verify again.

Changing one character of the message changes its hash completely, so the old signature no longer matches — the same avalanche behavior SHA-256's own page demonstrates directly. Changing the signature itself, even by one digit, fails just as surely, since modpow with the public exponent lands on a different number almost every time. Either edit is exactly the kind of tampering a signature exists to catch.

Real signature schemes always hash the message first rather than signing it raw, and the next demo shows why that's load-bearing, not a style choice. Two small numeric messages below are signed directly — no hashing at all — with the same private key as above.

Signs m1 and m2 directly (raw, unhashed) with the real private key, then checks whether multiplying the two signatures forges a valid signature for their product — without the forger ever touching d.

Why it works

RSA Encryption's own "Why it works" section shows (mᵉ)ᵃ = m (mod n) for any message m coprime to n, by Euler's theorem — encrypting with the public exponent and decrypting with the private one are inverse operations, and because modular exponentiation commutes, applying them in the other order gives the exact same identity: (mᵃ)ᵉ = mᵃᵉ = mᵉᵃ = m (mod n). Signing uses that second order. sign(m) = H(m)ᵃ mod n raises the message's hash to the private exponent first — something only the holder of d can compute. verify(m, s) = sᵉ mod n checks it by applying the public exponent, which anyone can do, and comparing the result to a fresh hash of the message computed independently. The two sides of the identity meeting is exactly what a correctly signed message guarantees; an attacker without d has no way to produce a value that survives the public exponent and lands back on the right hash, for the same reason they can't decrypt a ciphertext they didn't make: both require inverting the public operation without the one piece of information that makes inverting it cheap.

The raw-forgery demo above works for a structural reason RSA Encryption's own Pitfalls section already proves for encryption, transplanted here: sign is multiplicative. sign(m1) · sign(m2) = m1ᵃ · m2ᵃ = (m1·m2)ᵃ = sign(m1·m2) (mod n) — multiplying two valid signatures produces a valid signature for the product of their messages, with no private key and no factoring required, only ordinary multiplication mod n. Hashing first breaks exactly this shortcut, not by making the arithmetic harder but by removing the structure the shortcut depends on. sign(m) = H(m)ᵃ mod n is still multiplicative in the hash — H(m1)ᵃ·H(m2)ᵃ = (H(m1)·H(m2))ᵃ mod n still holds — but a real cryptographic hash is designed so that H(m1)·H(m2) mod n essentially never equals H(m1·m2 mod n) for any message an attacker would actually want signed. The forged value in the second demo's final button is a real signature of something — just not of any message whose content the forger got to choose, which is all a signature scheme actually promises to prevent.

Reference implementation

Reuses RSA Encryption's own keygen, modpow, modinv, and gcd verbatim — this page adds only the hash reduction and the two functions that apply it:

// sha256Hex(bytes) is this page's own embedded copy of SHA-256's reference implementation —
// see sha-256.html for the full processBlocks/padMessage breakdown.

function hashModN(message, n) {
  const digestHex = sha256Hex(utf8Bytes(message));
  const digestBig = BigInt('0x' + digestHex) % BigInt(n);
  return Number(digestBig);           // always < n here, so safely back in plain-number range
}

function sign(message, d, n) {
  const h = hashModN(message, n);
  return modpow(h, d, n);             // only the private-key holder can compute this
}

function verify(message, signature, e, n) {
  const h = hashModN(message, n);
  return modpow(signature, e, n) === h;   // anyone with the public key can check this
}

Checked against the hand-worked numbers for all three presets before any of it reached this page: at n = 3,233, e = 7, d = 1,783 (the same key pair RSA Encryption's own first preset generates), signing "pay alice 100 coins" gives a hash-mod-n of 2,918 and a signature of 641, and verify recovers 2,918 from that signature exactly — while the raw-forgery demo's sig(5) · sig(7) mod 3233 = 2,247 matches a direct signature of 35 mod 3233 exactly, and the same multiplication attempted against hash-mod-n values instead (429) does not match a direct hash-first signature of "35" (3,202) — all four outcomes reproduced in a scratch Node script against this exact client-side code before trusting the live page.

Pitfalls

Signing a raw, unhashed message is forgeable without the private key — demonstrated above, not just asserted. The first button in the second demo above runs the real multiplicative forgery: two genuine signatures, produced with the real d, combine into a third valid signature the signer never actually produced, for a message the signer never saw. This is the exact multiplicative structure RSA Encryption's own Pitfalls section already documents for plain ciphertexts — here it breaks authenticity instead of secrecy, which is arguably worse: a forged signature can be presented as proof of consent to something the key's owner never agreed to.

Hashing first closes that specific shortcut, but only because a real hash function has no usable algebraic structure of its own. The second button above tries the identical multiply-two-signatures trick against hash-mod-n values and fails, every time, for every preset — not because the arithmetic changed, but because H(m1)·H(m2) mod n has no relationship to H(m1·m2 mod n) for a hash designed the way SHA-256 is. Real deployments go one step further and don't hash-and-sign directly either: standard padding schemes (RSASSA-PSS, or the older PKCS#1 v1.5) add randomization and structure around the hash before the exponentiation, the same role OAEP plays for encryption on RSA Encryption's own Pitfalls section — OAEP itself is now built as its own entry, but these two signature-specific padding schemes (RSASSA-PSS, PKCS#1 v1.5) remain unbuilt here.

A small enough modulus is just as crackable here as it is for encryption. Nothing about signing changes the fact that recovering d from the public (n, e) means factoring n — this page's second preset is the identical n = 8,051 that Pollard's Rho's own demo factors in 3 steps, and the same toy-sized factoring risk RSA Encryption's own Pitfalls section demonstrates against encryption applies here against forgery, unchanged.

Complexity

Time: O(log n) per sign or verify — one modular exponentiation via the same square-and-multiply modpow RSA Encryption uses, plus one linear-time hash pass over the message, the same O(n) SHA-256 cost named on its own page. Space: O(1) beyond the message and the fixed-size key material. Security: forging a signature without d, once the message is hashed first, is believed as hard as the underlying RSA problem itself — recovering d from (n, e) alone, equivalent to factoring n, with no known polynomial algorithm. Without hashing, the scheme is not secure at all against the specific multiplicative forgery demonstrated above, regardless of key size — a reminder that this page's security claim describes the hash-first construction only, the one actually in the "Try it" demo's first button, not the raw variant the second demo deliberately breaks.