XTR

Sea p un número primo tal que p  ≡ 2 mod 3 y p ² - p + 1 tiene un factor primo q suficientemente grande . Como p ² ≡ 1 mod 3, vemos que p genera   ${\displaystyle (\mathbb {Z} /3\mathbb {Z} )^{*}}$y por lo tanto el tercer polinomio ciclotómico${\displaystyle \Phi _{3}(x)=x^{2}+x+1}$ es irreductible sobre${\displaystyle GF(p)}$De ello se deduce que las raíces${\displaystyle \alpha }$y${\displaystyle \alpha ^{p}}$formar una base normal óptima para${\displaystyle GF(p^{2})}$encima${\displaystyle GF(p)}$y

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

Considerando que p ≡ 2 mod 3 podemos reducir los exponentes módulo 3 para obtener

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

El costo de las operaciones aritméticas se da ahora en el siguiente lema, etiquetado como Lema 2.21 en "Una descripción general del sistema de clave pública XTR" : ^{[ 1 ]}

Lema

• El cálculo de x ^p se realiza sin utilizar la multiplicación.
• Calcular x ² requiere dos multiplicaciones en${\displaystyle GF(p)}$
• Calcular xy requiere tres multiplicaciones en${\displaystyle GF(p)}$
• Calcular xz-yz ^p requiere cuatro multiplicaciones en${\displaystyle GF(p)}$.

El rastro en XTR siempre se considera terminado${\displaystyle GF(p^{2})}$. En otras palabras, los conjugados de${\displaystyle h\in GF(p^{6})}$encima${\displaystyle GF(p^{2})}$son${\displaystyle h,h^{p^{2}}}$y${\displaystyle h^{p^{4}}}$y el rastro de${\displaystyle h}$es su suma:

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

Tenga en cuenta que${\displaystyle Tr(h)\in GF(p^{2})}$desde

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

Consideremos ahora el generador.${\displaystyle g}$del subgrupo XTR de un orden primo${\displaystyle q}$Recuerda que${\displaystyle \langle g\rangle }$es un subgrupo del supergrupo XTR de orden${\displaystyle p^{2}-p+1}$, entonces${\displaystyle q\mid p^{2}-p+1}$En la siguiente sección veremos cómo elegir${\displaystyle p}$y${\displaystyle q}$, pero por ahora basta con suponer que${\displaystyle q>3}$Para calcular la traza de${\displaystyle g}$tenga en cuenta que módulo${\displaystyle p^{2}-p+1}$tenemos

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

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

y por lo tanto

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

El producto de los conjugados de${\displaystyle g}$igual${\displaystyle 1}$, es decir, que${\displaystyle g}$tiene norma 1.

La observación crucial en XTR es que el polinomio mínimo de${\displaystyle g}$encima${\displaystyle GF(p^{2})}$

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

simplifica a

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

que está totalmente determinado por${\displaystyle Tr(g)}$. En consecuencia, los conjugados de${\displaystyle g}$, como raíces del polinomio mínimo de${\displaystyle g}$encima${\displaystyle GF(p^{2})}$, están completamente determinados por el rastro de${\displaystyle g}$. Lo mismo es cierto para cualquier potencia de${\displaystyle g}$: conjugados de${\displaystyle g^{n}}$son raíces de polinomios

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

y este polinomio está completamente determinado por${\displaystyle Tr(g^{n})}$.

La idea detrás del uso de trazas es reemplazar${\displaystyle g^{n}\in GF(p^{6})}$en protocolos criptográficos, por ejemplo el intercambio de claves Diffie-Hellman por${\displaystyle Tr(g^{n})\in GF(p^{2})}$y así obtener una reducción de un factor de 3 en el tamaño de la representación. Sin embargo, esto solo es útil si hay una forma rápida de obtenerlo.${\displaystyle Tr(g^{n})}$dado${\displaystyle Tr(g)}$. El siguiente párrafo presenta un algoritmo para el cálculo eficiente de${\displaystyle Tr(g^{n})}$Además, la computación${\displaystyle Tr(g^{n})}$dado${\displaystyle Tr(g)}$resulta ser más rápido que la computación${\displaystyle g^{n}}$dado${\displaystyle g}$. ^{[ 1 ]}

