Cryptography From Scratch

Cryptography is the discipline of transforming information so that only intended parties can read it. The word comes from Greek: kryptos (hidden) + graphein (to write). For security engineers, cryptography is not primarily a mathematical topic — it is a tool. You need to know which tool does what, when each one breaks, and why choosing the wrong one destroys the security guarantee you thought you had.

Modern cryptography provides four security properties:

No single cryptographic primitive provides all four. This is why real security systems combine multiple primitives — a TLS connection uses symmetric encryption (confidentiality), a MAC (integrity + authentication), and certificates (authentication + non-repudiation). Understanding which primitive provides which property is the foundation of cryptographic engineering.

Symmetric encryption uses the same key for both encryption and decryption. Think of a physical safe with one key: whoever has the key can lock and unlock it. The security guarantee: without the key, the ciphertext is computationally indistinguishable from random noise — an attacker learns nothing.

How AES Works — Without the Math

AES (Advanced Encryption Standard) is the gold standard symmetric cipher. It operates on fixed 128-bit blocks of data using a key of 128, 192, or 256 bits. Here is the conceptual model:

Plaintext (128 bits = 16 bytes)  +  Key (128/192/256 bits)
                   ↓
         [10/12/14 rounds of:]
           1. SubBytes   — replace each byte using a lookup table (S-box)
           2. ShiftRows  — shift rows of the 4×4 byte matrix cyclically
           3. MixColumns — linear transformation across each column
           4. AddRoundKey — XOR with the round key derived from the main key
                   ↓
         Ciphertext (128 bits) — looks like random noise without the key

AES-256 is considered quantum-resistant to a significant degree — even with a quantum computer using Grover's algorithm, the effective security is reduced from 256 to 128 bits, which remains computationally infeasible to brute force. AES has been the standard since 2001, survived extensive cryptanalysis, and no practical attack against a correctly implemented AES-256 exists today.

Block Cipher Modes — Where Things Go Wrong

AES encrypts exactly 128 bits at a time. Real data is longer. The mode of operation determines how AES is applied repeatedly to longer data. Choosing the wrong mode destroys security even though the underlying cipher is strong.

The Key Distribution Problem

Symmetric encryption has a fundamental problem: both parties need the same key, but they have to share it over an insecure channel. If you and a server have never communicated before, how do you agree on a secret key without an eavesdropper learning it? This is the key distribution problem. It is the reason asymmetric cryptography was invented.

Asymmetric (public-key) cryptography uses a mathematically linked key pair: a public key that can be freely shared, and a private key that must never leave your possession. The fundamental property: what one key encrypts, only the other key can decrypt.

How RSA Works — Conceptually

RSA's security rests on a mathematical asymmetry: it is easy to multiply two large prime numbers together, but computationally hard to factor the result back into the original primes. This is called the integer factorisation problem.

Key generation:
  1. Choose two large prime numbers p and q (each 1024+ bits)
  2. Compute n = p × q  (the modulus — this is public)
  3. Compute φ(n) = (p-1)(q-1)  (kept secret)
  4. Choose e (public exponent, usually 65537)
  5. Compute d such that e × d ≡ 1 (mod φ(n))  (private exponent)

Public key:  (n, e)  — safe to share with the world
Private key: (n, d)  — never share

Encryption:  ciphertext = plaintext^e mod n   (anyone can do this with public key)
Decryption:  plaintext = ciphertext^d mod n   (only holder of d can do this)

Why it works: recovering d from (n, e) requires factoring n back into p and q
              With a 2048-bit n, this takes longer than the age of the universe
              on classical computers

RSA in Practice

RSA is not used to encrypt large data — it is slow and limited to encrypting data smaller than the key size. The standard pattern: use RSA to encrypt a randomly generated AES key (called key encapsulation), then use that AES key to encrypt the actual data. The recipient uses their RSA private key to recover the AES key, then uses AES to decrypt the data. This hybrid approach combines RSA's key distribution capability with AES's speed.

Elliptic Curve Cryptography (ECC) — The Modern Standard

ECC achieves the same security as RSA with much shorter keys, by basing security on the elliptic curve discrete logarithm problem. A 256-bit ECC key provides equivalent security to a 3072-bit RSA key. This means smaller keys, faster operations, and less computational overhead — which is why ECC has largely replaced RSA in modern systems.

