MAT302 (Winter 2012): Algebraic Cryptography
Announcements
 (Apr 16) The solutions to PS4 and PS5 are now posted. See below.
 (Apr 2) A checklist of topics for the final exam is here.
 (Apr 2) Finals Practice Exam has been posted. Download it here. I will
discuss this in the review session which will take place from 12pm on Monday, April 2 tentatively at IB 370.
Please remember to submit the solutions to PS5 during the review session or (if you cannot make it) at the instructor's office (slip it under the door).
 (Mar 24) The final problem set (PS5) has been posted. It is due Monday, April 2 at 1pm in my office CCT 3073.
 (Feb 20) Solutions to Problem sets 1 and 2 have been posted  see below in the section on "Problem Sets". Go over the previous (and future!) problem sets to prepare for the midterm!
 (Feb 20) Midterm Practice Exam has been posted. Download it here. I expect everyone to look over this and come prepared for the review session on Monday.
 (Feb 20) Problem Set 4 has been posted and is due Mar 12 in class. Good luck!
 (Feb 08) Look at the first chapter of the book of Papadimitriou, Dasgupta and Vazirani [ link ] for a great exposition of the number theoretic algorithms we did so far.
 (Feb 07) Problem Set 3 has been posted and is due Feb 17 in class. Good luck!
 (Jan 20) Problem Set 2 has been posted and is due Jan 30 in class. Start working on this early. Good luck!
 (Jan 6) Problem Set 1 has been posted and is due Jan 16 in class. Good luck!
 (Jan 2) 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 IB 370 Wednesdays: 13pm at IB 379 Tutorial (Fri): 1011am at IB 360 
OFFICE HOURS  Wednesdays 34pm (and by appointment) 
TEXTBOOK 
We have a recommended 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 in the beginning of the 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 or at:
http://www.utm.utoronto.ca/regcal/WEBGEN127.html
http://www.utm.utoronto.ca/regcal/WEBGEN92.html (Academic Honesty)
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
 Problem Set 1. [ pdf  latex source ]
