MCS 425: Codes and Cryptography (Fall 2021)

Basic Information

• Lectures: Mon-Wed-Fri 12:00-12:50pm, Taft Hall 207
• Instructor: Yu Cheng
• Email: yucheng2@uic.edu
• Office Hours: Wed 3:30-4:30pm in SEO 416 and on Zoom (or by appointment).
• TA/Grader:
  • Truong Vu (tvu25@uic.ed). Office Hours: Fri 5-6pm on Zoom.
• Textbook (Required): Introduction to Cryptography with Coding Theory, Second Edition. Wade Trappe and Lawrence Washington
• Fun Reading: Introduction to Modern Cryptography, Second Edition, Jonathan Katz and Yehuda Lindell

Homeworks

Warning: the following assignments and due dates are from the past. If you are taking MCS 425 this semester, please refer to the current course webpage.

• Homework 1, due at 12pm on Sep 15 (Wed).
• Homework 2, due at 12pm on Oct 1 (Fri).
• Homework 3, due at 12pm on Oct 11 (Mon).
• Homework 4, due at 12pm on Nov 1 (Mon).
• Homework 5, due at 12pm on Nov 22 (Mon).

Course Project

• Project guidelines.
• Important dates:
• Oct 20: Decide on teams and topics.
• Nov 15 - Dec 1: Presentations.
• Dec 5: Project report due.

Weekly Schedule

Hand-written lecture notes can be found on Fall 2020's course webpage.


• Week 1-2 (Aug 23), Classical Ciphers:
• Introduction to the Course
• Possible Attacks (Section 1.1.1), Shift Ciphers (Section 2.1), Affine Ciphers (Section 2.2) (Lecture 2)
• Vigenère Cipher (Section 2.3) (Lecture 3, Lecture 4)
• Demo for Using/Attacking Classical Ciphers.
• Week 3-4 (Sep 6), Number Theory:
• Basic Number Theory (Section 3.1) (Lecture 5)
• Extended Euclidean Algorithm (Section 3.2) (Lecture 6)
• Modular Arithmetic, Multiplicative Inverse (Section 3.3) (Lecture 8)
• Fast Modular Exponentiation (Section 3.5) (Lecture 9)
• Euler’s Theorem (Section 3.6) (Lecture 10)
• Implementing Extended Euclidean and Fast Exponentiation (Lecture 11)
• Week 5-6 (Sep 20), Public Key Encryption:
• RSA Algorithm (Section 6.1) (Lecture 12)
• Primality Testing (Section 6.3) (Lecture 13)
• Factoring (Section 6.4) (Lecture 14)
• Discrete Logarithms (Section 7.1), Index Calculus (Section 7.2) (Lecture 15)
• Diffie-Hellman Key Exchange (Section 7.4), Bit Commitment (Section 7.3) (Lecture 16)
• Midterm Review, ElGamal Encryption (Section 7.5) (Lecture 17)
• Computing Discrete Logs (Section 7.2) (Lecture 18)
• Week 7-8 (Oct 4), Hash Functions and Digital Signatures:
• Hash Functions (Section 8.1), (Lecture 19)
• RSA Signatures (Section 9.1), Hashing and Signing (Section 9.3) (Lecture 20)
• Birthday Attacks (Section 8.4, Section 9.4) (Lecture 21)
• Exercises (Lecture 22)
* Midterm Exam (in person): Oct 13th (Wed), 12:00pm - 12:50pm.
• Man-in-the-Middle Attack (Section 10.1), Public Key Infrastructures (Section 10.4) (Lecture 24)
• Week 9 (Oct 18), Secret Sharing:
• Secret Splitting (Section 12.1), Threshold Schemes (Section 12.2) (Lecture 25)
• Zero-Knowledge Proof (Section 14.1) (Lecture 26)
• Week 10 (Oct 25), Information Theory:
• Probability Review (Section 15.1) (Lecture 27)
• Entropy (Section 15.2) (Lecture 28 and Lecture 29)
• Huffman Codes (Section 15.3) (Lecture 30)
• Week 11-12 (Nov 1), Error Correcting Codes:
• Introduction (Section 18.1) (Lecture 31)
• Codewords, Minimum Distance (Section 18.2) (Lecture 32)
• Bounds on General Codes (Section 18.3) (Lecture 33)
• Linear Codes (Section 18.4) (Lecture 34 and Lecture 35)
• Secure Multi-Party Computation (Lecture 36)
• Week 13-15 (Nov 15), Project Presentations:
• Project Presentations (Lecture 37-40)
• Final Exam Review (Lecture 41)
• Project Presentations (Lecture 43-45)
* Final Exam (in person): Dec 7th (Tue), 8:30am - 10am.

Grading

• Homeworks (30%): We have 5 homeworks. You are encouraged to discuss with other students, but you must acknowledge who you worked with and write up your solutions independently. Your lowest HW score will be dropped (and the remaining HW score will scale proportionally). Late homeworks are not accepted (exceptions with good reasons may be requested in advance).
• Midterm (20%): Oct 13th (Wed), 12:00pm - 12:50pm.
• Final (30%): Dec 7th (Tue), 8:30am - 10am.
• Course project (20%): Explore in depth a topic that we did not cover in class. Write a project report and prepare a presentation.
• Bonus (10%): There are bonus points for some homework questions and the best project reports.

Disability Policies

Religious Holidays