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

LOCATION: RLM 5.126

UNIQUE NUMBER: 57285

OFFICE HOURS: Wed 9:30 -- 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 Thu. 10/17, in class) and a final (on Sat. 12/14 7-10pm, in RLM 5.126) The two best grades from among these three will count 50% each for the course grade. Makeups will not be given.

HOMEWORK: Homework will be assigned every other week. 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 main emphasis will be on how to perform efficiently (usually with a computer) the number theoretic calculations that come up in cryptography. The prerequisites will be kept to a minimum, but previous exposure to elementary number theory or algebraic structures would be helpful. This course has a quantitative reasoning flag.

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.

Announcements

• No class 9/12.
• Review class 10/15.
• Review class 12/5.
• Material for midterm. Sections 1.2, 1.5, 2.2, 2.3, 2.4, 2.7 and 3.4 of the textbook.
• Material for final. Final is cumulative. In addition to the midterm material (see above) it will also cover sections 3.1, 3.2, 3.3, 3.5, 3.6, 5.1, 5.2, 5.3, and 5.4 of the textbook.

Homework

• Chapter 1, problems 1.9, 1.21, 1.24, 1.25, 1.32(c) due 9/19.
• Read section 2.1 of this paper (you won't need to read the rest of the paper!). Check the number theoretic assertions there. Namely, verify that p=2³²+15 is prime and that 3 is a primitive root modulo p. Is 2 a primitive root modulo p? Justify your answer. Justify the statement that there are approximately 10⁹ primitive roots modulo p. For what values of x, will 3^x modulo p fall outside of the range of valid IPv4 addresses, which is between 1 and 2³²-1? Choose another primitive root mod p and answer the last question again with 3 replaced by the primitive root you chose. Due 10/3.
• Chapter 2, problems 2.6, 2.8, Chapter 3, problems 3.13(a), 3.14(a),(b) (d), due 10/22.
• Chapter 3, problems 3.6, 3.7, 3.21, 3.23, due 11/5.
• Chapter 5, problems 5.8, 5.10 (b),(d), 5.13 and 5.18 (b),(c). Due 11/21.

Some links:

1. PARI/GP homepage.
2. Log file of pari/gp class on 9/19.
3. Log file of pari/gp session on 10/3.
4. Digital Signature Standard.
5. Presentation on advances in discrete logs. Discusses consequences for cryptography in a somewhat hysterical tone.
6. Factoring RSA keys by gcds.
7. An intuitive explanation of asymmetric cryptography.
8. Elliptic curve java applet.
9. Breaking ECC2K-130 Also here.
10. RSA-210 factored.
11. Log file of pari/gp session on elliptic curves on 11/14.
12. Log file of pari/gp session on Lenstra's algorithm on 11/26.

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. If you need special accomodation for an exam, please bring me a letter from SSD at least three weeks before the exam.