Unit 4: Cryptography

I. Introduction and Overview

Cryptography is the study of mathematical techniques for securing communication in the presence of adversaries; it converts intelligible plaintext into unintelligible ciphertext and back again under the control of a key. Number theory supplies its engine: modular arithmetic, greatest common divisors, and modular inverses over ℤ₂₆ (the 26 letters A=0 … Z=25).

• Core goals: confidentiality (hiding content), integrity (detecting tampering), authentication (verifying origin), non-repudiation (preventing denial).
• Key participants: Alice (sender), Bob (receiver), Oscar/Eve (adversary intercepting the channel).
• Kerckhoffs' principle: security must rest on secrecy of the key alone, never on secrecy of the algorithm.
• Convention used throughout: letters map to residues mod 26; encryption and decryption are inverse functions parameterised by the key.

A. History and Overview of Cryptography

Cryptography evolved from hand ciphers to mathematical systems.

• Ancient era: the Spartan scytale (c. 5th century BCE) wrapped a strip round a rod — an early transposition device; the Caesar cipher (1st century BCE) shifted letters by 3.
• Medieval/Renaissance: Al-Kindi (9th century) described frequency analysis, breaking monoalphabetic ciphers; the Vigenère cipher (16th century) introduced polyalphabetic substitution, long called le chiffre indéchiffrable.
• Mechanical era: the German Enigma machine (WWII) automated rotor-based polyalphabetic substitution and was broken at Bletchley Park.
• Modern era: Shannon's 1949 Communication Theory of Secrecy Systems founded the mathematical theory; DES (1977) and RSA (1978) began the public-key age.

II. Cryptosystems

A cryptosystem is the formal abstraction underlying every cipher below.

A. Formal Definition

A cryptosystem is a five-tuple (P, C, K, E, D).

P  = set of possible plaintexts
C  = set of possible ciphertexts
K  = keyspace (set of possible keys)
E  = { e_k : k ∈ K },  each e_k : P → C   (encryption rules)
D  = { d_k : k ∈ K },  each d_k : C → P   (decryption rules)
Requirement: for every k ∈ K there exists k' with  d_{k'}(e_k(x)) = x  for all x ∈ P

