MAT302 (Winter 2013): Introduction to Algebraic Cryptography

Announcements

(Apr 16) Check out the checklist of topics for the finals.
(Apr 16) I have posted the solutions to the midterm. They can be downloaded from this link. Good luck with the finals tomorrow!
(Apr 05) Here is the practice final we did in class today, together with solutions.
(Apr 05) I have posted the PS4 and PS5 solutions below. Check them out.
(Mar 23) PS4 has been updated. Essentially, you now have two parts in Question 3, and you need to answer only one of them.
(Mar 12) PS4 has been posted below and is due March 25.
(Mar 12) PS3 solutions has been posted below.
(Feb 18) Here is a practice midterm test. Make sure to attempt solving all these problems before the class on Monday, the 25th.
(Feb 18) Here is the list of topics you will need to know for the midterm. This includes everything we have done in class until the last lecture.
(Feb 11) I have posted a number of additional references and advanced reading material on primality testing.
(Feb 11) Problem Set 3 has been posted.
(Feb 11) Solutions to Problem Sets 1 and 2 have been posted. Check them out below!
(Jan 7) Problem Set 1 has been posted and is due Jan 21 in class. Good luck!
(Jan 7) Welcome to MAT 302! Make sure to check this website often.

Course Information

INSTRUCTOR	Vinod Vaikuntanathan Office: 3073 CCT Building E-mail: firstname.lastname@utoronto [dot] ca
WHEN & WHERE	Mondays: 1-2pm at CCT 2150 Wednesdays: noon-2pm at DV 3093 Tutorial (Fri): 4-5pm at IB 200
OFFICE HOURS	Monday 2-3pm (and by appointment)
TEXTBOOK	We have a required textbook that we will more or less follow through the course. In cases where the material taught is not readily available online, I will try to provide course notes or other online references. Required: J. Hoffstein, J. Pipher and J. Silverman, Available at the bookstore and online via the UofT Libraries. Reference: Steven Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, 1st Ed. Online Reference: Nigel Smart, Cryptography: An Introduction, Third Edition, http://www.cs.bris.ac.uk/~nigel/Crypto_Book/book.ps. Reference: Thomas Cormen, Charles Leiserson and Ronald Rivest, Introduction to Algorithms, The MIT Press.
GRADING	Five problem sets (for a total of 35%), class participation (5%), a midterm (20%) and a final (40%). Problem Sets are due at the beginning of class.

All this information (and more) can be found in the course information sheet.

See here for the policy on special consideration in case of late assignment submissions.

Students should become familiar with and are expected to adhere to the Code of Behaviour on Academic Matters, which can be found in the UTM Calendar:
https://registrar.utm.utoronto.ca/student/calendar/calendar_detail2.pl?Topic=Codes%20and%20Policies http://www.writing.utoronto.ca/advice/using-sources/how-not-to-plagiarize (Advice on avoiding plagiarism).

Course Description

The course will take students on a journey through the methods of algebra and number theory in cryptography, from Euclid to Zero Knowledge Proofs. Topics include: Block ciphers and the Advanced Encryption Standard (AES); Algebraic and Number-theoretic techniques and algorithms in Cryptography, including methods for primality testing and factoring large numbers; Encryption and Digital Signature systems based on RSA, Factoring, Elliptic Curves and Integer Lattices; and Zero-Knowledge Proofs.

Prerequisites: MAT223H5 Linear Algebra I, MAT224H5 Linear Algebra II, MAT301H5 Groups and Symmetries.

Problem Sets

Problem Set 1. [ pdf | latex source | solutions ]
Posted Jan 7, Due Jan 21 (Monday) at 1pm in class.

Problem Set 2. [ pdf | latex source | solutions ]
Posted Jan 22, Due Feb 4 (Monday) at 1pm in class.

Problem Set 3. [ pdf | latex source | solutions]
Posted Feb 11, Due Feb 25 (Monday) at 1pm in class.

Problem Set 4. [ pdf | latex source | solutions]
Posted Mar 12, Updated Mar 23, Due Mar 25 (Monday) at 1pm in class.

Problem Set 5. [ pdf | latex source | solutions]
Posted Mar 25, Due Apr 3 (Wednesday) at noon in class.

Supplementary Material for the Lectures

