Understanding multiplication in the AES specification

Question

I am reading through the AES specification and am not able to wrap my head around the multiplication definition (section 4.2).

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?

Answer 1

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.

Answer 2

What does "multiplication modulo $\mathtt{m(x)}$" mean in Rijndael's Galois field?

We use the polynomial $\mathtt{m(x)}$ to make sure byte multiplication in the MixColumns step transforms an input byte into a single output byte, and not two bytes. NIST's publication on AES says:

The result $x \cdot b(x)$ is obtained by reducing the above result modulo $m(x)$,

The centered dot $\cdot$ means finite field multiplication. That kind of multiplication is different from regular multiplication, such as, for example, done in Bash with arithmetic expansion:

printf "%02X\n" $((0xfe * 0x02))

Rather, finite field multiplication of two bytes in this Galois field means:

• We treat the two bytes as polynomials and multiply those two polynomials. The answers to this question show how the conversion from byte to polynomial works and how polynomial multiplication is performed. The videos by Creel and Heath David Hart are also helpful in understanding finite field multiplication.
• After multiplying the polynomials we might have produced a polynomial of degree 8 which means the bit representation of that polynomial needs nine bits and consequently doesn't fit into a byte. In such cases, we subtract the polynomial $\mathtt{m(x)}$ from the product polynomial. That's the "modulo $\mathtt{m(x)}$" part. Performing subtraction might come as a surprise since when dealing with natural numbers, "$\mathtt{A}$ modulo $\mathtt{B}$" means getting the remainder of the division of $\mathtt{A}$ and $\mathtt{B}$. But in Rijndael's Galois field, "modulo $\mathtt{m(x)}$" means subtracting $\mathtt{m(x)}$. This is done by XORing the byte representation of $\mathtt{m(x)}$, which is $\mathtt{11b}_{16}$, from the result of the polynomial multiplication to get a number that fits into a byte. On the other hand, if the resulting polynomial can be converted to 8 bits or less, you leave it as it is, no reduction needed.

A small example: Let's say you end up with polynomial $\mathtt{x^8 + x^7 + x^5 + x^3}$ after multiplying two polynomials (which represent two bytes). This polynomial in binary and hex is

$$\mathtt{110101000}_2$$

and

$$\mathtt{1a8}_{16}$$

respectively. If you haven't already, read these answers or the NIST AES publication to see how the conversion from polynomials to bits is done.

$\mathtt{1a8}_{16}$ is more than a byte, meaning we use $\mathtt{m(x)}$ to reduce that number to make it fit into a byte.

In binary and hex, $\mathtt{m(x)}$ is $\mathtt{100011011}_2$ and $\mathtt{11b}_{16}$.

As mentioned before, "modulo $\mathtt{m(x)}$" means XORing the number we want to reduce, $\mathtt{1a8}_{16}$, with $\mathtt{m(x)}$:

printf "%x\n" $((0x1a8 ^ 0x11b))

That gives us the byte $\mathtt{b3}_{16}$, we're done multiplying and reducing.

You can see that $\mathtt{11b}_{16}$ is suitable to reduce a number like $\mathtt{1a8}_{16}$ to a single byte when writing them out in binary:

  1 0001 1011   // 0x11b
  1 1010 1000   // 0x1a8

The leftmost 1 belongs to the second byte in those numbers. XORed, the 1s cancel each other out, we get zero and thus a number that fits into a byte.

Why does the standard say to XOR with $\mathtt{1b}_{16}$ instead of $\mathtt{11b}_{16}$?

In section 4.2.1 "Multiplication by $\mathtt{x}$" of the NIST publication on AES, it says:

If b7 = 1, the reduction is accomplished by subtracting (i.e., XORing) the polynomial $m(x)$. 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}. This operation on bytes is denoted by xtime().

At first, the standard defines $\mathtt{m(x)}$ to be $\mathtt{11b}_{16}$ and suddenly we are supposed to XOR with $\mathtt{1b}_{16}$ instead? What's going on?

Let's use example bytes from the NIST publication:

xtime({ae}) = {47}

xtime({ae}) means: The polynomial represented by $\mathtt{ae}_{16}$ is multiplied with the (pretty short) polynomial $\mathtt{x}$.

