В регистре сдвига с линейной обратной связью выделяют две части (модуля): собственно регистра сдвига и схемы (или подпрограммы) вычисляющих значение вдвигаемого бита. Регистр состоит из функциональных ячеек (или битов машинного слова или нескольких слов), в каждой из которой хранится текущее состояние одного бита . Количество ячеек , называют длиной регистра. Биты (ячейки) обычно нумеруются числами , каждая из которых способна хранить бит, причём в ячейку происходит вдвижение вычисленного бита, а из ячейки извлекается выдвигаемый очередной сгенерированный бит. Вычисление вдвигаемого бита обычно производится до сдвига регистра, и только после сдвига значение вычисленного бита помещается в ячейку .

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как ) и наиболее часто применяется в таких регистрах.

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

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

В течение каждого такта времени выполняются следующие операции:

Регистр сдвига с линейной обратной связью

Таким образом, в качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:

Свойства примитивных многочленов

Свойства

Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами ассоциированного многочлена . Его ненулевые коэффициенты называются отводами , как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи.

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

Линейная сложность бинарной последовательности - одна из самых важных характеристик работы РСЛОС. Введём следующие обозначения:

Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом:

Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов .

Свойства линейной сложности

Пусть и - двоичные последовательности. Тогда:

Корреляционная независимость

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

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

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

Пример

Для РСЛОС с ассоциированным многочленом генерируемая последовательность имеет вид . Допустим, перед началом процесса в регистре записана последовательность , тогда период генерируемого потока битов будет равен 7 со следующей последовательностью:

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор. Иными словами, период последовательности оказался равен 7, что произошло ввиду примитивности многочлена .

Алгоритмы генерации примитивных многочленов

Готовые таблицы

Вычисление примитивности многочлена - достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-битового сдвигового регистра имеется последовательность . Это означает, что для генерации нового бита необходимо с помощью функции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Код для такого РСЛОС на языке Си следующий:

Int LFSR (void ) { static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 ) << 31 ) | (S>> 1 ) ; return S & 1 ; }

Программные реализации РСЛОС генераторов достаточно медленны и быстрее работают, если они написаны на ассемблере, а не на языке Си. Одним из решений является использование параллельно 16-ти РСЛОС (или 32, в зависимости от длины слова в архитектуре конкретного компьютера). В такой схеме используется массив слов, размер которого равен длине РСЛОС, а каждый бит слова массива относится к своему РСЛОС. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности. [нужен пример кода ] (См.: bitslice).

Конфигурация Галуа

Конфигурация Галуа регистра сдвига с линейной обратной связью

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

Int LFSR (void ) { static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; }

Выигрыш состоит том, что все XOR выполняются за одну операцию.

• можно доказать, что приведенная первой конфигурация Фибоначчи и приведенная здесь конфигурация Галуа дают одинаковые последовательности (длиной 2 32 −1), но смещённые по фазе одна от другой
• цикл из фиксированного числа вызовов функции LFSR в конфигурации Галуа выполняется примерно в два раза быстрее, чем в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5)
• обратите внимание, что в конфигурации Галуа порядок бит в слове, определяющем обратную связь, обратный по сравнению с конфигурацией Фибоначчи

Примеры генераторов

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

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

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

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

Каскад Голлманна

Каскад Голлманна

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

Эта идея проста и может быть использована для генерации последовательностей с огромными периодами, большими линейными сложностями и хорошими статистическими свойствами. Но, к сожалению, они чувствительны к вскрытию, называемому «запиранием» (lock-in). Для большей стойкости рекомендуется использовать k не менее 15. Причём лучше использовать больше коротких РСЛОС, чем меньше длинных РСЛОС.

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

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

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

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

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

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

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

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

Другие виды

Самопрореживающие

Самопрореживающими называются генераторы, которые управляют собственной частотой. Было предложено два типа таких генераторов. Первый состоит из регистра сдвига с обратной линейной связью и некоторой схемы, которая тактирует этот регистр, в зависимости от того какими получаются выходные значения регистра сдвига. Если выход РСЛОС равен единице, то регистр тактируется d раз. Если выход равен нулю, то регистр тактируется k раз. Второй имеет практически ту же конструкцию, но несколько модифицированную: в схеме тактирования на вход, в качестве проверки на 0 или 1, поступает не сам выходной сигнал, а XOR определённых битов регистра сдвига с линейной обратной связью. К сожалению, этот вид генератора не безопасен.

