[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.