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 |
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 |
p=2p'+1 | q=2q'+1 |
p'=2p''+1 | q'=2q''+1 |
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.
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.
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.