XTR (algorithm)

XTR (short for ECSTR - “Efficient and Compact Subgroup Trace Representation”) is a public key encryption algorithm based on the computational complexity of the discrete logarithm problem . The advantages of this algorithm over others using this idea are its higher speed and smaller key size.

This algorithm uses a generator $g$ ${\ displaystyle g}$ $g$ relatively small subgroup of order $q$ ${\ displaystyle q}$ $q$ ( $q$ ${\ displaystyle q}$ $q$ - simple) subgroups $GF(p^{6})^{*}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ . With the right choice $q$ ${\ displaystyle q}$ $q$ , discrete logarithm in the group generated by $g$ ${\ displaystyle g}$ $g$ has the same computational complexity as in $GF(p^{6})^{*}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ . XTR uses arithmetic $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ ${\ displaystyle GF (p ^ {2})}$ instead $GF(p^{6})$ ${\ displaystyle GF (p ^ {6})}$ ${\ displaystyle GF (p ^ {6})}$ , providing the same security, but at a lower cost for computing and data transfer.

Content

1 Theoretical basis of XTR
- 1.1 Arithmetic operations in $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ ${\ displaystyle GF (p ^ {2})}$
- 1.2 Using traces in $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ ${\ displaystyle GF (p ^ {2})}$
- 1.3 Fast Computation Algorithm $Tr(g^{n})$ ${\ displaystyle Tr (g ^ {n})}$ ${\ displaystyle Tr (g ^ {n})}$ by $Tr(g)$ ${\ displaystyle Tr (g)}$ ${\ displaystyle Tr (g)}$ ^[2]
- 1.4 Algorithm for computing $S_{n}(c)$ ${\ displaystyle S_ {n} (c)}$ ${\ displaystyle S_ {n} (c)}$ given $n$ ${\ displaystyle n}$ $n$ and $c$ ${\ displaystyle c}$ $c$
2 Select options
- 2.1 Choosing a field and subgroup size
- 2.2 Subgroup selection
3 Examples
- 3.1 Diffie-Hellman Protocol
- 3.2 El Gamal scheme
4 notes

XTR Theoretical Framework

The algorithm works in the final field $GF(p^{6})$ ${\ displaystyle GF (p ^ {6})}$ $GF(p^{6})$ . Consider the order group $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ $p^{2}-p+1$ , and its subgroup of order q , where p is a prime, such that another sufficiently large prime q is a divisor $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ $p^{2}-p+1$ . A group of order q is called an XTR-subgroup. This cyclic group $\langle g\rangle$ ${\ displaystyle \ langle g \ rangle}$ $\langle g\rangle$ is a subgroup $GF(p^{6})^{*}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ $GF(p^{6})^{*}$ and has a generator g .

Arithmetic operations in $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ $GF(p^{2})$

Let p be a prime such that p ≡ 2 mod 3 and p ² - p + 1 be divided by a sufficiently large prime q . Since p ² ≡ 1 mod 3 , p generates $(\mathbb {Z} /3\mathbb {Z} )^{*}$ ${\ displaystyle (\ mathbb {Z} / 3 \ mathbb {Z}) ^ {*}}$ $(\mathbb {Z} /3\mathbb {Z} )^{*}$ . So the circular polynomial $\Phi _{3}(x)=x^{2}+x+1$ ${\ displaystyle \ Phi _ {3} (x) = x ^ {2} + x + 1}$ $\Phi _{3}(x)=x^{2}+x+1$ is irreducible in $GF(p)$ ${\ displaystyle GF (p)}$ $GF(p)$ . Hence the roots $\alpha$ ${\ displaystyle \ alpha}$ $\alpha$ and $\alpha ^{p}$ ${\ displaystyle \ alpha ^ {p}}$ $\alpha ^{p}$ form the optimal normal basis $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ $GF(p^{2})$ over $GF(p)$ ${\ displaystyle GF (p)}$ $GF(p)$ and

GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.

{\ displaystyle GF (p ^ {2}) \ cong \ {x_ {1} \ alpha + x_ {2} \ alpha ^ {p}: x_ {1}, x_ {2} \ in GF (p) \} .}

GF(p^{2})\cong \{x_{1}\alpha +x_{2}\alpha ^{p}:x_{1},x_{2}\in GF(p)\}.

Given 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)\}.

{\ displaystyle GF (p ^ {2}) \ cong \ {y_ {1} \ alpha + y_ {2} \ alpha ^ {2}: \ alpha ^ {2} + \ alpha + 1 = 0, y_ {1 }, y_ {2} \ in GF (p) \}.}

GF(p^{2})\cong \{y_{1}\alpha +y_{2}\alpha ^{2}:\alpha ^{2}+\alpha +1=0,y_{1},y_{2}\in GF(p)\}.

Thus, the cost of arithmetic operations is as follows:

Calculation of x ^p does not require multiplication
Computing x ² requires two multiplication operations in $GF(p)$ ${\ displaystyle GF (p)}$ $GF(p)$
Computing xy requires three multiplication operations in $GF(p)$ ${\ displaystyle GF (p)}$ $GF(p)$
Xz-yz calculation p requires four multiplication operations in $GF(p)$ ${\ displaystyle GF (p)}$ $GF(p)$ .: ^[1]

Using traces in $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$

Elements associated with $h\in GF(p^{6})$ ${\ displaystyle h \ in GF (p ^ {6})}$ at $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ are: myself $h,h^{p^{2}}$ ${\ displaystyle h, h ^ {p ^ {2}}}$ and $h^{p^{4}}$ ${\ displaystyle h ^ {p ^ {4}}}$ , and their sum is a trace $h$ ${\ displaystyle h}$ .

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

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

Besides:

{\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 {\ 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}}}

Consider a generator $g$ ${\ displaystyle g}$ XTR order groups $q$ ${\ displaystyle q}$ where $q$ ${\ displaystyle q}$ - Prime number. As $\langle g\rangle$ ${\ displaystyle \ langle g \ rangle}$ - subgroup of the order group $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ then $q\mid p^{2}-p+1$ ${\ displaystyle q \ mid p ^ {2} -p + 1}$ . Besides,

p^{2}=p-1

{\ displaystyle p ^ {2} = p-1}

and

p^{4}=(p-1)^{2}=p^{2}-2p+1=-p

{\ displaystyle p ^ {4} = (p-1) ^ {2} = p ^ {2} -2p + 1 = -p}

.

In this way,

{\begin{aligned}Tr(g)&=g+g^{p^{2}}+g^{p^{4}}\\&=g+g^{p-1}+g^{-p}.\end{aligned}}

{\ displaystyle {\ begin {aligned} Tr (g) & = g + g ^ {p ^ {2}} + g ^ {p ^ {4}} \\ & = g + g ^ {p-1} + g ^ {- p}. \ end {aligned}}}

We also note that conjugate to the element $g$ ${\ displaystyle g}$ is an $one$ ${\ displaystyle 1}$ , i.e, $g$ ${\ displaystyle g}$ has a norm of 1. A key feature of XTR is that the minimum polynomial $g$ ${\ displaystyle g}$ at $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$

(x-g)\!\ (x-g^{p-1})(x-g^{-p})

{\ displaystyle (xg) \! \ (xg ^ {p-1}) (xg ^ {- p})}

simplified to

x^{3}-Tr(g)\!\ x^{2}+Tr(g)^{p}x-1

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

In other words, conjugate to $g$ ${\ displaystyle g}$ elements like the roots of a minimal polynomial in $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ are completely determined by the trace $g$ ${\ displaystyle g}$ . Similar reasoning is true for any degree $g$ ${\ displaystyle g}$ :

x^{3}-Tr(g^{n})\!\ x^{2}+Tr(g^{n})^{p}x-1

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

