# MAT5123

## 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 𝒑𝒒.
• 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.