[SOLVED] CS411 Homework3

1.  Consider GF(2⁸) used in AES with the irreducible polynomial p(x) = x⁸+x⁴+x³+x+1. You are expected to query the server “cryptlygos.pythonanywhere.com/poly/<your_id>”, which will send you two binary polynomials a(x) and b(x) in GF(2⁸). Polynomials are expressed as bit strings of their coefficients. For example, p(x) is expressed as ‘100011011’. You can use the Python code “py” given in the assignment package to communicate with the server.
2.  You are expected to perform c(x) = a(x)×b(x) in GF(2⁸) and return c(x) as bit string.
3.  You are expected to compute the multiplicative inverse of a(x) in GF(2⁸) and return a^-1(x).
4.  Consider the Geffe generator of three LFRSs (LFSR₁, LFSR₂, and LFSR₃) with the following connection polynomials:

C₁(x) = x¹⁴ + x⁵ + 1

C₂(x) = x¹⁷ + x³ + 1

C₃(x) = x¹¹+ x² + 1

You also observed the following output sequence of the Geffe generator:

z = [0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

Can you find the initial states of LFSR₁, LFSR₂, and LFSR₃?

3.  Consider the combining function given in the following table, that is used to combine the outputs of three maximum-length LFSR sequences:

F(x₁, x₂, x₃) = x₁x₂ Å x₁x₃ Å x₂x₃ Å x₁x₂x₃.

1. The lengths of LFSRs are 79, 85, and 97, respectively. Compute the linear complexity and the period of the output sequence.
2.  Analyze the function F in terms of three criteria:

• Nonlinearity degree
• Balance
• Correlation

Is this a good combining function? Explain your answer.

4.  Consider a modified AES without ShiftRow and Mixcolumn layers, where the secret key length is 128-bit. Show that with moderate effort you can break it.
5.  The cipher block chaining (CBC) mode has the property that it recovers from the errors (corruption, deletion, and insertion) in ciphertext blocks. Its encryption schemes are given as follows

Encryption primitive: C_i = E_K(P_i Å C_i-1)

Decryption primitive: P_i = D_K(C_i) Å C_i-1

How many blocks decrypt incorrectly if the ciphertext block C_i is corrupted during transmission? Show which plaintext blocks are corrupted.

Exercise for Rainbow Tables (Non-credit question)

Consider ten digests in the attached file “rainbow_table.py”, each of which is the hash of a six-character password. Your mission is to find those passwords using the rainbow table given in the attached file “rainbowtable.txt”. Complete and submit the Python code in the file “rainbow_table.py” such that it finds and prints out the ten passwords corresponding to the digests.