# How to perform the modular reduce of Rijndael's finite field

I am trying to understand how to calculate the modular reduction of Rijndael's finite field.

The example on this page says that {53} • {CA} = {01}, because (11111101111110 mod 100011011) = {3F7E mod 11B} = {01} = 1.

I am able to get to the point where I have 3F7E mod 11B, but cant seem to figure out how the reduction works.

      11111101111110 (mod) 100011011
^100011011
1110000011110
^100011011
110110101110
^100011011
10101110110
^100011011
0100011010
^100011011 <-- here, right shifted two places?
00000001


From this example, why does it right shift two places at one point?

I also found an example that 0x1b*0xaa equals 0x8c. Trying to solve this myself I get to the point: 0xE0E mod 0x11B

 111000001110
^100011011
11011010110
^100011011
1010111010
^100011011
010001100
^100011011
10010111


This makes it 0x97

• IIRC Rijndael calculates on polynomials instead of integers. Thus each bit you set is actually some power of x which is present in the polynomial. – SEJPM Oct 16 '16 at 19:12
• Only if there is a leading 1 you should xor a left shifted 0x11b to your intermediate result to cancel out that 1. If you have a leading 0, you create a 1, which you do not want to have there. That's why there was the double shift, and that's what you are doing wrong in the last example. – j.p. Oct 16 '16 at 20:40
• @j.p. & SEJPM Please avoid providing answers via comments. Comments should only be used to ask for clarification etc. (In case of doubt, read the placeholder text of the comment box edit field.) – e-sushi Oct 21 '16 at 12:09

## 1 Answer

First let us have a look at the division of $\mathtt{0x3f7e}$ by $\mathtt{0x11b}$

1      11111101111110 |    (mod) 100011011
2     ^100011011      +-----------------------
3     +-------------+ |          1?????
4       1110000011110 |                >> 1
5      ^100011011     |
6      +------------+ |          11????
7        110110101110 |                >> 1
8       ^100011011    |
9       +-----------+ |          111???
10        10101110110 |                >> 1
11       ^100011011   |
12       +----------+ |          1111??
13         0100011010 |                >> 1
14        ^000000000  |
15        +---------+ |          11110?
16          100011010 |                >> 1
17         ^100011011 |
18         +--------+ |          111101
19           00000001 |


The result of the Euclidean division is therefore: $$\mathtt{0x3f7e} = \mathtt{0x11b} \times \mathtt{0x3d} + \mathtt{0x1}$$ Or : $$\mathtt{11111101111110} = \mathtt{100011011} \times \mathtt{111101} + \mathtt{1}$$ Thus: $$\mathtt{11111101111110} \equiv 1 \pmod{\mathtt{100011011}}$$

As we don't care of the result of the division but only of the residue, we directly forget it.

As you noticed each line there is a single right shift (>> 1) in the subtraction. But also notice that when a bit of the quotient is 0, nothing is being done after this right shift (see lines $\texttt{12}$ to $\texttt{15}$) (because we multiply the divisor by 0, the result will obviously be the same after the subtraction... by 0).

Thus we can factorize the lines $\texttt{14}$ to $\texttt{16}$ by double right shift (>> 2), giving us the Wikipedia division:

1      11111101111110 |    (mod) 100011011
2     ^100011011      +-----------------------
3     +-------------+ |          1?????
4       1110000011110 |                >> 1
5      ^100011011     |
6      +------------+ |          11????
7        110110101110 |                >> 1
8       ^100011011    |
9       +-----------+ |          111???
10        10101110110 |                >> 1
11       ^100011011   |
12       +----------+ |          1111??
13         0100011010 |                >> 2
17         ^100011011 |
18         +--------+ |          111101
19           00000001 |


## TL;DR: the double right shift correspond to the $\mathtt{0}$es in the quotient.

About: $\mathtt{0x1b} \times \mathtt{0xaa} \equiv \mathtt{0x8c} \pmod{\mathtt{0x11b}}$ And looking back at your division:

1     111000001110
2    ^100011011
3      11011010110
4     ^100011011
5       1010111010
6      ^100011011
7        010001100
8       ^100011011  <-- THIS IS VERY WRONG
9         10010111  <--


Lines $\texttt{8}$ and $\texttt{9}$ are simply not allowed: $$\mathtt{10001100} < \mathtt{10001101}$$ Thus $\mathtt{10001100}$ is the result and by a strange coincidence $\mathtt{10001100} = \mathtt{0x8c}$.