Math 4161: Mathematics of Cryptography - Winter 2017

Contact information:

Mike Zabrocki (zabrocki@mathstat.yorku.ca)
Course will take place in LSB 101, MWF 11:30am-12:30pm
Office: N518
office hours: W 1pm-3pm (I'm often in my office, but please email to make an appointment if you come other times)

Course description:

Cryptography deals with the study of making and breaking secret codes.

In this course we will be studying situations that are often framed as a game between three parties: a sender (e.g., an embassy), a receiver (the government office) and an opponent (a spy). We assume that the sender needs to get an urgent message to the receiver through communication channels which are vulnerable to the opponent. To do this communication, the sender and receiver agree in advance to use some sort of code which is unlocked by a keyword or phrase. The opponent will be able to intercept the message. Is he/she able to unlock the message without knowing the key?

In this course we will learn some probability theory, information theory and number theory to answer questions about how vulnerable the methods of sending secrets are. This has a great number of applications to internet credit card transactions, wireless communication and electronic voting. We will start by learning some classical codes (used up through WWI) and analyzing those. The last third of the course we will start to learn the methods that are used in modern cryptography.

Course references:

The main reference for this course is notes that will be made available as the course proceeds. The notes and the slides will be posted on the course moodle. I recommend that you print out only the part of the notes which you use (rather than printing out every scratch sheet that I post) because by the end of the course you will have close to a full book.

For those that prefer a published book, there is one by Nigel Small that has most of topics that we will cover in this course and that I think is well written and appropriate. However, I don't feel that it tracks the course closely enough to use it as a required textbook.

Cryptography: An Introduction (3rd Edition) by Nigel Smart

Course components:

The grades are based on the following components:

Quizzes (drop lowest 2 of 6)	65%
Computer assignment	10%
Final exam	25%
Total	100%

Please note that the grades will be based on a curve and will not use the absolute grading scale.
The quizzes are all open book, open notes. You should make hard copies of whatever you think you need for the quizzes. You may use a simple calculator, but not a smart phone. The final exam will be 3 hours and will not be comprehensive, instead it will be similar to an extra long quiz.
I will give you lots of practice questions to prepare for the upcoming quiz an the questions on the quizzes will be similar, but I try to make them novel. Your best way to prepare for this course is to do the practice. I will not post solutions to the practice (perhaps you will understand why once you see the nature of the questions). I can provide you with a hint or suggestion of how to solve a question if you ask by email, but you must tell me what you tried first.

Announcements:

(Jan 1, 2017) There is a moodle for this course and I will post documents there. If you are enrolled in the course you will be able to log in.

(Jan 13, 2017) I have a meeting at 2:30pm on Wednesday Jan 18 and so will be holding office hours from 1-2:30 that day. I also have a meeting scheduled February 15 and so office hours are cancelled Feb 15. If you are planning on coming to office hours or need to come some other time, it is best to send an email in advance.

(Jan 25, 2017) I've posted the scores for the quizzes in the 'text' section.

(Jan 30, 2017) I've written a sage program as a demo. Rather than post it on the moodle I want it to be accessible publicly. To use the programs that I demonstrate in class on Vigenere, paste the command:
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/vigenere.py")
into your worksheet. If you want to see the code itself (and I recommend that you look at what the functions do) follow this link.

(Feb 6, 2017) I'll update the list of programs that I have available, and give examples about how they are used but they are well documented and you should try looking at the code and see that you understand the connection between the math and the programs. You will have to use these at some point.

load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/vigenere.py")
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/index_of_coincidence.py")
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/rectangular.py")
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/plaintexts_cyphertexts.py")
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/breakmono.py")
load("http://garsia.math.yorku.ca/~zabrocki/math4161w17/sageprograms/ADFGVX.py")

For links to the source code itself: Vigenere, Index of Coincidence, Rectangular Transposition, Monoalphabetic Subtitution, ADFGVX.

(Feb 10, 2017) I worked out the bug with break mono (I had copied the updated file to the wrong directory) and all the commands above should now work. If you want to play with these programs, either download Sage to your computer OR go online and open an account on Sage Math Cloud OR run these commands from Sage Cell Server (no account required). I have taken screen shots of what it looks like to run the programs in the various setups downloaded on a computer in command line mode, downloaded on a computer in notebook mode, on Sage Math Cloud, and in the Sage Cell Server. My plan is to send the computer assignment sometime in the next week so watch for strange encrypted messages in your email.

(Feb 10, 2017) There was nothing wrong with my Vigenere code, I just didn't read the instructions. The command I should have used was
break_vig(ct_vig_4,"AAAA")
This displays 4 graphs, one for each position of the key.

(Feb 11, 2017) I've added ADFGVX encryption/decryption functions to the list of programs above. I've mentioned many times in class that I would like to see people do a project, but I haven't given any parameters about how that would work if anyone decided they wanted to do a project instead of the quizzes or final. See me if you are thinking of taking this up. I would need
1. that the final result meets certain criteria for 'working' (e.g. if the cyphertext has at least 5000 characters, this program will return English)
2. that it is written in a language that I can demonstrate in class
3. Code would need to be well documented, readable and meets standards of academic integrity
4. That I know in advance that you are planning on doing a project and that I have the chance to review and approve it.

(Feb 13, 2017) Please note that there was a grading error on question 1d of those quizzes that were labeled "Feb 3, 2017" (not those that were labeled "February 3, 2017"). This was my fault because I had a mistake on my key. If you have this quiz and would like that problem re-graded, please bring it to me next class.

(Feb 15, 2017) My meeting that was scheduled for Feb 15 was cancelled so I have un-cancelled office hours today. I'll try to remember to announce it in class today.

(Feb 27, 2017) To use the function decrypt_rt, you need to give a permutation and it should be expressed as a list of numbers (e.g. decrypt_rt(ct2, [4,1,3,2])).

(Mar 4, 2017) The assignment is due March 8. If you have not received it please let me know asap by email.

(Mar 14, 2017) I won't be able to hold office hours 1-3pm on Wednesday, March 15. I will be available after 3pm that day.

(Mar 14, 2017) You can try out my code to test if a number is prime and generate your own large primes by pasting the function that I wrote into the Sage Cell Server.

(Mar 29, 2017) The final exam for this course is Friday April 21, 2017 in ACW 005.

(Apr 13, 2017) I will have office hours 11am-12:30pm on Tuesday, April 18 and 12:30pm-2pm on Thursday, April 20.

(Apr 18, 2017) I added some more practice questions for the final since several people requested. Some of those are probably repeated, but it would take time to cut and rearrange the questions that appear elsewhere. I'm sorry, but I won't be able to post answers for these. That will take extra time that I don't have this week.

(Apr 18, 2017) I keep getting questions about what is on the exam. Almost anything having to do with number theory is relevant. You will need to be able to solve equations in to answer questions on El Gamal, DES, Knapsack and Feistel.

(May 2, 2017) I submitted grades late yesterday. I have posted on the moodle the data which I used to generate the grades (but not the actual totals themselves). I calculated them as I said that I would: 65% best 4 quizzes, 10% computer assignment, 25% final exam. I also scaled up some of the quizzes a bit to reduce the high standard deviations in the grades.

Topics:

Early Ciphers • Caesar • Vigenere • Rectangular Transposition • Monoalphabetic Substitution • Playfair • ADFGVX • Vernam’s Two Tape System • Hill Encipherment Probability Theory • Basics • Statistical Models of English Text • Random Number Generators

Codebreaking • Breaking Vigenere • Breaking Rectangular Transposition • Breaking Monoalphabetic Substitution Information Theory • Basics on the concept of Information • Entropy and Information • Fundamental Identities • Redundancy and Compression of Text • Redundancy of English Text • File and Text Compression • The Huffman Code • Perfect Secrecy Systems

Number Theory • Euclidean Algorithm • Chinese Remainder Theorem • Residue Systems • The Euler Phi Function • Primitive Roots • Quadratic Residues • Quadratic Reciprocity Law • The Jacobi Symbol • Primality Testing • The RSA Encipherment Scheme • Knapsack • Factoring Large Integers • Public Key Systems

Schedule:

Below is a rough schedule of how I expect this class to proceed and important dates.  You can expect to see this schedule revised as the course develops. You are expected to show up for lectures and be aware of any changes to the tentative schedule that I am providing for you here. I realize that the correction on the dates in class put quiz #2 on Jan 27, but in looking at the schedule it worked out better to keep it on Jan 20.

Lecture Schedule	Topics	Remarks
Friday, January 6	Introduction
Monday, January 9	classical ciphers- Caesar, Vigenere
Wednesday, January 11	Rectangular transposition, homophonic, Playfair
Friday, January 13		Quiz 1
Monday, January 16	ADFGVX, snail, Vernam
Wednesday, January 18	Hill, probability theory
Friday, January 20		Quiz 2
Monday, January 23	vocab, conditional probability, dependence/independence
Wednesday, January 25	craps, probability
Friday, January 27	probability and English
Monday, January 30	probability theory
Wednesday, February 1	breaking Vigenere
Friday, February 3		Quiz 3
Monday, February 6	breaking rectangular transposition, monoalphabetic
Wednesday, February 8	breaking ADFGVX, information theory
Friday, February 10	information theory
Monday, February 13	information theory, unicity distance
Wednesday, February 15	unicity distance, entropy of English
Friday, February 17		Quiz 4
Feb 20-Feb 24	reading week
Monday, February 27	codes and trees
Wednesday, March 1	perfect secrecy
Friday, March 3	intro to number theory
Monday, March 6	Euclidean algorithm, Euler-Fermat
Wednesday, March 8	RSA, Jacobi and Legendre symbols
Friday, March 10		Quiz 5
Monday, March 13	Jacobi symbol, primality testing
Wednesday, March 15	Diffie-Helman	office hours after 3pm
Friday, March 17	baby step/giant step, El Gamal
Monday, March 20	primitive roots, solving equations
Wednesday, March 22	examples
Friday, March 24		Quiz 6
Monday, March 27	Moebius inversion
Wednesday, March 29	cyclotomic polynomials, Knapsack
Friday, March 31	Fiestel and DES
Monday, April 3	number theory
Wednesday, April 5	number theory