XTR

Чтобы узнать о компании, см. XTR (компания) .

В криптографии . XTR это алгоритм шифрования с открытым ключом — XTR означает «ECSTR», что является аббревиатурой от «Эффективное и компактное представление трассировки подгруппы». Это метод представления элементов подгруппы мультипликативной группы конечного поля . этого он использует трассировку Для $GF(p^{2})$ представлять элементы подгруппы $GF(p^{6})^{*}$.

С точки зрения безопасности XTR опирается на сложность решения проблем, связанных с дискретным логарифмом , в полной мультипликативной группе конечного поля. В отличие от многих криптографических протоколов, основанных на генераторе полной мультипликативной группы конечного поля, XTR использует генератор $g$ относительно небольшой подгруппы некоторого простого порядка $q$ из подгруппы $GF(p^{6})^{*}$. При правильном выборе $q$, вычисляя дискретные логарифмы в группе, сгенерированной $g$, в общем, так же сложно, как и в $GF(p^{6})^{*}$ и, следовательно, криптографические приложения XTR используют $GF(p^{2})$ арифметика при достижении полного $GF(p^{6})$ безопасность, что приводит к существенной экономии затрат на связь и вычисления без ущерба для безопасности. Некоторые другие преимущества XTR — это быстрое создание ключей, малые размеры ключей и скорость.

Основы XTR

XTR использует подгруппу , обычно называемую подгруппой XTR или просто группой XTR , подгруппы, называемой супергруппой XTR , мультипликативной группы конечного поля. $GF(p^{6})$ с $p^{6}$ элементы. Супергруппа XTR в порядке $p^{2}-p+1$, где p — такое простое число, что достаточно большое простое число q делит $p^{2}-p+1$. Подгруппа XTR теперь имеет порядок q и является подгруппой $GF(p^{6})^{*}$, циклическая группа $\langle g\rangle$ с генератором g . В следующих трех абзацах будет описано, как элементы супергруппы XTR могут быть представлены с помощью элемента $GF(p^{2})$ вместо элемента $GF(p^{6})$ и как происходят арифметические действия в $GF(p^{2})$ вместо того, чтобы в $GF(p^{6})$.

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

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

$GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.$

Учитывая, что p ≡ 2 по модулю 3, мы можем уменьшить показатели степени по модулю 3, чтобы получить

$GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1},y_{2}\in GF(p)\}.$

Стоимость арифметических операций теперь указана в следующей лемме, помеченной как Лемма 2.21 в «Обзоре системы открытых ключей XTR» :

Лемма

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

Следы над $GF(p^{2})$

Трассировка . в XTR всегда считается завершенной $GF(p^{2})$. словами, конъюгаты Другими $h\in GF(p^{6})$ над $GF(p^{2})$ являются $h,h^{p^{2}}$ и $h^{p^{4}}$ и след $h$ их сумма:

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

Обратите внимание, что $Tr(h)\in GF(p^{2})$ с

