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

Описание

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

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

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

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

Параметры

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle S_{0}=P_{w}}$

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

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

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

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

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

${\displaystyle i=(i+1)\mod (2(R+1))}$

${\displaystyle j=(j+1)\mod c}$ ,

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

Шифрование

---

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

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

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

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

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

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

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

---

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

RC5P

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

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

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

RC5PFR

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

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

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

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

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

RC5KFR

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

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

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

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

RC5RA

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

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

${\displaystyle 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 года.