Интернет магазин китайских планшетных компьютеров

Компьютеры - Поточный шифр - Потоковые шифры основанные на РСЛОС. Усложнение

К сожалению, выходная последовательность РСЛОС легко предсказуема. Так, зная 2L знаков выходной последовательности, легко найти исходное заполнение регистра, решив систему линейных уравнений.
Считается, что для криптографического использования выходная последовательность РСЛОС должна иметь следующие свойства:

• большой период
• высокую линейную сложность
• хорошие статистические свойства

Существует несколько методов проектирования генераторов ключевого потока, которые разрушают линейные свойства РСЛОС и тем самым делают такие системы криптографически более стойкими:
1. использование нелинейной функции, объединяющей выходы нескольких РСЛОС
2. использование нелинейной фильтрующей функции для содержимого каждой ячейки единственного РСЛОС
3. использование выхода одного РСЛОС для управления синхросигналом одного РСЛОС.

Нелинейная комбинация генераторов

Нелинейная комбинация генераторов

Известно, что каждая Булева функция может быть записана как сумма по модулю 2 произведений порядков независимых переменных, . Это выражение называется алгебраической нормальной формой функции . Нелинейным порядком функции f называется максимальный порядок членов в записи её алгебраической нормальной формы.
Например, Булева функция имеет нелинейный порядок 3. Максимально возможный нелинейный порядок Булевой функции равен количеству переменных
Предположим теперь, что у нас регистров сдвига с линейной обратной связью, их длины попарно различны и больше двух. Все регистры объединены нелинейной функцией , как показано на рисунке. Функция представлена в алгебраической нормальной форме. Тогда линейная сложность потока ключей равна .
Если – попарно взаимно-простые числа, то длина периода ключевого потока равна: . Например, если , то . И длина периода ключевого потока равна .

Генератор Геффа

Пример:
В этом генераторе используются три РСЛОС, объединённые нелинейным образом. Длины этих регистров попарно простые числа.
Нелинейную функцию для данного генератора можно записать следующим образом:



Длина периода:

Линейная сложность:

Генератор Геффа криптографически слаб, потому что информация о состояниях генераторов РСЛОС 1 и РСЛОС 3 содержится в его выходной последовательности. Для того чтобы понять это, обозначим -ые выходные биты РСЛОС 1,2,3 и потока ключей, соответственно. Тогда корреляционная вероятность последовательности x₁ по отношению к последовательности :



Аналогично,
По этой причине, несмотря на длинный период и достаточно высокую линейную сложность, генератор Геффа поддаётся корреляционным атакам.

Генератор на нелинейном фильтре

Генераторы на нелинейных фильтрах

Выход каждой ячейки подаётся на вход некоторой нелинейной булевой фильтрующей функции . Предположим, что фильтрующая функция порядка , тогда линейная сложность потока ключей не больше .

Генераторы основанные на управлении синхросигналом

В нелинейных комбинациях генераторов и генераторах на нелинейных фильтрах перемещение данных во всех РСЛОС контролируется одним синхросигналом.
Основная идея функционирования рассматриваемого типа генераторов – внести нелинейность в работу генераторов потока ключей, основанных на РСЛОС, путём управления синхросигналом одного регистра выходной последовательностью другого.
Есть 2 типа генераторов основанных на управлении синхросигналом:
1. генератор переменного шага
2. сжимающий генератор.

Генератор переменного шага

Основная идея:
РСЛОС 1 используется для управления передвижением битов двух других РСЛОС 2 и 3.

Генератор переменного шага

Алгоритм работы:
1. Регистр РСЛОС 1 синхронизован внешним синхросигналом
2. Если на выходе регистра РСЛОС 1 единица, то на регистр РСЛОС 2 подаётся синхросигнал, а РСЛОС 3 повторяет свой предыдущий выходной бит
3. Если на выходе регистра РСЛОС 1 ноль, то на регистр РСЛОС 3 подаётся синхросигнал, а РСЛОС 2 повторяет свой предыдущий выходной бит
4. Выходная последовательность битов генератора с переменным шагом является результатом применения операции побитового исключающего ИЛИ к выходным последовательностям регистров РСЛОС 2 и РСЛОС 3.

Увеличение безопасности генераторов с переменным шагом:

• длины регистров РСЛОС 1, РСЛОС 2, РСЛОС 3 должны быть выбраны попарно простыми числами
• длины этих регистров должны быть близкими числами.

Сжимающий генератор

Сжимающий генератор

Контролирующий регистр РСЛОС 1 используется для управления выходом РСЛОС 2. Алгоритм:

1. Регистры РСЛОС 1 и РСЛОС 2 синхронизованы общим синхросигналом;
2. Если выходной бит РСЛОС 1 равен 1, выход генератора формируется выходным битом регистра РСЛОС 2;
3. Если выходной бит РСЛОС 1 равен 0, выходной бит регистра РСЛОС 2 отбрасывается.

Сжимающий генератор прост, масштабируем и имеет хорошие защитные свойства. Его недостаток состоит в том, что скорость генерации ключа не будет постоянной, если не принять некоторых предосторожностей.

Для увеличения безопасности сжимающего генератора:

• длины регистров РСЛОС 1 и РСЛОС 2 должны быть взаимно простыми числами;
• желательно использовать скрытое соединение между регистрами РСЛОС 1 и РСЛОС 2.