Алгоритм RC4

Текст взят из книги Брюса Шнайера "Прикладная криптография", 2-е издание

RC4 – это потоковый шифр с переменным размером ключа, разработанный в 1987 году Роном Ривестом для RSA Data Security, Inc. В течении семи лет он являлся собственностью компании, и подробное описание алгоритма предоставлялось только после подписания соглашения о неразглашении.

В сентябре 1994 года кто-то анонимно опубликовал исходный код в списке рассылки шифропанков. Он быстро распространился в телеконференции Usenet sci.crypt, и через Интернет – по различным ftp-серверам во всем мире. Обладатели легальных копий RC4 подтвердили совместимость этого кода. Корпорация RSA Data Security попыталась загнать джинна в бутылку, утверждая, что, несмотря на публикацию, алгоритм остается производственным секретом. Но было слишком поздно. С тех пор алгоритм обсуждался и изучался в Usenet, распространялся на конференциях и служил учебным пособием на курсах криптографии.

Описать RC4 несложно. Алгоритм работает в режиме OFB, т.е. гамма не зависит от открытого текста. Используется S-блок размером 8*8: $S_0, S_1, ... S_{255}$. Элементы представляют собой перестановку чисел от 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$


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

Так же несложна и инициализация S-блока. Сначала заполним его линейно: $S_0=0, S_1= 1, ... S_{255}= 255$. Затем заполним ключом другой 256-байтовый массив. Если необходимо, повторяем ключ, чтобы заполнить весь массив: $K_0, K_1, ... K_{255}$. Установим значение индекса j равным 0. Затем:


Для i от 0 до 255
$\quad \quad j = (j + S_i + K_i)\;mod\;256$
$\quad \quad$Поменяйте местами $S_i$ и $S_j$.


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

Эту идею можно обобщить на S-блоки и слова больших размеров. Выше была описана 8-битовая версия RC4. Нет причин, по которым нельзя бы было определить 16-битовый алгоритм RC4 с S-блоком размером 16*16 (100Кбайт памяти) и 16-битовым словом. Начальная установка займет намного больше времени – для сохранения приведенной схемы нужно заполнить 65536-элементный массив – но получившийся алгоритм должен работать быстрее.

Имя алгоритма – торговая марка, поэтому каждый, кто напишет собственный код, должен назвать его как-то иначе. Различные внутренние документы RSA Data Security до сих пор не опубликованы [1],[2].

Итак, какова же ситуация вокруг алгоритма RC4? Он уже не относится к производственным секретам, поэтому кто угодно имеет право воспользоваться им. Однако RSA Data Security почти наверняка возбудит дело против каждого, кто применит нелицензированный RC4 в коммерческом продукте. Возможно, им и не удастся выиграть процесс, но все же намного дешевле купить лицензию, чем судиться.

Смотрите Python-реализацию алгоритма.

Библиография
1. R.L. Rivest, "The RC4 Encryption Algorithm", RSA Data Security, Inc., Mar 1992
2. M.J.B. Robshaw, "Security of RC4", Technical Report TR-401, RSA Laboratories, Jul 1994
Криптографические примитивы
Алгоритмы с открытым ключом RSA DSA
Поточные шифры RC4
Хэш-функции RIPEMD-160 SHA-1/2
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License