Фільтр-генератори і булеви функції

Функція, що бере участь у схемі генератора називається функцією ускладнення. Для двійкових регістрів зсуву ця функція є булєвою.

Аналіз стійкості криптосхем, основаних на комбінуванні регістрів зсуву природним образом приводить до необхідності дослідження математичних властивостей булєвых відображень, під якими розуміються відображення () конечномерных векторних просторів над полем з двох елементів.

Інтуїтивно очевидна необхідність використання в криптографічних застосуваннях відображень, що перетворюють послідовності своїх аргументів найбільш складним, хаотичним чином.

На практиці даний підхід приводить до двох взаємозалежних задач: визначити, які формальні властивості відображень визначають його бажану складність (якість), а також вказати ефективний алгоритм псевдослучайного вибору відображення, що володіє необхідними властивостями.

Таблиця, що представляє булєву функцію, складається з рядків виду, причому набори аргументів лексикографічно упорядковані. Крайній правий стовпець таблиці називається вектором значень функції і часто позначається як. Кількість булєвих функцій дорівнює кількості векторів значень, тобто.

В упорядкованому списку аргументів будь-які фіксованих стовпців містять усі -мірні двійкові набори. Повна сукупність таких наборів зустрічається в зазначених стовпцях раз.

Позначимо кількість одиниць у через. Величина називається вагою булєвої функції. При рівноймовірному і незалежному виборі аргументів булєвї функції імовірності її значень, що дорівнюють одиниці і нулю, відповідно рівні,.

Міра називається відстанню Хемінга між функціями і. Відстанню Хемінга від функції до заданої множини функцій називається значення.

Важливою для криптографічних застосувань властивістю булєвых відображень, є рівноймовірність (збалансованість, урівноваженість).

Ця властивість полягає в тім, що всі елементи області значень мають прообрази і ці прообрази мають однакову потужність, тобто для кожного. Кількість нулів і одиниць у векторі значень рівноймовірної булєвой функції однаково.

Лінійні функції (форми) виду, де - вектор коефіцієнтів,, рівноймовірні.

Рівноймовірні також афінні функції виду,.

Практика показує, що криптографічні перетворення, яким притаманні властивості близьки до властивостей афінних функцій, у багатьох випадках призводять до істотного зниження стійкості шифрів. Таким чином, бажаною якістю функції є її нелінійність, що розуміється в широкому змісті: як заперечення лінійності. Наприклад, потрібно, щоб функція ускладнення мала максимально можливу, при інших умовах, відстань Хэмінга до множини афінных функцій. Іншою вимогою є відсутність (ослаблення) статистичних зв'язків між бітами входу і виходом функції. Наприклад, вимога кореляційної иммунности.

Функція є кореляційно імунною порядку, якщо для будь-якої сукупності номерів перемінних,, при будь-яких значеннях виконується співвідношення. Для такої функції ніяка підмножина перемінних не має особливостей щодо звуження сукупності їхніх можливих значень, виходячи з розподілу.

Дата добавления: 2014-10-15