Redbook1's profile - activity

I see. Well, the MDS matrix shown multiplies column vectors of four elements, all of which are bytes (as are the entries in the matrix) in the field $GF(2^8)$ and using an irreducible polynomial $p(x) = X^8 + X^4 + X^3 + X + 1$. An example column vector might be $(a3\ 25\ c4\ 06)^T$. Therefore multiplying by the first entry in the MDS matrix, $(02)$, gives: $02 \times a3 = X (X^7 + X^5 + X^2 + X) = X^6 + X^4 + X^3 + X^2 + 1 $ or $5d$ (after reduction by p(x)).

I have since found the branch number of a matrix is: $B(A) = min[weight(a) + weight(aA)], but I cannot find an example of this. I believe the weight of a matrix is the number of its non-zero components. Even so, I am not sure how to calculate it without a clear example.

Can anyone explain what a branch number is and how to calculate it? I have checked several books on matrices but it seems uncommon. In particular, the matrix:

$$02\quad 03\quad 01\quad 01$$ $$01\quad 02\quad 03\quad 01$$ $$01\quad 01\quad 02\quad 03$$ $$03\quad 01\quad 01\quad 02$$

These entries are hexadecimals (or bytes), e.g. in bits ${02}$ is $00000010$, and comes from the Mix column layer in the $AES$ cipher (just in case that makes a difference).

I have read this matrix has the maximum branch number of $n+1 = 5$, but I do not understand where this came from or what it means.

I also read this is an $MDS$ matrix and I think branch numbers and $MDS$ matrices are linked somehow but, again, I don't know how. I have looked for video tutorials on $MDS$ matrices and branch numbers but there is nothing for beginners.

A couple of simple examples for branch numbers and/or $MDS$ matrices would be really helpful.

Thank you!

Perfect! Many thanks.

1. I need to find all the sub-square matrices of a $4 \times 4$ matrix.
2. Then find the determinant of all $70$ of them.

I was directed to Sage but I know little about it. A simple program would be much appreciated.

For example, the matrix below:

$$2\quad 3\quad 1\quad 1$$ $$1\quad 2\quad 3\quad 1$$ $$1\quad 1\quad 2\quad 3$$ $$3\quad 1\quad 1\quad 2$$

Thanks to anyone who can help.

@slelievre Nice tip. But how do I untick my question from the community wiki?

@dan_fulea

• AES S-box is the substitution box in the encryption cipher AES. I don't think it is necessary to know exactly what it is to understand the question.
• $m$, $v$ and $y$ (and $s$) are all given. The S-box takes an input of 8 bits (written in hexadecimal) and produces an output. For example $S-[2A] = E5$ These outputs come from Lagrange interpolations (somehow) but I don't know how to do it .. even on paper. But I heard it can be done in Sage.
• I am not sure which Lagrange interpolation.

I found the Sage code for the AES S-box online. It is given below.

However, I do not know how to find the coefficients of a to h using Lagrange interpolation. They seem to appear from nowhere, but I am told they are the result of Lagrange interpolation. I only know how to apply Lagrange interpolation if I have a function and some given points. But it seems there are no given points.

Can anyone help? An example of how to use Lagrange interpolation in Sage for just one or two of these polynomials, say $a =x^2+1$, and $b = x^3+1$ would be very helpful.

R = PolynomialRing(GF(2),'x',1)
x = R.gen()

m = x^8 + x^4 + x^3 + x + 1
v = x^6 + x^5 + x + 1
y = x^7 + x^4 + x^2 + 1

a = x^2 + 1
b = x^3 + 1
c = x^7 + x^6 + x^5 + x^4 + x^3 + 1
d = x^5 + x^2 + 1
e = x^7 + x^6 + x^5 + x^4 + x^2
f = 1
g = x^7 + x^5 + x^4 + x^2 + 1
h = x^7 + x^3 + x^2 + x + 1

s = a*(y^254) + b*(y^253) + c*(y^251) + d*(y^247) + e*(y^239) + f*(y^223) + g*(y^191) + h*(y^127) + v

print (s % m)