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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

Функция [math]\displaystyle{ f }[/math]

  1. Пусть [math]\displaystyle{ K }[/math] — конечное поле размерности [math]\displaystyle{ q }[/math] с характеристикой [math]\displaystyle{ p }[/math](обычно, но не обязательно [math]\displaystyle{ p = q = 2 }[/math]).
  2. Пусть [math]\displaystyle{ L_N }[/math] — расширение [math]\displaystyle{ K }[/math] степени [math]\displaystyle{ N }[/math].
  3. Пусть [math]\displaystyle{ \beta_{ij} }[/math], [math]\displaystyle{ \alpha_i }[/math] и [math]\displaystyle{ \mu_0 }[/math] — элементы [math]\displaystyle{ L_N }[/math].
  4. Пусть [math]\displaystyle{ \theta_{ij} }[/math], [math]\displaystyle{ \varphi_{ij} }[/math] и [math]\displaystyle{ \xi_i }[/math] — целые.
  5. Наконец, пусть [math]\displaystyle{ f }[/math] — функция такая, что:[math]\displaystyle{ L_N \mapsto L_N }[/math][math]\displaystyle{ f:x\mapsto\sum_{i,j}{\beta_{ij}x^{q^{\theta_{ij}} + q^{\varphi_{ij}}}} + \sum_i{\alpha_ix^{q^{\xi_i}}} + \mu_0 }[/math]

Тогда [math]\displaystyle{ f }[/math] является многочленом от [math]\displaystyle{ x }[/math].

Пусть теперь [math]\displaystyle{ B }[/math] будет базисом [math]\displaystyle{ L_N }[/math]. Тогда выражение [math]\displaystyle{ f }[/math] в базисе [math]\displaystyle{ B }[/math] :

[math]\displaystyle{ f(x_1, ..., x_N) = (p_1(x_1, ..., x_N), ..., p_N(x_1, ..., x_N)) }[/math]где [math]\displaystyle{ p_1,...,p_N }[/math] — [math]\displaystyle{ N }[/math] многочленов от [math]\displaystyle{ N }[/math] переменных степени 2.

Это верно, так как для любого целого [math]\displaystyle{ \lambda }[/math], [math]\displaystyle{ x\mapsto x^{q^\lambda} }[/math] является линейной функцией [math]\displaystyle{ L_N \mapsto L_N }[/math]. Многочлены [math]\displaystyle{ p_1,...,p_N }[/math] могут быть найдены путем выбора «представления» [math]\displaystyle{ L_N }[/math]. Такое «представление» обычно задается выбором неприводимого многочлена [math]\displaystyle{ i_N(X) }[/math] степени [math]\displaystyle{ N }[/math] над [math]\displaystyle{ K }[/math], поэтому мы можем задать [math]\displaystyle{ L_N }[/math] с помощью [math]\displaystyle{ K[X]/(i_N(X)) }[/math]. В этом случае возможно найти многочлены [math]\displaystyle{ p_1,...,p_N }[/math].

Инверсия [math]\displaystyle{ f }[/math]

Следует заметить, что [math]\displaystyle{ f }[/math] не всегда является перестановкой [math]\displaystyle{ L_N }[/math] . Однако основой алгоритма HFE является следующая теорема.

Теорема: Пусть [math]\displaystyle{ L_N }[/math] — конечное поле, причем [math]\displaystyle{ \mid{L_N}\mid = q^n }[/math] с [math]\displaystyle{ q }[/math] и [math]\displaystyle{ n }[/math] «не слишком большими» (например, [math]\displaystyle{ q\leq{64} }[/math] и [math]\displaystyle{ n\leq{1024} }[/math]). Пусть [math]\displaystyle{ f(x) }[/math] — заданный многочлен от [math]\displaystyle{ x }[/math] над полем [math]\displaystyle{ L_N }[/math] со степенью [math]\displaystyle{ d }[/math] «не слишком большой» (например, [math]\displaystyle{ d\leq{1024} }[/math]). Пусть [math]\displaystyle{ a }[/math] — элемент поля [math]\displaystyle{ L_N }[/math]. Тогда всегда (на компьютере) можно найти все корни уравнения [math]\displaystyle{ f(x)=a }[/math].

Шифрование[1]

Представление сообщения [math]\displaystyle{ M }[/math]