A. Lenstra y E. Verheul presentan este algoritmo en su artículo titulado El sistema de clave pública XTR en ^{[ 2 ]} . Todas las definiciones y lemas necesarios para el algoritmo, así como el algoritmo mismo que se presenta aquí, se han tomado de dicho artículo.

Definición Para c en${\displaystyle GF(p^{2})}$definir

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

Definición Dejemos${\displaystyle h_{0},\!\ h_{1},h_{2}}$denotan las raíces, no necesariamente distintas, de${\displaystyle F(c,X)}$en${\displaystyle GF(p^{6})}$y dejar${\displaystyle n}$estar en${\displaystyle \mathbb {Z} }$. Definir

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

Propiedades de${\displaystyle c_{n}}$y${\displaystyle F(c,X)}$

1. ${\displaystyle c=c_{1}}$
2. ${\displaystyle c_{-n}=c_{np}=c_{n}^{p}}$
3. ${\displaystyle c_{n}\in GF(p^{2}){\text{ for }}n\in \mathbb {Z} }$
4. ${\displaystyle c_{u+v}=c_{u}c_{v}-c_{v}^{p}c_{u-v}+c_{u-2v}{\text{ for }}u,v\in \mathbb {Z} }$
5. O todo${\displaystyle h_{j}}$tener orden dividiendo${\displaystyle p^{2}-p+1}$y${\displaystyle >3}$o todos${\displaystyle h_{j}}$están en${\displaystyle GF(p^{2})}$. En particular,${\displaystyle F(c,X)}$es irreducible si y solo si sus raíces tienen orden divergente${\displaystyle p^{2}-p+1}$y${\displaystyle >3}$.
6. ${\displaystyle F(c,X)}$es reducible sobre${\displaystyle GF(p^{2})}$si y solo si${\displaystyle c_{p+1}\in GF(p)}$

Lemma Dejemos${\displaystyle c,\!\ c_{n-1},c_{n},c_{n+1}}$ be given.