${\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$ подгруппы XTR простого порядка $q$. Помните, что $\langle g\rangle$ является подгруппой супергруппы XTR порядка $p^{2}-p+1$, так $q\mid p^{2}-p+1$. В следующем разделе мы увидим, как выбрать $p$ и $q$, но пока достаточно предположить, что $q>3$. Чтобы вычислить след $g$ обратите внимание, что по модулю $p^{2}-p+1$ у нас есть

$p^{2}=p-1$ и

$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$ равно $1$,то есть, что $g$ имеет норму 1.

Важнейшее наблюдение в XTR заключается в том, что минимальный полином от $g$ над $GF(p^{2})$

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

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

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

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

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

и этот полином полностью определяется $Tr(g^{n})$.

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

Алгоритм быстрого расчета $Tr(g^{n})$ данный $Tr(g)$

А. Ленстра и Э. Верхёль описывают этот алгоритм в своей статье под названием « Система открытых ключей XTR» . Все определения и леммы, необходимые для алгоритма, а также сам алгоритм, представленные здесь, взяты из этой статьи.

Определение Для c в $GF(p^{2})$ определять

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

Определение Пусть $h_{0},\!\ h_{1},h_{2}$ обозначают (не обязательно различные) корни $F(c,X)$ в $GF(p^{6})$ и пусть $n$ быть внутри $\mathbb {Z}$. Определять

$c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.$

Свойства $c_{n}$ и $F(c,X)$

1. $c=c_{1}$
2. $c_{-n}=c_{np}=c_{n}^{p}$
3. $c_{n}\in GF(p^{2}){\text{ for }}n\in \mathbb {Z}$
4. $c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}{\text{ for }}u,v\in \mathbb {Z}$
5. Либо все $h_{j}$ иметь порядок деления $p^{2}-p+1$ и $>3$ или все $h_{j}$ находятся в $GF(p^{2})$. В частности, $F(c,X)$ неприводим тогда и только тогда, когда его корни имеют порядок погружения $p^{2}-p+1$ и $>3$.
6. $F(c,X)$ является приводимым к $GF(p^{2})$ тогда и только тогда, когда $c_{p+1}\in GF(p)$

Лемма Позволять $c,\!\ c_{n-1},c_{n},c_{n+1}$ быть дано.

1. Вычисление $c_{2n}=c_{n}^{2}-2c_{n}^{p}$ принимает два умножения $GF(p)$.
2. Вычисление $c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}$ занимает четыре умножения $GF(p)$.
3. Вычисление $c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}$ занимает четыре умножения $GF(p)$.
4. Вычисление $c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}$ занимает четыре умножения $GF(p)$.

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

Алгоритм 1 расчета $S_{n}(c)$ данный $n$ и $c$

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

${\bar {S}}_{i}(c)=S_{2i+1}(c)$

и ${\bar {m}}=n$ если n нечетно и ${\bar {m}}=n-1$ в противном случае. Позволять ${\bar {m}}=2m+1,k=1$ и вычислить ${\bar {S}}_{k}(c)=S_{3}(c)$ используя лемму выше и $S_{2}(c)$. Пусть дальше

$m=\sum _{j=0}^{r}m_{j}2^{j}$

с $m_{j}\in {0,1}$ и $m_{r}=1$. Для $j=r-1,r-2,...,0$ последовательно выполните следующие действия:

• Если $m_{j}=0$, использовать ${\bar {S}}_{k}(c)$ вычислить ${\bar {S}}_{2k}(c)$.
• Если $m_{j}=1$, использовать ${\bar {S}}_{k}(c)$ вычислить ${\bar {S}}_{2k+1}(c)$.
• Заменять $k$ к $2k+m_{j}$.

Когда эти итерации завершатся, $k=m$ и $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$. Если n даже использовать $S_{\bar {m}}(c)$ вычислить ${\bar {S}}_{m+1}(c)$.

Выбор параметра

Конечный выбор размера поля и подгруппы

Чтобы воспользоваться описанными выше представлениями элементов с их следами и, кроме того, обеспечить достаточную безопасность, о которой пойдет речь ниже , нам необходимо найти простые числа $p$ и $q$, где $p$ обозначает характеристику поля $GF(p^{6})$ с $p\equiv 2\ {\text{mod}}\ 3$ и $q$ - размер подгруппы, такой, что $q$ делит $p^{2}-p+1$.

Обозначим через $P$ и $Q$ размеры $p$ и $q$ в битах. Чтобы добиться безопасности, сравнимой с 1024-битным RSA , нам следует выбрать $6P$ около 1024, т.е. $P\approx 170$ и $Q$ может быть около 160.

Первый простой алгоритм для вычисления таких простых чисел $p$ и $q$ следующий алгоритм А:

Алгоритм А

1. Находить $r\in \mathbb {Z}$ такой, что $q=r^{2}-r+1$ это $Q$-битное простое число.
2. Находить $k\in \mathbb {Z}$ такой, что $p=r+k\cdot q$ это $P$-битное простое число с $p\equiv 2\ {\text{mod}}\ 3$.

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