Многоскоростной генератор с внутренним произведением

Этот генератор использует два регистра сдвига с линейной обратной связью с разными тактовыми частотами: РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d раз больше чем РСЛОС-1. Отдельные биты этих регистров объединяются операцией AND. Затем с выходами операции AND выполняется операция XOR. С этого блока XOR снимается выходная последовательность. Опять же и этот генератор не безупречен (Он не выстоял перед вскрытием линейной согласованности. Если - длина РСЛОС-1,- длина РСЛОС-2, а d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной ), но он имеет высокую линейную сложность и обладает великолепными статистическими характеристиками.

Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи .

Рис 19. Регистр сдвига с обратной связью.

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

Простейший тип регистров сдвига – регистр сдвига с линейной обратной связью (РСЛОС или ЛРС). Обратная связь – простая операция XOR над некоторыми битами регистра. Перечень этих битов определяется характеристическим многочленом и называется последовательностью отводов . Иногда такую схему называют конфигурацией Фибоначчи .

Рис.20. РСЛОС конфигурации Фибоначчи.

При программной реализации РСЛОС пользуются модифицированной схемой: для генерации нового значащего бита вместо использования битов последовательности отводов над каждым ее битом выполняется операция XOR с выходом генератора, заменяя старый бит последовательности отводов. Такую модификацию иногда называют конфигурацией Галуа .

Рис.21. РСЛОС конфигурации Галуа.

n -битовый РСЛОС может находиться в одном из 2 n – 1 внутренних состояний. Это значит, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2 n – 1 битов (заполнение нулями совершенно бесполезно). Прохождение всех 2 n – 1 внутренних состояний возможно только при определенных последовательностях отводов. Такие регистры называют РСЛОС с максимальным периодом. Для обеспечения максимального периода РСЛОС необходимо, чтобы его характеристический многочлен был примитивным по модулю 2. Степень многочлена является длиной регистра сдвига. Примитивный многочлен степени n – это такой неприводимый многочлен, который является делителем , но не является делителем x d + 1 для всех d , являющихся делителями 2 n – 1. (При обсуждении многочленов термин простое число заменяется термином неприводимый многочлен ). Характеристический многочлен приведенных на рисунках РСЛОС:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

примитивен по модулю 2. Период такого регистра будет максимальным, циклически проходя все 2 32 – 1 значений до их повторения. Наиболее часто используются прореженные многочлены, т.е. у которых есть только некоторые коэффициенты. наиболее популярны трехчлены.

Важным параметром генератора на базе РСЛОС, является линейная сложность . Она определяется как длина n самого короткого РСЛОС, который может имитировать выход генератора. Линейная сложность важна, поскольку при помощи простого алгоритма Берленкемпа-Мэсси можно воссоздать такой РСЛОС, проверив всего 2n битов гаммы. С определением нужного РСЛОС поточный шифр фактически взламывается.

Для построения поточных шифров очень часто используют последовательности на регистрах сдвига. Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи, как показано на рис. 87. Сам регистр сдвига представляет собой последовательность битов, число которых определяет длину регистра. Так, если в регистре задействовано п бит, то говорят, что n-битовый регистр сдвига. При каждом извлечении бита все биты регистра сдвига сдвигаются вправо на одну позицию, обычно в сторону младших разрядов. Периодом регистра сдвига называют длину получаемой последовательности до начала ее повторения .

Рис. 87.

В качестве обратной связи может выступать любая математическая функция, производящая действие над битами. К простейшему типу регистра сдвига с обратной связью относится регистр сдвига с линейной обратной связью (РСЛОС) . В РСЛОС обратная связь представляет собой просто операцию сложения по модулю 2 (XOR) над некоторыми битами регистра; перечень этих битов называется последовательностью отводов, или точек съема, как показано на рис. 88. Иногда такую схему называют конфигурацией Фибоначчи . Благодаря простоте последовательности обратной связи, для анализа РСЛОС можно использовать довольно развитую математическую теорию. В любом случае качество вырабатываемой ПСП оценивают специальным набором тестов.