1. Computing ${\displaystyle c_{2n}=c_{n}^{2}-2c_{n}^{p}}$ takes two multiplication in ${\displaystyle GF(p)}$.
2. Computing ${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$ takes four multiplication in ${\displaystyle GF(p)}$.
3. Computing ${\displaystyle c_{2n-1}=c_{n-1}\cdot c_{n}-c^{p}\cdot c_{n}^{p}+c_{n+1}^{p}}$ takes four multiplication in ${\displaystyle GF(p)}$.
4. Computing ${\displaystyle c_{2n+1}=c_{n+1}\cdot c_{n}-c\cdot c_{n}^{p}+c_{n-1}^{p}}$ takes four multiplication in ${\displaystyle GF(p)}$.

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

Algorithm 1 for computation of ${\displaystyle S_{n}(c)}$ given ${\displaystyle n}$ and ${\displaystyle c}$

• If ${\displaystyle n<0}$ apply this algorithm to ${\displaystyle -n}$ and ${\displaystyle c}$, and apply Property 2 to the resulting value.
• If ${\displaystyle n=0}$, then ${\displaystyle S_{0}(c)\!\ =(c^{p},3,c)}$.
• If ${\displaystyle n=1}$, then ${\displaystyle S_{1}(c)\!\ =(3,c,c^{2}-2c^{p})}$.
• If ${\displaystyle n=2}$, use the computation of ${\displaystyle c_{n+2}=c_{n+1}\cdot c-c^{p}\cdot c_{n}+c_{n-1}}$ and ${\displaystyle S_{1}(c)}$ to find ${\displaystyle c_{3}}$ and thereby ${\displaystyle S_{2}(c)}$.
• If ${\displaystyle n>2}$, to compute ${\displaystyle S_{n}(c)}$ define

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

and ${\displaystyle {\bar {m}}=n}$ if n is odd and ${\displaystyle {\bar {m}}=n-1}$ otherwise. Let ${\displaystyle {\bar {m}}=2m+1,k=1}$ and compute ${\displaystyle {\bar {S}}_{k}(c)=S_{3}(c)}$ using the Lemma above and ${\displaystyle S_{2}(c)}$. Let further

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

with ${\displaystyle m_{j}\in {0,1}}$ and ${\displaystyle m_{r}=1}$. For ${\displaystyle j=r-1,r-2,...,0}$ in succession, do the following:

• If ${\displaystyle m_{j}=0}$, use ${\displaystyle {\bar {S}}_{k}(c)}$ to compute ${\displaystyle {\bar {S}}_{2k}(c)}$.
• If ${\displaystyle m_{j}=1}$, use ${\displaystyle {\bar {S}}_{k}(c)}$ to compute ${\displaystyle {\bar {S}}_{2k+1}(c)}$.
• Replace ${\displaystyle k}$ by ${\displaystyle 2k+m_{j}}$.

When these iterations finish, ${\displaystyle k=m}$ and ${\displaystyle S_{\bar {m}}(c)={\bar {S}}_{m}(c)}$. If n is even use ${\displaystyle S_{\bar {m}}(c)}$ to compute ${\displaystyle {\bar {S}}_{m+1}(c)}$.

In order to take advantage of the above described representations of elements with their traces and furthermore ensure sufficient security, that will be discussed below, we need to find primes ${\displaystyle p}$ and ${\displaystyle q}$, where ${\displaystyle p}$ denotes the characteristic of the field ${\displaystyle GF(p^{6})}$ with ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$ and ${\displaystyle q}$ is the size of the subgroup, such that ${\displaystyle q}$ divides ${\displaystyle p^{2}-p+1}$.

We denote with ${\displaystyle P}$ and ${\displaystyle Q}$ the sizes of ${\displaystyle p}$ and ${\displaystyle q}$ in bits. To achieve security comparable to 1024-bit RSA, we should choose ${\displaystyle 6P}$ about 1024, i.e. ${\displaystyle P\approx 170}$ and ${\displaystyle Q}$ can be around 160.

A first easy algorithm to compute such primes ${\displaystyle p}$ and ${\displaystyle q}$ is the next Algorithm A:

Algorithm A

1. Find ${\displaystyle r\in \mathbb {Z} }$ such that ${\displaystyle q=r^{2}-r+1}$ is a ${\displaystyle Q}$-bit prime.
2. Find ${\displaystyle k\in \mathbb {Z} }$ such that ${\displaystyle p=r+k\cdot q}$ is a ${\displaystyle P}$-bit prime with ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$.

Correctness of Algorithm A:

It remains to check that ${\displaystyle q\mid p^{2}-p+1}$ because all the other necessary properties are obviously satisfied per definition of ${\displaystyle p}$ and ${\displaystyle q}$. We easily see that ${\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)}$ which implies that ${\displaystyle q\mid p^{2}-p+1}$.

Algorithm A is very fast and can be used to find primes ${\displaystyle p}$ that satisfy a degree-two polynomial with small coefficients. Such ${\displaystyle p}$ lead to fast arithmetic operations in ${\displaystyle GF(p)}$. In particular if the search for ${\displaystyle k}$ is restricted to ${\displaystyle k=1}$, which means looking for an ${\displaystyle r}$ such that both ${\displaystyle r^{2}-r+1{\text{ and }}r^{2}+1}$ are prime and such that ${\displaystyle r^{2}+1\equiv 2{\text{ mod }}3}$, the primes ${\displaystyle p}$ have this nice form. Note that in this case ${\displaystyle r}$ must be even and ${\displaystyle r\equiv 1{\text{ mod }}4}$.

On the other hand, such ${\displaystyle p}$ may be undesirable from a security point of view because they may make an attack with the Discrete Logarithm variant of the Number Field Sieve easier.

The following Algorithm B doesn't have this disadvantage, but it also doesn't have the fast arithmetic modulo ${\displaystyle p}$ Algorithm A has in that case.

Algorithm B

