MESH (шифр)

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

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

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

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

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

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

• умножение по модулю $2^{16}+1$, причем вместо нуля используется $2^{16}$ ($\odot$)
• циклический сдвиг влево на $n$ бит ($⋘n$)
• сложение по модулю $2^{16}$ ($⊞$)
• побитовое исключающее ИЛИ ($\oplus$)

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

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

MESH-64

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

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

Обозначим входную информацию для $i$-го раунда:
$X^{(i)}=(X_1^{(i)},X_2^{(i)},X_3^{(i)},X_4^{(i)}),i=1...9$

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

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)})=(X_1^{(i)}\odot Z_1^{(i)},X_2^{(i)}⊞Z_2^{(i)},X_3^{(i)}⊞Z_3^{(i)},X_4^{(i)}\odot Z_4^{(i)})$

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)})=(X_1^{(i)}⊞Z_1^{(i)},X_2^{(i)}\odot Z_2^{(i)},X_3^{(i)}\odot Z_3^{(i)},X_4^{(i)}⊞Z_4^{(i)})$

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
$(Y_5^{(i)},Y_6^{(i)})=(Y_1^{(i)}\oplus Y_3^{(i)},Y_2^{(i)}\oplus Y_4^{(i)})$

МА-вычисления описываются следующими формулами:
$Y_7^{(i)}=((Y_5^{(i)}\odot Z_5^{(i)}⊞Y_6^{(i)})\odot Z_6^{(i)}⊞(Y_5^{(i)}\odot Z_5^{(i)}))\odot Z_7^{(i)}$
$Y_8^{(i)}=Y_7^{(i)}⊞((Y_5^{(i)}\odot Z_5^{(i)}⊞Y_6^{(i)})\odot Z_6^{(i)})$

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
$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)})$

Согласно схеме, для получения зашифрованного сообщения необходимо после восьмого раунда провести перемешивание по нечетной схеме $(i=9)$

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

Для генерации ключей используется 128-битный пользовательский ключ, а также 16-битные константы $c_i$: $c_0=1$, $c_i=3*c_{i-1}$, они вычисляются в Поле Галуа $GF(2^{16})$ по модулю многочлена $x^{16}+x^5+x^3+x^2+1$. Пользовательский ключ разбивается на 8 16-битных слов $K_i,0⩽i⩽7$.

Вычисление подключей происходит следующим образом:
$Z_{i+1}^{(1)}=K_i\oplus c_i,0⩽i⩽6$
$Z_1^{(2)}=K_7\oplus c_7$
$Z_{l(i)}^{(h(i))}=(((((Z_{l(i-8)}^{(h(i-8))}⊞Z_{l(i-7)}^{(h(i-7))})\oplus Z_{l(i-6)}^{(h(i-6))})⊞Z_{l(i-3)}^{(h(i-3))})\oplus Z_{l(i-2)}^{(h(i-2))})⊞Z_{l(i-1)}^{(h(i-1))})⋘7\oplus c_i,$
где $8⩽i⩽59,h(i)=idiv7+1,l(i)=imod7+1$.

Расшифровка

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
$(Z_1^{(r)},...,Z_7^{(r)}),1⩽r⩽8$ - подключи полных раундов;
$(Z_1^{(9)},...,Z_4^{(9)})$ - подключи выходных преобразований.

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

• $((Z_1^{(9)}{)}^{-1},-Z_2^{(9)},-Z_3^{(9)},(Z_4^{(9)}{)}^{-1},Z_5^{(8)},Z_6^{(8)},Z_7^{(8)})$, - первый раунд расшифровки;
• $(-Z_1^{(10-r)},(Z_3^{(10-r)}{)}^{-1},(Z_2^{(10-r)}{)}^{-1},-Z_4^{(10-r)},Z_5^{(9-r)},Z_6^{(9-r)},Z_7^{(9-r)})$, - $r$-й четный раунд, $r\in \{2,4,6,8\}$;
• $((Z_1^{(9-r)}{)}^{-1},-Z_3^{(9-r)},-Z_2^{(9-r)},(Z_4^{(9-r)}{)}^{-1},Z_5^{(8-r)},Z_6^{(8-r)},Z_7^{(8-r)})$, - $r$-й нечетный раунд, $r\in \{3,5,7\}$;
• $((Z_1^{(1)}{)}^{-1},-Z_2^{(1)},-Z_3^{(1)},(Z_4^{(1)}{)}^{-1})$, - выходные преобразования.

MESH-96

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

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

