Почему конечные поля так важны в криптографии?

Я только начинаю заниматься криптографией и в настоящее время учусь, пытаясь реализовать некоторые криптоалгоритмы.

В настоящее время реализуя алгоритм обмена секретами Shamir, я заметил, что конечные поля продолжают появляться.

Я просто пока не понимаю, почему они актуальны.

Одна вещь, которую я вижу, это то, что они могут убедиться, что ни один из ваших результатов не является десятичным, поэтому нет ошибок округления, но я сильно сомневаюсь, что это причина, по которой они так важны. Было бы здорово, если бы кто-то мог дать мне интуитивное представление о том, зачем они нужны.

Кроме того, вредит ли безопасности тот факт, что они ограничены?

Я постараюсь дать общий ответ на этот вопрос.

Конечное поле, обозначаемое ${F_p}$, где p — простое число, хорошо работает с криптографическими алгоритмами, такими как AES, RSA и т. д., по следующим причинам:

• Нам нужно расшифровать зашифрованное сообщение, это возможно только тогда, когда доступна уникальная (биективная) обратная функция. Это возможно только тогда, когда у функции нет делителя нуля, а также она инъективна и сюръективна.

• Также это обеспечивает закрытую операцию, что означает, что любая операция, которую вы выполняете в поле, результат останется в поле, что упрощает реализацию криптографических алгоритмов.

• Конечное поле, порожденное простым числом (простым числом или неприводимым полиномом), обладает этими необходимыми характеристиками.

• Он используется не только в криптографии, но и в канальном кодировании, таком как BCH или кодирование Рида-Соломона. он широко распространен в большинстве кодов исправления ошибок связи, безопасности данных / контента, а также их расширения, такие как группы и кольца, используются в химии и других научных областях.

Вопросы, поднятые Марком и SSA, являются главными. У нас есть хорошо изученный класс структур, которые сочетаются с подходящими задачами, которые в настоящее время считаются неразрешимыми с вычислительной точки зрения (несмотря на то, что они хорошо изучены). На самом деле все аффинные линейные отображения $x\mapsto ax+b$ являются биекциями (см., что Марк сказал о максимальной энтропии) всякий раз, когда $а$ является ненулевым элементом поля. Если бы у нас не было конкретного поля, это не имело бы места.

Я также хочу добавить несколько свойств конечных полей характеристики два, в частности ($GF(2^n)$ или же $\Bbb{F}_{2^n}$):

• Пространство ключей (или пространство сообщений или еще что-то) имеет размер, который представляет собой точное целое число битов. Это, по общему признанию, не является насущной проблемой. Скорее удобство.
• Наличие полевой структуры позволяет анализировать определенные вычислительно эффективные операции с точки зрения безопасности. Например, мономиальные функции широко изучались с точки зрения дифференциального криптоанализа. Найдите функции APN (= Почти идеальная нелинейность). При более случайной структуре такой анализ был бы более утомительным.

Однако у этих полей есть и недостатки.

• дополнительная структура означает, что, например, DLP может быть более удобным, чем A) в группе «черных ящиков» того же размера или даже B) в простом поле почти такого же размера.

Почему поле: Идея совместного использования секрета Шамиром состоит в том, чтобы восстановить секрет (функциональность) и доказать, что любой общий секрет возможен (безопасность), используя полиномиальную интерполяцию.

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

В то время как обмен секретами Шамира обычно осуществляется с полями, это было сделано со многими другими алгебраическими структурами. Это обычно требует большой осторожности и сложно. Если вам действительно не нужно, делать это над полями намного проще и предпочтительнее.

Почему конечно: Для безопасности недостаточно того, что возможен любой общий секрет, каждый общий секрет также должен быть (почти) равновероятным. Использование конечных полей позволяет нам выбирать случайность из равномерного распределения, что, как оказывается, дает нам именно то, что мы хотим.

Мы могли бы работать с бесконечным полем, таким как рациональные числа, но в этом случае было бы очень трудно сделать так, чтобы все общие секреты были почти одинаково вероятными. Это связано с отсутствием равномерного распределения на бесконечных множествах. Грубо говоря, один из способов взглянуть на это состоит в том, что размер значения связан с размером коэффициентов и с тем, где мы оцениваем, поэтому, если мы хотим скрыть один из коэффициентов, нам нужно «заглушить» его с помощью остальные коэффициенты значительно больше.

Сделать это над целыми числами (не полем!) можно, но для обеспечения безопасности требуется довольно много работы. В качестве побочного эффекта (по крайней мере, для схемы, которую я рассматривал) доли в конечном итоге становятся намного больше. Вы не хотите эти расходы, если у вас нет веской причины. (Что вы иногда делаете.)

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

Другие области криптографии: Конечные поля используются во всей криптографии. Как правило, это связано с ненулевыми элементами в полях, имеющих мультипликативные обратные значения, которые нам очень часто нужны. У операции также есть много других хороших, доказуемых свойств.

Конечная часть обычно требуется для практичности, а иногда и из-за особых свойств конечных полей.

• АЕС: Одним из примеров является поле AES, где многие желаемые свойства следуют из алгебраических свойств. Например, вы не получите те же алгебраические свойства от целых чисел по модулю 256 (кольцо).

• Мультипликативная подгруппа: Другой пример — мультипликативная подгруппа конечного поля (ненулевые элементы конечного поля образуют циклическую группу), которая для тщательно выбранного конечного поля оказывается подходящей группой для криптографии на основе d.log. (Дискретные логарифмы определяются аналогично обычным логарифмам, но оказывается, что в некоторых группах их очень сложно вычислить без квантового компьютера.)

  В этом случае мы могли бы также использовать определенные кольца, но оказалось, что на практике для такого рода приложений лучше подходят первичные конечные поля. Например, безопасность не зависит от секретного группового порядка, что позволяет нам делать некоторые вещи, которые вы не можете сделать, если групповой порядок неизвестен. (RSA работает с такими кольцами, но имеет другие свойства и требования.)

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

  Изучение эллиптических кривых — важная часть теории чисел, но для криптографических целей кривые, заданные над бесконечными полями, непрактичны или непригодны для функциональных целей и не обладают требуемыми свойствами безопасности. (Например, приблизительный дискретный логарифм можно вычислить, взглянув на размер координат, который нарушил бы безопасность, если бы сначала не нарушил практичность.) Хотя эллиптические кривые, заданные для бесконечных полей, функционально не используются в криптографии, их изучение необходимо для анализа криптографии на эллиптических кривых.

  Эллиптические кривые над некоторыми конечными кольцами рассматривались в криптографическом контексте, но, за исключением неясных случаев, не представляют ничего интересного. (Очевидно, что факторинг эллиптических кривых исключен!)

• Дополнительные примеры: Криптография на основе решетки и криптография на основе кода, в которой используются алгебраические структуры, определенные над конечными полями. Многомерная криптография, основанная на системах полиномиальных уравнений над конечными полями.

  Опять же, многое из этого можно сделать над определенными конечными кольцами, но есть много недостатков и мало что можно получить.

В частности, для Шамира, посвященного секретному обмену, статья в Википедии Переговоры о почему используются конечные поля вместо другого кольца.В конечном поле никакая информация о секрете не утекает, если известно количество долей ниже порогового значения. Причина этого в том, что каждая функция на конечном поле имеет уникальное полиномиальное представление (степени не выше q-1)