Digital Signatures

A digital signature scheme is a triple of efficient algorithms $(\text{KeyGen}, \text{Sign}, \text{Verify})$. `KeyGen` outputs a key pair $(sk, pk)$: a private signing key kept secret by the signer, and a public verification key published to the world. `Sign(sk, m)` takes the private key and a message $m$ and outputs a signature $\sigma$. `Verify(pk, m, \sigma)` takes the public key, the message, and a purported signature, and outputs accept or reject. Correctness requires that a signature honestly produced always verifies: $\text{Verify}(pk, m, \text{Sign}(sk, m)) = \text{accept}$ for every valid key pair and message. This is structurally the mirror image of public-key encryption: encryption uses the public key to protect confidentiality, so only the private-key holder can undo it; signing uses the private key to produce a proof of authorship, so anyone with the public key can check it. The security goal is existential unforgeability under chosen-message attack (EUF-CMA): an adversary who can query a signing oracle on messages of its choosing should still be unable to output a valid pair $(m^*, \sigma^*)$ for any message $m^*$ it did not explicitly obtain a signature for — even a nonsensical or garbled message. This is a stronger requirement than "can't forge a signature on a specific message"; it rules out forging any new message-signature pair whatsoever. In practice, one never signs a raw message directly. Instead, the message is first passed through a cryptographic hash function $H$ (e.g., SHA-256), and the signature is computed over the fixed-length digest $H(m)$. This serves two purposes: it makes signing efficient regardless of message length, and — critically for RSA — it destroys the multiplicative algebraic structure of the raw RSA function that would otherwise enable forgery attacks. The combination of hashing plus a specific algebraic signing operation, together with (for RSA) a randomized padding transform, constitutes a concrete scheme like RSA-PSS or ECDSA.

RSA signatures (textbook, then hardened). Recall RSA key generation: choose primes $p, q$, set $n = pq$, choose public exponent $e$ coprime to $\varphi(n) = (p-1)(q-1)$, and compute private exponent $d \equiv e^{-1} \pmod{\varphi(n)}$. The public key is $(n, e)$, the private key is $d$ (equivalently $p, q, d$). The naive ("textbook") RSA signature is $\sigma = H(m)^d \bmod n$, verified by checking $\sigma^e \bmod n \stackrel{?}{=} H(m)$. This works because RSA encryption and decryption are inverse permutations: $(x^d)^e \equiv x^{ed} \equiv x \pmod n$ whenever $ed \equiv 1 \pmod{\varphi(n)}$, by Euler's theorem. But textbook RSA signing is insecure on its own: it is multiplicative, meaning $\sigma_1 \cdot \sigma_2 \equiv (H(m_1) H(m_2))^d \pmod n$, allowing an attacker to combine signatures on chosen messages to forge a signature on a related, unrequested message. RSA-PSS (Probabilistic Signature Scheme) fixes this by applying a randomized, structured encoding function to $H(m)$ before the modular exponentiation, using a fresh random salt each time, which destroys the exploitable algebraic relationship and — crucially — makes the scheme provably secure in the random oracle model.

ECDSA (Elliptic Curve Digital Signature Algorithm). Given a curve with base point $G$ of prime order $q$, the signer's private key is a random scalar $d \in [1, q-1]$, and the public key is the point $Q = dG$. Signing requires a fresh, secret, unpredictable per-signature nonce $k$; verification uses only public data. ```pseudocode // ===== ECDSA over a curve with base point G, order q ===== function KeyGen(): d ← random integer in [1, q-1] // private key Q ← d · G // public key (point) return (d, Q) function Sign(d, m): e ← H(m) mod q // hash, truncated/reduced mod q repeat: k ← random integer in [1, q-1] // MUST be fresh, secret, unpredictable (x1, y1) ← k · G r ← x1 mod q until r ≠ 0 s ← k^{-1} · (e + r·d) mod q until s ≠ 0 // (re-pick k if s = 0; probability ~0) return (r, s) function Verify(Q, m, (r, s)): if r ∉ [1, q-1] or s ∉ [1, q-1]: return reject e ← H(m) mod q w ← s^{-1} mod q u1 ← e·w mod q u2 ← r·w mod q (x1, y1) ← u1·G + u2·Q if (x1, y1) = O (point at infinity): return reject if r ≡ x1 (mod q): return accept else: return reject ```

RSA-PSS, side by side for comparison: ```pseudocode // ===== RSA-PSS (simplified) over modulus n, exponent e, private exponent d ===== function Sign(d, n, m): mHash ← H(m) salt ← random bytes of fixed length EM ← PSS_Encode(mHash, salt) // MGF-based padding, deterministic given salt σ ← EM^d mod n return σ function Verify(e, n, m, σ): EM' ← σ^e mod n mHash ← H(m) return PSS_Verify(EM', mHash) // recovers salt, recomputes MGF, compares ``` The public-key pair for RSA is $(n, e)$ and the private key is $d$; for ECDSA it is $(Q)$ public and $d$ private, with the curve and $G$ as shared system parameters. In both schemes, signing uses the secret and verification uses only public quantities — the essential asymmetry that gives non-repudiation.

