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