Week 2 Lecture 1 Notes

Product Ciphers

• Introduction to Product Ciphers

  • Concept developed by Claude Shannon.
  • Crypto systems defined by:
    • P: Set of plaintext
    • C: Set of ciphertext
    • K: Set of keys
    • E: Set of encryption functions
    • D: Set of decryption functions

• Considerations

  • For simplicity, assume P = C.
  • Define two crypto systems:
    • S1: (P, P, K1, E1, D1)
    • S2: (P, P, K2, E2, D2)
  • Product of these systems written as S1 x S2:
    • Key Set: K1 x K2 (Cartesian product of key sets)
    • Encryption (E) and Decryption (D) to be defined.

Defining E and D for Product Ciphers

• Encryption:

  • Use ordered pair of keys, k = (k1, k2).
  • Combined encryption function:
    • E(k1, k2)(x) = E2(E1(x))

• Decryption:

  • Corresponding decryption function:
    • D(k1, k2)(y) = D1(D2(y))
  • Property check:
    • D(k1, k2)(E(k1, k2)(x)) = x (for all x) confirms valid crypto system.

Example: Multiplicative Cipher and Shift Cipher

• Multiplicative Cipher:

  • P, C = Z_26
  • Keys: Numbers co-prime to 26.
  • Encryption: Multiplication modulo 26.
  • Decryption: Multiply ciphertext by the multiplicative inverse mod 26.

• Shift Cipher:

  • P, C = Z_26
  • Keys: Any element of Z_26.
  • Encryption: Add key modulo 26 to plaintext.

• Product of Ciphers:

  • Combining multiplicative and shift ciphers results in an Affine Cipher.
  • Prove equivalence of S x M and M x S as exercise.

Block Ciphers

• Definition:

  • Based on product ciphers, applying a cipher iteratively.
  • Operates on fixed-size blocks (e.g., 64-bit).

• Terms:

  • Each iteration called a round.
  • Each round has a round key derived from a key schedule.
  • Round function g combines input and key.

• Process:

  • For rth round:
    • Input: W(r-1)
    • Key: K_r
    • Output: W_r = g(W(r-1), K_r)

• Decryption:

  • Round function must allow recovery of original input:
    • g^{-1}(g(W, key)) = W

Modes of Operation for Block Ciphers

1. Electronic Code Book (ECB) Mode:
   • Fixed key, encrypts plaintext blocks independently.
2. Cipher Feedback (CFB) Mode:
   • Uses an initialization vector (IV).
   • Previous ciphertext influences the next encryption.
3. Cipher Block Chaining (CBC) Mode:
   • IV added to plaintext before encryption.
4. Output Feedback (OFB) Mode:
   • IV generates a sequence used to encrypt plaintext bits.

Summary

• Discussed product ciphers, principles of block cipher design, and modes of operation.
• Future lectures will cover block ciphers in more detail.