On the archive page above, you can look at test solutions. Please make sure your grades are correct.
Retakes: You will have an opportunity to improve your grade on the first test. Here’s how it works. You may retake one of the 10 point problems in Part B that you attempted. That means solving a similar problem. The written retakes will be posted on canvas as soon as I can manage.
If you got 7 or higher on your problem, you will do a written replacement problem (I will post these).
If you got 6 or lower, you will schedule to meet in person for a retake. If you want to do this, use the calendar link on the canvas main page for appointments (15 minute slot).
To Know: If you’re interested in the runtime of the Index Calculus, I have more detail in my overleaf text. Additionally, here are some course notes that cover it in more detail (from Andrew Sutherland’s MIT course on elliptic curves). This may be an interesting topic for a graduate student project: runtime for index calculus and/or index calculus improvements mod p and/or in other finite fields.
Solve the discrete logarithm problem for $p=131$, $g=2$, $h=17$, using the Index Calculus method. You may use the Index Calculus Tools and Sage’s modular arithmetic and plain arithmetic computations to avoid by-hand computations, but please solve the linear system by hand (i.e. choosing which equations to subtract from which etc.). Note: this is a randomized algorithm, so you will get different relations than someone else, or next time you run the tool. If you are not finding a very nice linear system, just try to get some more relations and pick simple manageable ones.
To Do: El Gamal Encryption Chain! We will use the same prime and generator as we did for Diffie-Hellman. This is set up on that tools page. Do the following:
If you have not already made a public key for Diffie-Hellman Key Exchange, then set up a Diffie-Hellman private and public key for yourself. Publish the public key on the “#public-keys” channel on discord. Note your public and private key down on paper for safekeeping. If you’ve lost your private key, delete your old key and do this again.
Choose an at most 6 letter word as a message. It should be a polite, recognizable english word, so the decrypter will be able to tell they’ve done this correctly. It should answer, in some fashion, the question “Best food?” Turn it into an integer using the Text to Integer tool. Make notes on paper.
Find the Diffie-Hellman public key immediately before yours in the #public-keys channel (if this doesn’t exist, use the most recent public key), and use that public key to encrypt your four-letter word to that person. Keep notes on paper of the key steps.
Post your ciphertexts publicly for that person on the channel. Use @username. It should consists of two numbers, which we called (K,c).
When you receive a message from someone on the channel, decrypt it. Hopefully it is an english word. If it is, yay! Respond on the channel to that person to tell them the decryption you got. Keep notes on paper of the key steps.
For the canvas submission, show your notes from this work. If you don’t get someone sending you a message in time, that’s ok, but keep an eye out and do the decryption stage when possible.
Challenges for fun:
Break someone else’s message! Use any algorithm. Let me know if you succeed on discord!
Get your friend to send two messages to the same person using the same ephemeral key. Break this!