XTR (алгоритм)

XTR (сокращение от ECSTR — «Efficient and Compact Subgroup Trace Representation») — алгоритм шифрования с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. Преимущества этого алгоритма перед другими, использующими эту идею, в более высокой скорости и меньшем размере ключа.

Данный алгоритм использует генератор $g$$g$ относительно малой подгруппы порядка $q$$q$ ($q$$q$ — простое) подгруппы $GF(p^6{)}^{\ast <!--\; \ast \; -->}$$GF(p^{6})^{*}$. При правильном выборе $q$$q$, дискретное логарифмирование в группе, порожденной $g$$g$, имеет ту же вычислительную сложность, что и в $GF(p^6{)}^{\ast <!--\; \ast \; -->}$$GF(p^{6})^{*}$. XTR использует арифметику $GF(p^2)$$GF(p^{2})$ вместо $GF(p^6)$$GF(p^{6})$, обеспечивая ту же защищенность, но с меньшими затратами на вычисления и передачу данных.

Теоретическая основа XTRПравить

Алгоритм работает в конечном поле $GF(p^6)$$GF(p^{6})$ . Рассмотрим группу порядка $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$ , и её подгруппу порядка q, где p — простое число, такое, что другое достаточно большое простое число q является делителем $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$ . Группа порядка q называется XTR-подгруппой. Эта циклическая группа $⟨<!--\; ⟨\; -->g⟩<!--\; ⟩\; -->$$\langle g\rangle$  является подгруппой $GF(p^6{)}^{\ast <!--\; \ast \; -->}$$GF(p^{6})^{*}$  и имеет генератор g.

Арифметические операции в $GF(p^2)$$GF(p^{2})$ Править

Пусть p — простое число, такое, что p ≡ 2 mod 3, а p² — p + 1 делится на достаточно большое простое q. Так как p² ≡ 1 mod 3, p порождает $(\mathbb{Z}/3\mathbb{Z}{)}^{\ast <!--\; \ast \; -->}$$(\mathbb {Z} /3\mathbb {Z} )^{*}$ . Таким образом, круговой многочлен ${\mathrm{\Phi <!--\; \Phi \; -->}}_3(x)=x^2+x+1$$\Phi _{3}(x)=x^{2}+x+1$  является неприводимым в $GF(p)$$GF(p)$ . Следовательно, корни $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$  и ${\mathrm{\alpha <!--\; \alpha \; -->}}^p$$\alpha ^{p}$  образуют оптимальный нормальный базис $GF(p^2)$$GF(p^{2})$  над $GF(p)$$GF(p)$  и

$GF(p^2)\cong <!--\; \cong \; -->\{x_1\mathrm{\alpha <!--\; \alpha \; -->}+x_2{\mathrm{\alpha <!--\; \alpha \; -->}}^p:x_1,x_2\in <!--\; \in \; -->GF(p)\}.$$GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.$ 

С учетом p ≡ 2 mod 3:

$GF(p^2)\cong <!--\; \cong \; -->\{y_1\mathrm{\alpha <!--\; \alpha \; -->}+y_2{\mathrm{\alpha <!--\; \alpha \; -->}}^2:{\mathrm{\alpha <!--\; \alpha \; -->}}^2+\mathrm{\alpha <!--\; \alpha \; -->}+1=0,y_1,y_2\in <!--\; \in \; -->GF(p)\}.$$GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1},y_{2}\in GF(p)\}.$ 

Таким образом, стоимость арифметических операций следующая:

• Вычисление x^p не требует умножения
• Вычисление x² требует двух операций умножения в $GF(p)$$GF(p)$ 
• Вычисление xy требует трех операций умножения в $GF(p)$$GF(p)$ 
• Вычисление xz-yzp требует четырёх операций умножения в $GF(p)$$GF(p)$ .:

Использование следов в $GF(p^2)$$GF(p^{2})$ Править

Элементами, сопряженными с $h\in <!--\; \in \; -->GF(p^6)$$h\in GF(p^{6})$  в $GF(p^2)$$GF(p^{2})$  являются: сам $h,h^{p^2}$$h,h^{p^{2}}$  и $h^{p^4}$$h^{p^{4}}$ , а их сумма — след $h$$h$ .

$Tr(h)=h+h^{p^2}+h^{p^4}.$$Tr(h)=h+h^{p^{2}}+h^{p^{4}}.$ 

