Notice: First test will be on Wednesday, September 18th, 2024
On canvas (Studio Tab), there’s a video called “Diffie-Hellman Key Exchange Exercise” (~ 16 min) [ EDIT: link here ], which is a tutorial to accompany the following exercise. In the video, I demonstrate how to use the course website tools (on this website) to put your Diffie-Hellman public key up on the discord server, and send a message to someone there. Here are the written notes from that video.
Here are the full written instructions: you will perform a Diffie-Hellman Key Exchange in order to send a message to someone. Big picture: you’ll do a Diffie-Hellman Key Exchange to make a shared secret and then use that shared secret as a key for a very simple encryption (a sort of Caesar Cipher or One-Time Pad):
Create a secret message which is at most 6 characters long. It should answer “Why CU?” Please don’t make it longer or this exercise won’t work.
Turn it into an integer using the Text to Integer tool. (This turns it into an integer by writing the letters in ASCII and making an integer base 255 with those digits. There’s an Integer-to-Text tool on the same page to undo this process.)
We will use prime $p=10^{15}+37$, and its primitive root $g=2$. The first box in the Diffie-Hellman Tools page will initialize this modular ring for you.
Use the Diffie-Hellman Tools (second box) to find a random secret a. We’ll call this your secret key. Keep it secret and SAVE IT, maybe in your underwear drawer. (Joking! — actually safer if you copy it into a text file on your computer, because if you write it by hand you’ll make an error.)
Compute $g^a$ using the Diffie-Hellman Tools third box appropriately (no need to do this by hand!) We’ll call this your public key.
Announce your public key on discord #public-keys. Be sure to explain this is your “Diffie-Hellman Public Key” (there will be other types later).
Find someone else’s public key ($g^b$) on discord (the most recent public key on the #public-keys channel is best, so everyone gets to have part of the fun). Let’s call that other person Bob. Use it to generate your shared secret ($g^{ab}$) with Bob (you’ll need your secret key for this). Again, you can use the third box in the Diffie-Hellman Tools page to do the computations (no need to work by hand).
Add the shared secret to your message mod p. Announce the result on discord in the #ciphertexts channel as the secret message for Bob. Include your public key for them, because they will need it. You post might look like “My Diffie-Hellman message for @soandso is X.”
When someone sends you a secret message, figure out how to decrypt it and announce the result (so you can check it worked!). You may need to use the Diffie-Hellman Tools and the Text to Integer converter.
With what time remains (if any), watch my video explaining the Euclidean Algorithm (14 minutes).
Compute the gcd of 135 and 170. Show all the steps of the algorithm, as in the video.
Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error.
Using the previous problem, tell me the inverse of $7$ modulo $15$ and the inverse of $15$ modulo $7$. (This should require no computation, just look at the previous problem and have an aha moment!)