Question

Arithmetic in the AES MixColumns operation

Recall that the MixColumns operation in AES performs arithmetic on 4-byte vectors using the

polynomial M(y) = y4 + 1. In this arithmetic, we have M(y) = 0, so y4 = 1.

(a) In this part of the problem, we consider multiplication of 4-byte vectors (viewed as polyno-

mials of degree ≤ 3 whose coefficients are bytes) by powers of y.

i. Formally prove that in this arithmetic, multiplication of any 4-byte vector by y is a circular left shift of the vector by one byte.

ii. Prove that in this arithmetic, yi = yj for any integer i ≥ 0, where j ≡ i (mod 4) with 0 ≤ j ≤ 3.

iii. Use part (a) (ii) to formally prove that multiplication of any 4-byte vector byyi (i≥0)isacircularleftshiftofthevectorbyjbytes,wherej≡i(mod4)with 0 ≤ j ≤ 3.

(b) Next, we consider arithmetic involving the coefficients of the polynomial c(y) = (03)y3 + (01)y2 + (01)y + (02) ,

that appears in MixColumns, where the coefficients of c(y) are bytes written in hexadeci- mal (i.e. base 16) notation. Arithmetic involving this polynomial requires the computation of products involving the bytes (01), (02) and (03) in the Rijndahl field GF(28). Recall that in this field, arithmetic is done modulo m(x) = x8 + x4 + x3 + x + 1.

i. Write the bytes (01), (02), (03) as their respective polynomial representatives c1(x), c2(x) and c3(x) in the Rijndahl field GF(28).

ii. Let b = (b7 b6 ···b1 b0) be any byte, and let d = (02)b be the product of the bytes (02) and b in the Rijndahl field GF(28). Then d is again a byte of the form d = (d7 d6 · · · d1 d0). Provide symbolic expressions for the bits di, 0 ≤ i ≤ 7, in terms of the bits bi of b.

iii. Provide analogous expressions as in part (b) (ii) for the byte product e = (03)b, where b = (b7 b6 ···b1 b0) is any byte.

(c) The

mial c(y) of part (b). In this part of the problem, you will evaluate such products symbol- ically.

1

MixColumns operation performs multiplication of 4-byte vectors by the polyno-

i. Let s(y) = s3y3+s2y2+s1y+s0 be a polynomial whose coefficients are bytes. Symbolically compute the product t(y) = s(y)c(y) mod y4 + 1. The result should be a polynomial of the form t(y) = t3y3+t2y2+t1y+t0 where t3,t2,t1,t0 are bytes. Provide symbolic expressions for the bytes ti, 0 ≤ i ≤ 3, in terms of the bytes si. The equations should consist of sums of byte products of the form 01si, 02si, 03si, 0 ≤ i ≤ 3. You need not compute these individual byte products as you did in part (b).

ii. Write your solution of part (c) (i) in matrix form; i.e. give a 4 × 4 matrix C whose entries are bytes such that

 t0   s0   t1  = C  s1 

  t2   s2 

t3 s3

Note that this yields the matrix representation of MixColumns presented (without

proof) in class.

Answer 1