1. Select a ${\displaystyle Q}$-bit prime ${\displaystyle q}$ so that ${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$.
2. Find the roots ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ of ${\displaystyle X^{2}-X+1\ {\text{mod}}\ q}$.
3. Find a ${\displaystyle k\in \mathbb {Z} }$ such that ${\displaystyle p=r_{i}+k\cdot q}$ is a ${\displaystyle P}$-bit prime with ${\displaystyle p\equiv 2\ {\text{mod}}\ 3}$ for ${\displaystyle i\in \{1,2\}}$

Correctness of Algorithm B:

Since we chose ${\displaystyle q\equiv 7\ {\text{mod}}\ 12}$ it follows immediately that ${\displaystyle q\equiv 1\ {\text{mod}}\ 3}$ (because ${\displaystyle 7\equiv 1\ {\text{mod}}\ 3}$ and ${\displaystyle 3\mid 12}$). From that and quadratic reciprocity we can deduce that ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ exist.

To check that ${\displaystyle q\mid p^{2}-p+1}$ we consider again ${\displaystyle p^{2}-p+1}$ for ${\displaystyle r_{i}\in \{1,2\}}$ and get that ${\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)}$, since ${\displaystyle r_{1}}$ and ${\displaystyle r_{2}}$ are roots of ${\displaystyle X^{2}-X+1}$ and hence ${\displaystyle q\mid p^{2}-p+1}$.

In the last paragraph we have chosen the sizes ${\displaystyle p}$ and ${\displaystyle q}$ of the finite field ${\displaystyle GF(p^{6})}$ and the multiplicative subgroup of ${\displaystyle GF(p^{6})^{*}}$, now we have to find a subgroup ${\displaystyle \langle g\rangle }$ of ${\displaystyle GF\!\ (p^{6})^{*}}$ for some ${\displaystyle g\in GF(p^{6})}$ such that ${\displaystyle \mid \!\!\langle g\rangle \!\!\mid =q}$.

However, we do not need to find an explicit ${\displaystyle g\in GF(p^{6})}$, it suffices to find an element ${\displaystyle c\in GF(p^{2})}$ such that ${\displaystyle c=Tr(g)}$ for an element ${\displaystyle g\in GF(p^{6})}$ of order ${\displaystyle q}$. But, given ${\displaystyle Tr(g)}$, a generator ${\displaystyle g}$ of the XTR (sub)group can be found by determining any root of ${\displaystyle F(Tr(g),\ X)}$que se ha definido anteriormente . Para encontrar tal${\displaystyle c}$podemos echar un vistazo a la propiedad 5 de${\displaystyle F(c,\ X)}$aquí afirmando que las raíces de${\displaystyle F(c,\ X)}$tener un orden de división${\displaystyle p^{2}-p+1}$si y solo si${\displaystyle F(c,\ X)}$es irreductible . Después de encontrar tal${\displaystyle c}$Necesitamos comprobar si realmente está en orden.${\displaystyle q}$, pero primero nos centraremos en cómo seleccionar${\displaystyle c\in GF(p^{2})}$de tal manera que${\displaystyle F(c,\ X)}$es irreductible.

Un enfoque inicial es seleccionar${\displaystyle c\in GF(p^{2})\backslash GF(p)}$aleatoriamente, lo cual se justifica por el siguiente lema.

Lema: Para un elemento seleccionado aleatoriamente${\displaystyle c\in GF(p^{2})}$la probabilidad de que${\displaystyle F(c,\ X)=X^{3}-cX^{2}+c^{p}X-1\in GF(p^{2})[X]}$es irreducible es aproximadamente un tercio.

Ahora bien, el algoritmo básico para encontrar uno adecuado${\displaystyle Tr(g)}$es el siguiente:

Esquema del algoritmo

1. Elige uno al azar${\displaystyle c\in GF(p^{2})\backslash GF(p)}$.
2. Si${\displaystyle F(c,\ X)}$Si es reducible, entonces vuelva al Paso 1.
3. Utilice el algoritmo 1 para calcular${\displaystyle d=c_{(p^{2}-p+1)/q}}$.
4. Si${\displaystyle d}$no está de orden${\displaystyle q}$, vuelva al paso 1.
5. Dejar${\displaystyle Tr(g)=d}$.

Resulta que este algoritmo efectivamente calcula un elemento de${\displaystyle GF(p^{2})}$eso es igual a${\displaystyle Tr(g)}$para algunos${\displaystyle g\in GF(p^{6})}$del orden${\displaystyle q}$.

Se pueden encontrar más detalles sobre el algoritmo, su corrección, tiempo de ejecución y la demostración del lema en "Una descripción general del sistema de clave pública XTR" en ^{[ 1 ] .}

