Cryptography from Scratch — Symmetric Keys, Public Keys, and Hashes

Cryptography isn't about producing unreadable text — it's about engineering an extreme gap in effort between people who hold the key and people who don't. We build up the three tools (symmetric, public-key, hashing) from zero, explain why factoring shows up at all, what a signature actually promises, and how every widely deployed cipher has eventually broken.

Cryptography is not about hiding

"Encryption" sounds like magic that turns text into gibberish. But what designers actually build is something far more mundane: a property where anyone holding a secret can reverse the operation cheaply, and anyone without it cannot reverse it in any practical amount of time. That gap in effort is the whole product.

Think about your front door. With a key it opens in a second. Without one, it can still be opened — by picking the lock, by force. The door is "secure" not because it can't be opened, but because opening it costs more than it's worth. Cryptography works the same way. The goal is never "unbreakable"; it's "breaking this takes longer than the age of the universe."

Once you see it that way, the whole field organizes into three tools.

1. Symmetric encryption — same key locks and unlocks. Fast.
2. Public-key encryption — the locking key and the unlocking key are different, which lets you share secrets with someone you've never met.
3. Hash functions — reversal isn't even attempted. They produce a fingerprint of data.

Every real system — HTTPS, SSH, cryptocurrencies, password storage — is these three tools with the labor divided among them. We'll build them up in order, along with the problem each one was invented to solve.

1. Symmetric encryption — one key, both directions

Start with the simplest cipher there is. Take the plaintext as a string of bits, take a key of the same length, and XOR them bit by bit (XOR: 1 if the bits differ, 0 if they match).

$$c = m \oplus k \qquad m = c \oplus k$$

Here $m$ is the plaintext, $k$ is the key, and $c$ is the ciphertext. In words: scramble once with the key, scramble again with the same key, and you're back where you started. XOR-ing the same value twice cancels out, so locking and unlocking are literally the same operation.

If the key is truly random, as long as the message, and never reused, this scheme (the one-time pad) is provably unbreakable — every possible plaintext looks equally plausible given the ciphertext. It is also useless in practice. If you can safely deliver a 1 GB key to send a 1 GB file, you could have safely delivered the file.

So in practice we use a function that stretches a short key (128 or 256 bits) into a stream that looks random. That's a block cipher, of which AES is the standard example: think of it as an enormous substitution table over 128-bit chunks, selected by the key, designed so that without the key the output is indistinguishable from noise.

Every extra key bit doubles the brute-force cost

An attacker who doesn't have the key has one last resort: try every key. With an $n$-bit key that's $2^n$ candidates — and this is where exponential growth does the heavy lifting.

As the figure shows, nudging $n$ upward changes the order of magnitude of the work. If an attacker's hardware gets 1,000× faster, adding ten bits to the key puts you back ahead. The defender's cost grows by addition; the attacker's grows by multiplication. That asymmetry is the foundation of the whole field. For the notation itself, see Complexity From Scratch.

2. The key distribution problem — sharing a key with a stranger

Symmetric encryption is fast and strong, but it carries a fatal precondition: sender and receiver must already share the same key.

Your browser and a shopping site you've never visited share nothing in advance. Send the key in the clear and any eavesdropper can decrypt too. Encrypt the key before sending it, and you need a key for that — around and around. This is the key distribution problem, and until the mid-1970s it was treated as a hard limit on what cryptography could do.

Diffie and Hellman broke that wall in 1976 with "New Directions in Cryptography." Their claim was counterintuitive: two parties can agree on a shared secret over a channel that is being fully monitored.

Here's how. Everyone knows a public number $g$ and a large prime $p$. Alice picks a private number $a$ and sends $g^a \bmod p$. Bob picks $b$ and sends $g^b \bmod p$. Now both can compute

$$(g^b)^a \equiv (g^a)^b \equiv g^{ab} \pmod{p}$$

where $\bmod p$ means "the remainder after dividing by $p$." Both sides arrive at the same value $g^{ab} \bmod p$, yet all that crossed the wire was $g^a$ and $g^b$. To recover $a$ from those, an eavesdropper would have to answer "what power of $g$ gives this number?" — the discrete logarithm problem, which we don't know how to solve at scale. That unsolvability is the security.

3. Public-key cryptography — why factoring, of all things?

Diffie–Hellman is a procedure for agreeing on a key. Public-key encryption goes one step further and splits the locking key from the unlocking key. Picture scattering open padlocks all over town: anyone can snap one shut, but only you hold the key that opens them.

To build that out of numbers, you need an operation that is cheap in one direction and hopeless in reverse. Factoring fits:

• Multiply two primes together: instant, even at hundreds of digits.
• Recover those two primes from the product: as far as anyone knows, the effort explodes with the number of digits.

RSA, devised in 1977, is built on exactly that asymmetry. Pick primes $p$ and $q$, set $n = pq$, take $\phi(n) = (p-1)(q-1)$, choose an $e$ coprime to it, and find $d$ with $ed \equiv 1 \pmod{\phi(n)}$. You publish $(n, e)$ and keep $d$ secret.

