RC5

RC5 — це алгоритм симетричного шифрування, розроблений Роном Райвестом в середині 90-х років.

RC5

Розробники	Рональд Рівест, RSA
Уперше оприлюднений	1994 р.
Раундів	12
Тип	Мережа Фейстеля

Характеристики

Під час розробки RC5 ставилося завдання досягти наступних характеристик:

• Придатність для апаратної та програмної реалізації. В RC5 використовуються тільки елементарні обчислювальні операції, які зазвичай застосовуються в мікропроцесорах.
• Швидкість виконання. RC5 є простим алгоритмом, що працює з даними розміром в машинне слово. Усі основні операції передбачають також роботу з даними довжиною в слово.
• Адаптованість до процесорів з різною довжиною слова. Довжина слова в бітах є параметром RC5 — при зміні довжини слова змінюється сам алгоритм.
• Змінна кількість раундів. Кількість раундів є другим параметром RC5. Цей параметр дозволяє обрати оптимальне співвідношення між швидкістю роботи та ступенем захисту.
• Змінна довжина ключа. Довжина ключа є третім параметром RC5. Як і в попередньому випадку, цей параметр дозволяє знайти прийнятний компроміс між швидкістю роботи та необхідним рівнем безпеки.
• Простота. Структура RC5 дуже проста не тільки для реалізації, але й для оцінки її криптоаналітичної стійкості.
• Низькі вимоги до пам'яті. Низькі вимоги до пам'яті роблять RC5 придатним для використання в смарт-картах та інших подібних пристроях з обмеженим обсягом пам'яті.
• Високий ступінь захисту. RC5 покликаний забезпечити високий ступінь захисту за умови вибору відповідних значень параметрів.
• Залежність циклічних зсувів від даних. В RC5 використовуються циклічні зсуви, величина яких залежить від даних, що має підвищувати криптоаналітичну стійкість алгоритму.

Алгоритм RC5 вбудовано до багатьох основних продуктів компанії RSA Data Security Inc., зокрема BSAFE, JSAFE та S/MAIL. RC5 фактично являє собою родину алгоритмів шифрування, що визначається трьома такими параметрами:

Параметри алгоритму RC5

Параметр	Визначення	Допустимі значення
w	Розмір слова в бітах. RC5 шифрує дані блоками завдовжки 2 слова	16, 32, 64
r	Кількість раундів	0, 1, …, 255
b	Кількість 8-бітових байтів (октетів) в таємному ключі К	0, 1, …, 255

Таким чином, RC5 шифрує блоки відкритого тексту довжиною 32, 64 чи 128 бітів в блоки шифрованого тексту тієї самої довжини. Довжина ключа може змінюватись від 0 до 2040 бітів. Конкретна версія RC5 позначається RC5-w/r/b. Наприклад, RC5-32/12/16 використовує 32-бітові слова (64-бітові блоки відкритого і шифрованого тексту), 12 раундів шифрування і ключ довжиною 16 байтів (128 бітів). Райвест пропонує використовувати RC5-32/12/16 як «стандартну» версію RC5.

Елементарні операції

В алгоритмі RC5 виконуються три елементарні операції (а також обернені до них):

• Додавання. Додавання слів, позначене символом +, виконується по модулю 2w. Обернена операція, позначена символом -, є відніманням по модулю 2w.
• Побітове виключне АБО. Ця операція позначається символом Å.
• Циклічний зсув вліво. Циклічний зсув слова x вліво на y бітів позначається x<<<y. Обернена операція є циклічним зсувом слова x вправо на y бітів і позначається x>>>y.

Шифрування

Вхідні дані: відкритий текст M=(A,B) довжиною 2w бітів; кількість раундів r; ключ K=K[0]…K[b-1].

Вихідні дані: шифрований текст С довжиною 2w бітів.

1. Обчислити (2r+2) підключів S[0]…S[2r+1] за відповідним алгоритмом з вхідного K та r.
2. A:=A+S[0], B:=B+S[1] (додавання здійснюється за модулем 2w).
3. Від i=1 до r виконати : A:=((AÅB)<<<B)+S[2i], B:=((BÅA)<<<A)+S[2i+1].
4. Вихідним значенням є C:=(A,B).

Дешифрування

Для дешифрування використовуються ті самі підключі, які застосовуються для шифрованого тексту C=(A,B), таким чином (віднімання здійснюється за модулем 2w).

1. Від i=r по спаданню до 1 виконати : B:=((B-S[2i+1])>>>A)ÅA, A:=((A-S[2i])>>>B)ÅB.
2. Результат M:=(A-S[0],B-S[1]). (рис. 1б)

Створення підключів

Підключі зберігаються в масиві з (2r+2) слів, елементи якого позначені S[0], S[1],…,S[2r+1]. Використовуючи як вхідні дані параметри r та w, цей масив ініціалізується псевдовипадковими фіксованими значеннями. Потім ключ K[0…b-1] довжиною b байтів перетворюється в масив L[0…c-1], що містить c слів. Для цього байти ключа копіюються в масив L доповнюючи при необхідності останнє слово справа нулями. Зрештою виконується деяка операція змішування, що об'єднує вміст L з ініціалізованими значеннями S, в результаті чого отримують остаточне значення масиву S.

Алгоритм створення підключів виглядає так:

Вхідні дані: розмір слова в бітах w; кількість раундів r; ключ довжиною b байтів K[0]…K[b-1].

Вихідні дані: підключі S[0]…S[2r+1] (де кожне S[i] має довжину w бітів).

• Перетворення ключа К в масив L. Нехай u=w/8 (кількість байтів у слові) і c=int[b/u] (довжина К в словах).

Ключ К заповнюється справа нулями при необхідності отримати кількість байтів, що ділиться на u (тобто for j=b to (c×u-1) do: K[j]:=0). For i=0 to c-1 do: (тобто заповнюємо L[j] від молодшого до старшого байта використовуючи по одному разу кожен байт K[×]).

• Ініціалізація масиву S:

S[0]:=Pw; for i=1 to 2r+1 do: S[i]:=S[i-1]+Qw. (тут Pw Qw є константами, заснованими на двійковому представленні чисел е та j (основи натуральних логарифмів та відношення золотого перетину). Значення цих констант для алгоритму RC5 наведено в табл. 4.)

• Змішування ініціалізованого масиву S з масивом ключів L:

i:=0, j:=0, A:=0, B:=0, t:=max(c, 2r+2). For s=1 to 3t do: (здійснюється три проходи більшого з масивів L і S) S[i]:=(S[i]+A+B)<<<3, A:=S[i], i:=(i+1)mod(2r+2). L[j]:=(L[j]+A+B)<<<(A+B), B:=L[j], j:=(j+1)mod(c)

• Виходом є S[0], S[1], … , S[2r+1].

При створенні програмного забезпечення захисту інформації особливу увагу слід приділяти безпечній реалізації таких програм. Так, наприклад, основними операціями з ключами шифрування є створення, знищення та встановлення значення. З метою запобігання розповсюдження ключової інформації в інші частини програми, операція знищення має заповнити нулями область пам'яті виділену для роботи з ключем, перед тим як звільняти її менеджеру пам'яті. Взагалі об'єкт ключа може підтримувати й інші операції, такі як створення нового випадкового ключа чи отримання ключа з даних протоколу обміну ключами.

Режими шифру

З метою забезпечення можливості ефективного використання RC5 в неоднорідному середовищі, специфікація RFC 2040 визначає чотири різних режими роботи цього алгоритму.

1. Блочний шифр RC5. Алгоритм прямого шифрування, при якому береться блок даних заданого розміру (2w бітів) і з нього за допомогою залежного від ключа перетворення генерується блок шифрованого тексту такого самого розміру. Цей режим часто називають режимом ECB (режим електронної шифрувальної книги).
2. RC5-CBC. Режим зв'язаних шифрованих блоків для RC5. В режимі СВС обробляються повідомлення, довжина яких кратна розміру блока RC5 (тобто кратна 2w бітам). Режим СВС забезпечує вищий ступінь захисту, ніж ЕСВ, оскільки генерує різні блоки шифрованого тексту для однакових повторних блоків відкритого тексту.
3. RC5-CBC-Pad. Модифікація режиму СВС, призначена для роботи з відкритим текстом будь-якої довжини. Довжина шифрованого тексту в цьому режимі перевищує довжину відкритого тексту не більш ніж на довжину одного блоку RC5.
4. RC5-CTS. Режим запозичення шифрованого тексту (ciphertext stealing), теж є модифікацією СВС. В цьому режимі допускається обробка відкритого тексту будь-якої довжини і генерується шифрований текст тієї самої довжини.

Див. також

• Блочний шифр