Дискретная математика
Группы и кольца (обзор)
Протокол Диффи-Хеллмана, защищающий ваш TLS-трафик прямо сейчас, работает в группе $\mathbb{Z}_p^*$. AES шифрует данные в поле $\mathrm{GF}(2^8)$ - конечном поле с 256 элементами. Группы и поля - не абстрактная алгебра, а инженерный фундамент современной криптографии.
- DH-обмен ключами: Алиса и Боб публикуют $g^a \bmod p$ и $g^b \bmod p$, вычисляя общий секрет $g^{ab} \bmod p$ - безопасность держится на сложности дискретного логарифма в группе $\mathbb{Z}_p^*$.
- AES работает над $\mathrm{GF}(2^8)$: операция MixColumns - умножение матриц над этим полем. Поле обеспечивает обратимость и диффузию - два ключевых свойства блочного шифра.
- Коды Рида-Соломона (исправление ошибок в QR-кодах и DVD) построены над конечными полями $\mathrm{GF}(p^k)$ - многочлены над полем образуют кольцо с нужными алгебраическими свойствами.
Цели урока
- Проверять выполнение аксиом группы и строить таблицу Кэли для конкретных структур
- Различать кольца и поля и объяснять роль делителей нуля
- Конструировать конечные поля $\mathrm{GF}(p^k)$ через неприводимые многочлены
Предварительные знания
- Модульная арифметика и теорема Эйлера
- Основы теории чисел: НОД, простые числа
Группы: симметрия и протоколы
Группа $(G, \cdot)$ - множество с ассоциативной операцией, нейтральным элементом и обратными. Порядок элемента $a$ - наименьшее $k$ с $a^k = e$. По теореме Лагранжа порядок подгруппы делит $|G|$ - отсюда: в $\mathbb{Z}_p^*$ (простое $p$) каждый ненулевой элемент имеет порядок, делящий $p-1$. Это основа малой теоремы Ферма $a^{p-1} \equiv 1 \pmod{p}$.
Кольца, поля и конечная геометрия
Кольцо $(R, +, \cdot)$ добавляет к группе второй операцией умножение (ассоциативное, дистрибутивное). Делители нуля - ненулевые $a, b$ с $ab = 0$ - делают кольцо «плохим» для деления. В $\mathbb{Z}/6\mathbb{Z}$: $2 \cdot 3 = 0$. Поле - коммутативное кольцо без делителей нуля, где каждый ненулевой элемент обратим. Конечные поля: $\mathrm{GF}(p)$ для простого $p$, и $\mathrm{GF}(p^k)$ - как $\mathbb{Z}_p[x]/(f(x))$ для неприводимого $f$ степени $k$.
В $\mathrm{GF}(2^8)$ (AES) элементы - многочлены степени $\leq 7$ над $\mathrm{GF}(2)$. Сложение - XOR (побитовое). Умножение - по модулю неприводимого многочлена $x^8 + x^4 + x^3 + x + 1$ (выбор NIST). Все 256 ненулевых элементов образуют циклическую группу - существует генератор $g$, порождающий всё поле.
$\mathbb{Z}/n\mathbb{Z}$ является полем только если $n$ - простое. При составном $n$ появляются делители нуля. Поэтому криптографические протоколы работают либо с $\mathbb{Z}/p\mathbb{Z}$ (простое $p$), либо с $\mathrm{GF}(2^k)$, но не с $\mathbb{Z}/n\mathbb{Z}$ для составного $n$ в роли поля.
Эварист Галуа в 1832 году, за день до дуэли, изложил теорию, теперь называемую е
Эварист Галуа в 1832 году, за день до дуэли, изложил теорию, теперь называемую его именем. Он доказал: многочлен разрешим в радикалах тогда и только тогда, когда его группа Галуа разрешима. Конечные поля $\mathrm{GF}(p^k)$ - прямое следствие его теории. Галуа погиб в 20 лет; полное осмысление его рукописей заняло ещё 14 лет.
Группы: аксиомы и дискретный логарифм
SHA-256 работает в кольце Z/2^32Z. AES шифрует в поле GF(2^8). Протокол Диффи-Хеллмана строится на сложности дискретного логарифма в Z_p*. Абстрактная алгебра - это не академика, это production криптография в каждом HTTPS-соединении.
Четыре аксиомы группы (G, *): (1) Замкнутость: a*b in G. (2) Ассоциативность: (a*b)*c = a*(b*c). (3) Нейтральный элемент e: a*e = a. (4) Обратный элемент: a*a^{-1} = e. Если ещё a*b = b*a - абелева (коммутативная) группа.
Теорема Лагранжа: порядок подгруппы делит порядок группы. Следствие: g^{|G|} = e для любого g. Для Z_p*: |Z_p*| = p-1, значит g^{p-1} = 1 mod p (малая теорема Ферма). Именно так вычисляется обратный элемент: g^{-1} = g^{p-2} mod p.
Почему дискретный логарифм в Z_p* с большим p вычислительно сложен, хотя g^x mod p вычисляется быстро?
Асимметрия сложности: g^x mod p вычисляется за O(log x) через быстрое возведение. Обратная задача - найти x по g^x mod p = h - не имеет полиномиального алгоритма; NFS работает за субэкспоненциальное время.
Кольца: Z/nZ и делители нуля
Кольцо (R, +, *): (R,+) - абелева группа, умножение ассоциативно и дистрибутивно. В Z/6Z: 2*3 = 0 (mod 6) - делители нуля! Именно поэтому Z/6Z не поле. AES требует поля (каждый элемент обратим) - поэтому используют GF(2^8), не Z/256Z.
Кольцо многочленов Z_2[x]: коэффициенты из {0,1}, сложение = XOR. Это кольцо с делителями нуля при приводимых многочленах. Фактор-кольцо Z_2[x]/(p(x)) по неприводимому p(x) степени k - это поле GF(2^k). Именно так устроен GF(2^8) в AES.
Почему Z/6Z имеет делители нуля, а Z/7Z - нет?
Кольцо Z/nZ является полем тогда и только тогда, когда n простое. Для составного n = a*b: [a]*[b] = [n] = [0], где оба ненулевые - делители нуля. При простом p никакое произведение двух ненулевых элементов не даст 0 mod p.
Поля GF(2^8): арифметика AES
GF(2^8) - поле из 256 элементов, лежащее в сердце AES-128/256. SubBytes (S-box) - это вычисление мультипликативного обратного в GF(2^8). MixColumns - умножение на фиксированную матрицу над GF(2^8). Коды Рида-Соломона (QR-коды, RAID-6) - полиномы над GF(2^8).
| Структура | Примеры | Обратимость умножения | Применение |
|---|---|---|---|
| Группа | Z, Z_p*, SO(3) | N/A | Криптография DH, ECDH |
| Кольцо | Z, Z/nZ, матрицы | Нет для всех | SHA-256, polynomial rings |
| Поле | Q, R, Z/pZ, GF(2^k) | Да (для ненулевых) | AES, Reed-Solomon, ECDSA |
GF(4) != Z/4Z. Z/4Z - кольцо с делителем нуля (2*2=4=0). GF(4) = Z_2[x]/(x^2+x+1) - поле, 4 элемента, все ненулевые обратимы. Конечные поля GF(p^k) единственны с точностью до изоморфизма - именно GF(2^8), не Z/256Z.
Почему AES использует GF(2^8), а не Z/256Z для операций над байтами?
SubBytes требует мультипликативного обратного для каждого байта. В Z/256Z чётные числа не обратимы (2*128=0). GF(2^8) - поле, где каждый ненулевой элемент обратим, что гарантирует корректность SubBytes.
Дискретный логарифм в DH-протоколе
Возьмём $p=23$, генератор $g=5$. Алиса выбирает $a=6$: публикует $5^6 \bmod 23 = 8$. Боб выбирает $b=15$: публикует $5^{15} \bmod 23 = 19$. Общий секрет: $8^{15} \bmod 23 = 19^6 \bmod 23 = 2$. Взломщик видит $8$ и $19$, но найти $a$ или $b$ - задача дискретного логарифма, вычислительно сложная при больших $p$.
Итоги
- Группы описывают симметрию и лежат в основе криптографии дискретного логарифма.
- Кольца расширяют группы вторым действием; делители нуля - главная патология.
- Поля - кольца без делителей нуля, конечные поля $\mathrm{GF}(p^k)$ строятся через неприводимые многочлены и используются в AES и кодах исправления ошибок.
Связь с другими темами
Криптографические алгоритмы (dm-28) строятся именно на этих структурах: RSA работает в кольце $\mathbb{Z}/n\mathbb{Z}$, ECC - в группе точек над полем. Теория чисел (dm-09, dm-10) поставляет инструменты для анализа порядков и первообразных корней.
- Dm 28 — связан
- Dm 09 — связан
- Dm 10 — связан
Вопросы для размышления
- В $\mathrm{GF}(2^8)$ умножение $\texttt{0x57} \times \texttt{0x83}$ даёт $\texttt{0xC1}$. Попробуйте выполнить это вручную через XOR-полиномиальное деление - и вы поймёте, почему AES можно эффективно реализовать на аппаратуре без умножителей.?