RC5

RC5 — это симметричный блочный шифр, разработанный в 1994 году американским криптографом Рональдом Ривестом из Массачусетского технологического института (MIT). Шифр известен своей простотой, высокой скоростью работы и адаптируемой архитектурой, позволяющей варьировать длину ключа, размер блока и количество раундов. RC5 стал основой для ряда других алгоритмов и широко использовался в учебных целях и встраиваемых системах, однако впоследствии был признан уязвимым для некоторых видов атак.

История

RC5 был представлен Рональдом Ривестом в 1994 году в техническом отчете «The RC5 Encryption Algorithm» (MIT/LCS/TR-684). Название расшифровывается как «Rivest Cipher 5» (шифр Ривеста 5). Алгоритм был разработан как более быстрая и гибкая альтернатива существовавшим на тот момент шифрам, таким как DES. RC5 не был запатентован в традиционном смысле, но его реализация была защищена авторским правом, а сам алгоритм был опубликован в открытом доступе. В 1995 году компания RSA Security (организация, занимающаяся информационной безопасностью) лицензировала RC5, и он стал частью набора криптографических протоколов.

В 1998 году на основе RC5 был создан шифр RC6, который стал финалистом конкурса AES (Advanced Encryption Standard), но не победил. RC5 также использовался в протоколе WEP (Wired Equivalent Privacy) для защиты беспроводных сетей, однако из-за слабой реализации ключей в WEP эта связь оказалась уязвимой.

Описание алгоритма

RC5 является блочным шифром, то есть шифрует данные блоками фиксированной длины. Его ключевая особенность — параметризуемость, обозначаемая как RC5-w/r/b, где:

• w — размер блока в битах (обычно 16, 32 или 64; стандартное значение — 32);
• r — количество раундов (от 0 до 255, рекомендуется не менее 12);
• b — длина ключа в байтах (от 0 до 255, обычно 16).

Таким образом, обозначение RC5-32/12/16 означает шифр с блоком 32 бита, 12 раундами и ключом длиной 16 байт (128 бит).

Структура

RC5 использует сеть Фейстеля, но с модификацией: в каждом раунде применяются операции сложения, XOR (исключающее ИЛИ) и циклического сдвига. Алгоритм состоит из трех основных этапов:

1. Расширение ключа — из исходного ключа генерируется массив из 2r+2 подключей (S[0], S[1], ..., S[2r+1]). Процедура использует константы, основанные на математических константах (например, P — нечетная часть числа e, Q — нечетная часть числа φ).
2. Шифрование — блок данных делится на две половины (A и B). Выполняется начальное сложение с первыми двумя подключами, затем r раундов, каждый из которых включает:

• XOR половин;
• циклический сдвиг влево на величину, зависящую от данных;
• сложение с подключами.

1. Расшифрование — обратная процедура: вычитание подключей, обратный сдвиг и XOR.

Пример шифрования (упрощенно)

Для блока из 64 бит (w=32) и 12 раундов:

• A = A + S[0]
• B = B + S[1]
• Для i от 1 до r:
• A = ((A XOR B) <<< B) + S[2i]
• B = ((B XOR A) <<< A) + S[2i+1]

Где <<< — циклический сдвиг влево.

Криптостойкость и уязвимости

RC5 считается достаточно стойким при правильном выборе параметров (например, 12 раундов и 128-битный ключ). Однако исследования выявили несколько уязвимостей:

• Линейный криптоанализ — для RC5 с 12 раундами и 64-битным блоком возможна атака, требующая около 2^44 известных открытых текстов.
• Дифференциальный криптоанализ — для 12-раундового RC5 с 64-битным блоком требуется около 2^54 выбранных открытых текстов.
• Атака на основе времени — если реализация не защищена от утечки времени выполнения, возможен подбор ключа.

В 1998 году был проведен проект «RC5-64 Challenge» (организованный RSA Security), в рамках которого с помощью распределенных вычислений был взломан RC5-32/12/16 (64-битный ключ). Взлом занял 5 лет и потребовал перебора около 2^64 ключей. Позже, в 2002 году, был взломан RC5-32/12/16 с 128-битным ключом (RC5-128) — это заняло около 4 лет.

Применение

RC5 применялся в следующих областях:

• Протокол WEP — для шифрования трафика в беспроводных сетях стандарта 802.11. Однако из-за слабой генерации ключей (статический ключ или короткий вектор инициализации) WEP был полностью скомпрометирован.
• Встраиваемые системы — благодаря малому размеру кода и высокой скорости, RC5 использовался в микроконтроллерах и смарт-картах.
• Криптографические библиотеки — например, в библиотеке OpenSSL (до версии 1.1.0) была поддержка RC5, но позже она была удалена из-за устаревания.
• Учебные цели — из-за простоты реализации RC5 часто используется в курсах криптографии для демонстрации принципов блочного шифрования.

Сравнение с другими шифрами

Интересные факты

• RC5 является одним из первых шифров, в которых операция циклического сдвига зависит от самих данных (data-dependent rotation), что усложняет криптоанализ.
• Алгоритм RC5 был использован в проекте «Distributed.net» для демонстрации возможностей распределенных вычислений — взлом RC5-64 стал одним из первых крупных успехов такого подхода.
• В 1995 году Рональд Ривест опубликовал алгоритм RC5 с открытым исходным кодом, что способствовало его широкому распространению в академической среде.

Критика

Основная критика RC5 связана с его уязвимостью к атакам по времени и недостаточной стойкостью при малом числе раундов (например, 8 или 10). Кроме того, 64-битный размер блока считается недостаточным для современных стандартов безопасности (рекомендуется не менее 128 бит). В связи с этим RC5 был вытеснен более современными алгоритмами, такими как AES (Rijndael) и ChaCha20.

Источники

• Rivest, R. L. (1994). The RC5 Encryption Algorithm. MIT/LCS/TR-684.
• RSA Laboratories. (1995). RC5 Algorithm Specification.
• Kaliski, B. S., & Robshaw, M. J. B. (1995). Linear Cryptanalysis of RC5.
• Biryukov, A., & Kushilevitz, E. (1998). Differential Cryptanalysis of RC5.
• Distributed.net. (2002). RC5-64 Challenge Results.