Check out the last daily post for info on a Module 1 retake. I’ve set up an appointment calendar (link is on the canvas main page where private links are kept). Choose a 15 minute slot and put your name and what problem you want to redo (one of the Part B long answer problems).
Let me know if you’d be interested in an opportunity for extra credit if you either (a) program all the algorithms of the course or (b) fill in proofs to a variety of results of the course. If so, I’ll design an assignment along these lines. Both are productive things to do, depending on your interests. There’s a discord thread for discussing this.
If you’re a graduate student (or taking for grad credit), we should chat one-on-one about a final project idea at this point. Let’s be in touch.
An RSA ciphertext chain!
If you need a review of RSA, check the lecture notes, overleaf (where there’s an explicit example with Sage advice), and lecture video. 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$.
Keep $d$ safe (along with $p$ and $q$, $n$ and $\varphi(n)$ just in case) in a private file on your computer. This is your private key information.
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, and encrypt your message to that person. Post it on the #ciphertexts channel for them (use @theirname to alert them).
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).
If you weren’t happy with your Module 1 grade, don’t despair! There is an opportunity to replace one grade from among the Part B questions you attempted (four questions each worth 10 points):
If you wish to replace a grade of 7, 8, or 9, I will provide a similar problem and ask you to hand in a solution on canvas. I will announce this after I have finished the in-person replacements for other students.
If you wish to replace a grade less than or equal to 6, then we will meet in person, and I will ask you to solve a similar problem. If you wish to do this, then please schedule a time with me (zoom or in person). This time can be anytime in the next week or so, but you must contact me to schedule it before Wednesday. Just email/DM me to set this up.
Your Module 1 test was handed back Monday and solutions are on the “Archive” tab above. Please take a look through these and make sure you understand how to do the problems and what your mistakes were.
Please compare last daily to the solutions here. Make sure you understand and correct your previous work.
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.
Use any remaining time to catch up on past daily posts, or do extra examples of CRT problems (you can make up your own by just putting in whatever numbers you want, as long as the moduli are coprime, and you can always check your answer by plugging it back into the original equations).
Find the inverse of 35 modulo 61. Use the extended Euclidean algorithm.
What if we want to solve 3x + 5y = 0? The zero is the weird part. Then we don’t use the Euclidean algorithm.
Give one solution by inspection (just find a clever one).
Now give another one different from the first.
Now give infinitely many.
Find a solution to 3x + 5y = 1 (using the algorithm from class, or by guessing one).
Now find infinitely many different solutions to 3x+5y = 1. (Hint: use questions 2 and 3 above)
The goal of this exercise is to work out the runtime of the Euclidean algorithm (you may have seen this already, but do this without looking anything up):
Think of the Euclidean algorithm as replacing one pair $(a,b)$ with a new pair $(a’,b’)=(b,a-qb)$ at each step. For example, if we start with $(a,b)=(183,105)$ as on the last daily post, then we get $(a’,b’)=(b,a-b)=(105,78)$ at the next step.
Show that, if $b < a/2$, then $b’ < a/2$.
Show that, if $b \ge a/2$, then $b’ \le a/2$.
Conclude that after two steps $(a,b) \rightarrow (a’,b’) \rightarrow (a^{”},b^{”})$, the size of the first entry has decreased by at least half (so, it may have decreased more than that).
Compute the gcd of 135 and 170. Show all the steps of the algorithm, as in the video.
Compute the gcd of 183 and 105. Show all the steps of the algorithm, as in the video.
Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error.
Using the previous problem, tell me the inverse of $7$ modulo $15 and the inverse of $15$ modulo $7$. (This should require no computation, just look at the previous problem and have an aha moment!)
Wednesday is your test! Information, including suggested review, will shortly be on the “Tests” tab above.
In class on Monday, we covered Euler’s Theorem and El Gamal. To make sure you are ready for the test on these topics, here are some exercises with solutions (after the page break). You should do them without the solutions, and then only afterward compare to the solutions (of course).
I will have extra office hours Tuesday 12-1, in my office (Math 308).
Note! We have our first in-class test on Wednesday. More information (specific topics) is available under the “Tests” tab of this site.
In preparation for the test, the best thing to do with your hour this weekend is to go over the worksheets from last week. Each of them has solutions (all of them on the “Archive” tab), and you should make sure you understand these. One way to verify you understand is to try to re-do the sheets without looking at the solutions. This is great practice for the test.
Please hand in Friday’s worksheet on canvas in the dropbox for this daily post.
In class Friday, you will be working together to do an example of the index calculus. There’s a video on canvas entitled “BONUS VIDEO: Index Calculus” for you to watch before class. This is very important (otherwise you’ll be lost in class).
The video is around 30-35 minutes. While watching the video, pause and rewind as needed and take your time.
Bring a laptop or tablet to class to use the website Sage tools.
After you are finished, with what time remains, try to recreate the video example. You can use the Index Calculus Tools here (as I did in the video) and they generate relations randomly, so you will end up with a slightly different computation, but it should lead to the same result.
Important: in class on Wednesday we will be doing a worksheet based on the material from the videos below, so watching these before class is essential. Also bring a device (computer or ipad) to class to use the Sage tools during class.
Watch the video on canvas about Baby-Step-Giant-Step algorithm (~15 mins) under Media Gallery, titled “BONUS VIDEO: Baby-Step-Giant-Step” (note: it’s clips from a previous semester). This teaches the Baby-Step-Giant-Step Algorithm. Lecture notes.
Watch the video on canvas about Big Oh notation (~15 mins) under Media Gallery, titled “BONUS VIDEO: Big Oh”. (note: it’s a clip from a previous semester). This teaches the definition of Big Oh and begins to discuss runtimes. Lecture notes.
Watch the video on canvas about Runtimes (~10 mins) under Media Gallery, titled “BONUS VIDEO: Runtimes”. (note: it’s a clip from a previous semester). This continues examples of runtime analysis. Lecture notes.
Bring a device (computer or ipad) to class to use the Sage tools during class.
On canvas (Media Gallery Tab), there’s a video called “BONUS VIDEO: 2023-09-08 (Diffie Hellman Key Exchange in Practice)” Please watch this (~ 20 min) video. In the video, I demonstrate how to use the course website tools (on this website) to put your Diffie-Hellman public key up on the discord server, and send a message to someone there. Here are the written notes from that video.
Here are the full written instructions: you will perform a Diffie-Hellman Key Exchange in order to send a message to someone. Big picture: you’ll do a Diffie-Hellman Key Exchange to make a shared secret and then use that shared secret as a key for a very simple encryption (a sort of Caesar Cipher or One-Time Pad):
Create a secret message which is at most 6 characters long. It should answer “Why CU?” Please don’t make it longer or this exercise won’t work.
Turn it into an integer using the Text to Integer tool. (This turns it into an integer by writing the letters in ASCII and making an integer base 255 with those digits. There’s an Integer-to-Text tool on the same page to undo this process.)
We will use prime $p=10^{15}+37$, and its primitive root $g=2$. The first box in the Diffie-Hellman Tools page will initialize this modular ring for you.
Use the Diffie-Hellman Tools (second box) to find a random secret a. We’ll call this your secret key. Keep it secret, maybe in your underwear drawer. (Joking! — actually safer if you copy it into a text file on your computer, because if you write it by hand you’ll make an error.)
Compute $g^a$ using the Diffie-Hellman Tools third box (no need to do this by hand!) We’ll call this your public key.
Announce your public key on discord #public-keys. Be sure to explain this is your “Diffie Hellman Public Key” (there will be other types later).
Find someone else’s public key ($g^b$) on discord (the most recent public key on the #public-keys channel is best, so everyone gets to have part of the fun). Let’s call that other person Bob. Use it to generate your shared secret ($g^{ab}$) with Bob (you’ll need your secret key for this). Again, you can use the third box in the Diffie-Hellman Tools page to do the computations (no need to work by hand).
Add the shared secret to your message mod p. Announce the result on discord in the #ciphertexts channel as the secret message for Bob. Include your public key for them, because they will need it. You post might look like “My Diffie-Hellman message for @soandso is X.”
When someone sends you a secret message, figure out how to decrypt it and announce the result (so you can check it worked!). You may need to use the Diffie-Hellman Tools and the Text to Integer converter.
Please bring a device to class (laptop or ipad) that can use the course website Sage tools. We will be doing some work together in class in groups.
Check out last day’s solutions:
The inverse of 7 mod 11 is 8, since 7*8 = 56 which is 1 more than 55. One way to get Sage to compute this is Mod(7,11)^(-1).
The inverse of 7 mod 14 was a trick question! It has no inverse, since 7 and 14 share a prime factor.
You can verify your euler phi functions by the Sage command euler_phi(26), which returns 12. We have $\varphi(12)=4$, $\varphi(26)=12$, $\varphi(27) = 18$.
For the problems about $1, a, a^2, \ldots$, I essentially used/discussed this in lecture today, but feel free to ask more questions.
If you did some Hill Cipher problems on the last daily post, check out some exercises and solutions I’ve added to the overleaf notes, which included those problems.
I’ve updated the discord link in canvas if anyone still needs it (it last one week each time).
In what follows, hand in as much as you got done on canvas. Remember, an hour of effective, useful work is all I ask.
Quick review question: What is the inverse of 7 mod 11? What is the inverse of 7 mod 14? (Watch for trick questions!)
Compute the Euler phi functions $\varphi(12)$, $\varphi(26)$, $\varphi(27)$. For each of these $n$, verify your answer by computing the set $(\mathbb{Z}/n\mathbb{Z})^*$.
If the affine cipher key $(\alpha, \beta)$ is `badly chosen’ (i.e. $\alpha$ may not be invertible), then bad things can happen. Find an example where two different plaintexts encrypt to the same ciphertext.
Some abstract thinking about modular arithmetic. Prove (explain your reasoning) that:
If you take successive powers of $a$ mod $n$, i.e. $a,a^2,a^3,a^4,a^5,\cdots$, that eventually you will get a repeat (the same residue will appear more than once, e.g. $a^2$ might equal $a^7$). (Hint: finiteness)
If $a$ is invertible, then some power of $a$ is $1$. (Hint: use the first part somehow.)
Can you find an example residue $a$ modulo $n$ for some $a$ and $n$ where no power of $a$ is ever $1$? You might want to mess around with the various Sage tools on this site.
For remaining time (if any), you have two fun options, pick whichever seems like more fun to do first/at all:
OPTION A: Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
Read about Hill cipher. (We mentioned it briefly Friday in class).
Can you find the Hill cipher key? The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS.
Consider Hill cipher with the matrix $$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$$ modulo $26$. Can you find two plaintexts that encrypt to the same ciphertext? (The plaintexts don’t need to be english, they can just be any letters.) What’s wrong with this matrix?
OPTION B: Learn a useful new algorithm! The Double-And-Add algorithm allows for fast exponentiation, among other things; it’s a sort of refinement of successive squaring.