XTR (алгоритм)

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

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

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

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

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

Пусть p — простое число, такое, что p ≡ 2 mod 3, а p² — p + 1 делится на достаточно большое простое q. Так как p² ≡ 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 mod 3:

$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)$
• Вычисление xy требует трех операций умножения в $GF(p)$
• Вычисление xz-yzp требует четырёх операций умножения в $GF(p)$.:

Использование следов в $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}}.$

Кроме того:

${\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$, где $q$ — простое число. Так как $\langle g\rangle$ — подгруппа группы порядка $p^{2}-p+1$, то $q\mid 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$

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

$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})$, то есть вычислять $Tr(g^{n})$ по $Tr(g)$ вместо $g^{n}$ по $g$ Однако для того, чтобы метод был эффективен, необходим способ быстро получать $Tr(g^{n})$ по имеющемуся $Tr(g)$.

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

Определение: Для каждого $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\in \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})$ для $n\in \mathbb {Z}$
4. $c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}$ для $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}$.

Алгоритм для вычисления $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$ — размер подгруппы и делитель $p^{2}-p+1$. Обозначим как $P$ и $Q$ размеры $p$ и $q$ в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать $P$ таким, что $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$.

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

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

Алгоритм Б

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$-битовое число и при этом $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)$. Найдя такое $c$ следует проверить, действительно ли оно порядка $q$, однако сначала нужно выбрать c\in GF(p²), такое, что 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]$ — неприводимо, больше 1/3.

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

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

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

Примеры

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

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

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

Схема Эль-Гамаля

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

1. Боб выбирает случайное $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 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 GF(p^{2})^{3}$.
3. Боб определяет симметричный ключ $K$ основанный на $Tr(g^{bk})\in GF(p^{2})$.
4. Боб шифрует сообщение $M$ ключом $K$, получая зашифрованное сообщение $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$.

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