Векторные пространства над конечными полями Галуа в криптографии

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

Самым фундаментальным и часто используемым в IT является простейшее поле Галуа — GF(2). Оно состоит всего из двух элементов: 0 и 1. Операция сложения в этом поле эквивалентна логической операции XOR (исключающее ИЛИ). В этой удивительной арифметике 1 + 1 = 0, что означает, что каждый элемент является обратным самому себе по сложению (вычитание полностью совпадает со сложением). Линейное векторное пространство над GF(2) размерности n представляет собой множество всех возможных битовых строк длины n. Системы линейных уравнений в таком пространстве решаются методом Гаусса без единой операции реального деления или умножения дробей, что позволяет процессорам выполнять криптографические операции со скоростью миллиардов бит в секунду.

Линейные коды, исправляющие ошибки

Когда ваш жесткий диск или канал связи (например, космический зонд, передающий фото с Марса) искажает биты информации, на помощь приходит теория кодирования, построенная на дискретной линейной алгебре. Линейный блоковый код — это просто линейное подпространство в пространстве над полем Галуа. Сообщение превращается в вектор и умножается на порождающую матрицу G (Generator matrix). Для проверки правильности полученного сообщения на приемной стороне вектор умножается на проверочную матрицу H (Parity-check matrix). Согласно законам линейной алгебры, если ошибок нет, результат умножения (синдром) будет строго нулевым вектором, так как проверочная матрица ортогональна порождающей. Если есть ошибки, значение синдрома аналитически указывает на искаженный бит, позволяя мгновенно его инвертировать и восстановить данные.

Ортодоксальная геометрия без расстояний

Векторные пространства над конечными полями разрушают нашу геометрическую интуицию. Например, в евклидовом пространстве скалярное произведение ненулевого вектора на самого себя всегда положительно. В пространстве над GF(2) вектор (1, 1) при скалярном умножении на себя дает 1*1 + 1*1 = 1 + 1 = 0. Это означает, что ненулевой вектор может быть ортогонален (перпендикулярен) самому себе! В таких пространствах существуют целые самоортогональные подпространства. Вместо евклидова расстояния метрика в таких системах измеряется с помощью расстояния Хэмминга — это количество координат (битов), в которых два вектора отличаются друг от друга. Поиск ортогональных базисов и подпространств с максимальным хэмминговым расстоянием — главная задача при проектировании надежных алгоритмов 5G связи.

Матрицы в стандарте шифрования AES

Венцом применения матриц над конечными полями является стандарт симметричного шифрования AES (Advanced Encryption Standard), которым зашифрован весь банковский трафик и мессенджеры. Внутри алгоритма AES данные представляются в виде матриц 4x4, элементы которых лежат в более сложном поле Галуа GF(2^8) (каждое число — это байт от 0 до 255). Один из важнейших этапов шифрования называется MixColumns (смешивание столбцов). На этом этапе каждый столбец матрицы данных умножается на специальную фиксированную обратимую матрицу. Это матричное умножение над конечным полем обеспечивает криптографическую диффузию: изменение всего одного бита во входном пароле приводит к лавинообразному непредсказуемому изменению всего зашифрованного блока, делая взлом шифра абсолютно невозможным для современных суперкомпьютеров.