Math/CMSC 456, Cryptology, Spring 2017, MWF 1:00 - 1:50


Course Location: PHY 1201

Lecturer: Larry Washington (For email address, hold cursor here and look at the bottom of the page)
Office: Math 4415, Phone: 301-405-5116
Office Hours: Wednesday 11:30am-12:30pm, Thursday noon-1pm.
Book: Introduction to Cryptography, by W. Trappe and L. Washington, 2nd edition (the 2nd edition differs substantially from the first edition)

Course Description:

Cryptology is the study of the design and analysis of various encryption schemes, and related topics. The plan is to study the basics of the subject and then touch on several recent developments. Although cryptography has been used for centuries, the subject changed significantly in the 1970s with the development of public-key cyptography and the RSA algorithm, which is fundamental for today's internet security. At this point, cryptography became much more mathematical, particularly number theoretical. Many more new ideas were subsequently introduced (elliptic curves, zero-knowledge proofs, secret sharing schemes, and improved hash functions, proofs of security, for example). We'll cover all these topics, plus, as time permits, very recent developments such as pairing-based cryptography (including ID-based encryption) and homormorphic encryption. This course will not teach you how to steal passwords or how to design firewalls. Instead, it will examine the basic ideas that lie behind the cryptographic algorithms that are in use today. The basic prerequisite is mathematical maturity (at the level of someone who has done well in two 400-level courses). It will also be assumed that students are familiar with modular arithmetic, basic matrix operations, and a computer language such as MATLAB or Mathematica. The necessary number theory (for example, Euler's theorem and the Chinese Remainder Theorem) will be covered during the course.

Grading: Homework 15%, Two midterms: 25% each, Final: 35%

The final exam will be on Monday, May 15, 1:30-3:30pm

Homework is due by 10:59:59pm on the due date (the math building closes at 11pm). Late homework will be accepted; however, the score will be reduced by a factor of 50%.

Approximate syllabus: (subject to adjustment):

1. Construction and analysis of simple cryptosystems (affine, substitution, Vigenere, linear feedback shift registers, one-time pad and perfect secrecy)

2. Public key cryptography (RSA, finding large primes, factoring techniques, ElGamal systems)

3. The Data Encryption Standard and the Advanced Encryption Standard

4. Signature schemes (how to sign an electronic message)

5. Key distribution

6. Secret sharing schemes (design a system that can be activated by any 5 people in a group, but never by 4)

7. Hash functions

8. Zero-knowledge proofs (prove that you have some information without revealing the information)

9. Elliptic curves and ID-based cryptography

10. Homomorphic encryption

Course Related Links

Computer Programs (borrowed from Jonathan Rosenberg's website):

The web page for the text has some sample programs you can use for working on the homework. 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 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.