NTRUEncrypt

El criptosistema de clave pública NTRUEncrypt , también conocido como algoritmo de cifrado NTRU , es una alternativa basada en retículos NTRU a RSA y la criptografía de curva elíptica (ECC), y se basa en el problema del vector más corto en un retículo (que no se sabe que se pueda romper utilizando computadoras cuánticas ).

Se basa en la supuesta dificultad de factorizar ciertos polinomios en un anillo de polinomios truncado en un cociente de dos polinomios con coeficientes muy pequeños. Romper el criptosistema está estrechamente relacionado, aunque no es equivalente, con el problema algorítmico de la reducción de retículos en ciertos retículos . Es necesaria una cuidadosa selección de parámetros para frustrar algunos ataques publicados.

Dado que tanto el cifrado como el descifrado utilizan únicamente multiplicaciones polinómicas simples, estas operaciones son muy rápidas en comparación con otros esquemas de cifrado asimétrico, como RSA, ElGamal y la criptografía de curva elíptica . Sin embargo, NTRUEncrypt aún no ha sido sometido a un análisis criptográfico comparable en su forma implementada.

Un algoritmo relacionado es el algoritmo de firma digital NTRUSign .

Específicamente, las operaciones NTRU se basan en objetos en un anillo de polinomio truncado.${\displaystyle \ R=\mathbb {Z} [X]/(X^{N}-1)}$con multiplicación por convolución y todos los polinomios en el anillo tienen coeficientes enteros y grado como máximo N -1:

${\displaystyle {\textbf {a}}=a_{0}+a_{1}X+a_{2}X^{2}+\cdots +a_{N-2}X^{N-2}+a_{N-1}X^{N-1}}$

Eso${\displaystyle X^{N}=1}$en este anillo tiene el efecto de que multiplicar un polinomio por${\displaystyle X}$rota los coeficientes del polinomio. Un mapa de la forma${\displaystyle f\mapsto fg}$por un fijo${\displaystyle g\in R}$de esta manera se obtiene un nuevo polinomio.${\displaystyle fg}$donde cada coeficiente depende de tantos coeficientes como${\displaystyle f}$ya que hay coeficientes distintos de cero en${\displaystyle g}$.

NTRU tiene tres parámetros enteros ( N , p , q ), donde N es el límite del grado polinómico, p se denomina módulo pequeño y q se denomina módulo grande; se supone que N es primo , q siempre es (mucho) mayor que p , y p y q son coprimos . Los mensajes en texto plano son polinomios módulo p, pero los mensajes cifrados son polinomios módulo q . Concretamente, el texto cifrado consiste en el mensaje en texto plano más un múltiplo elegido aleatoriamente de la clave pública, pero la clave pública en sí misma puede considerarse un múltiplo del módulo pequeño p , lo que permite al poseedor de la clave privada extraer el texto plano del texto cifrado.

El criptosistema de clave pública NTRUEncrypt es relativamente nuevo. La primera versión, simplemente llamada NTRU, fue desarrollada alrededor de 1996 por tres matemáticos ( Jeffrey Hoffstein , Jill Pipher y Joseph H. Silverman ). En 1996, estos matemáticos, junto con Daniel Lieman, fundaron NTRU Cryptosystems, Inc. y obtuvieron una patente ^{[ 1 ]} (actualmente caducada) sobre el criptosistema.

Durante los últimos diez años, se ha trabajado en la mejora del criptosistema. Desde su primera presentación, se han introducido cambios para optimizar tanto su rendimiento como su seguridad. La mayoría de las mejoras de rendimiento se centraron en acelerar el proceso. Hasta 2005, se pueden encontrar documentos que describen fallos de descifrado del NTRUEncrypt. En cuanto a la seguridad, desde la primera versión del NTRUEncrypt, se han introducido nuevos parámetros que parecen ser seguros frente a todos los ataques conocidos y que permiten un aumento razonable de la capacidad de cálculo.

Ahora el sistema está totalmente aceptado según los estándares IEEE P1363, dentro de las especificaciones para criptografía de clave pública basada en retículos ( IEEE P1363.1 ). Debido a la velocidad del criptosistema de clave pública NTRUEncrypt (consulte http://bench.cr.yp.to para ver los resultados de las pruebas de rendimiento) y su bajo consumo de memoria (véase más abajo ) , puede utilizarse en aplicaciones como dispositivos móviles y tarjetas inteligentes . En abril de 2011, NTRUEncrypt fue aceptado como estándar X9.98 para su uso en el sector de los servicios financieros. ^{[ 2 ]}

Sending a secret message from Alice to Bob requires the generation of a public and a private key. The public key is known by both Alice and Bob and the private key is only known by Bob. To generate the key pair two polynomials f and g, with degree at most ${\displaystyle \ N-1}$ and with coefficients in {-1,0,1} are required. They can be considered as representations of the residue classes of polynomials modulo ${\displaystyle \ X^{N}-1}$ in R. The polynomial ${\displaystyle {\textbf {f}}\en L_ {f}}$ must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithm) exist, which means that ${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}}$ and ${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}}$ must hold. So when the chosen f is not invertible, Bob has to go back and try another f.

