Поточный шифр гаммирования RC4

Выбор схемы шифратора как правило ориентирован на элементную базу, на которой предполагается осуществить ее реализацию. В качестве примера современного шифра гаммирования, ориентированного на программную реализацию приведем Алгоритм RC-4 (разработка RSА Security Incorporated). Данный шифр применен, в частности для защиты в распределенной базе данных Lotus Notus и в некоторых других программных продуктах.

Описание функционирования поточного шифра RC4 дается по работе Йована Голича [ГОЛ. J. D. Golić, «Linear Statistical Weakness of Alleged RC4 Keystream generator», in Lecture Notes in Computer Science 1233; Advances in Cryptology:: Proc. Eurocrypt '97, W. Fumy, Ed., May 1997, pp. 226-238, Berlin: Springer-Verlag, 1997]. Фактически, RC4 представляет собой семейство алгоритмов, задаваемых параметром n, который является положительным целым с рекомендованным типичным значением n = 8. Внутреннее состояние генератора RC4 в момент времени t состоит из таблицы , содержащей 2 ⁿ n -битных слов и из двух n -битных слов-указателей i_t и j_t. Таким образом, размер внутренней памяти составляет M = n 2 ⁿ + 2 n бит. Пусть выходное n -битное слово генератора в момент t обозначается как Z_t. Пусть начальные значения i ₀ = j ₀ = 0. Тогда функция следующего состояния и функция выхода RC4 для каждого t ³ 1 задается следующими соотношениями:

i_t = i_{t – 1} + 1

j_t = j_{t – 1} + S _{t – 1}(i_t)

S _t (i_t) = S _{t – 1}(j_t), S _t (j_t) = S _{t – 1}(i_t)

Z _t = S _t (S _t (i_t) + S _t (j_t)),

где все сложения выполняются по модулю 2 ⁿ. Подразумевается, что все слова, кроме подвергаемых изменению по формулам, остаются теми же самыми. Выходная последовательность n -битных слов обозначается как .

Начальная таблица S ₀ задается в терминах ключевой последовательности с использованием той же самой функции следующего состояния, начиная от таблицы единичной подстановки . Более строго, пусть j ₀ = 0 и для каждого 1£ t £ 2 ⁿ вычисляется j_t = (j_{t – 1} + S _{t – 1}(t – 1) + K _{t – 1}) mod 2 ⁿ, а затем переставляются местами S _{t – 1}(t – 1) и S _{t – 1}(j_t). На последнем шаге порождается таблица, представляющая S ₀. Ключевая последовательность K составляется из секретного ключа, возможно повторяющегося, и рандомизирующего ключа, передаваемого в открытом виде в целях ресинхронизации. Шифрованный текст получается сложением по модулю 2 двоичных векторов О_t длины n (байтов при n=8) открытого текста с двоичными векторами Z_t длины n.

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

Глава 4.