7.1. Шифр RC4

Шифр RC4 был разработан Роном Ривестом (англ. Ronald Linn Rivest) в 1987 году для компании RSA Data Security. Описание алгоритма было впервые анонимно опубликовано в телеконференции Usenet sci.crypt в 1994 году

.

Генератор, используемый в шифре, хранит своё состояние в массиве из 256 ячеек $S_0, S_1, \dots, S_{255}$, заполненных значениями от 0 до 255 (каждое значение встречается только один раз), а также двух других переменных размером в 1 байт $i$ и $j$. Таким образом, количество различных внутренних состояний генератора равно $255! \times 255 \times 255 \approx 2.17 \times 10^{509} \approx 2^{1962}$.

Процедура инициализации генератора.

• Для заполнения байтового массива из 256 ячеек $K_0, K_1, \dots, K_{255}$ используется предоставленный ключ. При необходимости (если размер ключа менее 256 байтов) ключ используется несколько раз, пока массив $K$ не будет заполнен целиком.
• Начальное значение $j$ равно $0$.
• Далее для значений $i$ от $0$ до $255$ выполняется:
  1. $j:= (j + S_i + K_i) \mod 256$,
  2. поменять местами $S_i$ и $S_j$.

Процедура получения следующего псевдослучайного байта $result$ (следующего байта гаммы):

1. $ i := (i + 1) \mod 256$,
2. $ j := (j + S_i) \mod 256$,
3. поменять местами $S_i$ и $S_j$,
4. $ t := ( S_i + S_j ) \mod 256$,
5. $ result := S_t$.

По утверждению Брюса Шнайера, алгоритм настолько прост, что большинство программистов могут закодировать его по памяти. Шифр RC4 использовался во многих программных продуктах, в том числе в IBM Lotus Notes, Apple AOCE, Oracle Secure SQL и Microsoft Office, а также в стандарте сотовой передачи цифровых данных CDPD. В настоящий момент шифр не рекомендуется к использованию [85], в нём были найдены многочисленные, хотя и некритичные уязвимости [40, 65, 83, 92].