Pre-Class Assignments, Math 202 Cryptography, Fall 2020

This page uses MathJax to display mathematical notation, so please let me know if any part isn't clear.

Be sure to check back, because this page will be updated often during the semester.

All chapter references are to the text Understanding Cryptography by Paar and Pelzl.

For Sunday August 23

Modular arithmetic and affine ciphers

To Read

Chapter 1, pp 1 - 23, although you can demphasize Section 1.4.2 Integer Rings

To Watch

Links in "Echo360 and other course videos" topic in onCourse. ~13 minutes total

Week 1: Overview
Week 1: Modular Arithmetic

Pre-Class Questions

No questions to turn in for the first week.
If you didn't see this before Monday's class, be sure to complete before Wednesday.

Due Sunday August 30 @ midnight

One-time pads

To Read

Chapter 2: through Section 2.2.2 The One-Time Pad, pp 29 - 38

To Watch

Links in "Echo360 and other course videos" topic in onCourse. ~14 minutes total

Week 2: Encoding messages as numeric values
Week 2: A few notes on stream ciphers
Week 2: Note on the size of the key space

To Download

Follow the instructions on the main course webpage to download Mathematica to your own computer.
Download the notebook aug31.nb and open it in Mathematica. Follow the instructions to work through the notebook. You'll use this to answer the last two Pre-Class Questions.
In case Mathematica is being tempermental for you, here's a pdf of the notebook so that you can at least take a look at the content.

Pre-Class Questions

Encrypt the plaintext x = 1101 using a stream cipher with key stream s = 0111.
Why are one-time pads unconditionally secure?
Use the Mathematica notebook to encrypt the message "Verbing weirds language" using a Caesar cipher with a shift of k = 17. (You should remove any spaces). What is the ciphertext?
Use the Mathematica notebook to decrypt the message "CNAVXVSZXFGECBLXGEDXOBISNAXABUNPAIPAVPYSBEUFIIPVBOLPAISBD" using an affine cipher with a key of k= = (23, 13). What is the plaintext?

Due Sunday September 6 @ midnight

AES and finite fields

To Read

Chapter 3: Section 3.1, pp 55 - 58, and Section 3.8 & 3.9, pp 81 - 82
Chapter 4: Sections 4.1 - 4.3, pp 87 - 99
Don't get boggged down in the notation in Section 4.3. We'll hit the high points we need in the videos and in class.

To Watch

Links in "Echo360 and other course videos" topic in onCourse

For general background, History/Intro to AES (~2:00 - ~18:00) by Christof Paar
AES explained as a Flash animation (~5 minutes)
Week 3: Clarification on Problem 3.12 from Problem Set #2
Week 3: GCDs and multiplicative inverses mod m
Week 3: Introduction to AES and finite fields

Pre-Class Questions

Does an affine cipher perfom confusion? Why or why not?
What is the purpose of diffusion in encryption algorithm?
Let f(x)=x² + 1 and g(x)=x+1 be polynomials in ℤ₂[x]. What is f(x) ∙ g(x) ?

Due Sunday September 13 @ midnight

AES Data path and key path

To Read

Chapter 4: finish the chapter, pp 99 - 117
A stick figure guide to AES (for reference)

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Multiplying matrices (for reference, if needed)
AES explained as a Flash animation (re-watch)
Week 4: Details of AES

Pre-Class Questions

Perform the following matrix multiplication and addition: \[ \left( \begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} \right) \cdot \left( \begin{matrix} 0 \\ 1 \\ 1 \end{matrix} \right) + \left( \begin{matrix} 1 \\ 0 \\ 0 \end{matrix} \right) \mod \ 2 \]
In which layer(s) of AES does confusion occur? Why?
In which layer(s) of AES does confusion NOT occur? Why?

Due Sunday September 20 @ midnight

Public key cryptography and RSA

To Read

Chapter 6: Sections 6.1-6.3, pp 149 - 157
Chapter 7: Sections 7.1-7.3, pp 173 - 179

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Asymmetric encryption - Simply explained gives a nice introductory motivation (~5 minutes)
How RSA works by F5 DevCentral (~ 14 minutes)
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?
For this question, we'll use the notation from the text for the RSA keys.
Bob publishes the public key k_pub=(n,e)=(25021,3).
1. If Alice uses Bob's public key to encrypt the message x=1315, what is the ciphertext y?
2. Bob's private key is k_pr=d=16467. Decrypt the ciphertext y from part (a) and verify that you obtain the correct plaintext.