• Symbols: x is a plaintext element, e_k the encryption function under key k, d_{k'} its matching decryption function.
• Correctness condition: decryption must invert encryption, so no information is lost.
• Symmetric key: all classical systems here use k' = k or a trivially derived key; sender and receiver share one secret.

B. Security Notions and Attack Models

Systems are judged by what an adversary can do.

• Ciphertext-only attack: Oscar sees only ciphertext (weakest attacker).
• Known-plaintext attack: Oscar has some plaintext–ciphertext pairs — this breaks the Hill cipher easily.
• Chosen-plaintext attack: Oscar can encrypt texts of his choosing.
• Keyspace size: a necessary (not sufficient) condition; a small |K| permits brute force. The shift cipher's |K| = 26 is trivially exhaustible.

III. Classical Cryptography

Classical cryptography covers pre-computer, character-based systems built on substitution (replacing symbols) or transposition (rearranging them), all defined over ℤ₂₆.

• Substitution ciphers: shift, affine, substitution, Vigenère, Hill — replace letters by other letters.
• Transposition ciphers: permutation cipher — reorder existing letters.
• Shared weakness: they preserve statistical structure of the language and yield to frequency analysis or algebraic attacks.

A. Shift Cipher

The shift cipher encrypts by adding a constant offset to every letter modulo 26.

Key: k ∈ {0,1,…,25}
Encryption:  e_k(x) = (x + k) mod 26
Decryption:  d_k(y) = (y − k) mod 26

• Symbols: x plaintext residue, y ciphertext residue, k the fixed shift.
• Caesar cipher: the special case k = 3.
• Worked example: plaintext H (7), k = 3 → (7+3) mod 26 = 10 = K.
• Limitation: only 26 keys; brute-force decryption of all shifts breaks it instantly.

B. Affine Cipher

The affine cipher generalises the shift by scaling and shifting each letter.

Key: (a, b) with gcd(a,26)=1
Encryption:  e_k(x) = (a·x + b) mod 26
Decryption:  d_k(y) = a⁻¹·(y − b) mod 26

• Symbols: a multiplier, b additive shift, a⁻¹ the modular inverse of a mod 26.
• Constraint on a: gcd(a,26)=1 guarantees a is invertible so decryption is unique; the valid values are {1,3,5,7,9,11,15,17,19,21,23,25}.
• Keyspace: 12 × 26 = 312 keys (minus the trivial identity).
• Worked example: a=5, b=8, plaintext E (4) → (5·4+8) mod 26 = 28 mod 26 = 2 = C.
• Limitation: still monoalphabetic; each plaintext letter always maps to the same ciphertext letter, so frequency analysis works.

C. Substitution Cipher

The substitution cipher replaces each letter by an arbitrary but fixed letter defined by a permutation of the alphabet.

• Key: a bijection π : ℤ₂₆ → ℤ₂₆; encryption e_π(x) = π(x), decryption d_π(y) = π⁻¹(y).
• Keyspace: 26! ≈ 4 × 10²⁶ — far too large for brute force.
• General case: shift and affine ciphers are special, structured subsets of the full substitution cipher.
• Limitation: despite the huge keyspace it is broken by frequency analysis — English letter frequencies (E ≈ 12.7%, T, A, …) and digram/trigram patterns (TH, THE) survive substitution.

D. Vigenère Cipher

The Vigenère cipher is polyalphabetic: it applies several shift ciphers in rotation using a keyword, so one plaintext letter can encrypt to different ciphertext letters.

Key: keyword k = (k₁, k₂, …, k_m)
Encryption:  y_i = (x_i + k_{(i mod m)}) mod 26
Decryption:  x_i = (y_i − k_{(i mod m)}) mod 26

• Symbols: m = keyword length (period), k_j the shift applied at position j.
• Effect: flattens the frequency distribution because position i is shifted by a repeating pattern.
• Worked example: plaintext HELLO, key KEY → shifts 10,4,24,10,4 → RIJVS.
• Limitation: the Kasiski test and index of coincidence recover the period m; once m is known, the ciphertext splits into m monoalphabetic shift ciphers, each solvable.

E. Hill Cipher

The Hill cipher encrypts blocks of letters using linear algebra over ℤ₂₆, spreading each plaintext letter across a whole block.

Key: invertible m×m matrix K over ℤ₂₆
Encryption:  C = K · P   (mod 26)
Decryption:  P = K⁻¹ · C  (mod 26)
Invertibility: gcd(det K, 26) = 1

• Symbols: P a column vector of m plaintext residues, C the ciphertext vector, K⁻¹ the matrix inverse mod 26 (found via adjugate ÷ determinant).
• Diffusion: changing one plaintext letter changes the whole ciphertext block, defeating single-letter frequency analysis.
• Worked example (m=2): K = [[3,3],[2,5]], plaintext HI = (7,8) → C = ((3·7+3·8), (2·7+5·8)) mod 26 = (45,54) mod 26 = (19,2) = TC.
• Limitation: purely linear, so a known-plaintext attack with m independent plaintext–ciphertext block pairs solves for K directly.

F. Permutation Cipher

The permutation (transposition) cipher hides a message by rearranging the positions of letters within fixed-length blocks, without changing the letters themselves.

Key: a permutation π of {1,2,…,m}
Encryption:  block (x₁,…,x_m) → (x_{π(1)},…,x_{π(m)})
Decryption:  apply the inverse permutation π⁻¹

• Symbols: m block size, π the reordering rule; it is the special case of a Hill cipher whose key is a permutation matrix.
• Distinguishing feature: it is a transposition cipher — letter frequencies are unchanged, but digram/positional structure is destroyed.
• Worked example: m=4, π = (2,4,1,3), block WXYZ → X Z W Y.
• Limitation: letter-frequency counts betray it as transposition; keyspace is only m!, and anagramming plus digram statistics reconstruct π.

G. Comparative Perspective on Classical Systems

The classical ciphers trade off keyspace, structure, and resistance to analysis.

1. Monoalphabetic (shift, affine, substitution): one fixed mapping; vulnerable to frequency analysis regardless of keyspace size.
2. Polyalphabetic and block (Vigenère, Hill, permutation): vary the mapping by position or mix letters together, resisting single-letter frequency counts but falling to period analysis (Vigenère), linear algebra (Hill), or anagramming (permutation).

• Common downfall: every system is broken by exploiting residual language structure, motivating Shannon's later demand for confusion and diffusion in modern cryptosystems.