Осталось это проверить $q\mid p^{2}-p+1$ поскольку все остальные необходимые свойства очевидно удовлетворяются по определению $p$ и $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)$ что подразумевает, что $q\mid p^{2}-p+1$.

Алгоритм А очень быстрый и может использоваться для поиска простых чисел. $p$ которые удовлетворяют полиному второй степени с малыми коэффициентами. Такой $p$ привести к быстрым арифметическим операциям в $GF(p)$. В частности, если поиск $k$ ограничивается $k=1$, что означает поиск $r$ такой, что оба $r^{2}-r+1{\text{ and }}r^{2}+1$ являются простыми и такими, что $r^{2}+1\equiv 2{\text{ mod }}3$, простые числа $p$ иметь эту красивую форму.Обратите внимание, что в этом случае $r$ должно быть четным и $r\equiv 1{\text{ mod }}4$.

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

Следующий алгоритм B не имеет этого недостатка, но он также не имеет быстрой арифметики по модулю. $p$ В этом случае алгоритм А имеет такое значение.

Алгоритм Б

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

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

Поскольку мы выбрали $q\equiv 7\ {\text{mod}}\ 12$ отсюда сразу следует, что $q\equiv 1\ {\text{mod}}\ 3$ (потому что $7\equiv 1\ {\text{mod}}\ 3$ и $3\mid 12$). Из этого и квадратичной взаимности мы можем сделать вывод, что $r_{1}$ и $r_{2}$ существовать.

Чтобы проверить это $q\mid p^{2}-p+1$ мы рассмотрим еще раз $p^{2}-p+1$ для $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)$, с $r_{1}$ и $r_{2}$ являются корнями $X^{2}-X+1$ и, следовательно, $q\mid p^{2}-p+1$.

Выбор подгруппы

В последнем пункте мы выбрали размеры $p$ и $q$ конечного поля $GF(p^{6})$ и мультипликативная подгруппа $GF(p^{6})^{*}$, теперь нам нужно найти подгруппу $\langle g\rangle$ из $GF\!\ (p^{6})^{*}$ для некоторых $g\in GF(p^{6})$ такой, что $\mid \!\!\langle g\rangle \!\!\mid =q$.

Однако нам не нужно искать явного $g\in GF(p^{6})$, достаточно найти элемент $c\in GF(p^{2})$ такой, что $c=Tr(g)$ для элемента $g\in GF(p^{6})$ порядка $q$. Но, учитывая $Tr(g)$, генератор $g$ (под)группы XTR можно найти, определив любой корень из $F(Tr(g),\ X)$ что было определено выше . Чтобы найти такого $c$ мы можем взглянуть на свойство 5 из $F(c,\ X)$ здесь говорится, что корни $F(c,\ X)$ иметь порядок деления $p^{2}-p+1$ тогда и только тогда, когда $F(c,\ X)$ является нередуцируемым . После нахождения такого $c$ нам нужно проверить, действительно ли это в порядке $q$, но сначала сосредоточимся на том, как выбрать $c\in GF(p^{2})$ такой, что $F(c,\ X)$ является нередуцируемым.

Первоначальный подход заключается в выборе $c\in GF(p^{2})\backslash GF(p)$ случайным образом, что подтверждается следующей леммой.

Лемма: Для случайно выбранного $c\in GF(p^{2})$ вероятность того, что $F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$ неуменьшаема, составляет около трети.

Теперь основной алгоритм поиска подходящего $Tr(g)$ заключается в следующем:

Краткое описание алгоритма

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

Оказывается, этот алгоритм действительно вычисляет элемент $GF(p^{2})$ это равно $Tr(g)$ для некоторых $g\in GF(p^{6})$ порядка $q$.

Более подробную информацию об алгоритме, его корректности, времени выполнения и доказательстве леммы можно найти в «Обзоре системы открытых ключей XTR» .

Криптографические схемы

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

Ключевое соглашение XTR-DH

