M 343 L Applied Number Theory Fall 01

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

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

UNIQUE NUMBER: 56115

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.

Homework

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

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 g^a.

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.

• New Mersenne prime found!.
• Midterm with solutions.
• Computer project with solutions.
• A script in Tcl with the Vigenere cipher and a few other things.
• Pari.
• Information about using Pari in the Math. dept. system by L. Finotti. NOTE: This is from another course, but it has useful tips.
• Pari-gp 2.0 code for Pollard's p-1 and Fermat's factoring algorithms.
• Pari-gp 2.0 code for RSA key generation, by L. Finotti.
• Pari-gp 2.0 code for Pohlig-Hellman algorithm for discrete logs.
• Pari-gp 1.39 code for the Index calculus (needs a lot of work). There is better code at P. Narula's page.
• Prime page.
• Twenty Years of Attacks on the RSA Cryptosystem, by D. Boneh.
• RSA Laboratories and their FAQ.
• Certicom and their elliptic curves tutorial.
• Federal government cryptographical standards from NIST. Includes the recommended elliptic curves.
• A list of other cryptosystems.
• NTRU and their FAQ.
• The new AES (advanced encryption standard) algorithm has been chosen. Here is a diagram of AES.
• The Cayley-Purser algorithm.