stringtranslate.com

Cifrado NTRU

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

Se basa en la presunta dificultad de factorizar ciertos polinomios en un anillo polinómico truncado en un cociente de dos polinomios que tienen coeficientes muy pequeños. Romper el criptosistema está fuertemente relacionado, aunque no es equivalente, al problema algorítmico de la reducción de retículos en ciertos retículos . Es necesaria una elección cuidadosa de los parámetros para frustrar algunos ataques publicados.

Dado que tanto el cifrado como el descifrado utilizan únicamente una simple multiplicación de polinomios, 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 una cantidad comparable de análisis criptográfico en forma implementada.

Un algoritmo relacionado es el algoritmo de firma digital NTRUSign .

Específicamente, las operaciones NTRU se basan en objetos en un anillo polinomial truncado con multiplicación por convolución y todos los polinomios en el anillo tienen coeficientes enteros y grado como máximo N -1:

En este anillo , el efecto que produce la multiplicación de un polinomio por rota los coeficientes del polinomio. Una función de la forma para un fijo produce un nuevo polinomio en el que cada coeficiente depende de tantos coeficientes de como coeficientes distintos de cero haya en .

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

Historia

El sistema de cifrado de clave pública NTRUEncrypt es un sistema de cifrado relativamente nuevo. La primera versión del sistema, que se llamó simplemente 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] (ahora vencida) sobre el sistema de cifrado.

Durante los últimos diez años se ha trabajado en mejorar el criptosistema. Desde la primera presentación del criptosistema, se han realizado algunos cambios para mejorar tanto el rendimiento del sistema como su seguridad. La mayoría de las mejoras de rendimiento se centraron en acelerar el proceso. [ más explicación necesaria ] Hasta 2005 se puede encontrar literatura que describe los fallos de descifrado de NTRUEncrypt. [ cita necesaria ] En cuanto a la seguridad, desde la primera versión de NTRUEncrypt, se han introducido nuevos parámetros [ cita necesaria ] que parecen seguros [ aclaración necesaria ] para todos los ataques [ especificar ] conocidos actualmente y un aumento razonable en la potencia de cálculo. [ aclaración necesaria ]

