Конечные поля Галуа: Алгебраический фундамент криптографии
Для создания надежных шифров и систем защиты данных классическая непрерывная математика (с ее бесконечными вещественными числами) абсолютно не подходит. Компьютеры работают с фиксированной памятью и битами, а операции деления над вещественными числами приводят к ошибкам округления. Для решения этих проблем информатика позаимствовала из высшей алгебры концепцию конечных полей (полей Галуа), названных в честь гениального французского математика Эвариста Галуа.
Математическое поле (Field) — это множество, на котором заданы операции сложения, вычитания, умножения и деления (кроме деления на ноль), причем эти операции подчиняются привычным законам: ассоциативности, коммутативности и дистрибутивности. Знакомые нам множества рациональных (дробей) и вещественных чисел образуют бесконечные поля. Но целые числа полем не являются: разделив 3 на 2, мы получим 1.5, что уже не целое число (множество не замкнуто относительно деления).
Конечное поле (GF — Galois Field) содержит строго ограниченное количество элементов. Теорема гласит, что конечное поле существует тогда и только тогда, когда количество его элементов равно p^n, где p — простое число (характеристика поля), а n — натуральное число.
Самое простое конечное поле — GF(2). Оно содержит всего два элемента (0 и 1), а операции сложения и умножения в нем в точности соответствуют логическим операциям XOR (исключающее ИЛИ) и AND (логическое И). Это основа всей бинарной логики процессоров.
Для сложных задач криптографии используются поля Галуа вида GF(p^n). Элементы такого поля представляются не как обычные числа, а как многочлены (полиномы) степени меньшей n, коэффициенты которых берутся из поля GF(p). Все операции сложения и умножения выполняются над полиномами с последующим взятием остатка от деления на специальный неприводимый полином (аналог простого числа в мире полиномов).
Самое известное и массовое применение этой математики — современный государственный стандарт шифрования AES (Advanced Encryption Standard). Вся его математика построена на вычислениях в поле GF(2^8). Размер поля выбран не случайно: 2^8 равно 256, что позволяет одному элементу поля идеально кодировать ровно один байт данных. Операция SubBytes в алгоритме AES — это просто нахождение мультипликативного обратного элемента в поле Галуа. Также поля Галуа критически важны для кодов Рида-Соломона, которые защищают данные от царапин на компакт-дисках и исправляют ошибки при скачивании файлов из интернета.