Suponemos que tanto Alice como Bob tienen acceso a los datos de la clave pública XTR.${\displaystyle \left(p,q,Tr(g)\right)}$y tienen la intención de acordar una clave secreta compartida.${\displaystyle K}$Pueden hacerlo utilizando la siguiente versión XTR del intercambio de claves Diffie-Hellman:

1. Alice elige${\displaystyle a\in \mathbb {Z} }$aleatoriamente con${\displaystyle 1<a<q-2}$, se calcula con el Algoritmo 1${\displaystyle S_{a}(Tr(g))=\left(Tr(g^{a-1}),Tr(g^{a}),Tr(g^{a+1})\right)\in GF(p^{2})^{3}}$y envía${\displaystyle Tr(g^{a})\in GF(p^{2})}$a Bob.
2. Bob recibe${\displaystyle Tr(g^{a})}$De Alicia, selecciona al azar${\displaystyle b\in \mathbb {Z} }$con${\displaystyle 1<b<q-2}$, aplica el Algoritmo 1 para calcular${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$y envía ${\displaystyle Tr(g^{b})\in GF(p^{2})}$a Alicia.
3. Alicia recibe${\displaystyle Tr(g^{b})}$De Bob, calcula con el Algoritmo 1${\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}}$y determina${\displaystyle K}$Residencia en${\displaystyle Tr(g^{ab})\in GF(p^{2})}$.
4. Bob aplica de forma análoga el Algoritmo 1 para calcular${\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}}$y también determina${\displaystyle K}$Residencia en${\displaystyle Tr(g^{ab})\in GF(p^{2})}$.

Para el cifrado ElGamal, suponemos ahora que Alice es la propietaria de los datos de la clave pública XTR.${\displaystyle (p,q,Tr(g))}$y que ha seleccionado un número entero secreto${\displaystyle k}$, calculado${\displaystyle Tr(g^{k})}$y publicó el resultado. Dados los datos de clave pública XTR de Alice${\displaystyle \left(p,q,Tr(g),Tr(g^{k})\right)}$Bob puede cifrar un mensaje${\displaystyle M}$, destinado a Alice, utilizando la siguiente versión XTR del cifrado ElGamal:

1. Bob selecciona al azar un${\displaystyle b\in \mathbb {Z} }$con${\displaystyle 1<b<q-2}$y calcula con el Algoritmo 1${\displaystyle S_{b}(Tr(g))=\left(Tr(g^{b-1}),Tr(g^{b}),Tr(g^{b+1})\right)\in GF(p^{2})^{3}}$.
2. A continuación, Bob aplica el Algoritmo 1 para calcular${\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}}$.
3. Bob determina una clave de cifrado simétrico.${\displaystyle K}$Residencia en${\displaystyle Tr(g^{bk})\in GF(p^{2})}$.
4. Bob utiliza un método de cifrado simétrico acordado con clave${\displaystyle K}$para encriptar su mensaje${\displaystyle M}$lo que da como resultado el cifrado${\displaystyle E}$.
5. Bob envía${\displaystyle (Tr(g^{b}),\ E)}$a Alicia.

Al recibir${\displaystyle (Tr(g^{b}),\ E)}$Alice descifra el mensaje de la siguiente manera:

1. Alice calcula${\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}}$.
2. Alice determina la clave simétrica.${\displaystyle K}$Residencia en${\displaystyle Tr(g^{bk})\in GF(p^{2})}$.
3. Alice utiliza el método de cifrado simétrico acordado con clave${\displaystyle K}$para descifrar${\displaystyle E}$lo que da como resultado el mensaje original${\displaystyle M}$.

El esquema de cifrado aquí descrito se basa en una versión híbrida común del cifrado ElGamal, donde la clave secreta${\displaystyle K}$se obtiene mediante un sistema de clave pública asimétrica y luego el mensaje se cifra con un método de cifrado de clave simétrica acordado por Alice y Bob.