Actualmente, el sistema está plenamente aceptado en los estándares IEEE P1363 bajo las especificaciones para criptografía de clave pública basada en red ( IEEE P1363.1 ). Debido a la velocidad del sistema de criptografía de clave pública NTRUEncrypt (consulte http://bench.cr.yp.to para ver los resultados de evaluación comparativa) y su bajo uso de memoria (consulte a continuación) [ dudosodiscutir ] , se puede utilizar 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 la industria de servicios financieros. [2]

Generación de clave pública

Para enviar un mensaje secreto de Alice a Bob es necesario generar una clave pública y una privada. La clave pública es conocida tanto por Alice como por Bob, y la clave privada solo la conoce Bob. Para generar el par de claves se requieren dos polinomios f y g , con grado como máximo y con coeficientes en {-1,0,1}. Pueden considerarse como representaciones de las clases de residuos de polinomios módulo en R . El polinomio debe satisfacer el requisito adicional de que existan los inversos módulo q y módulo p (calculados utilizando el algoritmo euclidiano ), lo que significa que y deben cumplirse. Por lo tanto, cuando la f elegida no es invertible, Bob tiene que volver atrás y probar con otra f .

Tanto f como (y ) son la clave privada de Bob. La clave pública h se genera calculando la cantidad

Ejemplo : En este ejemplo los parámetros ( N , p , q ) tendrán los valores N = 11, p = 3 y q = 32 y por lo tanto los polinomios f y g son de grado 10 como máximo. Los parámetros del sistema ( N , p , q ) son conocidos por todos. Los polinomios se eligen aleatoriamente, por lo que supongamos que están representados por

Utilizando el algoritmo euclidiano se calcula la inversa de f módulo p y módulo q , respectivamente.

Que crea la clave pública h (conocida tanto por Alice como por Bob) calculando el producto

Encriptación

Alice, que quiere enviar un mensaje secreto a Bob, presenta su mensaje en forma de polinomio m con coeficientes en . En las aplicaciones modernas de cifrado, el polinomio del mensaje se puede traducir en una representación binaria o ternaria. Después de crear el polinomio del mensaje, Alice elige aleatoriamente un polinomio r con coeficientes pequeños (no restringido al conjunto {-1,0,1}), que está destinado a ocultar el mensaje.

Con la clave pública h de Bob se calcula el mensaje cifrado e :

Este texto cifrado oculta los mensajes de Alice y puede enviarse de forma segura a Bob.

Ejemplo : Supongamos que Alicia quiere enviar un mensaje que se puede escribir como polinomio.

y que el 'valor cegador' elegido aleatoriamente puede expresarse como

El texto cifrado que representa su mensaje cifrado a Bob se verá así

Descifrado

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

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

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 ya se encuentran dentro del intervalo [- q /2, q /2] porque los polinomios r , g , f y m y el primo p tienen todos coeficientes que son pequeños en comparación con q . Esto significa que todos los coeficientes se dejan sin cambios durante la reducción módulo q y que el mensaje original se puede recuperar correctamente.

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

porque .

Sabiendo b, Bob puede usar la otra parte de su clave privada para recuperar el mensaje de Alice mediante la multiplicación de b y

porque la propiedad era requerida para .

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

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 recupere correctamente.

Reduciendo los coeficientes de un mod p se obtiene

que es igual a .

En el último paso, el resultado se multiplica por la clave privada de Bob para terminar con el mensaje original m

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

Ataques

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 realizar 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 montar 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 . Si tiene coeficientes pequeños, podría ser la clave secreta f , y Eve puede probar 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 probar si tiene valores pequeños.

Es posible montar un ataque de encuentro en el medio que es más poderoso. Puede reducir el tiempo de búsqueda en una raíz cuadrada. El ataque se basa en la propiedad que .

Eva quiere encontrar y tal que contenga y tal que tengan la propiedad

Si f tiene d unos y N - d ceros, entonces Eve crea todos los posibles y en los que ambos tienen longitud (por ejemplo, cubre los coeficientes más bajos de f y los más altos) con d /2 unos. Luego calcula para todos y los ordena en contenedores en función de las primeras k coordenadas. Después de eso, calcula todos 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 sumas 1 a las primeras k coordenadas. Luego, verificas los contenedores que contienen tanto y como y ves si se cumple la propiedad .

El ataque de reducción de red 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 el ataque de reducción de red es el algoritmo Lenstra-Lenstra-Lovász . Debido a que la clave pública h contiene tanto f como g , se puede intentar obtenerlas de h . Sin embargo, es demasiado difícil encontrar la clave secreta cuando los parámetros de NTRUEncrypt se eligen lo suficientemente seguros. El ataque de reducción de red se vuelve más difícil si la dimensión de la red se hace más grande y el vector más corto se hace más largo.

El ataque de texto cifrado elegido también es un método que recupera la clave secreta f y, por lo tanto, da como resultado una ruptura total. En este ataque, Eve intenta obtener su propio mensaje del texto cifrado y, por lo tanto, intenta obtener la clave secreta. En este ataque, Eve no tiene ninguna interacción con Bob.

Cómo funciona :

Primero, Eva crea un texto cifrado tal que y Cuando Eva escribe los pasos para descifrar e (sin calcular realmente los valores ya que no conoce f) encuentra :

En el cual tal que

Ejemplo :

Entonces K se convierte en .

Al reducir los coeficientes de un módulo p, en realidad se reducen los coeficientes de . Después de la multiplicación por , Eve encuentra:

Como se eligió que c fuera un múltiplo de p , m se puede escribir como

Lo que significa que .

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 distintos 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.

Mejoras de seguridad y rendimiento

Si se utilizan los últimos parámetros sugeridos (ver a continuación), el sistema de cifrado de clave pública NTRUEncrypt es seguro frente a la mayoría de los ataques. Sin embargo, sigue habiendo una lucha entre el rendimiento y la 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 hacer algunos cambios en la clave secreta f . Primero, construya f tal que , en donde 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 , lo que significa que Bob no tiene que calcular realmente la inversa y que Bob no tiene que realizar el segundo paso de 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 de encontrar pero f sigue siendo difícil de recuperar. En este caso, f tiene coeficientes diferentes de -1, 0 o 1, debido a la multiplicación por p . Pero debido a que Bob multiplica por p para generar la clave pública h , y luego reduce el texto cifrado módulo p , esto no tendrá un efecto en el método de cifrado.

En segundo lugar, f se puede escribir como el producto de múltiples polinomios, de modo que los polinomios tengan muchos coeficientes cero. De esta manera, se deben realizar menos cálculos.

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

Tabla 1: Parámetros

Referencias

  1. ^ "Patente de EE. UU. 6081597: método y aparato de criptosistema de clave pública" – a través de Google Patents .
  2. ^ "NTRUEncrypt de Security Innovation adoptado como estándar X9 para la protección de datos" (nota de prensa). 11 de abril de 2011.
  3. ^ "NIST-PQ-Submission-NTRU-20201016.tar.gz".

Enlaces externos