Рис. 88.

Записываются РСЛОС в виде полиномов. При этом сте- перь первого элемента полинома указывает на количество битов в регистре сдвила, а степенные показатели остальных членов полинома показывают, какие будут использованы точки съема. Так, например, запись х 4 + х + 1 обозначает, что будет использован регистр из четырех элементов, для которого в образовании обратной связи будут участвовать биты bi и b 0 (рис. 89).

Рис. 89. 4

Рассмотрим работу регистра, представленного на рис. 89. Инициализируем его, например, значением 0101 (начальная инициализация может выполняться любой последовательностью битов, кроме последовательности из одних нулей, так как в таком случае обратная связь всегда будет образовывать значение ноль и регистр не будет вырабатывать ожидаемую ПСП). Итак, в регистре происходит сдвиг вправо на одну позицию. Самый младший бит, равный 1, вытесняется из регистра и образует первый бит ПСП. Те биты, которые были в позициях Ь, и Ь 0 , до сдвига складываются по модулю 2 и образуют новый

старший бит регистра. Наглядный пример работы рассматриваемого РСЛОС приведен на рис. 90.

Рис. 90.

Как видно из рис. 90, заполнение регистра пройдет через вес 15 из 16 возможных состояний (ранее мы определили, что шестнадцатое состояние, когда РСЛОС равен 0000, рассматривать нельзя). После этого заполнение регистра станет опять равно начальному значению 0101, и выработка битовой последовательности начнет повторяться. Выходной последовательностью регистра будет строка младших значащих битов (до горизонтальной линии на рис. 90): 101011110001001. Размер битовой последовательности до ее повторения называется периодом. Для обеспечения максимального периода конкретного РСЛОС (т. с. для того, чтобы регистр прошел через вес возможные внутренние состояния) многочлен, который определяет работу регистра, должен быть примитивным по модулю 2. Как и в случае с большими простыми числами, не существует способа генерации таких многочленов. Можно лишь взять многочлен и проверить, является он неприводимым по модулю 2 или нет. В общем случае примитивный многочлен степени п - это такой неприводимый многочлен, который является делителем х 2 ” +1, но не является делителем x d +1 для всех d, являющихся делителями 2"-1 . В работе Б. Шнайера приведена таблица некоторых многочленов, которые являются неприводимыми по модулю 2.

Обобщая знания, полученные в результате рассмотрения примера работы РСЛОС (рис. 90), можно сказать, что п- битовый РСЛОС может находиться в одном из 2”-1 внутренних состояний. Теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2 п -1 битов. Такие регистры называются регистрами РСЛОС с максимальным периодом. Получившийся выход называют т-последовательностью .

В регистре сдвига с линейной обратной связью выделяют две части (модуля): собственно регистра сдвига и схемы (или подпрограммы) вычисляющих значение вдвигаемого бита. Регистр состоит из функциональных ячеек (или битов машинного слова или нескольких слов), в каждой из которой хранится текущее состояние одного бита . Количество ячеек , называют длиной регистра. Биты (ячейки) обычно нумеруются числами , каждая из которых способна хранить бит, причём в ячейку происходит вдвижение вычисленного бита, а из ячейки извлекается выдвигаемый очередной сгенерированный бит. Вычисление вдвигаемого бита обычно производится до сдвига регистра, и только после сдвига значение вычисленного бита помещается в ячейку .

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как ) и наиболее часто применяется в таких регистрах.

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

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

В течение каждого такта времени выполняются следующие операции:

Регистр сдвига с линейной обратной связью

Таким образом, в качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:

Свойства примитивных многочленов

Свойства

Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами ассоциированного многочлена . Его ненулевые коэффициенты называются отводами , как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи.

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

Линейная сложность бинарной последовательности - одна из самых важных характеристик работы РСЛОС. Введём следующие обозначения:

Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом:

Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов .

Свойства линейной сложности

Пусть и - двоичные последовательности. Тогда:

