A digital signature proves that a message came from the holder of a private key, and that it was not altered in transit. Anyone with the corresponding public key can verify it. Signatures enable trust without trusted third parties.
How signing works
The signer hashes the message to get a fixed-size digest, then encrypts the digest with their private key. The result is the signature. To verify, the recipient decrypts the signature with the signer's public key and compares it to their own hash of the message. If they match, the signature is valid.
Scheme
; Simplified RSA signature demo; In real RSA, we sign the hash of the message.; Here we sign small numbers directly.
(define (mod-exp base exp mod)
(cond
((= exp 0) 1)
((even? exp)
(let ((half (mod-exp base (/ exp 2) mod)))
(modulo (* half half) mod)))
(else
(modulo (* base (mod-exp base (- exp 1) mod)) mod))))
; RSA key generation (tiny primes for demo)
(define p-prime 61)
(define q-prime 53)
(define n (* p-prime q-prime)) ; 3233
(define phi (* (- p-prime 1) (- q-prime 1))) ; 3120
(define e 17) ; public exponent
(define d 2753) ; private exponent (d*e mod phi = 1); Sign: signature = message^d mod n
(define message 42)
(define signature (mod-exp message d n))
(display "Message: ") (display message) (newline)
(display "Signature: ") (display signature) (newline)
; Verify: recovered = signature^e mod n
(define recovered (mod-exp signature e n))
(display "Recovered: ") (display recovered) (newline)
(display "Valid? ") (display (= recovered message))
Python
# RSA signature (tiny keys for demo)
p, q = 61, 53
n = p * q # 3233
phi = (p-1) * (q-1) # 3120
e = 17# public exponent
d = 2753# private exponent
message = 42
signature = pow(message, d, n)
print(f"Message: {message}")
print(f"Signature: {signature}")
recovered = pow(signature, e, n)
print(f"Recovered: {recovered}")
print(f"Valid? {recovered == message}")
ECDSA
The Elliptic Curve Digital Signature Algorithm uses the same curve group from Ch.7. The signer picks a random nonce k, computes kG, and derives the signature (r, s) from the nonce point's x-coordinate, the message hash, and the private key. Verification uses the public key to check the equation. ECDSA signatures are half the size of RSA signatures at equivalent security.
Scheme
; ECDSA conceptual walkthrough (not full implementation); The key insight: the signature binds the message; to the signer's private key via a random nonce.; Steps (simplified):; 1. Hash the message: h = hash(msg); 2. Pick random nonce k; 3. Compute R = kG (a point on the curve); 4. r = R.x mod n (the order of the curve); 5. s = k^(-1) * (h + r * private_key) mod n; 6. Signature is (r, s); Verification:; 1. Compute w = s^(-1) mod n; 2. u1 = h * w mod n; 3. u2 = r * w mod n; 4. Compute point u1*G + u2*PublicKey; 5. Check that its x-coordinate equals r
(display "ECDSA sign:") (newline)
(display " sig = (r, s) where") (newline)
(display " r = (kG).x mod n") (newline)
(display " s = k^-1 * (hash + r * privkey) mod n") (newline)
(newline)
(display "ECDSA verify:") (newline)
(display " w = s^-1 mod n") (newline)
(display " check (hash*w*G + r*w*PubKey).x == r")
Certificate chains
A certificate binds a public key to an identity (e.g., "example.com"). A certificate authority (CA) signs this binding with its own private key. Your browser trusts a set of root CAs. Each root CA can sign intermediate CAs, which sign end-entity certificates. This chain of signatures is the certificate chain.
Scheme
; Certificate chain as nested signatures; Root CA signs Intermediate CA, which signs the site cert.
(display "Certificate chain:") (newline)
(display " Root CA (trusted by your browser)") (newline)
(display " signs -> Intermediate CA cert") (newline)
(display " signs -> example.com cert") (newline)
(newline)
(display "Verification walks the chain:") (newline)
(display " 1. Check example.com cert signature") (newline)
(display " using Intermediate CA public key") (newline)
(display " 2. Check Intermediate CA cert signature") (newline)
(display " using Root CA public key") (newline)
(display " 3. Root CA is in the trust store") (newline)
(newline)
(display "If any link breaks, the chain fails.")
Digital signature