Меню Главная Случайная статья Настройки XTR (алгоритм) Материал из https://ru.wikipedia.org XTR (сокращение от ECSTR — «Efficient and Compact Subgroup Trace Representation») — алгоритм шифрования с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. Преимущества этого алгоритма перед другими, использующими эту идею, в более высокой скорости и меньшем размере ключа. Данный алгоритм использует генератор ${\displaystyle g}$ относительно малой подгруппы порядка ${\displaystyle q}$ (${\displaystyle q}$ — простое) подгруппы ${\displaystyle GF(p^{6})^{*}}$. При правильном выборе ${\displaystyle q}$, дискретное логарифмирование в группе, порожденной ${\displaystyle g}$, имеет ту же вычислительную сложность, что и в ${\displaystyle GF(p^{6})^{*}}$. XTR использует арифметику ${\displaystyle GF(p^{2})}$ вместо ${\displaystyle GF(p^{6})}$, обеспечивая ту же защищенность, но с меньшими затратами на вычисления и передачу данных. Содержание 1 Теоретическая основа XTR 1.1 Арифметические операции в '"`UNIQ--postMath-0000000F-QINU`"' 1.2 Использование следов в '"`UNIQ--postMath-0000001C-QINU`"' 1.3 Алгоритм быстрого вычисления '"`UNIQ--postMath-00000042-QINU`"' по '"`UNIQ--postMath-00000043-QINU`"'[2] 1.4 Алгоритм для вычисления '"`UNIQ--postMath-00000069-QINU`"' при заданных '"`UNIQ--postMath-0000006A-QINU`"' и '"`UNIQ--postMath-0000006B-QINU`"' 2 Выбор параметров 2.1 Выбор поля и размера подгруппы 2.2 Выбор подгруппы 3 Примеры 3.1 Протокол Диффи-Хеллмана 3.2 Схема Эль-Гамаля 4 Примечания Теоретическая основа XTR Алгоритм работает в конечном поле ${\displaystyle GF(p^{6})}$. Рассмотрим группу порядка ${\displaystyle p^{2}-p+1}$, и её подгруппу порядка q, где p — простое число, такое, что другое достаточно большое простое число q является делителем ${\displaystyle p^{2}-p+1}$. Группа порядка q называется XTR-подгруппой. Эта циклическая группа ${\displaystyle \langle g\rangle }$ является подгруппой ${\displaystyle GF(p^{6})^{*}}$ и имеет генератор g. Арифметические операции вGF(p2){\displaystyle GF(p^{2})} Пусть p — простое число, такое, что p 2 mod 3, а p2 — p + 1 делится на достаточно большое простое q. Так как p2 1 mod 3, p порождает ${\displaystyle (\mathbb {Z} /3\mathbb {Z} )^{*}}$. Таким образом, круговой многочлен ${\displaystyle \Phi _{3}(x)=x^{2}+x+1}$ является неприводимым в ${\displaystyle GF(p)}$. Следовательно, корни ${\displaystyle \alpha }$ и ${\displaystyle \alpha ^{p}}$ образуют оптимальный нормальный базис ${\displaystyle GF(p^{2})}$ над ${\displaystyle GF(p)}$ и ${\displaystyle GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.}$ С учетом p 2 mod 3: ${\displaystyle GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1},y_{2}\in GF(p)\}.}$ Таким образом, стоимость арифметических операций следующая: Вычисление xp не требует умножения Вычисление x2 требует двух операций умножения в ${\displaystyle GF(p)}$ Вычисление xy требует трех операций умножения в ${\displaystyle GF(p)}$ Вычисление xz-yzp требует четырёх операций умножения в ${\displaystyle GF(p)}$.:[1] Использование следов вGF(p2){\displaystyle GF(p^{2})} Элементами, сопряженными с ${\displaystyle h\in GF(p^{6})}$ в ${\displaystyle GF(p^{2})}$ являются: сам ${\displaystyle h,h^{p^{2}}}$ и ${\displaystyle h^{p^{4}}}$, а их сумма — след ${\displaystyle h}$. ${\displaystyle Tr(h)=h+h^{p^{2}}+h^{p^{4}}.}$ Кроме того: ${\displaystyle {\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}}}$ Рассмотрим генератор ${\displaystyle g}$ XTR-группы порядка ${\displaystyle q}$, где ${\displaystyle q}$ — простое число. Так как ${\displaystyle \langle g\rangle }$ — подгруппа группы порядка ${\displaystyle p^{2}-p+1}$, то ${\displaystyle q\mid p^{2}-p+1}$. Кроме того, ${\displaystyle p^{2}=p-1}$ и ${\displaystyle p^{4}=(p-1)^{2}=p^{2}-2p+1=-p}$. Таким образом, ${\displaystyle {\begin{aligned}Tr(g)&=g+g^{p^{2}}+g^{p^{4}}\\&=g+g^{p-1}+g^{-p}.\end{aligned}}}$ Отметим также, что сопряженным к элементу ${\displaystyle g}$ является ${\displaystyle 1}$, то есть, ${\displaystyle g}$ имеет норму равную 1. Ключевой особенностью XTR является то, что минимальный многочлен ${\displaystyle g}$ в ${\displaystyle GF(p^{2})}$ ${\displaystyle (x-g)\!\ (x-g^{p-1})(x-g^{-p})}$ упрощается до ${\displaystyle x^{3}-Tr(g)\!\ x^{2}+Tr(g)^{p}x-1}$ Иными словами, сопряженные с ${\displaystyle g}$ элементы, как корни минимального многочлена в ${\displaystyle GF(p^{2})}$, полностью определяются следом ${\displaystyle g}$. Аналогичные рассуждения верны для любой степени ${\displaystyle g}$: ${\displaystyle x^{3}-Tr(g^{n})\!\ x^{2}+Tr(g^{n})^{p}x-1}$ — этот многочлен определяется следом ${\displaystyle Tr(g^{n})}$. Идея алгоритма в том, чтобы заменить ${\displaystyle g^{n}\in GF(p^{6})}$ на ${\displaystyle Tr(g^{n})\in GF(p^{2})}$, то есть вычислять ${\displaystyle Tr(g^{n})}$ по ${\displaystyle Tr(g)}$ вместо ${\displaystyle g^{n}}$ по ${\displaystyle g}$ Однако для того, чтобы метод был эффективен, необходим способ быстро получать ${\displaystyle Tr(g^{n})}$ по имеющемуся ${\displaystyle Tr(g)}$. Алгоритм быстрого вычисленияTr(gn){\displaystyle Tr(g^{n})}поTr(g){\displaystyle Tr(g)}[2] Определение: Для каждого ${\displaystyle c}$ ${\displaystyle GF(p^{2})}$ определим: ${\displaystyle F(c,X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X].}$ Определение: Пусть ${\displaystyle h_{0},\!\ h_{1},h_{2}}$ — корни ${\displaystyle F(c,X)}$ в ${\displaystyle GF(p^{6})}$, а ${\displaystyle n\in \mathbb {Z} }$. Обозначим: ${\displaystyle c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.}$ Свойства ${\displaystyle c_{n}}$ и ${\displaystyle F(c,X)}$: ${\displaystyle c=c_{1}}$ ${\displaystyle c_{-n}=c_{np}=c_{n}^{p}}$ ${\displaystyle c_{n}\in GF(p^{2})}$ для ${\displaystyle n\in \mathbb {Z} }$ ${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}}$ для ${\displaystyle u,v\in \mathbb {Z} }$ Либо все ${\displaystyle h_{j}}$ имеют порядок, являющийся делителем ${\displaystyle p^{2}-p+1}$ и ${\displaystyle >3}$, либо все ${\displaystyle h_{j}}$ — в поле ${\displaystyle GF(p^{2})}$. В частности, ${\displaystyle F(c,X)}$ — неприводим тогда и только тогда, когда его корни имеют порядок, являющийся делителем ${\displaystyle p^{2}-p+1}$ и ${\displaystyle >3}$. ${\displaystyle F(c,X)}$ приводим в поле ${\displaystyle GF(p^{2})}$ тогда и только тогда, когда ${\displaystyle c_{p+1}\in GF(p)}$ Утверждение: Пусть даны ${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1}}$. Вычисление ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p}}$ требует двух операций произведения в поле ${\displaystyle GF(p)}$. Вычисление ${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$ требует четырёх операций произведения в поле ${\displaystyle GF(p)}$. Вычисление ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}}$ требует четырёх операций произведения в поле ${\displaystyle GF(p)}$. Вычисление ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}}$ требует четырёх операций произведения в поле ${\displaystyle GF(p)}$. Определение: Пусть ${\displaystyle S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3}}$. Алгоритм для вычисленияSn(c){\displaystyle S_{n}(c)}при заданныхn{\displaystyle n}иc{\displaystyle c} При ${\displaystyle n<0}$ алгоритм применяется для ${\displaystyle -n}$ и ${\displaystyle c}$, затем используется свойство 2 для получения конечного результатаю При ${\displaystyle n=0}$, ${\displaystyle S_{0}(c)\!\ =(c^{p},3,c)}$. При ${\displaystyle n=1}$, ${\displaystyle S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})}$. При ${\displaystyle n=2}$, воспользуемся выражениями для ${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$ и ${\displaystyle S_{1}(c)}$, чтобы найти ${\displaystyle c_{3}}$ и, соответственно, ${\displaystyle S_{2}(c)}$. При ${\displaystyle n>2}$, чтобы вычислить ${\displaystyle S_{n}(c)}$, введем ${\displaystyle {\bar {S}}_{i}(c)=S_{2i+1}(c)}$ и ${\displaystyle {\bar {m}}=n}$ если не ${\displaystyle n}$ нечетно и ${\displaystyle {\bar {m}}=n-1}$ если четно. Положим ${\displaystyle {\bar {m}}=2m+1,k=1}$ и найдем ${\displaystyle {\bar {S}}_{k}(c)=S_{3}(c)}$, используя Утверждение, и ${\displaystyle S_{2}(c)}$. Пусть, в дальнейшем, ${\displaystyle m=\sum _{j=0}^{r}m_{j}2^{j}}$ где ${\displaystyle m_{j}\in {0,1}}$ и ${\displaystyle m_{r}=1}$. Для ${\displaystyle j=r-1,r-2,...,0}$ последовательно выполним следующее: При ${\displaystyle m_{j}=0}$, воспользуемся ${\displaystyle {\bar {S}}_{k}(c)}$ чтобы найти ${\displaystyle {\bar {S}}_{2k}(c)}$. При ${\displaystyle m_{j}=1}$, воспользуемся ${\displaystyle {\bar {S}}_{k}(c)}$ чтобы найти ${\displaystyle {\bar {S}}_{2k+1}(c)}$. Заменим ${\displaystyle k}$ на ${\displaystyle 2k+m_{j}}$. По завершении итераций, ${\displaystyle k=m}$, а ${\displaystyle S_{\bar {m}}(c)={\bar {S}}_{m}(c)}$. Если n — четно, воспользуемся ${\displaystyle S_{\bar {m}}(c)}$ чтобы найти ${\displaystyle {\bar {S}}_{m+1}(c)}$. Выбор параметров Выбор поля и размера подгруппы Чтобы воспользоваться преимуществами представления элементов групп в виде их следов и обеспечить достаточную защищенность данных, необходимо найти простые ${\displaystyle p}$ и ${\displaystyle q}$, где ${\displaystyle p}$ — характеристика поля ${\displaystyle GF(p^{6})}$, причем ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$, а ${\displaystyle q}$ — размер подгруппы и делитель ${\displaystyle p^{2}-p+1}$. Обозначим как ${\displaystyle P}$ и ${\displaystyle Q}$ размеры ${\displaystyle p}$ и ${\displaystyle q}$ в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать ${\displaystyle P}$ таким, что ${\displaystyle 6P>1024}$, то есть ${\displaystyle P\approx 170}$ а ${\displaystyle Q}$ может быть около 160. Первый алгоритм, который позволяет вычислить такие простые ${\displaystyle p}$ и ${\displaystyle q}$ — Алгоритм А. Алгоритм А Найдём ${\displaystyle r\in \mathbb {Z} }$ такое, что число ${\displaystyle q=r^{2}-r+1}$ — простое число длиной в ${\displaystyle Q}$ бит. Найдем ${\displaystyle k\in \mathbb {Z} }$ такое, что число ${\displaystyle p=r+k\cdot q}$ — простое длиной ${\displaystyle P}$ бит, а также ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$. Корректность Алгоритма А: Необходимо проверить лишь то, что ${\displaystyle q\mid p^{2}-p+1}$, так как все оставшиеся свойства очевидно выполнены из-за специфики выбора ${\displaystyle p}$ и ${\displaystyle q}$. Нетрудно заметить, что ${\displaystyle 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)}$, значит ${\displaystyle q\mid p^{2}-p+1}$. Алгоритм А очень быстрый, однако может быть небезопасен, так как уязвим против атаки с использованием решета числового поля. От этого недостатка избавлен более медленный Алгоритм Б. Алгоритм Б Выберем простое число ${\displaystyle q}$ длиной в ${\displaystyle Q}$ бит, такое, что ${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$. Найдем корни ${\displaystyle r_{1}}$ и ${\displaystyle r_{2}}$ ${\displaystyle X^{2}-X+1\ {\text{mod}}\ q}$. Найдем ${\displaystyle k\in \mathbb {Z} }$ такое, что ${\displaystyle p=r_{i}+k\cdot q}$, ${\displaystyle p}$- простое ${\displaystyle P}$-битовое число и при этом ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$ для ${\displaystyle i\in \{1,2\}}$ Корректность Алгоритма Б: Как только мы выбираем ${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$, автоматически выполняется условие ${\displaystyle q\equiv 1\ {\text{mod}}\ 3}$ (Так как ${\displaystyle 7\equiv 1\ {\text{mod}}\ 3}$ и ${\displaystyle 3\mid 12}$). Из этого утверждения и квадратичного закона взаимности следует, что корни ${\displaystyle r_{1}}$ и ${\displaystyle r_{2}}$ существуют. Чтобы проверить, что ${\displaystyle q\mid p^{2}-p+1}$ снова рассмотрим ${\displaystyle p^{2}-p+1}$ для ${\displaystyle r_{i}\in \{1,2\}}$ и заметим, что ${\displaystyle 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)}$.Значит ${\displaystyle r_{1}}$ и ${\displaystyle r_{2}}$ -корни ${\displaystyle X^{2}-X+1}$ и, следовательно, ${\displaystyle q\mid p^{2}-p+1}$. Выбор подгруппы В предыдущем разделе мы нашли размеры ${\displaystyle p}$ и ${\displaystyle q}$ конечного поля ${\displaystyle GF(p^{6})}$ и мультипликативной подгруппы в ${\displaystyle GF(p^{6})^{*}}$. Теперь следует найти подгруппу ${\displaystyle \langle g\rangle }$ в ${\displaystyle GF\!\ (p^{6})^{*}}$ для некоторых ${\displaystyle g\in GF(p^{6})}$ таких, что ${\displaystyle \mid \!\!\langle g\rangle \!\!\mid =q}$. Однако, необязательно искать явный элемент ${\displaystyle g\in GF(p^{6})}$, достаточно найти элемент ${\displaystyle c\in GF(p^{2})}$ такой, что ${\displaystyle c=Tr(g)}$ для элемента ${\displaystyle g\in GF(p^{6})}$ порядка ${\displaystyle q}$. Но при данном ${\displaystyle Tr(g)}$, генератор ${\displaystyle g}$ XTR-группы может быть найден путём нахождения корня ${\displaystyle F(Tr(g),\ X)}$. Чтобы найти это ${\displaystyle c}$, рассмотрим свойство 5 ${\displaystyle F(c,\ X)}$. Найдя такое ${\displaystyle c}$ следует проверить, действительно ли оно порядка ${\displaystyle q}$, однако сначала нужно выбрать c\in GF(p), такое, что F(c,\ X) — неприводимо. Простейший подход в том, чтобы выбирать ${\displaystyle c\in GF(p^{2})\backslash GF(p)}$ случайным образом. Утверждение: Для случайно выбранного ${\displaystyle c\in GF(p^{2})}$ вероятность, что ${\displaystyle F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]}$ — неприводимо, больше 1/3. Базовый алгоритм для поиска ${\displaystyle Tr(g)}$: Выберем случайное ${\displaystyle c\in GF(p^{2})\backslash GF(p)}$. Если ${\displaystyle F(c,\ X)}$ — приводим, вернемся на первый шаг. Воспользуемся алгоритмом для поиска ${\displaystyle S_{n}(c)}$. Найдем ${\displaystyle d=c_{(p^{2}-p+1)/q}}$. Если ${\displaystyle d}$ имеет порядок не равный ${\displaystyle q}$, вернемся на первый шаг. Пусть ${\displaystyle Tr(g)=d}$. Данный алгоритм вычисляет элемент поля ${\displaystyle GF(p^{2})}$ эквивалентный ${\displaystyle Tr(g)}$ для некоторых ${\displaystyle g\in GF(p^{6})}$ порядка ${\displaystyle q}$.[1] Примеры Протокол Диффи-Хеллмана Предположим, у Алисы и Боба есть открытый XTR-ключ ${\displaystyle \left(p,q,Tr(g)\right)}$ и они хотят сгенерировать общий закрытый ключ ${\displaystyle K}$. Алиса выбирает случайное число ${\displaystyle a\in \mathbb {Z} }$ такое, что ${\displaystyle 1<a<q-2}$, вычисляет ${\displaystyle S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}}$ и посылает ${\displaystyle Tr(g^{a})\in GF(p^{2})}$ Бобу. Боб получает ${\displaystyle Tr(g^{a})}$ от Алисы, выбирает случайное ${\displaystyle b\in \mathbb {Z} }$ такое, что ${\displaystyle 1<b<q-2}$, вычисляет ${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$ и посылает ${\displaystyle Tr(g^{b})\in GF(p^{2})}$ Алисе. Алиса получает ${\displaystyle Tr(g^{b})}$ от Боба, вычисляет ${\displaystyle 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}}$ и получает ${\displaystyle Tr(g^{ab})\in GF(p^{2})}$ — закрытый ключ ${\displaystyle K}$. Точно так же, Боб вычисляет ${\displaystyle 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}}$ и получает ${\displaystyle Tr(g^{ab})\in GF(p^{2})}$ — закрытый ключ ${\displaystyle K}$. Схема Эль-Гамаля Предположим, у Алисы есть часть публичного ключа XTR: ${\displaystyle (p,q,Tr(g))}$. Алиса выбирает секретное целое число ${\displaystyle k}$ и вычисляет и публикует ${\displaystyle Tr(g^{k})}$. Получив публичный ключ Алисы ${\displaystyle \left(p,q,Tr(g),Tr(g^{k})\right)}$, Боб может зашифровать сообщение ${\displaystyle M}$, предназначенное Алисе, используя следующий алгоритм: Боб выбирает случайное ${\displaystyle b\in \mathbb {Z} }$ такое, что ${\displaystyle 1<b<q-2}$ и вычисляет ${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$. Затем Боб вычисляет${\displaystyle 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}}$. Боб определяет симметричный ключ ${\displaystyle K}$ основанный на ${\displaystyle Tr(g^{bk})\in GF(p^{2})}$. Боб шифрует сообщение ${\displaystyle M}$ ключом ${\displaystyle K}$, получая зашифрованное сообщение ${\displaystyle E}$. Пару ${\displaystyle (Tr(g^{b}),\ E)}$ Боб посылает Алисе. Получив пару ${\displaystyle (Tr(g^{b}),\ E)}$, Алиса расшифровывает её следующим образом: Алиса вычисляет ${\displaystyle 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}}$. Алиса определяет симметричный ключ ${\displaystyle K}$ основанный на ${\displaystyle Tr(g^{bk})\in GF(p^{2})}$. Зная, что алгоритм шифрования сообщения — симметричный, Алиса ключом ${\displaystyle K}$ расшифровывает ${\displaystyle E}$, получая исходное сообщение ${\displaystyle M}$. Таким образом, сообщение передано. Примечания 1 2 Lenstra, Arjen K.; Verheul, Eric R. An overview of the XTR public key system (неопр.). Архивировано из оригинала 15 апреля 2006 года. Lenstra, Arjen K.; Verheul, Eric R. The XTR public key system (неопр.).