Кроме того:

${\begin{aligned}Tr(h)^{p^{2}}&=h^{p^{2}}+h^{p^{4}}+h^{p^{6}}\\&=h+h^{p^{2}}+h^{p^{4}}\\&=Tr(h)\end{aligned}}$ 

Рассмотрим генератор $g$$g$  XTR-группы порядка $q$$q$ , где $q$$q$  — простое число. Так как $⟨<!--\; ⟨\; -->g⟩<!--\; ⟩\; -->$$\langle g\rangle$  — подгруппа группы порядка $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$ , то $q\mid <!--\; \mid \; -->p^2-<!--\; -\; -->p+1$$q\mid p^{2}-p+1$ . Кроме того,

$p^2=p-<!--\; -\; -->1$$p^{2}=p-1$ 

и

$p^4=(p-<!--\; -\; -->1{)}^2=p^2-<!--\; -\; -->2p+1=-<!--\; -\; -->p$$p^{4}=(p-1)^{2}=p^{2}-2p+1=-p$ .

Таким образом,

${\begin{aligned}Tr(g)&=g+g^{p^{2}}+g^{p^{4}}\\&=g+g^{p-1}+g^{-p}.\end{aligned}}$ 

Отметим также, что сопряженным к элементу $g$$g$  является $1$$1$ , то есть, $g$$g$  имеет норму равную 1. Ключевой особенностью XTR является то, что минимальный многочлен $g$$g$  в $GF(p^2)$$GF(p^{2})$ 

$(x-<!--\; -\; -->g)(x-<!--\; -\; -->g^{p-<!--\; -\; -->1})(x-<!--\; -\; -->g^{-<!--\; -\; -->p})$$(x-g)\!\ (x-g^{p-1})(x-g^{-p})$ 

упрощается до

$x^3-<!--\; -\; -->Tr(g)x^2+Tr(g{)}^{p}x-<!--\; -\; -->1$$x^{3}-Tr(g)\!\ x^{2}+Tr(g)^{p}x-1$ 

Иными словами, сопряженные с $g$$g$  элементы, как корни минимального многочлена в $GF(p^2)$$GF(p^{2})$ , полностью определяются следом $g$$g$ . Аналогичные рассуждения верны для любой степени $g$$g$ :

$x^3-<!--\; -\; -->Tr(g^n)x^2+Tr(g^n{)}^{p}x-<!--\; -\; -->1$$x^{3}-Tr(g^{n})\!\ x^{2}+Tr(g^{n})^{p}x-1$ 

— этот многочлен определяется следом $Tr(g^n)$$Tr(g^{n})$ .

Идея алгоритма в том, чтобы заменить $g^n\in <!--\; \in \; -->GF(p^6)$$g^{n}\in GF(p^{6})$  на $Tr(g^n)\in <!--\; \in \; -->GF(p^2)$$Tr(g^{n})\in GF(p^{2})$ , то есть вычислять $Tr(g^n)$$Tr(g^{n})$  по $Tr(g)$$Tr(g)$  вместо $g^n$$g^{n}$  по $g$$g$  Однако для того, чтобы метод был эффективен, необходим способ быстро получать $Tr(g^n)$$Tr(g^{n})$  по имеющемуся $Tr(g)$$Tr(g)$ .

Алгоритм быстрого вычисления $Tr(g^n)$$Tr(g^{n})$  по $Tr(g)$$Tr(g)$ Править

Определение: Для каждого $c$$c$  $GF(p^2)$$GF(p^{2})$  определим:

$F(c,X)=X^3-<!--\; -\; -->c{X}^2+c^{p}X-<!--\; -\; -->1\in <!--\; \in \; -->GF(p^2)[X].$$F(c,X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X].$ 

Определение: Пусть $h_0,h_1,h_2$$h_{0},\!\ h_{1},h_{2}$  — корни $F(c,X)$$F(c,X)$  в $GF(p^6)$$GF(p^{6})$ , а $n\in <!--\; \in \; -->\mathbb{Z}$$n\in {\mathbb {Z}}$ . Обозначим:

$c_n=h_0^n+h_1^n+h_2^n.$$c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.$ 

Свойства $c_n$$c_n$  и $F(c,X)$$F(c,X)$ :

