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.

To Do: Please email me your requests for “re-do” problems (at most 2 for up to 80% credit) and I’ll make a combined Module 1&2 redo option.

To Know: Module 3 is open on canvas, due in a week.

To do: 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. Hand in on the daily dropbox.

To Know: I will post the next assessment either late tonight or early on the weekend. I will make it due Monday the 26th. I hope to have the 2nd assessment back to you this weekend.

To Do: Practice with finite fields!

Please create a finite field of size 9. To do this, you will need to find an irreducible polynomial of degree 2 in F_{3}[X]. To do this, just try some polynomials. One way to check if something that has degree 2 is irreducible is to check if it has any roots (since if it factors, it will have to have a linear root, i.e. factor). There are only 3 possible roots (namely 0,1,2) because we are working in F_{3}. Hint: choosing a polynomial without a linear coefficient will simplify your computations later on.

Next, make a complete multiplication table for your finite field of 9 elements. Take advantage of symmetry to speed this up. Practice makes perfect!

Use the Finite Field Tools to check your work (figure out what the tools do, then check your polynomial is irreducible and at least spot check some items on your multiplication table).

To Know: The next module assessment (for RSA, primality testing, euclidean algorithm, factoring etc) will go up on Thur or Fri and be due next Friday.

The last assessment is almost all graded, you may get it back tomorrow or on the weekend.

To Do: Practice working in F_{3}[X]:

Notice that the prime is 3!

Compute (X^2+2X+1)*(X+1).

Divide X^4 + X^2 + 1 by X^2 + X + 1 and determine the remainder. Check your work afterward by multiplying out.

Determine the gcd of X^4 + X + 1 and X^2 + 1. You will likely get a result of “2”. Keep in mind that 2*2 = 1, so this really means they are “coprime” (we can discuss this in class a bit).

Solve the Diophantine equation s(X^4+X+1)+t(X^2+1) = 1. Hint: If you got “2” as the gcd, then solve the (equation=2) first, then use 2*2=1 to figure out how to get the solutions to the (equation=1).

Hand in your answers to the canvas dropbox.

Check your answers against these solutions (only after you’ve done them all!).

Today, we’re going to try a little Quadratic Sieve factoring. Let n = 539873. Use the Quadratic Sieve Tools to show how the Quadratic Sieve would factor this. That is, write up a description of your factor base, what numbers you will B-factor and where they come from, what results (“facts”) you get, and how you use that to factor. Hand this in on the dropbox. Note: it’s up to you how many primes to keep in the factor base, and how big a list of numbers to B-factor. Just try to guess how much you’ll need to get facts, and expand your net if you need to. Comment: I say “would factor this” because I’m going to allow you a little shortcut. I’ve built in a “B-factor” function that will factor out small divisors of a number. You set the factor base and then it will factor powers of those numbers out. In the real quadratic sieve, you would use “sieving” to find the B-factorizations, not do them one-by-one (for runtime reasons). Instead, here, the tools will simply print out the B-factorizations and you can proceed from there.

Also To Do: Please finish the RSA ciphertext chain (including decrypting the message sent to you) because it’s important practice.

Announcement: There’s a Math Club at CU that hosts talks. Here’s the website (I’m speaking Tue morning) http://math.colorado.edu/mathclub/.

Module “corrections” (repeating because it’s important). I’d like to allow you to do corrections for the module assessments. For Module 1, I’d like you to email me / direct message me a maximum of two problems (individual problems/parts, not problems with multiple parts, e.g. 4d) from the assessment that you would like to re-do, to replace your current grade on those problems, up to a maximum of 80% credit. I will then look at the problems people are asking for and make “replacement” problems for you to attempt. This cannot lower your grade, it can only improve it. It is optional.

To Know: I’ve updated/combined the modules on the website under “Goals” because I got confused and combined the second and third into one thing anyway. You can check that out if you’d like — we’ll have just 6 assessments overall, not 9.

Module “corrections”. I’d like to allow you to do corrections for the module assessments. For Module 1, I’d like you to email me / direct message me a maximum of two problems (individual problems/parts, not problems with multiple parts, e.g. 4d) from the assessment that you would like to re-do, to replace your current grade on those problems, up to a maximum of 80% credit. I will then look at the problems people are asking for and make “replacement” problems for you to attempt. This cannot lower your grade, it can only improve it. It is optional.

To Do: Factor the number 184507 using the p-1 factoring method from today’s class. Tell me what you choose for a, and tell me what powers of a you compute, and tell me what gcd you tried, and what factor you found (you may need to keep lengthening the chain and trying again). You can use the Sage command “factorial(n)” if you want to save time. You can use the command “is_prime(n)” to check that you’ve factored it all the way. Do not ever use the command “factor(n)” since that’s cheating (except to check your answer after you’re done). Note: It’s in Section 6.4 of 2nd edition of text.

To Do: Hallowe’en RSA Ciphertext Chain!

Review the way the RSA cryptosystem works.

For this activity, you can use the helpful Sage tools on the RSA Tools page.

Create your own Public Key:

Choose two primes p and q of 10 digits each. Compute n, e, d according to the RSA system. Write down d so you don’t forget.

Publish (n,e) as your public key on the #ciphertexts channel on discord.

Encrypt a message to the last person in the chain:

Obtain their public key (n,e).

Make a message in ASCII (just like in the El Gamal ciphertext chain), which is a number < n. It should be an answer to a question “What would be fun to be for Halloween?” You probably have room for about 6 letters.

Encrypt your message to the person’s public key according to RSA, and post the ciphertext with a @whoever on the ciphertext channel.

Decrypt the message you receive:

Use the RSA decryption method with your own private key to read the message and post it on the ciphertext channel with @whoever for confirmation.

For the following problems, you can use a calculator and/or Sage for basic computations (reducing mod n, modular exponentiation, multiplication etc.). But otherwise work by hand showing your work.

Solve the linear congruence 50x = 10 mod 75.

Solve the linear congruence 13x = 14 mod 15.

Solve the linear congruence 7x = 13 mod 14.

The euler-phi function gives: phi(21733) = 21420. Use this fact to factor 21733. (Hint: revisit notes in class, I explained how to use a quadratic formula to do this).

Suppose Eve has an RSA modulus n = 47053, and also knows the encryption and decryption exponents e = 3497 and d=2333. Use the method shown in class (adapated Miller-Rabin algorithm, also explained on page 168 of 2nd edition of text (in Section 6.1)), to factor n.

In the problems above, show all the steps by hand and hand in on canvas. Useful functionality in Sage is basically just modular arithmetic functionality, but you might find the Miller-Rabin tool for determining how many powers of 2 are in something helpful.