UTSA logo Introduction to Cryptography
MAT 6973-01F
Summer I, 2006
Instructor: J. Iovino
 

Brief Description

The course in a basic introduction to modern cryptographic techniques. Some of the better known cryptosystems will be discussed as examples; the emphasis, however, will be on the mathematical foundations.

Intended Audience

Graduate and upper division students in mathematics, as well as computer science and statistics students who are comfortable with mathematical rigor.

Prerequisites

Real Analysis I (MAT 4213) or consent of instructor.

Content

  • Elementary number theory: congruences and residue class rings, Wilson's Theorem, Fermat's Little Theorem, The Euler phi-funtion, the Chinese Reminder Theorem.
  • Symmetric-key cryptosystems: block ciphers, stream ciphers.
  • Perfect Secrecy. The Vernam One-Time Pad.
  • Cyclic groups, primitive roots, discrete logarithms, one-way functions.
  • Cryptographic hash functions: collision-resistant compression and hash functions, arithmetical and efficient examples, the birthday attack.
  • Public-key cryptosystems: Diffie-Hellman key exchange, RSA, Rabin, El Gamal, DSS.
  • Digital signatures: RSA, Rabin, El Gamal, existential impersonation attacks.
  • Factorization algorithms: Pollards p-1 algorithm, Pollards rho algorithm, the Quadratic Sieve; refinements.
  • Other groups: finite fields, elliptic curves, quadratic forms.

    • Material covered

    6/6: Section 2.1.
    6/7: Section 2.1
    6/8: Section 2.1.
    6/12: Finished Section 2.1. Started Section 2.2.
    6/13: Finished Section 2.2.
    6/14: Perfect secrecy.
    6/19: Finished perfect secrecy. Primitive roots, I.
    6/20: Primitive roots, II. Secion 3.1
    6/21: Section 3.2.
    6/22: Section 3.3.
    6/26: El Gamal sinatures. Cryptographic hash functions.
    6/27: More El Gamal sinatures. Existential impersonation, Birthday Attacks.
    6/28: Section 5.1.
    7/3: Finished Section 5.1. Started finite fields.
    7/5: Finite fields.The projective plane. Elliptic curves on the projective plane.
    7/6: More elliptic curves.

    Assignments

    Due 6/13. Page 72: 2.6, 2.8, 2.10, 2.12, 2.16, 2.20.

    Due 6/20:

    • Page 75: 2.30.
    • Page 101: 2.42.
    • Prove that φ(n) is even for n>2.
    • Find all inteers n such that &phi(n)=2.
    • The message KYVMR CLVFW KYVBV PZJJV MVEKV VE was encrypted using a shift transformation c=m+k (mod 26). Use frequency analysis to find the value of k. What is the plaintext message?
    • The two most common letters in a long ciphertest encrypted by an affine transformation c=am+b are W and B, respectively. What are the most likely values of a and b?

    Due 6/27 (Note: This assignment was postponed until 6/28.):

    • Exercise 4.8.9 of the handout on perfect secrecy.
    • Prove that n equals the sum of all the numbers of the form &phi(d), where d is a divisor of n.
    • Page 144: 3.12, 3.14, 3.16.

    Due 7/5:

    • Prove that if ax=b (mod n) has a solution, then it has gcd(a,n) incongruent solutions.
    • Page 152, Exercise 3.26.
    • Form the handout on primitive roots: Exercises 9, 12, 15 on page 313, and 8, 9, 10, on page 319.

    Due 7/7:

    • Page 206, Exercises 5.2 and 5.4.
    • Explain why the function f(x)=ax+b is a poor choice for Pollards rho method.
    • Use polynomials to construct the Galois field of 9 elements; exhibit the addition and multiplication tables for this field.
    • Consider the group determined by the elliptic curve y2=x3+x+1 over the field of 3 elements. Is this group cyclic? Why?

    Textbook

    Mollin, Richard A. An Introduction to Cryptography. Chapman-Hall, 2001.

    Additional references

    Kenneth H. Rosen. Elementary Number Theory and its Applications. Fourth Edition. Addison-Wesley, 2000.

    Buchmann, Johannes A. Introduction to Cryptography. Undergraduate Texts in Mathematics. Springer-Verlag, 2001.

    Evaluation

    There will be five problem sets; each of them will be worth 20% of the grade. Your solutions must be the result of your individual work. All the University regulations regarding academic integrity apply.

    How to contact the instructor

    Office: SB 4.02.50

    Telephone: (210) 458-5531

    Email: iovino at math.utsa.edu

    Office hours: M, W, 4-5 pm, or by appointment.

    Valid HTML 4.0!