В 2017 году российской компанией КриптоПро был предложен новый AEAD режим шифрования Multilinear Galois Mode (MGM). Спустя некоторое время он был принят в российские и международные стандарты. Так как в интернете я смог найти только общее описание работы этого режима шифрования без конкретной реализации (ссылки в конце статьи), то я решил попробовать свои силы и реализовать очень упрощённую версию своими руками...

Для начала разберёмся со вспомогательными, но важными для понимания вещами.

Шифрование vs режим шифрования

Шифрование - это отображение вида $E: P \times K \rightarrow C$ , которое осуществляет преобразование открытого текста P в шифротекст С с иcпользованием ключа шифрования K. Примером такого отображения может служить "шифр Цезаря", о котором можно почитать в Википедии.

Режим шифрования - это подход к шифрованию открытого текста P, при котором он разбивается на блоки текста заведомо фиксированной длины. Далее каждый блок шифруется некоторым отображением E_k (ключ К - общий и заранее выбран), а потом они собираются обратно вместе в шифротекст С.

AEAD-режим блочного шифрования

AEAD - это класс блочных режимов шифрования, при котором часть сообщения шифруется, часть остается открытой, и всё сообщение целиком аутентифицировано. Иными словами, если, например, проводить аналогию с почтовыми письмами, то внутренность письма вы шифруете (запечатываете), адрес отправителя и адрес получателя оставляете снаружи конверта (не зашифрованными), чтобы почтовые службы смогли корректно обработать ваше письмо, и ещё дополнительно вы делаете приписку, с помощью которой получатель сможет проверить (аутентифицировать), что все данные как внутри, так и снаружи письма были сохранены.

Арифметика полей Галуа GF(2^n)

Арифметика полей Галуа встречается повсеместно в криптографии, и понимание принципов её работы в программном коде необходимо. Режим шифрования AEAD-MGM от чисел из полей Галуа GF(2ⁿ) требует реализации только 2 операций - сложения $(\oplus)$ и умножения $(\otimes)$ .

Примеры, которые приводятся дальше в этой части, я взял из вспомогательной статьи.

Она рекомендуется к прочтению, чтобы сложить более полное понимание об арифметике полей Галуа GF(2ⁿ).

Теперь перейдём к реализации. Для начала определим класс чисел в полях Галуа GF(2ⁿ):

// Galois Field Number
// для удобства показа идей и реализации тип uint32_t выбран специально
class Number
{
public:
	Number():
		value(0)
	{}
	Number(uint32_t value_):
		value(value_)
	{}

	operator uint32_t() const
	{ return value; }

public:
	friend Number operator+(Number left, Number right);
	friend Number operator*(Number left, Number right);

public:
	friend std::ostream& operator<<(std::ostream& os, Number number)
	{ return os << number.value; }

public:
	uint32_t value;
};

Теперь определим операцию сложения в поле GF(2ⁿ), которая по сути своей является обычной побитовой операцией XOR:

class Number
{ ... }

Number operator+(Number left, Number right)
{ return left.value ^ right.value; }

(операция в полях GF(2ⁿ) также является побитовой операцией XOR)

Чтобы определить операцию умножения , нам сначала нужно понять, как отличие в операции влияет на неё. Из школы нам известен алгоритм умножения в столбик:

$\begin{array}{r} \times \begin{array}{r} 17\\ 25\\ \end{array} \\ \hline + \begin{array}{r} 85\\ 340\\ \end{array}\\ \hline \begin{array}{r} 425\\ \end{array} \end{array}$

Как мы видим, операцию мы здесь применяем для того, чтобы сложить два промежуточных результата от умножения 17 на 5, и 17 на 20. Если представить число 25 как 25 = 2 * 10^1 + 5 * 10^0 , то становится видно, что операция используется для сложения результатов умножения числа 17 на числа при разных степенях 10. Если мы применим теперь наши рассуждения для разложений чисел по основанию 2, то результат не изменится.

$\begin{array}{r} \times \begin{array}{r} 111(7)\\ 101(5)\\ \end{array} \\ \hline + \begin{array}{r} 111(7) \\ 0000(0) \\ 11100(28) \\ \end{array} \\ \hline \begin{array}{r} 100011(35) \\ \end{array} \end{array}$

5 = 1*2^2 + 0*2^1 +1*2^0

Теперь, вспоминая что в полях GF(2ⁿ) является XOR, получим

