3.4 Теорема про лінійну складність комбінуючого генератора

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

Визначення. Довжина найменшого РЗЛЗЗ, що для деякого початкового стану генерує скінченну, або періодичну послідовність називається лінійною складністю послідовності.

Можна довести, що для довільної періодичної послідовності можна знайти РЗЛЗЗ, що її генерує, тому послідовність з малою лінійною складністю у якості гами неприйнятна.

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

Рис. 3.1 Способи комбінування залежних РЗЛЗЗ

Розглянемо комбінуючий генератор , що складається зРЗЛЗЗі булевої функції ускладненнязагального поліноміального виду:

.

Співставимо булевій функції функціюз аргументами з поля дійсних чисел виду

.

Сформулюємо частковий випадок теореми про лінійну складність комбінуючого генератора.

Теорема 3.1. Нехай мінімальні многочлени регістрів є примітивними, а всі числа – попарно взаємно прості. Тоді лінійна складність послідовності, що генерується генератором дорівнює.

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

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

Таким чином необхідно виділити бажані властивості булевих функцій та надати методику побудови таких функцій.

Ці питання відносяться до застосувань теорії булевих функій у криптографії.