Algoritmo de cifrado asimétrico desarrollado por Robert McEliece
En criptografía , el criptosistema McEliece es un algoritmo de cifrado asimétrico desarrollado en 1978 por Robert McEliece . [1] 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 manera más general, a la medición de estados de coset mediante muestreo de Fourier. [2]
El algoritmo se basa en la dificultad de decodificar un código lineal general (que se sabe que es NP-hard [3] ). Para una descripción de la clave privada, se selecciona un código corrector 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 binarios Goppa (códigos de subcampo de códigos de geometría algebraica de una curva de género 0 sobre campos finitos de característica 2); estos códigos pueden decodificarse eficientemente, gracias a un algoritmo debido a Patterson. [4] La clave pública se deriva de la clave privada disfrazando 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 aleatoriamente y (ver más abajo).
Existen variantes de este criptosistema que utilizan distintos tipos de códigos. La mayoría de ellos demostraron ser menos seguros, ya que se descifraron mediante descodificación estructural.
Hasta ahora, McEliece ha resistido el criptoanálisis con los códigos Goppa. Los ataques más efectivos conocidos utilizan algoritmos de decodificación de conjuntos de información . Un artículo de 2008 describe tanto un ataque como una solución. [5] Otro artículo muestra que para la computación cuántica , los tamaños de clave deben aumentarse por un factor de cuatro debido a las mejoras en la decodificación de conjuntos de información. [6]
El criptosistema McEliece tiene algunas ventajas sobre, por ejemplo, RSA . El cifrado y descifrado son más rápidos. [7] Durante mucho tiempo, se pensó que McEliece no podía usarse para producir firmas . Sin embargo, se puede construir un esquema de firma basado en el esquema Niederreiter , la variante dual del esquema McEliece. Una de las principales desventajas de McEliece es que las claves privada y pública son matrices grandes. Para una selección estándar de parámetros, la clave pública tiene una longitud de 512 kilobits.
Definición del esquema
McEliece consta de tres algoritmos: un algoritmo de generación de clave probabilística que produce una clave pública y una privada, un algoritmo de cifrado probabilístico y un algoritmo de descifrado determinista.
Todos los usuarios en una implementación de McEliece comparten un conjunto de parámetros de seguridad comunes: .
Generación de claves
El principio es que Alice elige un código lineal de alguna familia de códigos para los cuales conoce un algoritmo de decodificación eficiente y hace público el conocimiento pero mantiene en secreto el algoritmo de decodificación. 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 Goppa, esta información sería el polinomio de Goppa y los localizadores de código. Por lo tanto, Alice puede publicar una matriz generadora adecuadamente ofuscada de .
Más concretamente, los pasos son los siguientes:
- Alice selecciona un código binario-lineal capaz de corregir errores (de manera eficiente) de una gran familia de códigos, por ejemplo, los códigos binarios Goppa. Esta elección debería dar lugar a un algoritmo de decodificación eficiente . Sea también cualquier matriz generadora para . Cualquier código lineal tiene muchas matrices generadoras, pero a menudo hay una elección natural para esta familia de códigos. Saber esto revelaría, por lo que debería mantenerse en secreto.
- Alice selecciona una matriz binaria no singular aleatoria .
- Alice selecciona una matriz de permutación aleatoria .
- Alice calcula la matriz .
- La clave pública de Alice es ; su clave privada es . Tenga en cuenta que se pueden codificar y almacenar como parámetros utilizados para seleccionar .
Cifrado de mensajes
Supongamos que Bob desea enviar un mensaje m a Alice cuya clave pública es :
- Bob codifica el mensaje como una cadena binaria de longitud .
- Bob calcula el vector .
- Bob genera un vector de bits aleatorio que contiene exactamente unos (un vector de longitud y peso ) [1]
- Bob calcula el texto cifrado como .
Descifrado de mensajes
Al recibir , Alice realiza los siguientes pasos para descifrar el mensaje:
- Alice calcula la inversa de (es decir ).
- Alice calcula .
- Alice usa el algoritmo de decodificación para decodificar a .
- Alice calcula .
Prueba de descifrado de mensajes
Tenga en cuenta que , y que es una matriz de permutación, por lo tanto tiene peso .
El código Goppa puede corregir hasta errores y la palabra se encuentra a una distancia máxima de . Por lo tanto, se obtiene la palabra clave correcta .
Al multiplicar por el inverso de se obtiene , que es el mensaje de texto simple.
Tamaños de claves
Debido a que existe una elección libre en la matriz , es común expresar en "forma sistemática" de modo que las últimas columnas correspondan a la matriz identidad . Esto reduce el tamaño de la clave a . [8] [9] McEliece sugirió originalmente tamaños de parámetros de seguridad de , [1] lo que da como resultado un tamaño de clave pública de 524 × (1024 − 524) =262 000 bits . Un análisis reciente sugiere tamaños de parámetros de80 bits de seguridad cuando se utiliza la decodificación algebraica estándar, ocuando se utiliza la decodificación de lista para el código Goppa, lo que da lugar a tamaños de clave pública de520 047 y460 647 bits respectivamente. [5] Para la resiliencia frente a las computadoras cuánticas, se propusieron tamaños de con código Goppa, dando el tamaño de la clave pública de8 373 911 bits . [10] En su presentación de la ronda 3 a la estandarización post cuántica del NIST, se otorga el nivel más alto de seguridad, nivel 5, para los conjuntos de parámetros 6688128, 6960119 y 8192128. Los parámetros son , , respectivamente.
Ataques
Un ataque consiste en que un adversario, que conoce la clave pública pero no la privada, deduzca el texto simple a partir de un texto cifrado interceptado . Tales intentos deberían ser inviables.
Hay dos ramas principales de ataques para McEliece:
Ataques de fuerza bruta/no estructurados
El atacante conoce la matriz generadora de un código que es combinatoriamente capaz de corregir errores. El atacante puede ignorar el hecho de que es realmente la ofuscación de un código estructurado elegido de una familia específica y, en su lugar, simplemente utilizar un algoritmo para decodificar con cualquier código lineal. Existen varios algoritmos de este tipo, como el que recorre cada palabra del código, la decodificación de síndromes o la decodificación de conjuntos de información .
Sin embargo, se sabe que la decodificación de un código lineal general es NP-hard [ 3] , y todos los métodos mencionados anteriormente tienen un tiempo de ejecución exponencial.
En 2008, Bernstein, Lange y Peters [5] describieron un ataque práctico al criptosistema original de McEliece, utilizando el método de decodificación de conjuntos de información de Stern [11] .
Utilizando los parámetros sugeridos originalmente 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 nodos), puede llevarse a cabo en cuestión de días en grupos de ordenadores modestos.
Ataques estructurales
El atacante puede, en cambio, intentar recuperar la "estructura" de , recuperando así el algoritmo de decodificación eficiente u otro algoritmo de decodificación suficientemente fuerte y eficiente.
La familia de códigos de la que se elija determinará por completo si esto es posible para el atacante. Se han propuesto muchas familias de códigos para McEliece, y la mayoría de ellas han sido completamente "rotas" en el sentido de que se han encontrado ataques que recuperan un algoritmo de decodificación eficiente, como los códigos Reed-Solomon .
Los códigos binarios Goppa 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 a cifrado post-cuántico
Una variante de este algoritmo combinada con NTS-KEM [12] fue presentada y seleccionada durante la tercera ronda de la competencia de cifrado post-cuántico del NIST . [13]
Referencias
- ^ abc McEliece, Robert J. (1978). "Un criptosistema de clave pública basado en la teoría de codificación algebraica" (PDF) . Informe de progreso del DSN . 44 : 114–116. Código Bibliográfico :1978DSNPR..44..114M.
- ^ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). Criptosistemas McEliece y Niederreiter que resisten ataques de muestreo cuántico de Fourier . Avances en criptología—CRYPTO 2011. Apuntes de clase en informática. Vol. 6841. Heidelberg: Springer. págs. 761–779. doi : 10.1007/978-3-642-22792-9_43 . ISBN . 978-3-642-22791-2.Señor 2874885 .
- ^ ab Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk CA (1978). "Sobre la inherente intratabilidad de ciertos problemas de codificación". IEEE Transactions on Information Theory . IT-24 (3): 384–386. doi :10.1109/TIT.1978.1055873. MR 0495180.
- ^ NJ Patterson (1975). "La decodificación algebraica de los códigos Goppa". IEEE Transactions on Information Theory . IT-21 (2): 203–207. doi :10.1109/TIT.1975.1055350.
- ^ abc Bernstein, Daniel J.; Lange, Tanja ; Peters, Christiane (8 de agosto de 2008). "Ataque y defensa del criptosistema McEliece". Criptografía postcuántica. Apuntes de clase en informática. Vol. 5299. págs. 31–46. CiteSeerX 10.1.1.139.3548 . doi :10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.
- ^ Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF) . Criptografía postcuántica 2010. Notas de clase en informática. Vol. 6061. Berlín: Springer. págs. 73–80. doi :10.1007/978-3-642-12929-2_6. ISBN . 978-3-642-12928-5.Señor 2776312 .
- ^ "eBATS: ECRYPT Benchmarking de sistemas asimétricos". bench.cr.yp.to . 25 de agosto de 2018 . Consultado el 1 de mayo de 2020 .
- ^ Equipo McEliece Clásico (23 de octubre de 2022). "McEliece Clásico: criptografía conservadora basada en código: especificación del criptosistema" (PDF) . Resumen de la presentación al NIST de la ronda 4 .
- ^ Tanja Lange (23 de febrero de 2021). «Criptografía basada en códigos III - Códigos Goppa: definición y uso». YouTube .
- ^ Daniel Augot; et al. (7 de septiembre de 2015). "Recomendaciones iniciales de sistemas post-cuánticos seguros a largo plazo" (PDF) . PQCRYPTO: Criptografía post-cuántica para seguridad a largo plazo .
- ^ Jacques Stern (1989). "Un método para encontrar palabras clave de poco peso". Coding Theory and Applications . Lecture Notes in Computer Science. Vol. 388. Springer Verlag. págs. 106–113. doi :10.1007/BFb0019850. ISBN 978-3-540-51643-9.
- ^ "NTS-KEM". 29 de diciembre de 2017. Archivado desde el original el 29 de diciembre de 2017 . Consultado el 9 de diciembre de 2020 .
- ^ "Informe de situación sobre la tercera ronda del proceso de estandarización de la criptografía post-cuántica del NIST" (PDF) . NISTIR : 31.
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 . CRC Press. ISBN 978-0-8493-8523-0.
- Rahmschmid, Claudia; Adams, David (2023). McEliece Messaging: Smoke Crypto Chat: el primer McEliece-Messenger móvil publicado como prototipo estable en todo el mundo. Artículo de TK Info Portal.
- "¿Ordenadores cuánticos? Se ha descifrado el código de seguridad de Internet del futuro". Science Daily . Universidad Tecnológica de Eindhoven . 1 de noviembre de 2008.
- "McEliece clásico".(Presentación al Proyecto de estandarización de criptografía post-cuántica del NIST )