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

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

Описание [ править ]

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

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

Алгоритм [ править ]

И шифрование 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 - основание натурального логарифма , а w определено выше. Для общих значений w соответствующие значения P w даны здесь в шестнадцатеричном формате:
    • Для w = 16: 0xB7E1
    • Для w = 32: 0xB7E15163
    • Для w = 64: 0xB7E151628AED2A6B
  • Q w - вторая магическая константа, определяемая как , где Odd - ближайшее нечетное целое число к заданному входу, где - золотое сечение , а w определено выше. Для общих значений w соответствующие значения Q w даны здесь в шестнадцатеричном формате:
    • Для w = 16: 0x9E37
    • Для w = 32: 0x9E3779B9
    • Для w = 64: 0x9E3779B97F4A7C15
# Перерыв К в слова # и = ш / 8 с  =  потолка ( макс ( б ,  1 )  /  у ) # L первоначально список с-длина 0-значной W-длина слова для  я  =  б - 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 сделать  3  *  max ( t ,  c )  раз :  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)  СЛОВО  i ,  j ,  k ,  u  =  w / 8 ,  A ,  B ,  L [ c ];  для  ( i  =  b -1 ,  L [ c -1 ]  =  0 ;  i  ! =  -1 ;  i - )  L [ i / u ]  =  ( L [ i / u ]  <<  8 )  +  K [ i ] ;  для  ( S [ 0 ]  =  P ,  i  =  1 ;  i  <  t ;  i ++ )  S [ i ]  =  S [ i -1 ]  +  Q ;  для  ( 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  + Б ),  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 в указанном порядке. вернуть  A ,  B

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

void  RC5_ENCRYPT ( WORD  * pt ,  WORD  * ct ) {  WORD  i ,  A  =  pt [ 0 ]  +  S [ 0 ],  B  =  pt [ 1 ]  +  S [ 1 ];  для  ( 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 ; }

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

Расшифровка - это довольно простой способ полностью изменить процесс шифрования. Нижеприведенный псевдокод показывает процесс.

для  я  =  г  вниз  до  1  сделать :  B  =  (( B  -  S [ 2  *  я  +  1 ])  >>>  ) ^ = (( - S [ 2 * я ]) >>> Б ) ^ 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 ];  для  ( 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 ]; }

Криптоанализ [ править ]

12-раундовый RC5 (с 64-битными блоками) подвержен дифференциальной атаке с использованием 2 44 выбранных открытых текстов. [1] В качестве достаточной защиты рекомендуется 18–20 патронов.

Некоторые из этих сложных проблем были решены с помощью распределенных вычислений , организованных Distributed.net . Distributed.net использует сообщения RC5 методом перебора, зашифрованные с помощью 56-битных и 64-битных ключей, и работает над взломом 72-битного ключа с 3 ноября 2002 года. [4] По состоянию на 13 декабря 2019 года, 6,222% от общего числа Ключевое пространство было исследовано, и, судя по скорости, зарегистрированной в тот день, потребуется 102 года, чтобы заполнить 100% ключевого пространства. [5] Эта задача вдохновила на множество новых и новаторских разработок в области кластерных вычислений. [6]

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

См. Также [ править ]

  • Мадрыга
  • Красная щука

Ссылки [ править ]

  1. ^ a b Бирюков А., Кушилевиц Э. (1998). Улучшенный криптоанализ RC5. ЕВРОКРИПТ 1998.
  2. Перейти ↑ Rivest, RL (1994). «Алгоритм шифрования RC5» (PDF) . Труды Второго международного семинара по быстрому шифрованию программного обеспечения (FSE) 1994e . С. 86–96.
  3. ^ http://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf
  4. ^ "Distributed.net: Project RC5" . www.distributed.net . Проверено 14 декабря 2019 .
  5. ^ RC5-72 / Общая статистика проекта
  6. ^ "Архивная копия" . Архивировано из оригинала на 2014-10-28 . Проверено 28 октября 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )
  7. ^ Ривест, Р. Л., «Алгоритм блочного шифрования с чередованием, зависящим от данных», патент США № 5724428 , выданный 3 марта 1998 г.
  8. ^ "Distributed.net: Project RC5" . www.distributed.net . Проверено 14 декабря 2019 .
  9. ^ "Distributed.net: блоги сотрудников - 2008 - сентябрь - 08" . Проверено 15 декабря 2019 .

Внешние ссылки [ править ]

  • Исправленная статья Ривестса с описанием шифра
  • Оригинальная бумага Ривеста
  • Запись SCAN для шифра
  • Часто задаваемые вопросы о лабораториях RSA - Что такое RC5 и RC6?
  • Ссылки Хельгера Липмаа на RC5