Efficient AES - Use of T-tables

I'm really in trouble! I'm trying to understand how the T-tables in AES encryption work. But I don't know if I get the point. What I understood is that they are used to reduce the whole computation of the iteration of AES just looking at the T-boxes and the XOR operation. Now, what I got is that:

    State                 M Matrix
┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃
┗             ┛       ┗             ┛


I have my State matrix and M matrix composed by 4X4 bytes. Each t-table should receive in input one byte and give in output 4 bytes. Now, in order to create the t-tables i will have in the first table:

T0=(d4*02)+(d4*01)+(d4*01)+(d4*03)
(e0*02)+(e0*01)+(e0*01)+(e0*03)
(b8*02)+(b8*01)+(b8*01)+(b8*03)
(1e*02)+(1e*01)+(1e*01)+(1e*03)


Then the second table should be:

T0=(bf*03)+(bf*02)+(bf*01)+(bf*01)
(b4*03)+(b4*02)+(b4*01)+(b4*01)
(41*03)+(41*02)+(41*01)+(41*01)
(27*03)+(27*02)+(27*01)+(27*01)


And so on...until I'll have 4 tables. Am I right? Now...How can I use these tables?

(You should take a look at page 18 of FIPS 197 where it describes the MixColumns transform).

You're close. Swap the order of your matrices so that you have:

|02 03 01 01| |d4 e0 b8 1e|
|01 02 03 01| |bf b4 41 27|
|01 01 02 03| |5d 52 11 98|
|03 01 01 02| |30 ae f1 e5|


And then you compute the new columns. i.e. the new first column is:

|02 03 01 01| |d4|
|01 02 03 01| |bf|
|01 01 02 03| |5d|
|03 01 01 02| |30|


Which equals:

|02*d4 + 03*bf + 01*5d + 01*30|
|01*d4 + 02*bf + 03*5d + 01*30|
|01*d4 + 01*bf + 02*5d + 03*30|
|03*d4 + 01*bf + 01*5d + 02*30|


And so on.

Do you See the pattern in the sum? Each column in the matrix is multiplied by an element in the column and then they are summed. We can precompute these columns, and compute the above sum using 4 table lookups and 32-bit XOR operations.

The tables will be arrays of 32-bit values which look like this ("|" denotes byte concatenation):

T0[00] = 02*00 | 01*00 | 01*00 | 03*00
T0[01] = 02*01 | 01*01 | 01*01 | 03*00
...
T0[FF] = 02*FF | 01*FF | 01*FF | 03*FF

T1[00] = 03*00 | 02*00 | 01*00 | 01*00
T1[01] = 03*01 | 02*01 | 01*01 | 01*01
...
T1[FF] = 03*FF | 02*FF | 01*FF | 01*FF

T2[00] = 01*00 | 03*00 | 02*00 | 01*00
T2[01] = 01*01 | 03*00 | 02*00 | 01*00
...
T2[FF] = 01*FF | 03*FF | 02*FF | 01*FF

T3[00] = 01*00 | 01*00 | 03*00 | 02*00
T3[01] = 01*01 | 01*01 | 03*01 | 02*01
...
T3[FF] = 01*FF | 01*FF | 03*FF | 02*FF


Using four tables, you can compute the new state matrix with 16 table look-ups and 12 32-bit XOR operations.

T-table is an optimization for AES on 32-bit platforms introcuded by the designer of AES and explained in their book: J. Daemen and V. Rijmen, The Design of Rijndael, Berlin, 2002, p.56-59. A similar further optimization is feasible which is done in my AES C-code of 2003 (http://www.mokkong-shen.privat.t-online.de/).

• Link does not exist – pushpen.paul May 6 at 2:04

You can use one table instead of four tables, as the 2nd table is the first rotated by one byte and so on.

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.