Due Sunday September 27 @ midnight

The Euclidean Algorithm and Fast Exponentiation

To Read

Chapter 7: Section 7.4, pp 179 - 182

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Extended Euclidean Algorithm Example (I like this better than the text's explanation)

No questions to submit today since you shoud be prepping for Exam 1.

Due Sunday October 4 @ midnight

The Prime Number Theorem and RSA Digital Signatures

To Read

Mathematicians Will Never Stop Proving the Prime Number Theorem from Quanta Magazine
Chapter 10: Sections 10.1-10.2, pp 259 - 270

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Introduction to Digital Signatures by Jeff Suzuki (~5 minutes)
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 2¹⁰²⁴?
What is the purpose of a digital signature?
Suppose Alice and Bob want to exchange an AES key to use for a secure conversation.
1. If Alice generates the AES key, whose RSA credentials will they use to encrypt the key to send to Bob?
2. If Alice wants to sign the message containing the encrypted key, whose RSA credentials will they use to sign the message?

Due Sunday October 11 @ midnight

Diffie-Hellman Key Exchange and Hash Functions

To Read

Chapter 8: Section 8.1, pp 205 - 208
Chapter 11: Section 11.1, pp 293 - 296, and the list of Properties of Hash Functions at the end of Section 11.2, pg 303

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Public key cryptography - Diffie-Hellman Key Exchange by Art of the Problem (~8 minutes)
Hashing Algorithms and Security by Computerphile (~7 minutes)

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.
1. If Alice picks a private key of a=9, what will be their public key A?
2. If Bob picks a private key of b=14, what will be their public key B?
3. What will be the shared key?
What is one purpose of a hash function?

Due Sunday October 18 @ midnight

The Discrete Log Problem

To Read

Re-read the Tutorial Problems from last week to remind yourself of the terminology introduced there.
Chapter 8: Skim Section 8.2. 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}^* \)?
Explain the connection between questions 1 & 2.

Due Sunday October 25 @ midnight

Elgamal Digital Signatures

To Read

Section 10.3: The Elgamal Digitial Signature Scheme. Focus on 10.3.1 and 10.3.2, pp 270 - 273

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Week 10: Elgamal digital signatures

Pre-Class Questions

What is the hard math problem underlying Elgamal digital signatures? Where does this problem appear?
What is the purpose of the ephemeral key k_E used in an Elgamal digital signature?
If Bob receives a message signed with Elgamal, (x,(r,s)) from Alice, what values does Bob need to verify the signature?

Due Sunday November 1 @ midnight

The Digital Signature Algorithm

To Read

Chapter 10: Section 10.4, pp. 277 - 284

To Watch

Links in "Echo360 and other course videos" topic in onCourse

Week 11: The Digital Signature Algorithm

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? How does this compare to Elgamal signatures?
The text suggests using SHA-1 for the hash in DSA. Do a little research. Is this hash function still recommended?

Due Sunday November 8 @ midnight

Counter Modes, M-I-T-M Attacks, and TLS

To Read

Chapter 13: Section 13.3, pp 342 - 349
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

Links in "Echo360 and other course videos" topic in onCourse

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

Pre-Class Questions

None for today since I was so deliquent in getting this posted.

Due Sunday November 15 @ midnight

Blockchain and Bitcoin

To Read

You'll get more out of these readings if you've watched the videos first.

This Is What Happens When Bitcoin Miners Take Over Your Town (Politico)
This is kind of long, so feel free to skim. It's worthwhile, though, to see some real-life consequences.
Cryptocurrency miners go to federal court to block 'crippling' electric rate hike (KUOW)
Things Blockchain Is Supposed to Revolutionize (Slate)

To Watch

Links in "Echo360 and other course videos" topic in onCourse

But how does bitcoin actually work? (3Blue1Brown)
How secure is 256 bit security? (3Blue1Brown)
Smart contracts (Simply Explained)
The History of Ethereum (Blockgeeks)

Pre-Class Questions

What is the cryptographic problem that makes Bitcoin mining difficult?
Explain one significant difference between Bitcoin and Ethereum.
Look for a non-cryptocurrency proposal for using blockchain technology. What's the purpose of blockchain for this application?