1 Exam Coverage

The midterm examination will cover the topics of the first 13 lectures of the course (through October 19). 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 4 for reviewing number theory.
4. Textbook (Trappe and Washington), relevant sections from chapters 1–4, 6, 7, 15.
5. Supplementary textbook (Talbot and Welsh), sections 4.3, 5.1–5.3, 7.3, 7.4, 7.6, 7.7, 9.3.
6. Other resources available in the library and on the web.
7. 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.
      • 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.
   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.
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 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.
   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).
      • Shank’s algorithm for finding square roots modulo an odd prime.
      • Legendre symbol.
      • Jacobi symbol.
      • Jacobi symbol identities (don’t memorize, but understand what they are).
      • Computing the Jacobi symbol.
   7. Probabilistic primality testing
      • General framework for tests of compositeness (from lecture notes 10).
      • 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.