En criptografía , el criptosistema de 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 forma más general, miden los estados de las clases laterales mediante el muestreo de Fourier. [2]
El algoritmo se basa en la dureza 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 de corrección de errores para el cual se conoce un algoritmo de decodificación eficiente y que es capaz de corregirerrores. 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. [4] La clave pública se deriva de la clave privada al disfrazar el código seleccionado como un código lineal general. Para ello, la matriz generadora del código es perturbado por dos matrices invertibles seleccionadas al azar y (vea abajo).
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. [5] 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. [6]
El criptosistema de McEliece tiene algunas ventajas sobre, por ejemplo, RSA . El cifrado y el descifrado son más rápidos. [7] 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 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 que conoce un algoritmo de decodificación eficiente, y para hacer de conocimiento público, pero mantenga en secreto el algoritmo de decodificación. Tal algoritmo de decodificación requiere no solo saber, en el sentido de conocer una matriz generadora arbitraria, pero 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 una matriz generadora adecuadamente ofuscada de en público.
Más específicamente, los pasos son los siguientes:
- Alice selecciona un binario -código lineal capaz de corregir (eficientemente) errores de una gran familia de códigos, por ejemplo, códigos binarios Goppa. Esta elección debería dar lugar a un algoritmo de decodificación eficiente.. Deja tambien ser cualquier matriz generadora para . Cualquier código lineal tiene muchas matrices generadoras, pero a menudo existe una opción natural para esta familia de códigos. Sabiendo que esto revelaría por lo que debe mantenerse en secreto.
- Alice selecciona al azar matriz binaria no singular .
- Alice selecciona al azar matriz de permutación .
- Alice calcula el matriz .
- La clave pública de Alice es ; su clave privada es. Tenga en cuenta que podrían codificarse y almacenarse como los parámetros utilizados para seleccionar .
Cifrado de mensajes
Suponga 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 aleatorio -bit vector conteniendo exactamente unos (un vector de longitud y el peso ) [1]
- Bob calcula el texto cifrado como .
Descifrado de mensajes
Al recibir , Alice realiza los siguientes pasos para descifrar el mensaje:
- Alice calcula el inverso de (es decir ).
- Alice calcula .
- Alice usa el algoritmo de decodificación decodificar a .
- Alice calcula .
Prueba de descifrado del mensaje
Tenga en cuenta que , y eso es una matriz de permutación, por lo tanto tiene peso .
El código Goppa puede corregir hasta errores, y la palabra está a la distancia como máximo de . Por lo tanto, la palabra de código correcta es obtenido.
Multiplicar con el inverso de da , que es el mensaje de texto sin formato.
Tamaños de clave
McEliece sugirió originalmente tamaños de parámetros de seguridad de , [1] resultando en un tamaño de clave pública de 524 * (1024−524) = 262,000 bits [ aclaración necesaria ] . Un análisis reciente sugiere tamaños de parámetros depara 80 bits de seguridad cuando se usa decodificación algebraica estándar, ocuando se usa la 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. [5] Para la resiliencia frente a las computadoras cuánticas, los tamaños decon código Goppa, dando un tamaño de clave pública de 8,373,911 bits. [8] En su presentación de la ronda 3 a la estandarización cuántica posterior del NIST, el nivel más alto de seguridad, el nivel 5 se da para los conjuntos de parámetros 6688128, 6960119 y 8192128. Los parámetros son, , respectivamente.
Ataques
Un ataque consiste en un adversario, que conoce la clave pública pero no la clave privada, deduciendo el texto sin formato de algún 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 sabe que es la matriz generadora de un código que es combinatoriamente capaz de corregir errores. El atacante puede ignorar el hecho de quees realmente la ofuscación de un código estructurado elegido de una familia específica y, en su lugar, solo usa 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 .
Sin embargo, se sabe que la decodificación de un código lineal general es NP-hard , [3] sin embargo, 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 McEliece original, utilizando el método de decodificación de conjuntos de información de Stern. [9] 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 suficientemente potente y eficaz.
La familia de códigos de la que se elige completamente determina 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 .
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 al cifrado post-cuántico
Una variante de este algoritmo combinado con NTS-KEM [10] se ingresó y se seleccionó durante la segunda ronda del Concurso NIST Post-Quantum Encryption [11]
Referencias
- ↑ a b c McEliece, Robert J. (1978). "Un criptosistema de clave pública basado en la teoría de codificación algebraica" (PDF) . Informe de progreso de 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 los ataques de muestreo cuántico de Fourier . Avances en criptología — CRYPTO 2011. Lecture Notes in Computer Science. 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 .
- ^ a b Berlekamp, Elwyn R .; McEliece, Robert J .; Van Tilborg, Henk CA (1978). "Sobre la intratabilidad inherente de ciertos problemas de codificación". Transacciones IEEE sobre teoría de la información . IT-24 (3): 384–386. doi : 10.1109 / TIT.1978.1055873 . Señor 0495180 .
- ^ NJ Patterson (1975). "La decodificación algebraica de códigos Goppa". Transacciones IEEE sobre teoría de la información . IT-21 (2): 203–207. doi : 10.1109 / TIT.1975.1055350 .
- ^ a b c Bernstein, Daniel J .; Lange, Tanja ; Peters, Christiane (8 de agosto de 2008). Atacar y defender el criptosistema McEliece . Proc. 2do Taller Internacional de Criptografía Post-Cuántica . Apuntes de conferencias en Ciencias de la Computación. 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 contra McEliece (PDF) . Criptografía post-cuántica 2010. Apuntes de clase en Ciencias de la Computación. 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 .
- ^ 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 en clave de poco peso . Teoría y aplicaciones de la codificación . Apuntes de conferencias en Ciencias de la Computación. 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 estado de la segunda ronda del proceso de estandarización de criptografía post-cuántica del NIST" (PDF) . NISTIR : 9.
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 )