1. $c=c_1$$c=c_{1}$ 
2. $c_{-<!--\; -\; -->n}=c_{np}=c_n^p$$c_{-n}=c_{np}=c_{n}^{p}$ 
3. $c_n\in <!--\; \in \; -->GF(p^2)$$c_{n}\in GF(p^{2})$  для $n\in <!--\; \in \; -->\mathbb{Z}$$n\in \mathbb {Z}$ 
4. $c_{u+v}=c_u{c}_v-<!--\; -\; -->c_v^p{c}_{u-<!--\; -\; -->v}+c_{u-<!--\; -\; -->2v}$$c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}$  для $u,v\in <!--\; \in \; -->\mathbb{Z}$$u,v\in \mathbb {Z}$ 
5. Либо все $h_j$$h_{j}$  имеют порядок, являющийся делителем $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$  и $>3$$>3$ , либо все $h_j$$h_{j}$  — в поле $GF(p^2)$$GF(p^{2})$ . В частности, $F(c,X)$$F(c,X)$  — неприводим тогда и только тогда, когда его корни имеют порядок, являющийся делителем $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$  и $>3$$>3$ .
6. $F(c,X)$$F(c,X)$  приводим в поле $GF(p^2)$$GF(p^{2})$  тогда и только тогда, когда $c_{p+1}\in <!--\; \in \; -->GF(p)$$c_{p+1}\in GF(p)$ 

Утверждение: Пусть даны $c,c_{n-<!--\; -\; -->1},c_n,c_{n+1}$$c,\!\ c_{n-1},c_{n},c_{n+1}$ .

1. Вычисление $c_{2n}=c_n^2-<!--\; -\; -->2c_n^p$$c_{2n}=c_{n}^{2}-2c_{n}^{p}$  требует двух операций произведения в поле $GF(p)$$GF(p)$ .
2. Вычисление $c_{n+2}=c_{n+1}\cdot <!--\; \cdot \; -->c-<!--\; -\; -->c^p\cdot <!--\; \cdot \; -->c_n+c_{n-<!--\; -\; -->1}$$c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}$  требует четырёх операций произведения в поле $GF(p)$$GF(p)$ .
3. Вычисление $c_{2n-<!--\; -\; -->1}=c_{n-<!--\; -\; -->1}\cdot <!--\; \cdot \; -->c_n-<!--\; -\; -->c^p\cdot <!--\; \cdot \; -->c_n^p+c_{n+1}^p$$c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}$  требует четырёх операций произведения в поле $GF(p)$$GF(p)$ .
4. Вычисление $c_{2n+1}=c_{n+1}\cdot <!--\; \cdot \; -->c_n-<!--\; -\; -->c\cdot <!--\; \cdot \; -->c_n^p+c_{n-<!--\; -\; -->1}^p$$c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}$  требует четырёх операций произведения в поле $GF(p)$$GF(p)$ .

Определение: Пусть $S_n(c)=(c_{n-<!--\; -\; -->1},c_n,c_{n+1})\in <!--\; \in \; -->GF(p^2{)}^3$$S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3}$ .

Алгоритм для вычисления $S_n(c)$$S_{n}(c)$  при заданных $n$$n$  и $c$$c$ Править

• При $n<0$  алгоритм применяется для $-<!--\; -\; -->n$$-n$  и $c$$c$ , затем используется свойство 2 для получения конечного результатаю
• При $n=0$$n=0$ , $S_0(c)=(c^p,3,c)$$S_{0}(c)\!\ =(c^{p},3,c)$ .
• При $n=1$$n=1$ , $S_1(c)=(3,c,c^2-<!--\; -\; -->2c^p)$$S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$ .
• При $n=2$$n=2$ , воспользуемся выражениями для $c_{n+2}=c_{n+1}\cdot <!--\; \cdot \; -->c-<!--\; -\; -->c^p\cdot <!--\; \cdot \; -->c_n+c_{n-<!--\; -\; -->1}$$c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}$  и $S_1(c)$$S_{1}(c)$ , чтобы найти $c_3$$c_{3}$  и, соответственно, $S_2(c)$$S_{2}(c)$ .
• При $n>2$$n>2$ , чтобы вычислить $S_n(c)$$S_{n}(c)$ , введем

${\stackrel{¯<!--\; ¯\; -->}{S}}_i(c)=S_{2i+1}(c)$${\bar {S}}_{i}(c)=S_{2i+1}(c)$ 

