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].
В данной вариации размер блока составляет 64 бит, ключ — 128 бит. Шифрование проходит в 8,5 раунда. Половина раунда относится к выходным преобразованиям[3].
Обозначим входную информацию для
-го раунда:
Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На четных и нечетных раундах перемешивание происходит по-разному:
Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
![{\displaystyle (Y_{5}^{(i)},\ Y_{6}^{(i)})\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{3}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{4}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c88d8fc244de7f3332fe84a7a9d6a702da3bd409)
МА-вычисления описываются следующими формулами:
![{\displaystyle Y_{8}^{(i)}\ =\ Y_{7}^{(i)}\ \boxplus \ ((Y_{5}^{(i)}\ \odot \ Z_{5}^{(i)}\ \boxplus \ Y_{6}^{(i)})\ \odot \ Z_{6}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ba7ae30f74846d6831d142410cd50d114d3142)
Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
![{\displaystyle X^{(i+1)}\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{8}^{(i)},\ Y_{3}^{(i)}\ \oplus \ Y_{8}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{7}^{(i)},\ Y_{4}^{(i)}\ \oplus \ Y_{7}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c1d87835cdc3c75b96484c11c72047ea0f0b013)
Согласно схеме, для получения зашифрованного сообщения необходимо после восьмого раунда провести перемешивание по нечетной схеме
[4]
Для генерации ключей используется 128-битный пользовательский ключ, а также 16-битные константы
:
,
, они вычисляются в Поле Галуа
по модулю многочлена
. Пользовательский ключ разбивается на 8 16-битных слов
.
Вычисление подключей происходит следующим образом[5]:
где
.
Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
- подключи полных раундов;
- подключи выходных преобразований.
Тогда подключи расшифровки задаются следующим образом[6]:
, - первый раунд расшифровки;
, -
-й четный раунд,
;
, -
-й нечетный раунд,
;
, - выходные преобразования.
В данной вариации размер блока составляет 96 бит, ключ — 192 бит. Шифрование проходит в 10,5 раунда. Половина раунда относится к выходным преобразованиям[7].
Обозначим входную информацию для
-го раунда:
Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На четных и нечетных раундах перемешивание происходит по-разному:
Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
![{\displaystyle (Y_{7}^{(i)},\ Y_{8}^{(i)},\ Y_{9}^{(i)})\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{4}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{5}^{(i)},\ Y_{3}^{(i)}\ \oplus \ Y_{6}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e2a4bb76bad40cd4bf6323635df6729384ade9a)
МА-вычисления описываются следующими формулами:
![{\displaystyle Y_{12}^{(i)}\ =\ Y_{11}^{(i)}\ \odot \ ((Y_{7}^{(i)}\ \odot \ Z_{7}^{(i)}\ \boxplus \ Y_{8}^{(i)})\ \odot \ Y_{9}^{(i)}\ \boxplus \ Z_{8}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6aa9b1016102fc9140d93df984e7714827897cd)
Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
![{\displaystyle X^{(i+1)}\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{12}^{(i)},\ Y_{4}^{(i)}\ \oplus \ Y_{12}^{(i)},\ Y_{5}^{(i)}\ \oplus \ Y_{11}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{11}^{(i)},\ Y_{3}^{(i)}\ \oplus \ Y_{10}^{(i)},\ Y_{6}^{(i)}\ \oplus \ Y_{10}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/160ff35d58487bc4289086c5ba219d79e45070b8)
Для получения зашифрованного сообщения необходимо после 10-го раунда провести перемешивание по нечетной схеме
[8]
Для генерации ключей используется 192-битный пользовательский ключ, а также 16-битные константы, такие же, как и для MESH-64.
Вычисление подключей происходит следующим образом[9]:
где
.
Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
— подключи полных раундов;
- подключи выходных преобразований.
Тогда подключи расшифровки задаются следующим образом[10]:
, — первый раунд расшифровки;
, —
-й чётный раунд,
;
, —
-й нечётный раунд,
;
, — выходные преобразования.
В данной вариации размер блока составляет 128 бит, ключ — 256 бит. Шифрование проходит в 12,5 раунда. Половина раунда относится к выходным преобразованиям[11].
Обозначим входную информацию для
-го раунда:
Каждый раунд состоит из двух частей: перемешивание входных данных с подключами и MA-вычисления. На чётных и нечётных раундах перемешивание происходит по-разному:
Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
![{\displaystyle (Y_{9}^{(i)},\ Y_{10}^{(i)},\ Y_{11}^{(i)},\ Y_{12}^{(i)})\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{5}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{6}^{(i)},\ Y_{3}^{(i)}\ \oplus \ Y_{7}^{(i)},\ Y_{4}^{(i)}\ \oplus \ Y_{8}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f55216f97d69820d5b265a77ad70e22cc79cdbe2)
МА-вычисления описываются следующими формулами:
Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
![{\displaystyle X^{(i+1)}\ =\ (Y_{1}^{(i)}\ \oplus \ Y_{25}^{(i)},\ Y_{5}^{(i)}\ \oplus \ Y_{25}^{(i)},\ Y_{6}^{(i)}\ \oplus \ Y_{26}^{(i)},\ Y_{7}^{(i)}\ \oplus \ Y_{27}^{(i)},\ Y_{2}^{(i)}\ \oplus \ Y_{26}^{(i)},\ Y_{3}^{(i)}\ \oplus \ Y_{27}^{(i)},\ Y_{4}^{(i)}\ \oplus \ Y_{28}^{(i)},\ Y_{8}^{(i)}\ \oplus \ Y_{28}^{(i)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f7456ef94f422bce41674e35a2c22e3e226037a)
Для получения зашифрованного сообщения необходимо после 12-го раунда провести перемешивание по нечетной схеме
[12]
Для генерации ключей используется 256-битный пользовательский ключ, а также 16-битные константы, такие же, как для MESH-64 и для MESH-96.
Вычисление подключей происходит следующим образом[13]:
где
.
Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
— подключи полных раундов;
— подключи выходных преобразований.
Тогда подключи расшифровки задаются следующим образом[14]:
, - первый раунд расшифровки;
, -
-й чётный раунд,
;
, -
-й нечётный раунд,
;
, — выходные преобразования.
Ниже приводится таблица, содержащая расчетную информацию по возможным криптоатакам. В ней рассматриваются урезанные алгоритмы, количество раундов можно увидеть в соответствующей колонке. За данные принимаются выбранные подобранные открытые тексты, указывается необходимое количество таковых (в блоках). Время оценивается в количестве вычислений. Память отражает количество ячеек памяти, необходимых для хранения каких-либо данных во время криптоатаки. Как видно из таблицы, все варианты MESH более сложны для взлома представленными криптоатаками, чем IDEA, на котором он основан[15][16].
Таблица 1. Обобщение сложностей криптоатак на IDEA и MESH[17]
Шифр |
Криптоанализ |
Раундов |
Данные |
Память |
Время
|
IDEA (8,5 раундов) |
Интегральный |
![{\displaystyle 2.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb8bc46f7639b6020d61267cb92a9d169cf25ce) |
![{\displaystyle 23}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e140641068b3a0763290941fb20531be45227748) |
![{\displaystyle 23}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e140641068b3a0763290941fb20531be45227748) |
|
Усеченный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{56}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73127c7e21fe4373a88ac7c570b944a2e05e3470) |
![{\displaystyle 2^{32}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633) |
|
Невозможный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{38.5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b527285cbcd5278f4b9305b8cfc4d378100e088) |
![{\displaystyle 2^{37}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a707aa5c7d43866b55347b8979b14002df59ae0b) |
|
Невозможный дифф. |
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 2^{38.5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b527285cbcd5278f4b9305b8cfc4d378100e088) |
![{\displaystyle 2^{37}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a707aa5c7d43866b55347b8979b14002df59ae0b) |
|
MESH-64 (8,5 раундов) |
Интегральный |
![{\displaystyle 2.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb8bc46f7639b6020d61267cb92a9d169cf25ce) |
![{\displaystyle 2^{50.5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddf38e0a6b499766de5d96132e51753a6280187d) |
![{\displaystyle 2^{16}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e0dd3c0e42794174d2dbcb9a3ee2c6d69299d4) |
|
Усеченный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{64}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecfb4b886be67f9e99c7fdfecc364be7ba3cc7f9) |
![{\displaystyle 2^{32}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c222ea8e5f187a2bb499395b6f4a6f38b43633) |
|
Невозможный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{39.5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8df31a1405cec4f552717b4fa0f0ff478929ddf1) |
![{\displaystyle 2^{61}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/143a7a52490a72ba115778badbafe1b70db16931) |
|
Невозможный дифф. |
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 2^{39.5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8df31a1405cec4f552717b4fa0f0ff478929ddf1) |
![{\displaystyle 2^{61}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/143a7a52490a72ba115778badbafe1b70db16931) |
|
MESH-96 (10,5 раундов) |
Интегральный |
![{\displaystyle 2.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb8bc46f7639b6020d61267cb92a9d169cf25ce) |
![{\displaystyle 2^{50}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1663c54d80d2efca3724b7fcb7625e37555e2fb5) |
![{\displaystyle 2^{16}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e0dd3c0e42794174d2dbcb9a3ee2c6d69299d4) |
|
Усеченный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{96}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63e05230c1b6d1041560a57c2defb8adf83c33af) |
![{\displaystyle 2^{64}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecfb4b886be67f9e99c7fdfecc364be7ba3cc7f9) |
|
Невозможный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{56}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73127c7e21fe4373a88ac7c570b944a2e05e3470) |
![{\displaystyle 2^{93}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2de90139393252f5443b7d40cac33f8b92a5240) |
|
Невозможный дифф. |
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 2^{56}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73127c7e21fe4373a88ac7c570b944a2e05e3470) |
![{\displaystyle 2^{93}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2de90139393252f5443b7d40cac33f8b92a5240) |
|
MESH-128 (12,5 раундов) |
Интегральный |
![{\displaystyle 2.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/adb8bc46f7639b6020d61267cb92a9d169cf25ce) |
![{\displaystyle 2^{50}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1663c54d80d2efca3724b7fcb7625e37555e2fb5) |
![{\displaystyle 2^{16}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e0dd3c0e42794174d2dbcb9a3ee2c6d69299d4) |
|
Усеченный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{128}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/759062fdace390ded4a751eeff7689d2883995cd) |
![{\displaystyle 2^{64}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecfb4b886be67f9e99c7fdfecc364be7ba3cc7f9) |
|
Невозможный дифф. |
![{\displaystyle 3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26c8808dbfe434180b031ceef0418f5f1bc4f1a7) |
![{\displaystyle 2^{65}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f34f8a4ecaf55c11524a7e4d66398c0ee13c2b8) |
![{\displaystyle 2^{157}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/476355eba855108f8d79d282868e862bb43f8d61) |
|
Невозможный дифф. |
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 2^{65}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f34f8a4ecaf55c11524a7e4d66398c0ee13c2b8) |
![{\displaystyle 2^{157}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/476355eba855108f8d79d282868e862bb43f8d61) |
|
- ↑ The MESH Block Ciphers, 2002, p. 1-2.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 124.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 125.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 125-126.
- ↑ The MESH Block Ciphers, 2002, p. 3.
- ↑ The MESH Block Ciphers, 2002, p. 4.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 127.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 127-129.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 129.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 129-130.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 130.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 130-132.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 132.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 132-133.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 10-11.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 178-180.
- ↑ Cryptanalysis And Design Of Block Ciphers, 2003, p. 179.