- this polynomial is determined by the trace $Tr(g^{n})$ ${\ displaystyle Tr (g ^ {n})}$ .

The idea of the algorithm is to replace $g^{n}\in GF(p^{6})$ ${\ displaystyle g ^ {n} \ in GF (p ^ {6})}$ on $Tr(g^{n})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {n}) \ in GF (p ^ {2})}$ that is, calculate $Tr(g^{n})$ ${\ displaystyle Tr (g ^ {n})}$ by $Tr(g)$ ${\ displaystyle Tr (g)}$ instead $g^{n}$ ${\ displaystyle g ^ {n}}$ by $g$ ${\ displaystyle g}$ However, for the method to be effective, a way is needed $Tr(g^{n})$ ${\ displaystyle Tr (g ^ {n})}$ according to available $Tr(g)$ ${\ displaystyle Tr (g)}$ .

Fast calculation algorithm $Tr(g^{n})$ ${\ displaystyle Tr (g ^ {n})}$ by $Tr(g)$ ${\ displaystyle Tr (g)}$ ^[2]

Definition: For each $c$ ${\ displaystyle c}$ $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ define:

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

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

Definition: Let $h_{0},\!\ h_{1},h_{2}$ ${\ displaystyle h_ {0}, \! \ h_ {1}, h_ {2}}$ - roots $F(c,X)$ ${\ displaystyle F (c, X)}$ at $GF(p^{6})$ ${\ displaystyle GF (p ^ {6})}$ , but $n\in \mathbb {Z}$ ${\ displaystyle n \ in \ mathbb {Z}}$ . Denote:

c_{n}=h_{0}^{n}+h_{1}^{n}+h_{2}^{n}.

{\ displaystyle c_ {n} = h_ {0} ^ {n} + h_ {1} ^ {n} + h_ {2} ^ {n}.}

The properties $c_{n}$ ${\ displaystyle c_ {n}}$ and $F(c,X)$ ${\ displaystyle F (c, X)}$ :

$c=c_{1}$ ${\ displaystyle c = c_ {1}}$
$c_{-n}=c_{np}=c_{n}^{p}$ ${\ displaystyle c _ {- n} = c_ {np} = c_ {n} ^ {p}}$
$c_{n}\in GF(p^{2})$ ${\ displaystyle c_ {n} \ in GF (p ^ {2})}$ for $n\in \mathbb {Z}$ ${\ displaystyle n \ in \ mathbb {Z}}$
$c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}$ ${\ displaystyle c_ {u + v} = c_ {u} c_ {v} -c_ {v} ^ {p} c_ {uv} + c_ {u-2v}}$ for $u,v\in \mathbb {Z}$ ${\ displaystyle u, v \ in \ mathbb {Z}}$
Or all $h_{j}$ ${\ displaystyle h_ {j}}$ have a divisor order $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ and $>3$ ${\ displaystyle> 3}$ or all $h_{j}$ ${\ displaystyle h_ {j}}$ - in field $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ . In particular, $F(c,X)$ ${\ displaystyle F (c, X)}$ - irreducible if and only if its roots have an order that is a divisor $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ and $>3$ ${\ displaystyle> 3}$ .
$F(c,X)$ ${\ displaystyle F (c, X)}$ we give in the field $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ if and only if $c_{p+1}\in GF(p)$ ${\ displaystyle c_ {p + 1} \ in GF (p)}$

Statement: May they be given $c,\!\ c_{n-1},c_{n},c_{n+1}$ ${\ displaystyle c, \! \ c_ {n-1}, c_ {n}, c_ {n + 1}}$ .

