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

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

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

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

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

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

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

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

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

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

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

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

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

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

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