MATH 415

From CS Wiki
Jump to: navigation, search


Catalog Description: A survey of the mathematical foundations of modern cryptosystems; their computational strengths/weaknesses, and uses in society.

Total Credits: 3

Contact Hours: 3 lecture hours per week

Course Coordinator: Jennifer Johnson-Leung


Prereq: MATH 330: Linear Algebra

Textbook: "Introduction to Cryptography with Coding Theory," 2nd Edition, Trappe and Washington.

Textbook URL:

Prerequisites by Topic:

Main Topics Covered

  1. Elementary Number Theory: Modular arithmetic, Extended Euclidean algorithm, Femet's little theorem, Euler's Phi function, Euler's formula, primitive roots, Fast power algorithm & quadratic reciprocity.
  2. Affine Cipher
  3. Vigen'ere Cipher
  4. Symmetric Ciphers: AES.
  5. Discrete log problem
  6. Diffie-Hellman Key Exchange
  7. El-Gamal Cryptosystem
  8. Big O Notation
  9. Meet in the middle attacks: Baby-Step/Giant-Step
  10. Pohlig-Hellman
  11. RSA Encryption Algorithm
  12. Primality Tests
  13. Pollard's p-1 Algorithm
  14. Factoring as a difference of squares
  15. Sieves
  16. Index Calculus attack on discrete logs
  17. Lattice-based Cryptography: 2-D Lattice reduction, LLL algorithm, NTRU cryptosystem
  18. Elliptic Curves: ECDLP, EC Diffie-Hellman, EC El-Gamal
  19. Cryptography in Society

Course Outcomes

  1. Display a functional understanding of elementary number theory, including solving congruences and finding primitive roots.
  2. Analyze cryptosystems with specific insight into their weaknesses.
  3. Understand and be able to implement model versions of the RSA algorithm for public key encryption, including attacks and defensive protocols.
  4. Understand and be able to solve model versions of the discrete log problem, including its relationship to the Diffie-Hellman key exchange protocol as well as elliptic curve cryptosystems.
  5. Use open source computational software, including but not limited to SAGE and Octave.