Criptosistema McEliece - McEliece cryptosystem

En criptografía , el criptosistema de McEliece es un algoritmo de cifrado asimétrico desarrollado en 1978 por Robert McEliece . Fue el primer esquema de este tipo en utilizar la aleatorización en el proceso de cifrado. El algoritmo nunca ha ganado mucha aceptación en la comunidad criptográfica, pero es un candidato para la " criptografía post-cuántica ", ya que es inmune a los ataques que utilizan el algoritmo de Shor y, de forma más general, miden los estados de la clase lateral mediante muestreo de Fourier.

El algoritmo se basa en la dureza de decodificar un código lineal general (que se sabe que es NP-hard ). Para una descripción de la clave privada, se selecciona un código de corrección de errores para el que se conoce un algoritmo de decodificación eficiente y que es capaz de corregir errores. El algoritmo original utiliza códigos Goppa binarios (códigos de subcampo de códigos Goppa geométricos de una curva de género 0 sobre campos finitos de característica 2); estos códigos se pueden decodificar de manera eficiente, gracias a un algoritmo de Patterson. La clave pública se deriva de la clave privada al disfrazar el código seleccionado como un código lineal general. Para esto, la matriz generadora del código es perturbada por dos matrices invertibles seleccionadas al azar y (ver más abajo). ${\ Displaystyle t}$ ${\ Displaystyle G}$${\ Displaystyle S}$${\ Displaystyle P}$

Existen variantes de este criptosistema que utilizan diferentes tipos de códigos. La mayoría de ellos resultaron menos seguros; se rompieron por decodificación estructural .

McEliece con códigos Goppa se ha resistido hasta ahora al criptoanálisis. Los ataques más eficaces conocidos utilizan algoritmos de decodificación de conjuntos de información . Un artículo de 2008 describe tanto un ataque como una solución. Otro artículo muestra que para la computación cuántica , los tamaños de las claves deben incrementarse en un factor de cuatro debido a las mejoras en la decodificación del conjunto de información.

El criptosistema de McEliece tiene algunas ventajas sobre, por ejemplo, RSA . El cifrado y el descifrado son más rápidos. Durante mucho tiempo se pensó que McEliece no podía utilizarse para producir firmas . Sin embargo, se puede construir un esquema de firma basado en el esquema de Niederreiter , la variante dual del esquema de McEliece. Una de las principales desventajas de McEliece es que las claves pública y privada son matrices grandes. Para una selección estándar de parámetros, la clave pública tiene una longitud de 512 kilobits.

Definición de esquema

McEliece consta de tres algoritmos: un algoritmo de generación de claves probabilísticas que produce una clave pública y una privada, un algoritmo de cifrado probabilístico y un algoritmo de descifrado determinista.

Todos los usuarios de un recurso compartido de implementación McEliece un conjunto de parámetros de seguridad comunes: . ${\ Displaystyle n, k, t}$

Generación de claves

El principio es que Alice elige un código lineal de alguna familia de códigos para los que conoce un algoritmo de decodificación eficiente, y para que sea de conocimiento público, pero mantiene el algoritmo de decodificación en secreto. Tal algoritmo de decodificación requiere no solo conocer , en el sentido de conocer una matriz generadora arbitraria, sino que requiere que uno conozca los parámetros utilizados al especificar en la familia de códigos elegida. Por ejemplo, para los códigos binarios de Goppa, esta información sería el polinomio Goppa y los localizadores de códigos. Por lo tanto, Alice puede publicar públicamente una matriz generadora adecuadamente ofuscada . ${\ Displaystyle C}$${\ Displaystyle C}$${\ Displaystyle C}$${\ Displaystyle C}$${\ Displaystyle C}$

Más específicamente, los pasos son los siguientes:

