To Know: I’ll post the assessment for Module 2 on Wednesday, with 1 week to do it. The topics include everything since Module 1, which is a lot of modular arithmetic, Discrete Log Problem and methods to solve it, Diffie-Hellman Key Exchange and El Gamal Encryption (which we’ll cover on Monday). I’ll give a more detailed list of topics shortly.

To Do:

Read Chapter 7, Section 7.2.3, which includes an example of Index Calculus (approximately 1.3 pages).

Use the Index Calculus Sage tools on the website (or your own purpose-written code) to implement Index Calculus to solve the discrete log problem 3^x = 71 (mod 127). You’ll probably want to do the linear algebra part by hand. You’ll probably want to pick B fairly small; experiment to make it easy for yourself.

To Know: This module has stretched a bit big, because there’s a lot of basic background (including runtimes, Big-Oh, lots about modular arithmetic) that we’ll build a lot of the course on. We still will talk about El Gamal and some methods for solving discrete log. I hope maybe to post the assessment early next week.

To Do: At the end of class today, I talked on the last slide about the “Birthday” attack on discrete log. The basic idea is to create two lists of elements and look for collisions (coincidences). Here is a scaffolded exercise:

To Know: The first assessment is 95% graded and you’ll get detailed solutions back, and then I’m happy to chat about the (unintionally) hard counting problem that was in there! Another day or two.

Play with the Big-O notation interactive (I think it’s fixed again now). In particular, read the text at the top of the page — it suggests a few small exercises. You need to click away from a box after changing something to get the graphs to update.

Please Read Section 3.6 (skipping 3.6.1 if you like) and 3.7 of your textbook. Please read actively.Everything here is considered part of the material we have covered. The book takes a somewhat different approach to the modular arithmetic, so this is at once the same material we have been covering, and a different take on it. One thing that is new and we will come back to, is the formula for Euler’s phi-function. The book does it depending on the chinese remainder theorem, which we haven’t covered yet, so you can skip the justification, but it is nice to look at and be able to use the formula. The rest should look like a bit of a remix of things we’ve seen. Take the time to line it up, conceptually, with the things we’ve seen (particularly the “sum-up” from the last lecture).

To hand in:

(1) Use the formula for Euler phi from the book to compute phi(15) and phi(45), showing your work.

(2) Tell me three things you learned from the reading.

To Know: If you want/need an “invite link” for the ebook version of the text, it is now listed in canvas on the main page. You shouldn’t need this, but you may find it useful if you bought the ebook version. It allows you to use a special editor for reading your purchased ebook.

To Know: On canvas, you currently have access to Chapters 2, 3 and 7. Chapter 3 has background on modular arithmetic (but without much explanation/intuition). Chapter 7 is about discrete log.

Today’s daily post is a series of exercises.

Compute 2^10223 modulo 101 by hand, showing your work (this shouldn’t be laborious). Hint: use the fact that 101 is prime to reduce the exponent with respect to a known modulus, then use repeated squaring.

These next ones go together (do these by hand):

What is the multiplicative order of 7 mod 4?

Compute 7^7 mod 4 by hand (hint: use above)

Compute phi(10) (that’s Euler phi function).

What is the multiplicative order of 7 mod 10?

What is the last digit of 7^(7^7)?

Use Sage to compute 2^110 modulo 111. Based on the answer, tell me why you can conclude 111 is not prime.

Here’s another multi-stage problem:

Ask Sage to do this: p = next_prime(10); p This computes the next prime after 10.

Next, in the next cell, ask Sage to do this: Mod(3,p)^(p-1) Explain the result.

Next, in the next cell, ask Sage to do this: Mod(3^(p-1),p) Explain the result.

Next cell, ask Sage to do this: p = next_prime(10^240); p This is a much bigger prime, and it takes Sage a moment to find it.

Next, in the next cell, ask Sage to do this: Mod(3,p)^(p-1) Explain the result.

Next, in the next cell, ask Sage to do this: Mod(3^(p-1),p) Explain the result.

By hand, using Gauss’ algorithm demonstrated in class, compute the inverse of 107 modulo 311. Here are notes from class today.

Compare your result to the result the computer provides using the Gauss Modular Inverse tool (which you will always be able to find in the website left-hand menu).

