7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user220201
    Mar 10, 2014 at 2:20
  • $\begingroup$ 0x11b was chosen because it was the first one on the list of polynomials that did the job $\endgroup$ Mar 10, 2014 at 6:24
  • 1
    $\begingroup$ @user220201: I think the answers here might help explain the Galois maths. $\endgroup$ Mar 10, 2014 at 9:28

3 Answers 3

9
$\begingroup$
  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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – user220201
    Mar 10, 2014 at 6:31
  • $\begingroup$ 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. $\endgroup$
    – fkraiem
    Mar 10, 2014 at 6:37
  • $\begingroup$ 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. $\endgroup$ Mar 10, 2014 at 9:30
  • $\begingroup$ 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)$ $\endgroup$
    – user220201
    Mar 10, 2014 at 23:54
  • $\begingroup$ On pencil and paper, just do a long division, but real people use a computer (with e.g. Sage or PARI/GP). ;) $\endgroup$
    – fkraiem
    Mar 10, 2014 at 23:56
0
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ We have $\LaTeX$/MathJaX enabled in out site. $\endgroup$
    – kelalaka
    Aug 20, 2020 at 10:49
0
$\begingroup$

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))
  1. 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
}
$\endgroup$

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.