1. Alice selecciona un código lineal binario capaz de corregir (eficientemente) errores de una gran familia de códigos, por ejemplo, códigos Goppa binarios. Esta elección debería dar lugar a un algoritmo de decodificación eficaz . Sea también cualquier matriz generadora de . Cualquier código lineal tiene muchas matrices generadoras, pero a menudo existe una opción natural para esta familia de códigos. Saber esto revelaría que debería mantenerse en secreto.${\ Displaystyle (n, k)}$${\ Displaystyle C}$${\ Displaystyle t}$${\ Displaystyle A}$${\ Displaystyle G}$${\ Displaystyle C}$${\ Displaystyle A}$
2. Alice selecciona una matriz binaria no singular aleatoria .${\ Displaystyle k \ times k}$ ${\ Displaystyle S}$
3. Alice selecciona una matriz de permutación aleatoria .${\ Displaystyle n \ times n}$ ${\ Displaystyle P}$
4. Alice calcula la matriz .${\ Displaystyle k \ times n}$${\ Displaystyle {\ hat {G}} = SGP}$
5. La clave pública de Alice es ; su clave privada es . Tenga en cuenta que podría codificarse y almacenarse como los parámetros utilizados para la selección .${\ Displaystyle ({\ hat {G}}, t)}$${\ Displaystyle (S, P, A)}$${\ Displaystyle A}$${\ Displaystyle C}$

Cifrado de mensajes

Supongamos que Bob desea enviar un mensaje m a Alice cuya clave pública es : ${\ Displaystyle ({\ hat {G}}, t)}$

1. Bob codifica el mensaje como una cadena binaria de longitud .${\ Displaystyle m}$${\ Displaystyle k}$
2. Bob calcula el vector .${\ Displaystyle c ^ {\ prime} = m {\ hat {G}}}$
3. Bob genera un vector de bits aleatorios que contiene exactamente unos (un vector de longitud y peso )${\ Displaystyle n}$${\ Displaystyle z}$${\ Displaystyle t}$${\ Displaystyle n}$${\ Displaystyle t}$
4. Bob calcula el texto cifrado como .${\ Displaystyle c = c ^ {\ prime} + z}$

Descifrado de mensajes

Al recibir , Alice realiza los siguientes pasos para descifrar el mensaje: ${\ Displaystyle c}$

1. Alice calcula el inverso de (es decir ).${\ Displaystyle P}$${\ Displaystyle P ^ {- 1}}$
2. Alice calcula .${\ Displaystyle {\ hat {c}} = cP ^ {- 1}}$
3. Alice usa el algoritmo de decodificación para decodificar .${\ Displaystyle A}$${\ Displaystyle {\ hat {c}}}$${\ Displaystyle {\ hat {m}}}$
4. Alice calcula .${\ Displaystyle m = {\ hat {m}} S ^ {- 1}}$

Prueba de descifrado del mensaje

Tenga en cuenta que , y que es una matriz de permutación, tiene peso . ${\ Displaystyle {\ hat {c}} = cP ^ {- 1} = m {\ hat {G}} P ^ {- 1} + zP ^ {- 1} = mSG + zP ^ {- 1}}$${\ Displaystyle P}$${\ Displaystyle zP ^ {- 1}}$${\ Displaystyle t}$

El código Goppa puede corregir hasta errores, y la palabra está a una distancia máxima de . Por lo tanto, se obtiene la palabra de código correcta . ${\ Displaystyle G}$${\ Displaystyle t}$${\ Displaystyle mSG}$${\ Displaystyle t}$${\ Displaystyle cP ^ {- 1}}$${\ Displaystyle {\ hat {m}} = mS}$

Multiplicar con el inverso de da , que es el mensaje de texto sin formato. ${\ Displaystyle S}$${\ Displaystyle m = {\ hat {m}} S ^ {- 1} = mSS ^ {- 1}}$

Tamaños de clave