$\begin{array}{r} \otimes \begin{array}{r} 111\\ 101\\ \end{array} \\ \hline \oplus \begin{array}{r} 00111 \\ 00000 \\ 11100 \\ \end{array} \\ \hline \begin{array}{r} 11011 \\ \end{array} \end{array}$

Или $7 \otimes 5 = 7*2^2 \oplus 7 = 28 \oplus 7= 27$

Таким образом получаем первую часть нашего метода умножения в полях GF(2ⁿ):

// возвращаемый тип uint64_t потому, что
// если a < 2^32 и b < 2^32, то a * b < 2^(32 + 32) = 2^64, но не 2^32
uint64_t MulMod2(uint32_t left, uint32_t right)
{
	uint64_t result = 0;
	uint64_t offset = 0;
	while(right)
	{
		if (right & 1)
			result ^= left << offset;
		++offset;
		right >>= 1;
	}
	return result;
}

Замечу, что если мы хотим перемножать числа, которые не помещаются в машинное слово процессора (например, 128 разрядные), то нам стоит немного переписать этот метод. На этот раз мы будем раскладывать не только правое число, но и левое, суммируя по модулю 2 кол-во единиц при одинаковой степени 2.

$\begin{array}{} 7 = 1 * 2^2 \oplus 1 * 2^1 \oplus 1 * 2^0\\ 5=1*2^2 \oplus0*2^1\oplus1*2^0\\ 2^0: 1*1=1\\ 2^1:1*1\oplus1*0=1\\ 2^2:1*1\oplus1*0\oplus1*1=0\\ 2^3:1*0\oplus 1*1=1\\ 2^4: 1*1 = 1\\ 2^4 + 2^3+2^1+2^0=27\end{array}$

// uint128_t - некий абстрактный целочисленный тип содержащий 128 бит
// uint256_t - 256 бит
bool testbit(uint256_t value, size_t offset)
{ return value & (1 << offset); }

void setbit(uint256_t& value, size_t offset)
{ value |= 1 << offset; }

uint256_t MulMod2(uint128_t left, uint128_t right)
{
	uint256_t result = 0;
	for(size_t k = 0; k < 256; ++k)
	{
		size_t sum = 0;
		for(size_t i = 0, j = k; i <= k; ++i, --j)
		{
			if (testbit(left, i) && testbit(right, j))
				sum ^= 1;
		}
		if (sum)
			setbit(result, k);
	}
	return result;
}

Операции используемые здесь проще в реализации и легче проверяются.

Вторая часть операции умножения в полях Галуа заключается в том, чтобы как бы "вместить обратно" число, полученное от MulMod2 в интервал [1, 2ⁿ). Для этого вводится специальный порождающий многочлен - число в интервале [2ⁿ, 2ⁿ + 2ⁿ), на которое мы делим результат от MulMod2. Полученное при этом число будет лежать в интервале [1, 2ⁿ).

Об остатке от деления

Из школьной программы мы знаем, что для обычной арифметики остаток от деления на число m лежит в интервале [0, m). Почему же тогда арифметика в полях Галуа GF(2ⁿ) для порождающего многочлена (2ⁿ + x), 0 < x < 2ⁿ не даёт нам получить остаток (2ⁿ + y), 0 < y < 2ⁿ?

Ответ тут в том, что если бы мы получили остаток (2ⁿ + y), то тогда мы бы смогли бы применить следующую операцию

$(2^n+y) \oplus (2^n + x) = y \oplus x=z$

Так как 0 < x < 2ⁿ и 0 < y < 2ⁿ, а операция XOR сохраняет количество разрядов в числе, то z будет принадлежать интервалу [0, 2ⁿ). Так как 0 не встречается, то его отбрасываем, получая интервал [1, 2ⁿ). По итогу остаток (2ⁿ + y) преобразовался в остаток z, который принадлежит интервалу [1, 2ⁿ), а это противоречит предположению, что мы можем получить остаток (2ⁿ + y)

Вспомним школьное деление столбиком

Если это переписать в немного другом виде, то получится

$\begin{array}{c} 1300/12=13/12*10^2=1*10^2=100 \ (1*10^2 \ \text{в остатке}) \\ 100 + 50=150/12=15/12*10^1=1*10^1=10 \ (3*10^1 \ \text{в остатке}) \\ 30+0=30/12=30/12*10^0=2*10^0=2\ (6*10^0 \ \text{в остатке}) \\ 100+10+2=112 \ (6 \ \text{в остатке}) \end{array}$

