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

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

При правильном выборе коэффициентов а, b, с, . . . , т период этого генератора не меньше 2n-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.
Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего аддитивного генератора максимальна.

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

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита Bt: если его значение равно 1, то пара используется, если 0 - игнорируется .- это последовательность используемых слов Ai, a- это последовательность используемых слов Bt. Для генерации двух 32-битовых слов-результатови Ky+i эти слова используются парами -

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

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

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