For Monday, October 23rd, 2023

  1. I’ll post a short video solution to the last daily, but it’s not up yet; I’ll note it here when it is.
  2. 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$.
  3. What is $P + \infty$ on this curve?
  4. What is $-P$?
  5. 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$.
  6. Show that if $P=(x,0)$ is a point on an elliptic curve, then $2P = \infty$.

For Friday, October 20, 2023

  1. Check the previous daily post for some announcements in case you missed them.
  2. Solutions to the last daily post are in the lecture notes and also here.  Solutions to the one before are here.  Compare with your work.  Note: these solutions are slightly disorganized (some extra problems etc), so let me know if you have any trouble with them.
  3. The first two boxes on the Finite Field Tools page are a calculator for any finite field you want.  You may use these boxes to solve the following problems.
      1. Let us work in the Finite Field of size $5^2$, which, in the tools page, will by $\mathbb{F}_5[x]/(x^2+4x+2)$ where $x$ (called $a$ in the calculator) is a multiplicative generator.  Set this field R up in the first box on that page so you can use it in what follows.
      2. As a test of your calculator skills, what is the inverse of $x$?  You can input R(a^(-1)) into the second box.  You should get that the inverse is $2x + 3$ (which appears as 2a+3).
      3. Suppose you are Bob and your El Gamal private key is $b = 5$.  The generator is $g=x$ in this same finite field.  What is your public key (reduced to small degree)?
      4. Suppose that Alice encrypts you a message using your public key.  The message is a polynomial.  She sends you the ciphertext $c=4x$ with ephemeral public key $K = 4x+3$.  What is the plaintext polynomial?
  4. Using the online tools/Sage, find a multiplicative generator for $\mathbb{F}_3[x]/(x^2+1)$.

For Wednesday October 18th, 2023

  1. Compare your last daily post solutions to these solutions.
  2. Compare your test solutions to the online solutions (“Archive” tab has these under the test date).  If you have questions about grading, you can contact me with a pic of your problem, or set a time to chat (calendar link on the canvas main page).
  3. Retakes for 2nd Test:  You may retake one of the 10 point problems in Part B that you attempted.   The written retakes will be posted on canvas (for both Module 2 and 3) as soon as I can manage.
      1. If you got 7 or higher on your retake problem, you will do a written replacement problem.
      2. If you got 6 or lower, you can 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).
  4. What are the units of $\mathbb{F}_7[x]$?  (This is a concept check kind of question.)
  5. Determine whether $x^2 + x + 1$ is irreducible in $\mathbb{F}_3[x]$.  (This may require an exhaustive search method; you may use Sage if you like, but it’s not that bad by hand if you are efficient/thoughtful on the method.)  What about $x^2 + 2x + 2$?
  6. Consider the ring $\mathbb{F}_3[x]/(x^2+2x+2)$.  Reminder, this means the rules are:  $3=0$ and $x^2+2x+2 = 0$.  You might find it more helpful to write the second rule as $x^2 = x + 1$.
      1. Multiply out and simplify $(x+1)x$.
      2. Multiply out and simplify $(x+1)(x+2)$.
      3. Check your answer against my answer on the #daily-collaboration channel of discord.  If things aren’t working, ask for help on discord from me or your peers.
      4. Write out a list of all of the finitely many elements of the ring we are working in.
      5. Write out an addition table for these elements.
      6. Write out a multiplication table for these elements.
      7. On the #daily-collaboration channel of discord, put up a flashcard quiz question:  that is, give a problem (to add or multiply two elements) and then put its answer as a spoiler (surrounded by double bars), so someone else can use their addition/multiplication tables to check their answer to your quiz question.
      8. Use your tables to check someone else’s quiz question.  In this way, we will probably/hopefully quickly diagnose any problems with the computations and work out the bugs so everyone is getting good at it!
      9. If you make an error in your quiz question, you can use the discord edit functionality to fix it.  Eventually we’ll have a bunch of great quiz questions up there to check your work against!
  7. Find the inverse of $x$ in the finite field $\mathbb{F}_7[x]/(x^2+1)$.  Remember, this is just like the analogous problem for the integers.  It will require an extended euclidean algorithm computation in a polynomial ring.
  8. The multiplication table for the finite field $\mathbb{F}_2[x]/(x^2+x+1)$ can be found in the overleaf notes under “Finite Fields”.  Or you can make your own by hand.   You can use the multiplication table to do the following problems.
      1. Which elements of this field are invertible?  List them.  (This is a concept check question.)
      2. Compute the multiplicative order of $x$ in this field.
      3. Compute the multiplicative order of $x+1$.
      4. What is a multiplicative generator for this field (something whose powers generate all invertible elements, like a primitive root)?

