AES branch number?

Question

[twintwin1003]

По определению branch number Взято отсюда (7.3.1)
Где W(a) - вес вектора т.е. число ненулевых компонент вектора


В AES используется заранее определенная матрица в операции MixColumns. Нужно доказать, что для неё (матрицы) branch number = 5.

Вопросы:
1. В той же статье (7.3.1) сказано, что

the output can have at most 4 active bytes

и

Hence, the upper bound for the branch number is 5

Получается, что W(F(a)) максимум может быть равно 4 (почему?) и W(a) = 1. Почему W(a) = 1, ведь число ненулевых компонент может быть больше 1? Или именно здесь стоит обратить внимание на min()?
2. Каким образом вычислить W(F(a)), для каждого

Answer 1

[Sayonji]

W(F(a)) максимум может быть равно 4 (почему?)

Потому что вектор четырехмерный.

Почему W(a) = 1

Да, потому что там min. Дается верхняя оценка: если взять вектор x с одной ненулевой компонентой, то его W равно 1 и плюс 4 от F(x).

Каким образом вычислить W(F(a)), для каждого ...?

Перебрать, это ведь конечное поле. Перебор всех вариантов это вполне себе доказательство.

Comments

[twintwin1003]

> Потому что вектор четырехмерный.
Какой тогда смысл от заранее определенной матрицы? Её ведь не зря подбирали + в доке сказано, что именно благодаря ей достигается branch number = 5

> Да, потому что там min.
Это ок, уже разобрался, просто оценил вес по битам, а надо было по байтам. Верно же?)

> Перебрать, это ведь конечное поле
Разве только перебор?

[Sayonji]

twintwin1003:
> Какой тогда смысл от заранее определенной матрицы? Её ведь не зря подбирали
5 - это верхняя оценка; для любой матрицы 4x4 branch number будет <= 5. Подобрали матрицу, где оно равно 5.

> Разве только перебор?
Возможно, есть способ анализа, но зачем, если программа из 15 строчек может всё доказать?

[twintwin1003]

> Подобрали матрицу, где оно равно 5
По сути, в этом и вопрос, как доказать, что именно эта матрица дает branch number = 5? Доказать != перебор

> Возможно, есть способ анализа
Да, его и ищу :)