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

LOCATION: RLM 5.126

UNIQUE NUMBER: 55765

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 Tue, 10/28, in class) and a final (on Wed, 12/10, 9:00-12:00, 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 during the week of 9/29-10/3.
• Review class 10/23 (for the midterm on 10/28).
• Midterm 10/28 covering sections 1.2, 1.3, 1.5, 2.2, 2.3, 2.4, 2.7, 2.8, 2.9, 3.4. Bring a calculator.
• Extra office hours Tuesday 12/9, 1-3 PM.
• Final 12/10 9-12 covering sections 1.2, 1.3, 1.5, 2.2, 2.3, 2.4, 2.7, 2.8, 2.9, 3.1, 3.2, 3.4, 3.5, 3.6, 5.2, 5.3, 5.4, 5.6. Bring a calculator.

• Chapter 1, problems 1.9, 1.19, 1.25, 1.30, 1.32(b),(d) due 9/18.
• Chapter 2, problems 2.6, 2.8, 2.10, 2.28. Due 10/7.
• Chapter 2, problem 2.17, Chapter 3, problems 3.13(a), 3.14(a),(b) (d), due 10/23.
• Chapter 3, problems 3.6, 3.9 (b), (c) and the problem described in this text file. (The last problem is inspired by this blog post: Akamai, Heartbleed and RSA). Due 11/11.
• Chapter 3, problem 3.21, Chapter 5, problems 5.5 (d),(e), 5.13, 5.16. Due 11/25. (Last assignment)

Some links:

1. PARI/GP homepage.
2. Precompiled Mac PARI/GP binary and Precompiled Windows PARI/GP binary.
3. Log file of pari/gp class on 9/18.
4. Log file of class on 10/16.
5. Log file of pari/gp session on elliptic curves on 11/20.
6. Log file of pari/gp session on elliptic curve baby-step giant-step on 11/25.
7. Sage Math cloud. How to use Pari/GP in it.
8. Small subgroup attack on Java's Diffie-Hellman implementation.
9. Digital Signature Standard.
10. Presentation on advances in discrete logs. Discusses consequences for cryptography in a somewhat hysterical tone.
11. Factoring RSA keys by gcds.
12. An intuitive explanation of asymmetric cryptography.
13. Elliptic curve java applet Link seems dead.
14. Elliptic curve plotter.
15. Breaking ECC2K-130 Also here.
16. RSA-210 factored.
17. Akamai, Heartbleed and RSA.
18. UT public key.

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.