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).
Be aware that there’s a Cryptography Tools sheet available under Resources above. It has a Vigenere square, among other things, to make adding mod 26 easy.
Come up with a short (a few words) answer to the question “What’s the coolest math?” This is your plaintext.
Choose a 4-7 character word to use as a key. Make it less than half the length of your plaintext.
Encrypt the plaintext with Vigenere cipher (by hand, using the cryptography tools sheet if you like).
Post your answer on the discord channel #ciphertexts in category STUDY GROUPS, along with the key.
Choose another user’s post from #ciphertexts, and decrypt it (by hand). Post the answer in the form “So-and-so thinks the coolest math is….”
If by some chance you missed the daily post from yesterday, please catch up on it now. Modular arithmetic is a bedrock concept for the rest of the course – absolutely crucial.
I really do strongly encourage you to find partners to work with on discord. You can watch the video below with someone so you can bounce ideas around. Hop onto the text channel #study-room and just say “Hey all, I’m doing my daily post now.” Chances are someone else might be around. Or just ask on there or on the #ask-the-hive channel when you have questions. 🙂
Also, just be aware we are currently covering material that is in Chapter 2 of the text; you can use this as an added resource. Chapter 3 contains some brief explanation of modular arithmetic.
Watch my video Modular Arithmetic: Under the Hood (17:26). This gives an explanation for why everything works as described in the first video, so it should help demystify it a little. And, it offers a glimpse of what type of mathematical proof I hope you can write, coming into the course.
Therefore, your task is this: study the proofs from the video to understand them, then turn off the screen and attempt to write the theorem statement and proof yourself, in your own words. Turn on and compare, repeat, adjust, repeat. This is not to hand in, but it’s an opportunity to get more comfortable with something we will rely on during the class. Make sure none of the logical steps are mysterious — every one has a justification and a usefulness. Note: I could ask you to write these or similar proofs in an assessment.
Your final task is to write me a brief note in today’s canvas dropbox about your comfort level with the proofs from the video.
Thank you for your patience exploring discord on Monday! Wednesday will be more traditional. 🙂
If you have not already, then view the welcome video for the course, and the discord intro video (both available on the main landing page in canvas), and get set up on discord.
Read through Classroom Expectations in detail. Make sure you are set up technologically and contact me with any concerns. In particular, I’m hoping everyone will find discord useful. But I am very willing to help with your individual needs.
Make sure you have the textbook (Wade Trappe, Lawrence C. Washington, Introduction to Cryptography with Coding Theory, 2nd or 3rd edition). While you procure it, the 2nd chapter is available on canvas. I hope other chapters will be available from the library in electronic form, but this isn’t for sure yet.
Note: the next activity is to watch a video and do an accompanying worksheet. I strongly suggest working on this in groups, and collaborating on daily tasks with classmates in general. To that end, I’ve set two designated times to meet on discord (check out the STUDY GROUPS category) to do the video with peers:
Monday August 24th at 9 pm
Tuesday August 25th at 6 pm
The main activity for this daily post is to watch my video “Modular Arithmetic: User’s Manual” (9:22 mins:secs) and do the accompanying self-check worksheet. Please show your work on the last problem. Then upload a picture of the worksheet to the appropriate canvas dropbox to be checked for completeness. (Note: you don’t need to print; you can work on a separate sheet of paper if desired.)