Cryptography Homework

General Information

Numbered problems are in the class text unless otherwise mentioned. For instance
1.12: 2, 4, 6, 20.
refers to the section 1.12, exercises 2, 4, 6, and 20. Sometimes I will give a parenthetical comment after a problem number, either clarifying it or slightly modifying it, as I add below in the first assignment.
Read the corresponding section of the book before doing the problems. If I have not made the sections clear, ask me.
Always be mindful that particular answers are not the main point of the problems posed: The main thing is to develop the ability to understand and creatively use the ideas behind the problems. If the answer falls in your lap from an outside source, you will likely learn very little. Make sure you are thinking about your process: how you are choosing initial approaches and why the next step is being tried.
Try to work on the problems before the next class, so you are prepared to go on with new material.
I want to try using Blackboard. That means either electronic documents or carefully scanned paper and pen work, or a combination. No MS docx format. Old MS doc, open office, plain text and scanned pdf, png or jpg are fine.

Electronic submissions are due on the calendar day specified, unless otherwise stated. Paper submissions need to come during class or before class under my door.
Make sure each problem is clearly labeled. Try to keep problems in increasing order (or at least electronic document problems in order and scanned ones in order)
If for some emergency reason, you turn in a paper submission in class, staple pages, and make sure your name andwhat assignment your are turning in is on the top.
Code should work in Python 2.6.
Where an explanation or proof is required, show logic clearly, using full English and mathematical sentences. I will expect as much on quizzes and exams.
I will try to list problems just before or very shortly after the class where the subject is introduced. I may post a bit further than we get to, not knowing exactly how class will progress. Occasionally I may add an extra problem or two later. In that case I'll try to announce my intention in class, or at least in a later email.
Group work: where I allow group work, do the following:

Turn in one solution with all names at the top and a simple identifying group name.
Each group member should separately turn in a log entry with group name, your name, and a brief account of your contributions and an evaluation of the contributions of each of the others in the group.
Seeing a faster teammate's solution appear is no better than any seeing any other example. It is not kind of preparation for a later active solo exam. Take turns leading the additions to the solution. The weaker members should generally take the lead, with help in response from the team. At no time should problems be split up and worked separately, unless the solver of one is going to then play backup helper as the rest of the team works it through again.

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.

inverse(), by using xgcd
__pow__ using the squaring idea. Also allow negative powers if self has an inverse. If n is negative and self does not have an inverse, just let inverse() throw its exception. Add tests for negative exponents.

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 x³ + x² + 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 x² + 1 (beside your list of all the elements of the field). What is the multiplicative inverse of x+1? Of x² + 1?

HW8 due Thursday Nov 4 (Groups of 2 allowed)

1. Note my upload of likelyPrime.py. It includes

isLikelyPrime(n, pFail), based on the Miller-Rabin, which returns true if n is a prime with some probability > 1 - pFail.
likelyPrime(bits, pFail) producing a prime where the bit count is bits, with the same use of pFail as above.

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.