CO 487: Applied Cryptography (Winter 2016)

Instructor: David Jao, djao@math, MC 5032
Office hours: Tue., Wed., Thurs. 2:00pm-3:00pm

Teaching assistants:

Edward Eaton	eeaton	MC 5481	Office hours: Thu. 12:00-1:00
Chris Leonardi	cfoleona	MC 5481	Office hours: Mon. 10:30-11:30
Vishnu Narayan	vvnaraya	MC 6011	Office hours: Wed. 11:30-12:30
Luis Ruiz-Lopez	laruizlo	MC 5129	Office hours: Tue. & Thu. 11:00-12:00
Randy Yee	r7yee	MC 5497	Office hours: Tue. 1:00-2:00

It is highly recommended that students join the Google+ community (https://plus.google.com/communities/112531518617711352585) for CO 487 to keep up to date with online discussions of assignment problems and administrative issues.

Course materials

• Course outline (https:../../wiki/images/9/96/CO487-2016-outline.pdf)
• Handbook of Applied Cryptography, (http://www.cacr.math.uwaterloo.ca/hac/) by A. J. Menezes, P. C. van Oorschot and S. A. Vanstone.

Final exam information

Past final exams: 2015 (https:../../wiki/images/5/53/CO487-2016-final1.pdf), 2013 (https:../../wiki/images/4/46/CO487-2016-final2.pdf)

Midterm information

The midterm is a closed-book, no-calculator exam.

• Past midterms: 2015 #1 (https:../../wiki/images/7/7d/CO487-2016-sample-midterm1.pdf), 2015 #2 (https:../../wiki/images/0/04/CO487-2016-sample-midterm3.pdf), 2013 (https:../../wiki/images/e/e4/CO487-2016-sample-midterm2.pdf)
• Midterm room assignments (https:../../cgi-bin/midterm.cgi)
• Exam problems (https:../../wiki/images/b/bf/CO487-2016-midterm.pdf)
• Solutions (https:../../wiki/images/2/25/CO487-2016-midterm-solutions.pdf)
• Raw score distribution (https:../../scores.txt)

Schedule

The (tentative) schedule for the course is as follows:

• Assignment 1 (https:../../wiki/images/d/d2/Co487-2016-a1.pdf) (due Friday, January 15)
  • Vigenère ciphertexts for problem 1
  • Vigenère cipher cracking tool (https://www.simonsingh.net/The_Black_Chamber/vigenere_cracking_tool.html) for problem 1
  • Ciphertext c₁ (https:../../a1/enc1.txt) for problem 2
  • Ciphertext c₂ (https:../../a1/enc2.txt) for problem 2
  • One-time-pad encryption and decryption oracle (https://djao.math.uwaterloo.ca/cgi-bin/otp.cgi) for problem 2
  • Solutions (https:../../wiki/images/5/5c/Co487-2016-s1.pdf)
• Assignment 2 (https:../../wiki/images/f/ff/Co487-2016-a2.pdf) (due Friday, January 29)
  • A Tutorial on Linear and Differential Cryptanalysis (https://dx.doi.org/10.1080/0161-110291890885) (required reading)
    • To download, click on "Download full text", then "Shibboleth", select "University of Waterloo", and enter your login.
  • Ciphertexts for linear cryptanalysis for problem 2
  • Ciphertexts for differential cryptanalysis for problem 3
  • Solutions (https:../../wiki/images/d/dd/Co487-2016-s2.pdf)
• Assignment 3 (https:../../wiki/images/8/80/Co487-2016-a3.pdf) (due Friday, February 12)
  • SageMath Cloud (https://cloud.sagemath.com/) session transcript (https:../../smc-term.txt) and VIM commands (https:../../vim-commands.txt) from Feb. 3 class
  • SHA-1 implementation: HTML (read-only) (https://djao.math.uwaterloo.ca/SHA-1.html) and Mathematica (https://djao.math.uwaterloo.ca/SHA-1.nb) formats
  • MD4 implementation: HTML (read-only) (https://djao.math.uwaterloo.ca/MD4.html) and Mathematica (https://djao.math.uwaterloo.ca/MD4.nb) formats
  • MD5 implementation: HTML (read-only) (https://djao.math.uwaterloo.ca/MD5.html) and Mathematica (https://djao.math.uwaterloo.ca/MD5.nb) formats
  • MD4 and MD5 collision generator (https://www.bishopfox.com/resources/tools/other-free-tools/md4md5-collision-code/)
  • Solutions (https:../../wiki/images/6/60/Co487-2016-s3.pdf)
• Midterm (Wednesday, February 24, 8:30am-10:20am, room TBA)
• Assignment 4 (https:../../wiki/images/8/80/Co487-2016-a4.pdf) (due Monday, March 14)
  • Supplementary material for Question 2 (https:../../a4-q2.txt)
  • SageMath Cloud worksheet (https://cloud.sagemath.com/projects/880742c9-7f65-4e25-8e9b-d117af2f023b/files/Diffie-Hellman.sagews) from the lecture of Wed. March 2 (requires SageMath Cloud account)
  • SageMath Cloud worksheet (https://cloud.sagemath.com/projects/41ddf106-61ca-414d-9097-ec676a7ea8ea/files/RSA-Coppersmith.sagews) from the lecture of Mon. March 7
  • SageMath Cloud worksheet (https://cloud.sagemath.com/projects/e58b2e0e-20b8-4846-839b-d4c0392e73f9/files/Elgamal.sagews) from the lecture of Wed. March 9
  • Solutions (https:../../wiki/images/3/39/Co487-2016-s4.pdf)
• Assignment 5 (https:../../wiki/images/6/65/Co487-2016-a5.pdf) (due Monday, March 28)
  • SageMath Cloud worksheet (https://cloud.sagemath.com/projects/e375966f-a58f-45e4-80d7-e0ac9695dcc6/files/ECDSA.sagews) (and source (https://github.com/TheBlueMatt/bitcoinninja/blob/master/secp256k1.ecdsa.sage)) from the lecture of Wed. March 16
  • SageMath Cloud worksheet (https://cloud.sagemath.com/projects/ae9d2c45-1cf1-4b44-a9a9-5de3a3f94eef/files/Shor.sagews) from the lecture of Wed. March 23
  • Solutions (https:../../wiki/images/7/7c/Co487-2016-s5.pdf)

Lectures

1. Introduction to cryptography (https:../../wiki/images/2/27/CO487-2016-slides01.pdf) (January 4)
2. Symmetric-key encryption (https:../../wiki/images/0/01/CO487-2016-slides02.pdf) (January 6)
3. Security definitions for symmetric-key encryption (https:../../wiki/images/3/3a/CO487-2016-slides03.pdf) (January 8). Some (optional) links of interest:
   • Claude Shannon, A mathematical theory of communication (https://archive.org/details/bstj27-3-379) (1948)
   • Claude Shannon, Communication theory of secrecy systems (https://archive.org/details/bstj28-4-656) (1949)
   • Randall Munroe, Security (https://xkcd.com/538/) (2009)
4. Block ciphers (https:../../wiki/images/3/35/CO487-2016-slides04.pdf) (January 11)
5. Data Encryption Standard (https:../../wiki/images/6/65/CO487-2016-slides05.pdf) (January 13)
6. Linear cryptanalysis (https:../../wiki/images/9/97/CO487-2016-slides06.pdf) (January 15)
   • Howard Heys, A tutorial on linear and differential cryptanalysis (https://dx.doi.org/10.1080/0161-110291890885) (required reading)
     • To download, click on "Download full text", then "Shibboleth", select "University of Waterloo", and enter your login.
7. Differential cryptanalysis (https:../../wiki/images/b/b0/CO487-2016-slides07.pdf) (January 20)
8. Cryptanalysis of DES (https:../../wiki/images/9/9d/CO487-2016-slides08.pdf) (January 22). Optional reading:
   • Eli Biham and Adi Shamir, Differential cryptanalysis of DES-like cryptosystems (https://link.springer.com/chapter/10.1007/3-540-38424-3_1)
9. Advanced Encryption Standard (https:../../wiki/images/d/d2/CO487-2016-slides09.pdf) (January 25)
10. Block cipher modes of operation (https:../../wiki/images/d/dd/CO487-2016-slides10.pdf) (January 27)
11. Hash functions (https:../../wiki/images/d/df/CO487-2016-slides11.pdf) (January 29)
12. Iterated hash functions (https:../../wiki/images/7/74/CO487-2016-slides12.pdf) (February 1)
13. Collisions in iterated hash functions (https:../../wiki/images/4/47/CO487-2016-slides13.pdf) (February 3)
14. Message Authentication Codes (https:../../wiki/images/8/8f/CO487-2016-slides14.pdf) (February 5)
15. Authenticated encryption (https:../../wiki/images/2/20/CO487-2016-slides15.pdf) (February 8)
16. Applied cryptanalysis (https:../../wiki/images/a/a3/CO487-2016-slides16.pdf) (February 10)
17. Cryptography, law, and society (https:../../wiki/images/f/ff/CO487-2016-slides17.pdf) (February 12)
18. Introduction to public-key cryptography (https:../../wiki/images/d/db/CO487-2016-slides18.pdf) (February 26)
19. RSA encryption (https:../../wiki/images/d/d3/CO487-2016-slides19.pdf) (February 29). Optional reading:
    • R. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (https://people.csail.mit.edu/rivest/Rsapaper.pdf) (1978)
20. Diffie-Hellman key exchange (https:../../wiki/images/8/83/CO487-2016-slides20.pdf) (March 2). Optional reading:
    • W. Diffie and M. Hellman, New Directions in Cryptography (https://ee.stanford.edu/%7Ehellman/publications/24.pdf) (1976)
21. Security definitions for public-key cryptography (https:../../wiki/images/2/23/CO487-2016-slides21.pdf) (March 4)
22. Semantic security (https:../../wiki/images/2/2b/CO487-2016-slides22.pdf) (March 7)
23. Probabilistic encryption (https:../../wiki/images/1/1c/CO487-2016-slides23.pdf) (March 9)
24. Hybrid encryption (https:../../wiki/images/a/af/CO487-2016-slides24.pdf) (March 11)
25. Elliptic curve cryptography (https:../../wiki/images/1/1a/CO487-2016-slides25.pdf) (March 14)
26. Digital signatures (https:../../wiki/images/a/ab/CO487-2016-slides26.pdf) (March 16)
27. Side-channel attacks (https:../../wiki/images/8/8e/CO487-2016-slides27.pdf) (March 18)
28. Bitcoin (https:../../wiki/images/7/71/CO487-2016-slides28.pdf) (March 21). Optional reading:
    • S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (https://bitcoin.org/bitcoin.pdf) (2008)
29. Quantum computation (https:../../wiki/images/b/b2/CO487-2016-slides29.pdf) (March 23)
30. Quantum key distribution (https:../../wiki/images/4/49/CO487-2016-slides30.pdf) (March 28)
31. Hardware implementations (https:../../wiki/images/c/c6/CO487-2016-slides31.pdf) (March 30)
32. Post-quantum cryptography (April 1). No slides, but here are some useful links:
    • S. Galbraith, ECDLP can be solved in 24-th root time (https://ellipticnews.wordpress.com/2016/03/31/ecdlp-can-be-solved-in-24-th-root-time/) (2016)
    • NIST IR 8105 (https://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf)
    • NIST presentation from PQCrypto 2016 (https://pqcrypto2016.jp/data/pqc2016_nist_announcement.pdf)
    • NSA Suite B Cryptography (https://www.nsa.gov/ia/programs/suiteb_cryptography/)
    • N. Koblitz and A. Menezes, A riddle wrapped in an Enigma (https://eprint.iacr.org/2015/1018.pdf) (2015)
33. Exam review (https:../../wiki/images/a/a4/CO487-2016-slides32.pdf) (April 4)