Остатки всегда должны быть меньше 12 * 10^x, а результаты делений 13/12, 15/12, 30/12 должны лежать в интервале [0, 10), так как 10 - основание системы счисления.

В двоичной системе счисления происходит всё то же самое:

$\begin{array}{c} 11010_2/1011_2= 1101_2/1011_2 * 10_2=1*10_2=10_2 \ (100_2 \ \text{в остатке}) \\ 100_2 + 001_2 = 101_2/1011_2=0 \ (101_2 \ \text{в остатке}) \end{array}$

Теперь посмотрим на то же самое деление в столбик, если мы заменим на $\oplus$

Проверим, что полученный нами ответ удовлетворяет MulMod2

$\begin{array}{r} \otimes \begin{array}{r} 1011\\ 11\\ \end{array} \\ \hline \oplus \begin{array}{r} 01011 \\ 10110 \\ \end{array} \\ \hline \oplus \begin{array}{r} 11101 \\ 00110 \\ \end{array} \\ \hline \begin{array}{r} 11011 \end{array} \end{array}$ $\begin{array}{c} 1011_2 \otimes 11_2=11101_2 \oplus 110_2 = 11011_2 \\ 11_{10} \otimes 3_{10}=29_{10} \oplus 6_{10} = 27_{10} \end{array}$

Как видно, наш подход к делению оказался верным. Осталось только реализовать это в коде.

Для реализации воспользуемся тем свойством алгебры полей Галуа GF(2ⁿ), что если есть два числа

$\begin{array}{c} a = 2^n +x \ (0 < x < 2^n) \\ b=2^m+y \ (0 < y< 2^m) \\ n \geqslant m \end{array}$

то мы можем ввести

$\begin{array}{c} q = 2^{n-m} \\ b^*=b*q=2^n+y*2^{n-m} \ (0 < y * 2^{n - m} < 2^n) \\ a \oplus b^*=(2^n+x)\oplus(2^n+y*2^{n-m})=x \oplus y*2^{n-m} < 2^n\end{array}$

Если сравнить это с делением столбиком, то а - делимое, b - делитель, q - бит, который мы должны записать в частное, $a \oplus b^*$ - промежуточный результат для следующей итерации... Как только $a \oplus b^*$ станет меньше b, мы должны вернуть остаток. Итого код получается следующим:

size_t maxbit(uint64_t value)
{
	size_t retval = 0;
	while(value)
	{ value >>= 1; ++retval; }
	return retval;
}

uint32_t ModGenP(uint64_t value, uint64_t gen_polynom)
{
	while (true)
	{
		size_t vmaxbit = maxbit(value);
		size_t pmaxbit = maxbit(gen_polynom);
		
		if (vmaxbit < pmaxbit)
			return (uint32_t) value;
		
		size_t quotient = 1 << (vmaxbit - pmaxbit);
		value ^= gen_polynom * quotient;
	}
}

Теперь совмещая всё вместе, получим итоговый код для операции умножения в полях Галуа GF(2ⁿ):

class Number { ... }

Number operator*(Number left, Number right)
{
  // порождающий полином: x^32 + x^22 + x^2 + x^1 + 1
	uint64_t gen_p = (1ULL << 32) + (1 << 22) + (1 << 2) + (1 << 1) + 1;
	uint64_t value = MulMod2(left.value, right.value);
	return ModGenP(value, gen_p);
}

AEAD-MGM

Теперь, разобравшись со всеми сложными, но важными моментами, мы готовы перейти к процессу шифрования AEAD-MGM...

Основной файл с описанием, на который я буду опираться, можно найти здесь:

По сути процесс шифрования представляет собой:

Генерацию nonce (уникального для каждого обмена сообщениями)
Генерацию $(0 \ || \ nonce)$ и $(1 \ || \ nonce)$
Генерацию массивов Y, Z, H.
Деление входных данных (A и P) на блоки выбранного нами размера (32 бита)
Преобразование $P \rightarrow C$ и генерацию имитовставки Т

Для упрощения реализации в коде будем считать, что

P = N блоков по 32 бита информации в каждом
A = M блоков по 32 бита информации в каждом
Максимальный размер сообщений $max|P| = max|A|=2^{16}$

Доопределим incr_l, incr_r и ещё несколько вспомогательных функций:

