WikiSort.ru - Не сортированное

Функция ${\displaystyle f}$

1. Пусть ${\displaystyle K}$  — конечное поле размерности ${\displaystyle q}$ с характеристикой ${\displaystyle p}$ (обычно, но не обязательно ${\displaystyle p=q=2}$ ).
2. Пусть ${\displaystyle L_{N}}$  — расширение ${\displaystyle K}$ степени ${\displaystyle N}$ .
3. Пусть ${\displaystyle \beta _{ij}}$ , ${\displaystyle \alpha _{i}}$ и ${\displaystyle \mu _{0}}$  — элементы ${\displaystyle L_{N}}$ .
4. Пусть ${\displaystyle \theta _{ij}}$ , ${\displaystyle \varphi _{ij}}$ и ${\displaystyle \xi _{i}}$  — целые.
5. Наконец, пусть ${\displaystyle f}$  — функция такая, что:
   $${\displaystyle L_{N}\mapsto L_{N}}$$

   
   $${\displaystyle f:x\mapsto \sum _{i,j}{\beta _{ij}x^{q^{\theta _{ij}}+q^{\varphi _{ij}}}}+\sum _{i}{\alpha _{i}x^{q^{\xi _{i}}}}+\mu _{0}}$$

   

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

Пусть теперь ${\displaystyle B}$ будет базисом ${\displaystyle L_{N}}$ . Тогда выражение ${\displaystyle f}$ в базисе ${\displaystyle B}$  :

$${\displaystyle f(x_{1},...,x_{N})=(p_{1}(x_{1},...,x_{N}),...,p_{N}(x_{1},...,x_{N}))}$$

где ${\displaystyle p_{1},...,p_{N}}$  — ${\displaystyle N}$ многочленов от ${\displaystyle N}$ переменных степени 2.

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

Инверсия ${\displaystyle f}$

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

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

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

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

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

Шифрование ${\displaystyle x}$