To Know: We’ll soon finish elliptic curves, isogenies and lattices, so I’ll be putting together an assessment soon. Next up: quantum key exchange, quantum computers and quantum cryptanalysis.

To Do: A Ring-LWE ciphertext chain! You may want to review the course video on canvas and the class notes under “History“. Here’s what you’ll need:

Our general setup with be the prime p = 100000000003 and n=8. We will use k=100. (This will allow us enough room for a 3-letter word in ASCII as the message m.)

At the Ring-LWE Tools page you’ll see how to initialize the polynomial ring, and you’ll have two functions that generate short and random elements. In our case, “short” means coefficients from {0,1,-1}.

First, generate your own private/public key pair and post the public key (a,b) on the discord #ciphertexts channel. Keep your secret key for later (e.g. in a text file). Important note: to make it easier on everyone, surround your polynomials with backticks ` when pasting into discord, and it will post it verbatim, i.e. not interpret the asterisks as emphasis etc. This will make cutting-and-pasting into Sage easier.

Next, choose your favourite three-letter word and put it into ASCII (Here’s the tool). This is your message. Now, encrypt your message to the most recent unused public key on the #ciphertexts channel. Post your message (v,w) on the #ciphertexts channel and mention the appropriate person.

Wait until someone sends you a message. When this happens, decrypt it using your secret key (here’s the ascii to letters tool), and announce their favourite 3-letter word on #ciphertexts, mentioning them so they can confirm.

Post your record of the events/computations to the canvas dropbox.

To Do: By hand, find a reduced basis and a shortest nonzero vector in the lattice generated by (58,19) and (168,55). (We covered this in Monday’s class; also see section 17.2 in text, available on canvas.) Hand in on canvas.

Quick announcement: since students asked, I produced solutions to the El Gamal Ciphertext Chain task (this is a video available on canvas) and to the Break EC signatures when k is reused task.

CU Boulder is encouraging everyone in our community to vote. All the information you need is here, at this CU Boulder website: Your Vote, Your Voice.

There will be no daily task homework due Wednesday.

To Know: Don’t forget your re-do problems for module 1 and 2 (optional); see canvas.

To Know: I’ve been asked for solutions to the last two daily post tasks and I’ll make some videos about that over the weekend.

To Do: Watch this YouTube Video. This is my friend, mentor and collaborator, Dr. Kristin Lauter, from Microsoft Research. She’s giving a fairly generally accessible talk about a lot of different aspects of modern cryptography. She has a lot of perspective on this because she’s in industry — she does the underlying math and the deployment and implementation. She is one of the first people to propose using isogeny graphs in cryptography, for hash functions. You’ll find lots of interesting stuff in here about practicalities and cryptography in the real world, like the future of cryptography after quantum computing. It’s a great overview that should be just perfect for this moment in the course, where we’ve done the classical and pre-quantum crypto and are ready to dive into the newest of the new.

To Do: Just hand in some reactions to the video: What questions did you have? What did you learn? 3-6 sentences is fine.

To Know: I’ve put together a set of links to the most recent cryptography resources (for cutting edge research) since it was requested in class. Check back to the “Resources” tab soon. One interesting link is the article “The Uneasy Relationship between Mathematics and Cryptography”, which is one person’s experience of the last few decades and some of the conflict and disagreements in the field, among other things.

Totally optional extra resources: Here’s a YouTube Video (20 mins) that introduces isogeny-based cryptography, but with an emphasis on SIDH (not CSIDH), which is an earlier variant. It’s aimed at an undergraduate audience that knows what groups are. It has some review of the basics of elliptic curves and of Diffie-Hellman Key Exchange, so it may be of some interest for that reason too. But this one is totally optional.

To Know: Re-Do problems (if desired) are on canvas for Module 1 and 2. Due Monday.

To Do: In the EC Digital Signature algorithm we studied, I mentioned that if k is re-used, there’s an attack. Suppose you see Alice sign two messages: (m1,R,s1) and (m2,R,s2). Because R is the same, you know she used the same k. Explain how to obtain k. Then explain how to use that to obtain her secret key. (Note: if it helps, you can assume the order of P is prime, at first.) Hand in on canvas.

