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-yz^p вимагає чотирьох операцій множення в $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^{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]$ — є незвідним, більша 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$.

Таким чином, повідомлення надіслано.