ARC4 – это потоковый шифр, похожий на RC4, разработанный компанией RSA Security, и совпадающий с ним на всем известном множестве тестов. Подобные шифры широко применяются в различных системах защиты информации в компьютерных сетях (например, в протоколах SSL и TLS, алгоритме безопасности беспроводных сетей WEP, для шифрования паролей в Windows NT).

Алгоритм ARC4 строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа может составляет 128 бит.

Основное преимущество шифра – высокая скорость работы.

Описание алгоритма
Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция генерирует последовательность битов (k_i), которая затем объединяется с открытым текстом (m_i) посредством операции XOR (суммирования по модулю два). Так получается шифрограмма (c_i):

c_i = m_i xor k_i

Расшифровка заключается в регенерации этого ключевого потока (k_i) и сложении его и шифрограммы (c_i) по модулю два. В силу свойств суммирования по модулю два на выходе получается исходный незашифрованный текст (m_i):

m_i = c_i xor k_i = (m_i xor k_i) xor k_i

Другая главная часть алгоритма – функция инициализации, которая использует ключ для создания начального состояния генератора ключевого потока. Внутреннее состояние ARC4 представляется в виде массива байтов размером 2⁸ = 256 и двух счётчиков, каждый размером в один байт. Массив называется S-бокс, и далее будет обозначаться как SB. Он всегда содержит перестановку 256 возможных значений байта. Два счётчика обозначены как x и y.

Алгоритм инициализации ARC4 приведен ниже. Он использует ключ, сохранённый в Key, и имеющий длину 128 бит (16 байт). Инициализация начинается с заполнения массива SB последовательными значениями от 0 до 255. Далее идёт скребмлирование массива путём перестановок определяемых ключом.

  // Начальное заполнение массива
 for i = 0 to 255
  S [i] = i

  // Скремблирование
 j = 0

 for i = 0 to 255
  begin
   j = (j + S [i] + Key [i mod L]) mod 2^8 
   Перестановка(S [i], S [j])
  end

Генератор ключевого потока ARC4 переставляет значения, хранящиеся в SB, и каждый раз выбирает различное значение из SB в качестве результата. В одном цикле ARC4 определяется одно 8-битное слово K из ключевого потока, которое в последующем суммируется по модулю два с исходным текстом для получения зашифрованного текста:

  // Инициализация
 x = 0
 y = 0

 // Цикл генерации ключевого потока
 x = (x + 1) mod 256
 y = (y + S [x]) mod 256
 Перестановка(S [x], S [y])
 Результат: K = S [(S [x] + S [y]) mod 256]

Графически процесс генерации ключевого потока показан ниже: