RC5

RC5
	Один раунд (два полураунда) блочного шифра RC5.
Общий
Дизайнеры	Рон Ривест
Впервые опубликовано	1994
Преемники	RC6 , Акеларре
Деталь шифрования
Размеры ключей	От 0 до 2040 бит (рекомендуется 128)
Размеры блоков	32, 64 или 128 бит (рекомендуется 64)
Структура	Фейстеля Сеть типа
Раунды	1-255 (изначально предлагалось 12)
Лучший публичный криптоанализ
	12-раундовый RC5 (с 64-битными блоками) подвержен дифференциальной атаке с использованием 2 44 выбранные открытые тексты.

В криптографии отличающийся RC5 — это с симметричным ключом, блочный шифр своей простотой. Разработан Рональдом Ривестом в 1994 году. ^{[ 2 ]} RC означает «шифр Ривеста» или, альтернативно, «код Рона» (сравните RC2 и RC4 ). для расширенного стандарта шифрования (AES) Кандидат RC6 был основан на RC5.

Описание

В отличие от многих схем, RC5 имеет переменный размер блока (32, 64 или 128 бит ), размер ключа (от 0 до 2040 бит) и количество раундов (от 0 до 255). Первоначально предложенный выбор параметров включал размер блока 64 бита, 128-битный ключ и 12 раундов.

Ключевой особенностью RC5 является использование ротации в зависимости от данных; Одной из целей RC5 было стимулирование изучения и оценки таких операций как криптографических примитивов . ^{[ нужна ссылка ]} RC5 также состоит из ряда модульных дополнений и исключительных ИЛИ (XOR) . Общая структура алгоритма представляет собой сеть типа Фейстеля , аналогичную RC2. Процедуры шифрования и дешифрования можно указать в нескольких строках кода. Расписание ключей, однако, более сложное: расширение ключа осуществляется с использованием, по существу, односторонней функции с двоичными разложениями как e , так и золотого сечения в качестве источников « ничего в запасе ». Дразнящая простота алгоритма вместе с новизной вращения, зависящего от данных, сделали RC5 привлекательным объектом изучения для криптоаналитиков. ^{[ по мнению кого? ]} RC5 в основном обозначается как RC5-w/r/b, где w = размер слова в битах, r = количество раундов, b = количество байтов в ключе.

Алгоритм

Шифрование и дешифрование RC5 расширяют случайный ключ до 2 (r+1) слов, которые будут использоваться последовательно (и только один раз каждое) во время процессов шифрования и дешифрования. Все нижеизложенное взято из пересмотренной статьи Ривеста по RC5. ^{[ 3 ]}

Ключевое расширение

Алгоритм расширения ключа показан ниже, сначала в псевдокоде , затем в примере кода C, скопированного непосредственно из приложения к справочному документу.

Следуя схеме именования, приведенной в статье, используются следующие имена переменных:

$w$ – длина слова в битах, обычно 16, 32 или 64. Шифрование выполняется блоками по 2 слова.
$u = w /8$ – Длина слова в байтах.
$b$ – Длина ключа в байтах.
$K[]$ — ключ, рассматриваемый как массив байтов (с использованием индексации, отсчитываемой от 0).
$c$ – Длина ключа в словах (или 1, если b = 0).
$L[]$ — временный рабочий массив, используемый во время планирования ключей, инициализированный ключом в словах.
$r$ – количество раундов, используемых при шифровании данных.
$t = 2(r +1)$ – количество требуемых раундовых подразделов.
$S[]$ – круглые слова подключей.
P _w – первая магическая константа, определенная как Odd(( e − 2) × 2 ^В) , где Odd — ближайшее нечетное целое число к заданному входу, e — основание натурального логарифма , а w определено выше. Для общих значений w соответствующие значения P _w указаны здесь в шестнадцатеричном виде:
- Для w = 16: 0xB7E1
- Для w = 32: 0xB7E15163
- Для w = 64: 0xB7E151628AED2A6B
Q _w – вторая магическая константа, определяемая как Odd((𝜙 − 1) × 2 ^В) , где Odd — ближайшее нечетное целое число к заданному входу, где 𝜙 — золотое сечение , а w определено выше. Для общих значений w соответствующие значения Q _w приведены здесь в шестнадцатеричном формате:
- Для w = 16: 0x9E37
- Для w = 32: 0x9E3779B9
- Для w =64: 0x9E3779B97F4A7C15