Read it as: raise the message to the power $e$ and take the remainder mod $n$ to encrypt; raise that to the power $d$ and take the remainder to get the message back. $d$ was chosen precisely so the two exponentiations cancel. And to find $d$ you need $\phi(n)$, and to find $\phi(n)$ you need to factor $n$. The strength of the key is bolted directly to the difficulty of factoring.

Now the honest part. Nobody has proven that factoring is hard. We're relying on the empirical fact that decades of worldwide effort haven't produced a fast method. Meanwhile the records keep falling: a 768-bit modulus was factored in 2009, an 829-bit one in 2020. That's why recommended key lengths keep rising, and why RSA keys in current use are 2048 bits or more.

Newer designs mostly use elliptic-curve cryptography (ECC) instead, because it reaches the same strength with far shorter keys — a 256-bit curve key is considered comparable to a 3072-bit RSA key. The underlying hard problem changes to discrete logarithms, but the shape of the argument is identical.

Both are also orders of magnitude slower than symmetric ciphers, since both grind through exponentiation of huge numbers. That's why real HTTPS traffic is hybrid: public-key cryptography to agree on a symmetric key, then the symmetric cipher for the actual payload. Public keys are the expensive tool you use for one brief moment at the start.

4. Hash functions — the point is that you can't go back

The third tool has a different purpose entirely. A hash function crushes input of any length into a fixed-size value (say 256 bits). Crushing destroys information, so there is no way back. That's the specification, not a defect.

A cryptographic hash is expected to have three properties:

• Preimage resistance: you can't recover input from a hash value.
• Second-preimage resistance: given one input, you can't construct a different input with the same hash.
• Collision resistance: you can't find any pair of inputs sharing a hash value.

The third is the weakest link, and it's worth internalizing why. By the same reasoning as the birthday paradox, collisions in an $n$-bit hash turn up after roughly $2^{n/2}$ attempts. A 256-bit hash gives you 128 bits of collision resistance, not 256.

Don't confuse this with the hash you use in a hash table. That one is tuned to be fast and spread evenly; it makes no promise of standing up to an adversary who is choosing inputs on purpose. Reading this alongside Hashing and Nearest-Neighbor Search makes the difference in design goals concrete.

5. Signatures — public-key cryptography run backwards

Encryption gives you "only you can read this." A signature gives you the mirror image: "anyone can verify that you wrote this." You just flip which key does which job.

• Encryption: lock with the public key → unlock with the private key.
• Signature: produce with the private key → verify with the public key.

Only the holder of the private key can produce the value, and everyone holding the public key can confirm it came from that key. Textbook RSA signing operates not on the message but on its hash.

$$s = H(m)^d \bmod n \qquad \text{verify}: \; s^e \bmod n \overset{?}{=} H(m)$$

$H(m)$ is the message hash and $s$ is the signature. Read it as: take the value built with the secret exponent $d$, undo it with the public exponent $e$, and check that it matches the hash. Signing the hash keeps signatures a fixed size no matter how long the message is — and it also means that when the hash breaks, the signature breaks. If two documents with different contents can share a hash value, a signature on one is a valid signature on the other.

It's equally important to know what a signature does not promise. It says only "the holder of this public key produced this." It says nothing about whose key that is. Filling that last gap is the job of certificates and certificate authorities (PKI): a trusted third party signs the claim "this public key really does belong to example.com." The padlock in your browser is the result of verifying that chain.

Code you can touch (educational — never ship this)

Here's a full RSA round trip on tiny numbers.

p, q = 61, 53                      # real keys use primes of hundreds of bits
n = p * q                          # 3233
phi = (p - 1) * (q - 1)            # 3120
e = 17                             # coprime to phi
d = pow(e, -1, phi)                # 2753 = inverse of e mod phi

m = 65
c = pow(m, e, n)                   # 2790  encrypt
print(pow(c, d, n))                # 65    decrypt

s = pow(m, d, n)                   # sign (properly: sign the hash)
print(pow(s, e, n) == m)           # True  verify

pow(x, y, n) is the built-in that computes $x^y \bmod n$ efficiently. Ten lines for a full round trip — and shipping this would get you broken every time. Real RSA layers on padding (OAEP for encryption, PSS for signatures) that mixes in randomness so the same plaintext produces a different ciphertext each time. The code above is deterministic, so an observer can tell when you send the same message twice just by comparing ciphertexts. In cryptography, the distance between "the math checks out" and "this is secure" is enormous.

A history of breakage — every cipher ages out

The most common misconception in practice is that picking a strong algorithm ends the job. In reality, every widely deployed cipher has eventually reached the end of its life.

• DES (a US standard from 1977): its key was only 56 bits, and in 1998 the EFF built dedicated hardware that exhaustively searched the keyspace in under three days. The design wasn't bad — the key length was simply overtaken by hardware.
• MD5: a method for producing collisions was published in 2004, and by 2008 it had been used to demonstrate a forged certificate authority certificate. The Flame malware of 2012 exploited an MD5 collision to forge a software signature.
• SHA-1: theoretical weaknesses appeared in 2005, and in 2017 two PDFs with different contents but the same SHA-1 value were published (SHAttered). A stronger form of collision followed in 2020.
• RSA key lengths: each new factoring record has pushed the recommended size upward.

