# Fast AES-128 on 32 bits encryption

Suppose in AES-128, there are $5$ tables, namely Te0, Te1, Te2, Te3, Te0 which help in fast encryption on $32$ bits CPU. Each table contains 256 numbers, where each number is $4$ bytes.

Te4's numbers are generated by repeating hexadecimal in S-box. So Te4 contains numbers $0x63636363U, 0x7c7c7c7cU, 0x77777777U, ...$.

Te0 contains numbers which is obtained through the degree-wise multiplication between $\{ab\} x^3+\{ab\} x^2+\{ab\}x+\{ab\}$ and $\{02\} x^3+\{01\} x^2+\{01\}x+\{03\}$. The first polynomial is the number in Te4. So the first number in Te0 is $0xc66363a5U$, which is obtained through $\{63\} x^3+\{63\} x^2+\{63\}x+\{63\}$ and $\{02\} x^3+\{01\} x^2+\{01\}x+\{03\}$.

Te1's numbers are obtained through $1$ byte right rotation on numbers in Te0. So Te1 contains $0xa5c66363U$. Te2 and Te3 are also obtained by $1$ byte right rotation.

The followings are the screenshot of the five tables:     Question: If only table Te0 is used in the program, explain how to perform encryption.

I think we have to perform computation on the numbers, but I don't know how to do it. Would appreciate if anyone can give some hints on it.

## 1 Answer

There's no particular computation you have to do.

Since all other tables could be computed just by rotations of Te0 what you need is just to perform rotations, xors and table lookups.

Here's what usually done when you have only Te0.

You read the state column-wise, keeping in one 32 bit variable/register the value of one column. (As convention hereafter, the most significant byte of the 32 bit variable encodes the top byte of the column in the 4x4 AES state matrix).

Now what you want to perform are ShiftRows, SubBytes and MixColumns is:

uint32_t a; //This contains the state
uint32_t b; //This will contain the state after ShiftRows
//SuuBytes and MixColumns

b = Te0[FIRST_BYTE(a)]  ^
rotateL8 (Te0[SECOND_BYTE(a)]) ^
rotateL16(Te0[THIRD_BYTE (a)]) ^
rotateL24(Te0[FOURTH_BYTE(a)]);


Where the X_BYTE are macros returning the X most significant byte of the uint32_t, and the rotateLX macros perform left rotations of X bits.

The explanation is as follows: As input it is taking first byte of first column, second byte of second columns, etc. This is made to perform ShiftRows. In fact, the input will be the first column after ShiftRows operation. The table lookups by Te0 will return a word, containg: 2*Sbox(input), Sbox(input), Sbox(input), 3*Sbox(input)

Note that this corresponds to the first column of the formulas below, which is used to calculate MixColumns as shown in the wikipedia MixColumns page

$b_0 = 2a_0 + 3a_1 + 1a_2 + 1a_3$

$b_1 = 1a_0 + 2a_1 + 3a_2 + 1a_3$

$b_2 = 1a_0 + 1a_1 + 2a_2 + 3a_3$

$b_3 = 3a_0 + 1a_1 + 1a_2 + 2a_3$

Note that the addition in the above formulas are additions in $GF(2^8)$ and corresponds to the xors used in the C code.

Therefore when you do the second table lookup you need to rotate the result left by one byte, in order to match the second column in the formula above, and so on for third and fourth table lookups.

To evaluate a full round you need to evaluate the other 3 columns, the code is the same, you just need to rotate the indexes of a. So a full rounds can be obtained by:

for (int32_t i=0; i < 4; i++)
{
b[i] = Te0[FIRST_BYTE(a[i])]  ^
rotateL8 (Te0[SECOND_BYTE(a[(i+1) % 4])]) ^
rotateL16(Te0[THIRD_BYTE (a[(i+2) % 4])]) ^
rotateL24(Te0[FOURTH_BYTE(a[(i+3) % 4])]) ^ round_key[i];
}


Where the addition of $round_key[i]$ performs the AddRoundKey operation.

Please note that the final round requires special treatment since no MixColumns is performed. You will need to do the table lookup and just keep the second or third bytes (which corresponds to the Sbox of the input) discarding the rest. Something like:

for (int32_t i=0; i < 4; i++)
{
b[i] = (SECOND_BYTE(Te0(FIST_BYTE(a))) << 24) ^
(SECOND_BYTE(Te0(SECOND_BYTE(a[(i+1) % 4]))) << 16) ^
(SECOND_BYTE(Te0(THIRD_BYTE (a[(i+2) % 4]))) << 8 ) ^
(SECOND_BYTE(Te0(FOURTH_BYTE(a[(i+3) % 4]))) ^ round_key[i];
}