Мы предполагаем, что и Алиса, и Боб имеют доступ к открытого ключа XTR. данным $\left(p,q,Tr(g)\right)$ и намерены договориться об общем секретном ключе $K$. Они могут сделать это, используя следующую версию XTR обмена ключами Диффи-Хеллмана:

1. Алиса выбирает $a\in \mathbb {Z}$ случайно с $1<a<q-2$, вычисляется по алгоритму 1 $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 GF(p^{2})$ Бобу.
2. Боб получает $Tr(g^{a})$ от Алисы, выбирает случайным образом $b\in \mathbb {Z}$ с $1<b<q-2$, применяет алгоритм 1 для вычисления $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 GF(p^{2})$ к Алисе.
3. Алиса получает $Tr(g^{b})$ от Боба, вычисляет по алгоритму 1 $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}$ и определяет $K$ на основе $Tr(g^{ab})\in GF(p^{2})$.
4. Боб аналогичным образом применяет алгоритм 1 для вычисления $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}$ а также определяет $K$ на основе $Tr(g^{ab})\in GF(p^{2})$.

Шифрование XTR Эль-Гамаля

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

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

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

В более традиционном шифровании Эль-Гамаля сообщение ограничено пространством ключей, которое здесь будет $GF(p^{2})$, потому что $Tr(g)\in GF(p^{2})\ \forall p\in GF(p^{6})^{*}$. Шифрование в данном случае представляет собой перемножение сообщения на ключ, что является обратимой операцией в пространстве ключей. $GF(p^{2})$.

Конкретно это означает, что если Боб хочет зашифровать сообщение $M\!\ '$, сначала он должен преобразовать его в элемент $M$ из $GF(p^{2})$ а затем вычислить зашифрованное сообщение $E$ как $E=K\cdot M\in GF(p^{2})$.При получении зашифрованного сообщения $E$ Алиса может восстановить исходное сообщение $M$ путем вычисления $M=E\cdot K^{-1}$, где $K^{-1}$ является обратным $K$ в $GF(p^{2})$.

Безопасность

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

Дискретные логарифмы в общем $GF\left(p^{t}\right)$

Пусть сейчас $\langle \gamma \rangle$ быть мультипликативной группой порядка $\omega$. Безопасность протокола Диффи-Хеллмана в $\langle \gamma \rangle$ опирается на задачу Диффи-Хеллмана (DH) о вычислении $\gamma ^{xy}{\text{ given }}\gamma ,\gamma ^{x}{\text{ and }}\gamma ^{y}$. Мы пишем $DH(\gamma ^{x},\ \gamma ^{y})=\gamma ^{xy}$.Есть еще две проблемы, связанные с проблемой ЦТ. Первая из них — это задача решения Диффи–Хеллмана (DHD), позволяющая определить, $c=DH(a,b)$ для данного $a,b,c\in \langle \gamma \rangle$ а вторая — задача дискретного логарифма (DL), позволяющая найти $x=DL(a)$ для данного $a=\gamma ^{x}\in \langle \gamma \rangle {\text{ with }}0\leq x<\omega$.

Проблема DL, по крайней мере, так же сложна, как и проблема DH, и обычно предполагается, что если проблема DL в $\langle \gamma \rangle$ неразрешима, то же самое можно сказать и о двух других.

Учитывая простую факторизацию $\omega$ проблема DL в $\langle \gamma \rangle$ может быть сведена к задаче DL во всех подгруппах $\langle \gamma \rangle$ с простым порядком благодаря алгоритму Полига – Хеллмана . Следовательно $\omega$ можно смело считать простым.

Для подгруппы $\langle \gamma \rangle$ высшего порядка $\omega$ мультипликативной группы $GF\left(p^{t}\right)^{*}$ поля расширения $GF(p^{t})$ из $GF(p)$ для некоторых $t$, теперь есть два возможных способа атаковать систему. Можно сосредоточиться либо на всей мультипликативной группе, либо на подгруппе. Для атаки на мультипликативную группу наиболее известным методом является вариант дискретного логарифма решета числового поля или, альтернативно, в подгруппе можно использовать один из нескольких методов, которые принимают ${\mathcal {O}}({\sqrt {\omega }})$ операции в $\langle \gamma \rangle$, например, метод Ро Полларда .