Both f and ${\displaystyle \ \mathbf {f} _{p}}$ (and ${\displaystyle \mathbf {g} }$) are Bob's private key. The public key h is generated computing the quantity

${\displaystyle {\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {q}}.}$

Example: In this example the parameters (N, p, q) will have the values N = 11, p = 3 and q = 32 and therefore the polynomials f and g are of degree at most 10. The system parameters (N, p, q) are known to everybody. The polynomials are randomly chosen, so suppose they are represented by

${\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}$

${\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}$

Using the Euclidean algorithm the inverse of f modulo p and modulo q, respectively, is computed

${\displaystyle {\textbf {f}}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod {3}}}$

${\displaystyle {\textbf {f}}_{q}=5+9X+6X^{2}+16X^{3}+4X^{4}+15X^{5}+16X^{6}+22X^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}}$

Which creates the public key h (known to both Alice and Bob) computing the product

${\displaystyle {\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {32}}=8-7X-10X^{2}-12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}}$

Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients in ${\displaystyle [-p/2,p/2]}$. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation. After creating the message polynomial, Alice randomly chooses a polynomial r with small coefficients (not restricted to the set {-1,0,1}), that is meant to obscure the message.

With Bob's public key h the encrypted message e is computed:

${\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}}$

This ciphertext hides Alice's messages and can be sent safely to Bob.

Example: Assume that Alice wants to send a message that can be written as polynomial

${\displaystyle {\textbf {m}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}$

and that the randomly chosen ‘blinding value’ can be expressed as

${\displaystyle {\textbf {r}}=-1+X^{2}+X^{3}+X^{4}-X^{5}-X^{7}}$

The ciphertext e that represents her encrypted message to Bob will look like

${\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {32}}=14+11X+26X^{2}+24X^{3}+14X^{4}+16X^{5}+30X^{6}+7X^{7}+25X^{8}+6X^{9}+19X^{10}{\pmod {32}}}$

Cualquiera que conozca r podría calcular el mensaje m evaluando e - rh ; por lo tanto, Alice no debe revelar r . Además de la información disponible públicamente, Bob conoce su propia clave privada. Así es como puede obtener m : primero multiplica el mensaje cifrado e por parte de su clave privada f.

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

Al reescribir los polinomios, esta ecuación representa en realidad el siguiente cálculo:

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\pmod {q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\pmod {q}}}$

${\displaystyle {\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\pmod {q}}}$

En lugar de elegir los coeficientes de a entre 0 y q – 1, se eligen en el intervalo [- q /2, q /2] para evitar que el mensaje original no se pueda recuperar correctamente, ya que Alice elige las coordenadas de su mensaje m en el intervalo [- p /2, p /2]. Esto implica que todos los coeficientes de${\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}}$ya se encuentran dentro del intervalo [- q /2, q /2] porque los polinomios r , g , f y m y el primo p tienen coeficientes pequeños en comparación con q . Esto significa que todos los coeficientes permanecen sin cambios durante la reducción módulo q y que el mensaje original puede recuperarse correctamente.

El siguiente paso será calcular un módulo p :

${\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}}$

porque${\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0}$.

Sabiendo que Bob puede usar la otra parte de su clave privada${\displaystyle \ \left({\textbf {f}}_{p}\right)}$para recuperar el mensaje de Alice mediante la multiplicación de b y${\displaystyle \ {\textbf {f}}_{p}}$

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}}$

${\displaystyle {\textbf {c}}={\textbf {m}}{\pmod {p}}}$

porque la propiedad${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}}$se requería para${\displaystyle \ {\textbf {f}}_{p}}$.

Ejemplo : El mensaje cifrado e de Alice a Bob se multiplica por el polinomio f.

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {32}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}},}$

donde Bob utiliza el intervalo [- q /2, q /2] en lugar del intervalo [0, q – 1] para los coeficientes del polinomio a para evitar que el mensaje original no se pueda recuperar correctamente.

La reducción de los coeficientes de un módulo p da como resultado

${\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {3}}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod {3}}}$

