M 343 L Applied Number Theory Fall 01

Public-Key Cryptography

INSTRUCTOR: Felipe Voloch (RLM 9.122, ph.471-2674)

COURSE WEB PAGE: http://www.ma.utexas.edu/users/voloch/mathinfo3.html.

CLASS HOURS: Tue, Thu 11:00 -- 12:30 RLM 6.104


OFFICE HOURS: Wed 10:00 -- 11:30 or by appointment.

TEXTBOOK: P. Garrett, Making, Breaking Codes. Prentice Hall. Here is the author's errata to the book.

FIRST DAY HANDOUT: First day handout.

NOTE ON PREREQUISITES: The university's course schedule lists the prerequisites for this class as being 343K and 328K. This is incorrect. It should have said 343K or 328K, but anyhow the prerequisites are flexible. If you are not sure whether you have the right prerequisites, please contact me.

EXAMS AND GRADE POLICY: The grade will be determined from homework, a midterm and a final. The two best grades from among these three will count 50% each for the course grade. The midterm will be on Thursday, October, 25th during class time and the final on Saturday, December 15th at 9AM. Makeups will not be given.

HOMEWORK: The homework will have two parts. One part, worth 40% of the homework grade will consist of problems that will be assigned periodically in class and will be due a week after they are assigned. The other part, worth 60% of the homework grade, will consist of a computer project. The computer project will be assigned on October, 16th and will be due on November, 29th.

COURSE DESCRIPTION:The purpose of this course is to introduce students to applications of Number Theory to Cryptography. This topic addresses the problem of preserving data integrity during transmission or storage against malicious attacks. Security on the Internet is a hot topic and it is all based on interesting mathematics. The prerequisites will be kept to a minimum, but previous exposure to elementary number theory or algebraic structures would be helpful.

Topics to be covered:

Basic properties of integers. Prime numbers and unique factorization. Congruences, Theorems of Fermat and Euler, primitive roots.

Primality testing and factorization methods.

Cryptography, basic notions. Public key cryptosystems. RSA. Implementation and attacks.

Discrete log cryptosystems. Diffie-Hellman and the Digital Signature Standard.

Other Public-Key algorithms, such as NTRU.


  1. Due Sept. 18th. 1.1.03, 1.1.07, 1.3.05, 1.4.02, 3.1.01, 4.1.01.
  2. Due Sept. 27th. 10.2.02, 10.2.05, 12.5.02, 12.5.06, 7.3.02, 7.3.04, 13.2.03.
  3. Due Nov. 8th. 10.4.01, 10.4.02, 20.5.05.
  4. Due Nov. 15th. 17.6.02, 17.6.09, 17.6.10, 22.2.04, 22.4.01.

Computer project

Solutions now available, see below.

Do the following projects on the computer of your choice, using the software of your choice and send me the results by e-mail by November, 29th. Make sure to include your name in your message. The big numbers are in the following text file.

  1. Encrypt your social security number (no dashes) using the El-Gamal public key cryptosystem with parameters p, g=5 and ga.

  2. Find a composite number which is a strong pseudoprime to all bases b satisfying 1 < b < 10. (Hint: try numbers of the form (n+1)(2n+1)).

  3. You have discovered that an user with RSA public key n and e=17 has decryption exponent d. Factor n.

Some links:

This page has been visited times since March, 27th, 2001.