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-подгруппой. Эта циклическая группа $⟨g⟩$ является подгруппой $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}{)}^{*}$. Таким образом, круговой многочлен ${\mathrm{\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{array}{cc}Tr(h{)}^{p^2}& =h^{p^2}+h^{p^4}+h^{p^6}\\ & =h+h^{p^2}+h^{p^4}\\ & =Tr(h)\end{array}$

Рассмотрим генератор $g$ XTR-группы порядка $q$, где $q$ — простое число. Так как $⟨g⟩$ — подгруппа группы порядка $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{array}{cc}Tr(g)& =g+g^{p^2}+g^{p^4}\\ & =g+g^{p-1}+g^{-p}.\end{array}$

Отметим также, что сопряженным к элементу $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-c{X}^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)$, введем

${\overline{S}}_i(c)=S_{2i+1}(c)$

и $\overline{m}=n$ если не $n$ нечетно и $\overline{m}=n-1$ если четно. Положим $\overline{m}=2m+1,k=1$ и найдем ${\overline{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$, воспользуемся ${\overline{S}}_k(c)$ чтобы найти ${\overline{S}}_{2k}(c)$.
• При $m_j=1$, воспользуемся ${\overline{S}}_k(c)$ чтобы найти ${\overline{S}}_{2k+1}(c)$.
• Заменим $k$ на $2k+m_j$.

По завершении итераций, $k=m$, а $S_{\overline{m}}(c)={\overline{S}}_m(c)$. Если n — четно, воспользуемся $S_{\overline{m}}(c)$ чтобы найти ${\overline{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{)}^{*}$. Теперь следует найти подгруппу $⟨g⟩$ в $GF(p^6{)}^{*}$ для некоторых $g\in GF(p^6)$ таких, что $\mid ⟨g⟩\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)\mathrm{\setminus }GF(p)$ случайным образом.

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

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

1. Выберем случайное $c\in GF(p^2)\mathrm{\setminus }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-ключ $(p,q,Tr(g))$ и они хотят сгенерировать общий закрытый ключ $K$.

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

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

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

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

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