Key size equivalents:
RSA 1024 bits  ≈ ECC 160 bits  (now broken — do not use)
RSA 2048 bits  ≈ ECC 224 bits  (minimum acceptable)
RSA 3072 bits  ≈ ECC 256 bits  ← NIST P-256 — current standard
RSA 7680 bits  ≈ ECC 384 bits  ← for highly sensitive applications

Common ECC curves used in practice:
P-256 (NIST)    — TLS, certificates, FIDO2
P-384 (NIST)    — higher security requirements
X25519          — Diffie-Hellman key exchange in TLS 1.3
Ed25519         — SSH keys, code signing

Diffie-Hellman Key Exchange — Sharing a Secret in Public

Diffie-Hellman (DH) solves the key distribution problem: two parties can agree on a shared secret over a public channel without ever transmitting the secret itself, even though an eavesdropper can see all their messages.

Analogy using colours (simplified):
  1. Alice and Bob agree on a public colour: Yellow (visible to Eve)
  2. Alice picks a secret colour: Red. Mixes with Yellow → Orange (sends to Bob)
  3. Bob picks a secret colour: Blue. Mixes with Yellow → Green (sends to Alice)
  4. Alice mixes Bob's Green with her secret Red → Brown
  5. Bob mixes Alice's Orange with his secret Blue → Brown (same!)
  Eve sees: Yellow, Orange, Green — but cannot derive Brown without a secret colour

In math: the "mixing" is modular exponentiation
  The shared secret that Alice and Bob both arrive at is used as a symmetric key
  Eve, who watched everything, cannot compute it without solving the DLP

Ephemeral Diffie-Hellman (DHE / ECDHE) generates new key pairs for every session. This provides Perfect Forward Secrecy (PFS): if a server's private key is compromised in the future, an attacker who recorded past traffic cannot decrypt it, because each session used a different ephemeral key that no longer exists. TLS 1.3 mandates ECDHE — it removed all non-forward-secret cipher suites.

A cryptographic hash function takes input data of any size and produces a fixed-size output (the hash or digest). The critical properties:

Hash Algorithm Comparison

Why Password Hashing Is Different

SHA-256 is designed to be fast — a GPU can compute billions of SHA-256 hashes per second. This is catastrophic for password storage. An attacker with a breached database of SHA-256 password hashes can test every word in a dictionary, every combination of words, and every common password pattern in minutes.

Password hashing algorithms like bcrypt, scrypt, and Argon2 are deliberately slow and memory-intensive. Argon2 is configurable — increasing the cost parameter makes each hash take longer. A hash that takes 100ms on a legitimate login server takes 100ms per guess on an attacker's GPU — turning a database with a million passwords into a years-long cracking job rather than an hours-long one.

# Password hash formats in the wild
$2y$12$rounds...  → bcrypt with 12 rounds (2^12 = 4096 iterations)
$argon2id$...     → Argon2id — recommended for new systems
$6$rounds=656000$ → SHA-512 crypt (Linux /etc/shadow) — acceptable

# Never store passwords as:
SHA-256(password)  → cracked in seconds (rainbow tables, GPU)
MD5(password)      → cracked in milliseconds
plaintext          → this happens more than you would think

HMAC — Authentication with Hash Functions

A hash alone cannot authenticate a message — anyone can compute SHA-256(data). To prove the message came from someone with a specific key, you use HMAC (Hash-based Message Authentication Code):

HMAC-SHA256(key, message) = SHA256(key ⊕ opad || SHA256(key ⊕ ipad || message))
# The key is mixed into the hash so only the key holder can produce the same output

# Use cases:
# - JWT (JSON Web Tokens) signature verification
# - API authentication (AWS Signature, webhook validation)
# - Cookie integrity (signed cookies)
# - Message integrity in TLS and SSH

A digital signature provides authentication and non-repudiation using asymmetric cryptography. It proves two things: the message came from the holder of a specific private key, and the message has not been modified since signing.

How Signing Works

Signing (done by sender with PRIVATE key):
  1. Hash the message: h = SHA256(message)
  2. Encrypt the hash with the sender's private key: signature = RSA_decrypt(privateKey, h)
     Note: "encrypt with private key" = signing (counterintuitive naming)
  3. Send (message + signature) to the receiver

Verification (done by receiver with PUBLIC key):
  1. Hash the received message: h' = SHA256(received_message)
  2. Decrypt the signature with the sender's PUBLIC key: h = RSA_encrypt(publicKey, signature)
  3. Compare h and h'
     If h == h': the message was signed by the private key owner and was not modified
     If h != h': the message was tampered with or was not signed by the claimed sender

