XTR (алгоритм)

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

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

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

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

Арифметические операции в [math]\displaystyle{ GF(p^2) }[/math]

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

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

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

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

Использование следов в [math]\displaystyle{ GF(p^2) }[/math]

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

[math]\displaystyle{ Tr(h)=h + h^{p^2} + h^{p^4}. }[/math]

Кроме того:

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

[math]\displaystyle{ p^2 = p-1 }[/math]

и

[math]\displaystyle{ p^4 = (p-1)^2 = p^2 -2p +1 = -p }[/math].

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

[math]\displaystyle{ \begin{align} Tr(g) &= g + g^{p^2} + g^{p^4}\\ &= g + g^{p-1} + g^{-p}. \end{align} }[/math]

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

[math]\displaystyle{ (x-g)\!\ (x-g^{p-1})(x-g^{-p}) }[/math]

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

[math]\displaystyle{ x^3-Tr(g)\!\ x^2 + Tr(g)^p x -1 }[/math]

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

[math]\displaystyle{ x^3-Tr(g^n)\!\ x^2 + Tr(g^n)^p x -1 }[/math]

— этот многочлен определяется следом [math]\displaystyle{ Tr(g^n) }[/math].

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

Алгоритм быстрого вычисления [math]\displaystyle{ Tr(g^n) }[/math] по [math]\displaystyle{ Tr(g) }[/math]

Определение: Для каждого [math]\displaystyle{ c }[/math] [math]\displaystyle{ GF(p^2) }[/math] определим:

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

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

[math]\displaystyle{ c_n=h_0^n + h_1^n + h_2^n. }[/math]

Свойства [math]\displaystyle{ c_n }[/math] и [math]\displaystyle{ F(c,X) }[/math]:

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

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

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

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

Алгоритм для вычисления [math]\displaystyle{ S_n(c) }[/math] при заданных [math]\displaystyle{ n }[/math] и [math]\displaystyle{ c }[/math]

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

[math]\displaystyle{ \bar{S}_i(c) = S_{2i+1}(c) }[/math]

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

[math]\displaystyle{ m=\sum_{j=0}^r m_j 2^j }[/math]

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

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

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

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

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

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

Алгоритм А

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

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

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

Нетрудно заметить, что [math]\displaystyle{ 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]\displaystyle{ q\mid p^2-p+1 }[/math].

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

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

Алгоритм Б

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

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

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

Чтобы проверить, что [math]\displaystyle{ q\mid p^2-p+1 }[/math] снова рассмотрим [math]\displaystyle{ p^2-p+1 }[/math] для [math]\displaystyle{ r_i\in\{1,2\} }[/math] и заметим, что [math]\displaystyle{ 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]\displaystyle{ r_1 }[/math] и [math]\displaystyle{ r_2 }[/math] -корни [math]\displaystyle{ X^2-X+1 }[/math] и, следовательно, [math]\displaystyle{ q\mid p^2-p+1 }[/math].

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

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

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

Базовый алгоритм для поиска [math]\displaystyle{ Tr(g) }[/math]:

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

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

Примеры

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

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

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

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

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

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

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

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

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