# Break K into words
# u = w / 8
c = ceiling(max(b, 1) / u)
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
    L[i / u] = (L[i / u] <<< 8) + K[i]
     
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S[0] = P_w
for i = 1 to t-1 do:
    S[i] = S[i - 1] + Q_w
    
# The main key scheduling loop
i = j = 0
A = B = 0
do 3 * max(t, c) times:
    A = S[i] = (S[i] + A + B) <<< 3
    B = L[j] = (L[j] + A + B) <<< (A + B)
    i = (i + 1) % t
    j = (j + 1) % c

# return S

Пример исходного кода взят из приложения к статье Ривеста о RC5. Реализация предназначена для работы с w = 32, r = 12 и b = 16.

void RC5_SETUP(unsigned char *K)
{
   // w = 32, r = 12, b = 16
   // c = max(1, ceil(8 * b/w))
   // t = 2 * (r+1)
   WORD i, j, k, u = w/8, A, B, L[c];
   
   for (i = b-1, L[c-1] = 0; i != -1; i--)
      L[i/u] = (L[i/u] << 8) + K[i];
   
   for (S[0] = P, i = 1; i < t; i++)
      S[i] = S[i-1] + Q;
   
   for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c)
   {
      A = S[i] = ROTL(S[i] + (A + B), 3);
      B = L[j] = ROTL(L[j] + (A + B), (A + B));
   }
}

Шифрование

Шифрование включало несколько раундов простой функции, из которых, по-видимому, рекомендуется 12 или 20 раундов, в зависимости от требований безопасности и соображений времени. Помимо переменных, использованных выше, в этом алгоритме используются следующие переменные:

A, B — два слова, составляющие блок открытого текста, который необходимо зашифровать.

A = A + S[0]
B = B + S[1]
for i = 1 to r do:
    A = ((A ^ B) <<< B) + S[2 * i]
    B = ((B ^ A) <<< A) + S[2 * i + 1]

# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B

Пример кода C, предоставленный Ривестом, таков.

void RC5_ENCRYPT(WORD *pt, WORD *ct)
{
   WORD i, A = pt[0] + S[0], B = pt[1] + S[1];
   
   for (i = 1; i <= r; i++)
   {
      A = ROTL(A ^ B, B) + S[2*i];
      B = ROTL(B ^ A, A) + S[2*i + 1];
   }
   ct[0] = A; ct[1] = B;
}

Расшифровка

Дешифрование представляет собой довольно простой процесс обращения процесса шифрования. Приведенный ниже псевдокод показывает процесс.

for i = r down to 1 do:
    B = ((B - S[2 * i + 1]) >>> A) ^ A
    A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]

return A, B

Пример кода C, предоставленный Ривестом, таков.

void RC5_DECRYPT(WORD *ct, WORD *pt)
{
   WORD i, B=ct[1], A=ct[0];
   
   for (i = r; i > 0; i--)
   {
      B = ROTR(B - S[2*i + 1], A) ^ A;
      A = ROTR(A - S[2*i], B) ^ B;
   }
   
   pt[1] = B - S[1]; pt[0] = A - S[0];
}

Криптоанализ

Двенадцатираундовый RC5 (с 64-битными блоками) восприимчив к дифференциальной атаке с использованием 2 ⁴⁴ выбранные открытые тексты. ^{[ 1 ]} В качестве достаточной защиты предлагается 18–20 патронов.

Ряд этих проблем был решен с помощью распределенных вычислений , организованных Distributed.net . Distributed.net использует брутфорсированные сообщения RC5, зашифрованные с помощью 56-битных и 64-битных ключей, и работает над взломом 72-битного ключа с 3 ноября 2002 года. ^{[ 4 ]} По состоянию на 26 июля 2023 года было просмотрено 10,409% пространства ключей, и, исходя из показателей, зарегистрированных на тот день, для заполнения 100% пространства ключей потребуется чуть более 59 лет. ^{[ 5 ]} Эта задача вдохновила на множество новых и нестандартных разработок в области кластерных вычислений. ^{[ 6 ]}

