Главная | Обратная связь

Поточные шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

[править]Теоретическая основа

Есть несколько причин использования линейных регистров сдвига в криптографии:

· высокое быстродействие криптографических алгоритмов

· применение только простейших операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах

· хорошие криптографические свойства (генерируемые последовательности имеют большой период и хорошие статистические свойства)

· легкость анализа с использованием алгебраических методов за счет линейной структуры

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

· содержимое ячейки формирует часть выходной последовательности;

· содержимое -той ячейки перемещается в ячейку для любого , .

· новое содержимое ячейки определяется битом обратной связи, который вычисляется сложением по модулю 2 с определёнными коэффициентами битов ячеек .

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

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

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

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

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

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

Генераторы «стоп-пошёл»

Чередующийся генератор «стоп-пошёл»

Этот генератор использует вывод одного РСЛОС для управления тактовой частотой другого РСЛОС. Тактовый выход РСЛОС-2 управляется выходом РСЛОС-1, так что РСЛОС-2 может менять своё состояние в момент времени t, только если выход РСДОС-1 в момент времени t-1 был равен единице. Но эта схема не устояла перед корреляционным вскрытием.

Поэтому был предложен улучшенный генератор, основанный на этой же идее. Его называют чередующийся генератор «стоп-пошёл». В нём используются три РСЛОС различной длины. РСЛОС-2 тактируется, когда выход РСЛОС-1 равен единице, а РСЛОС-3, когда выход РСЛОС-1 равен нулю. Выходом генератора является сумма по модулю 2 РСЛОС-2 и РСЛОС-3. У данного генератора большой период и большая линейная сложность. Его авторы показали также способ корреляционного вскрытия РСЛОС-1, но это не сильно ослабляет генератор.

Пороговый генератор

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

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

Для случая трёх регистров сдвига генератор можно представить как:

Этот генератор похож на генератор Геффа за исключением того, что пороговый генератор обладает большей линейной сложностью. Его линейная сложность равна:

где , , — длины первого, второго и третьего регистров сдвига.

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

 

№ 13 Распределение секретных ключей. Подход на основе алгоритма традиционного шифрования. Продолжительность использования сеансового ключа.

Распределение ключей

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

^ Распределение с помощью протоколов с секретным ключом. Если долговременные секретные ключи распределены между пользователями и неким центром, который обычно называют центром доверия, то его можно использовать для генерирования ключей и обмена между любыми двумя пользователями всякий раз, когда в этом возникает необходимость. Протоколы, предназначенные для этой цели, — предмет обсуждения настоящей главы. Обычно они достаточно эффективны, но не лишены и недостатков. В частности, этот способ распределения предусматривает, что как оба пользователя, так и центр работают в режиме онлайн. Кроме того, статичные ключи при этом должны распределяться физическим путем.

^ Распределение с помощью протоколов с открытым ключом. Используя криптосистемы с открытым ключом, партнеры, не доверяющие посредникам и лишенные возможности встретиться, могут договориться об общем секретном ключе в режиме онлайн в соответствии с протоколом об обмене ключей. Это наиболее распространенное приложение техники шифрования с открытым ключом. Вместо того, чтобы шифровать большой объем данных непосредственно с помощью открытого ключа, стороны предварительно согласовывают секретный ключ. Затем для шифрования фактической информации применяется симметричный шифр с согласованным ключом.

Первый протокол, с которым мы познакомимся — это протокол широкоротой лягушки, предложенный Барроузом. Протокол передает ключ от А к В через посредника S, используя лишь 2 сообщения, но имеет множество недостатков. В частности, для его реализации необходима синхронизация часов, что создает дополнительные проблемы. В нем предполагается, что А выбирает сеансовый ключ и пересылает его пользователю В. Это означает, что пользователь B верит в компетентность A, в его способность создать стойкий ключ и хранить его в секрете. Такое сильное требование служит основной причиной слабого применения на практике протокола широкоротой лягушки. С другой стороны, это довольно простой и хороший пример, на котором можно продемонстрировать формальный анализ протоколов, чему, в частности, посвящена глава.

Протокол состоит из обмена двумя сообщениями (рис. 6.1):

Рис. 6.1. Протокол широкоротой лягушки

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

 

Рассмотрим более сложные протоколы, начав с одного из самых знаменитых, а именно, с протокола Нидхейма-Шредера. Этот протокол был разработан в 1978 году и является самым изучаемым на сегодняшний день. Он получил известность благодаря тому, что даже самый простой протокол может долгое время скрывать свои пробелы в обеспечении безопасности. Обмен письмами идет по следующей схеме (рис. 6.2):

Рис. 6.2. Протокол Нидхейма-Шредера

Теперь мы разберем каждое из сообщений протокола подробно и объясним их предназначение.

- В первом пользователь А сообщает центру доверия «5, что он намерен получить ключ для переписки с В. Обратите внимание на то, что к сообщению прикреплена уникальная числовая вставка, созданная А.

- S генерирует ключ и посылает его А вторым письмом. В него включается числовая вставка по которой клиент А узнает, что полученное сообщение было послано в ответ на его запрос. Сеансовый ключ зашифровывается с помощью и прикрепляется к этому сообщению.

- В третьем письме сеансовый ключ пересылается пользователю В.

- Участник В должен проверить, что отправителем этого послания действительно является А, т. е. он должен удостовериться, что А все еще действует, и в четвертом сообщении протокола он пересылает свою числовую вставку участнику А в зашифрованном виде.

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

Основной недостаток протокола Нидхейма-Шредера заключается в том, что в результате его работы у пользователя В нет оснований считать, что полученный ключ является новым, — факт, который был замечен только спустя некоторое время после опубликования протокола. Противник, найдя сообщения и ключ предыдущих сеансов, может использовать старые письма вместо последних трех сообщений, в которых упоминается В. Таким образом нападающий может обмануть S, вынуждая его принять свой ключ, в то время, как В предполагает, что ведет переговоры с А.