Для обоих подходов сложность проблемы DL в $\langle \gamma \rangle$ зависит от размера минимального окружающего подполя $\langle \gamma \rangle$ и от размера его простого порядка $\omega$. Если $GF\left(p^{t}\right)$ само по себе является минимальным окружающим подполем $\langle \gamma \rangle$ и $\omega$ достаточно велика, то задача DL в $\langle \gamma \rangle$ так же сложна, как и общая проблема DL в $GF\left(p^{t}\right)$.

Параметры XTR теперь выбраны таким образом, что $p$ не маленький, $q$ достаточно велик и $\langle g\rangle$ не может быть встроено в истинное подполе $GF(p^{6})$, с $q\mid p^{2}-p+1$ и $p^{2}-p+1$ является делителем $\mid \!GF(p^{6})^{*}\!\mid =p^{6}-1$, но оно не делит $p^{s}-1{\text{ for }}s\in \{1,2,3\}$ и таким образом $\langle g\rangle$ не может быть подгруппой $GF\!\ (p^{s})^{*}$ для $s\in \{1,2,3\}$.Отсюда следует, что проблему DL в группе XTR можно считать столь же сложной, как и проблему DL в группе XTR. $GF(p^{6})$.

Безопасность XTR

Криптографические протоколы, основанные на дискретных логарифмах, могут использовать множество различных типов подгрупп, таких как группы точек эллиптических кривых или подгруппы мультипликативной группы конечного поля, такие как группа XTR.Как мы видели выше, версии XTR протокола шифрования Диффи-Хеллмана и Эль-Гамаля заменяют использование элементов группы XTR использованием их трассировок. Это означает, что безопасность версий XTR этих схем шифрования больше не основана на исходных проблемах DH, DHD или DL. Следовательно, XTR-версии этих проблем необходимо определить, и мы увидим, что они эквивалентны (в смысле следующего определения) исходным проблемам.

Определения:

• Мы определяем проблему XTR-DH как задачу вычисления $Tr(g^{xy})$ данный $Tr(g^{x})$ и $Tr(g^{y})$ и мы пишем $XDH(g^{x},\ g^{y})=g^{xy}$.
• Проблема XTR-DHD — это проблема определения того, $XDH(a,b)=c$ для $a,b,c\in Tr(\langle g\rangle )$.
• Данный $a\in Tr(\langle g\rangle )$, задача XTR-DL состоит в том, чтобы найти $x=XDL(a)$, то есть $0\leq x<q$ такой, что $a=Tr(g^{x})$.
• Мы говорим, что проблема ${\mathcal {A}}$ (a,b)-эквивалентна задаче ${\mathcal {B}}$, если возникнет проблема ${\mathcal {A}}$ (или ${\mathcal {B}}$) может быть решено не более чем a (или b) вызовом алгоритма решения задачи ${\mathcal {B}}$ (или ${\mathcal {A}}$).

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

Теорема. Имеют место следующие эквивалентности:

я. Задача XTR-DL (1,1)-эквивалентна задаче DL в $\langle g\rangle$.

ii. Проблема XTR-DH (1,2)-эквивалентна проблеме DH в $\langle g\rangle$.

iii. Задача XTR-DHD (3,2)-эквивалентна задаче DHD в $\langle g\rangle$.

Это означает, что алгоритм, решающий XTR-DL, XTR-DH или XTR-DHD с немалой вероятностью, может быть преобразован в алгоритм, решающий соответствующую задачу, не относящуюся к XTR, DL, DH или DHD с немалой вероятностью, и наоборот.В частности, часть II. подразумевает, что определение небольшого ключа XTR-DH (являющегося элементом $GF(p^{2})$) так же сложно, как определить весь ключ DH (являющийся элементом $GF(p^{6})$ ) в группе представлений $\langle g\rangle$.