CO 485/685 - Fall 2009

The Mathematics of Public Key Cryptography

Instructor: David Jao

Office hours: Wed. & Thurs. 3-4

Administrative

• Midterm information
  • Location: B2 350
  • Date: November 5, 2009
  • Time: 4:30-6:30pm

Course materials

• Syllabus (https:../../wiki/images/8/87/Syllabus.pdf)
• Textbook: An Introduction to Mathematical Cryptography (https://www.springer.com/math/numbers/book/978-0-387-77993-5) by Hoffstein, Pipher, and Silverman.
• Online access to the textbook: on campus (https://www.springerlink.com/content/978-0-387-77993-5) and off campus (https://www.springerlink.com.proxy.lib.uwaterloo.ca/content/978-0-387-77993-5) (requires library password).
• AES animation (http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf) (via Wikipedia (https://en.wikipedia.org/wiki/Advanced_Encryption_Standard))
• Project descriptions (https:../../wiki/images/a/a2/2009-project.pdf) for those enrolled in CO 685 (updated)
• Practice problems (https:../../wiki/images/3/3d/Sample-midterm09.pdf) for the midterm.
  • The midterm is in B2 350 on Thursday, November 5, 2009, from 4:30pm to 6:30pm.
  • The exam covers all material up to (and including) Lecture 11: Hash functions.

Assignments

• Assignment 1 (https:../../wiki/images/b/b8/Co485-a1-2009.pdf) (due Friday, Sept. 25)
• Assignment 2 (https:../../wiki/images/1/14/Co485-a2-2009.pdf) (due Friday, Oct. 9)
• Assignment 3 (https:../../wiki/images/1/17/Co485-a3-2009.pdf) (due Friday, Oct. 30)
• Assignment 4 (https:../../wiki/images/0/01/Co485-a4-2009.pdf) (due Monday, Nov. 16)
• Assignment 5 (https:../../wiki/images/f/f5/Co485-a5-2009.pdf) (due Thursday, Nov. 26)

Lectures

1. Symmetric vs. public key cryptography. Diffie-Hellman, ElGamal. (https:../../wiki/images/b/be/Lecture01.pdf)
   • Sept. 14
2. Public key cryptography. Examples and security definitions. (https:../../wiki/images/e/ef/Lecture02.pdf) (updated)
   • Sept. 16, Sept. 28, Sept. 30, Oct. 2
3. Elementary number theory. Extended Euclidean Algorithm. Order and generators. (https:../../wiki/images/1/11/Lecture03.pdf)
   • Sept. 18, Sept. 21
4. Quadratic residues, Euler's criterion, Legendre symbols, Quadratic reciprocity. (https:../../wiki/images/e/e0/Lecture04.pdf)
   • Sept. 23, Sept. 25
5. Jacobi symbols. Jacobi reciprocity. (https:../../wiki/images/c/c8/Lecture05.pdf)
   • Sept. 28
6. Security and indistinguishability proofs. (https:../../wiki/images/a/a8/Lecture06.pdf)
   • Oct. 5
7. Why chosen ciphertext security matters. (https:../../wiki/images/5/5f/Lecture07.pdf)
   • Oct. 9
8. Primality testing. (https:../../wiki/images/b/be/Lecture08.pdf)
   • Oct. 14
9. Random number generators. (https:../../wiki/images/7/71/Lecture09.pdf)
   • Oct. 16
10. Zero knowledge proofs. (https:../../wiki/images/4/45/Lecture10.pdf)
    • Oct. 19, Oct. 21
11. Hash functions and random oracles. (https:../../wiki/images/f/ff/Lecture11.pdf)
    • Oct. 23
12. Digital signatures. (https:../../wiki/images/5/5d/Lecture12.pdf)
    • Oct. 26, Oct. 28
13. Chosen ciphertext security. (https:../../wiki/images/0/02/Lecture13.pdf)
    • Oct. 30, Nov. 2, Nov. 4
14. Integer factorization. (https:../../wiki/images/b/b8/Lecture14.pdf)
    • Nov. 6
15. Computation of discrete logarithms. (https:../../wiki/images/3/3e/Lecture15.pdf)
    • Nov. 9, Nov. 13
16. Elliptic curves: introduction and background. (https:../../wiki/images/6/68/Lecture16.pdf)
    • Nov. 11
17. Implementation of elliptic curves. (https:../../wiki/images/d/df/Lecture17.pdf)
    • Nov. 13
18. Elliptic curve cryptography. (https:../../wiki/images/2/2f/Lecture18.pdf)
    • Nov. 16
19. Pairing based cryptography. (https:../../wiki/images/b/b7/Lecture19.pdf)
    • Nov. 18