Calculation $c_{2n}=c_{n}^{2}-2c_{n}^{p}$ ${\ displaystyle c_ {2n} = c_ {n} ^ {2} -2c_ {n} ^ {p}}$ requires two product operations in the field $GF(p)$ ${\ displaystyle GF (p)}$ .
Calculation $c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}$ ${\ displaystyle c_ {n + 2} = c_ {n + 1} \ cdot cc ^ {p} \ cdot c_ {n} + c_ {n-1}}$ requires four product operations in the field $GF(p)$ ${\ displaystyle GF (p)}$ .
Calculation $c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}$ ${\ displaystyle c_ {2n-1} = c_ {n-1} \ cdot c_ {n} -c ^ {p} \ cdot c_ {n} ^ {p} + c_ {n + 1} ^ {p}}$ requires four product operations in the field $GF(p)$ ${\ displaystyle GF (p)}$ .
Calculation $c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}$ ${\ displaystyle c_ {2n + 1} = c_ {n + 1} \ cdot c_ {n} -c \ cdot c_ {n} ^ {p} + c_ {n-1} ^ {p}}$ requires four product operations in the field $GF(p)$ ${\ displaystyle GF (p)}$ .

Definition: Let $S_{n}(c)=(c_{n-1},c_{n},c_{n+1})\in GF(p^{2})^{3}$ ${\ displaystyle S_ {n} (c) = (c_ {n-1}, c_ {n}, c_ {n + 1}) \ in GF (p ^ {2}) ^ {3}}$ .

Algorithm for calculating $S_{n}(c)$ ${\ displaystyle S_ {n} (c)}$ given $n$ ${\ displaystyle n}$ and $c$ ${\ displaystyle c}$

At $n<0$ ${\ displaystyle n <0}$ the algorithm is applied to $-n$ ${\ displaystyle -n}$ and $c$ ${\ displaystyle c}$ , then property 2 is used to obtain the final result
At $n=0$ ${\ displaystyle n = 0}$ , $S_{0}(c)\!\ =(c^{p},3,c)$ ${\ displaystyle S_ {0} (c) \! \ = (c ^ {p}, 3, c)}$ .
At $n=1$ ${\ displaystyle n = 1}$ , $S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})$ ${\ displaystyle S_ {1} (c) \! \ = (3, c, c ^ {2} -2c ^ {p})}$ .
At $n=2$ ${\ displaystyle n = 2}$ , we will use expressions for $c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}$ ${\ displaystyle c_ {n + 2} = c_ {n + 1} \ cdot cc ^ {p} \ cdot c_ {n} + c_ {n-1}}$ and $S_{1}(c)$ ${\ displaystyle S_ {1} (c)}$ to find $c_{3}$ ${\ displaystyle c_ {3}}$ and correspondingly, $S_{2}(c)$ ${\ displaystyle S_ {2} (c)}$ .
At $n>2$ ${\ displaystyle n> 2}$ to calculate $S_{n}(c)$ ${\ displaystyle S_ {n} (c)}$ introduce

{\bar {S}}_{i}(c)=S_{2i+1}(c)

{\ displaystyle {\ bar {S}} _ {i} (c) = S_ {2i + 1} (c)}

and

{\bar {m}}=n

{\ displaystyle {\ bar {m}} = n}

if not

n

{\ displaystyle n}

odd and

{\bar {m}}=n-1

{\ displaystyle {\ bar {m}} = n-1}

if even. Put

{\bar {m}}=2m+1,k=1

{\ displaystyle {\ bar {m}} = 2m + 1, k = 1}

and find

{\bar {S}}_{k}(c)=S_{3}(c)

{\ displaystyle {\ bar {S}} _ {k} (c) = S_ {3} (c)}

using the Statement, and

S_{2}(c)

{\ displaystyle S_ {2} (c)}

. Let, further,

m=\sum _{j=0}^{r}m_{j}2^{j}

{\ displaystyle m = \ sum _ {j = 0} ^ {r} m_ {j} 2 ^ {j}}

Where

m_{j}\in {0,1}

{\ displaystyle m_ {j} \ in {0,1}}

and

m_{r}=1

{\ displaystyle m_ {r} = 1}

