1. Classical Cryptography

Caesar cipher

Shift each letter 3 forward (wrapping X→A, Y→B, Z→C):

Example: MEET YOU IN THE PARK
→ 12 4 4 19 · 24 14 20 · 8 13 · 19 7 4 · 15 0 17 10
→ 15 7 7 22 · 1 17 23 · 11 16 · 22 10 7 · 18 3 20 13
→ PHHW BRX LQ WKH SDUN

(Also: START THE ATTACK → VWDUW WKH DWWDFN.)

Decryption = recovering the original message, using .

Shift cipher (key )

Affine cipher

Encrypt example: ; K = 10 → = V.

Decrypt: from :

where is the inverse of mod 26 (exists because ).


2. Cryptanalysis (breaking codes)

Cryptanalysis = recovering plaintext from ciphertext without knowing the method and key.

Brute force for shift ciphers: try all 26 shifts.

Frequency analysis (smarter): most common English letters

ETAOINSHR
13%9%8%8%7%7%7%6%6%

Procedure: assume the most frequent ciphertext letter is E, compute shift , shift back by . If it’s not readable, try T, then A, …

Example: ZNK KGXRE HOXJ MKZY ZNK CUXS
Most common letter = K (10). Assume E (4) → K: ⇒ .
Shift by : THE EARLY BIRD GETS THE WORM ✓


3. Block Ciphers

Shift and affine ciphers are character (monoalphabetic) ciphers — one letter → one letter, so frequency analysis breaks them. Block ciphers replace blocks of letters with blocks, which is harder to attack.

Transposition cipher

  • Key: a permutation of .
  • Split the message into blocks of size (pad the last block with random letters).
  • Encrypt .
  • Decrypt with .

Example: .

  • Encrypt PIRATE ATTACK → blocks PIRA TEAT TACK → IAPR ETTA AKTC
  • Decrypt SWUE TRAE OEHS using → USEW ATER HOSE = USE WATER HOSE

4. Cryptosystems

Definition 1

A cryptosystem is a 5-tuple :

  • = plaintext strings, = ciphertext strings, = keyspace,
  • = encryption functions , = decryption functions ,
  • with for all .

Shift cipher as a cryptosystem: = strings over , , , .

Private-key cryptosystems

  • Knowing the encryption key ⇒ you can quickly get the decryption key.
  • Both parties must share a secret key (and exchange it securely).
  • Examples: shift, affine (weak); AES (current US standard, highly resistant to cryptanalysis — but still needs shared keys, often a new key per session).

Public-key cryptosystems (1970s)

  • Everyone publishes an encryption key; only the decryption key is secret.
  • Knowing how to encrypt does not let you decrypt without an infeasible amount of work.

5. The RSA Cryptosystem

Rivest, Shamir, Adleman (MIT, 1976). Discovered earlier in secret by Clifford Cocks at GCHQ (1973), revealed in the late 1990s.

Key setup

  • Choose two large primes (~200 digits each), found quickly with probabilistic primality tests.
  • Public key: with and .
  • Private key: = inverse of modulo .
  • Security rests on the fact that (~400 digits) can’t be factored in reasonable time, as far as is currently known.

Encryption

  1. Letters → two-digit numbers (A = 00, …, J = 09, …, Z = 25), concatenated.
  2. Split into blocks of digits, where is the largest even number such that ( digits) . Pad with X if needed.
  3. Encrypt each block: (use fast modular exponentiation, §4.2 Alg. 5).

RSA is a block cipher.

Example: encrypt STOP with , , .

  • STOP → 18191415; block size 4 (since ) → 1819 1415
  • ,
  • Ciphertext: 2081 2182

Decryption

Why it works: , so .
By Fermat (assuming ): and , so
and . By the CRT (since ): .

Example: decrypt 0981 0461 (same key).

  • is the inverse of 13 mod .
  • ,
  • 0704 1115 → 07 04 11 15 → HELP

RSA ties the whole chapter together: modular exponentiation (4.2), gcd & inverses (4.3/4.4), Fermat + CRT (4.4).