Rijndael Notes

Rijndael Cheat-Sheet 

   Rijndael(State,CipherKey)
   {
      KeyExpansion(CipherKey,ExpandedKey)
      AddRoundKey(State,ExpandedKey)
      for (i=1;i<Nr;i++)
          Round(State,ExpandedKey+Nb*i)
      FinalRound(State,ExpandedKey+Nb*Nr)
   }

   Round(State,RoundKey)
   {
      ByteSub(State)
      ShiftRow(State)
      MixColumn(State)
      AddRoundKey(State,RoundKey)
   }

   FinalRound(State,RoundKey)
   {
      ByteSub(State)
      ShiftRow(State)
      AddRoundKey(State,RoundKey)
   }
ByteSub

  1. x->1/x in GF(2^8)
  2. x->(y^7+y^6+y^5+y^4+1)x + (y^7+y^6+y^2+y) mod (y^8+1) in GF(2)^8, that is x is written as sum_i bit[x,i]y^i.

ShiftRow

The bytes of the cipherblock are written into a 4-by-Nb array, where Nb is 4, 6 or 8. Each row is cyclic shifted by c_i, for i=0,1,2,3 according to the schedule:

MixColumn

Each column is interpreted as a cubic polynomial in GF(2^3)[x], either the entries giving the coefficents, and 

    x -> ('03'y^3+'01'y^2+'01'y^1+'02')x mod (y^4+1)

Roundkey addition

The Nb*4 bytes of the expanded key are placed into a 4*Nb byte array, in the same fashion as the cipherblock, and xor is applied cell-by-cell.

KeyExpansion

The key is copied with 4 bytes going into a word, to a linear array of Nk*(Nb+1) words. The original key is copied to 0,...,Nk-1. New words are generated, to the first approximation, by 

   W[i] = W[i-1] XOR W[i-Nk]
However, for Nk=4 or 6, every Nk-th word, starting with word Nk gets modified so that the result is 
   if (i%Nk==0)
     W[i] = SubByte(RotByte(W[i-1]) XOR Rcon[i/Nk]) XOR W[i-Nk]
   else
     W[i] = W[i-1] XOR W[i-Nk]
For Nk=8 the schedule is more involved, as half way through the 8 words, another modification is applied: 
   if (i%Nk==0)
      W[i] = SubByte(RotByte(W[i-1])) XOR Rcon[i/Nk] XOR W[i-Nk]
   else if (i%Nk==4)
      W[i] = SubByte(W[i-1]) XOR W[i-Nk]
   else
     W[i] = W[i-1] XOR W[i-Nk]

Inverting the Cipher

The cipher is run in the inverse order. However, note that: 

   InvShiftRow(State)
   InvByteSub(State)
is the same as 
   InvByteSub(State)
   InvShiftRow(State)
and 
   InvAddRoundKey(State,InvRoundKey)
   InvMixColumn(State)
is the same as 
   InvMixColumn(State)
   InvAddRoundKey(State,InvRoundKey)
Operations, paired up in this way, and thanks to the special final round, make the structure of the inverse cipher the same as the forward cipher, with different maps.

The MixColumn forward map requires easy multiplications, by '01', '02' and '03' only. InvMaxColumn doesn't have as nice numbers, so the inverse cipher is slower.

Inverting the S-box matrix.

The notation in the reference seems upside-down, with the a_0 term being the coefficient of the term of maximum degree. We will go with this. The polynomial encoded in the matrix can be read off from the right-most column: 

s(x) = x^7+x^6+x^5+x^4+1 = [76540]
We will use the bracket notation demonstrated above to encode polynomials over GF(2).

Using the Euclidean algorithm to invert s(x) modulo x^8+1 = [80]. The required divisions are summarized: 

 Remainder = dividend + quotient divisor

 [41] = [80] + [10][76540]
 [320] = [76540] + [321][41]
 [20] = [41] + [10][320]
 [1] = [320] + [10][20]
 [0] = [20] + [1][1]
An example to explain the notation: 
 [320] = [76540] + [321][41]

 [76540] + ([321][41])  = [76540] + ([432] + [765])
                        = [76540] + [765432]
                        = [320]
Then back substitute (parenthesis are used around "coefficients" to distinguish them from the suite of remainders given by the Euclidean algorithm): 
[0] = [20] + ([1])[1]
    = [20] + ([1])([320] + [10][20])
    = ([0] + [1][10])[20] + ([1])[320]
    = ([210])[20] + ([1])[320]
    = ([210])([41] + [10][320]) + ([1])[320]
    = ([210])[41] + ([210][10] + [1])[320]
    ...
    = ([752])[76540] + ([6520])[80]
Hence x^7+x^5+x^2 is the inverse of x^7+x^6+x^5+x^4+1 modulo x^8+1.

Additional Notes

No Fixed Points for the S-Box

I have not completed this proof. However, there are no fixed points to the affine map. Such a fixed point satisfies, 

  x = A x + b
or 
  b = (A+I)x
(A+I) has exactly four one's in each row and column, so the vector of all one's is in the null space, and thus (A+I) is singular. The lack of fixed points then depends on b not being in the range of the singular map x->(A+I)x. The vector t = (1 1 0 0 1 1 0 0) is orthogonal to every column of (A+I) but is not orthogonal to b, hence, b cannot be in the range of (A+I).

It is also claimed that (1+x)= A x + b has no solutions. The same procedure and the same test vector t demonstrates this.

However, the true claim is that there are no solutions to x = A(1/x)+b, where this equation is in mixed mode, where the 1/x refers to x in GF(2^8) and the rest refers to operations in GF(2)^8.