MESH (шифр)

В криптографии, MESH — блочный шифр, являющийся модификацией IDEA. Разработан Жорже Накахарой, Винсентом Рэйменом, Бартом Пренелем и Йоосом Вандевалле в 2002 году. В отличие от IDEA, MESH имеет более сложную раундовую структуру. Иной алгоритм генерации ключей позволяет MESH избегать проблемы слабых ключей[1].

MESH
Создатель Накахара, Рэймен, Пренель, Вандевалле
Опубликован 2002
Размер ключа 128, 192, 256 бит
Размер блока 64, 96, 128 бит
Число раундов 8,5, 10,5, 12,5
Тип основан на IDEA, модификация Сети Фейстеля

Структура шифра

править

Каждый раунд в IDEA и MESH состоит из операций сложения и умножения. Последовательность таких вычислений в пределах одного раунда образует MA-бокс. Все MA-боксы в MESH используют минимум три чередующихся уровня сложений и умножений (по схеме «зиг-заг»), в то время, как в IDEA таковых только два. Это делает MESH более стойким против дифференциальной и линейной криптоатак. Также, с целью избежать проблемы слабых ключей, в MESH используются два следующих принципа:

  • Каждый подключ зависит от почти всех подключей, более точно — как минимум от шести предыдущих ключей нелинейно
  • Используются фиксированные константы. Без них, например, ключ из всех нулей перешел бы в подключи, каждый из которых равнялся бы нулю в любом раунде

Как и в IDEA, MESH использует следующие операции:

  • умножение по модулю  , причем вместо нуля используется   ( )
  • циклический сдвиг влево на   бит ( )
  • сложение по модулю   ( )
  • побитовое исключающее ИЛИ ( )

Операции расположены в порядке уменьшения приоритета. В вычислениях запись   обозначает 16-битное слово. Индексы описываются далее.

MESH описывается в трех вариациях по размерам блока: 64, 96, 128 бит. Размер ключа при этом берется вдвое больший[2].

В данной вариации размер блока составляет 64 бит, ключ — 128 бит. Шифрование проходит в 8,5 раунда. Половина раунда относится к выходным преобразованиям[3].

Раундовые преобразования

править

Обозначим входную информацию для  -го раунда:
 

Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На четных и нечетных раундах перемешивание происходит по-разному:

  • Для нечетных раундов:

 

  • Для четных раундов:

 

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
 

МА-вычисления описываются следующими формулами:
 
 

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
 

Согласно схеме, для получения зашифрованного сообщения необходимо после восьмого раунда провести перемешивание по нечетной схеме  [4]

Генерация ключей

править

Для генерации ключей используется 128-битный пользовательский ключ, а также 16-битные константы  :  ,  , они вычисляются в Поле Галуа   по модулю многочлена  . Пользовательский ключ разбивается на 8 16-битных слов  .

Вычисление подключей происходит следующим образом[5]:
 
 
 
где  .

Расшифровка

править

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
  - подключи полных раундов;
  - подключи выходных преобразований.

Тогда подключи расшифровки задаются следующим образом[6]:

  •  , - первый раунд расшифровки;
  •  , -  четный раунд,  ;
  •  , -  нечетный раунд,  ;
  •  , - выходные преобразования.

В данной вариации размер блока составляет 96 бит, ключ — 192 бит. Шифрование проходит в 10,5 раунда. Половина раунда относится к выходным преобразованиям[7].

Раундовые преобразования

править

Обозначим входную информацию для  -го раунда:
 

Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На четных и нечетных раундах перемешивание происходит по-разному:

  • Для нечетных раундов:

 

  • Для четных раундов:

 

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
 

МА-вычисления описываются следующими формулами:
 
 
 

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
 

Для получения зашифрованного сообщения необходимо после 10-го раунда провести перемешивание по нечетной схеме  [8]

Генерация ключей

править

Для генерации ключей используется 192-битный пользовательский ключ, а также 16-битные константы, такие же, как и для MESH-64.

Вычисление подключей происходит следующим образом[9]:
 
 
 
 
 
где  .

Расшифровка

править

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
  — подключи полных раундов;
  - подключи выходных преобразований.

Тогда подключи расшифровки задаются следующим образом[10]:

  •  , — первый раунд расшифровки;
  •  , —  чётный раунд,  ;
  •  , —  нечётный раунд,  ;
  •  , — выходные преобразования.

В данной вариации размер блока составляет 128 бит, ключ — 256 бит. Шифрование проходит в 12,5 раунда. Половина раунда относится к выходным преобразованиям[11].

Раундовые преобразования

править

Обозначим входную информацию для  -го раунда:
 

Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На чётных и нечётных раундах перемешивание происходит по-разному:

  • Для нечётных раундов:

 
 

  • Для чётных раундов:

 
 

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
 

МА-вычисления описываются следующими формулами:
 
 
 
 
 
 
 
 

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
 

Для получения зашифрованного сообщения необходимо после 12-го раунда провести перемешивание по нечетной схеме  [12]

Генерация ключей

править

Для генерации ключей используется 256-битный пользовательский ключ, а также 16-битные константы, такие же, как для MESH-64 и для MESH-96.

Вычисление подключей происходит следующим образом[13]:
 
 
 
где  .

Расшифровка

править

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
  — подключи полных раундов;
  — подключи выходных преобразований.

Тогда подключи расшифровки задаются следующим образом[14]:

  •  , - первый раунд расшифровки;
  •  , -  чётный раунд,  ;
  •  , -  нечётный раунд,  ;
  •  , — выходные преобразования.

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

править

Ниже приводится таблица, содержащая расчетную информацию по возможным криптоатакам. В ней рассматриваются урезанные алгоритмы, количество раундов можно увидеть в соответствующей колонке. За данные принимаются выбранные подобранные открытые тексты, указывается необходимое количество таковых (в блоках). Время оценивается в количестве вычислений. Память отражает количество ячеек памяти, необходимых для хранения каких-либо данных во время криптоатаки. Как видно из таблицы, все варианты MESH более сложны для взлома представленными криптоатаками, чем IDEA, на котором он основан[15][16].

Таблица 1. Обобщение сложностей криптоатак на IDEA и MESH[17]
Шифр Криптоанализ Раундов Данные Память Время
IDEA
(8,5 раундов)
Интегральный        
Усеченный дифф.        
Невозможный дифф.        
Невозможный дифф.        
MESH-64
(8,5 раундов)
Интегральный        
Усеченный дифф.        
Невозможный дифф.        
Невозможный дифф.        
MESH-96
(10,5 раундов)
Интегральный        
Усеченный дифф.        
Невозможный дифф.        
Невозможный дифф.        
MESH-128
(12,5 раундов)
Интегральный        
Усеченный дифф.        
Невозможный дифф.        
Невозможный дифф.        

Примечания

править

Литература

править