Группы, кольца и поля

1832. 20-летний Эварист Галуа записал свои математические идеи в ночь перед дуэлью - он знал, что утром, вероятно, погибнет. Погиб. Его теория конечных полей стала фундаментом AES через 150 лет. Каждый раз, когда AES шифрует байт, он выполняет операции в той самой алгебраической структуре, которую изобрёл Галуа.

• **AES (Advanced Encryption Standard)** - каждая операция SubBytes вычисляет мультипликативный обратный в GF(2^8), а MixColumns выполняет матричное умножение в том же поле. Миллиарды устройств ежесекундно работают в поле Галуа
• **Эллиптические кривые (ECC)** - ECDSA (подпись Bitcoin-транзакций), ECDHE (TLS handshake в браузерах) работают в группе точек эллиптической кривой над конечным полем GF(p)
• **AES-GCM (аутентифицированное шифрование)** - режим Galois/Counter Mode вычисляет тег аутентификации через умножение в GF(2^128). Название "Galois" в GCM - прямая ссылка на конечные поля. Каждое HTTPS-соединение использует GCM

Эварист Галуа и теория полей

В 1832 году 20-летний Эварист Галуа, находясь под арестом и зная, что его вызвали на дуэль, за одну ночь записал ключевые идеи своей теории - включая понятие конечных полей. Он погиб на следующее утро. Его рукописи были изданы только в 1846 году. Через 150 лет теория Галуа стала математической основой AES, принятого в 2001 году как стандарт шифрования США. AES-NI - аппаратные инструкции для арифметики GF(2^8) - встроены в каждый современный процессор Intel и AMD.

Предварительные знания

• Number Theory for Cryptography

Группы

**Группа** - это фундаментальная алгебраическая структура: множество G с операцией *, которая удовлетворяет ровно четырём аксиомам. Эти аксиомы настолько общие, что описывают огромное количество математических объектов - от целых чисел до точек на эллиптических кривых. В криптографии группы - это арена, на которой работают протоколы Diffie-Hellman, DSA, и вся криптография эллиптических кривых (ECC).

Рассмотрим конкретный пример: **Z_7* = {1, 2, 3, 4, 5, 6}** с умножением по модулю 7. Число 7 - простое, поэтому каждый ненулевой элемент имеет обратный. Проверим: 3 * 5 = 15 mod 7 = 1, значит 3^(-1) = 5. Аналогично: 2 * 4 = 8 mod 7 = 1, значит 2^(-1) = 4. Нейтральный элемент - 1. Все четыре аксиомы выполнены.

**Циклические группы и генераторы:** Группа **циклическая**, если существует элемент g (генератор), степени которого дают все элементы группы: G = {g^0, g^1, g^2, ..., g^(n-1)}. В Z_7* генератор g=3 порождает всю группу: - 3^1 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1 (все mod 7) **Порядок элемента** - минимальное k, при котором g^k = e (нейтральный). **Теорема Лагранжа:** порядок любого элемента делит порядок группы. Z_7* имеет порядок 6, поэтому порядки элементов: 1, 2, 3 или 6.

Почему группы критичны для криптографии? Протокол **Diffie-Hellman** работает в циклической группе: безопасность основана на том, что вычислить g^a (возведение в степень) - быстро, а найти a по g^a (дискретный логарифм) - вычислительно неразрешимо для больших групп. **ECC** работает в группе точек эллиптической кривой, где аналогичная задача ещё сложнее.

Кольца и поля

Группа - это множество с одной операцией. Но в арифметике мы используем две операции: сложение и умножение. **Кольцо** - это алгебраическая структура с двумя операциями, связанными дистрибутивным законом. **Поле** - это кольцо, в котором каждый ненулевой элемент имеет мультипликативный обратный. Поля - это именно та структура, которая нужна криптографии: в них можно складывать, вычитать, умножать и делить без ограничений.

Ключевое различие между кольцом и полем: в кольце Z_6 (целые по модулю 6) элемент 2 не имеет мультипликативного обратного, потому что 2 * k mod 6 никогда не равно 1 для целого k. Причина: gcd(2, 6) = 2, а не 1. Поэтому Z_6 - кольцо, но **не поле**. А вот Z_7 - поле: 7 простое, gcd(a, 7) = 1 для всех a от 1 до 6, и каждый элемент обратим.

**Почему поля важнее колец для криптографии?** Криптография требует **обратимых** операций. Шифрование - это функция E(x), и дешифрование - это E^(-1)(y). Если работать в кольце, где некоторые элементы необратимы, то нельзя гарантировать дешифрование каждого сообщения. В **поле** каждая операция (кроме деления на 0) обратима. Это даёт гарантированную обратимость шифрования и предсказуемую арифметику без "дыр". Z_p (p простое), GF(2^8), GF(2^128) - все поля, используемые в реальной криптографии.

Важный факт: конечное поле существует тогда и только тогда, когда количество его элементов равно p^n, где p - простое число, а n - натуральное. Не существует поля из 6, 10 или 12 элементов. Зато существуют GF(2), GF(4), GF(8), GF(16), ... (степени двойки) и GF(3), GF(9), GF(27), ... (степени тройки). Для каждого допустимого размера конечное поле единственно с точностью до изоморфизма - результат теории Галуа.

