Главная | Обратная связь

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

 

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

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

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

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

Рис. 6.2. Регистр сдвига с линейной ОС

Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (РСЛОС) (рис. 6.2). Обратная связь представляет собой XOR некоторых битов регистра; эти биты называются отводной последовательностью.

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

Например, многочлен x³² + x⁷ + x⁵ + x³ + x² + x + 1 примитивен по модулю 2. Рассмотрим этот многочлен в терминах РСЛОС с максимальным периодом. Степень многочлена задает длину РСЛОС. Свободный член многочлена всегда равен 1, и его можно опустить. Степени формальной переменной многочлена, за исключением 0-й, задают отводную последовательность, отсчитываемую от левого края сдвигового регистра. То есть члены многочлена с меньшей степенью соответствуют позициям, расположенным ближе к правому краю регистра. Тогда для взятого 32-битового сдвигового регистра новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов; получающийся РСЛОС будет иметь максимальную длину, циклически проходя до повторения через 2³²−1 различных значений.

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

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

Шифр A5

А5 — это поточный шифр, используемый для шифрования GSM (Group Special Mobile), — европейского стандарта для цифровых сотовых мобильных телефонов. А5 состоит из трех PCЛОС длиной 19, 22 и 23. Выходом является XOR трех PCЛОС. В А5 используется изменяемое управление тактированием. Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два РСЛОС. Существует тривиальная атака на открытом тексте, основанная на предположении о содержании первых двух РСЛОС и попытке определения третьего РСЛОС по ключевой последовательности. Тем не менее идеи, лежащие в основе А5, позволяют проектировать надежные поточные шифры. Алгоритм эффективен и удовлетворяет всем известным статистическим тестам, единственная его слабость — короткие регистры. Варианты А5 с более длинными сдвиговыми регистрами и более плотными многочленами обратной связи позволяют противостоять силовой атаке.

Шифр RC4

RC4 — это поточный шифр с переменным размером ключа, разработанный в 1987 г. Ривестом (R. Rivest) для RSA Data Security, Inc. Алгоритм работает в режиме OFB: поток ключей не зависит от открытого текста. Используется S-блок размером 8×8: S₀, S₁, S₂, …, S₂₅₅. Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины. В алгоритме применяются два счетчика, i и j, с нулевыми начальными значениями. Для генерации случайного байта выполняются следующие вычисления:

i = (i + 1) mod 256;

j = (j + S_i) mod 256.

Поменять местами S_i и S_j.

t = (S_i + S_j) mod 256;

K = S_t.

К используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем в DES. Также несложна и инициализация S-блока. Сначала S-блок заполняется по правилу: S₀ = 0, S₁ = 1, …, S₂₅₅ = 255. После этого ключ записывается в массив: K₀, K₁, …, K₂₅₅. Затем при начальном значении j = 0 в цикле выполняются следующие вычисления:

for i = 0 to 255 do j = (j + S_i + K_i) mod 256

Поменять местами S_i и S_j.

Компания RSA Data Security, Inc. утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу и что он в высокой степени нелинеен. S-блок медленно изменяется при использовании: i и j обеспечивают случайное изменение каждого элемента. RC4 входит в десятки коммерческих продуктов, включая Lotus Notes, AOCE компании Apple Computer и Oracle Secure SQL. Этот алгоритм также является частью спецификации стандарта Сотовой цифровой пакетной передачи данных CDPD (Cellular Digital Packet Data).

Шифр SEAL

SEAL — это эффективный поточный шифр, разработанный в IBM Рогэвэем (P. Rogaway) и Копперсмитом (D. Coppersmith). Алгоритм оптимизирован для 32-битовых процессоров. Для нормальной работы ему нужно восемь 32-битовых регистров и память на несколько килобайтов. В SEAL предусмотрен ряд предварительных действий с ключом с сохранением результатов в нескольких таблицах. Таблицы используются для ускорения процедур шифрования и дешифрования. Особенностью SEAL является то, что он в действительности является не традиционным поточным шифром, а представляет собой семейство псевдослучайных функций. При 160-битовом ключе k и 32-битовом регистре n, SEAL растягивает n в L-битовую строку k(n). L может принимать любое значение, меньшее 64 Кбайт. SEAL использует следующее правило: если k выбирается случайным образом, то k(n) должно быть неотличимо от случайной L-битовой функции n.

Практический эффект того, что SEAL является семейством псевдослучайных функций, состоит в том, что он удобен в ряде приложений, где не применимы традиционные поточные шифры. При использовании большинства поточных шифров создается однонаправленная последовательность бит: единственным способом определить i-й бит (зная ключ и позицию i) является генерирование всех битов вплоть до i-го. Отличие семейства псевдослучайных функций состоит в том, что можно легко получить доступ к любой позиции ключевой последовательности. Например, для шифрования жесткого диска, состоящего из множества 512-байтовых секторов, можно воспользоваться семейством псевдослучайных функций, подобных SEAL, и выполнить XOR каждого сектора с k(n). Это то же самое, как если бы была выполнена операция XOR всего диска с длинной псевдослучайной функцией, причем любая часть этой длинной последовательности бит может быть вычислена независимо. Семейство псевдослучайных функций также упрощает проблему синхронизации, встречающуюся в стандартных поточных шифрах, — можно зашифровать на ключе k n-е передаваемое сообщение х_n, выполнив XOR х_n и k(n). Получателю не нужно хранить состояние шифра для восстановления х_n, ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс дешифрования.