Cryptography Homework

General Information

Please do the Introductory Questionnaire (URL now correct and active!) by this weekend, so I can look at the results.  You must click the submit button and see a thank-you message for it to complete successfully.

Hw 1, Due Sept 9:  Groups of 2 allowed
1.12: 2, 4 (Python function), 6, 20 (not a program since it is an infinite sequence - just use words and symbols to define it recursively.  Hint: it is actually easiest to find the smallest possible numbers to put in the sequence.)
Problem A:  Code xgcdr: extended gcd, done by recursion. (Hint - works backwards from the base case like gcdr, but there is a bit more to do for the extended coefficients.)

Hw 2, Due Sept 16, Groups of 2 allowed
From the end of FiniteFields.pdf: 2, 4, 5ab, 6, 8

HW3:  Due Sept 23, Groups of 2 allowed.  Make sure code is in a .py file, and is executable and tested, and runs tests automatically when run as a script/main program.  That means there should be code calling the tests after
if __name__ == '__main__':
The easiest thing to do is doctests, with tests in the doc strings in each function/method that you write. If you prefer to write a separate special testing function, make sure it gets called.
1: Prove that if an element of Z/nZ is a zero divisor, then it has no multiplicative inverse.  Hint:  suppose a and b are not 0, ab = 0, and a-1 exists.  Consider the expression a-1ab and use basic ring properties to show there is a contradiction.
2: Give a direct proof, by counting, that φ(pq) = (p-1)(q-1) for p and q distinct primes.
3:  By hand (presumably using formulas we have discussed) calculate φ(14000)
4:  List Z/36Z*, the multiplicative subgroup of the integers mod 36.  List distinct representatives in 1, 2, ..., 35.
B: Coding:  In mod_arith1.py, improve the naive versions of these methods. 

C: Code the solution of the Chinese Remainder Theorem in Python, using xgcd.  You can do it in either of two forms, without the Mod classes or with.  The first corresponds to the original statement of the theorem closely.  The latter states the problem in an object oriented fashion and provides an opportunity to use the Mod classes. In the second version, for testing purposes remember that the most concise way to generate an object representing 3 mod 4 is ZMod(4)(3).

def CRT(a, n):
    '''Return the solution to the Chinese Remainder Theorem.
    Parameters a and n are lists of integers of the same positive length,
    with each element of n positive and coprime.
    Return the smallest nonnegative integer x so
    x mod n[i]  = a[i] mod n[i] for each index i.
    '''
   

def CRTM(mods):
    '''Return the solution to the Chinese Remainder Theorem as an element
    of a Mod class, x mod N.  The parameter is a nonempty sequence of
    Mod class instances, where all the parameter moduli are coprime.
    N is the product of the parameter moduli.
    For each element a mod m of mods, x satisfies: a mod m equals x mod m.
    '''

Reading homework before the Sept 23 class:  Buchhmann, Chapter 3, through Section 3.6.  Come ready with questions about what you have read.

HW4:  Due Sept 30, Groups of 2 allowed.
Follow code file and code testing guideline from HW3 henceforth unless other special insructions are given.

1.  Convert the mod 17 linear systems to one matrix, and display it for me, and solve via an appropriate variant in gaussJordan2.py, and convert both answers back to say for System 1, v=__, w = __, ....
and for System 2, v=__, w = __, ....
System 1:
 2v +  5w -  6x +   y       = 10 
  v -  7w - 10x +  9y -   z =  0
-3v -   w + 11x +  2y +  9z = 11
  4v +  9w -   x +   y +  3z =  2
  v + 12w + 15x +  2y -  8z =  5
System 2:
 2v +  5w -  6x +   y       =  3
  v -  7w - 10x +  9y -   z =  9
-3v -   w + 11x +  2y +  9z = 15
  4v +  9w -   x +   y +  3z =  4
  v + 12w + 15x +  2y -  8z =  1

You can display the matrix either in just a geometric layout, or as a Python matrix (list of lists).  You can immediately use the latter.