. For

j=r-1,r-2,...,0

{\ displaystyle j = r-1, r-2, ..., 0}

sequentially perform the following:

At $m_{j}=0$ ${\ displaystyle m_ {j} = 0}$ use ${\bar {S}}_{k}(c)$ ${\ displaystyle {\ bar {S}} _ {k} (c)}$ to find ${\bar {S}}_{2k}(c)$ ${\ displaystyle {\ bar {S}} _ {2k} (c)}$ .
At $m_{j}=1$ ${\ displaystyle m_ {j} = 1}$ use ${\bar {S}}_{k}(c)$ ${\ displaystyle {\ bar {S}} _ {k} (c)}$ to find ${\bar {S}}_{2k+1}(c)$ ${\ displaystyle {\ bar {S}} _ {2k + 1} (c)}$ .
Replace $k$ ${\ displaystyle k}$ on $2k+m_{j}$ ${\ displaystyle 2k + m_ {j}}$ .

Upon completion of the iterations, $k=m$ ${\ displaystyle k = m}$ , but $S_{\bar {m}}(c)={\bar {S}}_{m}(c)$ ${\ displaystyle S _ {\ bar {m}} (c) = {\ bar {S}} _ {m} (c)}$ . If n is even, we use $S_{\bar {m}}(c)$ ${\ displaystyle S _ {\ bar {m}} (c)}$ to find ${\bar {S}}_{m+1}(c)$ ${\ displaystyle {\ bar {S}} _ {m + 1} (c)}$ .

Select options

Select a field and subgroup size

To take advantage of the presentation of the elements of groups in the form of their traces and to ensure sufficient data security, you need to find simple $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ where $p$ ${\ displaystyle p}$ - field characteristic $GF(p^{6})$ ${\ displaystyle GF (p ^ {6})}$ , and $p\equiv 2\ {\text{mod}}\ 3$ ${\ displaystyle p \ equiv 2 \ {\ text {mod}} \ 3}$ , but $q$ ${\ displaystyle q}$ - subgroup size and divisor $p^{2}-p+1$ ${\ displaystyle p ^ {2} -p + 1}$ . Denote by $P$ ${\ displaystyle P}$ and $Q$ ${\ displaystyle Q}$ sizes $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ in bits. To achieve the security level that, for example, provides RSA with a key length of 1024 bits, you must select $P$ ${\ displaystyle P}$ such that $6P>1024$ ${\ displaystyle 6P> 1024}$ , i.e $P\approx 170$ ${\ displaystyle P \ approx 170}$ but $Q$ ${\ displaystyle Q}$ maybe around 160. The first algorithm to calculate such simple $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ - Algorithm A.

Algorithm A

Will find $r\in \mathbb {Z}$ ${\ displaystyle r \ in \ mathbb {Z}}$ such that the number $q=r^{2}-r+1$ ${\ displaystyle q = r ^ {2} -r + 1}$ Is a prime number in length $Q$ ${\ displaystyle Q}$ bit.
Will find $k\in \mathbb {Z}$ ${\ displaystyle k \ in \ mathbb {Z}}$ such that the number $p=r+k\cdot q$ ${\ displaystyle p = r + k \ cdot q}$ - simple length $P$ ${\ displaystyle P}$ bit as well $p\equiv 2\ {\text{mod}}\ 3$ ${\ displaystyle p \ equiv 2 \ {\ text {mod}} \ 3}$ .

Correctness of Algorithm A:

It is only necessary to verify that

q\mid p^{2}-p+1

{\ displaystyle q \ mid p ^ {2} -p + 1}

, since all the remaining properties are obviously satisfied due to the specifics of the choice

p

{\ displaystyle p}

and

q

{\ displaystyle q}

.

It is easy to see that

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 p ^ {2} -p + 1 = r ^ {2} + 2rkq + k ^ {2} q ^ {2} -r-kq + 1 = r ^ {2} -r + 1 + q ( 2rk + k ^ {2} qk) = q (1 + 2rk + k ^ {2} qk)}