Lecture 1 (Jan 7): Overview of the Course
- Exercise for today: Watch Professor Ronald Rivest's lecture on "The Growth of Cryptography" [ link ]
- My powerpoint slides for today's lecture [ pptx ]
Lecture 2 (Jan 9): Euclid's GCD and extended GCD algorithm, and applications.
- Reading for today's class: The Hoffstein-Pipher-Silverman (HPS) Book, Chapter 1, Sections 1.2 and 1.3 (excluding 1.3.1 and 1.3.2).
Lecture 3 (Jan 14): Properties of Z_N*: How to find inverses, the Euler Totient Function.
- Reading for today's class: The Hoffstein-Pipher-Silverman (HPS) Book, Chapter 1, Sections 1.3 (excluding 1.3.1 and 1.3.2), Section 1.4.
Lecture 4 (Jan 16): Fermat's Little Theorem, Fast exponentiation algorithms.
- Reading for today's class: Section 1.3 and 1.5.
Lecture 5 (Jan 21): Z_p* is cyclic for prime p, the number of elements of order d in Z_p*.
- Reading for today's class: Theorem 1.31 (Page 33) -- we will present a proof which is in the reference below.
- Professor Dana Angluin's lecture notes on computational number theory [ pdf ] are a great resource for number-theory oriented material in this class. Read Section 9 for today's topic.
Lecture 6 (Jan 23): The discrete logarithm problem and introduction to public-key cryptography. Diffie-Hellman Key Exchange.
- Reading for today's class: Sections 2.1, 2.2, 2.3.
- The Diffie-Hellman paper [ pdf ]
- Merkle's undergraduate class project that (co-)invented public key cryptography [ class project, pdf ]
Lecture 7 (Jan 28): Diffie Hellman overview, El Gamal Public Key Encryption.
- Reading for today's class: Section 2.4.
Lecture 8 (Jan 30): How hard is the discrete logarithm problem? The baby step-giant step method.
- Reading for today's class: Section 2.6, 2.7.
Lecture 9 (Feb 04): Finding roots and the RSA encryption scheme.
- Reading for today's class: Section 3.1, 3.2.
- The RSA paper [ RSApaper.pdf ]
Lecture 10 (Feb 06): Some Improper ways of using RSA. Primality Testing: Fermat Test and Carmichael Numbers, Miller-Rabin Test.
- Reading for today's class: Section 3.3, 3.4.
- Reading: "Twenty Years of Attacks on the RSA Cryptosystem" by Dan Boneh. [ RSA-survey.pdf ]
Lecture 11 (Feb 11): Miller Rabin (contd.) and its Analysis.
- Reading for today's class: Section 3.4.
- Reading: "Primality Tests based on Fermat's Little Theorem" by Manindra Agrawal. [ pdf ]
- More Advanced Reading: "Primality Testing: variations on a theme of Lucas" by Carl Pomerance. [ pdf ]
Lecture 12 (Feb 13): Group-theoretic proofs for Fermat and Miller-Rabin tests, Chinese Remainder theorem.
- Section 2.8 of the book.
- Optional Advanced Reading: Manindra Agrawal's paper and also the original AKS paper.
- Optional Advanced Reading: For a lighter description of AKS, see Terry Tao's blog.
Lecture 13 (Feb 25): Midterm Review.
Lecture 14 (Feb 27): Midterm.
Lecture 15 (Mar 04): Pollard's p-1 Factoring Algorithm.
- Section 3.5 of the book.

Lecture 16 (Mar 06): Factorization via Difference of Squares, Quadratic Field Sieve.

Section 3.6 of the book.

Schedule (subject to change)

Lecture	Topic	Announcements	Problem Sets
Lecture 1 (Jan 7)	Administrivia. a one-hour version of the course. [ supplementary material ]		Problem Set 1 posted; due Jan 21 in class.
Lecture 2 (Jan 9)	Euclid's GCD and extended GCD algorithm, and applications.
Lecture 3 (Jan 14)	Properties of Z_N*: How to find inverses, the Euler Totient Function.
Lecture 4 (Jan 16)	Fermat's Little Theorem, Fast exponentiation algorithms.
Lecture 5 (Jan 21)	Z_p* is cyclic for prime p.	Problem Set 1 due in class	Problem Set 2 posted; due Feb 4 in class.
Lecture 6 (Jan 23)	The discrete logarithm problem and introduction to public-key cryptography. Diffie-Hellman Key Exchange.
Lecture 7 (Jan 28)	El Gamal Public-key Encryption.
Lecture 8 (Jan 30)	How hard is the discrete logarithm problem?
Lecture 9 (Feb 4)	Finding roots and the RSA encryption scheme.	Problem Set 2 due in class
Lecture 10 (Feb 6)	Primality Testing: Fermat Test, Carmichael Numbers.
Lecture 11 (Feb 11)	Primality Testing: Miller-Rabin.		Problem Set 3 posted; due Feb 25 in class.
Lecture 12 (Feb 13)	Primality Testing: Miller Rabin and its analysis. The Chinese Remainder Theorem.
Feb 18--22	Reading Week -- NO CLASSES
Lecture 13 (Feb 25)	Midterm Review	Problem Set 3 due in class
Lecture 14 (Feb 27)	MIDTERM (in class)
Lecture 15 (Mar 4)	Pollard's p-1 Factoring Algorithm.
Lecture 16 (Mar 6)	Quadratic Field Sieve for Factoring.
Lecture 17 (Mar 11)	Zero Knowledge Proofs and Identification Schemes		Problem Set 4 posted; due Mar 25 in class
Lecture 18 (Mar 13)	Digital Signatures and their uses.
Lecture 19 (Mar 18)	RSA signatures, El Gamal and DSA Signatures.
Lecture 20 (Mar 20)	Secret Sharing Schemes.
Lecture 21 (Mar 25)	Elliptic Curves.	Problem Set 4 due in class	Problem Set 5 posted; due Apr 3 in class
Lecture 22 (Mar 27)	Elliptic Curves (Contd.)
Lecture 23 (Apr 1)	Elliptic Curves over finite fields.
Lecture 24 (Apr 3)	Elliptic Curves over Finite Fields (contd.), Elliptic Curve Cryptography.	Problem Set 5 due in class