M 343 L Applied Number Theory Fall 00

Public-Key Cryptography

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

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


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 New!

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

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, 28th. 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 public exponent e and the public modulus n
  2. Find a prime p > 10100 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:

This page has been visited times since March, 8th, 2000.