lo cual es igual a${\displaystyle \ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}}$.

En el último paso el resultado se multiplica por${\displaystyle \ {\textbf {f}}_{p}}$desde la clave privada de Bob para terminar con el mensaje original m

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}}$

${\displaystyle {\textbf {c}}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}$

¡Ese es precisamente el mensaje original que Alice le envió a Bob!

Desde la propuesta de NTRU se han introducido varios ataques al criptosistema de clave pública NTRUEncrypt. La mayoría de los ataques se centran en lograr una ruptura total encontrando la clave secreta f en lugar de simplemente recuperar el mensaje m . Si se sabe que f tiene muy pocos coeficientes distintos de cero, Eve puede realizar con éxito un ataque de fuerza bruta probando todos los valores para f . Cuando Eve quiere saber si f ' es la clave secreta, simplemente calcula${\displaystyle \ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}}$. Si tiene coeficientes pequeños, podría ser la clave secreta f , y Eve puede comprobar si f ´ es la clave secreta usándola para descifrar un mensaje que ella misma cifró. Eve también podría probar valores de g y comprobar si ${\displaystyle \ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}}$tiene valores pequeños.

Es posible realizar un ataque de encuentro en el medio que es más potente. Puede reducir el tiempo de búsqueda en raíz cuadrada. El ataque se basa en la propiedad de que${\displaystyle \ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}}$.

Eve quiere encontrar ${\displaystyle \ {\textbf {f}}_{1}}$y${\displaystyle \ {\textbf {f}}_{2}}$de tal manera que${\displaystyle \ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}}$posee y de tal manera que tengan la propiedad

${\displaystyle \left({\textbf {f}}_{1}+{\textbf {f}}_{2}\right)\cdot {\textbf {h}}={\textbf {g}}{\pmod {q}}}$

