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

{{Карточка блочного шифра
|название = RC5
|изображение = RC5 InfoBox Diagram.png
|создатель = [[Ривест, Рональд Линн|Рон Ривест]]
|создан = [[1994 год]]
|опубликован = [[1994 год]]
|размер ключа = 0-2040 битов (128 по умолчанию)
|размер блока = 32, 64 или 128 битов (64 по умолчанию для 32-разрядных платформ)
|число раундов = 1-255 (12 по умолчанию)
|тип = [[Сеть Фейстеля]]
}}

'''RC5''' (''Ron’s Code 5'' или ''Rivest’s Cipher 5'') — это [[блочный шифр]], разработанный [[Ривест, Рональд Линн|Роном Ривестом]] из компании {{iw|RSA Security}} с переменным количеством [[Раунд (криптография)|раундов]], длиной блока и длиной [[Ключ (криптография)|ключа]]. Это расширяет сферу использования и упрощает переход на более сильный вариант алгоритма.

== Описание ==
Существует несколько [[RC5#Варианты алгоритма|различных вариантов алгоритма]], в которых преобразования в «пол-раундах» классического RC5 несколько изменены.
В классическом алгоритме используются три примитивных операции и их инверсии:
* [[сложение]] по модулю <math>2^w</math>
* побитовое [[исключающее ИЛИ]] ([[XOR]])
* операции [[циклический сдвиг|циклического сдвига]] на переменное число бит (<math>x \lll y</math>).
Основным нововведением является использование операции сдвига на переменное число бит, не использовавшиеся в более ранних алгоритмах шифрования. Эти операции одинаково быстро выполняются на большинстве [[процессор]]ов, но в то же время значительно усложняют [[дифференциальный криптоанализ|дифференциальный]] и [[линейный криптоанализ]] алгоритма.

Шифрование по алгоритму RC5 состоит из двух этапов. Процедура расширения ключа и непосредственно [[шифрование]]. Для расшифрования выполняется сначала процедура расширения ключа, а затем операции, обратные процедуре шифрования. Все операции сложения и [[Вычитание|вычитания]] выполняются по модулю <math>2^w</math>.

=== Параметры ===
Так как алгоритм RC5 имеет переменные параметры, то для спецификации алгоритма с конкретными параметрами принято обозначение '''RC5-W/R/b''', где
* ''W'' — половина длины блока в [[бит]]ах, возможные значения 16, 32 и 64. Для эффективной реализации величину ''W'' рекомендуют брать равным [[машинное слово|машинному слову]]. Например, для 32-битных платформ оптимальным будет выбор ''W''=32, что соответствует размеру блока 64 бита.
* ''R'' — число [[Раунд (в криптографии)|раундов]], возможные значения от 0 до 255. Увеличение числа раундов обеспечивает увеличение уровня безопасности шифра. Так, при ''R''=0 информация шифроваться не будет. Также алгоритм RC5 использует '''таблицу расширенных ключей''' размера <math>2(R+1)</math> слов, которая получается из ключа заданного пользователем.
* ''b'' — длина ключа в [[байт]]ах, возможные значения от 0 до 255.

=== Расширение ключа ===
----
Перед непосредственно шифрованием или расшифрованием данных выполняется процедура расширения ключа.
Процедура генерации ключа состоит из четырёх этапов:
* Генерация констант
* Разбиение ключа на слова
* Построение таблицы расширенных ключей
* Перемешивание

==== Генерация констант ====
Для заданного параметра <math>W</math> генерируются две псевдослучайные величины используя две математические константы: <math>e</math> ([[экспонента]]) и <math>f</math> ([[Золотое сечение]]).

: <math>Q_w \leftarrow \textrm{Odd}((f-1)\cdot 2^w)</math>
: <math>P_w \leftarrow \textrm{Odd}((e-2)\cdot 2^w)</math>,

где <math>\textrm{Odd}()</math> — это [[округление]] до ближайшего нечетного целого.

Для <math>w = 16, 32, 64</math> получатся следующие константы:

* <math>P_{16} = \texttt{1011011111100001}_2 = \texttt{B7E1}_{16}</math>
* <math>Q_{16} = \texttt{1001111000110111}_2 = \texttt{9E37}_{16}</math>
* <math>P_{32} = \texttt{10110111111000010101000101100011}_2 = \texttt{B7E15163}_{16} </math>
* <math>Q_{32} = \texttt{10011110001101110111100110111001}_2 = \texttt{9E3779B9}_{16} </math>
* <math>P_{64} = \texttt{B7E151628AED2A6B}_{16}</math>
* <math>Q_{64} = \texttt{9E3779B97F4A7C15}_{16}</math>

==== Разбиение ключа на слова ====
На этом этапе происходит копирование ключа <math>K_0 \dots  K_{b-1}</math> в массив слов <math>L_0</math>…<math>L_{c-1}</math>, где <math>c=b/u</math>, где <math>u = W/8</math>, то есть, количество байт в слове.

Если <math>b</math> не кратен <math>W/8</math>, то <math>L</math> дополняется нулевыми битами до ближайшего большего размера <math>c</math>, кратного <math>W/8</math>.

В случае если <math>b=c=0</math>, то мы устанавливаем значение <math>c=1</math>, а <math>L_0=0</math>.

==== Построение таблицы расширенных ключей ====
На этом этапе происходит построение таблицы расширенных ключей <math>S_0 \dots S_{2 * (R+1) - 1}</math>, которое выполняется следующим образом:

: <math>S_0 = P_w</math>
: <math>S_{i+1} = S_{i} + Q_w</math>

==== Перемешивание ====
Циклически N раз выполняются следующие действия:<br>
: <math>G = S_i = (S_i + G + H) \lll 3</math>
: <math>H = L_j = (L_j + G + H) \lll (G + H)</math>
: <math>i = (i + 1) \mod (2(R + 1))</math>
: <math>j = (j + 1) \mod c</math>,
причем <math>G, H, i, j</math> — временные переменные, начальные значения которых равны 0. Количество итераций цикла <math>N</math> — это максимальное из двух значений <math>3*c</math> и <math>(3 \cdot 2 \cdot (R + 1))</math>.

=== Шифрование ===
----
Перед первым раундом выполняются операции наложения расширенного ключа на шифруемые данные:

: <math>A = (A + S_0)\;\bmod\;2^w</math>
: <math>B = (B + S_1)\;\bmod\;2^w</math>

В каждом раунде выполняются следующие действия:

: <math>A = ((A \oplus B) \lll B) + S_{2i}</math>
: <math>B = ((B \oplus A) \lll A) + S_{2i+1}</math>

=== Расшифрование ===
----
Для Расшифрования данных используются обратные операции, то есть для <math>i = R, R-1,...,1</math> выполняются следующие раунды:

: <math>B = ((B - S_{2i+1}) \ggg A) \oplus A</math>
: <math>A = ((A - S_{2i}) \ggg B) \oplus B</math>

После выполнения всех раундов, исходное сообщение находится из выражения:

: <math>B = (B - S_1)\;\bmod\;2^w</math>
: <math>A = (A - S_0)\;\bmod\;2^w</math>

== Свойства ==
Алгоритм RC5 обладает следующими свойствами:<ref name="fse1994">{{cite conference|last=Rivest|first=R. L.|year=1994|title=The RC5 Encryption Algorithm|booktitle=Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e|pages=86–96|url=http://theory.lcs.mit.edu/~rivest/Rivest-rc5rev.pdf|format=pdf|9=ref-en|access-date=2009-10-27|archive-date=2007-04-17|archive-url=https://web.archive.org/web/20070417135716/http://theory.lcs.mit.edu/~rivest/Rivest-rc5rev.pdf|url-status=dead}} {{Cite web |url=http://theory.lcs.mit.edu/~rivest/Rivest-rc5rev.pdf |title=Источник |access-date=2009-10-27 |archive-date=2007-04-17 |archive-url=https://web.archive.org/web/20070417135716/http://theory.lcs.mit.edu/~rivest/Rivest-rc5rev.pdf |deadlink=yes }}</ref>

* Пригодный как для аппаратной, так и для программной реализации (алгоритм использует операции, выполняющиеся одинаково быстро на всех [[процессор]]ах).
* Каждый раунд обрабатывает весь блок целиком (типичный раунд [[Сеть Фейстеля|сети Фейстеля]] обрабатывает только «подблок»).
* Одинаково хорош для машин с разной длиной машинного слова (то есть работает также хорошо и на 64-битных машинах).
* Имеет повторяющуюся структуру с переменным числом раундов, что позволяет пользователю самому выбирать между более высокой скоростью шифрования и большей защищенностью шифра.
* Имеет переменную длину ключа, что позволяет пользователю самому выбирать уровень безопасности, соответствующий специфике его приложения.
* Достаточно простой в реализации и анализе.
* Не требователен к памяти, что позволяет использовать его даже в мобильных и переносных устройствах.

== Криптостойкость ==
RSA потратила много времени на анализ его работы с 64-битным блоком. Так в период с 1995 по 1998 г. они опубликовали ряд отчётов, в которых подробно проанализировали криптостойкость алгоритма RC5.
Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 раундов.
Дифференциальный криптоанализ требует <math>2^{24}</math> выбранных открытых текстов для алгоритма с 5 раундами, <math>2^{45}</math> для 10 раундов, <math>2^{53}</math> для 12 раундов и <math>2^{68}</math> для 15 раундов. А так как существует всего лишь <math>2^{64}</math> возможных различных открытых текстов, то дифференциальный криптоанализ невозможен для алгоритма в 15 и более раундов.
Так что рекомендуется использовать 18-20 раундов, или по крайней мере не меньше 15 вместо тех 12 раундов которые рекомендовал сам Ривест.

=== RSA Security Challenge ===
Для стимуляции изучения и применения шифра RC5 RSA Security 28 января 1997 года предложила взломать серию сообщений, зашифрованных алгоритмом RC5 с разными параметрами,<ref>[http://www.rsasecurity.com/rsalabs/node.asp?id=2100 The RSA Laboratories Secret-Key Challenge] {{webarchive|url=https://web.archive.org/web/20040523210952/http://www.rsasecurity.com/rsalabs/node.asp?id=2100 |date=2004-05-23 }}</ref> назначив за взлом каждого сообщения приз в $10 000. Шифр с самыми слабыми параметрами RC5-32/12/5 был взломан в течение нескольких часов. Тем не менее, последний осуществлённый взлом шифра RC5-32/12/8 потребовал уже 5 лет вычислений в рамках проекта [[распределённые вычисления|распределённых вычислений]] ''RC5-64'' (здесь 64=''b''·8, длина ключа в битах) под руководством [[distributed.net]]. По-прежнему неприступными пока остаются RC5-32/12/''b'' для ''b'' от 9 до 16. distributed.net запустил проект ''RC5-72'' для взлома RC5-32/12/9, в котором по состоянию на январь 2023 года удалось перебрать около 10 % ключей.<ref>{{Cite web |url=http://stats.distributed.net/projects.php?project_id=8 |title=RC5-72: Overall project statistics |access-date=2010-02-14 |archive-date=2018-10-09 |archive-url=https://web.archive.org/web/20181009090806/http://stats.distributed.net/projects.php?project_id=8 |deadlink=no }}</ref>

В мае 2007 года RSA Security Inc. объявила о прекращении поддержки соревнования и выплаты денежного вознаграждения. Чтобы не прекращать проект ''RC-72'', distributed.net решила спонсировать для него приз в $4 000 из собственных средств.<ref>[http://n0cgi.distributed.net/cgi/planarc.cgi?user=bovine&plan=2008-09-08.02:09 distributed.net: staff blogs — 2008 — September — 08<!-- Заголовок добавлен ботом -->]</ref>

=== Атака по времени выполнения ===
На платформах, где операция циклического сдвига на переменное число битов выполняется за различное число [[такт (процессор)|тактов процессора]], возможна [[атака по времени]] исполнения на алгоритм RC5. Два варианта подобной атаки были сформулированы криптоаналитиками [[Хейз, Говард|Говардом Хейзом]] и [[Хандшух, Хелен|Хеленой Хандшух]] ({{lang-en|Helena Handschuh}}). Они установили, что ключ может быть вычислен после выполнения около 220 операций шифрования с высокоточными замерами времени исполнения и затем от 228 до 240 пробных операций шифрования. Самый простой метод борьбы с подобными атаками — принудительное выполнение сдвигов за постоянное число тактов (например, за время выполнения самого медленного сдвига).

== Варианты алгоритма ==
Так как одним из свойств RC5 является его простота в реализации и анализе, вполне логично, что многие криптологи{{кто}} захотели усовершенствовать классический алгоритм. Общая структура алгоритма оставалась без изменений, менялись только [[RC5#Шифрование|действия выполняемые над каждым блоком в процессе непосредственно шифрования]]. Так появилось несколько различных вариантов этого алгоритма:

=== RC5XOR ===
В этом алгоритме сложение с ключом раунда по модулю <math>2^w</math> заменено операцией XOR:

: <math>A_{i+1} = ((A_i \oplus B_i) \lll B_i) \oplus S_{2i}</math>

: <math>B_{i+1} = ((B_i \oplus A_i) \lll A_i) \oplus S_{2i+1}</math>

Этот алгоритм оказался уязвим для дифференциального и линейного криптоанализа. Бирюкову и Кушилевицу удалось найти атаку методом дифференциального криптоанализа для алгоритма RC5XOR-32/12/16, используя 228 выбранных открытых текстов.

=== RC5P ===
В этом алгоритме сложение двух обрабатываемых «подблоков» операцией XOR заменено сложением по модулю <math>2^w</math>:

: <math>A_{i+1} = ((A_i + B_i) \lll B_i) + S_{2i}</math>

: <math>B_{i+1} = ((B_i + A_i) \lll A_i) + S_{2i+1}</math>
<!-- 
Этот алгоритм оказался уязвим для дифференциального криптоанализа.{{Нет АИ|20|02|2011}}-->

=== RC5PFR ===
В данном алгоритме циклический сдвиг осуществляется на фиксированное для данного раунда число бит, а не на переменное.

: <math>A_{i+1} = ((A_i \oplus B_i) \lll R_i) + S_{2i}</math>

: <math>B_{i+1} = ((B_i \oplus A_i) \lll R_i) + S_{2i+1}</math>,

где <math>R_i</math> фиксированное число.

Этот алгоритм не достаточно хорошо изучен, однако предполагается,{{кем}} что он неустойчив к дифференциальному криптоанализу.

=== RC5KFR ===
В этом алгоритме число бит сдвига зависит от ключа алгоритма и от текущего раунда:

: <math>A_{i+1} = ((A_i \oplus B_i) \lll R_i(L_i)) + S_{2i}</math>

: <math>B_{i+1} = ((B_i \oplus A_i) \lll R_i(L_i)) + S_{2i+1}</math>,

Этот алгоритм также не достаточно хорошо изучен.

=== RC5RA ===
В этом алгоритме число бит сдвига определяется с помощью некоторой функции от другого «подблока»:

: <math>A_{i+1} = ((A_i \oplus B_i) \lll f(L_i)) + S_{2i}</math>

: <math>B_{i+1} = ((B_i \oplus A_i) \lll f(L_i)) + S_{2i+1}</math>,

Предполагается,{{кем}} что алгоритм RC5RA ещё более стоек к известным методам криптоанализа, чем RC5.

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

== Ссылки ==
{{Викиучебник|Программные реализации RC5|Программные реализации RC5}}

* {{Книга:Шнайер Б.: Прикладная криптография}}
* {{cite web
 |url         = http://www.inode.ru/articles/admin/2006-09-07/380#2
 |title       = Часто задаваемые вопросы по симметричным шифрам
 |accessdate  = 2009-11-11
 |lang        = ru
 |description = по материалам конференции fido7.ru.crypt
 |archiveurl  = https://web.archive.org/web/20110822105602/http://www.inode.ru/articles/admin/2006-09-07/380#2
 |archivedate = 2011-08-22
 |deadlink    = yes
}}
* {{cite web
 |url         = http://www.cio-world.ru/weekly/298888/page2.html
 |title       = Современные методы вскрытия алгоритмов шифрования
 |accessdate  = 2009-12-04
 |lang        = ru
 |description = Описание некоторых методов атак на алгоритмы шифрования
 |archiveurl  = https://web.archive.org/web/20090521201247/http://www.cio-world.ru/weekly/298888/page2.html
 |archivedate = 2009-05-21
 |deadlink    = yes
}}

{{симметричные криптоалгоритмы}}

[[Категория:Шифры]]
[[Категория:Сеть Фейстеля]]