malkovsky Jun 9 at 08:30

Детальный обзор полей Галуа

Medium

15 min

12K

Mathematics*Algorithms*Programming*History of IT

Review

+116

Comments 28

vened Jun 9 at 12:49

поле - это множество чисел

Всё ж, наверное, не "множество чисел".

(AES) [...] Проконсультировался с коллегами алгебраистами, так если честно и не понял почему и зачем именно такое преобразование используется, напишите в комментариях если знаете зачем.

В AES конечное поле используется потому, что это относительно простой способ задать строгую структуру с нужными свойствами на конечном наборе элементов. То есть, когда отображения внутри множества гарантированно будут взаимно однозначными (биекция), а поэтому можно получить для зафиксированного элемента a "равномерное" отображение $x \mapsto x + a$ на той же структуре, что и делается в AES, но при помощи умножения (шаг MixColumns базового преобразования). Конкретно в AES - схема используется для перемешивания значений, с некоторой гарантией отсутствия наложения результатов; то есть, наблюдая статистику на выходе преобразования - сложно различить входные значения (это прямо следует из того, что используемые операции биективны). Собственно, по этим же причинам конечные поля используются в прикладной криптографии вообще.

(Естественно, есть и обратный эффект: если структуры "слишком много", то, зная некоторый секрет, можно построить разбиение входных значений по выходным. Это одно из направлений поиска "закладок" алгебраическими методами. Поле - не всегда хорошо для криптосистемы. Группа - лучше.)

malkovsky Jun 9 at 13:14

Если уж докапываться до мелочей, то не хорошо обрубать контекст ;)

Простыми словами поле - это множество чисел

Я согласен, что в общем виде это не числа, но для человека незнакомого с концепцией проще её понять если использовать простые и знакомые термины, поэтому написал как написал. Точно также не считаю зазорным объясняя понятие "матрицы" для человека не знакомого с линейной алгеброй использовать описание "прямоугольная таблица с числами".

За пояснения по AES спасибо! А вообще можете объяснить на чем там криптостойкость основана? Не на GF же? А то закрадываются мысли о том, что "рекомендовано NIST" можно трактовать как любят спецслужбы: обыватель не сможет взломать, а мы сможем.

vened Jun 9 at 14:04

Я согласен, что в общем виде это не числа, но для человека незнакомого с концепцией проще её понять если использовать простые и знакомые термины, поэтому написал как написал.

Так главное - не перевернуть обобщение: рациональные числа образуют поле, но не очень хорошо писать, упрощая в другую сторону, что "поле - это рациональные числа".

Точно также не считаю зазорным объясняя понятие "матрицы" для человека не знакомого с линейной алгеброй использовать описание "прямоугольная таблица с числами".

А вот это обобщение лучше. Потому что "прямоугольные таблицы с числами" - это заведомо шире определение, чем матрицы. А "поля - числа" - наоборот.

А вообще можете объяснить на чем там криптостойкость основана? Не на GF же?

Так весь AES можно переписать "в GF" - так и называется: Rijndael-GF. Поэтому, в каком-то смысле, практическая стойкость прямо связана с арифметикой в конечном поле, да. Но, если чуть ближе к вычислительной реальности, то предположение о стойкости AES основывается лишь на том, что не удалось найти методов, позволяющих на практике использовать внутреннюю структуру шифра для того, чтобы отличить выдачу для конкретного открытого текста (и неизвестного ключа) от случайной последовательности той же длины, что и блок. Ну или есть другие варианты моделирования стойкости, но они похожи - смысл всё тот же: повторное комбинаторное перемешивание стирает "все" следы структуры шифра (и поля, кстати). Но строго это не доказано, конечно.

А то закрадываются мысли о том, что "рекомендовано NIST" можно трактовать как любят спецслужбы: обыватель не сможет взломать, а мы сможем.

Есть и такое мнение, факт. И алгебраичность AES только способствует "закрадыванию" таких мыслей. Но, скорее, если уж и взломать, то через ошибки реализации и утечки по побочным каналам.

malkovsky Jun 9 at 14:16

Сделаю небольшую пометку по поводу полей и чисел. По AES дополню статью вашим комментарием, спасибо!

NeoNN Jun 9 at 13:40