Обозначим входную информацию для $i$-го раунда:
$X^{(i)}=(X_1^{(i)},X_2^{(i)},X_3^{(i)},X_4^{(i)},X_5^{(i)},X_6^{(i)}),i=1...11$

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

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)},Y_5^{(i)},Y_6^{(i)})=(X_1^{(i)}\odot Z_1^{(i)},X_2^{(i)}⊞Z_2^{(i)},X_3^{(i)}\odot Z_3^{(i)},X_4^{(i)}⊞Z_4^{(i)},X_5^{(i)}\odot Z_5^{(i)},X_6^{(i)}⊞Z_6^{(i)})$

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)},Y_5^{(i)},Y_6^{(i)})=(X_1^{(i)}⊞Z_1^{(i)},X_2^{(i)}\odot Z_2^{(i)},X_3^{(i)}⊞Z_3^{(i)},X_4^{(i)}\odot Z_4^{(i)},X_5^{(i)}⊞Z_5^{(i)},X_6^{(i)}\odot Z_6^{(i)})$

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
$(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)})$

МА-вычисления описываются следующими формулами:
$Y_{10}^{(i)}=(((Y_7^{(i)}\odot Z_7^{(i)}⊞Y_8^{(i)})\odot Y_9^{(i)}⊞Z_8^{(i)})\odot (Y_7^{(i)}\odot Z_7^{(i)}⊞Y_8^{(i)})⊞Y_7^{(i)}\odot Z_7^{(i)})\odot Z_9^{(i)}$
$Y_{11}^{(i)}=Y_{10}^{(i)}⊞((Y_7^{(i)}\odot Z_7^{(i)}⊞Y_8^{(i)})\odot Y_9^{(i)}⊞Z_8^{(i)})\odot (Y_7^{(i)}\odot Z_7^{(i)}⊞Y_8^{(i)})$
$Y_{12}^{(i)}=Y_{11}^{(i)}\odot ((Y_7^{(i)}\odot Z_7^{(i)}⊞Y_8^{(i)})\odot Y_9^{(i)}⊞Z_8^{(i)})$

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
$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)})$

Для получения зашифрованного сообщения необходимо после 10-го раунда провести перемешивание по нечетной схеме $(i=9)$

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

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

Вычисление подключей происходит следующим образом:
$Z_{i+1}^{(1)}=K_i\oplus c_i,0⩽i⩽8$
$Z_1^{(2)}=K_9\oplus c_9$
$Z_2^{(2)}=K_{10}\oplus c_{10}$
$Z_3^{(2)}=K_{11}\oplus c_{11}$
$Z_{l(i)}^{(h(i))}=(((((Z_{l(i-12)}^{(h(i-12))}⊞Z_{l(i-8)}^{(h(i-8))})\oplus Z_{l(i-6)}^{(h(i-6))})⊞Z_{l(i-4)}^{(h(i-4))})\oplus Z_{l(i-2)}^{(h(i-2))})⊞Z_{l(i-1)}^{(h(i-1))})⋘9\oplus c_i,$
где $12⩽i⩽95,h(i)=idiv9+1,l(i)=imod9+1$.

Расшифровка

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
$(Z_1^{(r)},...,Z_9^{(r)}),1⩽r⩽10$ — подключи полных раундов;
$(Z_1^{(11)},...,Z_6^{(11)})$ - подключи выходных преобразований.

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

• $((Z_1^{(11)}{)}^{-1},-Z_2^{(11)},(Z_3^{(11)}{)}^{-1},-Z_4^{(11)},(Z_5^{(11)}{)}^{-1},-Z_6^{(11)},Z_7^{(10)},Z_8^{(10)},Z_9^{(10)})$, — первый раунд расшифровки;
• $(-Z_1^{(12-r)},(Z_4^{(12-r)}{)}^{-1},-Z_5^{(12-r)},(Z_2^{(12-r)}{)}^{-1},-Z_3^{(12-r)},(Z_6^{(12-r)}{)}^{-1},Z_7^{(11-r)},Z_8^{(11-r)},Z_9^{(11-r)})$, — $r$-й чётный раунд, $r\in \{2,4,6,8,10\}$;
• $((Z_1^{(11-r)}{)}^{-1},-Z_4^{(11-r)},(Z_5^{(11-r)}{)}^{-1},-Z_2^{(11-r)},(Z_3^{(11-r)}{)}^{-1},-Z_6^{(11-r)},Z_7^{(10-r)},Z_8^{(10-r)},Z_9^{(10-r)})$, — $r$-й нечётный раунд, $r\in \{3,5,7,9\}$;
• $((Z_1^{(1)}{)}^{-1},-Z_2^{(1)},(Z_3^{(1)}{)}^{-1},-Z_4^{(1)},(Z_5^{(1)}{)}^{-1},-Z_6^{(1)})$, — выходные преобразования.

