Math 626 -- Schedule and Assignments



Schedule

I will try to keep to this schedule but will update it as needed.
Day Topics Preparation
Mon. 1/29 Introduction and history of cryptography .
Wed. 1/31 Attacks on Enigma, Affine ciphers Koblitz III.1,2
Fri. 2/2 Maple: we'll meet in BA120 the new computer lab. Koblitz III.1,2
Mon. 2/5 Affine digraph systems, and attacks Koblitz III.1, Stinson Ch 1
Wed. 2/7 Affine matrix systems, digraph systems, and attacks Koblitz, III.2
Mon. 2/12 Public Key Cryptography, RSA system Koblitz I.3, IV.1,2
Wed. 2/14 Attacks on RSA Koblitz I.3, IV.2
Mon. 2/19 multiplicative group of Z/pq , iterative attack on RSA Koblitz I.3, IV.2
Wed. 2/21 Digital signatures and hash functions Koblitz I.3, IV.2
Mon. 2/26 Computational complexity and big O Koblitz I.1,2,3
Wed. 2/28 Polynomial time primality tests Koblitz V.1
Mon. 3/5 Polynomial time primality tests Koblitz V.1
Wed. 3/7 Factoring, Fermat's method and generalizations Koblitz V.3
Mon. 3/19 Factor base algorithms Koblitz V.3
Wed. 3/21 finite fields, Koblitz II.1, IV.3
Mon. 3/26 primitive elements, discrete log Koblitz IV.3
Wed. 3/28 Discrete log cryptosystems Koblitz IV.3
Mon. 4/2 EXAM: Affine crypto, RSA, primality test, factoring .
Wed. 4/4 Computing discrete logs, the Silver-Pohlig-Hellman algorithm Koblitz IV.3
Mon. 4/9 The index calculus for computing discrete logs, the ElGamal Signature scheme Koblitz IV.3, Coppersmith
Wed. 4/11 Improvements to the index calculus, the Digital Signature Standard Koblitz IV.3, Coppersmith
Mon. 4/16 Knapsack cryptosystems Koblitz IV.4
Wed. 4/18 Codes and McEliece and Neiderreiter cryptosystems Li et al in reader
Mon. 4/23 Attacks on McEliece system van Tilburg article in reader
Wed. 4/25 Turing machines, P and NP.
The decoding problem is NP-complete
Berlekamp et al in reader
Mon. 4/30 Bezout's theorem as an introduction to algebraic geometry .
Wed. 5/2 Elliptic curves Koblitz VI.1
Mon. 5/7 Group law on elliptic curves Koblitz VI.1
Wed. 5/9 Elliptic curve cryptosystems Koblitz VI.2
Mon. 5/14 Data Encryption Standard Stinson Ch 3
Wed. 5/16 DES attacks, Differential cryptanalysis
Advanced Encryptions Standard, Rijndael
Stinson Ch 3
Rijndael submission to AES in reader

Assignments

Due dates may change depending on schedule.
Assignment Topics covered Due date
I: Koblitz III.1 #7,8,9,10,14,15,16 Affine ciphers and attacks Wed. Feb. 7
II: Koblitz III.2 #11,12, 16-20,22,23 Affine matrices, product ciphers, number of keys Wed. Feb. 21
III: Koblitz II.1 #2, IV.2 #6, Probs A, B, C, D below RSA and attacks, the Chinese Remainder theorem Wed. Mar. 7
Koblitz I.1 #9,10,14,15; I.2 #9-12; I.3 #7,13,15,16,21 Computational complexity Don't turn in
IV: Koblitz V.1 #5,6,18,24, V.3 #6,8,9 Primality testing and factoring Mon. Mar 26
EXAM Affine crypto, RSA
primality test, factoring
Mon. Apr. 2
V: II.1 # 7d,9, Probs. E, F below, IV.3 # 1b,3,6,10 Discrete log cryptosystems, index calculus Mon. Apr 23
VI: Koblitz IV.4 #3,5, Probs. G, Mc. below Knapsack and McEliece cryptosystems Wed. May 2
VII: Prob. H, below, Koblitz VI.1 #5 a-c, 6 (char 2), 9, VI.2 # 3, 11 elliptic curve cryptosystems Wed. May 16

Computer Projects

Here are some Maple worksheets to get you started. First, a guide with some of my notes on Maple.
Guide
Simple text: For handling text within Maple.
Text processing: For reading text from a file and writing to a file.
Ngraphs: For parsing a list of letters into a Vector of numbers.
Matrices : For rewriting a Vector as a Matrix for use with an affine matrix cryptosystem.
An example of how all of the previous stuff can be used together to set up an affine matrix cryptosystem.
Finite Fields: A few procedures and a quick example to get you started with finite fields (final version).

You should implement all of the following algorithms.
For the cryptosystems, try exchanging messages with another student.
Also, try attacking a cipher that another student sets up.

  1. Euclidean algorithm
  2. Affine cryptosystem
  3. RSA cryptosystem
  4. Discrete Log cryptosystems:
  5. Knapsack cryptosystem

The following are more complex algorithms: implement a simplified version of each, then add complexity to build up to the final algorithm. Try experimenting with varied parameters to see how the algorithm performs.

  1. Miller-Rabin primality test,
  2. Factor base algorithm,
  3. The Silver-Pohlig-Hellman algorithm for computing discrete logs,
  4. Index calculus for computing discrete logs.
For help with Maple, here are a few references:

Andre Heck, Intorduction to Maple, Springer, QA 155.7 E4 H43 1996.

R. Klima, N. Stigmon, E. Stitziger, Applications of Abstract Algebra with Maple, , CRC Press, QA 162 K65 2000.