1
$\begingroup$

This refers to answer 2 on a similar question:Design properties of the Rijndael finite field

I am unsure what many of the terms mean in this answer. I think a bit-wise linear isomorphism of irreducible polynomial A refers to: $$A(x) = x^8+x^4+x^3+x+1=100011011$$ or $11B$ in hex. And I assume B refers to another irreducible polynomial over $GF(2^8)$ (btw Is there a list of these? I cannot find them). If I am right, I still cannot fully understand what is meant by:$$L(X+_AY)=L(X)+_BL(Y)$$ or $$L(X \times_AY)=L(X)\times _BL(Y)$$Specifically, I am not sure what $X$ and $Y$ are (but I think they are other polynomials) or what $+_A$, $+_B$, $\times_A$, $\times_B$ mean. A full numerical example would be very helpful, even if only one of the two equations above.

$\endgroup$
2
$\begingroup$

To answer this question, we'll first want to step back and discuss what a finite field is, and what a representation is.

A finite field is a group of finite size (always $p^k$, for some prime $p$ and integer $k$, in this case, $2^8$), along with addition and multiplication operators, where certain identities are true (e.g. $a \times (b + c) = a \times b + a \times c$), see this link for the list.

It turns out that, given a specific size $p^k$, the field is essentially unique (in the sense that, if we have two different sets of the same size where they both preserve the identities, they will always be a mapping between the two sets which preserve both the addition and multiplication operations, hence those two sets are essentially the same.

This is nice, however we need a way to talk about these elements; what we do is assign the element names; for $GF(2^8)$, we have precisely 256 elements, and so we typically give each element a unique 8 bit name. Such a way of assigning names is known as the 'representation'.

For $GF(2^8)$, there are a number of reasonable ways to assign these names, one such way is to select an irreducible polynomial, and compute the multiplication modulo that polynomial. That is the approach that AES takes, with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$. Let us call this specific representation (which is a way of assigning names to field members) $A$.

However, that isn't the only way of assigning names; we could consider a different irreducible polynomial, say, $x^8 + x^4 + x^3 + x^2 + 1$. That gives a different way of assigning names to field elements, that is, a different representation, we may call this representation $B$.

Now, we define $L$ to be the function that takes a field element (using the $A$ naming convention), and return the name of that same field element (using the $B$ naming convention). It turns out $L$ isn't unique; we'll ignore that for now. It turns out that $L$ is an isomorphism, as the field it maps from (the $A$ representation) and the field it maps to (the $B$ representation) are the same (because they're both different ways of given labels to the same underlying field).

It turns out that, if we just look at $L$ as a mapping between 8 bits to 8 bits, it is bit-wise linear.

In the $A, B$ representations I just gave, one such mapping is:

$$L(01) = 01$$ $$L(02) = 03$$ $$L(04) = 05$$ $$L(08) = 0F$$ $$L(10) = 11$$ $$L(20) = 33$$ $$L(40) = 55$$ $$L(80) = FF$$

Because $L$ is linear, it is easy to deduce $L(X)$ for any other $X$ not listed.

And, what $+_A$ means is the addition operation in the $A$ representation; that is, $X +_A Y$ takes the two field elements $X, Y$ (named using the $A$ convention), and evaluates to the field addition of those elements (also expressed in the $A$ naming convention. Hence, when we say:

$$L(X+_AY)=L(X)+_BL(Y)$$

$X, Y$ are both arbitrary field elements (in the $A$ naming convention), and what we're saying is that the $L$ mapping preserves addition; that is, if we add two arbitrary elements $X, Y$ (in the $A$ representation) and then map the sum, we always get the exact same value as we would have if we first mapped $X$ and $Y$ into the $B$ representation, and then added them (in the $B$ representation).

We call out $+_A$ and $+_B$ because they aren't necessarily the same operation (actually, in this case they are, but not in general); $+_A$ assumes the inputs are in the $A$ representation, and $+_B$ assumes they are in the $B$ representation.

You asked for a numeric example, here's a simple one (using the $\times$ operator; it turns out that the addition operation isn't that interesting).

If we pick $X = 03$ and $Y = 05$, we have (on the left side):

$L(03 \times_A 05) = L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08) = 08$

(Note: we have $L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08)$ because of the bitwise linearity of $L$)

On the right side, we have:

$L(03) \times_B L(05) = (L(01) \oplus L(02)) \times_B (L(01) \oplus L(04)) = 02 \times_B 04 = 08$

That is, both sides come up with the same value. This will always be true no matter what values we picked for $X, Y$

$\endgroup$
  • $\begingroup$ From the list L(01) = 01, L(02) = 03, etc. I assume 01 is hex for 0000 0001, 02 is hex for 0000 0010, etc. and these can be expressed as polynomials. However, I don't understand where the inputs for L(.) come from. I think they are field elements but: (i) how did you choose them? (ii) And how do we know what can or cannot be chosen? I see, for example, L(08) = 0F, but I cannot see how they relate to A and B or how the answer 0F comes to be. . $\endgroup$ – Red Book 1 Oct 19 '17 at 11:04
  • $\begingroup$ @RedBook1: actually, the inputs to $L$ are bitpatterns, specifically, the bitpattern in the $A$ representation; the output is the bitpattern in the $B$ representation that corresponds to the same abstract field element. For example, we have $L(08) = 0F$, that is, the same abstract field element has bitpattern 08 (or 00001000) in the $A$ representation and has bitpattern 0F (or 00001111) in the $B$ representation. $\endgroup$ – poncho Oct 19 '17 at 12:57
  • $\begingroup$ Sorry, but I am still not getting this. If, for instance, I see the bit-pattern 01010111 = 57, I think of polynomial $x^6 + x^4 + x^2 + x +1$. In our case, $A(x) = x^8 + X^4 + x^3 + x + 1 = 1 0001 1011$ and $B(x) = x^8 + X^4 + x^3 + x^2 + 1 = 1 0001 1101$. So when you say (for example) $L(08) = L(00001000)$ is a bit-pattern 'in' $A$, this seems to leave only $x^3$. In any case, I cannot see how this comes to be the same as $0F$ in $B$. Sorry if I am asking too much, but I think a step-by-step example of how $L(08)=0F$ would get me over this hurdle. $\endgroup$ – Red Book 1 Oct 19 '17 at 14:09
  • $\begingroup$ @RedBook1: I have no idea what you mean by $A(x)$ and $B(x)$; $A$ and $B$ are not functions; instead, they are a way of labeling things. Instead, lets go with an analogy; $A$ and $B$ are naming conventions; lets say that they're "English" and "French"; $L$ is the mapping between the two, so $L(\text{"Dog"}) = \text{"Chien"}$. $\endgroup$ – poncho Oct 19 '17 at 14:47
  • $\begingroup$ @RedBook1: as for why $L(02) = 03$, well, in the $A$ naming convention, the value 02 is one of the roots to the equation $x^8 + x^4 + x^3 + x + 1 = 0$. In the $B$ naming convention, the value 02 is one of the roots to the equation $y^8 + y^4 + y^3 + y^2 + 1 = 0$. It turns out that the value $x$ (02 in the $A$ naming convention) is the value $y+1$ (03 in the $B$ naming convention). As for why $L(08) = 0F$, well, cube each side, $02^3 = 08$ (in the $A$ naming convention), and $03^3 = 0F$ (in the $B$ naming convention) $\endgroup$ – poncho Oct 19 '17 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.