That's another way of writing $\mathtt{ae \cdot 02}$ since the polynomial $\mathtt{x}$ is short for $\mathtt{x^1}$ which translates to the binary number $\mathtt{10}_2$ (because bit at index 1 has to be set to 1). Multiplying a binary number by two is done by shifting the bits one position to the left.

If you're reimplementing xtime using a programming language, Bash for example, you might do it like this:

1. Shift 0xae one bit to the left: printf "0x%02x\n" $((0xae << 0x01)).
2. Which produces 0x15c. Since this is more than one byte we follow the standard and XOR with 0x1b:

printf "0x%02x\n" $((0x15c ^ 0x1b))

3. This produces 0x147 which is different from the expected result 0x47.

Now you're confused because you got 0x147 instead of 0x47. You try to XOR with the number that you were originally told is $\mathtt{m(x)}$, namely 0x11b, and get the right result of 0x47:

printf "0x%02x\n" $((0x15c ^ 0x11b))

You rewatch the videos by Creel and Heath David Hart: They use $\mathtt{11b}_{16}$ as well for reducing results to a single byte.

Hubris kicks in and you think you've found an error in the standard.

But there's a more natural explanation: I'm quite confident that when the standard authors suggest to left shift and use $\mathtt{1b}_{16}$ for XORing, they have a byte data type in mind.

We're left shifting a single byte. A byte contains eight bits, if we shift each bit one position to the left, the leftmost bit is gone.

Let's illustrate with some Rust code, the data type u8 is an unsigned number with 8 bits:

// Multiplies the input by two and reduces the product with m(x) to one byte if
// it would need two bytes
fn xtime(input: u8) -> u8 {
    // Tells us whether after the left shift the result would be larger than
    // a byte if we had used a bigger data type than u8
    let hi_bit_set = (0b1000_0000 & input) != 0;
    // If bit with index 7 (the high bit) is set, it's gone after the shift
    let mut output: u8 = input << 1;

    // If the high bit was set before the shift, multiplying by two would result
    // in more than one byte. Hence, we need to reduce
    if hi_bit_set {
        // We use 0x1b instead of 0x11b since the high bit is already gone after
        // the shift and XORing one byte with two bytes (0x11b) would result in
        // two bytes. Also, because output is a single byte (u8) the type checker
        // would forbid XORing that single byte with the two bytes of 0x11b
        output ^= 0x1b;
    }

    output
}

// Test xtime with numbers straight from the standard
#[test]
fn xtime_works() {
    assert_eq!(xtime(0x57), 0xae);
    assert_eq!(xtime(0xae), 0x47);
    assert_eq!(xtime(0x47), 0x8e);
    assert_eq!(xtime(0x8e), 0x07);
}

The leftmost bit of $\mathtt{11b}_{16}$ is used to zero out the rightmost bit of a second byte, the bit with index 8. Since we're operating on a single byte, there is no index 8 and we're left with $\mathtt{1b}_{16}$ to perform the reduction. As mentioned in the comments of the Rust xtime function, XORing a single byte with the two bytes of $\mathtt{11b}_{16}$ would produce two bytes. And that's the opposite of what we want to achieve with the reduction.

On the other hand, if we use two bytes (u16 in Rust) as the output's data type, the high bit wouldn't fall off after the left shift. Therefore, we indeed need to use 0x11b for reduction:

fn xtime_with_two_bytes(input: u8) -> u8 {
    let input_two_bytes: u16 = input as u16;
    let mut output: u16 = input_two_bytes << 1;

    // We need to reduce if the output is larger than one byte
    if output > 0xFF {
        output ^= 0x11b;
    }

    // We're pretty sure the result fits into a byte after reduction
    output as u8
}

Answer 3

I'll answer the below question:

---

How do I compute the modulo using a polynomial? For e.g. how to compute - (x13+x11+x9+x8+x6+x5+x4+x3+1)modulo(x8+x4+x3+x+1)

---

x13+x11+x9+x8+x6+x5+x4+x3+1 = 10101101111001

x8+x4+x3+x+1 = 100011011

10101101111001 modulo 100011011

->

10101101111001

^100011011

-> 00100000011001

^100011011

-> 00000011000001

11000001 < 100011011

so the answer is 11000001 = x7 + x6 + 1