и $\stackrel{¯<!--\; ¯\; -->}{m}=n$${\bar {m}}=n$  если не $n$$n$  нечетно и $\stackrel{¯<!--\; ¯\; -->}{m}=n-<!--\; -\; -->1$${\bar {m}}=n-1$  если четно. Положим $\stackrel{¯<!--\; ¯\; -->}{m}=2m+1,k=1$${\bar {m}}=2m+1,k=1$  и найдем ${\stackrel{¯<!--\; ¯\; -->}{S}}_k(c)=S_3(c)$${\bar {S}}_{k}(c)=S_{3}(c)$ , используя Утверждение, и $S_2(c)$$S_{2}(c)$ . Пусть, в дальнейшем,

$m=\underset{j=0}{\overset{r}{\sum <!--\; \sum \; -->}}{m}_j{2}^j$$m=\sum _{j=0}^{r}m_{j}2^{j}$ 

где $m_j\in <!--\; \in \; -->0,1$$m_{j}\in {0,1}$  и $m_r=1$$m_{r}=1$ . Для $j=r-<!--\; -\; -->1,r-<!--\; -\; -->2,...,0$$j=r-1,r-2,...,0$  последовательно выполним следующее:

• При $m_j=0$$m_{j}=0$ , воспользуемся ${\stackrel{¯<!--\; ¯\; -->}{S}}_k(c)$${\bar {S}}_{k}(c)$  чтобы найти ${\stackrel{¯<!--\; ¯\; -->}{S}}_{2k}(c)$${\bar {S}}_{2k}(c)$ .
• При $m_j=1$$m_{j}=1$ , воспользуемся ${\stackrel{¯<!--\; ¯\; -->}{S}}_k(c)$${\bar {S}}_{k}(c)$  чтобы найти ${\stackrel{¯<!--\; ¯\; -->}{S}}_{2k+1}(c)$${\bar {S}}_{2k+1}(c)$ .
• Заменим $k$$k$  на $2k+m_j$$2k+m_{j}$ .

По завершении итераций, $k=m$$k=m$ , а $S_{\stackrel{¯<!--\; ¯\; -->}{m}}(c)={\stackrel{¯<!--\; ¯\; -->}{S}}_m(c)$$S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ . Если n — четно, воспользуемся $S_{\stackrel{¯<!--\; ¯\; -->}{m}}(c)$$S_{\bar {m}}(c)$  чтобы найти ${\stackrel{¯<!--\; ¯\; -->}{S}}_{m+1}(c)$${\bar {S}}_{m+1}(c)$ .

Выбор параметровПравить

Выбор поля и размера подгруппыПравить

Чтобы воспользоваться преимуществами представления элементов групп в виде их следов и обеспечить достаточную защищенность данных, необходимо найти простые $p$$p$  и $q$$q$ , где $p$$p$  — характеристика поля $GF(p^6)$$GF(p^{6})$ , причем $p\equiv <!--\; \equiv \; -->2\text{mod}3$$p\equiv 2\ {\text{mod}}\ 3$ , а $q$$q$  — размер подгруппы и делитель $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$ . Обозначим как $P$$P$  и $Q$$Q$  размеры $p$$p$  и $q$$q$  в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать $P$$P$  таким, что $6P>1024$$6P>1024$ , то есть $P\approx <!--\; \approx \; -->170$$P\approx 170$  а $Q$$Q$  может быть около 160. Первый алгоритм, который позволяет вычислить такие простые $p$$p$  и $q$$q$  — Алгоритм А.

Алгоритм А

1. Найдём $r\in <!--\; \in \; -->\mathbb{Z}$$r\in \mathbb {Z}$  такое, что число $q=r^2-<!--\; -\; -->r+1$$q=r^{2}-r+1$  — простое число длиной в $Q$$Q$  бит.
2. Найдем $k\in <!--\; \in \; -->\mathbb{Z}$$k\in\mathbb{Z}$  такое, что число $p=r+k\cdot <!--\; \cdot \; -->q$$p=r+k\cdot q$  — простое длиной $P$$P$  бит, а также $p\equiv <!--\; \equiv \; -->2\text{mod}3$$p\equiv 2\ {\text{mod}}\ 3$ .

Корректность Алгоритма А:

Необходимо проверить лишь то, что $q\mid <!--\; \mid \; -->p^2-<!--\; -\; -->p+1$$q\mid p^{2}-p+1$ , так как все оставшиеся свойства очевидно выполнены из-за специфики выбора $p$$p$  и $q$$q$ .

