Ask Your Question
0

How do you calculate the branch number of a matrix?

asked 2018-02-16 07:06:40 -0500

Redbook1 gravatar image

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.

edit retag flag offensive close merge delete

Comments

We can help you in the implementation of you needs in Sage, but we can not decide for you what you need or want to achieve.

tmonteil gravatar imagetmonteil ( 2018-02-17 06:49:30 -0500 )edit

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.

Redbook1 gravatar imageRedbook1 ( 2018-02-17 12:05:26 -0500 )edit

The weight is defined on vectors (as in your formula!) and not on matrices. It is generally called Hamming weight. On the other hand, we are missing information to understand the matrix in your question. What does mean 02 and 00000010? What is the field of definition of your matrix? In order to apply the matrix to a vector you need to make sense of a multiplication.

vdelecroix gravatar imagevdelecroix ( 2018-02-18 12:28:13 -0500 )edit

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)).

Redbook1 gravatar imageRedbook1 ( 2018-02-19 01:44:18 -0500 )edit

2 answers

Sort by » oldest newest most voted
1

answered 2018-02-20 07:15:18 -0500

dan_fulea gravatar image

For a reference please look inside the book of Joan Daeman, Vincent Rijmen, the design of Rijndael. (Probably there will be a match to a closer point while searching for Rijndael.pdf in google.)

The chapter 3 explains the situation better then it can be done here, and 3.4.3 is dedicated to the MixColumnStep, the matrix in (3.12) is the same as posted. In order to introduce the data in sage, to have an other, alternative approach to the excellent and quick one of vdelecroix, i will work in the polynomial ring over the field $F = \mathbb F_{2^8}=\mathbb F_2(a)$ given by: $$ R = F[X]/(X^4+1)\ , $$ and let $x$ be the image of $X$ when taken modulo $X^4+1=(X+1)^4$. See loc. cit. for the equivalence of the description. Then the matrix multiplication is translated in a multiplication with the polynomial $$ c = \mathtt{03}\cdot x^3 + \mathtt{01}\cdot x^2 + \mathtt{01}\cdot x + \mathtt{02}\ ,$$ its inverse being $$ d = \mathtt{0B}\cdot x^3 + \mathtt{0D}\cdot x^2 + \mathtt{09}\cdot x + \mathtt{0E}\ .$$ In sage we can initialize this framework as folllows:

R.<A> = PolynomialRing( GF(2) )
F.<a> = GF( 2**8, modulus = A^8 + A^4 + A^3 + A + 1 )
S.<X> = PolynomialRing( F )
J     = S.ideal( X^4+1 )
Q.<x> = S.quotient( J )

c = (a+1)*x^3 + x^2 + x + a
d = 1/c

We do not need $d$ (immediately), but it is a good check to see how things work, it is

sage: d
(a^3 + a + 1)*x^3 + (a^3 + a^2 + 1)*x^2 + (a^3 + 1)*x + a^3 + a^2 + a

which matches the book value. Now we consider the branch number of the application which is the multiplication with $c$ of a polynomial $p$ from $Q$. The weight $w$ of a polynomial is the number of its non-zero coefficients, in translation. The branch number of $c$, in my notation here $$B(c) $$ is then the minimal number among all $$ w(p) + w(cp)\ ,\ p\ne 0\ . $$ Since we have "singletons", e.g. the polynomials $1,x,x^2,x^3$ (multiplied by constants in $F^\times$) taking $p$ to be one of them we have $$ B(c)\le B(1)+B(c\cdot 1)=1+4=5\ .$$ To show that $5$ is indeed the minimal value, we have to prove it by structure, or make the brute force check.

