Math 373578, 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 
DiffieHellman key exchange 

Lab 
Lab: Working
with finite fields, finding primitive roots 
6 
2.3 
DiffieHellman 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 stepGiant 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 
PohligHellman 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 PohligHellman Algorithm and RSA 
10 
3.4 
Primarity tests, and Factorization Algorithms 


Additional
topics: Primarity tests, and Factorization
Algorithms, (MillerRabin, Pollards’ p1) 

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 373576: 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. 
