Distinction between Substitution and Transposition Cipher, DES Sub-Key Generation, and Finite Fields

Part A: Substitution vs Transposition Cipher

Substitution Cipher replaces each plaintext character with a different character, while Transposition Cipher rearranges the positions of plaintext characters without changing them.

Feature	Substitution Cipher	Transposition Cipher
Basic Operation	Replaces characters with other characters	Rearranges the order of characters
Identity of characters	Characters change their identity	Characters retain identity but change position
Technique	Mapping of plaintext to ciphertext symbols	Permutation of plaintext characters
Example	Caesar Cipher, Vigenère Cipher	Rail Fence, Columnar Transposition
Key concept	Confusion (obscures relationship)	Diffusion (spreads plaintext over ciphertext)
Vulnerability	Frequency analysis can break it	Pattern analysis of positions can break it

---

Part B: Generation of 16 Sub-Keys in DES

In DES (Data Encryption Standard), 16 round sub-keys of 48 bits each are generated from the original 64-bit key using a key schedule algorithm.

Steps for Sub-Key Generation:

• Step a — Initial Key: Start with a 64-bit key (8 bits are parity bits, so effective key = 56 bits)

• Step b — PC-1 (Permuted Choice 1): The 64-bit key is passed through PC-1 permutation table, which discards the 8 parity bits and permutes the remaining 56 bits

• Step c — Split into halves: The 56-bit key is divided into two halves:

  • C₀ = Left 28 bits
  • D₀ = Right 28 bits

• Step d — Left Circular Shift: For each round $i$ (1 to 16), both $C_{i-1}$ and $D_{i-1}$ are left circular shifted by 1 or 2 positions:

  • 1-bit shift for rounds: 1, 2, 9, 16
  • 2-bit shift for all other rounds

• Step e — PC-2 (Permuted Choice 2): After shifting, $C_i$ and $D_i$ are combined (56 bits) and passed through PC-2 permutation table, which selects and permutes 48 bits out of 56 to produce the sub-key $K_i$

• Step f — Repeat: Steps d and e are repeated 16 times to generate $K_1, K_2, K_3, \ldots, K_{16}$

---

Part C: Finite Field and Its Implications

A Finite Field (also called Galois Field, denoted $GF(p^n)$) is a field that contains a finite number of elements where all arithmetic operations (addition, subtraction, multiplication, division) are defined and closed.

Properties of a Finite Field:

• It must satisfy all field axioms: closure, associativity, commutativity, distributivity, identity elements, and inverse elements
• The number of elements in a finite field is always $p^n$, where $p$ is a prime and $n$ is a positive integer
• The most common finite fields in cryptography are $GF(2^n)$

Implications in Cryptography:

• AES operates over the finite field $GF(2^8)$, where each byte is treated as a polynomial
• Arithmetic in finite fields ensures results always stay within a fixed range (no overflow)
• Modular arithmetic in $GF(p)$ is the foundation of RSA and Diffie-Hellman algorithms
• Provides mathematical structure that guarantees invertibility — essential for decryption
• Enables efficient hardware and software implementation of encryption algorithms

---

Conclusion: Substitution and transposition are fundamental classical cipher techniques that form the basis of modern ciphers. DES uses a systematic key schedule to derive 16 sub-keys for its Feistel rounds. Finite fields provide the algebraic framework that ensures correctness and security in modern encryption algorithms like AES and RSA.