02 — Foundations
Cryptographic Primitives
Four building blocks. Every secure system is a composition of these.
① Encryption
Reversible transform: c = E(k, m) and m = D(k, c). Symmetric uses one shared key; asymmetric uses a public/private pair. Provides confidentiality.
② Hash Function
One-way map h : {0,1}* → {0,1}ⁿ. Fixed-size digest of arbitrary input. Three required properties:
- Pre-image resistant — given h, infeasible to find m with H(m)=h
- Second pre-image resistant — given m, infeasible to find m' ≠ m with H(m')=H(m)
- Collision resistant — infeasible to find any (m, m') pair with H(m)=H(m')
Examples: SHA-256, SHA-3, BLAKE2. (MD5 and SHA-1 are broken — collisions found.)
Theory — the birthday bound
For an n-bit hash, collisions appear after only ~2n/2 tries (birthday paradox), not 2n. That is why SHA-256 gives only 128-bit collision security:collision effort ≈ 2^(n/2)
SHA-256 (n=256) → 2^128 operations
MD5 (n=128) → 2^64 # feasible → broken
③ MAC (Message Authentication Code)
Keyed hash: tag = MAC(k, m). Verifier with same key recomputes and compares. Provides integrity + authenticity but not non-repudiation (any key-holder could have produced it). Examples: HMAC-SHA256, CBC-MAC, Poly1305.
# HMAC construction ( works with any hash H )
HMAC(K, m) = H( (K ⊕ opad) ‖ H( (K ⊕ ipad) ‖ m ) )
opad = 0x5c repeated, ipad = 0x36 repeated
④ Digital Signature — How It Works
Signer hashes the message → h = H(m)
Encrypts the hash with private key → σ = E_priv(h)
Sends (m, σ) to the verifier
Verifier decrypts σ with signer's public key → h'
Verifier hashes received message → h = H(m)
Compares h' ?= h. If equal → authentic & untampered.
Why it works
Only the private-key holder can produce a valid σ; anyone with the public key can verify. This gives integrity + authenticity + non-repudiation in one operation.| Primitive | Keyed? | Reversible? | Provides |
|---|---|---|---|
| Encryption | Yes | Yes | Confidentiality |
| Hash | No | No | Integrity (detection only) |
| MAC | Yes (shared) | No | Integrity + Authenticity |
| Signature | Yes (pub/priv) | No (verify only) | Integrity + Auth + Non-repudiation |
Exam one-liner: Hash detects change, MAC proves a key-holder sent it, signature proves which key-holder and they can't deny it.