1
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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$
Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi this is quite difficult to follow, is there a concrete example some where? $\endgroup$ Commented Oct 30, 2018 at 13:47
  • $\begingroup$ Which part is difficult? $\endgroup$ Commented Oct 30, 2018 at 13:50

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.