# ETOOBUSY đźš€ minimal blogging for the impatient

# AES - multiplications in GF(256)

**TL;DR**

The

`MixColumns`

transformation of AES leverages operations in $GF(2^8)$, letâ€™s see it in Perl.

Before delving into `MixColumns`

, we have to realize that it requires
operating over field $GF(2^8)$.

In the spirit of *doing most by myself*, I was very happy to have coded
Math::GF in the past. Yay yay yay!

*On the other handâ€¦* Math::GF has two drawbacks as-is:

- a high setup time for $GF(2^8)$, which of course affects any program
using it
*directly* - it figures out the needed irreducible polynomial by itself, while AES tells us which one we should use.

The second issue is easy to address with some fiddling with the moduleâ€™s code, so no big deal. The first one, thoughâ€¦

The main culprit is the calculation of the multiplication table, which is theoretically a $256 \times 256$ matrix, which can be calculated more compactly because itâ€™s symmetric (so there are only $\frac{257 \cdot 258}{2} = 33153$ items), but still thereâ€™s a lot of items to calculate.

The solution I thought is to pre-calculate it once, save it and reload it when needed. Each item is a octet representing a single multiplication, so itâ€™s $33153$ bytes to store. Not too many.

This is how it can be coded, then:

```
sub GF_2_8_mult ($x, $y) {
state $table = GF_2_8_table();
my ($h, $l) = (ord($x), ord($y));
($h, $l) = ($l, $h) if $h < $l;
return substr $table, $l + $h * ($h + 1) / 2, 1;
} ## end sub GF_2_8_mult
```

The `GF_2_8_table`

function loads the pre-calculated mapping as above.
Iâ€™ll not put it here *extensively*, you can take it here. Anyway,
itâ€™s just a bunch of data.

The data are arranged in lower triangular form. This means that the first row (0) contains one single element, representing the square of the first element of the field (unsurprisingly mapped ontoâ€¦ 0), the second row contains two elements, the third row three etc.

All these items are taken from the matrix and arranged one after the other in a linear array (I know, I love linear arrays). So, if we want to get the multiplication of the $X$th element by the $Y$th one, assuming that $X \ge Y$, we have to look for the following element in the linear array:

\[\frac{X \cdot (X + 1)}{2} + Y\]The first part places us at the beginning of the $X$th row, then $Y$ is the offset inside the row.

In the code, $X$ is `$h`

and $Y$ is `$l`

, stressing the requirement that
the former must be higher than, or equal to, the latter. This is also
explicitly checked and enforced by swapping them, if necessary.

So, weâ€™re now ready for `MixColumns`

at last, in a *not-so-inefficient*
way.

Stay safe!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*