Корреляционная независимость

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

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

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

Пример

Для РСЛОС с ассоциированным многочленом генерируемая последовательность имеет вид . Допустим, перед началом процесса в регистре записана последовательность , тогда период генерируемого потока битов будет равен 7 со следующей последовательностью:

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор. Иными словами, период последовательности оказался равен 7, что произошло ввиду примитивности многочлена .

Алгоритмы генерации примитивных многочленов

Готовые таблицы

Вычисление примитивности многочлена - достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-битового сдвигового регистра имеется последовательность . Это означает, что для генерации нового бита необходимо с помощью функции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Код для такого РСЛОС на языке Си следующий:

Int LFSR (void ) { static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 ) << 31 ) | (S>> 1 ) ; return S & 1 ; }

Программные реализации РСЛОС генераторов достаточно медленны и быстрее работают, если они написаны на ассемблере, а не на языке Си. Одним из решений является использование параллельно 16-ти РСЛОС (или 32, в зависимости от длины слова в архитектуре конкретного компьютера). В такой схеме используется массив слов, размер которого равен длине РСЛОС, а каждый бит слова массива относится к своему РСЛОС. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности. [нужен пример кода ] (См.: bitslice).

Конфигурация Галуа

Конфигурация Галуа регистра сдвига с линейной обратной связью

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

Int LFSR (void ) { static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; }

Выигрыш состоит том, что все XOR выполняются за одну операцию.

• можно доказать, что приведенная первой конфигурация Фибоначчи и приведенная здесь конфигурация Галуа дают одинаковые последовательности (длиной 2 32 −1), но смещённые по фазе одна от другой
• цикл из фиксированного числа вызовов функции LFSR в конфигурации Галуа выполняется примерно в два раза быстрее, чем в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5)
• обратите внимание, что в конфигурации Галуа порядок бит в слове, определяющем обратную связь, обратный по сравнению с конфигурацией Фибоначчи

Примеры генераторов

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

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

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

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

Каскад Голлманна

Каскад Голлманна

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

Эта идея проста и может быть использована для генерации последовательностей с огромными периодами, большими линейными сложностями и хорошими статистическими свойствами. Но, к сожалению, они чувствительны к вскрытию, называемому «запиранием» (lock-in). Для большей стойкости рекомендуется использовать k не менее 15. Причём лучше использовать больше коротких РСЛОС, чем меньше длинных РСЛОС.

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

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

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

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

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

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

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

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

Другие виды

Самопрореживающие

Самопрореживающими называются генераторы, которые управляют собственной частотой. Было предложено два типа таких генераторов. Первый состоит из регистра сдвига с обратной линейной связью и некоторой схемы, которая тактирует этот регистр, в зависимости от того какими получаются выходные значения регистра сдвига. Если выход РСЛОС равен единице, то регистр тактируется d раз. Если выход равен нулю, то регистр тактируется k раз. Второй имеет практически ту же конструкцию, но несколько модифицированную: в схеме тактирования на вход, в качестве проверки на 0 или 1, поступает не сам выходной сигнал, а XOR определённых битов регистра сдвига с линейной обратной связью. К сожалению, этот вид генератора не безопасен.

Многоскоростной генератор с внутренним произведением

Этот генератор использует два регистра сдвига с линейной обратной связью с разными тактовыми частотами: РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d раз больше чем РСЛОС-1. Отдельные биты этих регистров объединяются операцией AND. Затем с выходами операции AND выполняется операция XOR. С этого блока XOR снимается выходная последовательность. Опять же и этот генератор не безупречен (Он не выстоял перед вскрытием линейной согласованности. Если - длина РСЛОС-1,- длина РСЛОС-2, а d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной ), но он имеет высокую линейную сложность и обладает великолепными статистическими характеристиками.

Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register , LFSR ) - регистр сдвига битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов , что находит применение, в частности, в криптографии .

Описание

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

Принцип работы

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

Корреляционная независимость

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

Программная реализация

