Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 at 6:24
    
@user220201: I think the answers here might help explain the Galois maths. –  figlesquidge Mar 10 at 9:28
add comment

1 Answer 1

up vote 4 down vote accepted
  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.

share|improve this answer
    
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 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 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 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 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 at 23:56
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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