MESH-128

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

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

Обозначим входную информацию для $i$-го раунда:
$X^{(i)}=(X_1^{(i)},X_2^{(i)},X_3^{(i)},X_4^{(i)},X_5^{(i)},X_6^{(i)},X_7^{(i)},X_8^{(i)}),i=1...13$

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

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)},Y_5^{(i)},Y_6^{(i)},Y_7^{(i)},Y_8^{(i)})=$
$(X_1^{(i)}\odot Z_1^{(i)},X_2^{(i)}⊞Z_2^{(i)},X_3^{(i)}\odot Z_3^{(i)},X_4^{(i)}⊞Z_4^{(i)},X_5^{(i)}\odot Z_5^{(i)},X_6^{(i)}⊞Z_6^{(i)},X_7^{(i)}\odot Z_7^{(i)},X_8^{(i)}⊞Z_8^{(i)})$

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

$(Y_1^{(i)},Y_2^{(i)},Y_3^{(i)},Y_4^{(i)},Y_5^{(i)},Y_6^{(i)},Y_7^{(i)},Y_8^{(i)})=$
$(X_1^{(i)}⊞Z_1^{(i)},X_2^{(i)}\odot Z_2^{(i)},X_3^{(i)}⊞Z_3^{(i)},X_4^{(i)}\odot Z_4^{(i)},X_5^{(i)}⊞Z_5^{(i)},X_6^{(i)}\odot Z_6^{(i)},X_7^{(i)}⊞Z_7^{(i)},X_8^{(i)}\odot Z_8^{(i)})$

Преобразования, выполняемые MA-боксами, одинаковы для всех раундов. Входные данные для них получаются следующим образом:
$(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)})$

МА-вычисления описываются следующими формулами:
$Y_{13}^{(i)}=Y_9^{(i)}\odot Z_9^{(i)},Y_{14}^{(i)}=Y_{13}^{(i)}⊞Y_{10}^{(i)},$
$Y_{15}^{(i)}=Y_{14}^{(i)}\odot Y_{11}^{(i)},Y_{16}^{(i)}=Y_{15}^{(i)}⊞Y_{12}^{(i)},$
$Y_{17}^{(i)}=Y_{16}^{(i)}\odot Z_{10}^{(i)},Y_{18}^{(i)}=Y_{15}^{(i)}⊞Y_{17}^{(i)},$
$Y_{19}^{(i)}=Y_{14}^{(i)}\odot Y_{18}^{(i)},Y_{20}^{(i)}=Y_{13}^{(i)}⊞Y_{19}^{(i)},$
$Y_{21}^{(i)}=Y_{20}^{(i)}\odot Z_{11}^{(i)},Y_{22}^{(i)}=Y_{19}^{(i)}⊞Y_{21}^{(i)},$
$Y_{23}^{(i)}=Y_{18}^{(i)}\odot Y_{22}^{(i)},Y_{24}^{(i)}=Y_{17}^{(i)}⊞Y_{23}^{(i)},$
$Y_{25}^{(i)}=Y_{24}^{(i)}\odot Z_{12}^{(i)},Y_{26}^{(i)}=Y_{23}^{(i)}⊞Y_{25}^{(i)},$
$Y_{27}^{(i)}=Y_{22}^{(i)}\odot Y_{26}^{(i)},Y_{28}^{(i)}=Y_{21}^{(i)}⊞Y_{27}^{(i)}.$

Используя результаты, полученные MA-боксами, находим входные данные для следующего раунда:
$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)})$

Для получения зашифрованного сообщения необходимо после 12-го раунда провести перемешивание по нечетной схеме $(i=9)$

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

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

Вычисление подключей происходит следующим образом:
$Z_{i+1}^{(1)}=K_i\oplus c_i,0⩽i⩽11$
$Z_{jmod12+1}^{(2)}=K_j\oplus c_j,12⩽j⩽15$
$Z_{l(i)}^{(h(i))}=(((((Z_{l(i-16)}^{(h(i-16))}⊞Z_{l(i-13)}^{(h(i-13))})\oplus Z_{l(i-12)}^{(h(i-12))})⊞Z_{l(i-8)}^{(h(i-8))})\oplus Z_{l(i-2)}^{(h(i-2))})⊞Z_{l(i-1)}^{(h(i-1))})⋘11\oplus c_i,$
где $16⩽i⩽151,h(i)=idiv12+1,l(i)=imod12+1$.

Расшифровка

