MATH/CMSC 456, Section 0101
Cryptology

Course web site:

Meeting times:

MWF, 10:00am-10:50am (MTH 0304). Sometimes there will be computer demonstrations in the lectures.

Instructor:

Professor Jonathan Rosenberg. His office is room 2114 of the Math Building, phone extension 55166, or you can contact him by email. Office hours are Wednesdays and Fridays after class (11AM-noon), or by appointment.

Capsule Description:

Cryptology is the study of how to transmit information securely (so that an eavesdropper cannot understand it). This is a very old subject. The Roman historian Suetonius, writing around the year 110 CE in his De Vita Caesarum, Divus Iulius, says of Julius Caesar: "There are also letters of his to Cicero, as well as to his intimates on private affairs, and in the latter, if he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others." Plutarch's Lives, another famous Roman historical work, describes a cipher used by the Spartans around 400BCE. The first rigorous treatment of cryptography was by the Belgian Auguste Kerckhoffs, whose articles on cryptographie militaire in 1883 quickly became classics. In fact, "Kerckhoffs's principles" are still quoted today. Some of the history of the subject is on display at the National Cryptologic Museum not too far from College Park. However, it is only in the modern "computer age" that cryptology has become a vital "everyday" subject and has been subjected to extensive rigorous analysis. We will explore the basic cryptographic schemes and how to analyze their security. Along the way we will cover some basic ideas from number theory and probability theory as they relate to this subject. Coding and information theory, the study of how information can be encoded and transmitted efficiently, is really a different subject, but we will need to refer to it in passing, since messages are often both encrypted and sent over noisy channels where compression and error correction are needed. There will be regular homework, some of it computer-based.

Text:

• Wade Trappe and Lawrence Washington, Introduction to Cryptography with Coding Theory, 2nd ed., Pearson/Prentice Hall, 2006.

Another useful book:

• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, Chapman and Hall/CRC, 2008.

Prerequisites:

Either two prior 400-level MATH courses or CMSC 330 (Organization of Programming Languages) and 351 (Algorithms). Except for things like very basic linear algebra, we will develop the math we need as we go along.

Course Requirements and Grading:

There will be regular homework (assigned and graded roughly once a week), most of it taken from the textbook, two in-class exams, and a final exam. The homework assignments and schedule of classes and exams are posted; though the schedule may be adjusted during the semester depending on how long it takes to get through certain topics and on class cancellations due to inclement weather. If you must miss an exam for a legitimate reason (e.g., illness, religious observance, or an event such as an official university athletic meet), please contact Dr. Rosenberg as soon as possible, preferably in advance, and a make-up will be arranged. The final exam is scheduled for Wednesday, May 19, at 8:00-10:00 am. That day is a Jewish religious holiday (Shavuot), so if that presents a problem for you, please contact me in advance about alternative arrangements. The final grade will be based on the following scheme:

These add up to a total score out of 500. The final grade will be based on this number, though if you are close to the borderline between two grades, I reserve the right to make adjustments based on class participation.

Accommodations will be made for students with disabilities, but students should inform Dr. Rosenberg of any special needs at the beginning of the semester.

Students who wish to collaborate on the homework may do so, but only in groups of two or three students. If you do work on the homework in a small group, then only one assignment should be submitted by the group, with all names on it, and all students in the group will receive the same homework score. If you do not do this, it is assumed that you did the homework alone. Please see the university regulations on academic integrity. You are asked to write the campus Honor Pledge on your homework assignments and exams.

Your feedback on the course, to be posted at the CourseEvalUM web site by May 12, is greatly appreciated, and will help improve the course in the future.

Course Outline:

1. We will certainly cover the first 10 chapters of Trappe-Washington, except for some of the more technical sections. These cover (in order) historical cryptosystems, DES, AES, and RSA (the three most important algorithms), discrete logarithms, hash functions, digital signatures, and security protocols.
2. We will probably add a few topics from Katz-Lindell, about security and pseudorandomness, since this is closely related to the topics in Ch. 2, Ch. 8, and Ch. 9.
3. After that, I would like to cover chapter 16 on use of elliptic curves, followed by some information and coding theory from chapters 15 and 18 (in that order), depending on the time available.

Computer Programs:

Prof. Washington's web page for the text has some sample programs you can use for working on the homework, but a few things are out of date. Also, if you are using matlab, you probably don't want to have to download all the M-files one at a time. So here are updated versions, with the matlab files bundled together:

1. Mathematica notebook for Mathematica 6 or 7. A tutorial on how to use Mathematica is available here. For the problems in Ch. 16 on plotting elliptic curves, use ContourPlot in place of ImplicitPlot, which is now obsolete.
2. zip archive of M-files for MATLAB. If you have the symbolic toolbox with the Mupad engine, which is now the default (as opposed to the Maple engine, which has to be explicitly substituted if you want it), use ciphertexts_mupad.m in place of ciphertexts_maple.m. Also note that there was a bug in the old version of addell.m (used for Ch. 16), which has been fixed in this archive.
3. Mupad notebook and transcript thereof illustrating calculations related to RSA, etc.
4. Mupad notebook and transcript thereof illustrating the "low exponent attack on RSA" (using continued fractions), section 6.2.1.
5. Mupad notebook and transcript thereof illustrating the "p - 1 factoring method", section 6.4.
6. Mathematica notebook illustrating the "p - 1 factoring method", section 6.4.
7. Mupad notebook and transcript thereof illustrating the "universal exponent method" of factoring, section 6.4.2.
8. Mupad notebook and transcript thereof illustrating Diffie-Hellman key exchange and various attacks on discrete log cryptosystems.
9. Mupad notebook and transcript thereof illustrating various algorithms for computing discrete logs.
10. Another Mupad notebook and transcript thereof illustrating various algorithms for computing discrete logs.
11. Mupad notebook and transcript thereof illustrating the "baby step, giant step" algorithm for computing discrete logs.
12. Mupad notebook and transcript thereof illustrating addition in elliptic curves mod n and applications to factoring.
13. Mupad notebook and transcript thereof illustrating doubling in an elliptic curve over Q.

Computer Access:

You can of course work on any computer you want, but since Mupad is not working in all university computer labs, I got all of you accounts on the grace linux system. You can ssh to linux.grace.umd.edu and log in with your university directory ID and password. The commands tap matlab2009b and matlab will bring up a version of matlab where Mupad runs fine.