Pre-Class Assignments
Math 202 Cryptography, Fall 2022
This page uses MathJax to display mathematical notation, so please let me know if any part isn't clear.
All section numbers refer to Understanding Cryptography: A Textbook for Students and Practitioners by Paar & Pelzl.
There are a few other resources that you might find useful for reference, including
- The textbook website
- Christof Paar's YouTube channel of lectures for the text
Be sure to check back, because this page will be updated often during the semester.
Week 1: Due Monday August 29 @ midnight
Welcome to Cryptography!
Modular arithmetic
Encoding messages as numeric variables
To Read
- Chapter 1: pp 1 - 23, although you can demphasize Section 1.4.2 Integer Rings
Optional videos from Fall 2020
- Week 1: Overview - Echo360 video, link in onCourse
- Week 1: Modular Arithmetic - Echo360 video, link in onCourse
No questions to submit for the first week.
If you didn't see this before Tuesday's class, be sure to complete before Thursday, and remember to fill out the Background Questionnaire linked from onCourse.
Week 2: Due Monday September 5 @ midnight
One time pads & stream ciphers
Introduction to AES
To Read
- Chapter 2: through Section 2.2.2 The One-Time Pad, pp 29 - 38
- Chapter 3: Section 3.1, pp 55 - 58, and Section 3.8 & 3.9, pp 81 - 82
- Chapter 4: Sections 4.1 - 4.2, pp 87 - 90 (Be sure to look at Figure 4.2 on pg 91, too)
Optional videos from Fall 2020
- Week 2: Encoding messages as numeric values - Echo360 video, link in onCourse
- Week 2: A few notes on stream ciphers - Echo360 video, link in onCourse
- Week 2: Note on the size of the key space - Echo360 video, link in onCourse
- AES explained as an interactive HTML5 animation
Pre-Class Questions
- Encrypt the plaintext x = 1101 using a stream cipher with key stream s = 0111.
- Why are one-time pads unconditionally secure?
- Does an affine cipher perfom confusion? Why or why not?
- What is the purpose of diffusion in encryption algorithm?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 3: Due Monday September 12 @ midnight
AES and finite fields
To Read
- Chapter 4: skim Sections 4.3 - 4.5, pp 90 - 115. Don't get boggged down in too many of the details in these Sections. We'll hit the high points we need in class.
- Chapter 4: Sections 4.6 - 4. 8, pp 115 - 117
Optional videos from Fall 2020
- For general background, History/Intro to AES by Christof Paar
- AES explained as an interactive HTML5 animation
- Week 3: Introduction to AES and finite fields - Echo360 video, link in onCourse
Pre-Class Questions
- Let f(x)=x 2 + x + 1 and g(x)=x+1 be polynomials in ℤ2[x]. What is f(x) ∙ g(x) ?
- In which layer(s) of AES does confusion occur? Why?
- Why does diffusion occur in the ShiftRows sublayer of AES?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 4: Due Monday September 19 @ midnight
Principles of Public Key Cryptography
RSA
To Read
- Chapter 6: Sections 6.1-6.2, pp 149 - 157
- Chapter 7: Sections 7.1-7.3, pp 173 - 179
Optional videos from Fall 2020
- Asymmetric encryption - Simply explained gives a nice introductory motivation
- How RSA works by F5 DevCentral
Note that what they call the "totient of n" is what we've called the Euler phi function \( \phi(n) \).
Pre-Class Questions
- Is nonrepudiation possible with a symmetric cipher? Explain.
- Give a real-world example where nonrepudiation is desirable.
- What is the hard math problem underlying the security of RSA?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 5: Due Monday September 26 @ midnight
RSA & the Euclidean Algorithm
To Read
- Chapter 7: Section 7.4, pp 179 - 182
Optional videos from Fall 2020
- Extended Euclidean Algorithm Example by John Bowers (I like this better than the text's explanation)
- The Euclidean Algorithm: How and Why, Visually by Proof of Concept gives a visual justification for why the Euclidean Algorithm works
No questions to submit this week since you shoud be prepping for Exam 1.
Week 6: Due Monday October 3 @ midnight
Digital signatures
Hash functions
To Read
- Mathematicians Will Never Stop Proving the Prime Number Theorem from Quanta Magazine
- Chapter 10: Sections 10.1-10.2, pp 259 - 270
- Chapter 11: Section 11.1, pp 293 - 296, and the list of Properties of Hash Functions in the box at the end of Section 11.2, pg 303
Optional videos from Fall 2020
- Introduction to Digital Signatures
by Jeff Suzuki
The process of RSA signatures is very clear, but one slightly weird thing in the video is that it has Bob specifying the message that Alice signs, rather than Alice signing a message that they want to send to Bob.
Pre-Class Questions
- Based on the Prime Number Theorem, approximately how many primes are less than 21024?
- What is the purpose of a digital signature?
- Suppose Alice and Bob want to exchange an AES key to use for a secure conversation.
- If Alice generates the AES key, whose RSA credentials will they use to encrypt the key to send to Bob?
- If Alice wants to sign the message containing the encrypted key, whose RSA credentials will they use to sign the message?
Week 7: No assignment due
No class meetings this week due to Fall Break and MAP Day.
Week 8: Due Monday October 17 @ midnight
Diffie-Hellman Key Exchange
To Read
- Chapter 8: Section 8.1, pp 205 - 208
Optional videos from Fall 2020
- Public key cryptography - Diffie-Hellman Key Exchange by Art of the Problem
- Hashing Algorithms and Security by Computerphile
Pre-Class Questions
- What's an advantage of Diffie-Hellman key exchange over using RSA to exchange a key for AES?
- Suppose Alice and Bob agree on values \(p=37\) and \( \alpha=5 \) for Diffie-Hellman.
- If Alice picks a private key of a=9, what will be their public key A?
- If Bob picks a private key of b=14, what will be their public key B?
- What will be the shared key?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 9: Due Monday October 24 @ midnight
The Discrete Log Problem
To Read
- Chapter 8: Skim Section 8.2, pp 208 - 216. There's a lot here, so don't get too bogged down. We'll talk about the major results we need during class.
Pre-Class Questions
- Solve the discrete log problem \( 3^x \equiv 26 \mod 31 \)
- What is ord(26) in \( \mathbb{Z}_{31}^* \)?
- Could you use your answer to #1 to figure out the answer to #2? Hint: Review last week's in-class work.
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 10: Due Monday October 31 @ midnight
The Digital Signature Algorithm
To Read
- Chapter 10: Section 10.4, pp. 277 - 282
Optional videos from Fall 2020
- Week 10: The Digital Signature Algorithm - Echo360 video, link in onCourse
Pre-Class Questions
- What is the hard math problem underlying the Digital Signature Algorithm? Where does this problem appear?
- What are the possible lengths of the message x that can be securely signed by DSA?
- What is the purpose of the ephemeral key kE used in DSA?
- The text suggests using SHA-1 for the hash in DSA. Do a little research. Is this hash function still recommended?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 11: Due Monday November 7 @ midnight
MITM attacks
Implications of Quantum Computing
To Read
- Chapter 13: Section 13.3, pp 342 - 350
- What Makes Quantum Computing So Hard to Explain? from Quanta Magazine
- Post-quantum encryption contender is taken out by single-core PC and 1 hour from Arstechnica
No questions to submit this week since you should be prepping for Exam 2.
Week 12: Due Monday November 14 @ midnight
Counter modes
Transport Layer Security
To Read
- Chapter 5: Section 5.1.2, pp 128 - 130 (the videos below will help, too)
- For more details on Transport Layer Security specifically:
- What is Transport Layer Security (TLS)? (Cloudflare)
- What Happens in a TLS Handshake? | SSL Handshake (Cloudflare)
To Watch
- Cipher Block Chaining Mode (Udacity)
- Counter Mode (Udacity)
I think this is a super clever, simple idea that uses a block cipher like in AES to create the key used in a stream cipher
No questions to submit this week.
Week 13: Due Monday November 21 @ midnight
What is a blockchain?
Structure of a Bitcoin transaction
To Read
- Types of Blockchains: PoW, PoS, and Private by Cryptopedia
- This Is What Happens When Bitcoin Miners Take Over Your Town from ProPublica
To Watch
- But how does bitcoin actually work? by 3Blue1Brown
No questions to submit this week.