means

q\mid p^{2}-p+1

{\ displaystyle q \ mid p ^ {2} -p + 1}

.

Algorithm A is very fast, but it can be unsafe, as it is vulnerable to attack using a sieve of a number field .

The slower Algorithm B. has been saved from this drawback.

Algorithm B

Choose a prime $q$ ${\ displaystyle q}$ in length $Q$ ${\ displaystyle Q}$ bit such that $q\equiv 7\ {\text{mod}}\ 12$ ${\ displaystyle q \ equiv 7 \ {\ text {mod}} \ 12}$ .
Find the roots $r_{1}$ ${\ displaystyle r_ {1}}$ and $r_{2}$ ${\ displaystyle r_ {2}}$ $X^{2}-X+1\ {\text{mod}}\ q$ ${\ displaystyle X ^ {2} -X + 1 \ {\ text {mod}} \ q}$ .
Will find $k\in \mathbb {Z}$ ${\ displaystyle k \ in \ mathbb {Z}}$ such that $p=r_{i}+k\cdot q$ ${\ displaystyle p = r_ {i} + k \ cdot q}$ , $p$ ${\ displaystyle p}$ - simple $P$ ${\ displaystyle P}$ bit number and at the same time $p\equiv 2\ {\text{mod}}\ 3$ ${\ displaystyle p \ equiv 2 \ {\ text {mod}} \ 3}$ for $i\in \{1,2\}$ ${\ displaystyle i \ in \ {1,2 \}}$

Correctness of Algorithm B:

As soon as we choose

q\equiv 7\ {\text{mod}}\ 12

{\ displaystyle q \ equiv 7 \ {\ text {mod}} \ 12}

, the condition is automatically satisfied

q\equiv 1\ {\text{mod}}\ 3

{\ displaystyle q \ equiv 1 \ {\ text {mod}} \ 3}

(As

7\equiv 1\ {\text{mod}}\ 3

{\ displaystyle 7 \ equiv 1 \ {\ text {mod}} \ 3}

and

3\mid 12

{\ displaystyle 3 \ mid 12}

) From this statement and the quadratic law of reciprocity it follows that the roots

r_{1}

{\ displaystyle r_ {1}}

and

r_{2}

{\ displaystyle r_ {2}}

exists.

To verify that

q\mid p^{2}-p+1

{\ displaystyle q \ mid p ^ {2} -p + 1}

consider again

p^{2}-p+1

{\ displaystyle p ^ {2} -p + 1}

for

r_{i}\in \{1,2\}

{\ displaystyle r_ {i} \ in \ {1,2 \}}

and note that

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 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} qk) = q (2rk + k ^ {2} qk)}

. Means

r_{1}

{\ displaystyle r_ {1}}

and

r_{2}

{\ displaystyle r_ {2}}

roots

X^{2}-X+1

{\ displaystyle X ^ {2} -X + 1}

and therefore

q\mid p^{2}-p+1

{\ displaystyle q \ mid p ^ {2} -p + 1}

.

Subgroup Selection

