Просмотр кода страницы RC4

'''RC4''' (от {{lang-en|Rivest cipher 4}} или {{lang-en2|Ron’s code}}), также известен как '''ARC4''' или '''ARCFOUR''' ({{lang-en2|alleged RC4}}) — [[потоковый шифр]], широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах [[SSL]] и [[TLS]], алгоритмах обеспечения безопасности беспроводных сетей [[WEP]] и [[WPA]]).

Шифр разработан компанией {{iw|RSA Security}}, и для его использования требуется [[лицензия]].

Алгоритм RC4, как и любой [[потоковый шифр]], строится на основе [[Генератор псевдослучайных чисел|генератора псевдослучайных]] [[бит]]ов. На вход генератора записывается ключ, а на выходе читаются псевдослучайные биты. Длина ключа может составлять от 40 до 2048 бит<ref name="KLEIN_ATTACKS">{{статья |заглавие=Attacks on the RC4 stream cipher |издание=Designs, codes and cryptography |том=48 |номер=3 |страницы=269—286 |doi=10.1007/s10623-008-9206-6 |ссылка=http://www.networklife.net/images/wep-rc4/RC4.pdf |язык=und |автор=Klein A. |год=2008 |archivedate=2015-04-02 |archiveurl=https://web.archive.org/web/20150402200846/http://www.networklife.net/images/wep-rc4/RC4.pdf }}</ref>. Генерируемые биты имеют [[Дискретное равномерное распределение|равномерное]] [[Распределение вероятностей|распределение]].

Основные преимущества шифра:
* высокая скорость работы;
* переменный размер ключа.
RC4 довольно уязвим, если:
* используются не случайные или связанные ключи;
* один ключевой поток используется дважды.
Эти факторы, а также способ использования могут сделать [[Криптосистема|криптосистему]] небезопасной (например, [[WEP]]).

== История ==
[[Потоковый шифр]] RC4 был создан [[Ривест, Рональд Линн|Рональдом Ривестом]], сотрудником компании {{iw|RSA Security}}, в [[1987 год]]у. Сокращение «RC4» официально обозначает «Rivest cipher 4» или «шифр [[Ривест, Рональд Линн|Ривеста]]» («4» — номер версии; см. [[RC2]], [[RC5]], [[RC6]]; RC1 никогда не публиковался; RC3 разрабатывался, но в нём была найдена [[Уязвимость (компьютерная безопасность)|уязвимость]]), но его часто считают сокращением от «''Ron’s code''» («код [[Ривест, Рональд Линн|Рона]]»)<ref>{{Cite web |url=http://people.csail.mit.edu/rivest/faq.html#Ron |title=Rivest FAQ |accessdate=2009-10-15 |archiveurl=https://web.archive.org/web/20170715072137/http://people.csail.mit.edu/rivest/faq.html#Ron |archivedate=2017-07-15 |url-status=dead }}</ref>.

В течение семи лет шифр являлся [[Коммерческая тайна|коммерческой тайной]], и точное описание алгоритма предоставлялось только после подписания [[Соглашение о неразглашении|соглашения о неразглашении]], но в сентябре [[1994 год]]а его описание было анонимно отправлено в список рассылки ({{lang-en|[[:en:Mailing list|mailing list]]}}) «[[:en:Cypherpunks|Cypherpunks]]»<ref>{{cite mailing list |url=http://cypherpunks.venona.com/date/1994/09/msg00304.html |title=Thank you Bob Anderson |date=1994-09-09 |accessdate=2007-05-28 |mailing-list=[[Cypherpunks]] |archive-date=2008-04-04 |archive-url=https://web.archive.org/web/20080404222417/http://cypherpunks.venona.com/date/1994/09/msg00304.html |url-status=live }}</ref>. Вскоре описание RC4 было опубликовано в [[Группа новостей|группе новостей usenet]] «[http://groups.google.com/group/sci.crypt sci.crypt]». Оттуда исходный код попал на множество сайтов в сети [[Интернет]]. Опубликованный алгоритм на выходе выдавал [[шифротекст]]ы, совпадающие с шифротекстами, выдаваемыми подлинным RC4. Обладатели легальных копий [[исходный код|исходного кода]] RC4 подтвердили идентичность алгоритмов при различиях в обозначениях и структуре программы.

Поскольку данный [[алгоритм]] известен, он более не является [[Коммерческая тайна|коммерческой тайной]]. Однако, название «RC4» является [[Товарный знак|торговой маркой]] компании {{iw|RSA Security}}. Чтобы избежать возможных претензий со стороны владельца [[Товарный знак|торговой марки]], шифр иногда называют «ARCFOUR» или «ARC4», имея в виду {{lang-en|'''a'''lleged '''RC4'''}} — «предполагаемый» RC4 (поскольку «RSA Security» официально не опубликовала алгоритм).

Алгоритм шифрования RC4 применяется в некоторых широко распространённых стандартах и протоколах шифрования (например, [[WEP]], [[WPA]], [[SSL]] и [[TLS]]).

RC4 стал популярен благодаря:
* простоте его аппаратной и программной реализации;
* высокой скорости работы алгоритма в обоих случаях.

В [[США]] длина ключа, рекомендуемая для использования внутри страны, равна 128 битам. Соглашение, заключённое между «SPA» ({{lang-en|[[:en:Software and Information Industry Association|'''s'''oftware '''p'''ublishers '''a'''ssociation]]}}) и правительством США, разрешило экспортировать шифры RC4 с длиной ключа до 40 бит. 56-и битные ключи разрешено использовать заграничным отделениям американских компаний<ref>{{Cite web |url=http://www.rsa.com/rsalabs/node.asp?id=2249 |title=RSA Laboratories — 3.6.2 What is RC2?<!-- Заголовок добавлен ботом --> |access-date=2012-11-07 |archive-date=2012-07-29 |archive-url=https://web.archive.org/web/20120729121801/http://www.rsa.com/rsalabs/node.asp?id=2249 |url-status=dead }}</ref>.

== Описание алгоритма ==
Ядро алгоритма [[Поточный шифр|поточных шифров]] состоит из функции — [[Генератор псевдослучайных чисел|генератора псевдослучайных]] [[бит]]ов ([[Гаммирование|гаммы]]), который выдаёт поток битов ключа (ключевой поток, гамму, последовательность псевдослучайных битов).

[[Файл:Gamma12.PNG|thumbnail|250px|Режим [[гаммирование|гаммирования]] для [[поточный шифр|поточных шифров]]]]

Алгоритм шифрования.
# Функция генерирует последовательность битов (<math>k_i</math>).
# Затем последовательность битов посредством операции «[[Сложение по модулю 2|суммирование по модулю два]]» (xor) объединяется с [[открытый текст|открытым текстом]] (<math>m_i</math>). В результате получается [[шифротекст|шифрограмма]] (<math>c_i</math>):

<math>c_i = m_i \oplus k_i</math>.

Алгоритм расшифровки.
# Повторно создаётся (регенерируется) поток битов ключа (ключевой поток) (<math>k_i</math>).
# Поток битов ключа складывается с [[шифротекст|шифрограммой]] (<math>c_i</math>) операцией «[[Сложение по модулю 2|xor]]». В силу свойств операции «[[Сложение по модулю 2|xor]]» на выходе получается исходный (незашифрованный) текст (<math>m_i</math>):

<math>m_i = c_i \oplus k_i = (m_i \oplus k_i) \oplus k_i</math>

RC4 — фактически класс алгоритмов, определяемых размером блока (в дальнейшем [[S-блоки|S-блока]]). Параметр ''n'' является размером слова для алгоритма и определяет длину ''S-блока''. Обычно, ''n'' = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. В алгоритме нет противоречий на увеличение размера ''S-блока'' . При увеличении ''n'', допустим, до 16 бит, элементов в ''S-блоке'' становится {{formatnum:65 536}} и соответственно время начальной итерации будет увеличено. Однако, скорость шифрования возрастёт<ref>Bruce Schneier. Applied cryptography. Second edition. John Wiley & Sons. 1996</ref>.

Внутреннее состояние RC4 представляется в виде массива размером 2<sup>''n''</sup> и двух счётчиков. Массив известен как ''S-блок'', и далее будет обозначаться как <code>S</code>. Он всегда содержит перестановку 2<sup>''n''</sup> возможных значений слова. Два счётчика обозначены через <code>i</code> и <code>j</code>.

Инициализация RC4 состоит из двух частей:
# инициализация ''S-блока'';
# генерация псевдослучайного слова <code>K</code>.

=== Инициализация ''S-блока'' ===
Алгоритм также известен как «key-scheduling algorithm» или «KSA». Этот алгоритм использует ключ, подаваемый на вход пользователем, сохранённый в <code>Key</code>, и имеющий длину <code>L</code> байт.
Инициализация начинается с заполнения массива <code>S</code>, далее этот массив перемешивается путём перестановок, определяемых ключом. Так как только одно действие выполняется над <code>S</code>, то должно выполняться утверждение, что <code>S</code> всегда содержит один набор значений, который был дан при первоначальной инициализации (''S[i] := i'').

 '''for''' i '''from''' 0 '''to''' 255
     S[i] := i
 '''endfor'''
 j := 0
 '''for''' i '''from''' 0 '''to''' 255
     j := ( j + S[i] + Key[ i mod L ] ) mod 256 // ''n'' = 8 ; 2<sup>''8''</sup> = 256
     поменять местами S[i] и S[j]
 '''endfor'''

=== Генерация псевдослучайного слова ''K'' ===
[[Файл:RC4.svg|right|thumbnail|320px|Генератор ключевого потока RC4]]

Эта часть алгоритма называется генератором псевдослучайной последовательности ({{lang-en|'''p'''seudo-'''r'''andom '''g'''eneration '''a'''lgorithm}}, {{lang-en2|PRGA}}).
Генератор ключевого потока RC4 переставляет значения, хранящиеся в <code>S</code>. В одном цикле RC4 определяется одно ''n''-битное слово <code>K</code> из ключевого потока. В дальнейшем ключевое слово будет [[Сложение по модулю 2|сложено по модулю два]] с исходным текстом, которое пользователь хочет зашифровать, и получен зашифрованный текст.

 i := 0
 j := 0
 '''while''' Цикл генерации:
     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 (для ''n'' = 8 будет сгенерирован один байт)
 '''endwhile'''

== Безопасность ==
В отличие от современных шифров (таких, как [[eSTREAM]]), RC4 не использует [[nonce]] (от [[Английский язык|англ.]] ''nonce'' — «number that can only be used once» — число, которое может быть использовано один раз) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов — генерировать '''новый''' ключ для RC4 с помощью [[Хеширование|хеш]]-функции от долгосрочного ключа и [[nonce]]. Однако многие приложения, использующие RC4, просто конкатенируют ключ и [[nonce]]. Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым<ref>{{Cite web |url=http://www.networklife.net/images/wep-rc4/RC4.pdf |title=Источник |access-date=2010-06-18 |archive-date=2015-04-02 |archive-url=https://web.archive.org/web/20150402200846/http://www.networklife.net/images/wep-rc4/RC4.pdf |url-status=live }}</ref><ref>{{cite web |url=http://aboba.drizzlehosting.com/IEEE/rc4_ksaproc.pdf |title=Архивированная копия |accessdate=2013-10-16 |url-status=dead |archiveurl=https://web.archive.org/web/20121116051309/http://aboba.drizzlehosting.com/IEEE/rc4_ksaproc.pdf |archivedate=2012-11-16 }}</ref><ref>[https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf DSpace<!-- Заголовок добавлен ботом -->]</ref>. Поэтому он был признан устаревшим многими софтверными компаниями, такими как [[Microsoft]]. Например, в [[.NET Framework]] от [[Microsoft]] отсутствует реализация RC4.

Здесь будут рассмотрены некоторые атаки на шифр и методы защиты от них.

=== Исследования Руза и восстановление ключа из перестановки ===
В 1995 году Андрю Руз ({{lang-en|Andrew Roos}}) экспериментально пронаблюдал, что первый байт ключевого потока коррелирован с первыми тремя байтами ключа, а первые несколько байт перестановки после алгоритма расписания ключей ({{lang-en|KSA}}) коррелированы с некоторой линейной комбинацией байт ключа<ref>{{Cite web |url=https://marcel.wanda.ch/Archive/WeakKeys |title=Weak keys in RC4<!-- Заголовок добавлен ботом --> |access-date=2012-11-07 |archive-date=2012-06-18 |archive-url=https://web.archive.org/web/20120618200629/http://marcel.wanda.ch/Archive/WeakKeys |url-status=dead }}</ref>. Эти смещения не были доказаны до 2007 года, когда Пол, Рафи и Мэйтрэ доказали коррелированность ключа и ключевого потока. Также Пол и Мэйтрэ доказали коррелированность перестановки и ключа. Последняя работа также использует коррелированность ключа и перестановки для того, чтобы создать первый алгоритм полного восстановления ключа из последней перестановки после KSA, не делая предположений о ключе и векторе инициализации ({{lang-en|IV}}, {{lang-en2|'''i'''nitial '''v'''ector}}). Этот алгоритм имеет постоянную вероятность успеха в зависимости от времени, которая соответствует квадратному корню из сложности полного перебора. Позднее было сделано много работ о восстановлении ключа из внутреннего состояния RC4.

=== Атака Флурера, Мантина и Шамира (ФМШ) ===
В 2001 году Флурер, Мантин и Шамир опубликовали работу об уязвимости ключевого расписания RC4. Они показали, что первые байты ключевого потока среди всех возможных ключей неслучайны. Из этих байтов можно с высокой вероятностью получить информацию об используемом шифром ключе. И если долговременный ключ и [[nonce]] просто склеиваются для создания ключа шифра RC4, то этот долговременный ключ может быть получен с помощью анализа достаточно большого количества сообщений, зашифрованных с использованием данного ключа<ref name=autogenerated1>{{статья |заглавие=Weaknesses in the key scheduling algorithm of RC4 |издание=Lecture notes in computer science |том=2259 |страницы=1—24 |doi=10.1007/3-540-45537-X_1 |ссылка=http://www.math.psu.edu/mathnet/mdoc/md15/rc4_ksaproc-1.pdf |deadlink=yes |archiveurl=https://web.archive.org/web/20080907110836/http://www.math.psu.edu/mathnet/mdoc/md15/rc4_ksaproc-1.pdf |archivedate=2008-09-07 |accessdate=2010-06-18 |язык=und |автор=Scott R. Fluhrer, Itsik Mantin, Adi Shamir |год=2001}}</ref>. Эта уязвимость и некоторые связанные с ней эффекты были использованы при взломе шифрования [[WEP]] в беспроводных сетях стандарта [[IEEE 802.11]]. Это показало необходимость скорейшей замены [[WEP]], что повлекло за собой разработку нового стандарта безопасности беспроводных сетей [[WPA]].

Криптосистему можно сделать невосприимчивой к этой атаке, если отбрасывать начало ключевого потока. Таким образом, модифицированный алгоритм называется «RC4-drop[n]», где <code>n</code> — количество байтов из начала ключевого потока, которые следует отбросить. Рекомендовано использовать <code>n = 768</code>, консервативная оценка составляет <code>n = 3072</code><ref>{{статья |заглавие=(Not so) random shuffles of RC4 |издание=Lecture Notes in Computer Science |том=2442 |страницы=304—319 |doi=10.1007/3-540-45708-9_20 |ссылка=http://eprint.iacr.org/2002/067.pdf |язык=und |автор=I. Mironov |год=2002 |archivedate=2010-01-19 |archiveurl=https://web.archive.org/web/20100119163158/http://eprint.iacr.org/2002/067.pdf }}</ref><ref>[http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop «RC4-drop(nbytes)»] {{Wayback|url=http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop |date=20120125020242 }}. «''Standard cryptographic algorithm naming''» database.</ref>.

Атака базируется на слабости {{iw|Вектор инициализации|инициализационного вектора|en|Initialization vector}}. Зная первое псевдослучайное слово <code>K</code> и <code>m</code> байтов входного ключа <code>Key</code>, используя слабость в алгоритме генерации псевдо-случайного слова <code>K</code> , можно получить <code>m + 1</code> байт входного ключа. Повторяя шаги добывается полный ключ.
При атаке на [[WEP]], для <code>n = 8</code> <code>IV</code> имеет вид (B; 255; N), где <code>B</code> — от 3 до 8, а <code>N</code> любое число . Для определения около 60 вариантов ''N'' потребуется перехватить примерно 4 миллиона пакетов.<ref name=autogenerated1 />

=== Атака Кляйна ===
В 2005 году [[Андреас Кляйн]] представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа и ключевого потока RC4. Кляйн проанализировал атаки на первом раунде (подобные атаке ФМШ), на втором раунде и возможные их улучшения. Он также предложил некоторые изменения алгоритма для усиления стойкости шифра. В частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким к атакам типа ФМШ<ref name="KLEIN_ATTACKS"/>.

=== Комбинаторная проблема ===
В 2001 году [[Ади Шамир]] и Ицхак Мантин первыми поставили комбинаторную проблему, связанную с количеством всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно <code>x</code> элементов из состояния (<code>x ≤ 256</code>), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов, также равно <code>x</code>. В 2004 году это предположение было доказано Сорадюти Полом ({{lang-en|Souradyuti Paul}}) и [[Пренель, Барт|Бартом Пренелем]] ({{lang-en|Bart Preneel}})<ref>{{статья |заглавие=A New Weakness in the RC4 Keystream generator and an approach to improve the security of the cipher |издание=Lecture notes in computer science |том=3017 |страницы=245—259 |doi=10.1007/b98177 |ссылка=http://www.cosic.esat.kuleuven.be/publications/article-40.pdf |язык=en |тип=journal |автор=Souradyuti Paul, Bart Preneel |год=2004 |archivedate=2009-03-06 |archiveurl=https://web.archive.org/web/20090306062950/http://www.cosic.esat.kuleuven.be/publications/article-40.pdf }}</ref>.

=== Атака NOMORE (2015) ===
Летом 2015 года Мэти Ванхоф (Mathy Vanhoef) и Франк Писсенс (Frank Piessens) из университета Левена в Бельгии продемонстрировали реальную атаку на протоколы [[TLS]] и [[TKIP]], использующие RC4 для шифрования передаваемых данных, получившую название «Numerous Occurrence MOnitoring & Recovery Exploit» (NOMORE)<ref>{{Cite web |url=http://www.rc4nomore.com/ |title=RC4 NOMORE |access-date=2016-04-17 |archive-date=2020-08-18 |archive-url=https://web.archive.org/web/20200818190323/http://www.rc4nomore.com/ |url-status=live }}</ref>. Идея взлома базируется на принципе [[Атака посредника|MITM]]. Встроившись в канал передачи данных, атакующая сторона генерирует серверу большое количество запросов, вынуждая его в ответ возвращать [[Magic cookie|куки]], зашифрованные одним и тем же ключом. Имея в распоряжении около 9x2<sup>27</sup> ~ 2<sup>30</sup> пар {открытый текст, шифротекст}, злоумышленник получает возможность на основе статистических методов [[Флюрер-Макгрю]] и [[ABSAB]] с вероятностью 94 % восстановить ключ и, следовательно, зашифрованные куки. Практические временные затраты составили около 52 часов, верхняя же оценка потребного времени на момент демонстрации составила около 72 часов<ref>{{Cite web |url=https://xakep.ru/2015/07/16/rc4-nomore/ |title=Хакеры показали практичный метод взлома RC4 |access-date=2016-04-17 |archive-date=2016-04-25 |archive-url=https://web.archive.org/web/20160425114828/https://xakep.ru/2015/07/16/rc4-nomore/ |url-status=live }}</ref>.

== Модификации RC4 ==
Ранее рассматривались атаки, основанные на коррелируемости первых байт шифрованного текста и ключа. Подобные слабости алгоритма могут быть решены отбрасыванием начальной части шифрованного текста<ref>{{Citation |chapter-url=http://eprint.iacr.org/2002/067 |chapter=(Not So) Random shuffles of RC4 |author=Ilya Mironov |date=2002-06-01 |title=Advances in cryptology – CRYPTO 2002 |pages=304–319 |series=Lecture notes in computer science |volume=2442 |publisher=Springer-Verlag |isbn=3-540-44050-X |doi=10.1007/3-540-45708-9_20 |id=Cryptology ePrint archive: Report 2002/067 |accessdate=2011-11-04 |archive-date=2011-09-06 |archive-url=https://web.archive.org/web/20110906055527/http://eprint.iacr.org/2002/067 |url-status=live }}</ref>. Надёжным считается отбрасывание первых 256, 512, 768 и 1024 байт. Исследования начала шифротекста были проведены для показания ненадёжности определённого числа первых байтов, что может привести к получению злоумышленником ключа шифрования.
Были предложены несколько модификаций RC4 выполняющие поставленную задачу усиления безопасности при использовании алгоритма: RC4A, [[VMPC]], RC4+.

=== RC4A ===
В 2004 году свет увидела работа Souradyuti Paul и Bart Preneel, в которой предлагалась модификация RC4A<ref>{{Citation |chapter=A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher |author1=Souradyuti Paul |authorlink1=Souradyuti Paul |author2=Bart Preneel |authorlink2=Bart Preneel |chapter-url=http://homes.esat.kuleuven.be/~psourady/publication-info/PP04-bias_rc4.htm |year=2004 |title=Fast Software Encryption, FSE 2004 |series=Lecture Notes in Computer Science |volume=3017 |publisher=Springer-Verlag |isbn=3-540-22171-9 |pages=245–259 |doi=10.1007/978-3-540-25937-4_16 |accessdate=2011-11-04 |url-status=dead |archiveurl=https://web.archive.org/web/20110611144259/http://homes.esat.kuleuven.be/~psourady/publication-info/PP04-bias_rc4.htm |archivedate=2011-06-11 }}</ref>.

Для RC4A используется два ''S-блока'' вместо одного, как в RC4, обозначим <code>S₁</code> и <code>S₂</code>. Для них соответствующе используются два счётчика <code>j₁</code>, <code>j₂</code>. Счётчик <code>i</code>, как и для RC4, используется в единственном числе для всего алгоритма.
Принцип выполнения алгоритма остается прежним, но имеется ряд отличий:
# <code>S₁</code> является параметром для <code>S₂</code>.
# За одну итерацию, то есть за одно увеличение индекса <code>i</code>, генерируется два байта шифротекста.

Алгоритм :
 i := 0
 j₁ := 0
 j₂ := 0
 '''while''' Цикл генерации:
     i := i + 1
     j₁ := ( j₁ + S₁[i] ) mod 256
     поменять местами S₁[i] и S₁[j₁]
     I₂ := ( S₁[i] + S₁[j₁] ) mod 256
     '''output''' := S₂[I₂]
     j₂ = ( j₂ + S₂[i] ) mod 256
     поменять местами S₂[i] и S₂[j₂]
     I₁ = ( S₂[i] + S₂[j₂] ) mod 256
     '''output''' := S₁[I₁]
 '''endwhile'''

Скорость шифрования данного алгоритма может быть увеличена за счёт [[Распараллеливание программ|распараллеливания]].

=== RC4+ ===
В 2008 году была разработана и предложена модификация RC4+. Авторы Subhamoy Maitra и Goutam Paul модифицировали инициализацию ''S-блока''(KSA+), использовав 3-уровневое скремблирование. Также модификации был подвергнут алгоритм генерации псевдослучайного слова (PRGA+)<ref name="rc4+">{{Citation |chapter=Analysis of RC4 and Proposal of Additional Layers for Better Security Margin |chapter-url=http://eprint.iacr.org/2008/396 |author1=Subhamoy Maitra |author2=Goutam Paul |date=2008-09-19 |title=Progress in Cryptology – INDOCRYPT 2008 |pages=27–39 |series=Lecture Notes in Computer science |volume=5365 |publisher=Springer-Verlag |isbn=3-540-89753-4 |doi=10.1007/978-3-540-89754-5_3 |id=Cryptology ePrint Archive: Report 2008/396 |accessdate=2011-11-04 |archive-date=2012-01-30 |archive-url=https://web.archive.org/web/20120130063511/http://eprint.iacr.org/2008/396 |url-status=live }}</ref>.

Алгоритм:
  <span style="color: green;">''Все арифметические операции выполняются по mod 256. Символами «<<» и «>>» обозначены [[битовый сдвиг|битовые сдвиги]] влево и вправо соответственно. Символ «⊕» обозначает операцию «[[Сложение по модулю 2|исключающее ИЛИ]]»''</span>
 '''while''' Цикл генерации:
     i := i + 1
     a := S[i]
     j := j + a
     b := S[j]
     S[i] := b     <span style="color: green;">''(поменяли местами S[i] и S[j])''</span>
     S[j] := a
     c := S[ i<<5 ⊕ j>>3 ] + S[ j<<5 ⊕ i>>3 ]
     '''output''' ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ]
 '''endwhile'''

== Реализация ==
{{Викиучебник|Программные реализации RC4|Программные реализации RC4}}

Работа многих [[Поточный шифр|поточных шифров]] основана на [[Линейный регистр сдвига с обратной связью|линейных регистрах сдвига с обратной связью]] ({{lang-en|LFSR}}). Это позволяет достичь высокой эффективности реализаций шифра в виде [[Интегральная схема|интегральной схемы]] (аппаратная реализация), но затрудняет программную реализацию таких шифров. Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый [[байт]] текста, поэтому программная реализация шифра должна работать быстро<ref>{{Cite web |url=http://www.rsa.com/rsalabs/node.asp?id=2250 |title=RSA Laboratories — 3.6.3 What is RC4? |access-date=2009-10-18 |archive-date=2009-02-26 |archive-url=https://web.archive.org/web/20090226081300/http://www.rsa.com/rsalabs/node.asp?id=2250 |url-status=dead }}</ref>.

== Криптосистемы и протоколы, использующие RC4 ==
* [[Wired Equivalent Privacy|WEP]];
* {{iw|BitTorrent protocol encryption}};
* [[MPPE]];
* [[браузер]] [[Opera Mini]]<ref>[http://www.opera.com/mobile/help/faq/#security Ответы] {{Wayback|url=http://www.opera.com/mobile/help/faq/#security |date=20100324165317 }} на вопровы пользователей браузера [[Opera mini]].</ref>;
* протокол [[Secure Sockets Layer|SSL]] (вариативно);
* протокол [[Secure shell|SSH]] (вариативно);
* протокол [[Remote Desktop Protocol|RDP]];
* [[Kerberos]]<ref>RFC 4757. The RC4-[[HMAC]] kerberos encryption types used by [[Microsoft]] [[Windows]].</ref> (вариативно);
* [[Simple Authentication and Security Layer|SASL]] mechanism digest-[[MD5]] (вариативно);
* формат [[Portable Document Format|PDF]]<ref>[http://www.pdf-tools.com/public/downloads/pdf-reference/pdfreference12.pdf PDF &amp; PDF/A software | PDF Tools AG | Premium PDF technology<!-- Заголовок добавлен ботом -->] {{webarchive|url=https://web.archive.org/web/20051103044315/http://www.pdf-tools.com/public/downloads/pdf-reference/pdfreference12.pdf |date=2005-11-03 }}</ref>
* [[Skype]] (вариативно)<ref>{{cite web
 |url         = http://www.h-online.com/security/news/item/Skype-s-encryption-procedure-partly-exposed-1034577.html
|title       = Skype's encryption procedure partly exposed
|publisher   = www.h-online.com
|accessdate  = 2010-07-08
|archiveurl  = https://www.webcitation.org/6Bz0wfS8x?url=http://www.h-online.com/security/news/item/Skype-s-encryption-procedure-partly-exposed-1034577.html
|archivedate = 2012-11-06
}}</ref>.

Слово «(вариативно)» означает, что RC4 является одним из нескольких алгоритмов шифрования, которые могут использоваться системой.

== См. также ==
* [[VMPC]]
* {{iw|CipherSaber}}

== Примечания ==
{{примечания|2}}

== Ссылки ==
* [https://web.archive.org/web/20041210203911/http://www.rsasecurity.com/rsalabs/node.asp?id=2009 RSA security response to weaknesses in key scheduling algorithm of RC4].
* [http://cypherpunks.venona.com/archive/1994/09/msg00304.html Письмо], содержащее описание алгоритма RC4, в списке рассылки «[[:en:Cypherpunks|Cypherpunks]]».
* Klein A. «[https://web.archive.org/web/20090513171944/http://cage.ugent.be/~klein/RC4/RC4-en.ps Attacks on the RC4 stream cipher]». 27 февраля 2006 года (формат [[PostScript]]).
 
{{Симметричные криптосистемы}}

[[Категория:Потоковые шифры]]