Math 373/578: Introduction to Cryptography


Homework Assignment

Text: = Introduction to Cryptography, by Johannes A. Buchmann





Due Day


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




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

Week 2 Homework, Week 2 Homework Solution




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




What do we learn?

Order computation, Chinese remainder theorem (continued). Decomposition of residual classes. Multiplicative functions. Euler phi-function 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




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




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,

Week 6 Homework,   Week 6 Homework Solution




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




What do we learn?

Public key cryptosystems, RSA, Diffie-Hellman, 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)




What do we learn?

Public key cryptosystems, RSA, Diffie-Hellman, and ElGamal. Introduction to Discrete Logarithms

Materials in Text: Sections: 8.5                                      Matlab PPT




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, Diffie-Hellman ket exchange, and ElGamal cryptosystems.




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




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

Week 11 Homework,   Week 11 Homework Solution




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




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.




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








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