If you didn’t get it right, or your version took more steps, revisit it with another example: 40 modulo 311. Keep at it until you feel confident in your ability to do this correctly by hand.

Recall the exercises on DLP from the weekend. Please revisit these and compare to the solutions posted here. Make sure you are comfortable doing these exercises.

Revisit the algorithm you created for the last problem: finding the discrete logarithm of h modulo p, with respect to primitive root g. If you didn’t succeed at creating this algorithm, take a look at my solutions.

Now modify this algorithm so that it computes random powers of g until it happens to hit h. Have it output the total number of random guesses it needed to make before it hit h. You might want to use the Sage function randint(L,H) which returns a random integer between L and H inclusive.

Run a series of tests for different size prime p (the modulus), and various h. Note: you can find a primitive root mod p using the Sage command primitive_root(p). Make a conjecture as to the expected number of random guesses before finding h.

To hand in online: some evidence of your work above (e.g. sage code/data & guess and/or by-hand inverse computation examples).

To Know: Please use PDF, PNG or JPG formats to upload files to canvas dropboxes. Don’t ZIP or compress files. Multiple files are fine. Please make sure they are readable. There are apps like CamScanner that turn photos into nice high-contrast PDFs.

To Know: Sorry I haven’t gotten to the “biggest number” thing yet, I promise we will! 🙂

Spend a bit more time with the last daily task exercises if you had trouble with it — in particular, contact me for some personal help and advice if needed. I think for some this was quick, but for others Sage was frustrating and I’d like to help.

To hand in today: a check-in. Just a quick note about how the course is going for you and if you are frustrated/happy or have any particular concerns. A sentence or two suffices.

Don’t forget your Module 1 assessment (classical crypto and intro to modular arithmetic) is due on Monday. You’ll find it in canvas; take home test style.

To Know: You may want to use the Sage Sandbox (you can always find a link at left) for quick computations with Sage that you don’t need to save. No login required.

To Know: If you are interested in learning LaTeX, the awesome software for typsetting mathematics, read on. It’s got a little learning curve at the beginning, but I’ve designed an intro video + 45 minute self-study worksheet that I use in classes (traditionally in the computer lab, where I do the intro bit live). Click here to do it!

To Know: Thanks for your feedback on the feedback survey. I read these carefully and consider all your suggestions and really try to see if I can implement changes. I can’t always, but I try!

To Do: Follow up on our lecture in class about DLP by doing these DLP exercises (tex) (hand in to the drop box). DLP = Discrete Logarithm Problem. Note: part of the purpose of the exercise is to learn how to find sage functionality by googling etc. Sage will do a lot for you in just a couple lines if you can locate the right commands. Don’t let yourself get frustrated, though, ask me on discord.

To Know: I have lowered the threshold to 36 daily tasks out of 45 to count as 100%. See the Grading page. This is because I know life happens, so if you have to quarantine, are ill, have religious observances, etc., this should cover it.

To Know: The Module 1 assessment is open and due on Monday. Make time for it somewhere in your schedule. “Assessment” means test, so please read the honor code rules carefully.

To Know: I made an error on the very last problem on the solutions I gave to last daily’s worksheet; these have since been corrected so you can download the new version.

To Do:

Keep working on the in-class worksheet. If you attended class, work on it until you finish question 10, or until about 25 minutes have passed, whichever comes first. (If you didn’t attend class, please devote more than one hour to the daily post so you can catch up on the missed class by watching the video and then spending more time on the worksheet.)

Watch the next video Modular Dynamics: Addition in Motion (14:47). This is essentially a sum-up of the in-class worksheet on additive dynamics and serves as “solutions” to it.

Finish writing up the solutions to the worksheet up to and including question 10 based on watching the video. Hand it in to the dropbox.

As time permits, consider some of the “Further Questions” on the worksheet. This might be easier after the video. Some of these are kind of open-ended, and they are optional, but helpful.

To Know: I’ll be posting the first module (classical cryptography) assessment this weekend and have it open for a week (I’ll make it due Monday, September 14). The info about it (topics covered; edited slightly) is in the previous daily post.