Программные реализации РСЛОС достаточно медленны и работают быстрее, если они написаны на ассемблере . Одно из решений - параллельное использование 16-ти РСЛОС (или 32-х, в зависимости от длины слова в архитектуре компьютера). В такой схеме используется массив слов, размер которого равен длине регистра сдвига , а каждый бит слова относится к своему РСЛОС. Так как используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности генератора .

Конфигурация Фибоначчи

Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность (32 , 31 , 30 , 28 , 26 , 1) {\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)} . Это означает, что для генерации нового бита необходимо с помощью операции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Полученный РСЛОС имеет максимальный период 2 32 − 1 {\displaystyle 2^{32}-1} . Код для такого регистра на языке Си следующий:

int LFSR_Fibonacci (void ) { static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | (S >> 1 ); return S & 0x00000001 ; }

Конфигурация Галуа

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

Код для регистра сдвига длины 32 бит на языке Си следующий:

int LFSR_Galois (void ) { static unsigned long S = 0x00000001 ; if (S & 0x00000001 ) { S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; return 1 ;} else { S >>= 1 ; return 0 ;} }

Стоит отметить, что цикл из фиксированного числа вызовов функции LFSR_Galois в конфигурации Галуа выполняется примерно в 2 раза быстрее, чем функция LFSR_Fibonacci в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5).

Пример генерируемой последовательности

Конфигурация Фибоначчи

Пусть РСЛОС задаётся характеристическим многочленом x 3 + x + 1 {\displaystyle x^{3}+x+1} . Это значит, что битами отвода будут 2-й и 0-й, а единица в формуле многочлена означает, что 0-й бит - входной. Функция обратной связи имеет вид S j = S j − 1 ⊕ S j − 3 {\displaystyle S_{j}=S_{j-1}\oplus S_{j-3}} . Допустим, изначальным состоянием регистра сдвига была последовательность . Дальнейшие состояния регистра приведены в таблице ниже:

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор битов. То есть генерируемая последовательность такова: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] {\displaystyle \left} (порядок бит в последовательности соответствует порядку их генерации РСЛОС). Таким образом, период последовательности равен 7, то есть максимально возможному значению, что произошло в силу примитивности заданного многочлена.

Конфигурация Галуа

Возьмём тот же характеристический многочлен, то есть c 3 = c 1 = 1 {\displaystyle c_{3}=c_{1}=1} , c 2 = 0 {\displaystyle c_{2}=0} . С выходным битом складывается только 1-й бит. Начальное состояние то же самое. Дальнейшие состояния регистра:

Внутреннее состояние регистра на седьмом шаге вернулось к исходному, следовательно, его период также равен 7. В отличие от конфигурации Фибоначчи, внутренние состояния регистра получились другие, но генерируемая последовательность та же, только сдвинута на 4 такта : [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] {\displaystyle \left} (порядок бит в последовательности соответствует порядку их генерации РСЛОС).

Генерация примитивных многочленов

Преимущества и недостатки

Преимущества

• высокое быстродействие криптографических алгоритмов, создаваемых на основе РСЛОС (например потоковых шифров);
• применение только простейших битовых операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах;
• хорошие криптографические свойства (РСЛОС могут генерировать последовательности большого периода с хорошими статистическими свойствами);
• благодаря своей структуре, РСЛОС легко анализируются с использованием алгебраических методов.

Недостатки

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

Генераторы с несколькими регистрами сдвига

Генератор такого типа состоит из нескольких регистров сдвига с линейной обратной связью, которые генерируют биты x 1 , i , x 2 , i , … , x M , i {\displaystyle x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i}} соответственно. Далее, генерируемые биты преобразуются некоторой булевой функцией f (x 1 , i , x 2 , i , … , x M , i) {\displaystyle f(x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i})} . Необходимо отметить, что у генераторов такого типа длины регистров L i {\displaystyle L_{i}} , i = 1 , 2 , … , M {\displaystyle i=1,\;2,\;\dots ,\;M} , взаимно просты между собой.

