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 F3[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 F3. 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).
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.
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.
Try out this Chinese Remainder Theorem problem, by hand: x = 3 mod 244 and x = 17 mod 495. Show all the steps of the process, including the extended euclidean algorithm. You can use the computer to do modular arithmetic for you (e.g. multiplying things if needed), but show the steps as if doing it by hand. Hand this in on the dropbox.
In preparation for class, try to solve 2x = 4 (mod 6). How many solutions are there? Can you give a generalizable theoretical proof your solution method is correct (not just an exhaustive check)?
To Know: Assessment for Module 2 is open and due on Wednesday.
Next up is to learn the Extended Euclidean Algorithm: video (10:58). Use it to solve the following linear Diophantine equation, to find one solution in integers x and y: 440x + 377y = 1. Write it up neatly.
Using Sage to do a single modular exponentiation, use the Fermat Primality Test to test if n = 3057601 is composite or probably prime, using the base 99908. Write down what you computed and what you conclude.
Next, 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. (These are the same numbers as above.) Write out the steps (the b_i’s and how you calculate them and what you observe and conclude).
To Know: I’ll post the assessment for Module 2 (DLP and related cryptography and modular arithmetic) later tonight. I’m just finalizing it. You’ll have a week to do it.
To Do: Learn the Euclidean Algorithm! It’s easy, because I’ve made a video about it (13:28). Do as the video says (pause and think/try when it says). Note: if you aren’t feeling very comfortable with what the GCD (greatest common divisor) is, you may want to watch this video about GCD first (12:01) — not required, but there for you if you need it.
Then use the Euclidean algorithm to compute the gcd of 2266 and 822. Notice how the numbers are even always as you continue down (think back to the video for what is happening). Hand a neatly organized version of your work on the daily dropbox on canvas.
To Know: My plan is to post the Module 2 assessment on Wednesday, with one week to do it.
To Know: If you’re interested in the runtime of the Index Calculus, 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.
FOR GRADUATE STUDENTS: Please provide me by Friday (email is fine) a short paragraph description of what you intend to do for your written project for the course.
To Do: El Gamal Encryption Chain! Check out the El Gamal Tools. We will use the prime there (the next prime after 10^6), and the primitive root 2. This is set up on that tools page. Here are my notes from class on El Gamal; you’ll also find it in Section 7.5 of the 2nd edition of the text on canvas. Do the following:
Set up a private and public key for yourself. Publish the public key on the “#ciphertexts” channel on discord (Under Study Groups). Note your public and private key down on paper.
Choose a four-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 “What do you like?” Make notes on paper.
Find the most recent unused public key on there (if possible), and use the public key to encrypt your four-letter word to that person. (It will involve two chunks, so you will have to send them as two separate ciphertexts.) Keep notes on paper of the key steps.
Post your ciphertexts publicly for that person on the channel. Since it consists of two chunks, you should post two pairs (r,t).
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.