1  Exam Coverage

1. In-person class lectures.
2. Written lecture notes, weeks 1-6, available on the course web site.
3. Written handouts, available on the course web site. I especially recommend handout 3 for reviewing number theory.
4. Textbook (Wenbo Mao), relevant sections from chapters 1-3, 5-8.
5. Other resources available in the library and on the web.

2  Review Outline

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.
      • Entropy.
      • 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.
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.
7. RSA.
   1. Components.
      • Modulus.
      • Encryption key.
      • Decryption key.
      • Encryption function.
      • Decryption function.
   2. Algorithms needed.
      • Primality testing.
      • Finding modular inverse.
      • Fast modular exponentiation.
   3. Theoretical basis.
      • Prime number theorem.
      • 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.
   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 groups.
   5. Order of subgroup divides order of group.
   6. Rings.
   7. Fields.
   8. Polynomials over fields.
   9. Finite fields.
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.
   3. Chinese remainder theorem.
   4. Prime number theorem.
   5. Primitive roots.
      • Lucas test.
      • Discrete logarithm.
   6. Quadratic residues.
      • Square roots modulo a prime.
      • Square roots modulo a product of two distinct primes.
      • Euler criterion.
      • Finding square roots modulo prime p when p ≡ 3 mod 4.
      • Legendre symbol.
      • Jacobi symbol.
      • Jacobi symbol identities (don't memorize, but understand what they are).
      • Computing the Jacobi symbol.
   7. Probabilistic primality testing framework (for any valid test of compositness).
      • Fermat test of compositness ζ_a(n).
      • Strassen-Solovay test of compositeness ν_a(n)
      • Miller-Rabin test of compositeness μ_a(n).
10. Cryptographic protocols based on number theory (besides RSA).
    1. Diffie-Hellman key exchange.
    2. ElGamal key agreement.
    3. ElGamal public key cryptosystem.
    4. Goldwasser-Micali (QR) probabilistic cryptosystem.