To Know: Reminder that there was a mistake on the Module 3 Assessment and because of the mistake I gave everyone until Wednesday. It had to do with Problem 4; if you did it already and want to re-do it, you can resubmit just that problem on canvas, or resubmit everything. It shows previous and current submissions. Please be clear, whatever you do.

To Know: There was also a typo on the last problem of the ReDo problems for Modules 1 and 2; this has also been updated on canvas, and I’ve set the deadline back until Monday. Phew!

My apologies for both of those errors.

To Do: An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: what do you miss during the pandemic? You will encrypt your answer. Here are the steps:

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. Note that p is 3 mod 4. We will furthermore use the point P = [3,11655832467975276266127] on E, which has order 61728394550949287614731.

You should create a private and public key pair based on the information given above. Publish your public key on the #ciphertexts channel on discord. Keep your private key in a text document somewhere to use for decrypting later.

You should answer the question (What do you miss during the pandemic?) with a word of 7 or fewer letters. Translate this into ASCII, and add two digits of “padding” as explained in class.

Turn your message into a point on the elliptic curve as described in class.

You should then obtain the most recent public key on the channel, and encrypt your ASCII message (turned into a point on the curve) to that public key. Post your encryption to the channel, mentioning the owner of the public key it is encrypted to.

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 that person misses during the pandemic, mentioning them.

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).

Hand in your notes from this exercise to the canvas dropbox.

To Know: I’ve put another chapter on canvas — the one with elliptic curves (and removed chapter 2)

To Know: Module 3 is due Monday.

To Know: Module make-up is due Friday the 30th. Please see the replacement problems on canvas.

To Do: Determine P^1(F_5). That is, just like the example from class today where I did P^1(F_3). List out all the elements, as I did in that example. Please give all the equivalent ways to write each element (just as I did in class). Class notes are available under “History” and the video is on canvas. Hand it in on canvas.

To Know: I’ve put up re-do problems. I’ve added a few new ones. You can do 2 from Module 1 and 2 from Module 2. You choose. If you want one that’s not there, let me know. It’s due the Friday after Module 3.

Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! You’ll notice I modified the code so that it will catch and report on the errors it encounters. Use the result to factor n (that is, take the gcd of the non-invertible residue with n to get a non-trivial factor).

Now do it again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.

Now try modifying one of the middle digits of n, and see how long it takes. Factor n.

Try modifying one of the digits a couple more times and see how long it takes. Factor n.

Report to canvas on how long it took (what multiple of P) on different curves and points, and different n. Explain why you think it was fast sometimes and slow other times.

That’s it for now. I’ve decided to talk about projective geometry in class, since students seem curious about it and it’s a very good topic. You can devote whatever other time you have to working on the module and re-do problems.

To Do: Please email me your requests for “re-do” problems (at most 2 for up to 80% credit) and I’ll make a combined Module 1&2 redo option.

To Know: Module 3 is open on canvas, due in a week.

To do: Compute the sum of the following two points on this elliptic curve. E: y^2 = x^3 + x + 1 modulo 7. P = (0,1) and Q = (2,2). Compute P+Q. Hand in on the daily dropbox.

To Know: I will post the next assessment either late tonight or early on the weekend. I will make it due Monday the 26th. I hope to have the 2nd assessment back to you this weekend.

To Do: Practice with finite fields!

Please create a finite field of size 9. To do this, you will need to find an irreducible polynomial of degree 2 in F_{3}[X]. To do this, just try some polynomials. One way to check if something that has degree 2 is irreducible is to check if it has any roots (since if it factors, it will have to have a linear root, i.e. factor). There are only 3 possible roots (namely 0,1,2) because we are working in F_{3}. Hint: choosing a polynomial without a linear coefficient will simplify your computations later on.

Next, make a complete multiplication table for your finite field of 9 elements. Take advantage of symmetry to speed this up. Practice makes perfect!

Use the Finite Field Tools to check your work (figure out what the tools do, then check your polynomial is irreducible and at least spot check some items on your multiplication table).