Find the square root of $3$ modulo $p=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.
IF YOU ARE IN 4440: Think about forming a group of 2-3 people for a poster. Read the poster info in the “Posters” tab above. Reach out on discord, in person, etc., if you like to find a group that way. Then fill in this form with your poster group situation so I can find out who is working with who or who needs helping finding a team.
IF YOU ARE IN 5440: You do an individual project *instead of a poster*. Send me an email with your thoughts on topic and your background and we can brainstorm.
Think about your topic.
Use the birthday paradox approximation formula (with the natural log e in it) to determine the minimal number of people who need to be in the classroom to have at least a 50% chance of a shared Ceres birthday. (You’ll need to look up how many earth days in a Ceres orbit.)
This problem outlines a proof that there are infinitely many primes from a CS perspective, using information theory (due to Chaitin).
Define the Komolgorov complexity $C(n)$ of an integer $n$ to be the length of the shortest computer program that will output $n$ in decimal form. (For concreteness, you can fix any programming language.) For example, the program for $2701$ might simply be ‘print(‘2701′)’. This gives a trivial upper bound on $C(n)$ of $O(\log n)$. Explain why.
For the numbers of the form $n=10^t$, prove that $C(n)$ is bounded above by $O(\log \log n)$ by giving an actual computer program.
Suppose there are only finitely many primes $p_1, \ldots, p_k$. The number $k$ is a constant. Show that for all $n$, $C(n)$ is bounded above by $O(\log \log n)$, by using unique factorization.
Prove that there must exist $n$ having $C(n) \ge \log n$, by using a counting argument.
Explain why this proves there are infinitely many primes.
If you need a review of RSA, check the lecture notes, overleaf (where there’s an explicit example with Sage advice). For what follows, the Sage Sandbox page should be useful, as may be the RSA Tools page. These pages show how to do operations like modular inverse, exponentiation, and euler phi function in Sage. You can use basic number theory functions in Sage to do all your computations.
First, set up your public and private key.
Choose two 8-decimal-digit primes and form their product $n$. You can get primes out of Sage using the next_prime() function. So pick a number in the ballpark you want (maybe using randint()) and use next_prime() to get the next smallest integer which is prime.
Compute $\varphi(n)$. Note that euler_phi() will do this for you in Sage, but it’s better to use the formula (p-1)*(q-1) because at cryptographic size, Sage would not return an answer, since euler_phi(n) would try to factor n.
Choose an encryption exponent $e$ that is positive and less than $\varphi(n)$.
Compute your decryption exponent $d$. It’s possible this will fail (e.g., if $e$ is not invertible!). If this error gets annoying (depends on your $\varphi(n)$), you could try using next_prime() to get a likely invertible $e$. (Concept check: why is a prime $e$ more likely to work?)
Keep $d$ safe (along with $p$ and $q$, $n$ and $\varphi(n)$, just in case) in a file on your computer. The $d$ is your private key information; be sure also to keep $p,q, \varphi(n)$ away from prying eyes.
Reveal your public key $n$ and $e$ on the discord #public-keys channel (“My RSA Public Key Is (n,e)=(….,….)”).
Create a secret message which is at most 6 letters long. It should answer “What’s something awesome?” Please don’t make it longer or this exercise won’t work.
Turn it into an integer using the Text to Integer tool. (There’s an Integer-to-Text tool on the same page to undo this process.)
Now find someone else who has posted their public key (the most recent one before yours), and encrypt your message to that person. Post it on the #ciphertexts channel for them (use @theirname to alert them). Note: this should be one residue modulo their public $n$.
When someone posts a message for you, decrypt it and announce the result using discord’s “spoiler” feature.
You can turn in on canvas a screenshot of your discord result(s).