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

Рисунок 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

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

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

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

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

Проект внутризоновой ВОЛП на участке Новосибирск—Карасук
Научно-технический прогресс во многом определяется скоростью передачи информации и ее объемом. Возможность резкого увеличения объемов передаваемой информации наиболее полно реализуется ...

Проектирование релейной защиты и автоматики
В электрической системе имеются следующие источники: ТЭЦ-1, ТЭЦ-2, ТЭЦ-3, ТЭЦ-4, ТЭЦ-5, ГРЭС, СарГЭС и БАЭС. ТЭЦ-1, ГРЭС допускается отдельно не учитывать, так как их мощность по сравнению с ...