MESH (шифр)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
MESH
Создатель:

Накахара, Рэймен, Пренель, Вандевалле

Опубликован:

2002

Размер ключа:

128, 192, 256 бит

Размер блока:

64, 96, 128 бит

Число раундов:

8.5, 10.5, 12.5

Тип:

основан на IDEA, модификация Сети Фейстеля

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

Структура шифра[править | править код]

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

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

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

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

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

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

MESH-64[править | править код]

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

Раундовые преобразования[править | править код]

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

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

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

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

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

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


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

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

Генерация ключей[править | править код]

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

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



где .

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

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

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

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

MESH-96[править | править код]

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

Раундовые преобразования[править | править код]

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

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

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

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

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

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



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

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

Генерация ключей[править | править код]

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

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





где .

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

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

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

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

MESH-128[править | править код]

В данной вариации размер блока составляет 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 раундов)
Интегральный
Усеченный дифф.
Невозможный дифф.
Невозможный дифф.

Примечания[править | править код]

Литература[править | править код]