2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Oct 16 '16 at 19:12
  • $\begingroup$ 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. $\endgroup$ – j.p. Oct 16 '16 at 20:40
  • $\begingroup$ @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.) $\endgroup$ – e-sushi Oct 21 '16 at 12:09
2
$\begingroup$

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}}$

enter image description here

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}$.

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