CSPP 532 Midterm Exam: Tuesday, July 31

The midterm will begin promptly at 5:30, and will be somewhere between 70 and 90 minutes in length. No calculators, books, notes, or other aids are permitted.

The best advice I can give you is to look over the homeworks. If you have any questions about what I was looking for on an old assignment, please ask.

Here's a sampling of things I might put on the test.

• Algorithms. You should focus on the algorithms discussed in class and assigned for homework:
  • Euclid's Algorithm (the simple version for GCD, the extended version for modular inverses)
  • Modular Exponentiation (done with repeated squaring)
  • Primality Testing (trial division and Miller-Rabin)
  I will not ask you to write out code or pseudocode, but I might ask you to describe the algorithms, I might ask you about running times, and I might ask you to do the algorithm on some reasonably-sized numbers.
• Math exercises. (For example, you should know Fermat's Theorem and Euler's Theorem, and you should know how to do phi(n) when n is prime or when n = pq for distinct primes p, q. I don't expect you to reproduce any proofs from class, but I might ask you to do a short proof.)
• The difference between polynomial time and exponential time. This is a central idea of the class. It could come up in a discussion of algorithms or of cryptosystems. Or I could ask something more direct.
• Cryptographic primitives. (For example, you should know what kinds of primitives DES, SHA, and HMAC are, and the key lengths associated with them. You don't need to reproduce the details of the algorithms. I don't expect you to memorize dates, but you should have a sense of which algorithms are current standards and which are now considered insecure.)
• Cryptographic protocols. In particular, how RSA works, and how you combine elements to get a particular scheme (like a signature scheme).
• Attacks. Birthday, birthday, birthday. This also includes factoring, a bit about Deep Crack, password-guessing, and so on.
• Implementation, and human issues. Again, not so much details (e.g., how PGP generates secret keys) but general ideas (the way systems can be insecure even when the underlying cryptography seems sound).

Good luck.