Since it is simpler to check, while in the same time using sage, let us check. A smaller value would come from realizations of $w(p)+w(cp)$ of the shape \begin{align} &1+3\\ &2+2\\ &3+1\\ &1+2\\ &2+1\\ &1+1\\ \end{aligned} so we will check if it is possible to realize one of the above cases. The case of weight one for one of the summands, the singleton case, is already checked, since a "singleton" can be reduced linearly to one of the polynomials $1, x, x^2, x^3$, and it is clear that multiplication with $c$ and/or $d=1/c$ does not provide a smaller value, $w(c)=w(d)=4$.

There is one more case left in the list, this is $2+2$, we have to eliminate it. Let us start with a polynomial $p$ of weight $2$. Because $w(p) = w(xp) = w(x^2p)=w(x^3p)$, we can assume that its constant coefficient is not zero, and further we can norm it to $1$. (We can maybe further restrict to special cases, but this is enough.) The question is now if any of the polynomials $$ c(1+fx^k)\ , \ f\in F^\times\ ,\ k\in{1,2,3} $$ has weight two (or smaller). The check is simple:

def w(p):
    return len( p.lift().coefficients() )

for f in F:
    if f.is_zero():
        continue
    for k in [1..3]:
        p = f*x^k + 1
        if w( c*p ) <= 2:
            print "Weight %s for %s" % ( w(c*p), p )

and there is no print. To still check that there is no error in between, let us alternatively print the weights $\le 3$ and the corresponding $p$-polynomials:

weight3 = [ f*x^k + 1 for f in F for k in [1..3] if not f.is_zero() and w(c*(f*x^k + 1)) <= 3 ]
for p in weight3:
    print "Weight %s for cp when p = %s" % ( w(c*p), p )

Results:

Weight 3 for cp when p = (a + 1)*x + 1
Weight 3 for cp when p = (a + 1)*x^2 + 1
Weight 3 for cp when p = (a^7 + a^6 + a^5 + a^4 + a^2 + a + 1)*x + 1
Weight 3 for cp when p = a*x^2 + 1
Weight 3 for cp when p = a*x^3 + 1
Weight 3 for cp when p = (a^7 + a^3 + a^2 + 1)*x + 1
Weight 3 for cp when p = (a^7 + a^3 + a^2 + 1)*x^2 + 1
Weight 3 for cp when p = (a^7 + a^3 + a^2)*x^3 + 1
Weight 3 for cp when p = (a^7 + a^6 + a^5 + a^4 + a^2 + a)*x^2 + 1
Weight 3 for cp when p = (a^7 + a^6 + a^5 + a^4 + a^2 + a)*x^3 + 1
Weight 3 for cp when p = x + 1
Weight 3 for cp when p = x^3 + 1

(Else we get of course the weight four.)

edit flag offensive delete link more
1

answered 2018-02-19 06:10:06 -0500

vdelecroix gravatar image

updated 2018-02-19 06:10:36 -0500

To construct your matrix A you can do

sage: m = matrix(ZZ, 4, [2,3,1,1,1,2,3,1,1,1,2,3,3,1,1,2])
sage: x = polygen(GF(2))
sage: K = GF(2^8, 'a', modulus=x^8 + x^4 + x^3 + x + 1)
sage: A = matrix(K, 4, lambda i,j: K.fetch_int(m[i,j]))
sage: A
[    a a + 1     1     1]
[    1     a a + 1     1]
[    1     1     a a + 1]
[a + 1     1     1     a]

The method fetch_int used above is exactly what you are describing in your question, converting integers into vectors of bits. Now the question is how to compute the quantity $B(A) = min_a (weight(a) + weight(aA))$. The naive loop will never terminate ($2^{32}$ element in the vector space)

sage: V = VectorSpace(K, 4)
sage: min((v*A + v).hamming_weight() for v in V if v)   # don't do this

Though, you can compute A*v + v for any vector in v

sage: for _ in range(10):
....:     v = V.random_element()
....:     print (v*A + v).hamming_weight()
4
4
4
4
4
4
4
4
4
4

You now have to come up with a better algorithm than looping through all elements of V to compute this minimum.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-02-16 07:06:40 -0500

Seen: 86 times

Last updated: Feb 20