To Know: The “Quantum” chapter of the text is now up in canvas.
To Do: Quantum Key Distribution!
I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “IN CLASS” channel category of discord. There you will find plenty of text channels, so fill them up with two people each as you arrive, taking the first empty spot (the first person needing a partner or the first unused channel). Announce your arrival. The first person to arrive in a channel is Alice, the second person to arrive is Bob. Once two people are there, it’s full, so pick the next channel. You’ll do all communication on the channel so I can help you debug if it doesn’t work.
Open up the QKD BB84 Tools. The first box contains some code to initialize; no need to read this, just run it. The second box is a spot where you can either create photons (in our instantiation, they are just integers), or measure existing photons. It just holds an example for now.
Once you know if you are Alice or Bob, follow the protocol for your role.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage).
Now choose a sequence of 16 bits: example 011001010101 etc. Again, true or good pseudo-randomness is best.
Use your two sequences to generate photons using the command create_photon in the QKD BB84 Tools page. This will create 16 integers (the photons), which you should obtain and paste into the channel as your “outgoing photon stream”.
Wait until Bob harvests your photon stream and reports that they are done “measuring” the photons.
Then, post to the channel the list of bases you used on your photons.
Bob will also post their list of bases used on the channel.
Then, determine the shared secret key from these two lists. Share it and see if Bob agrees.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage). Keep this secret for now.
Alice will create a stream of photons (integers). Harvest (cut-n-paste) Alice’s photon stream, and use the command measure_photon() in the QKD BB84 Tools page to measure them using your list of bases (first basis to measure first photon etc.) Record the measurements and keep them secret.
Report to the channel you have finished measuring.
Then, report to the channel your list of bases.
When Alice also reports her list of bases, derive the shared secret.
Then, post the shared secret you derived to check if it agrees with Alice’s.
To Do: When you’re done, just post to canvas a screenshot or record of your experience; you can screenshot the channel or you can screenshot your spreadsheet or a text file you kept a record in; whatever, just to show you did it.
To Do: Listen to this podcast (26:53). It’s a quantum computing entrepreneur talking about the current (well, 2017) take on how it fits in the big picture. He discusses things like Moore’s Law and the current state of computing, and what quantum computers should be able to do in the future.
To Do: Here’s an exercise (here’s latex source) in measuring a qubit with respect to different bases. Please hand in the answer on canvas.
To Do: Think about the polarized filter experiments I referred to at the end of the lecture — I’ll start with them next lecture, so try to figure out what happens in them before you come to class.
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.