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

# Разбиваем K на слова  # u = w / 8  c   =   потолок  (  max  (  b  ,   1  )   /   u  )  L изначально представляет собой список длиной c 0-значных слов длины w  для   i   =   b  -  1   до   #   0   do  :      L  [  i   /   u  ]   =   (  L  [  i   /   u  ]   <<<   8  )   +   K  [  i  ]       # Инициализируем независимый от ключа псевдослучайный массив S  # Первоначально S имеет длину =2(r+1) список неопределенных значений Слова длины w  S  [  0  ]   =   P_w  для   i   =   1   до   t  -  1   do  :      S  [  i  ]   =   S  [  i   -   1  ]   +   Q_w      # Основной цикл планирования ключей  i   =   j   =   0  A   =   B   =   0  do   3   *   максимум  (  t  ,   c  )   раз  :      A   =   S  [  i  ]   =   (  S  [  i  ]   +   A   +   B  )   <<<   3      B   =   L  [  j  ]   =   (  L  [  j  ]   +   A   +   B  )   << <   (  A   +   B  )      я   =   (  я   +   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)     СЛОВО   я  ,   j  ,   k  ,   ты   знак равно   ш  /  8  ,   А  ,   B  ,   L  [  c  ];        для   (  я   знак равно   б  -1  ,   L  [  c  -1  ]   знак равно   0  ;   я   !=   -1  ;   я  --  )        L  [  я  /  ты  ]   =   (  L  [  я  /  ты  ]   <<   8  )   +   K  [  я  ] ;        для   (  S  [  0  ]   знак равно   п  ,   я   знак равно   1  ;   я   <   т  ;   я  ++  )        S  [  я  ]   знак равно   S  [  я  -1  ]   +   Q  ;        for   (  A   =   B   =   я   =   j   =   k   =   0  ;   k   <   3   *   t  ;   k  ++  ,   я   =   (  i  +  1  )   %   t  ,   j   =   (  j  +  1  )   %   c  )     {        A   =   S  [  я  ]   =   ROTL  (  S  [  я  ]   +   (  А   +   B  ),   3  );        B   =   L  [  j  ]   =   ROTL  (  L  [  j  ]   +   (  A   +   B  ),   (  A   +   B  ));     }  }

Шифрование [ править ]

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

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

A   =   A   +   S  [  0  ]  B   =   B   +   S  [  1  ]  для   i   =   1   до   r   сделайте  :      A   =   ((  A   ^   B  )   <<<   B  )   +   S  [  2   *   i  ]      B   =   ((  B   ^   A  )   <<<   A  )   +   S  [  2   *   i   +   1  ]  # Блок зашифрованного текста состоит из блока шириной в два слова, состоящего из A и B в указанном порядке.  вернуть   А  ,   Б

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

void   RC5_ENCRYPT  (  WORD   *  pt  ,   WORD   *  ct  )  {     WORD   i  ,   A   =   pt  [  0  ]   +   S  [  0  ],   B   =   pt  [  1  ]   +   S  [  1  ];        для   (  я знак   равно   1  ;   я   <=   р  ;   я  ++  )     {        A   =   ROTL  (  A   ^   B  ,   B  )   +   S  [  2  *  я  ];        B   =   ROTL  (  B   ^   A  ,   A  )   +   S  [  2  *  я   +   1  ];     }     ct  [  0  ]   знак равно   А  ;   ct  [  1  ]   знак равно   B  ;  }

Расшифровка [ править ]

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

для   i   =   r   до   1   A   сделайте  :      B   =   ((  B   -   S  [  2   *   i   +   1  ])   >>>   )  ^   A   A      =   (   (  A   -   S  [  2   *   i  ])   >>>   B  )   ^   B  B   =   B   -   S  [  1  ]  A   =   A   -   S  [  0  ]  вернуть   A  ,   B

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

void   RC5_DECRYPT  (  WORD   *  ct  ,   WORD   *  pt  )  {     WORD   i  ,   B  =  ct  [  1  ],   A  =  ct  [  0  ];        для   (  я   знак равно   р  ;   я   >   0  ;   я  --  )     {        B   =   ROTR  (  B   -   S  [  2  *  я   +   1  ],   A  )   ^   A  ;        А   знак равно   ROTR  (  А   -   S  [  2  *  я  ],   B  )   ^   B  ;     }        пт  [  1  ]   =   B   -   S  [  1  ];   пт  [  0  ]   =   А   -   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]