RC5

RC5
Создатель	Рон Ривест
Создан	1994 год
Опубликован	1994 год
Размер ключа	0-2040 битов (128 по умолчанию)
Размер блока	32, 64 или 128 битов (64 по умолчанию для 32-разрядных платформ)
Число раундов	1-255 (12 по умолчанию)
Тип	Сеть Фейстеля

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

Описание

Существует несколькоразличных вариантов алгоритма,в которых преобразования в «пол-раундах» классического RC5 несколько изменены. В классическом алгоритме используются три примитивных операции и их инверсии:

• сложениепо модулю$2^{w}$
• побитовоеисключающее ИЛИ(XOR)
• операциициклического сдвигана переменное число бит ($x\lll y$).

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

Шифрование по алгоритму RC5 состоит из двух этапов. Процедура расширения ключа и непосредственношифрование.Для расшифрования выполняется сначала процедура расширения ключа, а затем операции, обратные процедуре шифрования. Все операции сложения ивычитаниявыполняются по модулю$2^{w}$.

Параметры

Так как алгоритм RC5 имеет переменные параметры, то для спецификации алгоритма с конкретными параметрами принято обозначениеRC5-W/R/b,где

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

Расширение ключа

---

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

• Генерация констант
• Разбиение ключа на слова
• Построение таблицы расширенных ключей
• Перемешивание

Генерация констант

Для заданного параметра$W$генерируются две псевдослучайные величины используя две математические константы:$e$(экспонента) и$f$(Золотое сечение).

$Q_{w}\leftarrow {\textrm {Odd}}((f-1)\cdot 2^{w})$

$P_{w}\leftarrow {\textrm {Odd}}((e-2)\cdot 2^{w})$,

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

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

• $P_{16}={\texttt {1011011111100001}}_{2}={\texttt {B7E1}}_{16}$
• $Q_{16}={\texttt {1001111000110111}}_{2}={\texttt {9E37}}_{16}$
• $P_{32}={\texttt {10110111111000010101000101100011}}_{2}={\texttt {B7E15163}}_{16}$
• $Q_{32}={\texttt {10011110001101110111100110111001}}_{2}={\texttt {9E3779B9}}_{16}$
• $P_{64}={\texttt {B7E151628AED2A6B}}_{16}$
• $Q_{64}={\texttt {9E3779B97F4A7C15}}_{16}$

Разбиение ключа на слова

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

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

В случае если$b=c=0$,то мы устанавливаем значение$c=1$,а$L_{0}=0$.

Построение таблицы расширенных ключей

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

$S_{0}=P_{w}$

$S_{i+1}=S_{i}+Q_{w}$

Перемешивание

Циклически N раз выполняются следующие действия:

$G=S_{i}=(S_{i}+G+H)\lll 3$

$H=L_{j}=(L_{j}+G+H)\lll (G+H)$

$i=(i+1)\mod (2(R+1))$

$j=(j+1)\mod c$,

причем$G,H,i,j$— временные переменные, начальные значения которых равны 0. Количество итераций цикла$N$— это максимальное из двух значений$3*c$и$(3\cdot 2\cdot (R+1))$.

Шифрование

---

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

$A=(A+S_{0})\;{\bmod {\;}}2^{w}$

$B=(B+S_{1})\;{\bmod {\;}}2^{w}$

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

$A=((A\oplus B)\lll B)+S_{2i}$

$B=((B\oplus A)\lll A)+S_{2i+1}$

Расшифрование

---

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

$B=((B-S_{2i+1})\ggg A)\oplus A$

$A=((A-S_{2i})\ggg B)\oplus B$

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

$B=(B-S_{1})\;{\bmod {\;}}2^{w}$

$A=(A-S_{0})\;{\bmod {\;}}2^{w}$

Свойства

Алгоритм RC5 обладает следующими свойствами:

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

Криптостойкость

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

RSA Security Challenge

Для стимуляции изучения и применения шифра RC5 RSA Security 28 января 1997 года предложила взломать серию сообщений, зашифрованных алгоритмом RC5 с разными параметрами,назначив за взлом каждого сообщения приз в $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 % ключей.

В мае 2007 года RSA Security Inc. объявила о прекращении поддержки соревнования и выплаты денежного вознаграждения. Чтобы не прекращать проектRC-72,distributed.net решила спонсировать для него приз в $4 000 из собственных средств.

Атака по времени выполнения

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

Варианты алгоритма

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

RC5XOR

В этом алгоритме сложение с ключом раунда по модулю$2^{w}$заменено операцией XOR:

$A_{i+1}=((A_{i}\oplus B_{i})\lll B_{i})\oplus S_{2i}$

$B_{i+1}=((B_{i}\oplus A_{i})\lll A_{i})\oplus S_{2i+1}$

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

RC5P

В этом алгоритме сложение двух обрабатываемых «подблоков» операцией XOR заменено сложением по модулю$2^{w}$:

$A_{i+1}=((A_{i}+B_{i})\lll B_{i})+S_{2i}$

$B_{i+1}=((B_{i}+A_{i})\lll A_{i})+S_{2i+1}$

RC5PFR

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

$A_{i+1}=((A_{i}\oplus B_{i})\lll R_{i})+S_{2i}$

$B_{i+1}=((B_{i}\oplus A_{i})\lll R_{i})+S_{2i+1}$,

где$R_{i}$фиксированное число.

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

RC5KFR

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

$A_{i+1}=((A_{i}\oplus B_{i})\lll R_{i}(L_{i}))+S_{2i}$

$B_{i+1}=((B_{i}\oplus A_{i})\lll R_{i}(L_{i}))+S_{2i+1}$,

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

RC5RA

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

$A_{i+1}=((A_{i}\oplus B_{i})\lll f(L_{i}))+S_{2i}$

$B_{i+1}=((B_{i}\oplus A_{i})\lll f(L_{i}))+S_{2i+1}$,

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

Ссылки

• Шнайер Б.Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. —М.:Триумф, 2002. — 816 с. —3000 экз.—ISBN 5-89392-055-4.
• Часто задаваемые вопросы по симметричным шифрам(рус.).— по материалам конференции fido7.ru.crypt. Дата обращения: 11 ноября 2009. Архивировано изоригинала22 августа 2011 года.
• Современные методы вскрытия алгоритмов шифрования(рус.).— Описание некоторых методов атак на алгоритмы шифрования. Дата обращения: 4 декабря 2009. Архивировано изоригинала21 мая 2009 года.