4.2 Нелінійність булевої функції
Практика показує, що криптографічні перетворення, які мають властивості близькі до властивостей афінних функцій, у багатьох випадках призводять до істотного зниження стійкості шифрів.
Виходячи з цього, в криптографії важливе значення мають функції, яким не притаманні подібні слабкості. Це є причиною введення різних характеристик щодо якості булевих функцій з точки зору криптографічних застосувань.
Відповідні критерії, строго кажучи, протичать один одному. Це тягне за собою необхідність компромісу, а також ускладнює пошук великих класів функцій з відповідними характеристиками.
Однією з важливих характеристик булевої функції є її нелінійність.
Нелінійністю булевої функції відзмінних називається параметр- відстань віддо множини афінних функцій, тобто значення,.
Через координатні функції це визначення можна узагальнити на булеві відображення , виходячи з властивостей сукупності усіх нетрівіальних лінійних комбінацій виду.
У цьому випадку ,,.
Для вивчення нелінійності та інших властивостей булевих функцій велике значення має перетворення Уолша-Адамара. Це перетворення діє на булевих функціях. Результатом перетворення є цілочислена псевдобулева функція.
При перетворенні Уолша-Адамара элементи 0 и 1 поля розглядаються як звичайні цілі числа. Результатом перетворення функції є цілочислена функція ,,що пов’язана з усіма векторами значень виду . Очевидно, у кожному подібному векторі одиниці відповідають місцям неспівпадінь правої частини з правою частиною відповідної лінійної функції .
Іншими словами, якщо на цих місцях замінити біти у векторі значень на протилежні, топеретвориться на.
Нехай вектор розглядається як запис деякого числа у двійковій системі счислення. У цьому контексті значення часто називається коефіціентом Уолша-Адамара функції з номером.
З урахуванням цього, . Далі ми покажемо, що дозволяє обчислити , де.
Значенням є різниця між кількістю нулів та одиницьу векторі : ,де проходить всю множину аргументів.
Оскільки піднесення мінус одиниці до степенів, що відрізняються на парні ціли доданки, дає той самий результат, то можна записати через звичайний скалярний добуток та дійсне додавання: .
Співставимо вектору значень булевої функції вектор значень псевдобулевої функції , в якому , тобто нулізамінимо на, а одиниці – на. Функція часто позначається якexp.
Це дає інший запис: , який можна розглядати як скалярний добуток .
Зауважимо, що , тобто, це число є парним.
Приклад. Обчислимо і при заданій .
Функції ,і. . . | |||
|
|
|
|
0000 |
0 |
0 |
1 |
0001 |
0 |
0 |
0 |
0010 |
0 |
0 |
0 |
0011 |
0 |
0 |
1 |
0100 |
1 |
1 |
0 |
0101 |
1 |
1 |
1 |
0110 |
1 |
1 |
1 |
0111 |
1 |
1 |
0 |
1000 |
0 |
1 |
1 |
1001 |
0 |
1 |
1 |
1010 |
0 |
1 |
0 |
1011 |
0 |
1 |
0 |
1100 |
1 |
0 |
0 |
1101 |
1 |
0 |
0 |
1110 |
1 |
0 |
0 |
1111 |
1 |
0 |
1 |
Оскільки функція - фіксована, то можна вважати, що аргументом є лінійна функція, яка задається вектором коефіціентів та уявляти результат перетворення Уолша-Адамара у вигляді таблиці з цілочисленим вектором значень .