M 343 L Applied Number Theory Fall 00

CLASS HOURS: Tue, Thu 9:30 -- 11:00 RLM 5.114

UNIQUE NUMBER: 55540

OFFICE HOURS: Wed 10:00 -- 11:30 or by appointment.

TEXTBOOK: S. C. Coutinho, The Mathematics of Ciphers, AK Peters 1999.

NEWSGROUP: utexas.class.m343l

EXAMS AND GRADE POLICY: The grade will be determined from a computer project, a midterm, and a final. The two best grades from among these three will count 50% each for the course grade. The computer project will be assigned on October, 3rd and will be due on November, 28th. The midterm will be on Thursday, October, 19th during class time and the final on Saturday, December 16th at 7PM (no kidding!). Makeups will not be given.

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.

Computer Project

1. Encrypt your social security number (no dashes) using the public exponent e and the public modulus n
2. Find a prime p > 10¹⁰⁰ such that p+2 is also prime and such that p is congruent to 1 modulo 1234.
3. Alice and Bob are exchanging a secret key using Diffie-Hellman with prime p, and primitive root g=19. If Alice sends Bob the number A and and Bob sends Alice the number B, what is their common secret key?

Some links:

• Pari-gp 1.39 code for the Index calculus (don't laugh!).
• Midterm with solutions.
• final.
• 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.
• Prime page.
• Twenty Years of Attacks on the RSA Cryptosystem, by D. Boneh.
• RSA Laboratories and their FAQ.
• Certicom and their elliptic curves tutorial.
• NTRU and their FAQ.
• Pari.
• Information about using Pari in the Math. dept. system by L. Finotti. NOTE: This is from another course, but it has useful tips.
• The Cayley-Purser algorithm.
• The new AES (advanced encryption standard) algorithm has been chosen.