uint32_t incr_l(uint32_t input)
{
    uint16_t L = (input & 0xffff0000) >> 16;
    uint16_t R = (input & 0x0000ffff);
    
    ++L;
    
    return (L << 16) + R;
}

uint32_t incr_r(uint32_t input)
{
    uint16_t L = (input & 0xffff0000) >> 16;
    uint16_t R = (input & 0x0000ffff);
    
    ++R;
    
    return (L << 16) + R;
}

uint32_t MSB(uint32_t number, size_t size)
{ return number & (0xffffffff - ((1 << size) - 1)); }

// nonce - одноразовый вспомогательный вектор, который должен быть
// уникальным для каждого обмена сообщениями. Его длина должна быть (N - 1),
// т.е. в нашем случае (32 - 1) = 31 бит. В рекомендациях предлагается его 
// генерация на основе счётчика, но, так как мы хотим использовать его только 1 раз,
// то возьмём просто какое-то подходящее значение.
constexpr uint32_t nonce()
{
  return 0x5678; // 0x5 = 0101 (первый бит не используется)
}

constexpr uint32_t Get0orN()
{ return (0 << 31) + nonce(); }

constexpr uint32_t Get1orN()
{ return (1 << 31) + nonce(); }

// Функция шифрования E_k. Для простоты реализации мы ничего не шифруем.
uint32_t Еncrypt(uint32_t input)
{
    return input;
}

// функции заполнения массивов Y, Z, H
void FillY(Number* Y, size_t count)
{
    Y[0] = Shifr(Get0orN());
    for(size_t i = 1; i < count; ++i)
        Y[i] = incr_r(Y[i - 1]);
}

void FillZ(Number* Z, size_t count)
{
    Z[0] = Shifr(Get1orN());
    for(size_t i = 1; i < count; ++i)
        Z[i] = incr_l(Z[i - 1]);
}

void FillH(Number* H, Number* Z, size_t count)
{
    for(size_t i = 0; i < count; ++i)
        H[i] = Shifr(Z[i]);
}

Ну и наконец сам алгоритм:

int main()
{
	constexpr size_t N = 10;
	constexpr size_t M = 10;
	
	Number Y[N];
	Number Z[N + M + 1];
	
	FillY(Y, N);
	FillZ(Z, N + M + 1);
	
	Number P[N] = {0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0x10};
	Number C[N];
	
	for(size_t i = 0; i < N; ++i)
		C[i] = Number(Shifr(Y[i])) + P[i];
	
	Number A[M] = {0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0x10};
	Number H[N + M + 1];
	
	FillH(H, Z, N + M + 1);
	
	// массив промежуточных результатов умножения
	Number V[21];
	for(size_t i = 0; i < M; ++i)
		V[i] = H[i + 0] * A[i];
	for(size_t i = 0; i < N; ++i)
		V[i] = H[i + M] * P[i];
	
	uint16_t lenC = N * 32;
	uint16_t lenA = M * 32;
	uint32_t lenS = (lenA << 16) + lenC;
	
	V[N + M] = H[N + M] * Number(lenS);
	
	Number sum = V[0];
	for(size_t i = 1; i <= N + M; ++i)
		sum = sum + V[i];
	
	// имитовставка
	uint32_t T = MSB(Shifr(sum), 11);
	
	for(size_t i = 0; i < N; ++i)
		std::cout << C[i] << ' ';
	std::cout << std::endl;
	std::cout << "T = 0x" << std::hex << T << std::endl;
	return 0;
}

Безусловно, режим шифрования AEAD-MGM в такой реализации не покрывает множество тонких моментов, но для понимания идей работы его, я думаю, вполне достаточно.

Полный код на С++:

Итоговый код

#include <iostream>
#include <cstdint>

// Galois Field Number
// для удобства показа идей и реализации тип uint32_t выбран специально
class Number
{
public:
	Number():
		value(0)
	{}
	Number(uint32_t value_):
		value(value_)
	{}

	operator uint32_t() const
	{ return value; }

public:
	friend Number operator+(Number left, Number right);
	friend Number operator*(Number left, Number right);

public:
	friend std::ostream& operator<<(std::ostream& os, Number number)
	{ return os << number.value; }

public:
	uint32_t value;
};

Number operator+(Number left, Number right)
{ return left.value ^ right.value; }

