Quantum Key Distribution! (Section 6.7 in textbook)
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.
Measure $|+\rangle$ in the $|0\rangle$, $|1\rangle$ basis (i.e. give results and probabilities).
Measure $|+\rangle + i|-\rangle$ in the $|0\rangle$, $|1\rangle$ basis (i.e. give results and probabilities).
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 normalized linear combination of $|+\rangle$ and $|-\rangle$.)
With what time remains, work through whatever parts are most useful or interesting to you of this worksheet. My suggestion: if you’re comfortable with the complex numbers as done in class, then start at “Domain Colouring” which is just lovely. If you need more practice with complex numbers because they are new, the earlier parts of the worksheet will provide that.
Find the square root(s), if any, of $3$ modulo $11$ using the algorithm from the end of class. Now draw the dynamical portrait of powers of $3$ modulo $11$. Label each vertex as $3^x = y$ for whatever x and y, so each vertex can be interpreted as its value mod $p$ and its power of $3$. Can you use this diagram to explain why the method works?
Write a small for loop in sage that runs the Blum-Blum-Shub pseudo-random number generator.
Invent a way to check that the output “looks random”. Do you know a good statistical test? Or could you graph it somehow? If you discover some type of non-random-ish behaviour, it could lead to a way to factor integers!
Explain how, if you can factor $n$, you could find square roots modulo $n = pq$ where $p,q$ are primes congruent to $3$ modulo $4$. This is basically just recalling something we did in class.
Explain how, if you can find square roots modulo $n$, this allows you to factor $n$. (Find square roots means find all square roots.) This is basically just recalling something we did in class. This and the previous exercise show that factoring $n$ is considered equivalent to finding square roots modulo $n$.
We are mid-semester, so please make sure your self-eval sheet is up to date and hand in a copy with today’s daily post, so I can see how things are going. Please contact me if you are concerned about your grade. The computed grade in canvas is NOT RELIABLE (the raw grades are reliable, but the conversion to estimated grade is not); you can compute for yourself using the grading tab above.
To Do: An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: best hallowe’en costume? 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. 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 #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.
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.
Turn your message into a point on the elliptic curve as described in class. This might mean updating the padding to “001”, “010” 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 a 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.
You should then obtain the most recent public key on the #public-keys channel, and encrypt your ASCII 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.
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.
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.
On the curve $y^2 = x^3 +2x + 1$ modulo 5, try to compute the addition of the two points P = (3,3) and Q = (1,2) by hand.
On the curve $y^2 = x^3 +2x + 1$ modulo 7, try to compute the addition of the two points P = (0,6) and Q = (0,1) by hand. The result should be the point at infinity (because these are inverses of each other), so the computation will “fail” — explain what fails that lets you know the result is the point at infinity.
On the curve $y^2 = x^3 +2x + 1$ modulo 35, try to compute the addition of the two points P = (28,13) and Q = (21,22) by hand. The result will fail. Explain why it fails and how it factors 35. Explain the relationship to the previous two problems.
Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! Write up a short explanation of your work.
Write a small Sage for loop to implement Pollard p-1 factoring. Use it to factor n=16637. Some hints so you don’t get stuck:
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).
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).
start your loop at power 2 (squaring), not zero
If time remains, explore EC Factoring:
Do the example above again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.
Try modifying one of the middle digits of n, and see how long it takes. Factor n completely using Sage’s factor() function, to see what kinds of primes it has in it. Repeat a few more times.
Report/discuss on discord on how long it took (i.e., what multiple of P blew up) 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.
Your group Poster Plan is due on Wednesday on canvas; please make contact with your group and make a plan. Click “Posters” above for all the details.
Make sure you did last day’s daily post and compare to solutions (link here). Those computations are important; we’ll use them more. Notice in particular what to do if your slope has a denominator, or you are adding a point to itself.
Give an example of four different vectors in $\mathbb{R}^2$ which become the same in $\mathbb{P}^1_\mathbb{R}$.
In the notes, we studied $\mathbb{P}_{\mathbb{F}_3}^2$, showing 26 equivalence classes, each a different colour. Pick one colour, write out the vectors in that equivalence class, and check that they are equivalent.
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. (We did this for $\mathbb{P}_{\mathbb{F}_3}^1$ in class.)
In general, in $\mathbb{P}_{\mathbb{F}_{p}}^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}}^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: first homogenize the equation so all terms have the same degree, then break into $Z=0$ and $Z \neq 0$ cases.)
Note: there was no daily post due Friday Oct 11th, no worries there.
Warning: Poster Plan is due Wednesday October 16th. See the tab “Posters” for more detail. It requires a title/abstract/work plan, so you’ll want to have at least a brief discussion as a group before Wednesday.
Friday’s class wasn’t a good one to miss, so I’ll try to post a link on the Archive page to last year’s recording, for those who weren’t in attendance.
I’ve added everyone into poster groups in canvas — check that this is correct! Also, you should be able to contact one another there, or on discord.
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$. (I’ll do this in class also.)
Show that if $P=(x,0)$ is a point on an elliptic curve, then $2P = \infty$.
Please answer this one-question form about who is in your poster group.
I’m using discord to schedule an office hour Tuesday.
Schedule your Test 1 retake if you like: 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). I added more slots this week and next.
TEST WEDNESDAY (see Tests tab for syllabus/review)
POSTER GROUPS. Ok, at this point if you haven’t gotten an email from me, then I think you’re working out a group of your own, but if that’s not the case, let me know! Get going looking into cool topics! Click “Posters” tab above.
Use the Miller-Rabin primality test with a=2 to determine if $n=90751$ is composite or probably prime. Show your steps.
If it comes up probably prime, try it with a=3. Show your steps.
Next, possibly using the Miller-Rabin Tools, implement the Miller-Rabin primality test to test if n = 3057601 is composite or probably prime, using the base 99908.
The euler-phi function gives: phi(21733) = 21420. Use this fact to factor 21733. (Hint: revisit notes in class friday sept 27, I explained how to use a quadratic formula to do this).
Factor $n=31861$ using the Quadratic Sieve Tools page to produce the relations you will need. You may need to expand your factor base or the number of relations the boxes produce.
If you got lucky and got a single relation that did it, can you instead find a pair or larger combination of relations that do it?
Many of the messages posted on the #ciphertexts channel during the RSA ciphertext chain were pretty small. Can you attack any of them using the “small message” attack demonstrated in class?
Reminder: fill out the form (link in last daily) about poster groups.
Reminder: Test Wednesday!! See Tests tab above.
I’ll post the proof of infinitude of primes based on Komolgorov complexity in the overleaf notes [edit: done, see section 3.7] — this is the solution to the last daily post.
Use Fermat’s Primality Test to detect whether 2001 and 2003 are composite or probably prime. Show your work (but you can use a calculator like Sage for the exponentiation).
If one of them is probably prime, then try a different a and explain what you learn.
Use Fermat Factoring to factor $n=16080$. Show the steps.
I wish to factor $n=38191$. How do I do it, if I have the following info:
196 ^2 - n factors as 3^2 * 5^2
201 ^2 - n factors as 2 * 5 * 13 * 17
214 ^2 - n factors as 3^2 * 5 * 13^2
227 ^2 - n factors as 2 * 3^3 * 13 * 19
229 ^2 - n factors as 2 * 3 * 5^3 * 19
241 ^2 - n factors as 2 * 3^2 * 5 * 13 * 17
254 ^2 - n factors as 3^4 * 5^2 * 13
If you aren’t familiar with for loops and if statements in Python/Sage, please visit these super quick tutorials: Python: For Loops and Python: If Statements.
Play around with Sage to see if you can find Carmichael numbers. This might require writing a for loop in python.