In the previous section we found the sizes $p$ ${\ displaystyle p}$ and $q$ ${\ displaystyle q}$ final field $GF(p^{6})$ ${\ displaystyle GF (p ^ {6})}$ and multiplicative subgroup in $GF(p^{6})^{*}$ ${\ displaystyle GF (p ^ {6}) ^ {*}}$ . Now you should find a subgroup $\langle g\rangle$ ${\ displaystyle \ langle g \ rangle}$ at $GF\!\ (p^{6})^{*}$ ${\ displaystyle GF \! \ (p ^ {6}) ^ {*}}$ for some $g\in GF(p^{6})$ ${\ displaystyle g \ in GF (p ^ {6})}$ such that $\mid \!\!\langle g\rangle \!\!\mid =q$ ${\ displaystyle \ mid \! \!! langle g \ rangle \! \!! \ mid = q}$ . However, it is not necessary to look for an explicit element. $g\in GF(p^{6})$ ${\ displaystyle g \ in GF (p ^ {6})}$ , just find the element $c\in GF(p^{2})$ ${\ displaystyle c \ in GF (p ^ {2})}$ such that $c=Tr(g)$ ${\ displaystyle c = Tr (g)}$ for item $g\in GF(p^{6})$ ${\ displaystyle g \ in GF (p ^ {6})}$ of order $q$ ${\ displaystyle q}$ . But with this $Tr(g)$ ${\ displaystyle Tr (g)}$ generator $g$ ${\ displaystyle g}$ XTR groups can be found by finding the root $F(Tr(g),\ X)$ ${\ displaystyle F (Tr (g), \ X)}$ . To find it $c$ ${\ displaystyle c}$ , consider property 5 $F(c,\ X)$ ${\ displaystyle F (c, \ X)}$ . Finding such $c$ ${\ displaystyle c}$ should check whether it is really order $q$ ${\ displaystyle q}$ , however, we must first choose c \ in GF (p²) such that F (c, \ X) is irreducible. The simplest approach is to choose $c\in GF(p^{2})\backslash GF(p)$ ${\ displaystyle c \ in GF (p ^ {2}) \ backslash GF (p)}$ randomly.

Statement: For a randomly selected $c\in GF(p^{2})$ ${\ displaystyle c \ in GF (p ^ {2})}$ the probability that $F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]$ ${\ displaystyle F (c, \ X) = X ^ {3} -cX ^ {2} + c ^ {p} X-1 \ in GF (p ^ {2}) [X]}$ - irreducible, more than 1/3.

Basic search algorithm $Tr(g)$ ${\ displaystyle Tr (g)}$ :

Choose random $c\in GF(p^{2})\backslash GF(p)$ ${\ displaystyle c \ in GF (p ^ {2}) \ backslash GF (p)}$ .
If $F(c,\ X)$ ${\ displaystyle F (c, \ X)}$ - we bring, we will return to the first step.
We use the algorithm to search $S_{n}(c)$ ${\ displaystyle S_ {n} (c)}$ . Will find $d=c_{(p^{2}-p+1)/q}$ ${\ displaystyle d = c _ {(p ^ {2} -p + 1) / q}}$ .
If $d$ ${\ displaystyle d}$ has an order not equal $q$ ${\ displaystyle q}$ back to the first step.
Let be $Tr(g)=d$ ${\ displaystyle Tr (g) = d}$ .

This algorithm calculates a field element $GF(p^{2})$ ${\ displaystyle GF (p ^ {2})}$ equivalent $Tr(g)$ ${\ displaystyle Tr (g)}$ for some $g\in GF(p^{6})$ ${\ displaystyle g \ in GF (p ^ {6})}$ of order $q$ ${\ displaystyle q}$ . ^[one]

Examples

Diffie-Hellman Protocol

Suppose Alice and Bob have an XTR public key $\left(p,q,Tr(g)\right)$ ${\ displaystyle \ left (p, q, Tr (g) \ right)}$ and they want to generate a shared private key $K$ ${\ displaystyle K}$ .

