Русская Википедия:XTR (алгоритм)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Арифметические операции в <math>GF(p^2)</math>

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

<math>GF(p^2) \cong \{x_1 \alpha + x_2 \alpha^p : x_1, x_2 \in GF(p)\}.</math>

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

<math>GF(p^2) \cong \{y_1 \alpha + y_2 \alpha^2 : \alpha^2+\alpha+1=0, y_1, y_2 \in GF(p)\}.</math>

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

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

Использование следов в <math>GF(p^2)</math>

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

<math>Tr(h)=h + h^{p^2} + h^{p^4}.</math>

Кроме того:

<math>

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

           &= h + h^{p^2} + h^{p^4} \\
           &= Tr(h)

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

<math>p^2 = p-1</math>

и

<math>p^4 = (p-1)^2 = p^2 -2p +1 = -p</math>.

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

<math>

\begin{align} Tr(g) &= g + g^{p^2} + g^{p^4}\\

     &= g + g^{p-1} + g^{-p}.

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

<math>(x-g)\!\ (x-g^{p-1})(x-g^{-p})</math>

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

<math>x^3-Tr(g)\!\ x^2 + Tr(g)^p x -1</math>

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

<math>x^3-Tr(g^n)\!\ x^2 + Tr(g^n)^p x -1</math>

— этот многочлен определяется следом <math>Tr(g^n)</math>.

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

Алгоритм быстрого вычисления <math>Tr(g^n)</math> по <math>Tr(g)</math>

Определение: Для каждого <math>c</math> <math>GF(p^2)</math> определим:

<math>F(c,X) = X^3 - cX^2 + c^pX - 1 \in GF(p^2)[X].</math>

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

<math>c_n=h_0^n + h_1^n + h_2^n.</math>

Свойства <math>c_n</math> и <math>F(c,X)</math>:

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

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

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

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

Алгоритм для вычисления <math>S_n(c)</math> при заданных <math>n</math> и <math>c</math>

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

<math>\bar{S}_i(c) = S_{2i+1}(c)</math>

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

<math>m=\sum_{j=0}^r m_j 2^j</math>

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

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

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

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

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

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

Алгоритм А

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

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

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

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

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

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

Алгоритм Б

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

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

Как только мы выбираем <math>q\equiv7\ \text{mod}\ 12</math>, автоматически выполняется условие <math>q\equiv1\ \text{mod}\ 3</math> (Так как <math>7\equiv1\ \text{mod}\ 3</math> и <math>3\mid 12</math>). Из этого утверждения и квадратичного закона взаимности следует, что корни <math>r_1</math> и <math>r_2</math> существуют.

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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