Нетрудно заметить, что $p^2-<!--\; -\; -->p+1=r^2+2rkq+k^2{q}^2-<!--\; -\; -->r-<!--\; -\; -->kq+1=r^2-<!--\; -\; -->r+1+q(2rk+k^{2}q-<!--\; -\; -->k)=q(1+2rk+k^{2}q-<!--\; -\; -->k)$$p^{2}-p+1=r^{2}+2rkq+k^{2}q^{2}-r-kq+1=r^{2}-r+1+q(2rk+k^{2}q-k)=q(1+2rk+k^{2}q-k)$ , значит $q\mid <!--\; \mid \; -->p^2-<!--\; -\; -->p+1$$q\mid p^{2}-p+1$ .

Алгоритм А очень быстрый, однако может быть небезопасен, так как уязвим против атаки с использованием решета числового поля.

От этого недостатка избавлен более медленный Алгоритм Б.

Алгоритм Б

1. Выберем простое число $q$$q$  длиной в $Q$$Q$  бит, такое, что $q\equiv <!--\; \equiv \; -->7\text{mod}12$$q\equiv 7\ {\text{mod}}\ 12$ .
2. Найдем корни $r_1$$r_{1}$  и $r_2$$r_{2}$  $X^2-<!--\; -\; -->X+1\text{mod}q$$X^{2}-X+1\ {\text{mod}}\ q$ .
3. Найдем $k\in <!--\; \in \; -->\mathbb{Z}$$k\in\mathbb{Z}$  такое, что $p=r_i+k\cdot <!--\; \cdot \; -->q$$p=r_{i}+k\cdot q$ , $p$$p$ - простое $P$$P$ -битовое число и при этом $p\equiv <!--\; \equiv \; -->2\text{mod}3$$p\equiv 2\ {\text{mod}}\ 3$  для $i\in <!--\; \in \; -->\{1,2\}$$i\in \{1,2\}$ 

Корректность Алгоритма Б:

Как только мы выбираем $q\equiv <!--\; \equiv \; -->7\text{mod}12$$q\equiv 7\ {\text{mod}}\ 12$ , автоматически выполняется условие $q\equiv <!--\; \equiv \; -->1\text{mod}3$$q\equiv 1\ {\text{mod}}\ 3$  (Так как $7\equiv <!--\; \equiv \; -->1\text{mod}3$$7\equiv 1\ {\text{mod}}\ 3$  и $3\mid <!--\; \mid \; -->12$$3\mid 12$ ). Из этого утверждения и квадратичного закона взаимности следует, что корни $r_1$$r_{1}$  и $r_2$$r_{2}$  существуют.

Чтобы проверить, что $q\mid <!--\; \mid \; -->p^2-<!--\; -\; -->p+1$$q\mid p^{2}-p+1$  снова рассмотрим $p^2-<!--\; -\; -->p+1$$p^{2}-p+1$  для $r_i\in <!--\; \in \; -->\{1,2\}$$r_{i}\in \{1,2\}$  и заметим, что $p^2-<!--\; -\; -->p+1=r_i^2+2r_{i}kq+k^2{q}^2-<!--\; -\; -->r_i-<!--\; -\; -->kq+1=r_i^2-<!--\; -\; -->r_i+1+q(2rk+k^{2}q-<!--\; -\; -->k)=q(2rk+k^{2}q-<!--\; -\; -->k)$$p^{2}-p+1=r_{i}^{2}+2r_{i}kq+k^{2}q^{2}-r_{i}-kq+1=r_{i}^{2}-r_{i}+1+q(2rk+k^{2}q-k)=q(2rk+k^{2}q-k)$ .Значит $r_1$$r_{1}$  и $r_2$$r_{2}$  -корни $X^2-<!--\; -\; -->X+1$$X^{2}-X+1$  и, следовательно, $q\mid <!--\; \mid \; -->p^2-<!--\; -\; -->p+1$$q\mid p^{2}-p+1$ .

Выбор подгруппыПравить