For Monday, October 16th, 2023

  1. Hi everyone, sorry I wasn’t feeling well on Friday, so class was cancelled.
  2. As a replacement, I’ve posted a video of the corresponding lecture from last year’s class on canvas.  First up, please watch that.  It is titled “BONUS: Lecture Math 4440 10-12-2022: Introduction to polynomial arithmetic and finite fields” and appears at the end/bottom of the default listing by creation date in the Media Gallery.  (This doesn’t count as your daily post time, it’s lecture-replacement time.)  Here are the notes.
  3. Do two polynomial long divisions:
        1. In $\mathbb{F}_2[x]$, divide $x^4 + x + 1$ by $x^2 + x + 1$.
        2. In $\mathbb{F}_5[x]$, divide $x^5 + 3$ by $x^2 + 2$.
  4. Working in $\mathbb{F}_3[x]$, do the Euclidean algorithm on $x^4+x^3 + x^2  + 2x + 1$ and $x^2 + 2$.  What is the gcd?
  5. Consider the ring $\mathbb{F}_3[x] / (x+ 1)$.
      1. List all the elements (there should be 3).
      2. Explain in your own words why there are only 3.
  6. Consider the ring $\mathbb{F}_2[x] / (x^2 + x+ 1)$.
      1. List all the elements (there should be 4).
      2. Create an addition table.
      3. Create a multiplication table.

FRIDAY CLASS CANCELLED

Dear all,

Today’s (Friday Oct 13) Coding and Cryptography Math 4440/5440 class is cancelled.  There will be a replacement video lecture & activities, posted on the website as soon as I am able.  My apologies for the short notice.

UPDATE:  I’m posting a video of the corresponding lecture from last year’s class on canvas, as your first task, please watch that.  It is titled “BONUS: Lecture Math 4440 10-12-2022: Introduction to polynomial arithmetic and finite fields” and appears at the end/bottom of the default listing by creation date in the Media Gallery.  I will follow up with a daily post on here.

For Friday, October 13th, 2023

  1. Friday we are beginning some new stuff, but here’s something fun we didn’t get to do before the test: an RSA signature chain!
      1. Look up RSA signature in the lecture notes, or Monday’s video, if you need a refresher.
      2. Decide on an answer to the question “my new year’s resolution is…” which fits in 6 characters.  This is your “document” you will sign.  (I won’t hold you to it!)
      3. Look up your old public/private RSA key pair.  If you lost it, you’ll have to break your own public key to recover your private key!  (Or make a new one and replace your old one from the #public-keys channel).
      4. Turn your document into a number using text-to-integer.
      5. Sign your document (as an integer).  Post your document (as text, not integer), public key, and signature together on the #ciphertexts channel (For example, My document is ….. , my public key is A=…., and my signature is s=….).
      6. Find someone else’s signed document and verify it, then announce whether you succeeded.  If you didn’t succeed, seek help from me or them to debug the situation.
  2. Now, warmup for Friday’s class:  consider the polynomials $f(x) = 3x^2 + 2x$ and $g(x) = 3x + 1$, where the coefficients of these polynomials live modulo $5$.  What is:
      1. f(x) + g(x)?  remember to treat the coefficients mod 5.
      2. f(x)*g(x)?
      3. the remainder of f(x) divided by g(x)?  if it isn’t clear what I mean by this, what should I mean by this?

For Wed Oct 11th, 2023

  1. Reminder:  Wednesday is a test, and information is available on the “Test” tab.  I’ll be on discord as much as possible for questions while you study.
  2. Bonus office hour Tuesday October 10th, my office Math 308 at 1-2 pm.  Zoom is also an option, it worked to have the laptop open also (but give me a heads-up on discord).
  3. Use your time to study, and hand in some practice problems.  Use the spoiler feature on the #check-answers channel on discord if you want to check something with me/others, although for most computational problems you’ll benefit from finding a way to check in Sage.
  4. I’ve added a few more problems (these) to the practice problem folder.

For Friday, October 6, 2023

  1. This tool will quickly produce the iterates of a function: Pollard Rho.  Use it to demonstrate the Pollard Rho factoring method on $n=4189$.  You can use Sage to do your gcd’s, but make a nice little table on paper to demonstrate which gcd’s you are doing.  If it doesn’t work, try modifying the function slightly (e.g. x^2-1) or the starting value, etc. (Pollard rho is a very flexible method.)
  2. 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 birthday.
  3. Discrete Log Review!  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$.
      1. 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.
      2. How long should you make these lists to expect a decent probability of a collision?
      3. With reference to the last part, what is the runtime of the birthday attack on discrete log?
      4. The Baby-Step-Giant-Step algorithm is a sort of “organized” birthday algorithm.  Explain why I say this.
  4. If time remains, a fun challenge:  try to use the short message RSA attack discussed in class today on the short RSA message we had on discord (see the discord “ciphertexts” channel where I’ve pointed it out).
  5. BTW, Wikipedia shows how to obtain the birthday paradox estimate.

For Wednesday October 4th, 2023

  1. 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
  2. Look at the Quadratic Sieve Tools page.  Do these things to get familiar with it:
    1. Initialize the first box, see how it gives you n and k.
    2. Change n, see how k changes.
    3. Run the second box to get a factor base.
    4. Make your factor base bigger.
    5. Run the third box to factor things in the list k^2-n, reporting only those that factor in the factor base.
    6. Change m in the third box to get more relations.
  3. 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.
  4. 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?
  5. Suppose Eve listens in to an RSA session, so she knows Bob’s public key $(n,e)$ and the ciphertext $c$.  Suppose she computes two lists:  (a) a list of $c x^{-e} \pmod n$ for many small $x$; (b) a list of $y^e \pmod n$ for many small $y$.
      1. Explain how she can compute the message if she finds a collision between these two lists.
      2. How likely is a collision?  What would have to be true about the message for a collision to happen?