RSA Security , у которой был патент на алгоритм (сейчас срок действия которого истек), ^{[ 7 ]} предложил серию призов в размере 10 000 долларов США за взлом зашифрованных текстов, зашифрованных с помощью RC5, но эти конкурсы были прекращены с мая 2007 года. ^{[ 4 ]} В результате компания Distributed.net решила профинансировать денежный приз. Человек, обнаруживший выигрышный ключ, получит 1000 долларов США, его команда (если применимо) получит 1000 долларов США, а Фонд свободного программного обеспечения получит 2000 долларов США. ^{[ 8 ]}

См. также

Ссылки

^ Перейти обратно: ^а ^б Бирюков, Алексей ; Кушилевиц, Эяль (31 мая 1998 г.). Улучшенный криптоанализ RC5 (PDF) . ЕВРОКРИПТ 1998. doi : 10.1007/BFb0054119 .
^ Ривест, Р.Л. (1994). «Алгоритм шифрования RC5» (PDF) . Материалы второго международного семинара по быстрому программному шифрованию (FSE), 1994e . стр. 86–96. Архивировано из оригинала (PDF) 17 апреля 2007 г. Проверено 18 декабря 2004 г.
^ http://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf. Архивировано 21 сентября 2018 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}
^ Перейти обратно: ^а ^б «distributed.net: Проект RC5» . www.distributed.net . Проверено 14 декабря 2019 г.
^ RC5-72 / Общая статистика проекта
^ «Суперкомпьютер PlayStation 3 ставит Университет Массачусетского университета в Дартмуте на первое место в мире в списке задач по взлому кода» (пресс-релиз). Массачусетский университет в Дартмуте . 24 сентября 2014 г. Архивировано из оригинала 29 июня 2022 г. Проверено 24 января 2024 г.
^ Ривест, Р.Л., «Алгоритм блочного шифрования с чередованием, зависящим от данных», патент США № 5,724,428 , выданный 3 марта 1998 г., срок действия истек 1 ноября 2015 г.
^ «distributed.net: блоги сотрудников – 2008 г. – сентябрь – 08» . Проверено 15 декабря 2019 г.

Внешние ссылки

[Biryukov-1] Перейти обратно: ^а ^б Бирюков, Алексей ; Кушилевиц, Эяль (31 мая 1998 г.). Улучшенный криптоанализ RC5 (PDF) . ЕВРОКРИПТ 1998. doi : 10.1007/BFb0054119 .

[fse1994-2] Ривест, Р.Л. (1994). «Алгоритм шифрования RC5» (PDF) . Материалы второго международного семинара по быстрому программному шифрованию (FSE), 1994e . стр. 86–96. Архивировано из оригинала (PDF) 17 апреля 2007 г. Проверено 18 декабря 2004 г.

[3] ttp://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf. Архивировано 21 сентября 2018 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}

[distributed.net:_Project_RC5-4] Перейти обратно: ^а ^б «distributed.net: Проект RC5» . www.distributed.net . Проверено 14 декабря 2019 г.

[5] RC5-72 / Общая статистика проекта

[6] «Суперкомпьютер PlayStation 3 ставит Университет Массачусетского университета в Дартмуте на первое место в мире в списке задач по взлому кода» (пресс-релиз). Массачусетский университет в Дартмуте . 24 сентября 2014 г. Архивировано из оригинала 29 июня 2022 г. Проверено 24 января 2024 г.

[7] Ривест, Р.Л., «Алгоритм блочного шифрования с чередованием, зависящим от данных», патент США № 5,724,428 , выданный 3 марта 1998 г., срок действия истек 1 ноября 2015 г.

[8] «distributed.net: блоги сотрудников – 2008 г. – сентябрь – 08» . Проверено 15 декабря 2019 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]