Скрытые уравнения поля

Скрытые уравнения поля (HFE, анг. Hidden Field Equations) — разновидность криптографической системы с открытым ключом, которая является частью многомерной криптографии. Также известна как односторонняя функция с потайным входом HFE. Данная система является обобщением системы Матцумото-Имаи и впервые была представлена Жаком Патарином в 1996 году на конференции Eurocrypt.[1]

Система скрытых уравнений поля основана на многочленах над конечными полями разного размера, чтобы замаскировать связь между закрытым ключом и открытым ключом.[2]

HFE на самом деле является семейством, которое состоит из основных HFE и комбинаций версий HFE. Семейство криптосистем HFE основано на трудности поиска решений системы многомерных квадратных уравнений (так называемой задаче MQ[3]), поскольку она использует частные аффинные преобразования, чтобы скрыть расширение поля и частные полиномы. Скрытые уравнения поля также использовались для построения схем цифровой подписи, таких как Quartz and Sflash.[2][1]

Основная идея[1]

[править | править код]

Функция

[править | править код]
  1. Пусть  — конечное поле размерности с характеристикой (обычно, но не обязательно ).
  2. Пусть  — расширение степени .
  3. Пусть , и  — элементы .
  4. Пусть , и  — целые.
  5. Наконец, пусть  — функция такая, что:

Тогда является многочленом от .

Пусть теперь будет базисом . Тогда выражение в базисе  :

где  — многочленов от переменных степени 2.

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

Инверсия

[править | править код]

Следует заметить, что не всегда является перестановкой . Однако основой алгоритма HFE является следующая теорема.

Теорема: Пусть  — конечное поле, причем с и «не слишком большими» (например, и ). Пусть  — заданный многочлен от над полем со степенью «не слишком большой» (например, ). Пусть  — элемент поля . Тогда всегда (на компьютере) можно найти все корни уравнения .

Представление сообщения

[править | править код]

В поле количество публичных элементов .

Каждое сообщение представлено значением , где  — строка из элементов поля . Таким образом, если , то каждое сообщение представлено битами. Более того, иногда предполагается, что в представление сообщений была помещена некоторая избыточность .

Шифрование

[править | править код]

Cекретная часть

[править | править код]
  1. Расширение поля степени .
  2. Функция :, которая была описана выше, с «не слишком большой» степенью .
  3. Два аффинных преобразования и :

Публичная часть

[править | править код]
  1. Поле c элементами и длина .
  2. многочленов размерности над полем .
  3. Способ добавления избыточности в сообщениях (то есть способ получения из ).

Основная идея построения семейства систем скрытых уравнений поля в качестве многомерной криптосистемы заключается в построении секретного ключа, начиная с полинома с одним неизвестным над некоторым конечным полем .[2] Этот полином может быть инвертирован над , то есть может быть найдено любое решение уравнения , если оно существует. Преобразование секрета, также как и расшифровка или/и подпись, основано на этой инверсии.

Как было сказано выше, можно идентифицировать системой уравнений , используя фиксированный базис. Для того чтобы построить криптосистему, полином должен быть преобразован таким образом, чтобы публичная информация скрывала первоначальную структуру и предотвращала инверсию. Это достигается рассмотрением конечных полей в качестве векторного пространства над и выбором двух линейных аффинных преобразований и . Триплет формирует приватный ключ. Приватный полином определён на . Публичным ключом является полином .[2]

Расширения HFE

[править | править код]

Скрытые уравнения поля имеют четыре основных модификации: +, -, v и f, и их можно комбинировать по-разному. Основной принцип заключается в следующем[2]:

  1. Модификация «+» состоит из линейного комбинирования публичных уравнений с некоторыми случайными уравнениями.
  2. Модификация «-» появился благодаря Ади-Шамиру и удаляет избыточность «» из публичных уравнений.
  3. Модификация «f» состоит из фиксации некоторых входных переменных открытого ключа.
  4. Модификация «v» определяется как сложная конструкция, такая что обратная функция может быть найдена только в том случае, если некоторые v переменных фиксированы. Эта идея принадлежит Жаку Патарину.

Атаки на криптосистемы HFE

[править | править код]

Две самые известные атаки на систему скрытых уравнений поля[4]:

  1. Получение закрытого ключа (Шамир-Кипнис): ключевым моментом этой атаки является восстановление закрытого ключа как разреженных одномерных многочленов над полем расширений . Атака работает только для базовой системы скрытых уравнений поля и не работает для всех её вариаций.
  2. Атака, основанная на алгоритме Грёбнера (разработана Жаном-Чарльзом Фужером): идея атаки заключается в использовании быстрого алгоритма для вычисления базиса Грёбнера системы полиномиальных уравнений. Фужер взломал HFE в рамках the HFE Challenge 1 за 96 часов в 2002 году. В 2003 году Фужер вместе с Жу работали над безопасностью HFE.

Примечания

[править | править код]
  1. 1 2 3 4 Jacques Patarin Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm. Дата обращения: 15 декабря 2017. Архивировано 2 февраля 2017 года.
  2. 1 2 3 4 5 Christopher Wolf and Bart Preneel, Asymmetric Cryptography: Hidden Field Equations. Дата обращения: 8 декабря 2017. Архивировано 10 августа 2017 года.
  3. Enrico Thomae and Christopher Wolf, Solving Systems of Multivariate Quadratic Equations over Finite Fields or: From Relinearization to MutantXL. Дата обращения: 8 декабря 2017. Архивировано 10 августа 2017 года.
  4. Nicolas T. Courtois, "The Security of Hidden Field Equations".