Digital Certificates — Binding Public Keys to Identity

A public key is just a number. Without a way to verify which person or organisation that key belongs to, public key cryptography is vulnerable to impersonation. Digital certificates solve this by binding a public key to an identity (a domain name, an organisation, a person) with a trusted third party's signature.

X.509 Certificate structure (simplified):
  Subject:        CN=bank.example.com          ← who this certificate is for
  Public Key:     RSA 2048-bit key material    ← the key being certified
  Issuer:         DigiCert TLS RSA SHA256 CA   ← who signed this certificate
  Valid From:     2026-01-01
  Valid Until:    2027-01-01
  Extensions:
    SAN:          bank.example.com, www.bank.example.com  ← additional names
    Key Usage:    Digital Signature, Key Encipherment
  Signature:      [DigiCert's signature over all of the above]

The Chain of Trust

A certificate is only trustworthy if the issuer is trustworthy. Certificates form a chain:

Certificate validation: your browser downloads the certificate, checks the signature against the Intermediate CA's public key, checks the Intermediate CA's certificate against the Root CA's public key, and verifies that the Root CA is in its trusted store. Any break in the chain — expired certificate, untrusted issuer, mismatched domain — causes the browser to reject the connection.

TLS 1.3 — A Real Cryptographic Protocol

TLS 1.3 Handshake:

Client → Server: ClientHello
  Supported cipher suites: [TLS_AES_256_GCM_SHA384, TLS_CHACHA20_POLY1305_SHA256]
  Key exchange: ECDHE with X25519 (ephemeral key — new for every session)
  Client random: 32 bytes

Server → Server: (Generates ephemeral ECDHE key pair)

Server → Client: ServerHello
  Selected cipher: TLS_AES_256_GCM_SHA384
  Server's ECDHE public key
  Certificate (signed by CA — proves server identity)
  Certificate Verify (signature of the handshake with server's private key)
  Finished (HMAC of all handshake messages)

[Both derive the same shared secret via ECDHE — Diffie-Hellman]

Client → Server: Finished (HMAC confirms client received identical handshake)

[All subsequent traffic encrypted with AES-256-GCM]
[Session keys derived from the ECDHE shared secret — discarded after session]

What each primitive does here: ECDHE solves key distribution (both derive the same session key without transmitting it). AES-256-GCM provides confidentiality and integrity for the session data. The certificate + signature provides authentication (this is actually the server you intended to reach). HMAC-SHA384 verifies the handshake was not tampered with. Remove any one primitive and the security guarantee collapses.

SSH Key Authentication

1. Server sends a random challenge
2. Client signs the challenge with their Ed25519 private key
3. Server verifies the signature against the stored public key
4. Verified = authenticated. No password exchanged.

Why this is secure:
- The private key never leaves the client machine
- A network observer sees only the challenge and signature — cannot derive the private key
- A stolen authorized_keys file is useless without the private key

JWT — JSON Web Tokens

JWT format: header.payload.signature
All three parts are Base64url-encoded

Header: {"alg": "HS256", "typ": "JWT"}
Payload: {"sub": "user123", "role": "admin", "exp": 1777777777}
Signature: HMAC-SHA256(secret, base64(header) + "." + base64(payload))

Verification:
  1. Decode header — get algorithm
  2. Recompute signature using the server's secret key
  3. Compare to received signature
  4. If match: payload is authentic — user is who they claim to be
  5. Check exp — is the token expired?

The vulnerability pattern:
  {"alg": "none"} — some libraries accepted this, treating the signature as optional
  {"alg": "HS256"} with the public key as the secret — confusing RSA and HMAC
  Always explicitly specify acceptable algorithms in your JWT library

Quantum computers pose a specific threat to asymmetric cryptography. Shor's algorithm running on a sufficiently large quantum computer can factor large integers and solve the discrete logarithm problem exponentially faster than classical computers — breaking RSA and ECC. Grover's algorithm can search an unsorted database quadratically faster, effectively halving the security of symmetric keys (a 256-bit AES key becomes equivalent to 128-bit against a quantum attacker).

The timeline for cryptographically relevant quantum computers (large enough to break RSA-2048) is genuinely uncertain — estimates from "never" to "within 10-15 years." What is certain is that adversaries are doing "harvest now, decrypt later" — collecting encrypted traffic today to decrypt once quantum computers exist. For data that must remain confidential for 10+ years, the threat is current.

NIST standardised the first post-quantum cryptography algorithms in 2024: