Homework 2

due Monday February 25, 2008

solutions should be submitted in the handwritten or printed form in class

Required reading

Re: Lecture 3 - Mathematical Background: Groups, Rings, and Fields

  1. W. Stallings, Cryptography and Network Security, 4th Edition


  3. A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography


Re: Lecture 2 - Rijndael

  1. W. Stallings, Cryptography and Network Security, 4th Edition, Chapter 5, Advanced Encryption Standard.

  2. Federal Information Processing Standards Publication (FIPS) 197, Specification for the Advanced Encryption Standard (AES), Nov. 26, 2001, available at http://csrc.nist.gov/CryptoToolkit/aes/, and in particular sections

Written assignment

Problem 1 (3 points)

For the cyclic group F2^4* = multiplicative group of the field  F2^4=Z2[x]/(x4+x3+1) find

a. order of the group

b. all generators of this group

c. all subgroups generated by the elements of this group.

Problem 2 (3 points)

Generate tables of logarithms and antilogarithms that can be used to speed up computations in the Galois field

GF(24) = Z2[x]/f(x), where f(x)=x4+x3+1.

Use your tables to compute

a. 'A' '7'

b. '5' 'F'

c. 'B' -1

d. 'C' 'D'-1

Problem 3 (3 points)

Perform the following multiplications in GF(28)=Z2[x]/m(x), where m(x)=x8+x4+x3+x+1. using three methods:

a. using conversion to the polynomial representation

b. using the xtime function

c. using the look-up tables of logarithms and antilogarithms

A. '08' 'B2'
B.  '17' 
C.  'EF'

Record and report the time it took you to perform each multiplication using each of the listed above methods.

Problem 4 (5 points)

Compute an output of the MixColumns transformation for the following sequence of input bytes "C0 FF EE 01". Use multiplication based on the xtime function in  your calculations.

Apply the InvMixColumns transformation to the obtained result to verify your calculations. Use the look-up tables of logarithms and antilogarithms for multiplication in GF(28).

Change the first byte of the input from C0 to C1, perform the MixColumns transformation again for the new input, and determine how many bits have changed in each output byte.

Problem 5 (3 points)

Using your knowledge about the internal structure of the ByteSub and InvByteSub transformations, verify the correctness of the following entries of the AES S-box and AES Inverse S-box:

a. S-box['02'] = '77'

b. InverseS-box['02'] = '6A'

Problem 6 (3 points)

Compute the first two round keys of AES corresponding to the 128-bit key of all zeros.