Math 373/578: Introduction to Cryptography
Homework Assignment
Text: = Introduction to Cryptography, by Johannes A. Buchmann
Week 
Problems 

Due Day 
1 
What
do we learn? What is Cryptography? Divisibility. Properties of divisibility. Primes and factorization into primes. Greatest common divisor, relatively prime integers, Euclidean Algorithm, writing the greatest common divisor of a and b as a linear combination of a and b. Materials in Text: Sections 1.1, 1.2, 1.3, 1.7, 1.8 Week 1 Homework, Week 1 Homework Solution Lab: Getting started with matlab, Exercises 1.12.15, 1.12.22 

1/13/12 
2 
What
do we learn? Congruence. Residuals modulo m. Addition, subtraction. multiplication in mod m integers (residual classes mod m). Finding multiplicative inverse and the use of Euclidean Algorithms. The concepts of semigroups, groups, rings and fields. Materials in Text: Sections 2.1, 2.2, 2.3, 2.4, 2.5 


3 
What
do we learn? Division in residual classes modulo m. Order of a unit. Subgroups. Fermat’s little Theorem, Fast exponentiation. Chinese Remainder Theorem Materials in Text: Sections 2.6, 2.8, 2.9, 2.10, 2.11, 2.12 Week 3 Homework, Week 3 Homework Solution Lab: Computing order, inverse, fast exponentiation, and Chinese remainder theorem Matlab Power point 


4 
What
do we learn? Order computation, Chinese remainder theorem (continued). Decomposition of residual classes. Multiplicative functions. Euler phifunction and its formula. Primitive root mod m. Polynomials over a field and construction of finite fields. Materials in Text: Sections 2.14, 2.15, 2.16, 2.17, 2.18, 2.19, 2.20 Week 4 Homework, Week 4 Homework Solution Review For Exam 1 


5 
Exam 1 (on 2/13/12, in Room 415, No computers nor calculators) Exam 1 Solutions Exam 1 will cover these Topics: Properties of divisibility, greatest common divisors, Euclidean Algorithm, operations modulo m, computing multiplicative inverse, solving linear and quadratic equations mod m, Chinese remainder theorem applications, Euler phi function and its computation, Fermat and Euler Theorems and their applications in exponentiation mod m, polynomials over finite fields, quickly identifying linear factors, identifying quadratic factors, determining reducibility of polynomials, finite field construction, addition, multiplication and inverse computation in Z_p[x]/(P(x)). Lab: Primitive roots, numbers to letters,
some classic ciphers encoding and decoding (Lab on 2/17/12, Room 422) Matlab
Power Point 


6 
What
do we learn? Cryptosystems. Alphabets and Words. Numbers in different bases. Classic Ciphers Materials
in Text: Sections: 3.1, 3.2, 3.3, 3.4, 

2/22/12 
7 
What
do we learn? Block Ciphers, Affine Ciphers. Matrices and Linear Maps. Encoding and decoding with block ciphers Materials in Text: Sections: 3.6, 3.10, 3.11, 3.14, Week 7 Homework, Week 7 Homework Solution Lab: Matrix computation, Matrix inverse, Encoding and decoding with linear algebra Matlab PPT Decoding Example 

2/29/12 
8 
What
do we learn? Public key cryptosystems, RSA, DiffieHellman, and ElGamal Materials in Text: Sections: 8.1, 8.2, 8.3, 8.4 Week 8 Homework, Week 8 Homework Solution Lab: Using matlab in public key cryptosystems (3/9/12) 

3/7/12 
9 
What
do we learn? Public key cryptosystems, RSA, DiffieHellman, and ElGamal. Introduction to Discrete Logarithms Materials
in Text: Sections: 8.5
Matlab PPT 


9 
Exam 2 (on 3/16/12, in Room 422, Matlab programs are needed) Exam 2 Solutions Exam 2 will cover these Topics: Coding and decoding using classic secret key cryptosystems (shift cipher, affince cipher and block ciphers). Matrices and Linear Algebra on mod m integers. Public key cryptosystems, RSA, DiffieHellman ket exchange, and ElGamal cryptosystems. 

3/16/12 
10 
What
do we learn? Discrete log and the related cryptosystems. Factoring and factorization algorithms. Week 10 Homework, Week 10 Homework Solution Materials in Text: Sections: 10.1, 10.2, 10.3, 10.4, 10.5 Lab: Using matlab in discrete log encoding and decoding 

4/2/12 
11 
What
do we learn? Discrete log and the related
cryptosystems. Factoring and factorization algorithms. Introduction to
Elliptic curves. Materials in Text: Sections: 9.1, 9.2, 9.3 

4/9/12 
12 
What
do we learn? Elliptic curve cryptosystem. . Materials in Text: Sections: 13.1, 13.2, additional material Week 12 Homework, Week 12 Homework Solution Lab: Using matlab in Elliptic curve cryptosystem computations (4/13/2012 in Room 422) Elliptic Curve Matlab 

4/16/12 
12 
Exam 3 （On 4/20/2012, in Room 422, Matlab programs are needed) Exam 3 Solutions Exam 2 will cover these Topics: Algorithms and basic theory of Discrete logarithms and Factorizations. Computing with Elliptic curves over finite fields, Elliptic curve discrete log and cryptosystems. 

4/20/12 
13 
What
do we learn? Selected Topics: more on Elliptic curve crypto systems, Hash Functions and Digital Signatures. Week 13 Homework Week 13 Homework Solution Lab: Using matlab in elliptic curve encoding and decoding 

4/27/12 




14 
Final Week (May 3 2012, 11:0013:00 in Room 422, Armstrong Hall) 

5/3/2012 



