Symmetric and Asymmetric

A cipher turns a readable message (the plaintext) into scrambled ciphertext, using a key. Ciphers come in two families:

• Symmetric: the same key locks and unlocks. If you can encrypt, you can decrypt. Every classical cipher, and most of the encryption running the internet today, works this way.
• Asymmetric (public-key): the key that locks is different from the key that unlocks. The locking key can be published for anyone to use; the unlocking key stays private.

The usual picture for asymmetric encryption is a public mailbox. Anyone can drop a letter through the slot (the public key), but only the person with the key to the box (the private key) can take letters out.

Classical ciphers are modular arithmetic on a 26-letter clock: number the letters A = 0 to Z = 25, shift, and wrap round at the end.

Caesar

Shift every letter by the same amount. With a shift of 3, H (7) becomes K (10), and Y (24) becomes B, because 24 + 3 = 27 and 27 mod 26 = 1. The key is the shift.

Vigenère

Use a keyword instead of one shift. Each letter of the message is shifted by the next letter of the key (A = 0, B = 1, …), and the keyword repeats.

Gronsfeld

Vigenère with a key made of digits, so each shift is 0 to 9. A long number makes a natural Gronsfeld key.

To decrypt either one, shift each letter back by the matching key letter or digit. Because the same key works both ways, both are symmetric. Modern symmetric ciphers such as AES are vastly stronger, but the idea is the same: one shared secret key.

A symmetric cipher is only as safe as its key, and both people need the same one. So how do they agree on it, if anyone might be listening? For most of history the answer was to meet in person, or to trust a courier carrying a codebook.

In 1976 Whitfield Diffie and Martin Hellman published a way for two people to agree on a secret number in full view of an eavesdropper. RSA, the first practical public-key encryption, followed in 1977. Both rest on the same new ingredient: a calculation that is easy one way and very hard to undo.

A one-way function is quick to compute and very slow to reverse. Three show up throughout the worksheets:

A trapdoor is a secret that makes the hard direction easy. Knowing the two primes lets you take square roots and undo RSA's powers; knowing the secret exponent lets you finish a key exchange. The private key is the trapdoor.

At real-world sizes the hard direction would take longer than the age of the universe. Puzzle-sized numbers are chosen so a computer can do it in seconds, which is exactly the part the worksheets do for you.

Related problems, and how safe they are

Factoring and the discrete logarithm are different problems, but close relatives: both ask you to undo a calculation in a group of remainders, and in 1994 Peter Shor found a single algorithm for a quantum computer that solves both quickly. So in that sense they share the same weakness.

Nobody has proved that either is truly hard for ordinary computers. If P = NP, the most famous open question in computer science, both would be easy; but even a proof that P ≠ NP wouldn't settle it, because neither is known to be among the hardest problems in NP. (The Riemann hypothesis, about how primes are spread out, comes up in proofs about testing whether a number is prime, but isn't known to make factoring easier or harder.) Their security rests on decades of failed attempts to break them, not on a proof.

That's why cryptographers keep replacements ready. If large quantum computers arrive, or someone finds a faster method (with or without help from AI), these systems would fall. In 2024 the U.S. standards agency NIST published “post-quantum” systems built on different problems, mostly about lattices, for exactly that reason.

Public-key ideas do a few different jobs, and a puzzle may use one or chain several together:

• Public-key encryption. Anyone locks a message with the public key, and only the private key unlocks it. What you see: a public key and a ciphertext.
• Key exchange. Two people end up sharing a secret number, or pass a message back and forth, without ever sending a key. What you see: a conversation, with numbers going both ways. The result is usually not the message itself; it's a key.
• Hybrid systems. Key exchange first, then a fast symmetric cipher using the agreed number as its key. That's how secure websites work today. In a puzzle, the second stage may be a classical cipher such as Vigenère or Gronsfeld, and the puzzle should say which.

So when a decryption gives you a number that doesn't read as anything, ask whether it's the message or a key for the next stage.

Cryptographers tell their stories with the same cast: Alice and Bob want to talk privately, and Eve the eavesdropper sees everything they send. In these puzzles you're Eve.

The steps are much the same whatever the system:

1. Identify the system from how the puzzle describes it. What's public, what's sent, and how is the message said to be locked?
2. Label every number: which is the modulus, which is the public key, which is the ciphertext.
3. Break the hard problem: factor, or take a discrete log. The worksheets do this part.
4. Finish as the owner would, using the private key you've recovered.
5. Turn the number back into text. See From Letters to Numbers.
6. If it's a key, not a message, decrypt the next stage with it.