McEliece sugirió originalmente tamaños de parámetros de seguridad de , lo que resulta en un tamaño de clave pública de 524 * (1024−524) = 262,000 bits. Un análisis reciente sugiere tamaños de parámetros de 80 bits de seguridad cuando se usa decodificación algebraica estándar, o cuando se usa decodificación de lista para el código Goppa, dando lugar a tamaños de clave pública de 520,047 y 460,647 bits respectivamente. Para la resiliencia frente a las computadoras cuánticas, se propusieron tamaños de con código Goppa, dando un tamaño de clave pública de 8,373,911 bits. En su presentación 3 y vuelta a la NIST normalización poste cuántica el más alto nivel de seguridad, nivel 5 se da para conjuntos de parámetros 6688128, 6960119, y 8192128. Los parámetros son , , respectivamente. ${\ Displaystyle n = 1024, k = 524, t = 50}$${\ Displaystyle n = 2048, k = 1751, t = 27}$${\ Displaystyle n = 1632, k = 1269, t = 34}$${\ Displaystyle n = 6960, k = 5413, t = 119}$${\ Displaystyle n = 6688, k = 128, t = 13}$${\ Displaystyle n = 6960, k = 119, t = 13}$${\ Displaystyle n = 8192, k = 128, t = 13}$

Ataques

Un ataque consiste en un adversario, que conoce la clave pública pero no la privada, deduciendo el texto sin formato de algún texto cifrado interceptado . Tales intentos deberían ser inviables. ${\ Displaystyle ({\ hat {G}}, t)}$${\ Displaystyle y \ in \ mathbb {F} _ {2} ^ {n}}$

Hay dos ramas principales de ataques para McEliece:

Ataques de fuerza bruta / no estructurados

El atacante sabe cuál es la matriz generadora de un código capaz de corregir errores de forma combinatoria . El atacante puede ignorar el hecho de que en realidad es la ofuscación de un código estructurado elegido de una familia específica y, en su lugar, utilizar un algoritmo para decodificar con cualquier código lineal. Existen varios de estos algoritmos, como pasar por cada palabra de código del código, decodificar el síndrome o decodificar el conjunto de información . ${\ Displaystyle {\ hat {G}}}$${\ Displaystyle (n, k)}$${\ Displaystyle {\ hat {C}}}$${\ Displaystyle t}$${\ Displaystyle {\ hat {C}}}$

Sin embargo, se sabe que la decodificación de un código lineal general es NP-hard , y todos los métodos mencionados anteriormente tienen un tiempo de ejecución exponencial.

En 2008, Bernstein, Lange y Peters describieron un ataque práctico al criptosistema original McEliece, utilizando el método de decodificación de conjuntos de información de Stern. Utilizando los parámetros originalmente sugeridos por McEliece, el ataque podría llevarse a cabo en 2 operaciones de ^60,55 bits. Dado que el ataque es vergonzosamente paralelo (no es necesaria la comunicación entre los nodos), se puede llevar a cabo en días en modestos clústeres de computadoras.

Ataques estructurales

En cambio, el atacante puede intentar recuperar la "estructura" de , recuperando así el algoritmo de decodificación eficiente u otro algoritmo de decodificación eficiente suficientemente fuerte. ${\ Displaystyle C}$${\ Displaystyle A}$

La familia de códigos de la que se elige determina completamente si esto es posible para el atacante. Se han propuesto muchas familias de códigos para McEliece, y la mayoría de ellas se han "roto" por completo en el sentido de que se han encontrado ataques que recuperan un algoritmo de decodificación eficiente, como los códigos Reed-Solomon . ${\ Displaystyle C}$

Los códigos Goppa binarios propuestos originalmente siguen siendo una de las pocas familias de códigos sugeridas que han resistido en gran medida los intentos de idear ataques estructurales.

Candidato post-cifrado cuántico

Se ingresó y seleccionó una variante de este algoritmo combinado con NTS-KEM durante la segunda ronda de la competencia de encriptación post-cuántica del NIST .

Referencias

enlaces externos

• Alfred J. Menezes; Scott A. Vanstone; AJ Menezes; Paul C. van Oorschot (1996). "Capítulo 8: Cifrado de clave pública" . Manual de criptografía aplicada . Prensa CRC. ISBN 978-0-8493-8523-0.

• "¿Computadoras cuánticas? Código de seguridad de Internet del futuro crackeado" . Science Daily . Universidad Tecnológica de Eindhoven . 1 de noviembre de 2008.

• "McEliece clásico" .(Envío al proyecto de estandarización de criptografía post-cuántica del NIST )