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

A. Find the four square roots of 1 in Z_(pq).
B. Let p=29 and q=43 and consider the RSA cryptosystem with n=pq. Find a formula for d, the decrypting exponent, as a function of e, the encrypting exponent.
C. To protect against the RSA attacks discussed in class we might choose n=pq with

p=2p'+1 q=2q'+1

p'=2p''+1 q'=2q''+1

with all p's and q's pime numbers.
1. How many enciphering exponents e give distinct RSA encryptions?
2. What is the maximum possible order of an enciphering exponent, where the order is the minimal k such that X^(e^k)=X mod n?
3. How many e have this order?
4. Answer the previous three questions for the following values of n a) 722329, and b) 1,034,641.
D. For each of the following RSA keys, one of the attacks described in class is effective. Write Maple code for Fermat factorization, for attempting to find the decryption key, and for iterative attack. Then use these to factor n.
1. (n := 1571068647977, e := 61165167623)
2. ( n := 2117470765609, e := 8609599)
3. ( n := 18021426084869, e := 17907786722857)
The following two problems should be done with a partner.
I would also like to see the Maple worksheet for your work.
E. Different values of q can give fields with quite different structures. Consider q = 121, 125, 127, 128, 131.
Answer each of the following questions for each value of q. Then discuss which would be best for a cryptosystem defending against the Silver-Pohlig-Hellman algorithm.
1. Find a primitive element
2. Find the total number of primitive elements.
3. Identify all of the primitive elements.
F. In Koblitz' Exercise IV.3 #7 he says that using a Fermat prime for a discrete log system is "an astonishingly bad idea." The algorithm he describes for computing discrete logs is essentially a simple version of the Silver-Pohlig-Hellman algorithm. Write Maple code to implement the algorithm. For each of the Fermat primes 17, 257 and 65537 compute the discrete log of 5 base 3.

The following problem and Koblitz IV.3 #5 are probably best done using Maple, unless you like arithmetic. Show me the Maple code.
G. (from Stinson) Frank uses the Merkle-Hellman Cryptosystem with public key t=(1394,1256,1508,1987,439,650,724,339,2303,810). Suppose Oscar discovers that p=2503.
1. By trial and error determine the value of a such that the list t*a^(-1) mod p is a permutation of a superincreasing list.
2. Decrypt 5746.
For the following problem mimic the analysis in van Tilburg's paper.
Mc. Suppose there were an error correcting code over F_(16) with parameters n=256, and k=178 correcting t=21 errors with a computationally efficient decoding algorithm. Discuss the advantages/disadvantages of using this code in a McEliece type of cryptosystem instead of McEliece's original Goppa code with parameters n=1024, k=524, t=50 over F_2. Consider the construction of public/private keys, the key sizes, the rate of the code and the security of the cryptosystem.
H. Verify Bezout's theorem for the following pairs of curves in characteristic 0.
1. y = x^3 and x=0
2. y= x^3 and y=1
3. y= x^3-x^2 and y=x^2
4. y^2= x^3-3x and x=y^2
5. y^2= x^3 +x and x=y^2

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.

Euclidean algorithm
Affine cryptosystem
RSA cryptosystem
Discrete Log cryptosystems:
- Massey-Omura message transmission,
- El Gamal message transmission
- Diffie Hellman key exchange
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.

Miller-Rabin primality test,
Factor base algorithm,
The Silver-Pohlig-Hellman algorithm for computing discrete logs,
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.

*p=2p'+1*	*q=2q'+1*
*p'=2p''+1*	*q'=2q''+1*