To Know: If you had trouble with sage.colorado.edu (some people had the server kind of hang on them, or had trouble with tab complete or the ? command; for most it was fine), there’s an alternative called CoCalc (cocalc.com) where you can use Sage Mathematics Software for free. Unfortunately, sage.colorado.edu runs Python 2, Sage 8.4, whereas CoCalc is on Python 3, Sage 9.1. This means it can be a bit of work to transport a notebook from one spot to another. If you are computer savvy, it’s not hard to google, but I’m not going to post full instructions here. Likely, you’ll be fine if you just avoid the tab complete or ? command.

To Know: What’s coming next is more modular arithmetic, and this will involve some more proofs. I will also begin to assign exercises that may really need the aid of basic computer algorithms to avoid impossibly long work by hand. I expect that most students have a solid grounding in _either_ proofs or coding, and some of you have both. If both, great! But the course expectation is that you’ll devote some time to strengthening your weak side. So please do expect that; I’ll just try to stream that work a little: keep reading.

To Know: Here’s some description of what to cover to brush up:

PROOFS: Chapters 4-7, 9-10 of Hammack’s Book of Proof provide a comprehensive overview of the proof methods studied in MATH 2001, and should be the main background needed for the course. If you need a refresher, you could do this concurrently through the next few weeks. I will set up “proofs club” where we meet as a group to do examples and talk about proofs.

PROGRAMMING: If you’re new to programming, then you’ll want to make sure to set aside some time to work carefully through the rest of the Sage worksheet we started on Friday. It’s designed to cover basically everything you should need to do exercises in the class. But you’ll want to get more practice in the form of doing the Challenge problems in Section X. I will set up “programming club” where we can continue to work through this at a time that works for students.

To do: Having read the above, drop me an email if you want to be part of “Proof Club” or “Programming Club”. We’ll set up zoom meetings to do some extra work making sure background in these areas is solid. All optional, but you do need these skills for the course. So if you want to be in on coordination for this, then opt in.

To do: Decrypt the following ADFGVX cipher by hand using the key shown in my slides, for practice. VXDGDGDGVGGADAFXXDXDXDAAAGAG. (BTW, Do you notice how the different columns prefer different letters? With reference to the video from class, remind yourself how this type of pattern can be used for cryptanalysis.)

To know: The libraries are scanning chapters of the textbook for me to upload to canvas. But I can only have one or two on there at a time. So if you’d like to read Chapter 2, please access it soon, as it will eventually get taken down. The relevant parts of Chapter 2 for the course right now are: intro, 2.1, 2.2, 2.3, 2.4, 2.6, 2.7, 2.9, 2.12. I’ve done some picking-and-choosing, so what I’ve covered in notes/class/videos/exercises is the official material, not the book. But the book should provide a good backup resource and alternate explanation for lots of what I’ve done.

To know: The assessment for this module will open tomorrow and be due Thursday September 10th. After that there’ll be a chance to correct your errors for some increase in credit. The material covered is:

Caesar cipher and cryptanalysis (frequency analysis)

Vigenere cipher and cryptanalysis (including why it works)

Affine cipher and cryptanalysis

Hill cipher (how to encrypt/decrypt, cryptanalysis)

AFDGVX cipher (how to encrypt/decrypt)

enigma (generalities, history)

terminology as covered in the slides of Wed Sept 2 (transposition cipher, block cipher, diffusion, etc. etc.)

DES (generalities, history)

modular arithmetic, to use in practice (addition, multiplication, powers, inverses using a multiplication table)

modular arithmetic, the mathematical rigor to the definition (e.g. why the operations are well-defined), definitions of invertible, inverses, unit group.

To know: the next class will be an introduction to Sage. I’ll have a worksheet ready to go; you’ll need a web browser to log in and participate.

To know: If you are interested in classical cryptography, a nice textbook with lots of history and details is “Secret History: The Story of Cryptology” by Craig P. Bauer. Here’s a super-cool short Numberphile video about Enigma Machine.

To do: If you missed the last few minutes of class on Wednesday (I went overtime by 5 minutes), review those last minutes on the canvas video.

To do: Compare your answers to the Exercises from the last daily to these solutions. If you still have any questions, contact me (or your peers) on discord (or email).

To do: Here are some exercises (tex) to hand in on the daily dropbox. You may wish to use the Hill Cipher Tools part of the course webpage, to avoid by-hand matrix calculations.

Purely, optionally, for fun: PSNAABAEDLEDNIONPLESMELUIOEAEEMATCO (Key: one inch and a standard can of beans.)