Линейные рекуррентные генераторы

Рисунок 2.10-Каскад Голлмана

Концептуально они очень просты и могут быть использованы для генерации последовательностей с огромными периодами, огромными линейными сложностями и хорошими статистическими свойствами. Они чувствительны к вскрытию, называемому запиранием (lock-in) и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром.

Аддитивные генераторы

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

Начальное состояние генератора представляет собой массив n-битовых слов: 8-битовых слов, 16-битовых слов, 32-битовых слов, и т.д.: Х1 ,Х2, X3, ., Хm. Это первоначальное состояние и является ключом. i-ое слово генератора получается как:

= (Xi-a + Xi-a + Хi-c+ + Xi-m) mod 2n (2.12)

При правильном выборе коэффициентов а, b, с, . . . , т период этого генератора не меньше 2n-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.

Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего аддитивного генератора максимальна.

= (Xi-55 +Xi-24) mod2n (2.13)

2.4.7.1 Fish

Fish - это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе. Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста. Название алгоритма представляет собой сокращение от Fibonacci shrinking generator - прореживаемый генератор Фиббоначи.

Во-первых используйте два следующих аддитивных генератора. Ключом является начальные состояния этих генераторов.

= (Ai-55+Ai-24) mod232= (Bi-52 +Bi-19) mod 232

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита Вi: если его значение равно 1, то пара используется, если 0 - игнорируется. Сj- это последовательность используемых слов Ai , a Dj - это последовательность используемых слов Вi . Для генерации двух 32-битовых слов-результатов К2j и K2j+1 эти слова используются парами - C2j, C2j+1, D2j, D2j+1.

j = C2j + (D2j, ^ D2j+1)j = D2j+1 ^ (Ej, ^ C2j+1)j = E2j + F2jj+1 = C2j+1 + F2j

Этот алгоритм быстр. на процессоре i486/33 реализация Fish на языке С шифрует данные со скоростью 15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 240.

Mush

Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко. Возьмем два аддитивных генератора: А и В. Если бит переноса А установлен, тактируется В. Если бит переноса В установлен, тактируется А. Тактируем А и при переполнении устанавливаем бит переноса. Тактируем В и при переполнении устанавливаем бит переноса. Окончательным выходом является XOR выходов А и В. Проще всего использовать те же генераторы, что и в Fish:

= (Ai-55+Ai-24) mod232= (Bi-52 +Bi-19) mod 232

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

МЕТОДЫ ОЦЕНКИ КАЧЕСТВА ГЕНЕРАТОРОВ ПСП

Читайте также

Приемно-контрольная панель на базе микроконтроллера
Приемно-контрольные приборы (ПКП) осуществляют прием информации от извещателей, ее запоминание, обработку и передачу соответствующим службам, а также выполняют процедуры взятия под охра ...

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

Нанотехнологии в науке и технике
В течение тысячелетий человек использовал в быту и технике макроскопические тела, состоящие из большого числа атомов, будь это каменный топор или авиалайнер. Первая научно- ...