MAT302 (Winter 2013): Introduction to Algebraic Cryptography




Announcements

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.

    • 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