Watch this excellent 3Blue1Brown/MinutePhysics video (17:34) which closely relates to class. In particular, it revisits polarized photons and some of what we’ve done for class already, but then moves on to Bell States and Bell’s Theorem, which I wish we had time to do, but we are going to focus on quantum computation next. If anyone is curious, I have an old video doing the underlying math of this that I can put up on canvas.
If you’re curious, here’s an article about a Bell test at NIST here in Boulder and how they are using it to make random numbers.
Please look over your exams and the solutions and let me know if there are any grading questions etc. There’ll be a re-do opportunity as before (more info soon).
I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “QKD pairs” 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 mysterious looking 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.
Write $|-\rangle$ as a linear combination of $|0\rangle$ and $|1\rangle$.
Write $|i\rangle$ as a linear combination of $|+\rangle$ and $|-\rangle$.
Consider the state $|\psi\rangle = \frac{1}{\sqrt{5}} |0\rangle + \frac{2}{\sqrt{5}}|1\rangle$.
Measure it in the basis $|0\rangle$, $|1\rangle$. What are the possible outcomes and their probabilities?
Measure it in the basis $|+\rangle$, $|-\rangle$. What are the possible outcomes and their probabilities? (To do this, you will first need to write $|\psi\rangle$ as a linear combination of $|+\rangle$ and $|-\rangle$.)
Module test! See the Goals page (top navbar) for list of topics, just now updated to include the last stuff.
If you would like a practice problem on Dual_EC_DRBG, I’ll try to post one on discord for you tonight. But for the daily post, there’s no requirement to hand anything in, just study what you need.
Don’t forget the Module 4 Assessment is on Friday. Calculators allowed like last time. Details about the material (and review problems) are on the “Goals” page on the navbar above.
To Do: An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: what did 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,1] 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 6 or fewer letters. Translate this to an integer and add three 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 #ciphertexts 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.
There’s a module 4 test on Friday! I will post more information about that in this spot and update the “Goals” page above with practice problems etc. I just wanted to post the daily questions before I got to all that.
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. You can use the #daily-collaboration channel.
I’m almost done setting up the written Module 2/3 retakes, I’ll announce on discord when they are up.
Compute a full list of the elements in $\mathbb{P}_{\mathbb{F}_5}^1$. Each element is an equivalence class (a bunch of different vectors that differ by scalar multiplication), so write out all the vectors in each equivalence class.
In $\mathbb{P}_{\mathbb{F}_4}^2$, where $\mathbb{F}_4 = \mathbb{F}_2[x]/(x^2+x+1)$, what other vectors are equivalent to the vector $[1,x,x+1]$. Give a complete list. How many should there be?
In general, in $\mathbb{P}_{\mathbb{F}_{p^n}}^k$, how many vectors are in each equivalence class? For example, in the example from lecture, in $\mathbb{P}_{\mathbb{F}_{3}}^1$, there were 2 in each class. What is the size of $\mathbb{P}_{\mathbb{F}_{p^n}}^k$ (i.e. how many equivalence classes)?
Find all the points of the affine equation $y^2 = xy – 1$ on the “line at $\infty$”. (Hint: we did this with the elliptic curve at the end of lecture; see notes/video.)
Compare your last daily post with the solutions (which are in the beginning of the class notes under Archive for Oct 17), clearing up any misconceptions.
Your textbook has a nice chapter on elliptic curves that teaches it much as we have done, so there are some examples there. It does give a general formula, but I’d like you to do the computations below from the definitions in class, because you learn more that way.
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$.
What is $P + \infty$ on this curve?
What is $-P$?
Suppose, on the same curve, we want to compute the sum of $Q$ with itself. That means we need to find a tangent line! Compute $Q+Q$.
Show that if $P=(x,0)$ is a point on an elliptic curve, the $2P = \infty$.
Show that $x^2 + 1$ is irreducible modulo $7$ (meaning, when having coefficients mod $\mathbb{F}_7$). Is $\mathbb{F}_7[x]/(x^2+1)$ a field?
Find the inverse of $x$ in the finite field $\mathbb{F}_7[x]/(x^2+1)$.
The multiplication table for the finite field $\mathbb{F}_2[x]/(x^2+x+1)$ can be found in the course notes for Oct 12th (Archive page at top bar) or by using the Finite Fields Tools page (use p = 2 and F.<b> = GF(p^2, modulus=x^2+x+ 1)). Or you can make your own by hand. You can use the multiplication table to do the following problems.
Compute the multiplicative order of $x$ in this field.
Compute the multiplicative order of $x+1$.
Which elements of this field are invertible? List them. (This is a concept check question.)
What is a multiplicative generator for this field (something whose powers generate all invertible elements, like a primitive root)?
The first two boxes on the Finite Field Tools page are a calculator for any finite field you want. You may use these boxes to solve the following problems.
Let us work in the Finite Field of size $5^2$, which, in the tools page, will by $\mathbb{F}_5[x]/(x^2+4x+2)$ where $x$ (called $a$ in the calculator) is a multiplicative generator. Set this field R up in the first box on that page so you can use it in what follows.
As a test of your calculator skills, what is the inverse of $x$? You can input R(a^(-1)) into the second box. You should get that the inverse is $2x + 3$ (which appears as 2a+3).
Suppose you are Bob and your El Gamal private key is $b = 5$. The generator is $g=x$ in this same finite field. What is your public key (reduced to small degree)?
Suppose that Alice encrypts you a message using your public key. The message is a polynomial. She sends you the ciphertext $c=4x$ with ephemeral public key $K = 4x+3$. What is the plaintext polynomial?
If time remains, revisit the statement and proof of Fermat’s Little Theorem (for example, in the overleaf notes, the august 31 lecture notes (click “Archive” in the bar above), or solutions to the Module 1 test). State and prove the analogous theorem for a finite field of $p^n$ elements where $p$ is prime.