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 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 1/25/12 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 Lab:  Computing order, inverse, fast exponentiation,  and Chinese remainder theorem       Matlab Power point 2/1/12 4 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 Review For Exam 1 2/8/12 5 (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 2/13/12 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, 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, Diffie-Hellman, and ElGamal Materials in Text: Sections: 8.1, 8.2, 8.3, 8.4 Lab: Using matlab in public key cryptosystems (3/9/12) 3/7/12 9 What do we learn? Public key cryptosystems, RSA, Diffie-Hellman, 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, Diffie-Hellman ket exchange, and ElGamal cryptosystems. 3/16/12 10 What do we learn? Discrete log and the related cryptosystems. Factoring and factorization algorithms. 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 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:00-13:00 in Room 422, Armstrong Hall) 5/3/2012