2
$\begingroup$

Section 4.1.1 "Finite Field Multiplication"(page 53) of "The Design of Rijndael", it states

enter image description here

How the equation 4.1 has been formed and transformed into equation 4.2?


In section 2.1.6 "Polynomials and Bytes"(page 15), equation 2.27 and 2.28, highest power of x is 7, whereas in above equations 4.1 and 4.2, it is 8. How?

enter image description here

In next line it states

The multiplication by 02 is denoted xtime(x). xtime can be implemented with a shift operation and a conditional XOR operation.

From Equation 2, it seems all values have been given left circular rotation by 1 bit, but what is Conditional XOR? How this multiplication can be implemented with a shift operation and a conditional XOR operation?

$\endgroup$
  • 1
    $\begingroup$ I bet you have not read the previous chapters of the book, and that the answers are there. -1 $\endgroup$ – fkraiem Sep 12 '17 at 6:45
  • $\begingroup$ I have added the information from related section 2.1.6, and my query about it in the question. $\endgroup$ – khan Sep 12 '17 at 7:45
5
$\begingroup$

I. Polynomial representation

$b_7b_6b_5b_4b_3b_2b_1b_0$ represent the polynomial in $\operatorname{GF}(2)[X]$: $b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0$ .

$\texttt{02}$ is $\texttt{00000010}$ thus $0x^7+0x^6+0x^5+0x^4+0x^3+0x^2+1x^1+0x^0 = x$.

$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0 \cdot x = $
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0$
or $b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
that is equivalent to $b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1 = b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$

II. Modulo reduction by $x^8 + x^4 + x^3 + x + 1$:

This leads to two problems:

  • you have a loss of information: you cannot invert the S-box (which would be anoying in the case of AES)
  • the upper bit does not fit into the byte

That is why there is the $\bmod m(x)$.

In the specification of Rijndael, we consider the bytes as polynomials. Byte addition is defined as addition of the corresponding polynomials. In order to define the byte multiplication, we use the following irredutible polynomial as reduction polynomial:

$m(x) = x^8 + x^4 + x^3 + x + 1$. (2.29, p.16)

Thus we will reduce $b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x)$.

Remark that:
$x^8 + x^4 + x^3 + x + 1 \equiv 0 \mod m(x)$
by $a \equiv c \mod m \iff a - b \equiv c - b \mod m$ we have
$x^8 \equiv - x^4 - x^3 - x - 1 \mod m(x)$
because $-1 = 1$ in $\operatorname{GF}(2)$
$x^8 \equiv x^4 + x^3 + x + 1 \mod m(x)$

Thus (going back to our previous equation):
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x) = $
$b_7(x^4 + x^3 + x + 1)+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
$b_7x^4 + b_7x^3 + b_7x^1 + b_7x^0+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
grouping by power this leads to:
$b_6x^7+b_5x^6+b_4x^5+b_7x^4 + b_3x^4+b_7x^3 + b_2x^3+b_1x^2+b_7x^1 + b_0x^1+b_7x^0= $
in other terms:
$b_6x^7+b_5x^6+b_4x^5+(b_7 + b_3)x^4+(b_7 + b_2)x^3+b_1x^2+(b_7 + b_0)x^1+b_7x^0$

III. $\ll$ and $\oplus$

Addition over $\operatorname{GF}(2)$ is equivalent to a XOR ($\oplus$) thus we find the previous formula: $b_6x^7+b_5x^6+b_4x^5+(b_7 \oplus b_3)x^4+(b_7 \oplus b_2)x^3+b_1x^2+(b_7 \oplus b_0)x^1+b_7x^0$

In the end the multiplication of $b_7b_6b_5b_4b_3b_2b_1b_0$ by $\texttt{02}$ can be seen as:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus \texttt{000}b_7b_7\texttt{0}b_7b_7$
or with a conditional XOR:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus b_7\cdot(\texttt{00011011})$

$\endgroup$
  • $\begingroup$ Thanks a lot :) in last equation . means AND operator and a byte is constructed by b7b7b7b7b7b7b7b7 AND (00011011). or it is multiplication? how do one multiply or AND one bit b7 with 8 bits of 00011011? $\endgroup$ – khan Sep 12 '17 at 12:01
  • $\begingroup$ assuming unsigned bytes this could be implemented as : $(x \ll 1) \oplus (\sim ((x \gg 7) - 1) \& (\texttt{00011011}))$ $\endgroup$ – Biv Sep 12 '17 at 12:10
  • $\begingroup$ assuming signed bytes this could be implemented as : $(x \ll 1) \oplus ((x \gg 7) \& (\texttt{00011011}))$ but this is uses a compiler defined behavior... $\endgroup$ – Biv Sep 12 '17 at 12:10
  • $\begingroup$ in simple words, there are two scenarios. 1) if MSB of x is 0 then just left rotate x by 1bit. 2) if MSB of x is 1, left rotate x by 1bit and xor with 00011011? how this equation (x≪1)⊕(∼((x≫7)−1)&(00011011)) is achieving that? why we have negation and - operator? $\endgroup$ – khan Sep 12 '17 at 12:33
  • $\begingroup$ SHIFT !!!! note rotate. $\endgroup$ – Biv Sep 12 '17 at 12:57

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.