M 343 L Applied Number Theory Fall 08

Cryptography

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

CLASS HOURS: TTh 9:30 -- 11:00

LOCATION: RLM 5.126

UNIQUE NUMBER: 59020

OFFICE HOURS: Wed 9:00 -- 11:00 or by appointment.

TEXTBOOK: W. Trappe and L. C. Washington, Introduction to Cryptography with Coding Theory, 2nd edition. There is an errata on the webpage.

NOTE ON PREREQUISITES: The university's course schedule has listed the prerequisites for this class as being 343K or 328K, but 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 (to be given on Thursday, October 16th in class) and a final (to be given on Monday, December 15th 9-12, RLM 5.122). The two best grades from among these three will count 50% each for the course grade. 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 in October.

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. Elliptic curve cryptosystems.

Symmetric cryptosystems, such as DES and AES.

Announcement

The midterm is postponed to Oct. 23 and the computer project to Oct 28th.

Homework

  1. Chapter 3, problems 1, 2, 3, 4, 5, 6. Due 9/11
  2. Chapter 3, problems 12, 13, 14, 15, 16. Due 9/18
  3. Chapter 6, problems 2, 3, 4, 7, 8, 10. Due 10/2
  4. Chapter 7, problems 1, 3, 4, 7, 8, 11. Due 11/6

Computer project

  • Chapter 6 (Section 6.9) Problems 2, 4, 7, 10, 12. Due 10/28 (changed).
  • Chapter 7 (Section 7.7) Problems 1, 2, 3 and Chapter 16 (Section 16.8), Problems 1 and 2. Due 11/25.

    Some links:

    1. PARI/GP homepage.
    2. Lecture on using GP from 10/1.
    3. Lecture on using GP for discrete logs and elliptic curves from 11/18.
    4. Pari/GP script with an example of Schoof's algorithm.
    5. AKS
    6. New Mersenne prime!
    7. Secure Remote Password
    8. DNScurve, a DNS fix proposal which uses elliptic curves.
    9. Latest news on factoring with quantum computers.
    10. Elliptic curve java applet.
    11. midterm.

    The University of Austin provides upon request appropriate academic accommodations for qualified students with disabilities. For more information, contact the Office of the Dean of Students at 471- 6259, 471-6441 TTY.