En el cifrado ElGamal más tradicional, el mensaje está restringido al espacio de claves, que en este caso sería${\displaystyle GF(p^{2})}$, porque${\displaystyle Tr(g)\in GF(p^{2})\ \forall p\in GF(p^{6})^{*}}$El cifrado en este caso es la multiplicación del mensaje por la clave, que es una operación invertible en el espacio de claves.${\displaystyle GF(p^{2})}$.

Concretamente, esto significa que si Bob quiere cifrar un mensaje${\displaystyle M\!\ '}$, primero tiene que convertirlo en un elemento${\displaystyle M}$de${\displaystyle GF(p^{2})}$y luego calcular el mensaje cifrado${\displaystyle E}$como${\displaystyle E=K\cdot M\in GF(p^{2})}$Tras la recepción del mensaje cifrado${\displaystyle E}$Alice puede recuperar el mensaje original.${\displaystyle M}$mediante computación${\displaystyle M=E\cdot K^{-1}}$, dónde${\displaystyle K^{-1}}$es lo inverso de${\displaystyle K}$en${\displaystyle GF(p^{2})}$.

Dejemos que ahora${\displaystyle \langle \gamma \rangle }$ser un grupo multiplicativo de orden${\displaystyle \omega }$. La seguridad del protocolo Diffie-Hellman en${\displaystyle \langle \gamma \rangle }$Se basa en el problema de Diffie-Hellman (DH) de computación.${\displaystyle \gamma ^{xy}{\text{ given }}\gamma ,\gamma ^{x}{\text{ and }}\gamma ^{y}}$. Nosotros escribimos${\displaystyle DH(\gamma ^{x},\ \gamma ^{y})=\gamma ^{xy}}$. Hay otros dos problemas relacionados con el problema DH. El primero es el problema de decisión de Diffie-Hellman (DHD) para determinar si${\displaystyle c=DH(a,b)}$para dado${\displaystyle a,b,c\in \langle \gamma \rangle }$y el segundo es el problema del logaritmo discreto (DL) para encontrar${\displaystyle x=DL(a)}$para un dado${\displaystyle a=\gamma ^{x}\in \langle \gamma \rangle {\text{ with }}0\leq x<\omega }$.

El problema DL es al menos tan difícil como el problema DH y generalmente se supone que si el problema DL en${\displaystyle \langle \gamma \rangle }$Si es intratable, entonces también lo son los otros dos.

Dada la factorización prima de${\displaystyle \omega }$el problema DL en${\displaystyle \langle \gamma \rangle }$puede reducirse al problema DL en todos los subgrupos de${\displaystyle \langle \gamma \rangle }$con orden primo debido al algoritmo de Pohlig-Hellman . Por lo tanto${\displaystyle \omega }$Se puede asumir con seguridad que es primo.

Para un subgrupo${\displaystyle \langle \gamma \rangle }$de orden primo${\displaystyle \omega }$del grupo multiplicativo${\displaystyle GF\left(p^{t}\right)^{*}}$de un campo de extensión${\displaystyle GF(p^{t})}$de${\displaystyle GF(p)}$para algunos${\displaystyle t}$Ahora existen dos formas posibles de atacar el sistema. Se puede enfocar en todo el grupo multiplicativo o en el subgrupo. Para atacar el grupo multiplicativo, el método más conocido es la variante del logaritmo discreto de la criba de cuerpos numéricos o, alternativamente, en el subgrupo se puede utilizar uno de varios métodos que toman${\displaystyle {\mathcal {O}}({\sqrt {\omega }})}$operaciones en${\displaystyle \langle \gamma \rangle }$, como el método rho de Pollard .

Para ambos enfoques la dificultad del problema DL en${\displaystyle \langle \gamma \rangle }$depende del tamaño del subcampo circundante mínimo de${\displaystyle \langle \gamma \rangle }$y en el tamaño de su orden primo${\displaystyle \omega }$. Si${\displaystyle GF\left(p^{t}\right)}$en sí mismo es el subcampo circundante mínimo de${\displaystyle \langle \gamma \rangle }$y${\displaystyle \omega }$es suficientemente grande, entonces el problema DL en${\displaystyle \langle \gamma \rangle }$es tan difícil como el problema general de DL en${\displaystyle GF\left(p^{t}\right)}$.

Los parámetros XTR ahora se eligen de tal manera que${\displaystyle p}$no es pequeño,${\displaystyle q}$es suficientemente grande y${\displaystyle \langle g\rangle }$no puede estar integrado en un verdadero subcampo de${\displaystyle GF(p^{6})}$, desde${\displaystyle q\mid p^{2}-p+1}$y${\displaystyle p^{2}-p+1}$es un divisor de${\displaystyle \mid \!GF(p^{6})^{*}\!\mid =p^{6}-1}$pero no divide${\displaystyle p^{s}-1{\text{ for }}s\in \{1,2,3\}}$y por lo tanto${\displaystyle \langle g\rangle }$no puede ser un subgrupo de${\displaystyle GF\!\ (p^{s})^{*}}$para${\displaystyle s\in \{1,2,3\}}$. De ello se deduce que el problema DL en el grupo XTR puede considerarse tan difícil como el problema DL en${\displaystyle GF(p^{6})}$.

Los protocolos criptográficos basados ​​en logaritmos discretos pueden utilizar diversos subgrupos, como grupos de puntos de curvas elípticas o subgrupos del grupo multiplicativo de un cuerpo finito, como el grupo XTR. Como vimos anteriormente, las versiones XTR de los protocolos de cifrado Diffie-Hellman y ElGamal sustituyen el uso de elementos del grupo XTR por el uso de sus trazas. Esto significa que la seguridad de las versiones XTR de estos esquemas de cifrado ya no se basa en los problemas DH, DHD o DL originales. Por lo tanto, es necesario definir las versiones XTR de dichos problemas, y veremos que son equivalentes (en el sentido de la siguiente definición) a los problemas originales.

Definiciones:

• Definimos el problema XTR-DH como el problema de computación.${\displaystyle Tr(g^{xy})}$dado${\displaystyle Tr(g^{x})}$y${\displaystyle Tr(g^{y})}$y escribimos${\displaystyle XDH(g^{x},\ g^{y})=g^{xy}}$.
• El problema XTR-DHD es el problema de determinar si${\displaystyle XDH(a,b)=c}$para${\displaystyle a,b,c\in Tr(\langle g\rangle )}$.
• Dado${\displaystyle a\in Tr(\langle g\rangle )}$, el problema XTR-DL es encontrar${\displaystyle x=XDL(a)}$, es decir${\displaystyle 0\leq x<q}$de tal manera que${\displaystyle a=Tr(g^{x})}$.
• Decimos que ese problema${\displaystyle {\mathcal {A}}}$es (a,b)-equivalente al problema${\displaystyle {\mathcal {B}}}$, si se presenta algún problema${\displaystyle {\mathcal {A}}}$(o${\displaystyle {\mathcal {B}}}$) se puede resolver con como máximo a (o b) llamadas a un algoritmo de resolución de problemas${\displaystyle {\mathcal {B}}}$(o${\displaystyle {\mathcal {A}}}$).

Tras presentar las versiones XTR de estos problemas, el siguiente teorema revela un resultado importante que establece la conexión entre los problemas XTR y los que no lo son, los cuales, de hecho, son equivalentes. Esto implica que la representación XTR de los elementos con sus trazas es, como se ha visto anteriormente, tres veces más rápida que la representación habitual sin comprometer la seguridad.

Teorema: Se cumplen las siguientes equivalencias:

i. El problema XTR-DL es (1,1)-equivalente al problema DL en${\displaystyle \langle g\rangle }$.

ii. El problema XTR-DH es (1,2)-equivalente al problema DH en${\displaystyle \langle g\rangle }$.

iii. El problema XTR-DHD es (3,2)-equivalente al problema DHD en${\displaystyle \langle g\rangle }$.

Esto significa que un algoritmo que resuelve XTR-DL, XTR-DH o XTR-DHD con una probabilidad no despreciable puede transformarse en un algoritmo que resuelve el problema no XTR correspondiente DL, DH o DHD con una probabilidad no despreciable y viceversa. En particular, la parte ii. implica que determinar la clave pequeña XTR-DH (siendo un elemento de${\displaystyle GF(p^{2})}$) es tan difícil como determinar toda la clave DH (siendo un elemento de${\displaystyle GF(p^{6})}$) en el grupo de representación${\displaystyle \langle g\rangle }$.