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).
On the archive page above, you can look at test solutions. Please make sure your grades are correct.
Retakes: 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).
To Know: If you’re interested in the runtime of the Index Calculus, I have more detail in my overleaf text. Additionally, here are some course notes that cover it in more detail (from Andrew Sutherland’s MIT course on elliptic curves). This may be an interesting topic for a graduate student project: runtime for index calculus and/or index calculus improvements mod p and/or in other finite fields.
Solve the discrete logarithm problem for $p=131$, $g=2$, $h=17$, using the Index Calculus method. You may use the Index Calculus Tools and Sage’s modular arithmetic and plain arithmetic computations to avoid by-hand computations, but please solve the linear system by hand (i.e. choosing which equations to subtract from which etc.). Note: this is a randomized algorithm, so you will get different relations than someone else, or next time you run the tool. If you are not finding a very nice linear system, just try to get some more relations and pick simple manageable ones.
To Do: El Gamal Encryption Chain! We will use the same prime and generator as we did for Diffie-Hellman. This is set up on that tools page. Do the following:
If you have not already made a public key for Diffie-Hellman Key Exchange, then set up a Diffie-Hellman private and public key for yourself. Publish the public key on the “#public-keys” channel on discord. Note your public and private key down on paper for safekeeping. If you’ve lost your private key, delete your old key and do this again.
Choose an at most 6 letter word as a message. It should be a polite, recognizable english word, so the decrypter will be able to tell they’ve done this correctly. It should answer, in some fashion, the question “Best food?” Turn it into an integer using the Text to Integer tool. Make notes on paper.
Find the Diffie-Hellman public key immediately before yours in the #public-keys channel (if this doesn’t exist, use the most recent public key), and use that public key to encrypt your four-letter word to that person. Keep notes on paper of the key steps.
Post your ciphertexts publicly for that person on the channel. Use @username. It should consists of two numbers, which we called (K,c).
When you receive a message from someone on the channel, decrypt it. Hopefully it is an english word. If it is, yay! Respond on the channel to that person to tell them the decryption you got. Keep notes on paper of the key steps.
For the canvas submission, show your notes from this work. If you don’t get someone sending you a message in time, that’s ok, but keep an eye out and do the decryption stage when possible.
Challenges for fun:
Break someone else’s message! Use any algorithm. Let me know if you succeed on discord!
Get your friend to send two messages to the same person using the same ephemeral key. Break this!
Reminder! We have a course textbook on Overleaf with examples of the algorithms we cover. The table of contents should help you find anything, and I have been adding in solutions to some daily post problems there.
Here are solutions to the last daily post (link to appear shortly).
Reminder! You should be filling out your own daily post tracking sheet. Please attach a copy of that to the daily post submission today so we can take stock.
Use the Baby-Step-Giant-Step algorithm (and show all steps) to solve the discrete logarithm problem $34 = 3^x \pmod{113}$. You may use Sage’s functionality to compute the lists, including the tools on the BabyStepGiantStep page if you want to (ask for help on discord if you need some explanation of the page), so it shouldn’t involve much work by hand. But please present the solutions tidily and in a well-explained and well-labelled way (indicate where each term in each list comes from, not just the value you get), so the algorithm is evident.
Suppose I write the standard trial division algorithm for factoring an integer $n$. That is, I loop through all integers $k$ less than $n$, and try dividing $n$ by $k$ to see if it divides evenly. What is the runtime of this algorithm? As a function of the size of the input to the algorithm (the input is the number $n$ written in binary notation), is this an exponential or polynomial algorithm, or something in between?
Explain why for trial division, to factor $n$, you actually only need to loop through integers $k$ less than or equal to the square root of $n$. How does this change your runtime analysis?
Consider the discrete log problem $h = g^a$ modulo $p$. Suppose you make two lists: $g^x$ for random $x$ and $hg^{-y}$ for random $y$.
Explain how, if you get a collision, it results in a solution to the discrete log problem. This algorithm is called the “Birthday attack” on discrete log.
The Baby-Step-Giant-Step algorithm is a sort of “organized” birthday algorithm. Explain why I say this.
How long should you make these lists to expect a decent probability of a collision?
With reference to the last part, what is the runtime of the birthday attack on discrete log?
If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.