Time complexity. For RSA signing (with $n$ an $\ell$-bit modulus), the dominant cost is modular exponentiation $x^d \bmod n$, done via square-and-multiply in $O(\ell)$ modular multiplications, each costing $O(\ell^2)$ with schoolbook multiplication (or $O(\ell \log \ell)$ with FFT-based methods) — giving $O(\ell^3)$ naive total, dramatically reduced in practice using the Chinese Remainder Theorem (CRT), which performs two exponentiations modulo the half-size primes $p, q$ instead of one modulo the full $n$, yielding roughly a $4\times$ speedup. Verification uses the small public exponent $e$ (commonly $65537 = 2^{16}+1$), needing only about 17 modular multiplications, so RSA verification is much faster than RSA signing — an important asymmetry: browsers verify certificates far more often than CAs sign them. For ECDSA over a curve with an $n$-bit order, signing and verification both cost one or two scalar multiplications $k \cdot G$, each computable via double-and-add in $O(n)$ point additions, each point addition costing $O(1)$ field operations on $O(n)$-bit numbers. Concretely, ECDSA signatures are far smaller (a 256-bit curve gives ~64-byte signatures) than RSA's (256-byte for RSA-2048) for comparable security levels, because elliptic-curve discrete log currently has no known sub-exponential attack, whereas RSA's security rests on integer factorization, which is broken by the sub-exponential general number field sieve, forcing RSA to use much larger moduli for equivalent hardness.

Space complexity. RSA public keys are $O(\ell)$ bits ($\ell = 2048$–$4096$ typically); ECDSA public keys are $O(n)$ bits with $n = 256$–$384$ typically, giving roughly an order-of-magnitude space savings for equivalent conjectured security.

Correctness (why verification accepts honest signatures). RSA: by Euler's theorem, for any $x$ coprime to $n$, $x^{ed} \equiv x \pmod n$ whenever $ed \equiv 1 \pmod{\varphi(n)}$, which holds by construction of $d$ as the modular inverse of $e$. So $\sigma^e = (H(m)^d)^e = H(m)^{ed} \equiv H(m) \pmod n$, matching what `Verify` recomputes. ECDSA: substitute $s = k^{-1}(e + rd) \bmod q$ into the verifier's computation. We have

but since $s \equiv k^{-1}(e+rd)$, we get $k \equiv s^{-1}(e + rd) \pmod q$, so $u_1 + u_2 d \equiv k \pmod q$. Therefore

whose $x$-coordinate is exactly $r$ by definition — so the check $r \equiv x_1 \pmod q$ succeeds for any honestly generated signature. This is an algebraic identity, not a heuristic; it holds with certainty (not just high probability) whenever the arithmetic is done correctly.

Security (why forgery is hard — the honest tradeoffs). RSA-PSS is provably EUF-CMA secure in the random oracle model, assuming the RSA problem (inverting $x \mapsto x^e \bmod n$ without $d$) is hard; hardness of the RSA problem is widely believed but not proven equivalent to factoring. ECDSA's security proof is comparatively weaker in general — no proof from a clean standard assumption is known for the "raw" DSA/ECDSA construction, though it is secure in idealized models (generic group model plus random oracle) and it has withstood decades of cryptanalysis when correctly implemented. Both schemes' security completely collapses if implementation details are violated: RSA signing must use structured padding (never sign raw hashes without PSS or a properly implemented PKCS#1v1.5), and ECDSA/DSA must never reuse or leak information about the nonce $k$ — a single repeated or partially known nonce across two signatures directly yields the private key via simple linear algebra (shown below).

We trace a full ECDSA signature and verification over a small illustrative curve (small parameters are used purely for hand-computable arithmetic; real deployments use 256-bit+ curves like secp256k1 or P-256). Suppose (toy parameters, not cryptographically secure — for illustration only):

• Curve group with base point $G$ of prime order $q = 17$.
• Private key $d = 5$, so public key $Q = 5G$ (a specific point, computed by the curve's group law — treated here as an opaque point since our focus is the signature arithmetic, not curve arithmetic itself).
• Message digest $e = H(m) \bmod q = 9$.
• Signer picks fresh random nonce $k = 3$.
• Suppose $k \cdot G$ has $x$-coordinate $x_1 = 4$ (a concrete value the curve's group law would produce).

Signing:

Signature: $(r, s) = (4, 4)$.

Verification (verifier knows only $Q$, $m$, $(r,s)$; recomputes $e = 9$):

The verifier recovers $u_1 + u_2 d = 15 + 1\times5 = 20 \equiv 3 \pmod{17} = k$, exactly reconstructing the signer's secret nonce's scalar multiple $kG$, without ever learning $k$ or $d$ — confirming the algebraic identity derived above.

Now, the classic catastrophic failure — nonce reuse. Suppose the signer, careless or using a broken RNG, signs two different messages $m_1, m_2$ (digests $e_1, e_2$) using the same nonce $k$. Then:

Since both use the same $k$, they also share the same $r$ (as $r$ depends only on $kG$). Subtracting:

Once $k$ is recovered, the private key falls out immediately:

This is not a theoretical curiosity — it is precisely the bug that exposed Sony's PlayStation 3 code-signing private key in 2010 (a fixed, non-random $k$ was used for every signature) and has recovered private keys from real Bitcoin wallets with buggy random number generators.

Digital signatures emerged directly from the invention of public-key cryptography, and RSA's own paper already proposed signing as well as encryption.

Digital signatures are the authentication backbone of the modern internet and beyond. Every TLS certificate is a signature by a certificate authority binding a domain name to a public key, the foundation of Public-Key Infrastructure and Certificates; the server then proves possession of the corresponding private key during The TLS Handshake via a fresh signature over the handshake transcript. Code signing (Windows Authenticode, Apple's codesigning, Android APK signing) uses RSA or ECDSA signatures to let operating systems verify that an app or update genuinely came from its claimed publisher before executing it. DNSSEC signs DNS records to prevent cache-poisoning attacks. Cryptocurrencies like Bitcoin and Ethereum authorize every transaction with an ECDSA (or, increasingly, Schnorr/EdDSA) signature proving control of the spending key. Secure email standards (S/MIME, PGP) and document-signing platforms rely on the same primitives to provide legally recognized non-repudiation.

Ask the tutor: How does RSA-PSS's randomized padding formally prevent the multiplicative forgery attack that breaks textbook RSA signatures?