Поточные шифры, основанные на регистрах сдвига с обратной связью

Большинство реальных поточных шифров основано на регистрах сдвига с обратной связью (рис. 4.9). Регистр сдвига применяют для генерации ключевой последовательности.

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

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

Периодом регистра называется длина получаемой последователь­ности до начала ее повторения.

Простейшим видом регистра сдвига с обратной связью является регистр сдви­га с линейной обратной связью (РСЛОС), (рис 4.10.)

Обратная связь представляет со­бой Å некоторых (не всех) битов регис­тра; эти биты называются отвод­ной последовательностью. Задать последовательность бит, входящих в обратную связь, мож­но с помощью коэффициентов, равных 0 или 1 для каждого бита.

Рассмотрим пример 4-битового РСЛОС с отводом от первого и чет­вертого битов (рис. 4.11). Если его проинициализировать значе­нием 1111, то до повторе­ния регистр будет прини­мать следующие внутренние состояния:

1111 0111 1011 0101 1010 1101 0110 0011 1001 0100 0010 0001 1000 1100 1110.

Выходной последовательностью будет строка младших значащих битов:

1111 0101 1001 000...

РСЛОС (n -битовый) может находиться в одном из 2 ⁿ -1 внутренних состояний (значений битов). Это означает, что теоретически такой регистр может генерировать псевдо­случайную последовательность с периодом 2 ⁿ -1 битов.

Число внутренних состояний и период равны 2 ⁿ -1, потому что за­полнение РСЛОС нулями приведет к тому, что сдвиговый регистр бу­дет выдавать бесконеч­ную последовательность нулей, что абсо­лют­но бесполезно. Только при опреде­ленных отводных последовательностях РСЛОС циклически пройдет через все внутренние состояния. Такие РСЛОС имеют максимальный период. Получивший­ся результат называется М- последовательностью.

Формально n -битовый РСЛОС можно описать многочленом степени n от фор­мальной переменной х, где i -му биту соответствует член х ⁱ с коэффициентом 0, если бит входит вотводную последовательность, или с коэффициентом 1, если не входит. Свобод­ный член многочлена всегда равен 1. В нашем примере это будет

х ⁴+х+ 1.

Степени формальной переменной многочлена, за исключением 0-й, задают от­водную последовательность, отсчитываемую от левого края сдвигового регистра. То есть члены многочлена с меньшей степенью соответствуют позициям, распо­ложенным ближе к правому краю регистра. Нулевой бит, которому в многочлене соответствует х⁰ =1, всегда входит в отводную последовательность. Это гаранти­рует, что все биты регистра не станут нулевыми одновременно.

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

Например, многочлен х ³² + х ⁷ + х ⁵ + х ³ + х² + х + 1примитивен по модулю 2. Рассмотрим этот многочлен в терминах РСЛОС с максима­льным периодом. Степень многочлена задает длину РСЛОС.

Тогда для взятого 32-битового сдвигового регистра новый бит гене­рируется с помощью Å тридцать второго, седьмого, пятого, третьего, второго и первого битов (рис. 4.12); получающийся РСЛОС будет иметь максимальную длину, циклически проходя до повторения через 2³²-1 различных значений.

Рисунок 4.12. 32-битовый РСЛОС с максимальным периодом

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

Кроме того, большие случайные числа, генерируемые с использова­ни­ем иду­щих подряд бит этой последовательно­сти, сильно коррелиро­ваны и для некото­рых типов приложений вовсе не являются случай­ными. Несмотря на это, РСЛОС часто используются при разработке алгоритмов шифрования. Примером является шифр А5.

Алгоритм А5

А5 — это поточный шифр, используемый для шифрования GSM (Grouр Sрecial Mobile) – европейского стандарта для цифровых сото­вых мобильных телефонов, а именно, канала «телефон - базовая станция».

А5 состоит из трех РСЛОС длиной 19, 22 и 23. Выходом является Å трех РСЛОС. В А5 используется изменяемое управление тактировани­ем (сдвигом на каждом шаге). Каждый регистр тактируется в зависи­мости от своего среднего бита, затем выполняется Å с обратной поро­говой функцией средних битов всех трех регистров. Обычно на каж­дом этапе тактируется два РСЛОС.

Существует тривиальная атака на открытом тексте, основанная на предполо­жении о содержании первых двух РСЛОС и попытке опреде­ления третьего РСЛОС по ключевой последовательности. Тем не менее идеи, лежащие в основе А5, позволяют проектировать надежные поточные шифры. Алгоритм эффективен и удовлетворяет всем извес­тным статистическим тестам, единственная его слабость — короткие регистры. Варианты А5 с более длинными сдвиговыми регистрами и более плотными многочленами обратной связи позволяют противостоять силовой атаке.

Алгоритм А5/1 - одна из двух разновидностей алгоритма А5.

Рисунок 4.13. Криптосхема генератора шифра A5/1

Генератор А5/1 состоит из трех ЛРС над GF(2) длины 19, 22 и 23 (рис. 4.13) с характеристическими многочленами соответственно

x ¹⁹ + х ⁵ + х² + х + 1                                                       х²² + х + 1      x ²² + х ¹⁵ + х² + х + 1.

Сумма битов, снимаемых с трех ЛРС, образует гамму генератора. Нелинейность алгоритма достигается за счет неравномерного движения всех ЛРС, контролируемого блоком управления движени­ем (БУД).

После вычисления знака гаммы происходит сдвиг некото­рых (не менее чем двух) регис­тров. Сдвиг зависит от значения трех битов: 10-го бита ЛРС-1, 11-го бита ЛРС-2 и 12-го бита ЛРС-3 - и определяется по правилу: если все три бита одинаковы, то сдвигают­ся все регистры, в противном случае сдвигаются два регистра, чьи управляющие биты совпадают.

Открытый текст представляет собой набор 114-битовых блоков. Перед шифрованием каждого блока происходит перезагрузка состояний регистров, которая определяется однозначно передаваемым в линию несекретным номером блока и секретным 64-битовым сеан­совым ключом шифра. Определение сеансового ключа шифра равно­сильно определению состояния регистров после перезагрузки, так как сеансовый ключ восстанавливается однозначно по состоянию ре­гистров и по номеру блока из решения линейной системы уравнений от 64 переменных над полем Галуа GF(2), которое будет рассмотрено далее.

После перезагрузки регистров осуществляется 100 тактов холо­стого прогона, то есть 100 первых знаков гаммы игнорируются. В последующие 114 тактов вырабатываемые генератором биты ис­пользуются для гаммиро­вания блока открытого текста.