Math 175: Introduction to Cryptology and Discrete Mathematics

Fall 2002

Course meets: MW 11:30-1 in 427 Dennison, and F 11-12 in B737 East Hall (computer lab in the basement).

Instructor: Sergey Fomin, 2858 East Hall, 764-6297, fomin@umich.edu

Office hours: MW 1-2 and F 12-1 in 2858 East Hall, and by appointment.

Course homepage: http://www.math.lsa.umich.edu/~fomin/175.html

Text (required):
Invitation to cryptology, by Thomas H. Barr, Prentice Hall, 2002.

Supplementary texts (none required):
The mathematics of ciphers, by S.C.Coutinho, AK Peters, 1998.
Cryptological mathematics, by R.E.Lewand, Mathematical Association of America, 2000.
Introduction to cryptography, by J.A.Buchmann, Springer-Verlag, 2001.
An Introduction to Cryptology and Discrete Math - The Math 175 Coursepack, by C.Greene, P.Hanlon, T.Hsu, and J.Hutchinson.

Prerequisites: Math 115 or equivalent (single-variable calculus) recommended.

Description: This course gives a historical introduction to Cryptology, the science of secret codes. It begins with the oldest recorded codes, taken from hieroglyphic engravings, and ends with the encryption schemes used to maintain privacy during Internet credit card transactions. Since secret codes are based on mathematical ideas, each new kind of encryption method leads in this course to the study of new mathematical ideas and results.

The first part of the course deals with permutation-based codes: substitutional ciphers, transpositional codes, Vigenere ciphers and more complex polyalphabetic substitutions including those created by rotor machines such as the WWII Enigma. The mathematical subjects treated in this section include permutations, modular arithmetic and some elementary statistics.

In the second part of the course, the subject moves to bit stream encryption methods. These include block cipher schemes such as the Data Encryption Standard (DES). The mathematical concepts introduced here are recurrence relations and some more advanced statistical results.

Public key encryption is the subject of the final part of the course. We learn the mathematical underpinnings of Diffie-Hellman key exchange, RSA and Knapsack codes. A substantial number of results from elementary number theory are needed and proved in this section of the course.

There is considerable development of problem-solving skills in Math 175. So, students taking the course should have significant mathematical experience and sophistication.

Grading: There are no quizzes and no exams in the course. The grade will be based on homework together with weekly computer labs.

This course will not be graded on a curve, i.e., there are not a set number of each grade to be given out. Every student with the total score of 90% (resp., 80%, 70%, 60%) is guaranteed the final grade of A (resp., B or higher, C or higher, D or higher).

Homework: There will be four types of homework assignments:

  1. Regular homework. Traditional problem sets.
  2. Pick-your-own. Harder problems, but you pick the ones you like (from a given set).
  3. Crypto challenges.
  4. Lab reports.
Topics covered:
Disclaimer: The links below are to pages outside this website. These pages are independently maintained by respective owners, who are responsible for their content.

  1. Shift ciphers. Affine ciphers. The cipher wheel. Jefferson's cipher wheel.
  2. The Josephus problem. Watch the game or try different parameter values.
  3. Proofs by induction.
  4. Binary notation.
  5. Congruences and modular arithmetic.
  6. Substitutional ciphers. Try the Magic Decoder or the Cypherspace.
  7. Permutations. Basic counting techniques.
  8. Transpositional ciphers.
  9. The Vigenere cipher.
  10. Binomial coefficients. The Pascal triangle and the Sierpinski gasket.
  11. Rotor machines. The Enigma: photos, simulator.
  12. Random experiments. Bernoulli trials. Pseudorandom bit streams.
  13. Linear shift registers. Linear recurrences. Fibonacci numbers. Phyllotaxis.
  14. Finite differences.
  15. Modular arithmetic.
  16. Euclidean algorithm. The three jugs puzzle.
  17. The fundamental theorem of arithmetic.
  18. The Hill cipher.
  19. Feistel networks.
  20. Knapsack ciphers.
  21. Fermat's little theorem.
  22. Diffie-Hellman key exchange.
  23. Mental poker.
  24. RSA.

Useful links

Cryptology courses on the net