Test II Review Sheet for
Colorado State University, Pueblo
Math 319 — Number Theory — Spring 2015

Definitions

You should be able to give careful, complete, formal definitions of — and examples and know theorems involving — the following terms:
  1. Euler's $\phi$ or totient function
  2. the [multiplicative] order of $a$ in mod $n$, $\operatorname{ord}_n(a)$
  3. the cyclic subgroup of $(\ZZ/n\ZZ)^*$ generated by $a$, $\left<a\right>$
  4. a coset of $\left<a\right>$
  5. cryptography
  6. cryptanalysis
  7. cryptology
  8. cryptosystem
  9. confidentiality of a cryptosystem
  10. [message] integrity of a cryptosystem
  11. [sender] authentication of a cryptosystem
  12. [sender] non-repudiation of a cryptosystem
  13. the scytale cryptosystem
  14. plaintext
  15. cipher
  16. ciphertext
  17. encrypt, decrypt
  18. key
  19. Caesar cryptosystem
  20. Kerckhoff's Principle
  21. ROT13
  22. Vigenère cryptosystem
  23. one-time pad
  24. keyspace
  25. brute force attack
  26. message space
  27. frequency distribution and frequency analysis
  28. ETAOINSHRDL
  29. square error, a distance between distribution functions
  30. symmetric/private-key cryptosystem
  31. asymmetric/public-key cryptosystem, with its public key and private key
  32. [cryptographic] salt
  33. [cryptographic] one-way function
  34. the RSA cryptosystem
  35. the prime number counting function $\pi(x)$
  36. cryptographic hash function
  37. pre-image resistance
  38. second pre-image resistance
  39. collision resistance
  40. an RSA digital signature: accept, reject, signing key, and verification key
  41. man-in-the-middle attack
  42. digital certificate
  43. web of trust, key-signing party
  44. certificate authority [CA]
  45. public key infrastructure [PKI]

Theorems, Conjectures, and Algorithms

Please know careful, complete statements of the following:
  1. a few results about computing Euler's totient function
  2. The Fundamental Theorem of Arithmetic
  3. Wilson's Theorem
  4. the version of Lagrange's Theorem for $\operatorname{ord}_n(a)$
  5. Euler's Theorem
  6. Fermat's Little Theorem [two versions]

Things to know how to do

  1. compute $\phi(n)$
  2. prove simple statements about or using prime numbers
  3. encrypt and decrypt messages with the cryptosystems mentioned above
  4. sign and verify using RSA digital signatures
  5. use frequency analysis to crack a simple cryptosystem
  6. use a man-in-the-middle attack in some situation where you completely control a network
  7. make a digital certificate for someone (say, at a key-signing party)
  8. give proofs of any of the theorems mentioned above

Format of the test

Be able to state — in full formality and five-part harmony — all the definitions. You will be asked to do so for something like four or five out of seven or eight choices. You must also be able to give context, ideas, examples, etc., for each term you define!

You will also be asked to give full and formal statements of several of the theorems mentioned above, as well as an example (or counterexample when some hypothesis is dropped) to which the theorem applies. There are only a few theorems above, so you should be ready on all of them. You will also likely have to use those theorems in proving other statements.

There will then be a choice of two or three [or four] out of six [seven, or eight] proof-y and/or computational things to do. Some of these will be proofs of the above theorems. Others will be to perform some cryptographic or cryptanalytic task with given data -- obviously, this data will be small, and you may use a calculator to help you with it. Finally, there will be some small statements, on the level of maxiquizzes, that you can choose to prove.

Part of the test will be take-home, over the weekend, so you have time to think things through carefully.