${\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$

Si f tiene d unos y N - d ceros, entonces Eve crea todos los posibles${\displaystyle \ {\textbf {f}}_{1}}$y${\displaystyle \ {\textbf {f}}_{2}}$en el que ambos tienen longitud${\displaystyle \ {\frac {1}{2}}N}$(p.ej${\displaystyle \ {\textbf {f}}_{1}}$cubre el${\displaystyle \ {\frac {1}{2}}N}$coeficientes más bajos de f y${\displaystyle \ {\textbf {f}}_{2}}$el más alto) con d /2 unos. Luego calcula${\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}}$a pesar de${\displaystyle \ {\textbf {f}}_{1}}$y los ordena en contenedores según las primeras k coordenadas. Después de eso, calcula todos${\displaystyle \ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$y los ordena en contenedores no solo en función de las primeras k coordenadas, sino también en función de lo que sucede si se suma 1 a las primeras k coordenadas. Luego se comprueban los contenedores que contienen ambos${\displaystyle \ {\textbf {f}}_{1}}$y${\displaystyle \ {\textbf {f}}_{2}}$y ver si la propiedad${\displaystyle \ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$sostiene.

El ataque de reducción de retículos es uno de los métodos más conocidos y prácticos para romper NTRUEncrypt. En cierto modo, se puede comparar con la factorización del módulo en RSA. El algoritmo más utilizado para este ataque es el algoritmo Lenstra-Lenstra-Lovász . Dado que la clave pública h contiene tanto f como g, se puede intentar obtenerlas a partir de h . Sin embargo, resulta muy difícil encontrar la clave secreta cuando los parámetros de NTRUEncrypt se eligen con la seguridad suficiente. El ataque de reducción de retículos se vuelve más difícil si la dimensión del retículo aumenta y el vector más corto se alarga.

El ataque de cifrado elegido también permite recuperar la clave secreta f , lo que resulta en una ruptura total del sistema. En este ataque, Eve intenta obtener su propio mensaje a partir del texto cifrado y, por lo tanto, intenta obtener la clave secreta. En este ataque, Eve no interactúa con Bob.

Cómo funciona :

La primera Eva crea un texto cifrado${\displaystyle \ {\textbf {e}}=c{\textbf {h}}+c}$de tal manera que${\displaystyle \ c=0{\pmod {p}},c<{\frac {q}{2}}}$y${\displaystyle \ 2c>{\frac {q}{2}}}$Cuando Eva escribe los pasos para descifrar e (sin calcular realmente los valores ya que no conoce f) encuentra${\displaystyle \ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$:

${\displaystyle {\textbf {a}}={\textbf {f}}\left(c{\textbf {h}}+c\right){\pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK}$

En el cual${\displaystyle \ K=\sum k_{i}x^{i}}$ de tal manera que

${\displaystyle k_{i}={\begin{cases}1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1,\\-1&{\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1,\\0&{\text{otherwise.}}\end{cases}}}$

Ejemplo :

${\displaystyle {\textbf {f}}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}$

${\displaystyle {\textbf {g}}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}$

Entonces K se convierte en${\displaystyle \ K=-1+X^{2}-X^{10}}$.

Reducir los coeficientes de un módulo p realmente reduce los coeficientes de${\displaystyle \ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}}$. Después de la multiplicación con${\displaystyle \ {\textbf {f}}_{p}}$Eve descubre:

${\displaystyle {\textbf {m}}=c{\textbf {f}}_{p}\cdot {\textbf {g}}+c{\textbf {f}}_{p}\cdot {\textbf {f}}-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

${\displaystyle {\textbf {m}}=c{\textbf {h}}+c-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

Como c fue elegido como un múltiplo de p , m puede escribirse como

${\displaystyle {\textbf {m}}=-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

Lo que significa que${\displaystyle \ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}}$.

Ahora bien, si f y g tienen pocos coeficientes que son iguales en los mismos factores, K tiene pocos coeficientes distintos de cero y, por lo tanto, es pequeño. Al probar diferentes valores de K, el atacante puede recuperar f .

Al cifrar y descifrar un mensaje según NTRUEncrypt, el atacante puede comprobar si la función f es la clave secreta correcta o no.

Utilizando los parámetros sugeridos más recientes (véase más abajo ), el sistema criptográfico de clave pública NTRUEncrypt es seguro frente a la mayoría de los ataques. Sin embargo, persiste un dilema entre rendimiento y seguridad. Es difícil mejorar la seguridad sin reducir la velocidad, y viceversa.

Una forma de acelerar el proceso sin dañar la efectividad del algoritmo es realizar algunos cambios en la clave secreta f . Primero, construya f de tal manera que${\displaystyle \ {\textbf {f}}=1+p{\textbf {F}}}$, en la que F es un polinomio pequeño (es decir, coeficientes {-1,0, 1}). Al construir f de esta manera, f es invertible módulo p . De hecho${\displaystyle \ {\textbf {f}}^{-1}=1{\pmod {p}}}$lo que significa que Bob no tiene que calcular realmente la inversa y que Bob no tiene que llevar a cabo el segundo paso del descifrado. Por lo tanto, construir f de esta manera ahorra mucho tiempo, pero no afecta la seguridad de NTRUEncrypt porque solo es más fácil encontrar${\displaystyle \ {\textbf {f}}_{p}}$pero f sigue siendo difícil de recuperar. En este caso, f tiene coeficientes distintos de -1, 0 o 1, debido a la multiplicación por p . Pero como Bob multiplica por p para generar la clave pública h , y luego reduce el texto cifrado módulo p , esto no afectará al método de cifrado.

En segundo lugar, f puede expresarse como el producto de varios polinomios, de manera que estos tengan muchos coeficientes cero. De este modo, se requieren menos cálculos.

Según la presentación NTRU NIST de 2020 ^{[ 3 ],} los siguientes parámetros se consideran seguros:

• Jaulmes, E. y Joux, A. Un ataque de texto cifrado elegido contra NTRU. Lecture Notes in Computer Science; Vol. 1880. Actas de la 20.ª Conferencia Internacional Anual de Criptología sobre Avances en Criptografía. págs.  20-35, 2000.
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: Un criptosistema de clave pública basado en anillos . En Teoría Algorítmica de Números (ANTS III), Portland, OR, junio de 1998, JP Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlín, 1998, 267–288.
• Howgrave-Graham, N., Silverman, JH y Whyte, W., Ataque de encuentro en el medio a una clave privada NTRU .
• J. Hoffstein, J. Silverman. Optimizaciones para NTRU . Criptografía de clave pública y teoría computacional de números (Varsovia, 11-15 de septiembre de 2000), DeGruyter, de próxima publicación.
• AC Atici, L. Batina, J. Fan e I. Verbauwhede. Implementaciones de bajo coste de NTRU para seguridad generalizada .

• Sitio web técnico de NTRU archivado el 2 de julio de 2018 en Wayback Machine.
• Página principal de IEEE P1363
• Security Innovation (adquirió NTRU Cryptosystems, Inc.)
• Implementación de NTRUEncrypt bajo licencia BSD de código abierto
• Licencia de código abierto GPL v2 de NTRUEncrypt
• strongSwan es una solución IPsec de código abierto que utiliza un intercambio de claves basado en NTRUEncrypt.
• - Biblioteca SSL/TLS integrada que ofrece conjuntos de cifrado que utilizan NTRU (wolfSSL)