bool testbit(uint64_t value, size_t offset)
{ return value & (1 << offset); }

void setbit(uint64_t& value, size_t offset)
{ value |= 1 << offset; }

uint64_t MulMod2(uint32_t left, uint32_t right)
{
	uint64_t result = 0;
	uint64_t offset = 0;
	while(right)
	{
		if (right & 1)
			result ^= left << offset;
		++offset;
		right >>= 1;
	}
	return result;
}

size_t maxbit(uint64_t value)
{
	size_t retval = 0;
	while(value)
	{ value >>= 1; ++retval; }
	return retval;
}

uint32_t ModGenP(uint64_t value, uint64_t gen_polynom)
{
	while (true)
	{
		size_t vmaxbit = maxbit(value);
		size_t pmaxbit = maxbit(gen_polynom);
		
		if (vmaxbit < pmaxbit)
			return (uint32_t) value;
		
		size_t quotient = 1 << (vmaxbit - pmaxbit);
		value ^= gen_polynom * quotient;
	}
}

Number operator*(Number left, Number right)
{
	uint64_t gen_p = (1ULL << 32) + (1 << 22) + (1 << 2) + (1 << 1) + 1;
	uint64_t value = MulMod2(left.value, right.value);
	return ModGenP(value, gen_p);
}

uint32_t incr_l(uint32_t input)
{
	uint16_t L = (input & 0xffff0000) >> 16;
	uint16_t R = (input & 0x0000ffff);
	
	++L;
	
	return (L << 16) + R;
}

uint32_t incr_r(uint32_t input)
{
	uint16_t L = (input & 0xffff0000) >> 16;
	uint16_t R = (input & 0x0000ffff);
	
	++R;
	
	return (L << 16) + R;
}

uint32_t MSB(uint32_t number, size_t size)
{ return number & (0xffffffff - ((1 << size) - 1)); }

constexpr uint32_t Get0orN()
{
	constexpr uint32_t nonce = 0x5678;
	constexpr uint32_t zero  = 0;
	
	return (zero << 31) + nonce;
}

constexpr uint32_t Get1orN()
{
	constexpr uint32_t nonce = 0x5678;
	constexpr uint32_t one   = 1;
	
	return (one << 31) + nonce;
}

uint32_t Shifr(uint32_t input)
{
	return input;
}

void FillY(Number* Y, size_t count)
{
	Y[0] = Shifr(Get0orN());
	for(size_t i = 1; i < count; ++i)
		Y[i] = incr_r(Y[i - 1]);
}

void FillZ(Number* Z, size_t count)
{
	Z[0] = Shifr(Get1orN());
	for(size_t i = 1; i < count; ++i)
		Z[i] = incr_l(Z[i - 1]);
}

void FillH(Number* H, Number* Z, size_t count)
{
	for(size_t i = 0; i < count; ++i)
		H[i] = Shifr(Z[i]);
}

int main()
{
	constexpr size_t N = 10;
	constexpr size_t M = 10;
	
	Number Y[N];
	Number Z[N + M + 1];
	
	FillY(Y, N);
	FillZ(Z, N + M + 1);
	
	Number P[N] = {0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0x10};
	Number C[N];
	
	for(size_t i = 0; i < N; ++i)
		C[i] = Number(Shifr(Y[i])) + P[i];
	
	Number A[M] = {0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0x10};
	Number H[N + M + 1];
	
	FillH(H, Z, N + M + 1);
	
	// массив промежуточных результатов умножения
	Number V[21];
	for(size_t i = 0; i < M; ++i)
		V[i] = H[i + 0] * A[i];
	for(size_t i = 0; i < N; ++i)
		V[i] = H[i + M] * P[i];
	
	uint16_t lenC = N * 32;
	uint16_t lenA = M * 32;
	uint32_t lenS = (lenA << 16) + lenC;
	
	V[N + M] = H[N + M] * Number(lenS);
	
	Number sum = V[0];
	for(size_t i = 1; i <= N + M; ++i)
		sum = sum + V[i];
	
	// имитовставка
	uint32_t T = MSB(Shifr(sum), 11);
	
	for(size_t i = 0; i < N; ++i)
		std::cout << C[i] << ' ';
	std::cout << std::endl;
	std::cout << "T = 0x" << std::hex << T << std::endl;
	return 0;
}

Ссылки на статьи

AEAD-MGM

Арифметика полей Галуа GF(2ⁿ):