дываются друг с другом и с содержимым регистра переноса . Результат mod 2 и становится новым битом. Результат, деленный на 2, становится новым содержимым регистра переноса .

Сдвиговый регистр

Сумма mod 2

Сумма

Сумма div 2

Выходной бит

Рис. 17-3. Сдвиговый регистр с обратной связью по переносу.

На 13-й приведен пример 3-битового FCSR с ответвлениями в первой и второй позициях. Пусть его начальное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра.

Сдвиговый регистр

0 0 1

1 0 0

0 1 0

1 0 1 1 1 0

1 1 1

0 1 1

1 0 1

0 1 0 0 0 1

0 0 0

1 0 0

Регистр переноса

0 0 0 0 0 0

Сумма mod 2

Выходной бит

Сумма div 2

Рис. 17-4. 3-битовый FCSR.

Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10 .

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

только три ответвления, поэтому регистр переноса однобитовый . Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, 1, 2 или 3.

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

В третьих, максимальный период FCSR не 2n-1, где n - длина сдвигового регистра. Максимальный период равен где q - это целое число связи. Это число задает ответвления и определяется как:

q = 2ql + 22q2 + 23q3 + . . . + 2nqn-1

(Да, qi отсчитываются слева направо.) И даже хуже, q должно быть простым числом, для которого 2 является примитивным корнем. В дальнейшем предполагается, что q удовлетворяет этому условию.

В приведенном примере q = 2*0 + 4*1 + 8*1 - 1 == 11. 11 - это простое число, примитивным корнем которого является 2. Роэтому максимальный период равен 10.

Не все начальные состояния дают максимальный период . Например, рассмотрим FCSR с начальным значением 101 и регистром переноса, установленным в 4.

Сдвиговый регистр Регистр переноса

1 0 1 4

1 1 0 2

1 1 1 1

1 1 1 1

С этого момента регистр выплевывает бесконечную последовательность единиц .

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

Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путем. Запустите на некоторое время FCSR. (Если m - это начальный объем памяти, а t - количество ответвлений, то достаточно log2(t) + log2(m) +1 тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за n битов, где n - это длина FCSR, не используйте это начальное состояние. В противном случае его можно использовать . Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми.

В 16-й перечислены все целые числа связи, меньшие 10000, для которых 2 является примитивным корнем . Для всех этих чисел максимальный период равен q-1. Чтобы получить по одному из этих чисел последовательность ответвлений, рассчитаем бинарный состав q+1. Например, 9949 дает последовательность ответвлений в позициях 1, 2, 3, 4, 6, 7, 9, 10 и 13, так как

9950 = 213 + 210 + 29 + 27 + 26 + 24 + 23 + 22 + 21

В 15-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR максимальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и 128 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений , а, b, c и d.

q = 2а + 2b + 2c + 2d - 1

Для создания FCSR с периодом q - 1 можно использовать любую из этих последовательностей .

Идея использовать в криптографии FCSR все еще является очень новой, впервые она была выдвинута Энди Клаппером (Andy Klapper) и Марком Горески (Mark Goresky) [844, 845, 654, 843, 846]. Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении неких чисел, называемых 2-adic. Соответствующая теория выходит далеко за пределы этой книги, но в мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить и 2-adic сложность. Существует 2-adic аналог и для алгоритма Berlekamp-Massey. Это означает, что перечень возможных потоковых шифров по крайней мере удвоился. Все, что можно делать с LFSR, можно делать и с FCSR.

Существуют работы, развивающие эту идею и рассматривающие несколько регистров переноса . Анализ этих генераторов последовательностей основан на сложении разветвленных расширений 2-adic чисел [845, 846].

17.5 Потоковые шифры, использующие FCSR

Потоковые шифры на базе FCSR не описаны в литературе, теория все еще слишком нова. Чтобы как-то "погнать зайца дальше" я предложу здесь несколько вариантов . Я охватываю два направления: предлагаю потоковые шифры на базе FCSR, которые совпадают с ранее предложенными генераторами LFSR, а также предлагаю потоковые шифры, использующие FCSR и LFSR одновременно. Безопасность первого варианта возможно может быть проанализирована с помощью 2-adic чисел, генераторы второго варианта не могут быть проанал и-зированы с использованием алгебраических методов - возможно их анализ может быть выполнен только косвенным образом. В любом случае, важно выбирать LFSR и FCSR с взаимно простыми периодами.

Все придет потом. Сейчас мне неизвестно ни о реализации, ни об анализе ни одной из этих идей . Подождите несколько лет и просматривайте литературу, прежде чем вы поверите в одну из этих идей .

Каскадные генераторы

Существует два способа использовать FCSR в каскадных генераторах:

- Каскад FCSR. Каскад Голлманна с FCSR вместо LFSR.

- Каскад LFSR/FCSR. Каскад Голлманна с генераторами, меняющими LFSR на FCSR и наоборот.

Комбинированные генераторы FCSR

Эти генераторы используют переменное количество LFSR и/или FCSR и множество функций, объединяющих регистры. Операция XOR разрушает алгебраические свойства FCSR, поэтому имеет смысл использовать эту операцию для их объединения. Генератор, показанный на 12th, использует переменное число FCSR. Его выходом является XOR выходов отдельных FCSR.

Другими генераторами, являющимися развитием аналогичных линий, являются :

- Генератор четности FCSR. Все регистры - FCSR, а объединяющая функция - XOR.

- Генератор четности LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью XOR.

- Пороговый генератор FCSR. Все регистры - FCSR, а объединяющей функцией является мажорирование .

- Пороговый генератор LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью мажорирования.

- Суммирующий генератор FCSR. Все регистры - FCSR, а объединяющая функция - сложение с переносом.

- Суммирующий генератор LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью сложения с переносом.

Табл. 17-1.

Целые значения связи для FCSR с максимальным периодом