В предыдущем разделе мы нашли размеры $p$$p$  и $q$$q$  конечного поля $GF(p^6)$$GF(p^{6})$  и мультипликативной подгруппы в $GF(p^6{)}^{\ast <!--\; \ast \; -->}$$GF(p^{6})^{*}$ . Теперь следует найти подгруппу $⟨<!--\; ⟨\; -->g⟩<!--\; ⟩\; -->$$\langle g\rangle$  в $GF(p^6{)}^{\ast <!--\; \ast \; -->}$$GF\!\ (p^{6})^{*}$  для некоторых $g\in <!--\; \in \; -->GF(p^6)$$g\in GF(p^{6})$  таких, что $\mid <!--\; \mid \; -->⟨<!--\; ⟨\; -->g⟩<!--\; ⟩\; -->\mid <!--\; \mid \; -->=q$$\mid \!\!\langle g\rangle \!\!\mid =q$ . Однако, необязательно искать явный элемент $g\in <!--\; \in \; -->GF(p^6)$$g\in GF(p^{6})$ , достаточно найти элемент $c\in <!--\; \in \; -->GF(p^2)$$c\in GF(p^{2})$  такой, что $c=Tr(g)$$c=Tr(g)$  для элемента $g\in <!--\; \in \; -->GF(p^6)$$g\in GF(p^{6})$  порядка $q$$q$ . Но при данном $Tr(g)$$Tr(g)$ , генератор $g$$g$  XTR-группы может быть найден путём нахождения корня $F(Tr(g),X)$$F(Tr(g),\ X)$ . Чтобы найти это $c$$c$ , рассмотрим свойство 5 $F(c,X)$$F(c,\ X)$ . Найдя такое $c$$c$  следует проверить, действительно ли оно порядка $q$$q$ , однако сначала нужно выбрать c\in GF(p²), такое, что F(c,\ X) — неприводимо. Простейший подход в том, чтобы выбирать $c\in <!--\; \in \; -->GF(p^2)\mathrm{\setminus <!--\; \setminus \; -->}GF(p)$$c\in GF(p^{2})\backslash GF(p)$  случайным образом.

Утверждение: Для случайно выбранного $c\in <!--\; \in \; -->GF(p^2)$$c\in GF(p^{2})$  вероятность, что $F(c,X)=X^3-<!--\; -\; -->c{X}^2+c^{p}X-<!--\; -\; -->1\in <!--\; \in \; -->GF(p^2)[X]$$F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$  — неприводимо, больше 1/3.

Базовый алгоритм для поиска $Tr(g)$$Tr(g)$ :

1. Выберем случайное $c\in <!--\; \in \; -->GF(p^2)\mathrm{\setminus <!--\; \setminus \; -->}GF(p)$$c\in GF(p^{2})\backslash GF(p)$ .
2. Если $F(c,X)$$F(c,\ X)$  — приводим, вернемся на первый шаг.
3. Воспользуемся алгоритмом для поиска $S_n(c)$$S_{n}(c)$ . Найдем $d=c_{(p^2-<!--\; -\; -->p+1)/q}$$d=c_{(p^{2}-p+1)/q}$ .
4. Если $d$$d$  имеет порядок не равный $q$$q$ , вернемся на первый шаг.
5. Пусть $Tr(g)=d$$Tr(g)=d$ .

Данный алгоритм вычисляет элемент поля $GF(p^2)$$GF(p^{2})$  эквивалентный $Tr(g)$$Tr(g)$  для некоторых $g\in <!--\; \in \; -->GF(p^6)$$g\in GF(p^{6})$  порядка $q$$q$ .

ПримерыПравить

Протокол Диффи-ХеллманаПравить

Предположим, у Алисы и Боба есть открытый XTR-ключ $\left(p,q,Tr(g)\right)$$\left(p,q,Tr(g)\right)$  и они хотят сгенерировать общий закрытый ключ $K$$K$ .

