NTRUEncrypt ( abreviatura de Nth-degree TRUncated Polynomial Ring o Number Theorists aRe Us) es un sistema criptográfico de clave pública anteriormente llamado NTRU .
El criptosistema NTRUEncrypt, basado en un criptosistema de celosía , se creó como una alternativa a RSA y Elliptic Curve Cryptosystems (ECC) . La estabilidad del algoritmo está asegurada por la dificultad de encontrar el vector de red más corto , que es más resistente a los ataques que se realizan a las computadoras cuánticas . A diferencia de sus competidores RSA , ECC , Elgamal , el algoritmo utiliza operaciones sobre el anillo de polinomios truncados de grado no superior a :
Tal polinomio también se puede representar mediante un vector
Como cualquier algoritmo joven, NTRUEncrypt es poco conocido, aunque fue aprobado oficialmente para su uso en finanzas por el Comité de Normas Acreditadas X9 . [una]
Hay una implementación de código abierto de NTRUEncrypt . [2]
NTRUEncrypt, originalmente llamado NTRU, se inventó en 1996 y se presentó al mundo en las conferencias CRYPTO , Conferencia RSA , Eurocrypt . El motivo que sirvió como inicio del desarrollo del algoritmo en 1994 fue el artículo [3] , que hablaba de la facilidad de descifrar algoritmos existentes en computadoras cuánticas, lo cual, como ha demostrado el tiempo, no está lejos [4] . En el mismo año, los matemáticos Jeffrey Hoffstein, Jill Pipher y Joseph H. Silverman, quienes desarrollaron el sistema junto con el fundador de NTRU Cryptosystems, Inc. (más tarde rebautizado como SecurityInnovation), Daniel Lieman patentó su invención. [5]
NTRU opera en polinomios de grado como máximo
donde los coeficientes son enteros. Con respecto a las operaciones de suma y multiplicación módulo a polinomio , dichos polinomios forman un anillo R , llamado anillo de polinomios truncados , que es isomorfo al anillo del cociente
NTRU utiliza el anillo polinomial truncado R junto con el módulo de los números coprimos p y q para reducir los coeficientes de los polinomios.
El algoritmo también usa polinomios inversos en el anillo de polinomios truncados. Cabe señalar que no todo polinomio tiene un inverso, pero si existe un polinomio inverso, entonces es fácil calcularlo. [6] [7]
Se seleccionarán las siguientes opciones a modo de ejemplo:
Designaciones de parámetros | norte | q | pags |
---|---|---|---|
Valores paramétricos | once | 32 | 3 |
Para enviar un mensaje de Alice a Bob, se necesita una clave pública y privada. Tanto Bob como Alice conocen la clave pública, solo Bob conoce la clave privada, que utiliza para generar la clave pública. Para hacer esto, Bob elige dos polinomios "pequeños" f g de R . La "pequeñez" de los polinomios está implícita en el sentido de que es pequeña con respecto a un polinomio arbitrario módulo q : en un polinomio arbitrario los coeficientes deben estar distribuidos aproximadamente uniformemente módulo q , mientras que en un polinomio pequeño son mucho más pequeños que q . La pequeñez de los polinomios se determina usando los números df y dg :
La razón por la que los polinomios se eligen de esta manera es que f probablemente tendrá una inversa, pero g definitivamente no la tendrá ( g (1) = 0, y el elemento cero no tiene inversa).
Bob debe mantener estos polinomios en secreto. A continuación, Bob calcula los polinomios inversos y , es decir, tales que:
y .Si f no tiene un polinomio inverso, Bob elige otro polinomio f .
La clave secreta es un par y la clave pública h se calcula mediante la fórmula:
EjemploPor ejemplo, tomemos df =4 y dg =3. Entonces, como polinomios, uno puede elegir
A continuación, para el polinomio f , se buscan polinomios inversos módulo p =3 y q =32:
El paso final es calcular la clave pública h en sí misma :
Ahora que Alice tiene la clave pública, puede enviar el mensaje cifrado a Bob. Para hacer esto, necesita representar el mensaje como un polinomio m con coeficientes módulo p elegidos del rango (- p /2, p /2). Es decir, m es un polinomio "pequeño" módulo q . A continuación, Alice necesita elija otro polinomio "pequeño" r , que se llama "deslumbrante", definido por el número dr :
Utilizando estos polinomios, el mensaje cifrado se obtiene mediante la fórmula:
En este caso, cualquiera que conozca (o pueda calcular) el polinomio ciego r podrá leer el mensaje m .
EjemploSupongamos que Alicia quiere enviar un mensaje representado como un polinomio
y eligió un polinomio "cegador" para el cual dr = 3:
Entonces el texto cifrado e listo para ser enviado a Bob será:
Ahora, habiendo recibido el mensaje cifrado e , Bob puede descifrarlo utilizando su clave privada. Primero, obtiene un nuevo polinomio intermedio:
Si escribimos el texto cifrado, obtenemos la cadena:
y finalmente:
Después de que Bob haya calculado el polinomio a módulo q, debe elegir sus coeficientes del rango (- q /2, q /2] y luego calcular el polinomio b obtenido del polinomio a por reducción módulo p:
desde .
Ahora, usando la segunda mitad de la clave secreta y el polinomio b resultante , Bob puede descifrar el mensaje:
Es fácil ver eso
El polinomio resultante c es de hecho el mensaje original m .
Ejemplo : Bob recibió un mensaje cifrado e de Alice
Utilizando la clave secreta f , Bob obtiene un polinomio a
con coeficientes pertenecientes al intervalo (- q /2, q /2). A continuación, transforma el polinomio a en el polinomio b , reduciendo los coeficientes módulo p.
El paso final es multiplicar el polinomio b con la segunda mitad de la clave privada
Cuál es el mensaje original que estaba transmitiendo Alice.
El primero de los posibles ataques es el ataque de fuerza bruta . Aquí, son posibles varias variantes de enumeración: ya sea para clasificar todos y comprobar la pequeñez de los coeficientes de los resultados , que, según la idea, deberían haber sido pequeños, o para clasificar todos , comprobando también la pequeñez de los coeficientes. del resultado En la práctica, el espacio es más pequeño que el espacio , por lo que la durabilidad está determinada por el espacio . Y la persistencia de un mensaje individual está determinada por el espacio .
Hay una variante más óptima de reunión de enumeración en el medio propuesta por Andrew Odlyzhko . Este método reduce el número de opciones a la raíz cuadrada:
Seguridad de la clave privada = = ,
Y la perseverancia de un solo mensaje = = .
Un ataque de encuentro en el medio intercambia el tiempo necesario para el cálculo de la memoria necesaria para almacenar resultados temporales. Así, si queremos asegurar la estabilidad del sistema , debemos elegir un tamaño de clave .
Un ataque bastante serio en un solo mensaje, que puede evitarse siguiendo una regla simple: no envíe el mismo mensaje varias veces. La esencia del ataque es encontrar una parte de los coeficientes del polinomio cegador r . Y los coeficientes restantes simplemente se pueden ordenar, leyendo así el mensaje. Dado que el mismo mensaje cifrado con diferentes polinomios ciegos es , donde i=1, … n. Puedes evaluar una expresión que sea exactamente igual a . Para un número suficientemente grande de mensajes transmitidos (digamos, para n = 4, 5, 6), es posible recuperar, en base a la pequeñez de los coeficientes, la mayor parte del polinomio ciego .
Considere una red generada por las filas de una matriz de 2 N × 2 N con determinante , que consta de cuatro bloques de tamaño N × N :
Dado que la clave pública es , entonces , esta red contiene un vector de tamaño 2 N , que contiene primero los coeficientes del vector f , multiplicados por el coeficiente , luego los coeficientes del vector g . La tarea de encontrar dicho vector, para N grande y parámetros correctamente seleccionados, se considera difícil de resolver.
El ataque de texto cifrado elegido es el ataque más peligroso. Fue propuesto por Éliane Jaulmes y Antoine Joux [8] en 2000 en la conferencia CRYPTO. La esencia de este ataque es seleccionar un polinomio a(x) tal que . Al mismo tiempo, Eve no interactúa ni con Bob ni con Alice.
Si tomamos el texto cifrado , donde , obtenemos un polinomio . Como los coeficientes de los polinomios f y g toman los valores "0", "1" y "-1", entonces los coeficientes del polinomio a pertenecerán al conjunto {-2py, -py, 0, py, 2py}. Si se elige py tal que , entonces al reducir el módulo del polinomio a(x), solo se darán coeficientes iguales a -2py o 2py . Ahora que el i -ésimo coeficiente sea igual a 2py , entonces el polinomio a(x) después de la reducción del módulo se escribirá como:
,y el polinomio b(x) :
,finalmente calcula:
.Ahora, si consideramos todos los i posibles , entonces en lugar de individual , podemos componer un polinomio K y el mensaje descifrado tomará la forma:
,o, clave secreta:
,La probabilidad de encontrar componentes clave de esta manera es de aproximadamente 0,1 ... 0,3 para una clave de tamaño 100. Para claves grandes (~500), esta probabilidad es muy pequeña. Al aplicar este método una cantidad suficiente de veces, puede restaurar completamente la clave.
Para protegerse contra este tipo de ataques, se utiliza el método de cifrado avanzado NTRU-FORST . Para el cifrado, se utiliza un polinomio ciego , donde H es una función hash criptográficamente fuerte y R es un conjunto aleatorio de bits . Después de recibir el mensaje, Bob lo descifra. Luego, Bob cifra el mensaje recién descifrado de la misma manera que lo hizo Alice. Después de eso, lo compara con el recibido. Si los mensajes son idénticos, Bob acepta el mensaje; de lo contrario, lo rechaza.
A pesar de que existen algoritmos rápidos para encontrar el polinomio inverso, los desarrolladores propusieron para uso comercial como clave secreta f tomar:
,donde F es un polinomio pequeño. La llave así elegida tiene las siguientes ventajas:
Uno de los estudios archivado el 6 de octubre de 2016 en Wayback Machine mostró que NTRU es 4 órdenes de magnitud más rápido que RSA y 3 órdenes de magnitud más rápido que ECC .
Como se mencionó anteriormente, los desarrolladores, para garantizar la alta estabilidad del algoritmo, sugieren usar solo los parámetros recomendados que se indican en la tabla:
Designacion | norte | q | pags | d.f. | DG | dr. | Durabilidad garantizada |
---|---|---|---|---|---|---|---|
NTR167:3 | 167 | 128 | 3 | 61 | veinte | Dieciocho | Durabilidad moderada |
NTR251:3 | 251 | 128 | 3 | cincuenta | 24 | dieciséis | Nivel de resistencia estándar |
NTR503:3 | 503 | 256 | 3 | 216 | 72 | 55 | El más alto nivel de durabilidad. |
NTR167:2 | 167 | 127 | 2 | 45 | 35 | Dieciocho | Durabilidad moderada |
NTR251:2 | 251 | 127 | 2 | 35 | 35 | 22 | Nivel de resistencia estándar |
NTR503:2 | 503 | 253 | 2 | 155 | 100 | sesenta y cinco | El más alto nivel de durabilidad. |