The pattern is always the same: a theoretical weakness is announced, falling compute costs turn it into a practical attack, and the algorithm is finally removed from the standards. Because that migration takes years, the correct posture is to start moving when the weakness is announced, not when the break lands. Reacting after the fact is already too late.

The migration currently underway is preparation for quantum computers. Shor's algorithm, published in 1994, showed that a sufficiently large quantum computer solves factoring and discrete logarithms efficiently — which puts RSA and elliptic-curve cryptography squarely in the breakable column. The effect on symmetric ciphers and hashes is much milder: in theory the effective strength halves ($2^n$ becomes $2^{n/2}$), which is a large part of why AES-256 is recommended.

Replacements are already standardized: in 2024, NIST published lattice-based key agreement and signature schemes as federal standards (ML-KEM, ML-DSA, SLH-DSA). The attack to worry about operationally is "harvest now, decrypt later" — store the ciphertext today, decrypt it once the hardware exists. The longer your data must stay secret, the more urgent the migration.

One useful contrast: error correction and cryptography both start from "assume it breaks," but they assume different opponents. Error correction faces probabilistic noise; cryptography faces an intelligence that has read your design and will choose the worst possible input. Something that works on average is not good enough.

How this shows up on the job

Who touches it, and when. Backend web developers hit it in password storage, sessions, and token verification. SRE and infrastructure engineers hit it in certificate renewal, key-management permissions, and TLS configuration. Embedded and IoT developers hit it in firmware signing and in generating keys on devices with weak sources of randomness. Anyone working on payments or healthcare systems meets it in at-rest encryption and key-rotation audits.

The names you'll actually type. For symmetric encryption, AES-256-GCM or ChaCha20-Poly1305 — AEAD modes that encrypt and detect tampering in one step. Use libsodium or your language's standard crypto library, never a hand-rolled implementation. For passwords, argon2id or bcrypt, with the cost parameters (memory, iterations) tuned to your hardware. To inspect TLS and certificates: openssl s_client -connect host:443 and openssl x509 -text. Keep keys in a key-management service — AWS KMS, Google Cloud KMS, an HSM — not in environment variables. For message authentication, use HMAC-SHA256 rather than inventing something.

Pitfalls that turn into incidents.

• Rolling your own crypto: designing or implementing an algorithm yourself is a near-certain loss. "It works" and "it's secure" are unrelated claims.
• ECB mode: encrypting each block independently maps identical plaintext blocks to identical ciphertext blocks, so patterns show straight through. If it's the library default, be suspicious.
• Nonce (IV) reuse: with AES-GCM in particular, reusing a key/nonce pair doesn't just leak plaintext — it lets an attacker recover the authentication key and forge messages. Guarantee uniqueness with a counter or a long random value.
• Sources of randomness: never generate keys with a general-purpose RNG like Python's random. Use the crypto APIs — secrets in Python, crypto.randomBytes in Node.js. History includes both keys guessed from a degraded random source and private keys fully recovered because a signature nonce was reused.
• Timing in string comparison: comparing tokens or MACs with == makes the runtime depend on how many leading characters matched, letting an attacker recover the value one character at a time. Use a constant-time comparison such as hmac.compare_digest.
• Hand-rolling a MAC as hash(key + message): hashes through SHA-2 are vulnerable to length-extension attacks, which break this construction outright. HMAC exists specifically to prevent it.
• Hardcoded keys and no rotation: a key committed to a repository lives in the history forever. Design so keys can be replaced.

Questions you'll get in interviews and design reviews. "Why shouldn't passwords be stored with SHA-256?" — because it's too fast; a GPU tries enormous numbers of candidates per second, so you want something deliberately slow and memory-hungry like Argon2 or bcrypt, with a distinct salt per user. "Why does HTTPS use both public-key and symmetric crypto?" — public keys are slow, so they're spent only on agreeing a key, and the payload rides on the fast symmetric cipher. "What actually happens when a certificate expires?" — the signature is still mathematically valid, but verifiers refuse to extend trust to it. Most cryptographic failures are failures of operations, not of mathematics.

Summary

• Cryptography doesn't produce "unbreakable." It produces an exponential gap in effort between those who hold the key and those who don't.
• Symmetric is fast but requires a pre-shared key; public-key needs no pre-sharing but is slow. Real systems combine both.
• Public-key security rests on unproven assumptions — that factoring and discrete logarithms are hard.
• A hash's value is that it can't be reversed; a signature proves only which key produced something. Proving whose key it is belongs to certificates.
• Every cipher in use will eventually break. Designing so you can migrate matters as much as picking a strong algorithm today.

Next we'll follow how these three tools actually fit together, walking the HTTPS handshake one round trip at a time.