I have been given a 4x4 matrix and each entry is an 8-bit long byte. I have been given the 4x4 matrix that I need to multiply each column by of the first matrix by.

$$\begin{pmatrix}2 & 3 & 1 & 1\\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2\end{pmatrix}$$

The method that I have been told to use seems confusing. I have searched around the internet and found many examples with polynomials but I'm not supposed to use this method.

All I have been told is:

Multiplying by 01 does nothing Multiplying by 02 corresponds to multiplying the byte by 10 (because 2 is 10 in binary). This is simply a left shift by one place. If the left-hand bit of the original byte was 1, then XOR the answer with 100011011. Multiplying by 03 corresponds to multiplying the byte by 11 (because 3 is 11 in binary). This is a left shift, followed by an XOR with the original byte. Again, if the left-hand bit of the original byte was 1, then XOR the answer with 100011011.

I find the XOR bit strange as well - because that is a string of 9 bits and the bytes are only 8.

Can anyone make sense of this or point me in the direction of a good example?


If you look at the code in the Wikipedia we will see this part of the code;

  • h = (unsigned char)((signed char)r[c] >> 7);
  • b[c] = r[c] << 1;
  • [c] ^= 0x1B & h;

h stores the leftmost bit of c

c is x-or'ed with 0x1b but not with 0x11b why?

When shifting r left by one, the MSB value is discarded. Before discarding, we hold this value with h.

  • If h==0 than modulus operation is not required. The 0x1B & h = 0x0 so there is no x-or with 0x1b
  • If h=1 than modulus operation is required. The 0x1B & h = 0x1B. The x-or with 0x1b is performed.
  • Note that: it is not x-or with 0x11b it is with 0x1b since we discarded the MSB 1 while shifting. Therefore, there is no need to x-or with 0x11b, x-oring with 0x1b is enough. Now, it is clear that everthing is in Bytes.

A small example;

Here [ ] represents 8-bit.

Let multiply $a = (x^7+x^6+x^3+x)$ by $\{2\}$

  • binary representation of $a = [11001010]$
  • $h = 1 = [00000001]$
  • $b = a \ll 1 = 1[10010100]$ but everthing is in Bytes, therefore
  • $b = [10010100]$
  • $h \wedge 0x1b = [00000001] \wedge [00011011] = [00011011] = 0x1b$
  • $b \oplus 0x1b = [10010100] \oplus [00011011] = [10001111] = 0x8f$
  • $\begingroup$ Hi this is quite difficult to follow, is there a concrete example some where? $\endgroup$ – countduckula Oct 30 '18 at 13:47
  • $\begingroup$ Which part is difficult? $\endgroup$ – kelalaka Oct 30 '18 at 13:50

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.