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 Email: firstname.lastname@utoronto [dot] ca 
WHEN & WHERE 
Mondays: 12pm at CCT 2150 Wednesdays: noon2pm at DV 3093 Tutorial (Fri): 45pm at IB 200 
OFFICE HOURS  Monday 23pm (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.

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/usingsources/hownottoplagiarize (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 Numbertheoretic 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 ZeroKnowledge Proofs.Prerequisites: MAT223H5 Linear Algebra I, MAT224H5 Linear Algebra II, MAT301H5 Groups and Symmetries.
Problem Sets
Posted Jan 7, Due Jan 21 (Monday) at 1pm in class.
Posted Jan 22, Due Feb 4 (Monday) at 1pm in class.
Posted Feb 11, Due Feb 25 (Monday) at 1pm in class.
Posted Mar 12, Updated Mar 23, Due Mar 25 (Monday) at 1pm in class.
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 HoffsteinPipherSilverman (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 HoffsteinPipherSilverman (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 numbertheory oriented material in this class. Read Section 9 for today's topic.
 Lecture 6 (Jan 23):
The discrete logarithm problem and introduction to publickey cryptography.
DiffieHellman Key Exchange.
 Reading for today's class: Sections 2.1, 2.2, 2.3.
 The DiffieHellman 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 stepgiant 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, MillerRabin Test.
 Reading for today's class: Section 3.3, 3.4.
 Reading: "Twenty Years of Attacks on the RSA Cryptosystem" by Dan Boneh. [ RSAsurvey.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):
Grouptheoretic proofs for Fermat and MillerRabin 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 p1 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 onehour 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 publickey cryptography. DiffieHellman Key Exchange. Lecture 7 (Jan 28) El Gamal Publickey 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: MillerRabin. 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 1822 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 p1 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