Прекрасная статья, почти введение в основы криптографии, узнаю старый добрый Хабр. Побольше бы такого, вместо однообразного потока бреда про ИИ, найм и прочее.

malkovsky Jun 9 at 16:30

Благодарю! Будет еще. А так like, subscribe, repost - джентельменский набор для поддержки автора ;)

Komrus Jun 9 at 14:03

Вспомнились студенческие времена...
Подумалось, что с теми годами у меня ассоциируются "Поля Галуа" и "Земляничные поля" :)

mayorovp Jun 9 at 16:14

Забыли про такое применение полей Галуа, как сдвиговые регистры с линейной обратной связью (Linear-feedback shift register, LFSR).

malkovsky Jun 9 at 16:28

Честно говоря, я их просто не особо озознал и переварил. Они используются как-нибудь кроме генерации псевдослучайных чисел?

mayorovp Jun 9 at 16:35

А генерации псевдослучайных чисел недостаточно?

malkovsky Jun 9 at 16:53

Добавлю

mayorovp Jun 10 at 08:50

Linear shift feedback register

Ну как так? Регистр вообще- то с линейной обратной связью (linear feedback), а у вас почему-то линейный сдвиг вышел...

malkovsky Jun 10 at 08:58

Посыпаю голову пеплом ... поправил

mrhru2 Jun 9 at 22:12

М-последовательности (последовательности максимальной длины) используются в некоторых видах локации. Например, при картографировании Венеры использовали последовательность длиной 127, если я правильно ошибаюсь. Еще могут использоваться и в гидролокации.

Основное свойство таких последовательностей длины 2^m-1=N, это то, что их автокорреляционная функция имеет пик равный N и -1 в остальных позициях..

Refridgerator Jun 11 at 05:50

LFSR по модулю 2 используются в цифровой обработке сигналов для задач измерения, потому что дискретный амплитудный спектр по максимальной длине периода - константный, а сама амплитуда сигнала минимально возможная и не теряет точности при масштабировании (в отличие от ЛЧМ).

alcotel Jun 12 at 11:59

Для получения "контрольной суммы" (CRC) сообщений в большинстве интерфейсов - Ethernet, USB, PCIe, CAN, беспроводных. А где удачная CRC, там и хороший хэш.

Математически это нахождение остатка от деления сообщения (полинома большой степени) на порождающий полином. Аппаратно - это LFSR с дополнительным входом.

andrettv Jun 9 at 22:21

Так здОрово, что напрашивается продолжение) Например, про применение теории решёток (ML-KEM, ML-DSS и прочие, устойчивые к алгоритму Шора) и про легковесную криптографию (Ascon и пр.)

malkovsky Jun 9 at 22:29

Ух, поизучаю, но на текущий момент у меня 0 знаний по указанным темам.

andrettv Jun 11 at 10:58

Посмотрите, например, https://eprint.iacr.org/2024/1287.pdf

cher-nov Jun 10 at 14:40

а деление с остатком необратимо

А если представить элементы поля не в виде чисел, а в виде кортежей $\langle mag; rem \rangle$ (величина и остаток), где у "обычных" целых чисел остаток по умолчанию будет равен ?

malkovsky Jun 10 at 14:55

Как будто в этом кортеже не будет хватать информации о делителе, т.е. вот вы поделили (a, 0) на (b, 0) и получили (q, r). Как потом (q, r) умножить на (с, 0)?

Также стоит отметить, что рациональные числа -- это пары (a, b), где a, b - целые, gcd(a, b)=1 и b!=0 умножение (a, b) * (c, d)=(ac/gcd(ac, bd), bd/gcd(ac, bd)), обратный элемент (a, b)^{-1}=(b, a)

cher-nov Jun 10 at 19:12

Как потом (q, r) умножить на (с, 0)?

q * c + r , разве нет?

malkovsky Jun 10 at 19:41

Мне не особо понятна какая тут арифметика получается. Надо тогда полностью правила умножения/обращения для таких пар, чтобы предметно обсуждать.

Readme Jun 11 at 18:32

если представить элементы поля не в виде чисел, а в виде кортежей

Тогда это уже будет не поле целых чисел, а поле таких "кортежей" (кажется, полностью идентичное полю рациональных чисел). Вопрос просто в определении: по определению поля, множество целых чисел не является полем, так как частное от деления целых чисел может не принадлежать множеству целых чисел.