Алгоритм RC4

RC4 - широко используется для обеспечения безопасности финансовых транзакций в Интернет. Патент на криптоалгоритм принадлежит RSA и является предметом коммерческой тайны. Исходники кода, идентичного RC4, были анонимно опубликованы в 1994 году. Длина ключа не ограничена. Криптостойкость - 10 баллов. Криптоатаки против этого шифра не известны.

Поток ключей в этом алгоритме не зависит от открытого текста. Используется S-блок: S(0),....,S(255).Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины. В алгоритме применяются два счётчика (i и j) с нулевыми начальными значениями. Алгоритм шифрования представлен на рисунке 6.2.2.5. Сплошные стрелки означают передачу значений между элементами схемы (присваивание), пунктирные стрелки - индексацию в массиве.

Для генерации случайного байта выполняется следующее:

i = (i+1) mod 256;

j = (i+ S(i))) mod 256;

меняем местами S(i) и S(j);

t = (S(i) + S(j)) mod 256;

K = S(t).

Байт K используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем DES.

Сначала нужно заполнить его линейно: S(0)=0;....;S(255)=255. Затем заполнить ключом другой 256-байтовый массив, при небходимости для заполнения всего массива повторяя ключ: K(0),...,K(255),j=0 (рис. 6.2.2.6).

for i=0 to 255:

j=(j+S(i)+K(i)) mod 256 ;

меняем местами S(i) и S(j).

Некоторые важные свойства алгоритма RC4:

• Преобразование очередного состояния генератора (S) обратимо, так что все возможные состояния повторяются с одинаковой частотой с некоторым периодом.
• Поскольку S содержит каждый байт ровно один раз, маловероятно, что одни байты будут выдаваться в качестве результата чаще, чем другие.

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

В начале происходит инициализация блока S (по алгоритму, представленному на рисунке 6.2.2.6):

Сначала заполняется S блок линейно: S(0)=0;....;S(255)=255.

Затем заполняется ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: K(0),...,K(255). Для примера возьмем ключ «абв», соответствующие ASCII-коды – 160,161,162.

j=0.

i = 0;

j = (0 + S(0) + K(0)) mod 256 = 160;

Меняем местами S(0) и S(160);

i = 1;

j = (1 + S(1) + K(1)) mod 256 = 163;

Меняем местами S(1) и S(163);

и т.д.

Получаем последовательность S(0) = 160, S(1) = 163, S(2) = 166 и т.д.

Затем используем полученную последовательность для инициализации блока S (в алгоритме на рисунке 6.2.2.6), который используется непосредственно для создания ключа шифрования. Далее установим счетчики i и j в 0. Затем, следуя по алгоритму, получаем:

i = (0+1) mod 256 = 1;

j = (1+S(1)) mod 256 = 164;

Меняем местами S(1) и S(164);

t = (S(1) + S(164)) mod 256 = (163 + 164) mod 256 = 71;

K = S(71).

i = (1+1) mod 256 = 2;

j = (2+S(2)) mod 256 = 168;

Меняем местами S(2) и S(168);

t = (S(2) + S(168)) mod 256 = (166 + 168) mod 256 = 78;

K = S(78).

и т.д.

Получаем последовательность байтов ключа К. Она разбивается на биты. Далее производим операцию XOR с битами текста.

Утверждается, что алгоритм устойчив к дифференциальному и линейному криптоанализу, что в нём нет никаких коротких циклов, и что он в высокой степени нелинеен. RC4 может находиться в, примерно, 21700 (256!*2562) возможных состояниях. S -блок медленно изменяется при использовании: i обеспечивает изменение каждого элемента, а j - что элементы изменяются случайным образом.