Конечные поля GF(p) и GF(2^n)

Конечные поля названы **полями Галуа** (Galois Fields, GF) в честь Эвариста Галуа. Существует два типа конечных полей, критически важных для криптографии: **GF(p)** - целые числа по модулю простого p, и **GF(p^n)** - расширения, где элементы представлены как полиномы. В криптографии чаще всего встречаются GF(p) для больших простых p (RSA, Diffie-Hellman, ECC) и GF(2^n) - расширения над GF(2), где арифметика сводится к побитовым операциям (AES, GHASH).

GF(2^n) устроено сложнее. Его элементы - это **полиномы степени не выше n-1 с коэффициентами из GF(2)** (то есть коэффициенты - 0 или 1). Например, элемент GF(2^8) - это полином вроде x^7 + x^4 + x^2 + 1, который кодируется байтом 10010101. Сложение полиномов - это XOR коэффициентов, а умножение - полиномиальное умножение по модулю неприводимого полинома.

**Неприводимый полином - аналог простого числа:** В GF(p) модуль - простое число p, которое нельзя разложить на множители. В GF(2^n) модуль - **неприводимый полином** степени n. Выбор неприводимого полинома **не влияет на безопасность** - все поля GF(2^n) одного размера изоморфны. Но влияет на **производительность**: для AES выбран x^8 + x^4 + x^3 + x + 1, потому что он позволяет эффективную аппаратную реализацию.

Почему GF(2^n) идеален для компьютеров? Сложение - это XOR (одна процессорная инструкция). Элементы - это n-битные числа, прекрасно помещающиеся в регистры. AES использует GF(2^8), потому что один элемент поля - это ровно один байт. AES-GCM использует GF(2^128), потому что один элемент - это ровно один 128-битный блок. Конечные поля характеристики 2 - это мост между абстрактной алгеброй и процессорной архитектурой.

Операции в конечных полях

Теперь, когда понятна структура GF(2^n), разберём операции подробно - на примере **GF(2^8)**, которое используется в AES. Каждый байт (0x00 - 0xFF) - элемент поля. AES использует неприводимый полином m(x) = x^8 + x^4 + x^3 + x + 1 (0x11B в hex). Все операции SubBytes, MixColumns и другие трансформации AES - это арифметика в GF(2^8).

**AES S-box: инверсия в GF(2^8) + аффинное преобразование** Самая криптографически важная операция в GF(2^8) - нахождение мультипликативного обратного. S-box AES работает в два шага: 1. **Инверсия в GF(2^8):** байт b заменяется на b^(-1) (0 отображается в 0) 2. **Аффинное преобразование:** линейное преобразование + сдвиг Почему именно инверсия? Максимальная нелинейность (минимальная корреляция с линейными функциями), высокий алгебраический порядок, доказуемая устойчивость к дифференциальному и линейному криптоанализу.

Операции в конечных полях - не абстракция, а рабочий инструмент современной криптографии. Каждый раз, когда браузер устанавливает HTTPS-соединение, процессор выполняет миллионы операций в GF(2^8) (AES) и GF(p) (ECDHE key exchange). Набор инструкций AES-NI в современных процессорах - это аппаратная реализация арифметики GF(2^8). Абстрактная алгебра, изобретённая Галуа в 1832 году, буквально впаяна в кремний.

Ключевые идеи

• **Группа** - множество с операцией, удовлетворяющей четырём аксиомам (замкнутость, ассоциативность, нейтральный, обратный). Циклические группы с генераторами - основа Diffie-Hellman и ECC
• **Кольцо vs поле:** кольцо имеет две операции с дистрибутивностью, поле добавляет мультипликативную обратимость всех ненулевых элементов. Криптографии нужны именно поля - для гарантии обратимости шифрования
• **GF(p) и GF(2^n):** два типа конечных полей в криптографии. GF(p) - арифметика mod простого p (RSA, ECC). GF(2^n) - полиномы над GF(2), где сложение = XOR (AES, GCM)
• **Операции в GF(2^8):** сложение через XOR, умножение через xtime и редукцию, инверсия через возведение в степень. AES S-box построен на инверсии в GF(2^8) - ради доказуемой нелинейности. Теория Галуа впаяна в каждый современный процессор через AES-NI

Вопросы для размышления

• Почему криптография работает в конечных полях, а не в бесконечных (вещественные числа, комплексные числа)? Какие практические и теоретические преимущества даёт конечность?
• В AES S-box используется инверсия в GF(2^8). Если бы выбрали другой неприводимый полином (не x^8 + x^4 + x^3 + x + 1), изменились бы криптографические свойства S-box? Почему да или нет?
• RSA работает в кольце Z_n (где n - составное), а не в поле. Какие свойства кольца (в отличие от поля) делают RSA возможным?

Связанные уроки

• crypto-03-number-theory
• crypto-14-aes
• crypto-26-ecc-math
• crypto-23-key-exchange
• crypto-24-rsa-math
• ml-04
• nt-01