В поле [math]\displaystyle{ K }[/math] количество публичных элементов [math]\displaystyle{ q=p^m }[/math].

Каждое сообщение [math]\displaystyle{ M }[/math] представлено значением [math]\displaystyle{ x }[/math], где [math]\displaystyle{ x }[/math] — строка из [math]\displaystyle{ n }[/math] элементов поля [math]\displaystyle{ K }[/math]. Таким образом, если [math]\displaystyle{ p=2 }[/math], то каждое сообщение представлено [math]\displaystyle{ nm }[/math] битами. Более того, иногда предполагается, что в представление [math]\displaystyle{ x }[/math] сообщений была помещена некоторая избыточность [math]\displaystyle{ r }[/math].

Шифрование [math]\displaystyle{ x }[/math]

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

  1. Расширение [math]\displaystyle{ L_n }[/math] поля [math]\displaystyle{ K }[/math] степени [math]\displaystyle{ n }[/math].
  2. Функция [math]\displaystyle{ f }[/math]:[math]\displaystyle{ {L_n}\mapsto{L_n} }[/math], которая была описана выше, с «не слишком большой» степенью [math]\displaystyle{ d }[/math].
  3. Два аффинных преобразования [math]\displaystyle{ S }[/math] и [math]\displaystyle{ T }[/math]: [math]\displaystyle{ {K^n}\mapsto{K^n} }[/math]

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

  1. Поле [math]\displaystyle{ K }[/math] c [math]\displaystyle{ q=p^m }[/math] элементами и длина [math]\displaystyle{ n }[/math].
  2. [math]\displaystyle{ n }[/math] многочленов [math]\displaystyle{ (p_1,...,p_n) }[/math] размерности [math]\displaystyle{ n }[/math] над полем [math]\displaystyle{ K }[/math].
  3. Способ добавления избыточности [math]\displaystyle{ r }[/math] в сообщениях (то есть способ получения [math]\displaystyle{ x }[/math] из [math]\displaystyle{ M }[/math]).

Основная идея построения семейства систем скрытых уравнений поля в качестве многомерной криптосистемы заключается в построении секретного ключа, начиная с полинома [math]\displaystyle{ P }[/math] с одним неизвестным [math]\displaystyle{ x }[/math] над некоторым конечным полем [math]\displaystyle{ L_N }[/math].[2] Этот полином может быть инвертирован над [math]\displaystyle{ L_N }[/math], то есть может быть найдено любое решение уравнения [math]\displaystyle{ P(x)=y }[/math], если оно существует. Преобразование секрета, также как и расшифровка или/и подпись, основано на этой инверсии.

Как было сказано выше, [math]\displaystyle{ P }[/math] можно идентифицировать системой [math]\displaystyle{ n }[/math] уравнений [math]\displaystyle{ (p_1,...,p_n) }[/math], используя фиксированный базис. Для того чтобы построить криптосистему, полином [math]\displaystyle{ (p_1,...,p_n) }[/math] должен быть преобразован таким образом, чтобы публичная информация скрывала первоначальную структуру и предотвращала инверсию. Это достигается рассмотрением конечных полей [math]\displaystyle{ \mathbb{L}_{n} }[/math] в качестве векторного пространства над [math]\displaystyle{ \mathbb{K} }[/math] и выбором двух линейных аффинных преобразований [math]\displaystyle{ S }[/math] и [math]\displaystyle{ T }[/math]. Триплет [math]\displaystyle{ (S,P,T) }[/math] формирует приватный ключ. Приватный полином [math]\displaystyle{ P }[/math] определён на [math]\displaystyle{ \mathbb{L}_{n} }[/math]. Публичным ключом является полином [math]\displaystyle{ (p_1,...,p_n) }[/math].[2]

[math]\displaystyle{ M\overset{+r}{\to}x\overset{\text{секрет}: S}{\to}x'\overset{\text{секрет}: P}{\to}y'\overset{\text{секрет}: T}{\to}y }[/math]

Расширения HFE

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

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

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

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

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

Примечания

  1. ↑ 1,0 1,1 1,2 1,3 Jacques Patarin Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm. Дата обращения: 15 декабря 2017. Архивировано 2 февраля 2017 года.
  2. ↑ 2,0 2,1 2,2 2,3 2,4 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".

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Скрытые_уравнения_поля&oldid=5862614