Math 373-578, Introduction to Cryptography

1.         Text: An Introduction to Mathematical Cryptocraphy, by Hoffstein, Pipher and Silverman

2.         A lab will be arranged about every other week or as needed, in Room 303, Armstrong Hall.

3.         Tentative Teaching Pace:

 Week Sections Contents

 1 1.1 What is Cryptography, Examples 2 1.2 Divisibility, Basic properties, Primes, Division Algorithm, GCD, Euclidean Algorithm, Using Euclidean Algorithm to Find GCD, Relatively prime integers.

 1.3 Modular Arithmetic: Congruence, +, - and *, Ring of integers mod m, Units, order of a unit, Primitive roots, group of units, Euler phi function, Shift ciphers, Fast powering algorithm

 3 Lab Lab: Getting along with matlab, Finding gcd, Playing with Euclidean Algorithm, Computing mod m operations, Finding multiplicative inverse mod m. Encoding with shift ciphers, Breaking the shift ciphers.

 1.4 Prime numbers, multiplicative inverse mod m, unique factorization of integers, Finite fields.

 Exam 1 (tentative)

 4 1.5, 1.7 Power of finite field elements, Primitive roots, revisited, and how to check if a number is a primitive root in a give field. Symmetric and asymmetric ciphers. 2.1 Secret and public key ciphers 5 2.2 Discrete log problem

 2.3 Diffie-Hellman key exchange

 Lab Lab: Working with finite fields, finding primitive roots 6 2.3 Diffie-Hellman key exchange 2.4 The ElGamal crypto system 2.5, 2.6 Group Theory briefed/review. Revisit Discrete Log. 7 2.7 A collision Algorithm, Baby step-Giant step Algorithm.

 2.8 Chinese remainder Theorem, Applications

 Lab Lab: working with key exchanges, Discrete log problems, and Chinese remainder Theorem Applications 8 2.9, 2.10 Pohlig-Hellman Algorithm, Algebraic structures review Exam 2  (tentative) 9 3.1, 3.2 Roots mod pq, What is an RSA system 3.2, 3.3 RSA system, and its implementation consideration, attacking RSA Lab Lab: Working with Pohlig-Hellman Algorithm and RSA 10 3.4 Primarity tests, and Factorization Algorithms Additional topics: Primarity tests, and Factorization Algorithms, (Miller-Rabin, Pollards’ p-1) 3.10 Probabilistic encryption 11 5.1, 5.2 Elliptic curves, and Examples 5.2, Elliptic curves over finite fields Lab Lab: Factorization, Elliptic Curves 12 5.3 Elliptic curve discrete log problem 5.4 Elliptic curve crypto systems 13 5.5 Elliptic curve factorizations (breaking elliptic curve cryptosystems) Exam 3  (tentative) 14 5.7 Elliptic curves over fields of characteristic 2 Additional Topics: Applications 15 6.1,6.2 Congruential public key cryptosystem, Knapsack cryptosystem 6.3 Vector space and linear algebra review Lab Lab: Elliptic Curves Cryptosystem Applications If time permits Additional Topics, Using linear algebra in code breaking, (A Project for Graduate Students) 16 Final Exam

Math 373-576: Homework Assignments

Written homework will be collected weekly. Normally we will not accept late submission of homework except that the late submission is due to illness or other unforeseen reasons. (Additional assignments will be given as the class moves forward).

 Week Assignments Due Day (Thursday of the next week) 1 Written: 1.6, 1.11, 1.14, 1.17, 1/18/18 2 Lab: 1.7, 1.9, 1,10, 1.16, 1.17, 1.25, 1/25/18 Written: 1.23(a), 1.28(a), 1,32(a), 1,34(a), (b)(i), (d) 2/1/18 3 Exam 1  (tentative) 4 Written Week 4, Homework , emailed to students 2/15/18 5 Written: 2.3 2.4, 2.6, 2.8 2/25/18 6 Lab: 1.23, 2.17, 2.18 Written: 2.10,  2.11(b), 2.23, 2.34, 2.36 (2.11(a)-(d), 2.20 for graduate students. Keep a questioning and discovering mind when working on these problems. ) 7 Exam 2  (tentative) 8 Lab: 2.28(a), (c) Written: 2.37, 2.38  (2.29, 2.33, 2.40 for graduates) 9 Written: 3.5(a), 3.5(b)(i), 3.8(b), 3.14(d), 3.23(c) (3.10, 3.34 for graduate students only) Possible additional HW (as a project) may be distributed. 10 Written:, 3.21(a), 3.24(b), 3.25(b)(d) 11 Lab: 3.1, 3.5(b)(ii), 3.6 12 Exam 3  (tentative) 13 Written5.1, 5.2, 5.5(a), 5.6(a), (5.3 for graduate students only) 14 Lab: 5.5(b)(c)(d), 5.6(b)(c), 5.7(a)(c), 5.10(a)(c), 5.13, 5.18 Written: 5.8, 5.14, 5.16, 5.17 (5.9, 5.19, 5.21 for grad only) Final Exam (same room) Please see university final exam schedule.