Test make-ups: You have an opportunity to improve your grade on Test 1 and Test 2. Here’s how it works. For each test, you may retake one of the 10 point problems in Part B that you attempted. That means solving a similar problem. Your retake score replaces your original score on that problem, so you can completely make up the lost points (up to the full 10 points).

• If you got 7 or higher on your problem, you will do a written replacement problem. The written retakes are posted on canvas.
• If you got 6 or lower, you will schedule to meet in person for a retake. Use the calendar link on the canvas main page for appointments (15 minute slot).

Deadlines: Test 1 make-ups must be done by the end of October (Friday, October 30th). Test 2 make-up deadline: TBA.

Relevant Textbook Sections:

5.6 (Elliptic Curve Diffie-Hellman), 5.7 (Elliptic Curve El Gamal), including 5.7.1 (Placing a message on a curve) and 5.7.2 (Square roots modulo $p$).

To Do:

1. An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: best hallowe’en costume? You will encrypt your answer. Here are the steps:
   1. Keep notes as you do all this. Here are the EC El Gamal Tools you can use to do this.
   2. As a group, we will all use the elliptic curve $E$ given by $y^2 = x^3 + x^2 + x + 1$ over the finite field of $p = 123456789101234567891027$ elements. We will furthermore use the point P = E([3,11655832467975276266127,1]) on $E$, which has order $61728394550949287614731$.
   3. You should create a private and public key pair based on the information given above. Publish your public key on the #public-keys channel on discord (note: this is a point $(x,y)$ on the curve). Keep your private key in a text document somewhere to use for decrypting later.
   4. You should answer the question (Best hallowe’en costume?) with a word of 6 or fewer letters. Translate this to an integer (Text to Integer tool as usual) and add three digits of “padding” “000” at the end.
   5. Turn your message into a point on the elliptic curve as described in class. This might mean updating the padding to “001”, “002” etc. until it works. For this step, you need to take modular square roots. The command is sqrt. For example, sqrt(Mod(2,7)) will give you the square root of $2$ modulo $7$ (which is $3$). If it returns something with the string ‘sqrt’ in it, that means it failed (no square root), e.g. sqrt(Mod(3,7)) will just return sqrt3 — that means no square root.
   6. You should then obtain the most recent public key on the #public-keys channel, and encrypt your message (turned into a point on the curve) to that public key. Post your encryption to the #ciphertexts channel, @mentioning the owner of the public key it is encrypted to.
   7. You should then keep an eye on the channel and when someone encrypts a message to your public key (they should @mention you), you should decrypt it and announce what the plaintext was, @mentioning them back.
   8. When someone decrypts your message, you should give them a thumbs up to let them know it’s right (or let them know if it isn’t).
   9. Hand in your notes from this exercise to the canvas dropbox.
   10. Challenge for fun: break someone else’s message! Hint: factor the order of $P$.
2. Today we introduced Pollard’s $p-1$ algorithm. As a recap, to factor $n$, we take some $a$ modulo $n$, and create a chain $a, a^2, a^{3!}, a^{4!}$, etc. At each point, we take $\gcd(a^{B!}-1,n)$, hoping to get a nontrivial factor. We didn’t explain why it works. Can you reason out why it might work, at least heuristically?
3. Write a small Sage for loop (use the Sage Sandbox) to implement Pollard $p-1$ factoring. Use it to factor $n=16637$. Some hints so you don’t get stuck:
   1. remember to make $a$ into a value modulo $n$, for example with a = Mod(2,n) (it will actually work with integers but they grow so fast it isn’t efficient).
   2. when you want to take a gcd of a value mod $n$, you need to make it an integer again by putting a ZZ around it, so like gcd(ZZ(a)-1,n).
   3. start your loop at power $2$ (squaring), not zero.
4. With perfect timing, this discovery about the history of the NIST elliptic curves was released today! https://www.anthropic.com/research/ecdsa-curve-origins