# CO 485/685 - Fall 2008

## The Mathematics of Public Key Cryptography

Instructor: David Jao

Office hours: Wed. 3:30-4:30, Thurs. 4-5

### Course materials

- Syllabus (
*https:../../wiki/images/f/fe/Outline.pdf*) - Course notes (
*https:../../wiki/images/e/e6/Co685.pdf*) (updated November 26) - Rabin decryption oracle (
*https:../../cgi-bin/rabin.cgi*) - Quiz 1 (
*https:../../wiki/images/e/ea/Quiz1.pdf*) - AES animation (
*http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf*) (via Wikipedia (*https://en.wikipedia.org/wiki/Advanced_Encryption_Standard*))

### Assignment schedule

This schedule is tentatively made available for planning purposes and may be subject to change.

- Assignment 1 (
*https:../../wiki/images/6/65/Assignment1.pdf*) (due September 22)- Corrected version as of Monday, September 15: In problem 3(a), q-1 should have been p-1, p should have been a prime, and the due date has been moved to Monday.

- Assignment 2 (
*https:../../wiki/images/a/a8/Assignment2.pdf*) (due October 3)- The number in problem 1 is 624142660586694101446291308147581805825611279851037995772020202145871 for those of you who wish to cut and paste it.

- Assignment 3 (
*https:../../wiki/images/4/44/Assignment3.pdf*) (due October 17)- In problem 1, the prime p is 10
^{75}+ 129. The public key is 421853791186609042825716562661266229106681564402837873445139139395759685625 and the ciphertext is (357087535603338629029169017815297250719503384049242732666037767131122789608, 4551181581441151217382245023086425998289291635511324855776759119834162513230).

- In problem 1, the prime p is 10
- Midterm (October 22)
- The midterm will be held in RCH 212 from 4:30 to 6:20.
- The midterm is closed book and closed notes. A non-programmable calculator is allowed.
- The exam covers all material up to and including hash functions (October 8).
- Some practice problems (
*https:../../wiki/images/7/79/Practice-exam.pdf*) are available.

- Assignment 4 (
*https:../../wiki/images/7/70/Assignment4.pdf*) (due November 14) - Assignment 5 (
*https:../../wiki/images/6/62/Assignment5.pdf*) (due November 28) - Final exam (December 5)
- The final exam will be held in RCH 212 from 12:30 to 3:00.
- The exam is closed book and closed notes. A non-programmable calculator is allowed.
- Practice problems (
*https:../../wiki/images/a/a3/Practice-final.pdf*) for the final exam.

- Project (
*https:../../wiki/images/0/00/Project.pdf*) (CO 685 only; due December 19)

### Lectures

- September 8: Symmetric vs. public key cryptography. Diffie-Hellman, ElGamal.
- Septemebr 10: Examples of public key cryptosystems: RSA, Rabin, GM.
- September 12: Polynomial time algorithms, Computational number theory, Euclidean algorithm.
- September 15: Modular arithmetic, generators, quadratic residues.
- September 17: Euler's criterion, quadratic reciprocity.
- September 19: Jacobi symbols, modular square roots.
- September 22: Security definitions: one-way, IND-CPA, IND-CCA2
- September 24: Primality testing, Solovay-Strassen test
- September 26: Integer factorization. Pollard rho algorithm, Dixon's random squares method.
- September 29: Running time of integer factorization. Security proofs.
- October 1: Discrete logarithms, CDH, DDH, IND-CPA security.
- October 3: Pollard rho algorithm for discrete logarithms.
- October 6: Pohlig-Hellman algorithm, index calculus.
- October 8: Hash functions, preimage resistance, collision resistance.
- October 10: Why chosen ciphertext security matters.
- October 15: Cryptographic random number generators. Blum-Blum-Shub.
- October 17: Hard core predicates. Zero knowledge proofs.
- October 20: Proof of correctness and zero knowledge for zero knowledge proofs.
- October 22: One round and non-interactive zero knowledge proofs.
- October 24: Chosen ciphertext secure cryptosystems. DDN, Fujisaki-Okamoto.
- October 27: Proof of security for Fujisaki-Okamoto.
- October 29: Digital signature schemes. Security definitions.
- October 31: RSA signatures. ElGamal, DSA, Schnorr signature schemes.
- November 3: Elliptic curves: motivation, definition, group law
- November 5: Size and structure of elliptic curve group and n-torsion points.
- November 7: Hasse-Weil bound. Schoof's algorithm. Point compression.
- November 10: ECDSA. Bilinear pairings. BLS signatures.
- November 12: Full domain hash RSA, proof of unforgeability.
- November 14: BDH, tripartite key exchange, non-interactive key exchange, IBE.
- November 17: Relationship between pairings, DLOG, and DDH. Embedding degree.
- November 19: Divisors and principal divisors.
- November 21: Definition of Weil pairing. Proof of bilinearity.
- November 24: Efficient computation of the Weil pairing.
- November 26: Boneh-Boyen signatures and Boneh-Boyen IBE.
- November 28: Security proof for Boneh-Boyen signatures.
- December 1: Optimal embedding degrees for type 1 and type 2 pairings.