2.  Prove:
If m is an kxk matrix with Z/nZ elements, and for some index i, gcd(n, m[0][i], m[1][i], ..., m[k-1][i] ) > 1,
then m is not invertible.

3.  Explain clearly why my gauss_jordanModPow2 works, including giving answer False when it should. The discussion should center on places where a multiplicative inverse is calculated, or cannot be calculated.  In other respects it is like gauss_jordanExactField, which you can assume does work.

D. Code.  Fill out the two functions in the stub ASCII2.py.  In particular the doctests that I have already included should work.

E, E+ postponed to HW6, after some more hints/background
Read throgh 3.15.3

HW5:  Due Oct 7, Groups of 2 allowed.
5.1:  Buchmann 3.16.6
5.2 Assuming my version of caesar ciphers in caesar.py,  what is the plaintext and the key for this ciphertext?
'TBI D?XBR YIK'
5.3 Assuming the alphabet of capital letters, as in Buchmann, If an affine linear cipher v -> Av + b mod 26 with block length 3 maps plaintext ENCRYPTAGAIN to ciphertext BLOCKCIPHERS, what are A and v?  Use the methods of 3.14.  Feel free to let Python do the matrix calculations with gaussJordan2.py, and also the conversion to and from letters and Mod 26 using capLetCode.py.   Note addition of  affineEncrypt, affineDecrypt functions to capLetCode.py,  correction/addition to shell record for breaking affine code in class, affineCrypt.txt, and also gaussJordan26.pyc, gaussJordan27.pyc which include solutions to HW4 E+, for use in this problem. 

331 students:  a specific numersolution for this specific example is sufficient.  431: see below

331 extra credit and 431 all:  Write general code that will produce matrix A and vector v if given block size k and plaintext and ciphertext of length k*(k+1) in the uppercase letter alphabet. This only needs to work in the cases where there is an invertible matrix.  Test it with the example above and another one with a larger k.

HW6:  Due Monday, Oct 18.  Groups of 2 allowed:
6.1:  Find all Carmichael numbers less than 50,000.  I give you an aid:  factoring.py includes factor(n) providing a list of factors for n.
6.2:  Code showsComposite(n, a) which is true if a <n and a is shown to be a witness to the compositeness of n or if gcd(a, n) > 1. 

No homework due Thursday, October 21.  See the Midterm Topics.  Do bring notes to the exam!

HW7 due Thursday Oct 28 (Groups of 2 allowed)
1.  Find all irreducible polynomials of degree 1, 2, and 3 over Z/2Z. (Hint: 3 is the highest degree for which some factor of a reducible polynomial P must be of degree 1, meaning a factor of x or x+1, and these are factors of a polynomial P respectively if  P(0) or P(1) is 0.)
2..   Consider the field  of polynomials over Z/2Z mod x3 + x2 + 1. (slight variation on the notes example)
Show that x is a generator of the unit group (nonzero element), and label the discrete logarithms for each nonzero element.  Use these discrete logarithms to write out two columns (or rows) of the multiplication table for multiplication by x+1 and by x2 + 1 (beside your list of all the elements of the field).  What is the multiplicative inverse of  x+1?  Of x2 + 1?

HW8 due Thursday Nov 4 (Groups of 2 allowed)

1.  Note my upload of likelyPrime.py.  It includes
 Code getSafePrimes(bits, pFail) to return two random probable primes at least bits long.  Use the technique in factorAttack.pdf to get numbers that are not vulnerabe to the p-1 attack or Fermat's method.  For the latter, make sure the primes differ by at least 2**(bits-1).

2.  See added notes in classOutline about monic polymonials.  With that idea, this is a slight modification of the problem discussed in class:  Complete the function listMonicIrreducible in irredHW.py.  Make it efficient:  only test against necessary polynomials.  Only include monic polynomials.  That make the list shorter and more efficient.  For reference the file already includes code for the slower brute-force approach to checking for irreducibility.  In that verson, I just directly print the irreducible polynomials.  The file also include a function using the intToBaseList function of bases.py that simplifies generating an exhaustive list of monic polynomials.

