XTR (abreviatura de ECSTR - "Representación de seguimiento de subgrupos eficiente y compacta") es un algoritmo de cifrado de clave pública basado en la complejidad computacional del problema del logaritmo discreto . Las ventajas de este algoritmo sobre otros que usan esta idea son una mayor velocidad y un tamaño de clave más pequeño.
Este algoritmo utiliza un generador de un subgrupo relativamente pequeño de orden ( es simple) del subgrupo . Con la elección correcta de , el logaritmo discreto en el grupo generado por , tiene la misma complejidad computacional que en . XTR usa aritmética en lugar de , lo que brinda la misma seguridad, pero con menos sobrecarga de cómputo y transferencia de datos.
El algoritmo trabaja en un campo finito . Considere un grupo de orden , y su subgrupo de orden q , donde p es un número primo , tal que otro número primo suficientemente grande q es divisor de . Un grupo de orden q se denomina subgrupo XTR. Este grupo cíclico es un subgrupo y tiene un generador g .
Sea p un número primo tal que p ≡ 2 mod 3 y p 2 - p + 1 es divisible por un número primo q suficientemente grande . Como p 2 ≡ 1 mod 3 , p genera . Por lo tanto, el polinomio circular es irreducible en . Por lo tanto, las raíces y forman una base normal óptima sobre y
Dado p ≡ 2 mod 3 :
Así, el costo de las operaciones aritméticas es el siguiente:
Los elementos conjugados de in son: él mismo y , y su suma es la traza .
Además:
Considere el generador de un grupo XTR de orden , donde es un número primo. Como es un subgrupo del grupo de orden , entonces . Además,
y
.De este modo,
Tenga en cuenta también que el conjugado del elemento es , es decir, tiene una norma igual a 1. La característica clave de XTR es que el polinomio mínimo en
simplificado a
En otras palabras, los elementos conjugados, como raíces del polinomio mínimo en , están completamente determinados por la traza . Un razonamiento similar es cierto para cualquier grado :
— este polinomio se define de la siguiente manera .
La idea del algoritmo es reemplazar con , es decir, calcular por en lugar de por .Sin embargo, para que el método sea efectivo, una forma de obtener rápidamente de los disponibles .
Definición: Para cada uno definimos:
Definición: Sean las raíces en , y . Denotar:
Propiedades y :
Enunciado: Sea .
Definición: Sea .
Al final de las iteraciones, , y . Si n es par, use para encontrar .
Para aprovechar la representación de los elementos del grupo en forma de sus trazas y garantizar la suficiente seguridad de los datos, es necesario encontrar simple y , donde es la característica del campo , y , y es el tamaño del subgrupo y el divisor . Indicar como y los tamaños y en bits. Para lograr el nivel de seguridad que, por ejemplo, proporciona RSA con una longitud de clave de 1024 bits, debe elegir tal que , es decir, a puede ser de aproximadamente 160. El primer algoritmo que le permite calcular tales números primos es Algoritmo UNA.
Algoritmo A
El algoritmo A es muy rápido, pero puede ser inseguro, ya que es vulnerable a un ataque de tamiz de campo numérico .
El Algoritmo B más lento se salva de esta deficiencia.
Algoritmo B
En la sección anterior, encontramos los tamaños tanto del campo final como del subgrupo multiplicativo en . Ahora necesitamos encontrar un subgrupo en para algunos tal que . Sin embargo, no es necesario buscar un elemento explícito , basta con encontrar un elemento tal que para el elemento de orden . Pero dado , el generador de grupos XTR se puede encontrar encontrando la raíz de . Para encontrar esto , considere la propiedad 5 . Habiendo encontrado tal , uno debe verificar si realmente es de orden , pero primero debe elegir c\in GF(p²), tal que F(c,\ X) es irreducible. El enfoque más simple es elegir al azar.
Enunciado: Para uno elegido al azar , la probabilidad de que - sea irreducible es mayor que 1/3.
Algoritmo de búsqueda básico :
Este algoritmo calcula el elemento de campo equivalente para algún pedido . [una]
Supongamos que Alice y Bob tienen una clave XTR pública y desean generar una clave privada compartida .
Supongamos que Alice tiene parte de la clave pública XTR: . Alice elige un número entero secreto y calcula y publica . Dada la clave pública de Alice , Bob puede cifrar el mensaje destinado a Alice usando el siguiente algoritmo:
Habiendo recibido un par , Alice lo descifra de la siguiente manera:
Por lo tanto, el mensaje se transmite.