MAT5123

From Department of Mathematics at UTSA
Jump to navigation Jump to search

Catalog entry

MAT 5123. Introduction to Cryptography. (3-0) 3 Credit Hours.

Prerequisite: MAT 4213. Congruences and residue class rings, Fermat’s Little Theorem, the Euler phi-function, the Chinese Remainder Theorem, complexity, symmetric-key cryptosystems, cyclic groups, primitive roots, discrete logarithms, one-way functions, public-key cryptosystems, digital signatures, finite fields, and elliptic curves. Differential Tuition: $150. Course Fees: GS01 $90.

Textbook

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography (2nd Ed.) Springer Undergraduate Mathematics Series, Springer-Verlag (2014). ISBN: 978-1-4939-1711-2.

Week Sections Topics Student Learning Outcomes
1

1.2, 1.3

Substitution ciphers and basic theory of divisibility.

  • Caesar’s and more general substitution ciphers.
  • Greatest common divisor. The extended Euclidean algorithm.

2

1.4, 1.5.

Modular arithmetic and finite fields.

  • Primes and integer factorizations.
  • The Fundamental Theorem of Arithmetic.
  • Modular arithmetic and shift ciphers.
  • Modular rings and finite fields 𝔽ₚ.
  • Powers and primitive roots in finite fields. Fermat's Little Theorem.
  • Fast exponentiation.

3

1.7, 2.1–2.3.

Public and private-key cryptosystems.

Cyclic groups.

Discrete Logarithms.

Diffie-Hellman key exchange.

  • Symmetric and asymmetric ciphers.
  • Encoding schemes.
  • Perfect secrecy. Vernon’s cipher.
  • Examples of symmetric ciphers.
  • Discrete Logarithms.
  • The Diffie-Hellman key exchange.

4

2.4, 2.5. 2.6, 2.7.

Elgamal public-key cryptosystem (EGPKC).

Cyclic groups.

Collision algorithms.

  • Theory of finite cyclic groups.
  • The Discrete Logarithm Problem (DLP).
  • Shanks’ Babystep-Giantstep DLP algorithm.

5

2.8, 2.9, 2.10

Rudiments of ring theory.

The Chinese Remainder Theorem.

The Pohlig-Hellman Algorithm.

  • Rings. Polynomial rings. Quotient rings.
  • Systems of congruences. The Chinese Remainder Theorem.
  • The Pohlig-Hellman Algorithm.

6

None

Review. First midterm exam.

7

3.1, 3.2, 3.3.

Modular groups of units.

The RSA cryptosystem.

Practical considerations of security in implementation.

  • Modular groups 𝑈ₙ.
  • Euler's “totient” function 𝜑. Euler's Theorem.
  • Powers and roots modulo 𝒑𝒒.
  • The Rivest-Shamir-Adleman (RSA) cryptosystem.
  • Implementation and security issues of cryptosystems: Kerchoff's Principle, Known- and Chosen-Plaintext attacks, Man-in-the-Middle attacks, obfuscation (Random-Oracle) attacks, parameter reuse.

8

3.4, 3.5.

Primality testing and factorization attacks on RSA.

  • Distribution of primes. The Prime Number Theorem.
  • Fermat's Little Theorem and Carmichael numbers.
  • The Miller-Rabin probabilistic primality test.
  • Pollard's “𝒑−𝟣” factorization algorithm.

9

4.1, 4.2, 4.3

Digital Signatures.

  • Definition and uses of digital signatures.
  • RSA digital signatures.
  • Elgamal digital signatures and DSA.

10

5.1, 5.3, 5.6, 5.7.

Probability, entropy, information theory and complexity.

  • Rudiments of combinatorics and probability.
  • Bayes's Formula.
  • Random variables and expected values.
  • Entropy of a probability distribution.
  • Perfect secrecy.
  • Complexity theory and 𝒫 versus 𝒩𝒫.

11

None

Review. Second midterm exam.

12

6.1, 6.2., 6.3

Elliptic curves and discrete logarithms.

  • Introduction to elliptic curves (ECs).
  • Elliptic curves over finite fields.
  • Fast multiples (“powers”) in ECs. The Double-and-Add algorithm.
  • The Elliptic Curve Discrete Logarithm Problem (ECDLP).

13

6.4, 6.7

Elliptic-Curve Cryptography (ECC).

Elliptic curves in characteristic 2.

  • EC Diffie-Hellman key exchange.
  • EC Elgamal PKC.
  • EC digital signature.
  • Definition and construction of finite (Galois) fields 𝐺𝐹(2ⁿ).
  • Elliptic curves over 𝐺𝐹(2ⁿ).

14

6.6

Atkin-Morain's “ECs and Primality Proving” (Math. Comp. 61 (1993) 29–68. [1])

EC-based primality testing and factorization techniques.

  • Lenstra's EC factorization algorithm.
  • EC primality certification.

15

None.

Student Presentations. Wrap-up and review.