RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].

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

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - S0, S1, S2, ... S2r+1 - где r - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала разделим блок открытого текста на два 32-битовых слова: A и B. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра A, и т.д.) Затем:

A = A + S0

B = B + S1

For i = 1 to r:

A = ((A A B) <<< B) + S2i

B = ((B A A) <<< A) + S2i+1

Результат находится в регистрах A и B.

Дешифрирование также просто. Разбейте блок открытого текста на два слова, A и B, а затем:

For i = r down to 1:

B = ((B - S2i+1) >>> A) A A

A = ((A - S2i) >>> B) A B

B = B - S1

A = A - S0

Символ ">>>" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 232.

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в массив L из c 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 232:

S0 = P

for i = 1 to 2(r + 1) - 1:

Si = (Si-1 + Q) mod 232

P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении e и phi.

Наконец, подставляем L в S:

i = j = 0

A = B = 0

выполнить n раз (где n - максимум 2(r + 1) и c):

A = Si = (Si + A + B) <<< 3

B = Li = (Li + A + B) <<< (A + B)

i = (i + 1) mod 2(r + 1)

j = (j + 1 ) mod c

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым словом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, P и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15, соответственно. Ривест обозначил различные реализации RC5 как RC5-w/r/b, где w - это размер слова, r - число этапов, а b - длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 224 выбранных открытых текстов для 5 этапов, 245 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утверждает, что плата за лицензирование будет очень мала, но это лучше проверить.