Для расшифровки MESH, как и IDEA, использует уже существующую схему, но с измененными раундовыми подключами. Обозначим подключи, использовавшиеся при шифровании, следующим образом:
$(Z_1^{(r)},...,Z_{12}^{(r)}),1⩽r⩽12$ — подключи полных раундов;
$(Z_1^{(13)},...,Z_8^{(13)})$ — подключи выходных преобразований.

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

• $((Z_1^{(13)}{)}^{-1},-Z_2^{(13)},(Z_3^{(13)}{)}^{-1},-Z_4^{(13)},-Z_5^{(13)},(Z_6^{(13)}{)}^{-1},-Z_7^{(13)},(Z_8^{(13)}{)}^{-1},Z_9^{(12)},Z_{10}^{(12)},Z_{11}^{(12)},Z_{12}^{(12)})$, - первый раунд расшифровки;
• $(-Z_1^{(14-r)},(Z_5^{(14-r)}{)}^{-1},-Z_6^{(14-r)},(Z_7^{(14-r)}{)}^{-1},(Z_2^{(14-r)}{)}^{-1},-Z_3^{(14-r)},(Z_4^{(14-r)}{)}^{-1},-Z_8^{(14-r)},Z_9^{(13-r)},Z_{10}^{(13-r)},Z_{11}^{(13-r)},Z_{12}^{(13-r)})$, - $r$-й чётный раунд, $r\in \{2,4,6,8,10,12\}$;
• $((Z_1^{(13-r)}{)}^{-1},-Z_5^{(13-r)},(Z_6^{(13-r)}{)}^{-1},-Z_7^{(13-r)},-Z_2^{(13-r)},(-Z_3^{(13-r)}{)}^{-1},-Z_4^{(13-r)},(Z_8^{(13-r)}{)}^{-1},Z_9^{(12-r)},Z_{10}^{(12-r)},Z_{11}^{(12-r)},Z_{12}^{(12-r)})$, - $r$-й нечётный раунд, $r\in \{3,5,7,9,11\}$;
• $((Z_1^{(1)}{)}^{-1},-Z_2^{(1)},(Z_3^{(1)}{)}^{-1},-Z_4^{(1)},-Z_5^{(1)},(Z_6^{(1)}{)}^{-1},-Z_7^{(1)},(Z_8^{(1)}{)}^{-1})$, — выходные преобразования.

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

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

Таблица 1. Обобщение сложностей криптоатак на IDEA и MESH

Шифр	Криптоанализ	Раундов	Данные	Память	Время
IDEA (8,5 раундов)	Интегральный	$2.5$	$23$	$23$	$2^{64}$
	Усеченный дифф.	$3.5$	$2^{56}$	$2^{32}$	$2^{67}$
	Невозможный дифф.	$3.5$	$2^{38.5}$	$2^{37}$	$2^{53}$
	Невозможный дифф.	$4$	$2^{38.5}$	$2^{37}$	$2^{70}$
MESH-64 (8,5 раундов)	Интегральный	$2.5$	$2^{50.5}$	$2^{16}$	$2^{76}$
	Усеченный дифф.	$3.5$	$2^{64}$	$2^{32}$	$2^{78}$
	Невозможный дифф.	$3.5$	$2^{39.5}$	$2^{61}$	$2^{64}$
	Невозможный дифф.	$4$	$2^{39.5}$	$2^{61}$	$2^{112}$
MESH-96 (10,5 раундов)	Интегральный	$2.5$	$2^{50}$	$2^{16}$	$2^{96}$
	Усеченный дифф.	$3.5$	$2^{96}$	$2^{64}$	$2^{109}$
	Невозможный дифф.	$3.5$	$2^{56}$	$2^{93}$	$2^{96}$
	Невозможный дифф.	$4$	$2^{56}$	$2^{93}$	$2^{144}$
MESH-128 (12,5 раундов)	Интегральный	$2.5$	$2^{50}$	$2^{16}$	$2^{128}$
	Усеченный дифф.	$3.5$	$2^{128}$	$2^{64}$	$2^{142}$
	Невозможный дифф.	$3.5$	$2^{65}$	$2^{157}$	$2^{128}$
	Невозможный дифф.	$4$	$2^{65}$	$2^{157}$	$2^{192}$

Литература

• J. Nakahara, Jr.; V. Rijmen; B. Preneel; J. Vandewalle. The MESH Block Ciphers (англ.). — 2002.
• J. Nakahara, Jr. Cryptanalysis And Design Of Block Ciphers (англ.). — 2003. — Июнь. — ISBN 90-5682-407-4.