UTSA logo Introduction to Cryptography
MAT 6973-01F
Summer I, 2007
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/4: Section 1.1.
    6/5: Section 1.1.
    6/6: Sections 1.1 and 1.2.
    6/7: Section 1.3.
    6/11: Section 1.4.
    6/12: Primitive roots.
    6/13: Primitive roots.
    6/14: Primitive roots.
    6/15: Primitive roots.
    6/18: Sections 2.1 and 2.2.
    6/19: Finished Section 2.2.
    6/20: Section 4.3.
    6/21: Section 4.4.
    6/21: Section 4.4.
    6/25: Section 4.4. Probablility.
    6/26: Probablility and perfect secrecy.
    6/27: Perfect secrecy.
    6/28: Cryptographic hash functions.
    6/29: Complexity.
    7/2: Complexity.
    7/3: Secret sharing.
    7/5: Secret sharing. Pseudoprimes.
    7/6: Pseudoprimes.

    Resources

  • PARI/GP Download Page.
  • A list of basic cryptographic functions on PARI/GP.
  • Adi Shamir, Ron Rivest, Len Adleman, Ralph Merkle, Martin Hellman, and Whit Diffie in August, 2000.
  • Another photo of the RSA trio.

    • Assignments

    Due 6/11: Sections 1.1 and 1.3: 1.8, 1.20, 1.26, 1.28, 1.64, 1.66, 1.68, 1.72, 1.74, 1.78.

    Due 6/18:

    • Exercises 1.100 and 1.104 (page 43)
    • Give an alternative proof, by induction on te number of prime factors of n, of Proposition 1.7 (page 48).
    • Prove that φ(n) is even for n>2.
    • Exercises 9, 10, 14, 15, from Section 9.1 the handout on primitive roots (page 312).
    Due 6/25:
    • Exercise 2.2 (page 89).
    • Exercise 2.12 (page 103).
    • Exercise 2.30 (page 106).
    • Exercise 4.16 (page 180).
    • Exercise 4.30 (page 186).
    Due 7/2:
    • Exercise 4.8.7, 4.8.8, and 4.8.9 (page 89 of the handout).
    Due 7/9:
    • Exercises 1.31, 1.35, 1.36, 1.42 (page 78).
    • Secret sharing problems stated in class.
    • Every Carmichael number must have at least three prime factors.

    Textbook

    Mollin, Richard A. An Introduction to Cryptography, Second edition, Chapman and Hall/CRC, Boca Raton, New York, London, Tokyo, 2006. ISBN 1-58488-618-8.

    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: Tue, Wed, Thu, 4-5 pm.

    Valid HTML 4.0!