1. Алиса выбирает случайное число $a\in <!--\; \in \; -->\mathbb{Z}$$a\in \mathbb {Z}$  такое, что $1<a<q-2$ , вычисляет $S_a(Tr(g))=\left(Tr(g^{a-<!--\; -\; -->1}),Tr(g^a),Tr(g^{a+1})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}$  и посылает $Tr(g^a)\in <!--\; \in \; -->GF(p^2)$$Tr(g^{a})\in GF(p^{2})$  Бобу.
2. Боб получает $Tr(g^a)$$Tr(g^{a})$  от Алисы, выбирает случайное $b\in <!--\; \in \; -->\mathbb{Z}$$b\in \mathbb {Z}$  такое, что $1<b<q-2$ , вычисляет $S_b(Tr(g))=\left(Tr(g^{b-<!--\; -\; -->1}),Tr(g^b),Tr(g^{b+1})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}$  и посылает $Tr(g^b)\in <!--\; \in \; -->GF(p^2)$$Tr(g^{b})\in GF(p^{2})$  Алисе.
3. Алиса получает $Tr(g^b)$$Tr(g^{b})$  от Боба, вычисляет $S_a(Tr(g^b))=\left(Tr(g^{(a-<!--\; -\; -->1)b}),Tr(g^{ab}),Tr(g^{(a+1)b})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{a}(Tr(g^{b}))=\left(Tr(g^{(a-1)b}),Tr(g^{ab}),Tr(g^{(a+1)b})\right)\in GF(p^{2})^{3}$  и получает $Tr(g^{ab})\in <!--\; \in \; -->GF(p^2)$$Tr(g^{ab})\in GF(p^{2})$  — закрытый ключ $K$$K$ .
4. Точно так же, Боб вычисляет $S_b(Tr(g^a))=\left(Tr(g^{a(b-<!--\; -\; -->1)}),Tr(g^{ab}),Tr(g^{a(b+1)})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{b}(Tr(g^{a}))=\left(Tr(g^{a(b-1)}),Tr(g^{ab}),Tr(g^{a(b+1)})\right)\in GF(p^{2})^{3}$  и получает $Tr(g^{ab})\in <!--\; \in \; -->GF(p^2)$$Tr(g^{ab})\in GF(p^{2})$  — закрытый ключ $K$$K$ .

Схема Эль-ГамаляПравить

Предположим, у Алисы есть часть публичного ключа XTR: $(p,q,Tr(g))$$(p,q,Tr(g))$ . Алиса выбирает секретное целое число $k$$k$  и вычисляет и публикует $Tr(g^k)$$Tr(g^{k})$ . Получив публичный ключ Алисы $\left(p,q,Tr(g),Tr(g^k)\right)$$\left(p,q,Tr(g),Tr(g^{k})\right)$ , Боб может зашифровать сообщение $M$$M$ , предназначенное Алисе, используя следующий алгоритм:

1. Боб выбирает случайное $b\in <!--\; \in \; -->\mathbb{Z}$$b\in \mathbb {Z}$  такое, что $1<b<q-2$  и вычисляет $S_b(Tr(g))=\left(Tr(g^{b-<!--\; -\; -->1}),Tr(g^b),Tr(g^{b+1})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}$ .
2. Затем Боб вычисляет$S_b(Tr(g^k))=\left(Tr(g^{(b-<!--\; -\; -->1)k}),Tr(g^{bk}),Tr(g^{(b+1)k})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{b}(Tr(g^{k}))=\left(Tr(g^{(b-1)k}),Tr(g^{bk}),Tr(g^{(b+1)k})\right)\in GF(p^{2})^{3}$ .
3. Боб определяет симметричный ключ $K$$K$  основанный на $Tr(g^{bk})\in <!--\; \in \; -->GF(p^2)$$Tr(g^{bk})\in GF(p^{2})$ .
4. Боб шифрует сообщение $M$$M$  ключом $K$$K$ , получая зашифрованное сообщение $E$$E$ .
5. Пару $(Tr(g^b),E)$$(Tr(g^{b}),\ E)$  Боб посылает Алисе.

Получив пару $(Tr(g^b),E)$$(Tr(g^{b}),\ E)$ , Алиса расшифровывает её следующим образом:

1. Алиса вычисляет $S_k(Tr(g^b))=\left(Tr(g^{b(k-<!--\; -\; -->1)}),Tr(g^{bk}),Tr(g^{b(k+1)})\right)\in <!--\; \in \; -->GF(p^2{)}^3$$S_{k}(Tr(g^{b}))=\left(Tr(g^{b(k-1)}),Tr(g^{bk}),Tr(g^{b(k+1)})\right)\in GF(p^{2})^{3}$ .
2. Алиса определяет симметричный ключ $K$$K$  основанный на $Tr(g^{bk})\in <!--\; \in \; -->GF(p^2)$$Tr(g^{bk})\in GF(p^{2})$ .
3. Зная, что алгоритм шифрования сообщения — симметричный, Алиса ключом $K$$K$  расшифровывает $E$$E$ , получая исходное сообщение $M$$M$ .

Таким образом, сообщение передано.