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