M 343 L Applied Number Theory Fall 10

Cryptography

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

)

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

LOCATION: RLM 5.126

UNIQUE NUMBER: 55475

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

TEXTBOOK: An Introduction to Mathematical Cryptography by Jill Pipher, Jeffrey Hoffstein, Joseph H. Silverman.

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 (on 10/14, in class) and a final (on 12/13, 2:00-5:00 PM, NOA 1.124) The two best grades from among these three will count 50% each for the course grade. Makeups will not be given.

HOMEWORK: Part of the homework will consist of computer projects.

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.

Basic Number Theoretic Algorithms. Euclidean Algorithm, Modular Exponentiation. 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.

Homework

Chapter 1, problems 1.2, 1.9, 1.21, 1.25, due 9/16.
Chapter 1, problems 1.30, 1.32, 1.33, due 9/23.
Chapter 2, problems 2.6, 2.8, 2.17, 2.26, due 10/12.
Chapter 3, problems 3.5, 3.6, 3.7, 3.14, due 10/28.
Chapter 3, problems 3.21, 3.23, 3.28, due 11/11.
Chapter 5, problems 5.6, 5.8, 5.13, due 11/23.

Final

Material for final: sections 1.2, 1.3, 1.5, 2.2, 2.3, 2.4, 2.7, 2.8, 2.9, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 5.1, 5.2, 5.3, 5.4.
Office hours: Friday 12/10 10:00-11:30 and 12:30-2:00
Final: 12/13, 2:00-5:00 PM, NOA 1.124

Some links:

PARI/GP homepage.
GP session from 9/16 lecture.
GP session from 11/9 lecture.
Elliptic curve java applet.
Breaking ECC2K-130 Also here.

The University of Texas at 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.