1 Exam Coverage

The midterm examination will cover the topics of the first 11 lectures of the course (through October 13). These topics are presented in several different formats:

1. In-person class lectures.
2. Written lecture notes, available on the course web site.
3. Written handouts, available on the course web site. I especially recommend handout 5 for reviewing number theory.
4. Textbook (Stinson), relevant sections from chapters 1–5. Roughly speaking, this is all of chapter 1, sections 2.1–2.3, 2.7 from chapter 2, sections 3.1, 3.2, 3.5, 3.7 from chapter 3, a little bit about MAC’s (message authentication codes) from section 4.1 and 4.4, and sections 5.1, 5.2.1, 5.2.3, 5.3, 5.7.1.
5. Other resources available in the library and on the web.
6. Problem sets and solutions.

2 Review Outline

Below I give a list of topics, concepts, definitions, theorems, algorithms, and protocols that we have covered and that I expect you to know. This list is not inclusive, as I’m sure I have missed some things.

1. Secret-message transmission problem.
   1. Model.
      • Alice.
      • Bob.
      • Eve (passive eavesdropper).
      • Mallory (active eavesdropper).
      • Plaintext.
      • Ciphertext.
      • Key.
      • Encryption function.
      • Decryption function.
   2. Attacks.
      • Known plaintext.
      • Chosen plaintext.
      • Known ciphertext.
      • Chosen ciphertext.
   3. Breaking system.
      • Finding key.
      • Decrypting ciphertext.
      • Extracting partial information from ciphertext.
2. Information security in the real world.
3. Classical cryptography.
   1. Cryptosystems.
      • Caeser cipher.
      • One-time pad.
      • Simple XOR system.
      • Monoalphabetic cipher.
      • Playfair cipher.
      • Hill cipher.
      • Polyalphabetic cipher.
      • Transposition techniques.
      • Rotor machines.
      • Steganography.
   2. Security.
      • Kerckhoffs’s assumption (that only key is secret).
      • Statistical inference.
      • Brute force attack.
      • Redundancy.
      • Information-theoretic security.
   3. Stream cipher.
      • Keystream generator.
      • Next-state generator.
   4. Block cipher.
      • Block size.
      • Padding.
      • Chaining modes.
        • Electronic Codebook Mode (ECB).
        • Cipher Block Chaining Mode (CBC).
        • Cipher-Feedback Mode (CFB).
        • Output Feedback Mode (OFB).
        • Propagating Cipher-Block Chaining Mode (PCBC).
        • Recoverability from lost/damaged ciphertext blocks.
4. Data Encryption Standard (DES).
   1. Feistel network.
   2. Block size.
   3. Key size.
   4. Subkey.
   5. S-box.
   6. Rounds.
   7. Decryption.
   8. Group property of a cryptosystem.
   9. Double encryption.
   10. Birthday paradox.
5. Message Authentication Codes (MACs).
   1. Definition.
   2. Need for MACs; why encryption isn’t enough.
   3. MACs from DES and other block ciphers.
6. Asymmetric cryptosystems.
   1. Definition and requirements.
   2. Public key model.
   3. Need for resistence against chosen plaintext attack.
   4. Man-in-the-middle attack (whereby Alice is fooled into thinking that Mallory’s public key really belongs to Bob).
7. RSA.
   1. Components.
      • Modulus.
      • Encryption key.
      • Decryption key.
      • Encryption function.
      • Decryption function.
   2. Algorithms needed.
      • Primality testing. [Know why needed, but actual method not covered on midterm.]
      • Finding modular inverse.
      • Fast modular exponentiation.
   3. Theoretical basis.
      • Prime number theorem. [Not covered on midterm.]
      • Existence of modular inverse.
      • Proof that decryption function is inverse of encryption function.
   4. Computational efficiency.
   5. Security properties.
      • Factoring problem.
      • Computing ϕ(n) given factorization of n.
      • Factoring n given ϕ(n).
      • Factoring n given public and private keys. [Not covered on midterm.]
   6. Hybrid system.
      • Use RSA for secure transmission of random session key.
      • Use symmetric cryptosystem for body of message.
8. Algebra.
   1. Groups.
   2. Abelian group
   3. Subgroups.
   4. Cyclic group, generator, and order of an element.
   5. Order of subgroup divides order of group.
9. Number theory.
   1. Modular arithmetic.
      • Divides (a|b).
      • Division theorem: a = bq + r, 0 ≤ r < b.
      • The remainder operator “a mod n”
      • The congruence relation a ≡ b (mod n)
      • Z_n.
      • Computing in Z_n for large n.
      • Fast modular exponentiation.
   2. Z*_n
      • Relatively prime pairs of numbers.
      • Euler’s totient function ϕ(n)
      • Euler’s theorem and Fermat’s little theorem.
      • Consequence: x ≡ y (mod ϕ(n)) implies a^x ≡ a^y (mod n).
      • Greatest common divisor (gcd).
      • Euclidean gcd algorithm.
      • Diophantine equations and modular inverses.
      • Extended Euclidean algorithm.