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 Inc. с переменным количеством раундов, длиной блока и длиной ключа. Это расширяет сферу использования и упрощает переход на более сильный вариант алгоритма.

Описание[править | править исходный текст]

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

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

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

Параметры[править | править исходный текст]

Т.к. алгоритм 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_0L_{c-1}, где c=\mathcal {d}b/u\mathcal {e}, где u = W/8, то есть, количество байт в слове.

Если c не кратен W/8, то L_i дополняется нулевыми битами до ближайшего большего размера 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}

Расшифровка[править | править исходный текст]

Для расшифровки выполняются обратные операции, т.е. в каждом раунде выполняются следующие операции:

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

Свойства[править | править исходный текст]

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

  • Пригодный как для аппаратной, так и для программной реализации (алгоритм использует операции выполняющиеся одинаково быстро на всех процессорах).
  • Каждый раунд обрабатывает весь блок целиком (типичный раунд сети Фейстеля обрабатывает только «подблок»).
  • Одинаково хорош для машин с разной длиной машинного слова (т.е. работает также хорошо и на 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 Inc. 28 января 1997 года предложила взломать серию сообщений, зашифрованных алгоритмом RC5 с разными параметрами,[2] назначив за взлом каждого сообщения приз в $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, в котором по состоянию на октября 2013 года удалось перебрать около 3% ключей.[3]

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

Атака по времени выполнения[править | править исходный текст]

На платформах, где операция циклического сдвига на переменное число битов выполняется за различное число тактов процессора, возможна атака по времени исполнения на алгоритм 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}

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

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.

Примечания[править | править исходный текст]

  1. Rivest, R. L. (1994). "The RC5 Encryption Algorithm" (pdf). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e: 86–96. 
  2. The RSA Laboratories Secret-Key Challenge
  3. RC5-72: Overall project statistics
  4. distributed.net: staff blogs — 2008 — September — 08

Ссылки[править | править исходный текст]