Digital Signatures

A digital signature lets anyone verify two things about a piece of data:

1. Authenticity — it really came from the holder of the private key.
2. Integrity — it hasn't been modified since it was signed.

Same construction as the public-vs-private lesson — sign with private, verify with public — but the schemes matter. Pick the wrong one and you ship a system that can be forged.

The hash-then-sign pattern

Every modern signature scheme follows the same shape:

sign(message, private_key):
  digest = HASH(message)              ← e.g. SHA-256
  return SIGN_PRIMITIVE(digest, private_key)

verify(message, signature, public_key):
  digest = HASH(message)
  return VERIFY_PRIMITIVE(digest, signature, public_key)

You never sign the raw message. You hash it first, then sign the hash. Reasons:

• Asymmetric primitives operate on a fixed-size input (the size of n for RSA, the size of the curve scalar for ECDSA / Ed25519). Messages are arbitrary length.
• A hash gives the signature a fixed structure regardless of input size.
• Signing the hash is faster than signing many bytes. The slow part is the public-key operation; the hash is cheap.

In Ed25519 the hash is baked into the spec — Sign(m) internally computes SHA-512(prefix || m). In RSA-PSS and ECDSA you pick the hash explicitly.

The three schemes you'll meet

RSA-PSS

PKCS#1 v1.5 was the original RSA padding scheme. It's been slowly replaced because of structural attacks (Bleichenbacher 1998 oracle, ROBOT 2017). PSS — Probabilistic Signature Scheme — is the modern padding:

hash || padding || randomness  →  encode  →  RSA-sign

The randomness makes each signature unique even for identical messages, and PSS has a security proof in the random-oracle model. Use PSS for new RSA signatures. Use v1.5 only if you're stuck with a peer that can't accept PSS (some older code-signing tooling, certain JWT libraries).

Scheme	Status	Use it?
RSA PKCS#1 v1.5 sig	Legacy	Only for compat with old systems
RSA-PSS	Modern	Yes — preferred RSA signature padding
RSASSA-PSS-SHA256 (TLS 1.3)	Mandatory in TLS 1.3	Yes

ECDSA

The standard signature scheme on NIST curves (P-256, P-384). Defined in FIPS 186-4. Mathematical structure:

sign(m, d):                      verify(m, (r, s), Q):
  k = random nonce               e = hash(m)
  (x, y) = k·G                   w = s⁻¹ mod n
  r = x mod n                    u₁ = e·w mod n
  s = k⁻¹ · (hash(m) + d·r)      u₂ = r·w mod n
                                 (x', y') = u₁·G + u₂·Q
                                 accept if x' mod n == r

The infamous fragility: k must be a fresh, unpredictable, unbiased nonce per signature. If two signatures share k:

sig1: s₁ = k⁻¹ (h₁ + d·r)         where r = (k·G).x for both
sig2: s₂ = k⁻¹ (h₂ + d·r)
      s₁ - s₂ = k⁻¹ (h₁ - h₂)
      ⇒ k = (h₁ - h₂) / (s₁ - s₂)
      ⇒ d = (s₁·k - h₁) / r

The private key falls out of two simultaneous equations. This is exactly how Sony's PlayStation 3 master signing key was recovered in 2010 — every game shipped with a fixed nonce. Bitcoin wallets have leaked keys to this same bug repeatedly.

Defence: derive k deterministically from (d, m) per RFC 6979. Modern libraries (libsodium, BoringSSL, the Python cryptography package) do this by default.

Ed25519

The 2010s answer to all of ECDSA's footguns. Ed25519:

• Uses a deterministic nonce (no k to mess up).
• Uses a special curve form (twisted Edwards) chosen for constant-time arithmetic.
• Has a fixed signature size (64 bytes).
• Has no padding choices, no hash choices, no parameters.

sign(m, seed):
  h = SHA-512(seed)
  prefix = h[32..64]
  k = SHA-512(prefix || m) mod n   ← deterministic, no randomness
  R = k · G
  s = k + hash(R || A || m) · clamped_seed mod n
  return (R, s)

Same private key + same message → byte-identical signature. Reproducible builds love this. No nonce-reuse class of bug.

Determinism, reproducibility, attestation

Three reasons deterministic signatures matter in practice:

1. Reproducible builds. Two independent CI runs that sign the same artifact with the same key produce identical outputs. Verifiable supply chain. ECDSA can't do this without RFC 6979.
2. No RNG dependency. Embedded devices and air-gapped signers don't always have a good entropy source at signing time. Ed25519 doesn't need one.
3. Diagnostic visibility. "Same input → same signature" is an invariant you can test in CI. ECDSA without RFC 6979 forces you to test "valid against verify" instead, which catches fewer bugs.

Threat models

• Existential forgery: attacker produces a valid (m, sig) pair for any m of their choosing. Modern schemes are designed to resist this under the random-oracle model.
• Selective forgery: attacker picks a target m in advance and produces a valid sig. Even harder to achieve.
• Universal forgery: attacker recovers the private key. The PS3 attack was universal forgery via nonce reuse.

A signature scheme is "secure" only against the threat model it was designed for. Raw RSA without padding is malleable — given a valid (m, sig), an attacker can produce (m', sig') for a chosen m' even without the key. PKCS#1 v1.5 padding partially fixes this but has its own attacks. PSS is the current best answer for RSA. Ed25519 has no comparable malleability bugs.

What this lesson asks of you

The playground asks you to choose the right signature scheme and configuration for five concrete contexts (release artifacts, JWTs, Bitcoin transactions, embedded device, FIDO2). The visualizer animates the sign-verify flow side by side for ECDSA, Ed25519, and RSA-PSS so you can see why ECDSA's per-signature randomness step is the part that goes wrong.