Honors Topics in Math for the Liberal Arts: Cryptology (Fall 2009)

Instructor: Wesley Pegden (pegd[*remove*this*]en@math.rutgers.edu)
Meetings: Tuesday and Friday, 11:30AM-12:50PM, room 219 in Scott Hall on College Avenue Campus.

You do not need to buy any textbook for this course. Lecture notes are provided by the instructor instead.
Download the lecture notes here:
Part 1 (on classical ciphers),
Part 2 (on modern symmetric encryption), and
Part 3 (on public-key cryptography... preliminary version).
Please check the page of errors in the notes.
Other handouts: the syllabus, and the modulo 26 multiplication table.

Grade Breakdown: 40% Homework/Quizzes/Tests, 20% Midterm, 10% paper, 30% Final.

This course covers the mathematics of communicating secrets. We will discuss encryption schemes used thousands of years ago, as well as those used today in everyday communications.

In this course you will learn how to break real codes, and you will learn how the mathematics of cryptography has developed to make it possible to secure communication, with codes that cannot practically be broken.

We will also discuss some of the public policy and political issues surrounding the use of cryptology, including media copy protection, electronic voting machines, and international and domestic surveilance.

****Final Information****

The final exam for this course will be at 12 noon on December 16. in the normal classroom. Be sure to study the review sheet.

Homeworks

Homework 1 (Due Friday September 4)

(to be handed in)
Problems 1.1.4, 1.1.6, 1.1.8, and 1.2.2 from the notes.

Homework 2 (Due Friday September 11)

(note: due to the Labor day schedule, we do not have class on Tuesday Sept. 8)
(to be handed in)
Problems 1.4.2, 1.4.6, 1.4.8, and 1.4.9 from the notes.

Homework 3 (Due Tuesday September 15)

(to be handed in)
Problems 1.5.1, 1.6.1, and 1.6.3 from the notes.

Homework 4 (Due Friday September 18)

(to be handed in)
Problems 1.7.2, 1.7.4 and 1.7.5. You can do 1.7.6 instead of 1.7.5 for +3 bonus points, but be aware that it may be tricky, since it is so short! Note: To do 1.7.5, you should read through all of Section 1.7.3 ("Breaking the Vigenère cipher"); the problems continues a break of a cipher begun in that section.

Note that there will be a QUIZ on Friday, covering all the material from sections 1.1 through 1.6 (so, everything before the Vigenère cipher.)

Due Tuesday September 22

[graded (out of 2 points) but not counted towards final grade]
Problems 1.8.1 and 1.8.2 from the notes.

Homework 5 (Due Friday September 25)

(to be handed in)
Finish breaking the first ciphertex from the worksheet, do problem 1.8.6, and break the second ciphertext from the worksheet. (In class the following hint was given for the second ciphertext: although the most common bigram in the text, ZU, corresponds to the most common bigram in English (TH), the 4th most common bigram in the text, FJ, actually corresponds to the second most common bigram in English (HE)).

OOPS: An error in problem 1.8.6 means that decryption is not possible. On the homework, you can explain why it is not possible.

Homework 6 (For Tuesday September 29)

Not to be handed in.
Practice known plaintext attacks with the handout that was given out on Friday. Please remember that there will be a test on Friday, October 2.

Homework 7 (For Friday, October 9)

(to be handed in)
Exercises 2.2.2 and 2.2.3 from the second part of the notes.

Homework 8 (For Tuesday, October 13)

(to be handed in)
2.2.5 and 2.3.2 from the notes.

Homework 9 (For Friday, October 16)

(to be handed in)
Decrypt the message !GP?! which was encrypted with the BabyCSS cipher with 111101 as the key.

Homework 10 (For Tuesday, October 20)

(to be handed in)
Problems 2 and 3 from the BabyBlock worksheet. Any two of the problems with cipherblock chaining (4,5,6) can be done for 4 bonus points each. Friday will be a review for the Midterm, which is on Tuesday, October 27.

For Friday, October 30

Read chapter 5 from The Public Domain: Enclosing the Commons of the Mind. (Paper assignments announced)

Homework 11 (Due Tuesday, November 10)

3.1.3 from the notes.

Homework 12 (Due Friday, November 13)

3.2.2, 3.2.3, and 3.2.4 from the notes. (3.2.1 can be done for bonus points.)

Homework 13 (Due Tuesday, November 17)

3.2.5a, 3.2.5b, 3.3.1b, 3.3.2c
Note: because of an error in the notes, it was announced in class that this assignment may be turned in on Friday the 20th without penalty.

Homework 14 (Due Friday, November 20)

Problems 3.4.1 and 3.4.2 from the notes. Please note that there will be a QUIZ on Tuesday, November 24 on RSA. For the quiz, you should be able to use the Euclidean algorithms to answer questions like "what is the gcd of 527 and 901", use the extended Euclidean algorithm to answer questions like "what is the inverse of 5 modulo 106", fast exponentiation to answer questions such as "What is 5^73 (mod 300)", and be able to carry out RSA keypair generation (i.e.,: generate a public/private RSA keypair, starting with the primes p=15,q=23), as well as encrypt and decrypt using RSA (using fast exponentiation). Note that you should have the RSA protocol memorized (it is not that complicated!), and be comfortable doing modular arithmetic with reasonably large numbers, with the help of your calculator.

Practice problems for quiz

Here are some practice problems for the quiz:
Generate a keypair using RSA starting from the primes p=15 and q=23. Which key do you publish? Which key do you keep secret? Why is it bad if people learn your value for phi(n)? (phi is the greek letter phi) If you receive the message 99, what does this decrypt to?
Note that you should bring a calculator for the quiz, and be comfortable using it to solve probelms like these.

Homework 15 (Due Tuesday, November 24)

3.5.4 from the notes (3.5.3 can be done for bonus points).

Homework 16 (Due Friday, December 4)

Pick a four digit number, check by hand that it is not a multiple of 2, 3, 5, or 11, and check it using Fermat's primality test. To conclude that it is probably prime you should get the "maybe prime" outcome 3 times. (If you find it to be composite that's fine too.)
Also due are 3.8.1 and 3.8.2 from the notes.