Период данного генератора равен T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L {\displaystyle T=(2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdots (2^{L_{M}}-1)\lesssim 2^{L}} , где L = ∑ i = 1 M L i {\displaystyle L=\sum \limits _{i=1}^{M}L_{i}} - общее число ячеек. Следовательно, использование нескольких РСЛОС увеличивает период генерируемой последовательности по сравнению с одним регистром, что увеличивает криптостойкость генератора. Также увеличивается линейная сложность или длина кратчайшего регистра, соответствующего данному генератору. Такой регистр находится с помощью алгоритма Берлекэмпа - Мэсси по генерируемой последовательности. В лучшем случае его длина соизмерима с периодом генерируемой последовательности .

Генераторы с нелинейными преобразованиями

Структурная схема такого генератора ничем не отличается от схемы предыдущего генератора. Главное отличие заключается в том, что устройство преобразования задано нелинейной булевой функцией f (x 1 , x 2 , … , x M) {\displaystyle f(x_{1},x_{2},\dots ,x_{M})} . В качестве такой функции берётся, например, полином Жегалкина (согласно теореме Жегалкина , всякая булева функция единственным образом может быть представлена полиномом Жегалкина).

Нелинейный генератор может быть также реализован на регистре сдвига с нелинейной обратной связью . Он может дать 2 2 L − 1 − L {\displaystyle 2^{2^{L-1}-L}} вариантов последовательностей максимального периода , что больше, чем у РСЛОС .

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

Данный метод используется, например, в генераторе Геффа и обобщённом генераторе Геффа, однако такие генераторы могут быть взломаны корреляционным вскрытием .

Генераторы с различным тактированием регистров сдвига

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

Генератор «стоп-пошёл» (англ. Stop-and-Go , Both-Piper ) использует вывод РСЛОС-1 для управления тактовой частотой РСЛОС-2, так что РСЛОС-2 меняет своё состояние в некоторый момент времени , только если выход РСЛОС-1 в момент времени был равен единице. Данная схема не устояла перед корреляционным вскрытием .

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

Усложнённая схема тактирования использована в двустороннем генераторе «стоп-пошёл» , в котором используются 2 регистра сдвига одинаковой длины. Если выход РСЛОС-1 в некоторый момент времени t i − 1 {\displaystyle t_{i-1}} - единице, то РСЛОС-2 не тактируется в момент времени t i {\displaystyle t_{i}} . Если выход РСЛОС-2 в момент времени t i − 1 {\displaystyle t_{i-1}} равен нулю, а в момент времени t i − 2 {\displaystyle t_{i-2}} - единице, и если этот регистр тактируется в момент времени t i {\displaystyle t_{i}} , то в этот же момент РСЛОС-1 не тактируется. Линейная сложность данной схемы примерно равна периоду генерируемой последовательности.

Самопрореживающий генератор

Многоскоростной генератор с внутренним произведением

Данный генератор использует два регистра сдвига РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d {\displaystyle d} раз больше, чем у РСЛОС-1. Определённые биты этих регистров перемножаются друг с другом операцией AND . Результаты умножений суммируются операцией XOR, и получается выходная последовательность. Этот генератор имеет высокую линейную сложность и обладает хорошими статистическими свойствами. Однако его состояние может быть определено по выходной последовательности длиной L 1 + L 2 + log 2 ⁡ d {\displaystyle L_{1}+L_{2}+\log _{2}{d}} , где L 1 {\displaystyle L_{1}} и L 2 {\displaystyle L_{2}} - длины РСЛОС-1 и РСЛОС-2 соответственно, а d {\displaystyle d} - отношение их тактовых частот.

Каскад Голлманна

Данная схема представляет собой улучшенную версию генератора «стоп-пошёл». Он состоит из последовательности РСЛОС, тактирование каждого из которых управляется предыдущим РСЛОС. Если выходом РСЛОС-1 в момент времени t i {\displaystyle t_{i}} является 1,то тактируется РСЛОС-2. Если выходом РСЛОС-2 в момент времени t i {\displaystyle t_{i}} является 1, то тактируется РСЛОС-3, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна L {\displaystyle L} , то период системы из M {\displaystyle M} РСЛОС равен (2 L − 1) M {\displaystyle (2^{L}-1)^{M}} , а линейная сложность - L (S) = L (2 L − 1) M − 1 {\displaystyle L(S)=L(2^{L}-1)^{M-1}} .

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