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.
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.
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.)
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.)
To know: I made a Vigenere Cipher video. Watching is optional. This is meant to explain the cryptanalysis. I felt something was lost in translation during class, so I made an attempt to tease it apart in further detail so you can make sense of it. If you don’t feel really confident about the keylength explanation (i.e. why it works), then go to 3:36 in the video
To know: daily posts won’t be accepted late. Don’t worry, I drop a bunch because life happens to everyone, so it’s ok to miss a few.
Your first daily task today is to be done without any aids or research. Get a blank sheet of paper and, without looking anything up or looking at anything, write down the biggest finite positive integer you can. It must be well-defined. That is, it must be possible, in theory, to compute (with arbitrarily much computation power and memory) the integer. And if you are going to give a famous named number, you must give its definition (no “I remember some big number called X”; you need to define it). The winners — the biggest numbers, if I can determine them — will get some points toward prizes of dubious value at the end of semester; no grades involved. Hand this in on canvas.
For the rest of today I have some exercises for you (not to be handed in; but I can provide solutions upon request). Whenever I assign exercises, do as many as an hour affords for the dailypost, and do the rest as part of your studying for the course, when time permits.
(Exercise 1) Suppose you have a known plaintext situation for affine cipher. The plaintext is HAHAHA and the ciphertext is NONONO. Determine the key. Hint: write down some equations modulo 26 that must be true and try to solve for the key. Use the Crypto Tools Sheet (addition and multiplication tables mod 26) in solving.
(Exercise 2) Suppose you have a known plaintext situation for affine cipher. The plaintext is III (that’s 888, in case there’s any confusion) and the ciphertext is QQQ. Explain why this is not enough information to determine the key.
(Exercise 3) Suppose you have a known plaintext situation for affine cipher. The plaintext is BO and the ciphertext is OB. Explain why this is not enough information to determine the key.
(Exercise 4) I decide to make affine cipher more secure by encrypting first with one key, and then encrypting again using another key. Is there any reason this is more secure? Why or why not?
A note about daily posts! Sometimes the tasks may take more than hour, or be frustrating. In these circumstances, you should feel you have done your due diligence after one hour and hand in what you have (maybe skip over the frustrating task at first). Then you can come back to them later sometime.
Exercise: What one-time pad key is needed to make the ciphertext ABC decode to WHY? What one-time pad key is needed to make it decode to NOT?
Watch this 3 minute video description of the Affine Cipher (titled “Daily Due Monday August 31st: Quick Initial Description of the Affine Cipher” on canvas Media Gallery).
Do the associated worksheet in advance of next class. We’ll take the worksheet up at the beginning of next class.
Using only by hand computations and the “Cryptanalysis Tools” (menu at left), which automates certain computations, decrypt the first few words of the following Vigenere cipher: text file of ciphertext. (Funny, my browser thinks it is Hungarian!) Keep a record of your work (i.e.. paste the results and annotate your steps in a text file).
Note on the above: you shouldn’t need to do anything too much by hand; the tools above will be all you need to find the key (just cut-n-paste strings as needed). For the final decryption, you’ll have to do that by hand, but just do a few words to prove it is english to prove the key is correct!
For the completion check, upload your record of your vigenere decryption, and your exercise and worksheet answers (you can type the exercise and worksheet answers, which are just text, in at the end of the vigenere decryption file so it’s just one file).