3.  This is a really basic use of the PolyModP module:  Write and test a function generated(p):  Given an  an instance p of PolyModP, which is a non-zero element of a finite field.  (That means the polynomial and coefficient moduli satisfy the usual conditions:  polynomial modulus is irreducible, and the coeficient modulus is prime.)  Return a list of all the powers of g in order, starting from p**0, p**1, ....  An obvious place to test it is with p = PolyModP('x', 'x^3+x^2+1', 2) - from your last homework.

E. Extra credit for 331, expected for 431 (moved from HW4) :  write a working version of gauss_jordanMod, where the modulus may have any number of zero divisors. .  It must work when the determinant is invertible, and it return False otherwise.  Like in HW4#3, this centers on correctly generating invertible elements on the main diagonal, but this it trickier.  In class we should have done some samples by hand.  Those should be generalizable.  See the revised classOutlinenotes,with addition I made after class, incorporating some of what we put on the board and in my comments.  As in HW4#3, for full credit you must prove that the algorithm works when it should, and returns false when it should.  See the last two examples at the end of gaussJordan2.py for examples to follow by hand and then generalize.

E+  This is an extra credit version of E (extra credit for all).  The notes in the class outline suggest an approach with an extra level  of looping, going step by step, doing whole row operations at each step in the gcd algorithm.   For this version get rid of the extra  loop of whole row operations, and prove this version works.  If you are confident of your E+ solution, it can replace the basic E solution.  You may quote as facts the information in the documentation string for mgcd.

HW9 due Thursday Nov 11 (Groups of 2 allowed)

1.  See ElGamalIntHW.py and complete the function stubs.
2.  Code the Shanks baby/giant step algorithm for discrete log by completing babyGiantModP in shanksHW.py.  For simpliciy assume over Z/pZ for prime p. 

HW10 due Thursday Nov 18 (Groups of 2 allowed)
1.  For 1 point of credit, repeat of Hw8 problem 2.  Satisfy both requirements as discussed in class:  Only test against monic irreducible polynomials, and stop testing polynomials, based on their degree, when they cannot help eliminate the current polynomial you are testing.  As with integer factoring, you do not need to test the"larger" (in the sense of degree) factor of a polynomial.  Make sure you irreducible list has monic polynomials from degree 1 and all degrees < n.
2.  Code PohligHellman and getX for arbitrary group elements in the revised PohligHellman.py,  Add tests both with elements that are in modular arithmetic fields and other tests using PolyModP fields.
3.  Complete rabin.py, filling in the two function stubs and addin testing.  Your findIrreducible should generate random polynomails and test them using isIrreducible, until an irreducible one is found.  You can use intToBaseList function in bases.py to succinctly generate a random polynomial with only one call to random.randint.  The shell testing history from class is at RabinShell.txt.  Updated for more efficient powers with modulus.  Old version RabinShellSlowString.txt

HW11 due Thursday Dec 2 (Groups of 2 allowed) 2 points for each of the two methods.
Complete secretshareHW.py.  I wrote under 15 lines (aside from finding the bug I made in secretShareDecrypt, that I warn you about in the documentation).  The initial version was not the most general possible:  The decryptions will not work if the original polynomial has too high degree, but we decrease the set of possible solutions if we insist the random polynomial is of degree equal to n-1.  The restriction should just be that it is of degree at most n-1.
Remember the Python syntax for iterating though a list of pairs:
for xj, fxj in pairs:
    ...

HW12 due Thursday Dec 9 (Groups of 2 allowed)
1.  Buchmann 2.23.22.   Remember Lagrange's Theorem
2. Buchmann 4.8.6
3.  Diffe-Hellman + one time pad.  I coded 95% of of it!  Complete diffehellmanHW.py (2-3 lines needed).  Uses ElGamalInt.py (HW solution)  Make sure you follow my test code.

Remember the course surveys.  Links to both are there.