Posted Jan 6, Due Jan 16 (Monday) at 1pm in class.
Solution Set 1. [pdf]  Problem Set 2. [ pdf  latex source ]
Posted Jan 20, Due Jan 30 (Monday) at 1pm in class.
Solution Set 2. [pdf]  Problem Set 3. [ pdf  latex source ]
Posted Feb 07, Due Feb 17 (Friday) at 10am in class (NOTE the Friday deadline).
Solution Set 3. [pdf]  Problem Set 4. [ pdf  latex source ]
Posted Feb 20, Due Mar 12 (Monday) at 1pm in class.
Solution Set 4. [pdf]  Problem Set 5. [ pdf  latex source ]
Posted Mar 23, Due Apr 02 (Monday) at 1pm in the instructor's office (CCT 3073).
If you cannot make it on Friday, please slip the solutions under the office door.
Solution Set 5. [pdf]
Supplementary Material for the Lectures
 Lecture 1 (Jan 2): Overview of the Course
 Exercise for today: Watch Professor Ronald Rivest's lecture on "The Growth of Cryptography" [ link ]
 If you are interested in the historical evolution of cryptography, the book "The CodeBreakers  The Story of Secret Writing" by David Kahn is a good read.
 My powerpoint slides for today's lecture [ pptx ]
 Lecture 2 (Jan 4): The Caesar and Affine Ciphers. Some Basic Number Theory  the groups Z_{n} and Z*_{n} and the Euler Totient Function.
 References for today: Chapter 1, Section 1.4 (Caesar and Affine Ciphers) and Chapter 6, Section 6.3.3 (Euler's Phi Function) of Paar and Pelzl.
 Lecture notes to be posted after class.
 Lecture 3 (Jan 9): The Vigenere Cipher. Frequency Analysis attacks.
 Lecture notes for Frequency Analysis attacks [ pdf ].
Warning: these are rough notes for the "frequency analysis" section of today's lecture. Will be updated after class.
 Lecture notes for Frequency Analysis attacks [ pdf ].
 Lecture 4 (Jan 11): Perfect Security and the Onetime Pad. The Euclidean Algorithm
 Reference for today: Chapter 2.2.2. of PaarPelzl to read about onetime pad.
 Reference for today: Chapter 6.3.1 and 6.3.2 of PaarPelzl for the (extended) Euclidean algorithm.
 Lecture 5 (Jan 16): The extended Euclidean Algorithm, and how to find inverses mod n.
 Reference for today: Chapter 6.3.1 and 6.3.2 of PaarPelzl for the (extended) Euclidean algorithm.
 Lecture 6 (Jan 18): The extended Euclidean Algorithm (contd.), Running time of the Euclidean algorithm.
 Reference for today: Chapter 6.3.1 and 6.3.2 of PaarPelzl for the (extended) Euclidean algorithm.
 Lecture 7 (Jan 23): Fermat's Little Theorem and Euler's Theorem. Fast Exponentiation Methods.
 Reference for today: Section 6.3.4 of PaarPelzl for Fermat's little theorem and Euler's theorem.
 Make sure to brush up on your Group Theory before you come to class, e.g., from Joseph A. Gallian, "Contemporary Abstract Algebra".
 Lecture 8 (Jan 25): Exponentiation Algorithms. Analysis of Running Times of Algorithms, the asymptotic notation.
 Reference for the asymptotic notation: Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", Third Edition, Chapter 3 , The MIT Press.
 Lecture 9 (Jan 30): Finding Modular Roots, the RSA Encryption Scheme.
 The Original RSA Paper: pdf
 Read Chapter 7 of PaarPelzl.
 Lecture 10 (Feb 1): RSA Encryption Scheme (contd.)
 The Original RSA Paper: pdf
 Lecture 11 (Feb 6): RSA Encryption Scheme (contd.)
 Lecture 12 (Feb 8): Asymptotic Notation, Running times of Algorithms
 Lecture 13 (Feb 13): Primality Testing, Wilson's Theorem, the Fermat Test
 Lecture 14 (Feb 15): Fermat Test (contd.), Fermat Witnesses and Liars, the Discrete Logarithm Problem and the Diffie Hellman key exchange scheme
 Lecture 15 (Feb 27): Midterm Review.
 Make sure to review all the prior material before coming to class. Go over the practice midterm posted here.
 Lecture 16 (Feb 29): Midterm.
Schedule (subject to change)
Lecture  Topic  Announcements  Problem Sets 
Lecture 1 (Jan 2)  Administrivia. a onehour version of the course. [ supplementary material ]  
Lecture 2 (Jan 4)  The Caesar and Affine Ciphers. Some Basic Number Theory  the groups Z_{n} and Z*_{n} and the Euler Totient Function. 
Problem Set 1 posted; due Jan 16 in class. 

Lecture 3 (Jan 9)  The Vigenere Cipher. Frequency Analysis attacks.  
Lecture 4 (Jan 11)  Perfect Security and the Onetime Pad. The (extended) Euclidean Algorithm  
Lecture 5 (Jan 16) 
Problem Set 1 due in class 

Lecture 6 (Jan 18) 
Problem Set 2 posted; due Jan 30 in class. 

Lecture 7 (Jan 23)  
Lecture 8 (Jan 25)  
Lecture 9 (Jan 30) 
Problem Set 2 due in class 
Problem Set 3 posted; due Feb 13 in class. 

Lecture 10 (Feb 1)  
Lecture 11 (Feb 6)  
Lecture 12 (Feb 8)  
Lecture 13 (Feb 13) 
Problem Set 3 due in class 
Problem Set 4 posted; due Mar 12 in class (You have 4 weeks for this pset!) 

Lecture 14 (Feb 15)  
Feb 2024  Reading Week  NO CLASSES  
Lecture 15 (Feb 27)  
Lecture 16 (Feb 29)  MIDTERM (in class)  
Lecture 17 (Mar 5)  
Lecture 18 (Mar 7)  
Lecture 19 (Mar 12) 
Problem Set 4 due in class 

Lecture 20 (Mar 14)  
Lecture 21 (Mar 19)  
Lecture 22 (Mar 21) 
Problem Set 5 posted; due Apr 2 at 1pm in the instructor's office CCT 3073 

Lecture 23 (Mar 26)  
Lecture 24 (Mar 28) 