Course content of CS3314 Cryptography
Lecture 2: Fundamentals of Classical Cryptography (Basics of Cryptography)
1. The Overall Framework of Cryptography
The components of cryptology
- Cryptography: the techniques for designing encryption and protecting information
- Cryptanalysis: the techniques for breaking ciphers
- Cryptology = Cryptography + Cryptanalysis
The five-tuple of a cryptosystem
A cryptosystem consists of five sets
(P, C, K, E, D)
- P: plaintext space (Plaintext)
- C: ciphertext space (Ciphertext)
- K: key space (Key)
- E: encryption algorithm (Encryption)
- D: decryption algorithm (Decryption)
Satisfying:
D(E(M, K₁), K₂) = M
2. The Two Major Cryptosystems
| System | Key relationship | Characteristics | Examples |
|---|---|---|---|
| Single-key (symmetric) cryptography | K₁ = K₂ | Same key for encryption and decryption; fast; key distribution is difficult | AES, DES |
| Two-key (asymmetric) cryptography | K₁ ≠ K₂ | Different keys for encryption and decryption; the public key can be published | RSA, ECC |
⚠️ Kerckhoffs’s principle:
The security of a cryptosystem should depend only on the secrecy of the key, not on the secrecy of the algorithm.
3. Cryptanalysis and Attack Models
| Attack type | What the attacker knows | Characteristics |
|---|---|---|
| Ciphertext-only | Only ciphertext | The hardest |
| Known-plaintext | Some plaintext-ciphertext pairs | Common against symmetric ciphers |
| Chosen-plaintext | Can choose inputs to be encrypted | Typical attack on RSA and the like |
| Chosen-ciphertext | Can choose ciphertexts to be decrypted | Targets public-key systems |
Attacker capability ranking: ciphertext-only < known-plaintext < chosen-plaintext < chosen-ciphertext
4. Information Theory and the Foundations of Security
Shannon’s contributions
- Proposed the principles of diffusion and confusion
- Established the mathematical foundations of cryptography
- Proved that the One-Time Pad provides perfect secrecy
Classes of security
| Type | Definition | Characteristics |
|---|---|---|
| Unconditional security / perfect secrecy (Unconditional Security) | Cannot be broken no matter how much computing power is available | e.g. the one-time pad (OTP) |
| Computational security (Computational Security) | Breaking it costs too much or takes too long | e.g. AES, RSA |
Condition: if I(M; C) = 0 → perfect secrecy
Necessary condition: H(K) ≥ H(M) → the entropy of the key is at least the entropy of the message (equivalently, key space ≥ plaintext space)
5. Classical Cipher Techniques
1️⃣ Substitution Cipher
Replace plaintext characters with other symbols
| Type | Encryption rule | Characteristics / weaknesses |
|---|---|---|
| Caesar shift cipher | c = (p + k) mod 26 | Key space of 25; easily brute-forced |
| Monoalphabetic substitution | Arbitrary permutation table | Breakable by frequency analysis |
| Affine cipher | E(x)=ax+b (mod 26), requires gcd(a,26)=1 | Easily broken by statistical attacks |
| Playfair cipher | Encrypts pairs of letters (digraphs) | Frequency patterns are weakened but it can still be broken |
| Hill cipher | Linear substitution on vectors, Kp=C | Resists ciphertext-only attacks, but not known-plaintext-pair attacks |
| Vigenère cipher | Polyalphabetic substitution with period r | Breakable with the Kasiski method |
| One-time pad (OTP) | cᵢ = mᵢ ⊕ kᵢ | The only unconditionally secure system, but key management is difficult |
2️⃣ Transposition Cipher
The characters are unchanged; only their order changes.
| Type | Method | Characteristics |
|---|---|---|
| Rail Fence | Write diagonally, read row by row | Simple, easily broken |
| Columnar Transposition | Write into a matrix, then read the columns in key order | Letter frequencies are unchanged |
| Product Cipher | Combination of substitution + transposition | The bridge from classical to modern |
6. Mechanical Ciphers and the Evolution to Modern Cryptography
Rotor Machine
- Based on polyalphabetic substitution; physical rotors produce different mappings.
- Representatives: the German Enigma and the Japanese Purple.
- Lesson: multiple layers of substitution + dynamic permutation → the precursor of the Feistel structure / DES.
7. Steganography
- Hides the existence of the message; it is not encryption.
- Examples: invisible ink, image LSB, IoT SmartConfig.
- Drawbacks: low capacity, easy to detect.
8. Key Takeaways
- Security depends on the key, not on the algorithm.
- Substitution or transposition alone is not secure; they must be combined.
- The key space must be large enough to defend against brute-force attacks.
- The OTP is the only unconditionally secure system.
- The prototypes of modern cipher algorithms: product ciphers and rotor machines.
Translated from the Chinese original.