Alice picks a random number $a\in \mathbb {Z}$ ${\ displaystyle a \ in \ mathbb {Z}}$ such that $1<a<q-2$ ${\ displaystyle 1 <a <q-2}$ calculates $S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}$ ${\ displaystyle S_ {a} (Tr (g)) = \ left (Tr (g ^ {a-1}), Tr (g ^ {a}), Tr (g ^ {a + 1}) \ right) \ in GF (p ^ {2}) ^ {3}}$ and sends $Tr(g^{a})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {a}) \ in GF (p ^ {2})}$ To bob.
Bob gets $Tr(g^{a})$ ${\ displaystyle Tr (g ^ {a})}$ from Alice, picks random $b\in \mathbb {Z}$ ${\ displaystyle b \ in \ mathbb {Z}}$ such that $1<b<q-2$ ${\ displaystyle 1 <b <q-2}$ calculates $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)) = \ left (Tr (g ^ {b-1}), Tr (g ^ {b}), Tr (g ^ {b + 1}) \ right) \ in GF (p ^ {2}) ^ {3}}$ and sends $Tr(g^{b})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {b}) \ in GF (p ^ {2})}$ Alice.
Alice gets $Tr(g^{b})$ ${\ displaystyle Tr (g ^ {b})}$ from Bob, calculates $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 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}}$ and gets $Tr(g^{ab})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {ab}) \ in GF (p ^ {2})}$ - private key $K$ ${\ displaystyle K}$ .
Similarly, Bob computes $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 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}}$ and gets $Tr(g^{ab})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {ab}) \ in GF (p ^ {2})}$ - private key $K$ ${\ displaystyle K}$ .

El Gamal Scheme

Suppose Alice has a part of the XTR public key: $(p,q,Tr(g))$ ${\ displaystyle (p, q, Tr (g))}$ . Alice picks a secret integer $k$ ${\ displaystyle k}$ and calculates and publishes $Tr(g^{k})$ ${\ displaystyle Tr (g ^ {k})}$ . Having received Alice’s public key $\left(p,q,Tr(g),Tr(g^{k})\right)$ ${\ displaystyle \ left (p, q, Tr (g), Tr (g ^ {k}) \ right)}$ Bob can encrypt the message $M$ ${\ displaystyle M}$ intended by Alice using the following algorithm:

Bob picks random $b\in \mathbb {Z}$ ${\ displaystyle b \ in \ mathbb {Z}}$ such that $1<b<q-2$ ${\ displaystyle 1 <b <q-2}$ and calculates $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)) = \ left (Tr (g ^ {b-1}), Tr (g ^ {b}), Tr (g ^ {b + 1}) \ right) \ in GF (p ^ {2}) ^ {3}}$ .
Bob then calculates $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 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}}$ .
Bob defines a symmetric key $K$ ${\ displaystyle K}$ based on $Tr(g^{bk})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {bk}) \ in GF (p ^ {2})}$ .
Bob encrypts the message $M$ ${\ displaystyle M}$ the key $K$ ${\ displaystyle K}$ receiving an encrypted message $E$ ${\ displaystyle E}$ .
A couple $(Tr(g^{b}),\ E)$ ${\ displaystyle (Tr (g ^ {b}), \ E)}$ Bob sends Alice.

Getting a pair $(Tr(g^{b}),\ E)$ ${\ displaystyle (Tr (g ^ {b}), \ E)}$ Alice decodes her as follows:

Alice calculates $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 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}}$ .
Alice defines a symmetric key $K$ ${\ displaystyle K}$ based on $Tr(g^{bk})\in GF(p^{2})$ ${\ displaystyle Tr (g ^ {bk}) \ in GF (p ^ {2})}$ .
Knowing that the message encryption algorithm is symmetric, Alice keyed $K$ ${\ displaystyle K}$ decrypts $E$ ${\ displaystyle E}$ receiving the original message $M$ ${\ displaystyle M}$ .

Thus, the message is transmitted.

Notes

↑ ¹ ² Lenstra, Arjen K .; Verheul, Eric R. An overview of the XTR public key system (neopr.) . Archived on April 15, 2006.
↑ Lenstra, Arjen K .; Verheul, Eric R. The XTR public key system (neopr.) .

[XTR-1-1] ¹ ² Lenstra, Arjen K .; Verheul, Eric R. An overview of the XTR public key system (neopr.) . Archived on April 15, 2006.

[XTR-2-2] Lenstra, Arjen K .; Verheul, Eric R. The XTR public key system (neopr.) .