Math 4450/6450, Introduction to Cryptography

Spring 2004

• Instructor: Matt Baker
• Time and place: TuTh 11:00 A.M. - 12:15 P.M, 322 Boyd
• E-mail: mbaker@math.uga.edu.
• Office: 440 Boyd
• Office Hours: Tuesday 4-5, Wednesday 1:30 - 2:30

Course texts:

• "Introduction to Cryptography with Coding Theory" by Wade Trappe and Lawrence C. Washington (primary text)
• "The Code Book" (plus "The Code Book CD-ROM") by Simon Singh

Final exam:

• Download the final exam here (pdf format).

Tenth homework assignment:

• Trappe-Washington Section 15.6 # 2,6,12
• Trappe-Washington Section 15.7 # 1,5

Ninth homework assignment:

• Download the assigment here (pdf format).

Eighth homework assignment:

• Download the assigment here (pdf format).

Seventh homework assignment:

• Download the assigment here (pdf format).

Useful Links:

• Boris Alexeev's substitution cipher decryption tools
• Eric Morris' decryption tools
• Quadratic sieve survey paper
• MSRI streaming video lecture by Carl Pomerance on "Smooth Numbers and the Quadratic Sieve"
• Papers about factoring
• RSA survey paper
• Andrew Granville's survey paper on primality testing (accessible from UGA only)
• The AKS algorithm (links to original paper and news articles)
• The Prime Pages website
• Primes is in P (expository paper by R. Schoof)
• Information about the Enigma cipher
• Resources for undergraduate mathematics majors

Prerequisites:

Math 4000 or equivalent. No previous coursework in number theory or computer programming is required, but may be helpful.

Course outline:

For centuries, cryptology, the science of secret codes, has been almost solely in the realm of government and the military. With the advent of electronic communication and commerce it has become vitally important to have secure cryptographic systems available to ordinary people. Many of the modern methods that are in use or have been suggested are based on computational problems in number theory and algebra, especially factoring large numbers and the "discrete logarithm" problem (given two elements in a group with one a power of the other, find the exponent). In this course, we will take a tour of various cryptographic systems (both classical and modern), learning their strengths and weaknesses. Along the way, we will study modern algorithms for recognizing prime numbers, factoring composite numbers, and computing discrete logarithms. The mathematical structures introduced will include finite fields and elliptic curves.

Exams:

There will be a take-home midterm and a take-home final exam.

Homework:

Homework will be assigned on a regular basis. There will be some reading assignments and some computer-based projects as part of the homework. Students taking the course at the 6000 level will be assigned some extra problems, and will also be expected to write a short (roughly four pages) expository paper on a topic of their choosing.

Grading Policy:

Homework will account for 50% of your course grade, the miderm 25%, and the final exam 25%.

Collaboration:

On the homework sets, collaboration is both allowed and encouraged. However, you must write up yourself and understand your own homework solutions. On the midterm and final exams, collaboration is not permitted.

Miscellany:

If at any point during the semester you feel unsatisfied with some aspect of the course, please come talk to me about it! I have no problem making adjustments mid-stream if necessary. This course is supposed to be highly informative and, above all, fun.