# Understanding multiplication in the AES specification

I am reading through the AES specification and am not able to wrap my head around the multiplication definition (section 4.2). Sorry to refer to a spec but AES is the holy grail in crypto so I hope its not too much to ask.

Here are my questions -

1. In section 4.2 why is the modulo chosen as {01}{1b} which is $283$ and not $255$? The irreducible polynomial is $m(x)=x^8 +x^4 +x^3 +x+1$. Is there a significance to this seemingly random choice? Later on in the explanation it also says the modulo operation produces values that can be represented in a single byte. How is that possible if the modulo is performed over $283$?

2. Later on the same section in the example {57} • {83} is computed to be $x^{13} +x^{11} +x^9 +x^8 +x^6 +x^5 +x^4 +x^3 +1$ - which is $11129$. Using a calculator it appears this is wrong. Its coming out to be $11397$. What am I missing?

3. In section 4.2.1 (multiplication by $x$) it says - It follows that multiplication by $x$ (i.e., {00000010} or {02}) can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with {1b}.

Here again I don't get it. By my understanding it should be a left shift followed by modulo with {01}{1b}.

Can someone please explain this to me?

-
I realize now that the operation is done over Galois fields and not regular arithmetic. I will keep it open while I read up on arithmetic on Galois fields for a bit. –  user220201 Mar 10 '14 at 2:20
0x11b was chosen because it was the first one on the list of polynomials that did the job –  Richie Frame Mar 10 '14 at 6:24
@user220201: I think the answers here might help explain the Galois maths. –  figlesquidge Mar 10 '14 at 9:28
People need to stop downvoting questions like this for the sake of downvoting. I've read over Fips-197 multiple times in an attempt to learn and implement it for myself and questions like these become integral "side lessons" to bridge the learning gap (i.e. "what am I missing"). So here's your 0 back :) –  Matt Borja May 3 at 14:15

1. 011b is a hexadecimal representation of the polynomial $m(X) = X^8 + X^4 + X^3 + X + 1$ (so you should never regard it as an integer). This polynomial has coefficients in the finite field $\mathrm{GF}(2)$, which is just the math-y way to say that its coefficients are in $\{0,1\}$:

hex | 0    1    1    b
bin | 0000 0001 0001 1011
x^n |         8 7654 3210


The 1-bits indicate which power has a coefficient of $1$. When you take any polynomial and divide it by $m(x)$, which has degree $8$, the remainder will have degree smaller than $8$, so using the same representation scheme as above, it can be represented on one byte.

2. 57 and 83 are likewise representations of polynomials using that same method, I will leave it to you to check that when you multiply those two polynomials, you do indeed find the asserted result.

3. Your understanding is correct, those two operations are the same. But again, remember that you are working on polynomials, not integers.

EDIT: It's important to understand the difference between the objects AES manipulates and those you are used to. When you think of a data type which takes only one byte, you think of integers in $\{0,\dots,255\}$ with the usual addition and multiplication modulo $256$. The problem with those numbers is that while they have all the nice properties we are used to for addition, they fail catastrophically for multiplication: you can take two non-zero numbers (which ones?), multiply them, and obtain $0$!

This is not acceptable for AES: it requires a "nice" multiplication operation, meaning that when you multiply two non-zero elements, you want to obtain a non-zero element. This weird system of polynomials modulo $m(X)$ does exactly this.

-
Thanks for the great explanation. Can you comment on the choice of the polynomial chosen for the modulo? It seems rather odd. Specifically going by what you said, it can be any polynomial as long as the degree is 8. So is there some logic behind the choice? –  user220201 Mar 10 '14 at 6:31
First, it cannot be any polynomial of degree $8$. In order to obtain a nice multiplication, it must be an irreducible polynomial of degree $8$. Mathematically, any irreducible polynomial of degree $8$ will do. The choice of this particular polynomial was made for computational reasons, probably in part what you alluded to in 3.: it makes the operation of multiplication by $x$ very easy (and fast) to implement. –  fkraiem Mar 10 '14 at 6:37
It must be a polynomial $p$ with $\deg(p)=8$ and be irreducible. What this means is that it cannot have any (non-trivial) factors. –  figlesquidge Mar 10 '14 at 9:30
How do I compute the modulo using a polynomial? For e.g. how to compute - $(x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1) modulo (x^8 + x^4 + x^3 + x + 1)$ –  user220201 Mar 10 '14 at 23:54
On pencil and paper, just do a long division, but real people use a computer (with e.g. Sage or PARI/GP). ;) –  fkraiem Mar 10 '14 at 23:56