Criptografía Post-cuántica: Implementación de McEliece y una nueva versión

Escuela de Ingeniería Informática Trabajo Fin de Grado Grado en Ingeniería Informática de Servicios y Aplicaciones Criptografía Post-cuántica: Implementación de McEliece y una nueva versión Autor: David Moreno Centeno Tutor: José Ignacio Farrán Martín II Agradecimientos A los dos tutores de ambos trabajos fin de grado, Diego Ruano y Jose Ignacio Farrán por todo el tiempo empleado a lo largo de este año para guiarme y ayudarme a realizar el proyecto, y a mis padres, que me han dado el apoyo y ánimos necesarios a lo largo de la realización de todo el documento y también durante toda la carrera. III IV V Resumen La seguridad empleada en prácticamente todas comunicaciones realizadas actualmente utiliza una criptografía de clave pública o híbrida mediante el uso de sistemas criptográficos como el RSA, Gamal o de curva elíptica entre otros. Dichos sistemas aunque son actualmente seguros, en cuanto seamos capaces de construir un ordenador cuántico, se conoce un algoritmo que permite romperlos en tiempo polinómico. Por ello, actualmente se están estudiando distintos criptosistemas que sean resistentes a ataques realizados por un ordenador cuántico. El presente documento se centra en el criptosistema de McEliece, el cual es uno de los criptosistemas resistente frente a estos ataques. En adicción se muestran los códigos Reed-Solomon, Goppa y de producto de matrices, que se pueden emplear, entre otros, para construir el criptosistema. Después vemos un posible ataque contra el criptosistema construido a partir de un código Reed-Solomon. Por último se muestra un método innovador que nos permite reducir notablemente el tamaño de las claves del criptosistema mediante el empleo de códigos de producto de matrices. Abstract The security used in almost all communications currently performed a public key cryptography or hybrid through the use of cryptographic systems such as RSA, Gamal or elliptical curve among others. These systems although they are currently safe, as soon as we are able to build a quantum computer, it is known an algorithm that can break them in polynomial time. For this reason, different cryptosystems that are resistant to attacks carried out by a quantum computer are currently being studied. This paper focuses on the McEliece cryptosystem, which is one of the cryptosystems resistant to these attacks. In addition, Reed-Solomon, Goppa and matrix product codes are shown, which can be used to build the cryptosystem. Afterwards, a possible attack against the cryptosystem built from a Reed-Solomon code is shown. Finally, it shows an innovative method that allows us to significantly reduce the size of the cryptosystem keys by using matrix product codes. VI Índice general 1. Introducción 1 1.1. Motivación.................................... 4 1.2. Objetivos..................................... 4 1.3. Organización de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Metodología de trabajo 9 2.1. Ciclo de vida del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2. Herramientas empleadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Planificación y estimación de costes . . . . . . . . . . . . . . . . . . . . . 13 2.3.1. Empleo de recursos de personal . . . . . . . . . . . . . . . . . . . 13 2.3.2. Estimación de costes del proyecto . . . . . . . . . . . . . . . . . . 14 3. SageMath 17 3.1. Introducción................................... 17 3.2. Códigoslineales................................. 19 3.3. CódigosRSyGRS................................ 31 3.4. Códigos punteados y recortados . . . . . . . . . . . . . . . . . . . . . . . 37 3.5. Códigoscíclicos................................. 41 4. Códigos de Goppa 49 4.1. Introducción................................... 49 4.2. Codificación................................... 53 4.3. Descodificación ................................. 55 4.3.1. Algoritmo de Patterson . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.2. Funciones auxiliares . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3.3. Función de descodificación . . . . . . . . . . . . . . . . . . . . . . 60 4.4. Otrasfunciones ................................. 63 5. Criptosistemas de McEliece 67 5.1. Introducción................................... 67 5.2. Descripción del criptosistema . . . . . . . . . . . . . . . . . . . . . . . . . 68 VII VIII ÍNDICE GENERAL 5.3. Cifrado...................................... 69 5.3.1. Procesodecifrado ........................... 69 5.3.2. Implementación en Sage . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4. Descifrado.................................... 73 5.4.1. Proceso de descifrado . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.4.2. Implementación en Sage . . . . . . . . . . . . . . . . . . . . . . . . 74 5.5. Otrasfunciones ................................. 78 5.6. Ventajas y desventajas del criptosistema . . . . . . . . . . . . . . . . . . . 79 5.7. Posiblesataques................................. 80 6. Ataque contra los códigos GRS 85 6.1. Introducción................................... 85 6.2. Ataque por filtración a códigos GRS . . . . . . . . . . . . . . . . . . . . . 88 6.2.1. Ataqueestándar ............................ 88 6.2.2. Ataque al criptosistema de McEliece . . . . . . . . . . . . . . . . . 92 7. Códigos de producto de matrices 101 7.1. Introducción...................................101 7.2. Codificación...................................106 7.3. Descodificación .................................107 7.3.1. Otrasfunciones.............................114 7.4. Nuevo criptosistema de McEliece . . . . . . . . . . . . . . . . . . . . . . . 117 7.4.1. Generacion de claves . . . . . . . . . . . . . . . . . . . . . . . . . . 118 7.4.2. Cifrado..................................119 7.4.3. Descifrado................................120 8. Pruebas del código implementado 127 8.1. Goppa ......................................128 8.2. Códigos de producto de matrices . . . . . . . . . . . . . . . . . . . . . . . 129 8.3. Criptosistema de McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.4. Ataqueporfiltración ..............................135 9. Conclusiones 137 9.1. Trabajofuturo..................................138 Bibliografía 141 A. Contenido del CD 145 B. Manual de usuario 149 B.1. Instalación de Sage y acceso a Jupyter . . . . . . . . . . . . . . . . . . . . 149 B.2. Manualdeusuario ...............................150 Capítulo 1 Introducción Cuando una persona desea transmitir un mensaje a una o varias personas a través de un canal de comunicación, debe tener en cuenta que existe la posibilidad de que una persona ajena a la comunicación intente obtener dicho mensaje. Para evitar este problema surge la criptografía, la cual se centra en el estudio de métodos que nos permiten convertir un mensaje de texto plano en una secuencia aleatoria de caracteres de un alfabeto para que dicho mensaje resulte ilegible para cualquier persona ajena a la comunicación que capte el mensaje. Para ello, se puede emplear tanto la codificación como el cifrado, los cuales se centran en que la información sea transmitida de forma confidencial. Se pueden distinguir dos tipos de codificaciones en función de la longitud que tienen sus palabras; si todas las palabras de un código tienen la misma longitud se denomina código en bloque y si no lo son se denomina código de longitud variable. Por tanto, aunque realizar la codificación o cifrado de un mensaje tiene como principal objetivo garantizar la seguridad de la comunicación establecida, también nos permite detectar y corregir cierta cantidad de errores que pueden surgir durante la transmisión del mensaje, si empleamos cierto tipo de códigos en bloque o comprimir la información si en su lugar empleamos códigos de longitud variable, donde para ello tenemos que codificar los caracteres que se emplean de forma mas frecuente con las palabras del código de menor longitud. Los primeros sistemas criptográficos, conocidos como clásicos o como cifrados de clave privada emplean una clave que debe conocer tanto el emisor como el receptor antes de comenzar la comunicación, ya que emplean dicha clave tanto para cifrar como para descifrar los distintos mensajes. Por ello, no eran suficientes para el intercambio de mensajes de forma segura mediante un canal inseguro ya que, dicha clave debe cambiarse cada cierto tiempo y para realizar esto de forma segura, es necesario reali- 1 8CAPÍTULO 1. INTRODUCCIÓN Capítulo 2 Metodología de trabajo En cualquier proyecto es necesario realizar una estructuración de todo el trabajo que se va a realizar. Existen distintas formas de realizar este trabajo, sin embargo nosotros hemos decidido emplear un desarrollo iterativo que nos permita ir validando el código que vamos desarrollando. Por tanto, comenzamos implementando las funciones mas importantes del proyecto que se emplearán en adicción por el resto de funciones que vayamos desarrollando en etapas posteriores. Además, es evidente que la metodología empleada debe ser secuencial ya que, por ejemplo no podemos realizar la construcción completa de los códigos de producto de matrices sin haber realizado la implementación de los códigos de Goppa y mucho menos sin haber comprendido ambos códigos de forma teórica. Hay que tener en cuenta que el empleo del método iterativo nos permite ademas identificar los aspectos mas importantes del proyecto a desarrollar, sin los cuales no podríamos comenzar a realizar otros aspectos de menor relevancia. También, nos permite identificar un conjunto de funciones que quizás en un principio no considerábamos de gran importancia y después vemos que presentan una mayor relevancia. 2.1. Ciclo de vida del proyecto Ahora mostramos las distintas etapas que hemos ido realizando a lo largo de todo el trabajo realizado: 1) En una primera etapa de prácticamente cualquier proyecto que se vaya a desarrollar es necesario realizar un estudio del estado del arte. Por tanto, se comienza por adquirir una serie de conocimientos teóricos acerca de los tipos de códigos que vamos a utilizar a lo largo del proyecto. Obviamente dicha adquisición debe ser secuencial ya que será necesario por ejemplo realizar un estudio en primer 9 10 CAPÍTULO 2. METODOLOGÍA DE TRABAJO lugar de los códigos y códigos lineales de forma general antes de comenzar a estudiar un tipo particular de código lineal. Una vez realizado dicho estudio, el cual se irá ampliando también a lo largo del resto de etapas en partes mas concretas, se procede a realizar una planificación de la estructura que a priori deseamos que tenga el presente documento. En adicción a todo este estudio teórico de los códigos, también se realiza un estudio básico del lenguaje de programación Python junto con un estudio mas detallado del lenguaje de programación SageMath, debido a que ninguno de los dos lenguajes se ha estudiado a lo largo de los cursos académicos de ambas carreras. Para finalizar la primera etapa, también es necesario adquirir algunos conocimientos que nos permitan redactar el documento empleando Latex, el cual nos facilitará la introducción de distintas expresiones matemáticas a lo largo del documento. 2) En una segunda etapa, tras adquirir un cierto manejo del lenguaje Sage, así como un conocimiento teórico elemental de todos los aspectos a tratar, vamos a centrarnos en realizar un estudio acerca de todos los códigos que ya se encuentran implementados en Sage, que además necesitaremos emplear a lo largo del proyecto que vamos a desarrollar. Esto nos permitirá obtener información acerca del tiempo necesario que tendremos que emplear para implementar las distintas funciones que usaremos en el proyecto y no se encuentran desarrolladas en Sage actualmente. También provocará una reducción del tiempo necesario para realizar las implementaciones al adquirir un mayor conocimiento de distintas clases y métodos ya desarrollados, evitando en ocasiones que generemos cierta cantidad de código o sentencias que ya se encuentran desarrolladas en Sage. Para finalizar la segunda etapa, se realiza la construcción en Sage de los códigos de Goppa binarios, para el cual se dispone de funciones para codificar, introducir errores y descodificar vectores entre otras. También se realiza la implementación del criptosistema de McEliece en Sage, de forma que dicha construcción solo se puede realizar empleando los códigos de Goppa binarios implementados. Una vez realizadas ambas construcciones realizamos una serie de ejemplos para validar su correcto funcionamiento. 3) Ahora en la tercera etapa profundizamos en el estudio teórico de los códigos de producto de matrices para poder realizar la implementación de dichos códigos en Sage. En esta etapa únicamente se construyen dichos códigos mediante el empleo de códigos ya desarrollados en Sage. La razón principal de esto, es que a diferencia de los códigos de Goppa que hemos implementado, el algoritmo de descodificación de los códigos ya implementados nos avisa mediante el empleo de un error en caso de que se intenten corregir una cantidad de errores superior a la capacidad correctora del código, lo cual facilita la implementación del algoritmo de descodificación de los códigos de producto de matrices. En adicción, solo 2.1. CICLO DE VIDA DEL PROYECTO 11 se permite la construcción de estos códigos mediante el empleo de una matriz Aque debe ser cuadrada. Para finalizar, se incrementan las implementaciones de los códigos de Goppa y del criptosistema de McEliece; de forma que ahora es posible aplicar la funciones de codificación, introducción de errores y descodificación de los códigos de Goppa en vectores sobre los que no se realiza una restricción del tamaño y también es posible realizar la codificación y descodificación en listas y cadenas de caracteres. En cuanto al criptosistema de McEliece, ahora también es posible realizar su construcción empleando cualquiera de los códigos que estaban implementados desde el principio en Sage. 4) En cuanto a la cuarta etapa continuamos aumentando el estudio teórico de los códigos de producto de matrices y también la implementación en Sage de estos códigos, permitiendo ahora realizar su construcción mediante el empleo de una matriz no necesariamente cuadrada y también utilizando códigos de Goppa para su generación. Por último, añadimos los códigos de producto de matrices como otra construcción alternativa que se puede realizar sobre el criptosistema de McEliece. 5) En la quinta etapa nos centramos en el estudio del ataque de filtración contra los códigos Reed-Solomon generalizados donde, en un comienzo realizamos la implementación en Sage del ataque estandar contra estos códigos y después realizamos las modificaciones pertinentes que nos permiten implementar dicho ataque contra criptosistemas de McEliece que empleen los códigos Reed-Solomon generalizados para su construcción. Para finalizar se realiza en esta última etapa una pequeña fase de investigación mediante la cual obtenemos como resultado un método innovador que permite modificar el criptosistema de McEliece paliando la principal desventaja que presenta este criptosistema, que es el gran tamaño que presentan las claves que emplea. Para ello, es necesario la construcción del criptosistema empleando códigos de producto de matrices. Por tanto, incrementamos la implementación de estos códigos añadiendo dos funciones donde una de ellas nos permite obtener las claves con tamaño reducido y la otra nos permite obtener las claves totales, a partir de las reducidas, necesarias para la construcción del criptosistema. También se incrementa el código generado del criptosistema de McEliece, de forma que permita generar el criptosistema empleando las matrices obtenidas mediante el empleo de las otras funciones. 6) Para finalizar, en esta etapa realizamos una serie de ejemplos mas complejos que nos permitan validar el correcto funcionamiento de todas las funciones y clases implementadas. También analizamos el tiempo que emplean todas las funciones generadas, modificando en algunos casos distintos algoritmos, para que su complejidad sea menor y por tanto la eficiencia de las funciones que los emplean mejore. 12 CAPÍTULO 2. METODOLOGÍA DE TRABAJO Durante la realización de todo el proyecto se han ido realizando reuniones con los dos tutores para mostrar los avances realizados, solventar dudas y problemas que iban surgiendo e ir mostrando los ejemplos que se iban realizando. En adicción, al finalizar cada una de las etapas que acabamos de explicar, se realizaba una reunión para dar el visto bueno a los avances teóricos y de implementación, junto con los resultados obtenidos hasta el momento. De esta forma, íbamos validando el trabajo realizado y por tanto, en la mayoría de ocasiones los problemas iban surgiendo en relación a temas que se iban tratando en las etapas siguientes. 2.2. Herramientas empleadas Para la realización de todo el proyecto, vamos a emplear únicamente dos tipos de herramientas: Jupyter Notebook el cual es un entorno de trabajo open source que permite la implementación de código en Python u otros lenguajes, entre los cuales se incluye Sage el cual es el lenguaje de programación que emplearemos para la construcción de todo el código que realicemos. En el capítulo 3 mostramos mas información acerca de Sage.Jupyter surge en 2014 como resultado de la evolución del proyecto IPython y aunque en un principio fue creado por un profesor de la Universidad de California, es un software completamente libre y por tanto presenta un gran soporte de mantenimiento. Todo el código que generamos, lo organizamos en hojas de trabajo que se almacenan como archivos en formato .ipynb dentro de una carpeta que elegimos previamente. Dicho entorno se ejecuta mediante el empleo de un navegador web y por tanto se puede considerar como un entorno multiplataforma. A partir de estos archivos, podemos ir modificando e incrementando el código fácilmente, además de poder enviar dicho código a cualquier persona por correo electrónico o cualquier otra forma de comunicación alternativa en el formato estándar .ipynb u en otros de los formatos mas empleados actualmente como por ejemplo Latex,HTML oPDF entre otros. El entorno TexMaker es un editor de texto que nos permite manejar distintas variantes del lenguaje Tex, entre ellas la variante Latex que emplearemos para la redacción del presente documento. Este editor es gratuito y fue desarrollado en 2003 por Pascal Brachet empleando para ello el lenguaje de programación C++. Actualmente se encuentra bajo la licencia pública general (GPL) e incluye soporte para mas de 18 idiomas, corrección ortográfica, visor incorporado en pdf interconectado con las líneas de código generadas entre otros aspectos. Para finalizar, destacamos que es necesario haber instalado previamente una distribución de Tex, como por ejemplo MikTex para su correcto funcionamiento, aunque di- 2.3. PLANIFICACIÓN Y ESTIMACIÓN DE COSTES 13 cha instalación se puede realizar dentro del propio instalador de TexMaker, por tanto esto no dificulta nada su instalación. 2.3. Planificación y estimación de costes 2.3.1. Empleo de recursos de personal Para la realización de todo el proyecto se dispone de un único trabajador que irá ejerciendo los distintos roles por los que debe pasar el proyecto. Vamos a distinguir tres posibles roles. En primer lugar se ejercerá como jefe de proyecto para realizar una planificación acerca de los distintos temas a tratar a lo largo de todo el proyecto, para lo cual será necesario un primer contacto con toda la teoría que se podría estudiar en el proyecto y después realizar una selección y descarte de distintas partes que vayamos considerando mas o menos importantes para el proyecto. Por último, para cada parte se asigna una estimación de las horas que se creen necesarias emplear para su desarrollo, aunque al tratarse de un modelo iterativo, dichas horas pueden variar según los distintos incrementos que se vayan realizando durante todo el proyecto. En segundo lugar se toma el rol de analista, el cual se centra en realizar un estudio detallado de las distintas partes elegidas por el jefe de proyecto para comenzar su desarrollo teórico, así como la construcción de toda la documentación necesaria para el proyecto, entre las que se encuentran explicar detalladamente todas las partes teóricas y también documentar todo el código que implementará el proyecto. Por tanto, es claro que a lo largo del proyecto se destinará una mayor cantidad de horas en el rol de analista frente a los otros dos roles. Por último, también se ejercerá el rol de programador, el cual se centra en realizar la implementación en Sage de los distintos programas del proyecto. Para este proyecto hay que destacar que el número de horas destinadas al rol de programador se ha reducido respecto si el proyecto hubiera sido desarrollado realmente por distintas personas ejerciendo un rol distinto, ya que los programas que hay que desarrollar necesitan de al menos un pequeño estudio previo de la teoría, lo cual sería realizado en principio por el analista. Por otro lado, el tiempo estimado empleado por el trabajador en el desarrollo del proyecto ha cambiado en función de los distintos meses. Para los meses de octubre y noviembre del año 2018 el tiempo estimado de empleo se encuentra en unas 5 −7 horas semanales. De igual forma, para los meses de enero, febrero, marzo y abril del año 2019 el tiempo también se encuentra en torno a unas 5 −7 horas semanales. Después la mitad del mes de junio y los meses de julio y agosto se incrementaron notablemente la cantidad de horas empleadas ascendiendo hasta unas 40 −45 horas 14 CAPÍTULO 2. METODOLOGÍA DE TRABAJO semanales. Por último, en el mes de septiembre se han empleado unas 60−65 horas semanales hasta realizar la entrega del proyecto, donde de nuevo se han incrementado el número de horas empleadas para poder realizar todas las tareas previstas dentro del plazo esperado, así como la revisión completa de todo el proyecto desarrollado. En resumen, haciendo un recuento por meses de la cantidad de horas empleadas, podemos ver en la tabla 2.1 que la estimación de horas utilizadas para la realización de todo el proyecto se encuentra entre 690 y 807 horas. Meses Horas/Semana Nº de semanas Horas Octubre-Noviembre 5 −7 10 50 −70 Enero-Abril 5 −7 16 80 −112 Junio-Agosto 40 −45 11 440 −495 Septiembre 60 −65 2 120 −130 Total 39 690 −807 Tabla 2.1: Estimación de horas. 2.3.2. Estimación de costes del proyecto Ahora vamos a realizar un presupuesto del proyecto desarrollado en función principalmente de la estimación de horas realizada, ya que en dicho presupuesto no tendremos en cuenta el hardware empleado para su realización ni tampoco otros costes relacionados con la ubicación y recursos energéticos empleados durante su desarrollo. En adicción, analizando el software empleado, no tendremos en cuenta el coste de la distribución de Microsoft Windows del portátil empleado y como únicamente se emplean los programas TexMaker y Jupyter para el empleo de Latex ySage respectivamente, como vimos en la sección 5.2, consideramos que el coste del software es nulo al ser ambos programas gratuitos. Por tanto, únicamente tendremos en cuenta el trabajo realizado por el único trabajador para realizar el presupuesto. Para ello, diferenciaremos entre los distintos roles que ejerce y para cada uno de ellos tenemos en cuenta el salario medio de cada rol. Según [31] el salario medio neto de un programador se encuentra en 1200€, el de un analista en 1400€y el de un jefe de proyecto en 1900€, luego el sueldo neto por hora es aproximadamente 7, 5€, 9€y 12€respectivamente. 2.3. PLANIFICACIÓN Y ESTIMACIÓN DE COSTES 15 Rol Horas Precio/Hora Precio Programador 130 −150 7,5 975 −1125 Analista 460 −527 9 4140 −4743 Jefe proyecto 100 −130 12 1200 −1560 690 −807 6315 −7428 Tabla 2.2: Presupuesto del proyecto. Teniendo en cuenta esto, obtenemos un presupuesto del proyecto cuyo precio total supone entre 6315€y 7428€según una estimación de las horas empleadas en cada rol que podemos observar en la tabla 2.2. 16 CAPÍTULO 2. METODOLOGÍA DE TRABAJO Capítulo 3 SageMath 3.1. Introducción Como hemos dicho en el capítulo 2, el trabajo que se desarrolla en el documento se apoya en el empleo de un lenguaje de programación basado en Python llamado Sagemath oSage. Dicho lenguaje de programación nos permite realizar fácilmente los distintos cálculos que necesitaremos utilizar para realizar los distintos ejemplos que se van presentando a lo largo del documento, para que la comprensión de las distintas partes teóricas sea mas sencilla. También, emplearemos Sage para realizar la construcción automática de las claves públicas y privadas del criptosistema de McEliece, donde podremos escoger entre una serie de códigos para realizar su construcción, los cuales diferenciamos entre los códigos que ya están implementados total o parcialmente, que son como veremos los códigos Reed-Solomon, Reed-Solomon generalizados y los códigos cíclicos, y los códigos que necesitamos construir desde cero, que son los códigos de Goppa y los códigos de producto de matrices. Además de esto, también emplearemos Sage para realizar un ataque al criptosistema de McEliece que emplea códigos Reed-Solomon o Reed-Solomon generalizados para su construcción. Para ello, recurrimos a una vulnerabilidad que presentan estos códigos, la cual nos permite recuperar los parámetros ocultos de los códigos Reed-Solomon o Reed-Solomon generalizados que se emplean para realizar la construcción del criptosistema de McEliece. Para realizar la implementación de dicho ataque será necesario emplear los códigos punteados y los códigos recortados, los cuales están ya implementados en Sage. La realización de todo lo mostrado es posible como ya hemos dicho, realizando una cantidad mínima de cálculos a mano, gracias al empleo de Sage al ser un software dotado de gran cantidad de paquetes matemáticos, que nos permiten abordar distintos aspectos matemáticos como son el álgebra o cálculo numérico teniendo en cuenta el cuerpo sobre el que se está trabajando, pudiendo emplear cuerpos finitos, los cuales son de gran utilidad en el desarrollo de las distintas partes que veremos de la teoría 17 24 CAPÍTULO 3. SAGEMATH Proposición 3.15. Dado un código lineal [n,k], C, la distancia mínima de C es igual a el peso mínimo de C. Sage también nos proporciona una función capaz de obtener la distancia mínima de un código Cdado, aunque dicha función se encuentra limitada por un algoritmo de GAP, de forma que solo es posible emplearla en códigos construidos sobre cuerpos finitos de menos de 256 elementos: In: C.minimum_distance() También, nos proporciona otra función que nos devuelve una lista de tamaño n, a= [a1,..., an], siendo nla longitud del código C, la cual indica mediante el entero que se encuentra en la posición aide la lista a, el número de palabras de peso ique tiene el código C: In: C.weight_distribution() Obviamente, el costo computacional de ambas funciones es muy elevado al tener que ir realizando operaciones sobre cada palabra que pertenece al código C, por ello, para códigos con parámetros fundamentales elevados, dichas funciones necesitarán emplear una gran cantidad de tiempo, aunque se empleen otros métodos que permitan obtener la distancia de una forma mas óptima, como vimos en [1, Corolario 2.18] del trabajo fin de grado de matemáticas. Por tanto no serán funciones útiles para códigos con grandes parámetros. Proposición 3.16. (cota de Singleton) Dado un código lineal [n,k], C, cuya mínima distancia es d, se cumple que d ≤n−k+1. Los códigos que satisfacen la igualdad en la cota de Singleton, es decir, que cumplen d=n−k+1, son conocidos como códigos de máxima distancia separable o MDS. A partir de los conceptos de distancia y peso mínimo de un código lineal definidos, podemos observar que estos son los que nos permiten detectar cierta cantidad de errores. Denotamos por eun vector, llamado vector de errores, con longitud igual a la longitud de las palabras del código que se esta empleando y con peso ω(e)<d, siendo dla distancia mínima de dicho código. Ya que si el error tiene peso ω(e)≥d, entonces una palabra del código, c, con dicho error, puede dar lugar a otra palabra del código, c0=c+e, lo que provoca en ocasiones que no nos percatemos del error producido. Por otro lado, una vez detectada una palabra con cierta cantidad de errores, debemos preguntarnos cuantos errores somos capaces de corregir. Para ello veamos ahora la capacidad correctora de dichos códigos: 3.2. CÓDIGOS LINEALES 25 Definición 3.17. Dado un código lineal, C, diremos que es corrector de terrores si para cualesquiera dos palabras del código, a,b∈Cy para cualesquiera dos vectores de errores, eye0con ω(e),ω(e0)≤t, tenemos que a+e6=b+e0. El siguiente teorema nos proporciona una forma mas sencilla de obtener la capacidad correctora del código: Teorema 3.18. Un código [n,k]es corrector de t errores ⇔t<d 2, siendo d la distancia mínima de dicho código. Definición 3.19. Dada una palabra cdel código Csobre el cuerpo Fqde parámetros [n,k], llamaremos descodificación de ca la obtención del vector m∈Fk qtal que su codificación según la definición 3.9 sea c. En Sage existen una serie de funciones relacionadas con la corrección de errores y la descodificación: Para realizar la corrección de errores de una palabra del código Ctenemos la función: In: C.decode_to_code(word, decoder_name=None, *args) donde el parámetro word hace referencia a la palabra sobre la que deseamos corregir los errores que contiene. Los parámetros decoder_name y∗args son ambos opcionales, para los cuales, el primero indica el nombre del descodificador que queremos usar y el segundo son el conjunto de parámetros que se desean pasar a dicho descodificador. Para realizar la corrección de errores de la palabra y ademas la descodificación se emplea: In: C.decode_to_message(word, decoder_name=None, *args) cuyos parámetros son idénticos a los de la función decode_to_code(). Hay que destacar que si en la descodificación realizada por dicha función tenemos que obtener un vector cuyas últimas coordenadas se corresponden con elementos nulos, la función nos devuelve el vector obtenido a partir de la eliminación de dichas últimas coordenadas nulas. Ademas tenemos una función que permite ver los distintos descodificadores disponibles para el código C: In: C.decoders_available() 26 CAPÍTULO 3. SAGEMATH Una función que nos proporciona un descodificador de los posibles para C: In: C.decoder(decoder_name, *args) donde debemos introducir dos parámetros, decoder_name donde indicamos el nombre de un descodificador de los todos los posibles para C, que queremos obtener y ∗args que hace referencia a los argumentos que queremos pasar al descodificador seleccionado. Por último, podemos añadir un nuevo descodificador para el código Cque hayamos implementado: In: C.add_decoder(name, decoder) donde el parámetro name indica el nombre con el que se reconocerá el descodificador y en el parámetro decoder debemos introducir el nombre de la función en la que hemos implementado nuestro descodificador. Si partimos ahora de un código lineal Cde parámetros [n,k], hemos visto que su matriz de control, H, tiene rango máximo, por tanto, puede coincidir con la matriz generatriz de otro código lineal C0, donde ambos códigos están definidos sobre Fq. Podemos observar que al tener Cdimension k, necesariamente C0tiene que tener dimension n−ky una matriz de control de C0coincidirá con una matriz generatriz de C,G, ya que por la definición 3.10 sabemos que GHt=0. Definición 3.20. Llamaremos código dual de un código lineal, C, y lo denotaremos por C⊥, al código C0. La función de Sage que nos permite obtener el código dual es: In: C.dual_code() Además de todas las funciones de Sage descritas, existen una gran variedad de ellas que no hemos comentado como por ejemplo C.base_f ield() que nos permite saber el cuerpo sobre el que se encuentra el código C,C.list() para conseguir un listado con todos los elementos que constituyen el código C,C.cardinality() para obtener la cantidad de elementos que componen C,C.dimension() para conocer la dimensión de C,C.is_subcode(C1)para saber si Ces un subcodigo de C1,C.length() para saber la longitud de CoC.syndrome(m)para obtener el síndrome del vector mpara el código C(ver [1, Definición 2.23] en el trabajo fin de grado de matemáticas), entre otros. Todas estas funciones, se pueden emplear en el resto de códigos que se encuentran ya implementados en Sage y que vamos a emplear, al ser todos ellos códigos lineales. 3.2. CÓDIGOS LINEALES 27 Ejemplo 3.1. Veamos un ejemplo sencillo en el que empleemos la mayoría de las funciones que hemos descrito. Para ello, vamos ha construir un código lineal, C, sobre el cuerpo F2con parámetros fundamentales n=6, k=3 e imponemos que la distancia mínima del código que obtengamos sea d=3 mediante un bucle while: In: seguir=True; while seguir: C=codes.random_linear_code(GF(2),6,3) if C.minimum_distance()==3: seguir=False C Out: [6, 3] linear code over GF(2) Obviamente si validamos la distancia del código, obtenemos que es 3: In: C.minimum_distance() Out: 3 De igual forma, podemos comprobar la dimensión, longitud o cuerpo que esta empleando el código C: In: C.dimension() Out: 3 In: C.length() Out: 6 In: C.base_field() Out: Finite Field of size 2 Como la dimensión es k=3 y el cuerpo empleado es F2sabemos que la cantidad de elementos del código es 23=8, lo cual también podemos obtener mediante la función de Sage descrita anteriormente: In: C.cardinality() Out: 8 Ahora obtenemos todos los elementos del código C: 28 CAPÍTULO 3. SAGEMATH In: C.list() Out: [(0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 1, 0), (1, 1, 1, 0, 0, 0), (0, 1, 1, 1, 1, 0), (1, 1, 0, 1, 0, 1), (0, 1, 0, 0, 1, 1), (0, 0, 1, 1, 0, 1), (1, 0, 1, 0, 1, 1)] A partir de una base de esos elementos podemos construir una matriz generatriz del código C, siendo las filas de la matriz generatriz los correspondientes elementos de la base. En lugar de realizar esto, empleamos la función de Sage que nos proporciona directamente una matriz generatriz: In: C.generator_matrix() Out: [1 0 0 1 1 0] [1 1 1 0 0 0] [1 1 0 1 0 1] Ahora obtenemos la matriz generatriz en forma estándar y la matriz Ade la definición 3.7: In: C.systematic_generator_matrix() Out: [1 0 0 1 1 0] [0 1 0 0 1 1] [0 0 1 1 0 1] In: C.redundancy_matrix() Out: [1 1 0] [0 1 1] [1 0 1] En cuanto a una matriz de control del código obtenemos: In: C.parity_check_matrix() Out: [1 0 1 0 1 1] [0 1 1 0 0 1] [0 0 0 1 1 1] 3.2. CÓDIGOS LINEALES 29 Por último, vamos a realizar la codificación de un vector my su posterior descodificación con y sin errores. Para ello en primer lugar, vamos a ver los codificadores disponibles para un código lineal: In: C.encoders_available() Out: [ ' GeneratorMatrix ' , ' Systematic ' ] Seleccionamos el codificador GeneratorMatrix y lo guardamos en una variable llamada codi f icador: In: codificador=C.encoder('GeneratorMatrix') codificador Out: Generator matrix-based encoder for [6, 3] linear code over GF(2) Seleccionamos un vector mde F2,m= (1,0,1): In: m=vector(GF(2),[1,0,1]) m Out: (1, 0, 1) y empleamos la variable codi f icador para realizar su codificación: In: c=codificador(m) c Out: (0, 1, 0, 0, 1, 1) Podemos comprobar fácilmente que obtenemos el mismo resultado si multiplicamos el mensaje mpor la matriz generatriz de C: In: c1=m*C.generator_matrix() c1 Out: (0, 1, 0, 0, 1, 1) Una vez realizada la codificación, vamos a realizar su descodificación, para ello primero vamos a ver los descodificadores disponibles para un código lineal: In: C.decoders_available() Out: [ ' InformationSet ' , ' NearestNeighbor ' , ' Syndrome ' ] 30 CAPÍTULO 3. SAGEMATH De los tres disponibles, vamos a emplear el descodificador del síndrome, el cual fue explicado en [1, Sección 2.2] del trabajo fin de grado de matemáticas: In: mm=C.decode_to_message(c, 'Syndrome',1) mm Out: (1, 0, 1) Ahora vamos a introducir un vector de error ede peso de Hamming 1 que podamos corregir, el cual añadimos al mensaje codificado, c: In: e=vector(GF(2),[0,0,0,0,0,1]) e Out: (0, 0, 0, 0, 0, 1) In: cc=c+e cc Out: (0, 1, 0, 0, 1, 0) y realizamos su corrección de errores para obtener la palabra del código y también para obtener el mensaje descodificado: In: mm=C.decode_to_code(cc, 'Syndrome',1) mm Out: (0, 1, 0, 0, 1, 1) In: mm=C.decode_to_message(cc, 'Syndrome',1) mm Out: (1, 0, 1) Para finalizar calculamos el código dual de C: In: C.dual_code() Out: [6, 3] linear code over GF(2) 3.3. CÓDIGOS RS Y GRS 31 3.3. Códigos Reed-Solomon y Reed-Solomon generalizados Los códigos Reed-Solomon y Reed-Solomon generalizados, también conocidos de forma abreviada como códigos RS y códigos GRS respectivamente, son un tipo de códigos creados por Irving S. Reed y Gustave Solomon en el año 1960. Dichos códigos pertenecen a la categoría Forward Error Correction (FEC). Estos códigos resultan ser muy útiles para la corrección de errores a ráfagas que afectan a bloques contiguos. Por ello se emplean en una gran diversidad de casos, por ejemplo, en la tecnología DSL y variantes como la ADSL y VDSL, en distintas unidades de almacenamiento como discos duros, CD, DVD, BlueRay y también en códigos de barras y radiodifusión digital actual como DVB y sus variantes. Definición 3.21. Un código Reed-Solomon es un código sobre un cuerpo finito Fq, con un vector a= (a1,..., an)∈Fn q, donde ai6=aj∀i6=j, y nes un número entero con 0<n≤q−1. Normalmente, se considera n=q−1 para tener la longitud máxima que puede alcanzar el código, y de esta forma sería un código cíclico. Sea Lk⊂Fq[x]el espacio vectorial formado por todos los polinomios de grado menor que k, donde kes un entero con 0 <k≤n. Es evidente que la dimensión de Lkes kdebido a que cualquier polinomio de grado menor que kse puede generar como combinación lineal de los elementos {1, x,..., xk−1}sobre el cuerpo Fq, y al ser dichos elementos linealmente independientes, forman una base de Lk. Entonces el código Reed-Solomon asociado al vector a, se denota por RSk(a), y esta formado por los vectores obtenidos al evaluar los polinomios de Lken las coordenadas del vector a, es decir, RSk(a) = {(f(a1),..., f(an)) |f∈Lk}. En Sage podemos realizar la construcción de los códigos Reed-Solomon fácilmente al estar ya implementados: In: codes.ReedSolomonCode(base_field, length, dimension, primitive_root=None) donde el parámetro base_f ield hace referencia al cuerpo finito sobre el que se quiere construir el código, length la longitud que queremos que posea el código y dimension la dimensión que deseamos que tenga el código. En cuanto al parámetro primitive_root, es opcional y en el debemos indicar un elemento primitivo del cuerpo sobre el que nos encontramos que queremos para el código que vamos a construir. Lo habitual es no emplear dicho parámetro y que Sage seleccione automáticamente un elemento primitivo. 32 CAPÍTULO 3. SAGEMATH Las principales características de los códigos Reed-Solomon son que son códigos lineales y además siempre son códigos MDS (máxima distancia separable). Veamos ahora la definición de los códigos Reed-Solomon generalizados, la cual es muy parecida a la de los Reed-Solomon: Definición 3.22. Un código Reed-Solomon generalizado es un código sobre un cuerpo finito Fq, con un vector b= (b1, ..., bn)∈Fn q, donde bi6=0∀iy con un vector a= (a1,..., an)∈Fn q, donde ai6=aj∀i6=j, y nes un número entero con 0 <n≤q−1. Considerando igual que para los códigos Reed-Solomon Lk⊂Fq, el espacio vectorial de dimensión kformado por todos los polinomios de grado menor que k, tenemos que el código Reed-Solomon asociado al vector ayb, denotado por GRSk(a,b)es: GRSk(a,b) = {(b1f(a1), ..., bnf(an)) |f∈Lk} Para la construcción de los códigos Reed-Solomon generalizados mediante Sage, también disponemos de una clase que nos facilita su construcción: In: codes.GeneralizedReedSolomonCode(self, evaluation_points, dimension, column_multipliers=None) donde tenemos dos parámetros obligatorios y uno opcional: para el parámetro evaluation_points debemos introducir una lista de elementos distintos del cuerpo que vamos a emplear que se corresponde con el vector ade la definición 3.22. El otro parámetro obligatorio es dimension donde debemos indicar la dimensión que deseamos que tenga el código que vamos a generar. Por último, tenemos el parámetro opcional column_multipliers, donde debemos introducir una lista de elementos no nulos del cuerpo que vamos a emplear, la cual se corresponde con el vector bde la definición 3.22. Si no se introduce dicho parámetro, se considera automáticamente que el vector bque vamos a emplear para la construcción del código tiene todas sus entradas con valor 1. En el caso en que no introduzcamos el parámetro opcional, podemos observar que el código de Reed-Solomon generalizado que vamos a construir coincide con el código Reed-Solomon. Por tanto, lo habitual es emplear dicho parámetro opcional para construir realmente códigos Reed-Solomon generalizados. Proposición 3.23. El código dual de GRSk(a,b)es GRSn−k(a,b0), donde b0= (b0 1, ..., b0 n)es un vector de Fn qcon b0 i6=0∀i=1, ..., n. Además, b0∈GRSn−1(a,b)⊥y se cumple que n ∑ i=1 b0 ibif(ai) = 0∀f∈Lk−1(3.1) 3.3. CÓDIGOS RS Y GRS 33 Corolario 3.24. El código dual de GRSk(a,b)es MDS. Proposición 3.25. Una matriz generatriz, G ∈Fk×n q, de un código Reed-Solomon generalizado es: G=     b1b2··· bn b1a1b2a2··· bnan . . .. . .. . . b1ak−1 1b2ak−1 2··· bnak−1 n      Corolario 3.26. Si el elemento b ∈Fn qes b = (1,...,1)entonces tenemos que GRSk(a,b) = RSk(a)como hemos mencionado anteriormente. Por tanto una matriz generatriz de un Reed- Solomon será igual que la matriz generatriz del Reed-Solomon generalizado, tomando en dicha matriz el valor de 1todas las coordenadas del vector b, es decir, bi=1∀i=1, ..., n. En cuanto a la matriz de control de los códigos Reed-Solomon y Reed-Solomon generalizados, al ser dichos códigos lineales, se obtiene según lo visto en la definición 3.10. Para la obtención tanto de la matriz generatriz como de la matriz de control de un código Reed-Solomon generalizado o Reed-Solomon mediante Sage, tenemos que emplear las mismas funciones que empleamos para su obtención en los códigos lineales en la sección 3.2: In: C.generator_matrix() In: C.parity_check_matrix() Para realizar la codificación de un mensaje m= (m1, ..., mk), de tamaño k, empleando un código Reed-Solomon generalizado GRSk(a,b), tenemos que obtener su polinomio: fm(x) = ∑k i=1mixi−1. Ahora, evaluando dicho polinomio sobre las coordenadas del vector ay multiplicando el resultado obtenido de cada evaluación por la coordenada correspondiente del vector bobtenemos su codificación: c= (b1fm(a1),..., bnfm(an)). Obviamente, podemos observar que esto coincide con realizar la codificación explicada en 3.3, para cualquier código lineal, realizando simplemente la multiplicación del mensaje por la matriz generatriz, es decir, c=mG. Si observamos en Sage los codificadores disponibles para un código Reed-Solomon o Reed-Solomon generalizado mediante la función encoders_available(), obtenemos como resultado los codificadores EvaluationPolynomial yEvaluationVector que se corresponden con las dos formas de codificar explicadas en el párrafo anterior. Ademas, seguimos teniendo el codificador Systematic que actúa de forma semejante al de los códigos lineales. 40 CAPÍTULO 3. SAGEMATH Si comparamos la matriz generatriz obtenida para el código lineal Ccon la matriz generatriz obtenida para el código punteado, vemos que son bastante diferentes en relación a lo que debemos obtener según la nota 3.28. Esto es debido a que esta en forma sistemática la matriz generatriz del código punteado en la primera posición como ya comentamos. Por ello, vamos a comprobar que se genera el mismo código con la matriz generatriz obtenida para el código punteado y la que tendríamos que obtener según la nota 3.28: In: G=matrix(GF(2),[[C.generator_matrix()[i,j] for jin range(1,7)] for iin range(3)]) G Out: [0 1 1 0 1 1] [0 0 0 0 1 1] [1 1 1 1 0 0] Para el cálculo de la matriz Gsimplemente quitamos la primera columna de la matriz generatriz del código lineal C. Ahora a partir de esta matriz construimos otro código lineal y obtenemos su matriz en forma estándar: In: Clineal=codes.LinearCode(G) Clineal.systematic_generator_matrix() Out: [1 0 0 1 0 0] [0 1 1 0 0 0] [0 0 0 0 1 1] Donde vemos que se corresponde con la matriz generatriz que tenemos del código punteado en la primera posición. Por último, vamos a calcular el código recortado en la quinta posición a partir del mismo código lineal C: In: Cshort=C.shortened([4]) Cshort Out: [6, 2] linear code over GF(2) donde su matriz generatriz es: In: C.systematic_generator_matrix() Out: [1 0 0 0 0 1 1] [0 1 0 0 1 1 1] [0 0 1 1 0 1 1] 3.5. CÓDIGOS CÍCLICOS 41 3.5. Códigos cíclicos Para finalizar el capítulo vamos a introducir el último de los códigos implementados en Sage que vamos a emplear en los siguientes capítulos, que son los códigos cíclicos. Definición 3.34. Sea Cun código lineal, diremos que Ces un código cíclico si y solo si para cualquier palabra del código c= (c1, ..., cn)∈Cse tiene que c0∈Cdonde c0= (cn,c1, ..., cn−1). La siguiente proposición puede considerarse como una definición alternativa de un código cíclico, donde se representan las palabras del código como polinomios en lugar de vectores, pero antes de mostrarla, vamos a introducir la definición de un concepto necesario para dicha proposición. Definición 3.35. Llamamos ideal de un anillo Aa un conjunto I⊆Ano vacio que verifica: Es un subgrupo aditivo de A, es decir, que Ies cerrado respecto a la operación suma, el elemento neutro pertenece a A, luego 0 ∈Iy es cerrado respecto a los inversos. ∀x∈Iy∀a∈Ase cumple que ax ∈I. Proposición 3.36. Dado Fq[x]/hxn−1i, consideramos el siguiente isomorfismo ϕ:Fn q−→ Fq[x]/hxn−1i (c1, ..., cn)7−→ c1+···+cnxn−1 Se tiene que C ⊂Fq[x]/hxn−1i∼ =Fn qes un código cíclico si y solo si C es un ideal de Fq[x]/hxn−1i. Para la versión actual de Sage, los códigos cíclicos están limitados, de forma que solo los códigos cíclicos que verifican que su longitud, n, y tamaño u orden del cuerpo finito empleado, q, son coprimos son los que se pueden implementar, es decir, los códigos cíclicos deben cumplir que mcd(q,n) = 1. A pesar de ello, muchos libros como por ejemplo [35] realizan dicha restricción para poder emplear algunas técnicas algebraicas. Dicha restricción también obliga a que el polinomio xn−1 tenga todos sus factores irreducibles distintos. Corolario 3.37. Dado un código cíclico C de longitud n, existe un polinomio mónico único, g(x)∈Fq[x], llamado polinomio generador de C, divisor de xn−1y tal que C =hg(x)i. 42 CAPÍTULO 3. SAGEMATH Corolario 3.38. Los elementos de un código cíclico C de longitud n pueden identificarse con los polinomios de grado menor que n y que sean múltiplos de g(x). Actualmente Sage proporciona tres formas para realizar la construcción de un código cíclico, todas ellas empleando siempre la clase: In: codes.CyclicCode(self, generator_pol=None, length=None, code=None, check=True, D=None, field=None, primitive_root=None) cuyos parámetros se emplean parcialmente para cada una de las formas empleadas para realizar su construcción: Proporcionando el polinomio generador y la longitud deseada para el código cíclico en los parámetros generator_pol ylength respectivamente. Mediante el empleo de un código lineal dado en el parámetro code, para el cual se calcula el polinomio generador para dicho código. Se puede emplear también el parámetro check si se desea comprobar si el código lineal dado es o no cíclico. Indicando la longitud deseada para el código cíclico, el cuerpo sobre el que queremos construirlo y un subconjunto de un conjunto para el código mediante los parámetros length,f ield yDrespectivamente. Por ello, necesitamos especificar el nombre de los argumentos, además del valor que les deseamos dar. Veamos los posibles parámetros que podemos introducir: El parámetro generator_pol es donde debemos indicar el polinomio generador que hemos definido en el corolario 3.37. length indica la longitud que deseamos que tenga el código cíclico. code introducimos un código lineal a partir del cual realizar la construcción del código cíclico. check indica mediante un valor booleano si queremos que compruebe si el código introducido para generar el código es cíclico o no, dicho parámetro no se suele emplear ya que en caso de que el código no sea cíclico obtenemos directamente un error. f ield, indicamos el cuerpo sobre el que queremos construir el código. Además tiene los parámetros Dyprimitive_root que permite realizar la construcción de los códigos de la tercera forma. Sin embargo, como no mostramos la teoría necesaria para realizar la construcción de los códigos cíclicos de esta forma, no explicamos dichos parámetros. 3.5. CÓDIGOS CÍCLICOS 43 Una vez generado el código cíclico de alguna de las formas posibles, podemos obtener el polinomio generador en Sage mediante el empleo de la función generator_polynomial(). Ahora veamos como obtener una matriz generatriz y de control de forma asequible para códigos cíclicos. Teorema 3.39. Dado un código cíclico C con parámetros fundamentales [n,k]y polinomio generador g(x) = g0+g1x+···+gn−kxn−k, tenemos que una matriz generatriz de C es: G=        g0g1g2g3··· gn−k0 0 ··· 0 0g0g1g2··· gn−k−1gn−k0··· 0 0 0 g0g1··· gn−k−2gn−k−1gn−k··· 0 . . .. . .. . .. . ..... . .. . ..... . .. . . 0000··· 0g0g1··· gn−k        En Sage podemos obtener dicha matriz generatriz, de igual forma que para el resto de códigos, mediante el empleo de la función generator_matrix(). Antes de mostrar una matriz de control para los códigos cíclicos, vamos a definir el polinomio de control de un código cíclico, el cual nos facilitará la obtención de una matriz de control. Definición 3.40. Dado un código cíclico Ccon parámetros fundamentales [n,k]y polinomio generador g(x)de grado n−k, llamamos polinomio de control de Cal polinomio h(x) = xn−1 g(x)=h0+h1x+···+hkxk Sage también cuenta con la función check_polynomial(), que nos proporciona el polinomio de control del código cíclico. Teorema 3.41. Dado un código cíclico C con parámetros fundamentales [n,k]y polinomio de control de grado k, h(x) = h0+h1x+···+hkxk, tenemos que una matriz de control de C es: H=        0 0 ··· 0hkhk−1··· h1h0 0 0 ··· hkhk−1hk−2··· h00 0 0 ··· hk−1hk−2hk−3··· 0 0 . . .. . .. . .. . .. . .. . .. . .. . .. . . hkhk−1··· h00 0 ··· 0 0        También, mediante la función parity_check_matrix() podemos obtener una matriz de control del código cíclico. 44 CAPÍTULO 3. SAGEMATH Por último, veamos los procesos de codificación y descodificación de un código cíclico. En cuanto al proceso de codificación de un código cíclico Ccon parámetros fundamentales [n,k]y polinomio generador g(x)existen dos posibles formas de realizarla: Al ser Cun código lineal, se puede realizar la codificación explicada en la sección 3.2, es decir, multiplicar el vector mque deseamos codificar por una matriz generatriz de C,G. Para los códigos cíclicos, también se puede realizar una codificación conocida como polinómica. Para ello, tenemos que identificar el mensaje mque queremos codificar con el polinomio m(x)de grado menor que kque le corresponde. Entonces para realizar su codificación solo tenemos que multiplicarlo por el polinomio generador g(x): g(x)a(x) = c(x)|c∈C donde chace referencia a la codificación de m. Veamos los codificadores disponibles en Sage para estos códigos: In: C.encoders_available() Out: [ ' Polynomial ' , ' Systematic ' , ' Vector ' ] Por tanto, vemos que tenemos tanto el codificador Vector como el Polynomial, los cuales se corresponden con los dos métodos que hemos explicado. En adicción también tenemos el codificador Systematic, que realiza la codificación de igual forma que el codificador Vector pero empleando la matriz generatriz en forma estándar. Una vez escogido el codificador, se emplea para realizar la codificación la función encode() que explicamos para los códigos lineales en la sección 3.2. En cuanto a la descodificación de los códigos cíclicos el proceso que se emplea habitualmente es el de síndrome-líder, explicado en [1, Sección 2.2] del trabajo fin de grado de matemáticas, el cual es por tanto válido para cualquier código lineal. A pesar de ello, también vimos que dicho método es poco eficiente en cuanto trabajamos con códigos lineales de elevada longitud y dimensión. Sin embargo, dicho inconveniente se ve reducido notablemente debido a la estructura cíclica, ya que si Ces un código cíclico, basta con realizar la corrección de los errores en una posición fija, la cual se suele tomar la última. Esto permite reducir el tamaño de la tabla que debemos almacenar con los lideres y síndromes en n, la causa es que tenemos que guardar únicamente los síndromes y lideres cuyos lideres tengan la ultima coordenada no nula. 3.5. CÓDIGOS CÍCLICOS 45 Por ejemplo, para [1, Ejemplo 2.4] del trabajo fin de grado de matemáticas únicamente tendríamos que almacenar el síndrome (1,1,1)junto con el líder (0,0,0,0,0,0, 1). De igual forma que para los codificadores, obtenemos todos los posibles descodificadores ya implementados en Sage: In: C.decoders_available() Out: [ ' InformationSet ' , ' NearestNeighbor ' , ' SurroundingBCH ' , ' Syndrome ' , ' UnderlyingGRS ' ] donde de los cinco posibles emplearemos el descodificador Syndrome, al ser el que hemos explicado. Entonces realizamos la descodificación empleando las funciones decode_to_code() ydecode_to_message() que también explicamos para los códigos lineales en la sección 3.2. Para terminar vamos a realizar un ejemplo para mostrar el empleo de todos los conceptos que hemos visto: Ejemplo 3.4. Vamos a realizar la construcción de un código cíclico Csobre F2, cuyos parámetros fundamentales sean [7,4]. Para ello, emplearemos la longitud deseada junto con el polinomio generador, g(x). Según vimos en el corolario 3.37, g(x)debe ser un divisor de x7−1. Por tanto, vamos a obtener los factores en que se descompone: In: F.<x>=PolynomialRing(GF(2)) p=F(x^7-1) In: p.factor() Out: (x + 1) * (x3 + x + 1) * (x3 + x2 + 1) Como queremos que la dimensión del código sea k=4, tenemos que escoger un polinomio generador de grado 3, por lo que son válidos tanto x3+x+1 como x3+ x2+1. Elegimos g(x) = x3+x2+1 y realizamos la construcción del código cíclico C: In: g=F(x**3+x**2+1) C=codes.CyclicCode(generator_pol =g, length = 7) C Out: [7, 4] Cyclic Code over GF(2) 46 CAPÍTULO 3. SAGEMATH Obtenemos la matriz generatriz: In: C.generator_matrix() Out: [1 0 1 1 0 0 0] [0 1 0 1 1 0 0] [0 0 1 0 1 1 0] [0 0 0 1 0 1 1] donde vemos que coincide con lo visto en el teorema 3.39. Ahora obtenemos el polinomio de control del código C: In: C.check_polynomial() Out: x4 + x3 + x2 + 1 el cual podemos observar que coincide con la multiplicación del resto de factores de x7−1 distintos al del polinomio g(x): In: F(x+1)*F(x^3+x+1) Out: x4 + x3 + x2 + 1 Calculamos la matriz de control del código C: In: C.parity_check_matrix() Out: [1 1 1 0 1 0 0] [0 1 1 1 0 1 0] [0 0 1 1 1 0 1] donde vemos que dicha matriz no coincide con la que obteníamos en el teorema 3.41, aunque es claro que también es una matriz de control ya que podemos observar que ambas están constituidas por las mismas filas pero ordenadas de distinta forma. Ahora vamos a realizar, la codificación del vector m= (1,0,0,1)empleando el codificador Polynomial, por tanto, primero identificamos el vector mcon el polinomio m(x) = x3+1: In: m=vector(GF(2),[1,0,0,1]) m Out: (1, 0, 0, 1) 3.5. CÓDIGOS CÍCLICOS 47 In: c=C.encode(F(x^3+1),'Polynomial') c Out: (1, 0, 1, 0, 0, 1, 1) Si identificamos ccon el polinomio c(x) = 1+x2+x5+x6podemos comprobar que la codificación coincide con realizar el producto de m(x)yg(x): In: c=F(x^3+1)*g c Out: x6 + x5 + x2 + 1 Calculamos la distancia mínima del código C,d: In: C.minimum_distance() Out: 3 Al ser d=3, obtenemos que el código Ces capaz de corregir t=1 errores. Por tan- to, introducimos un vector econ peso de Hamming 1 y lo añadimos a la codificación, c, realizada obteniendo el vector y: In: e=vector(GF(2),[0,0,0,1,0,0,0]) e Out: (0, 0, 0, 1, 0, 0, 0) In: y=c+e y Out: (1, 0, 1, 1, 0, 1, 1) Por último, realizamos la descodificación del vector y. Para ello, podemos corregir el error introducido y después realizar la descodificación sobre la palabra del código obtenida, sin errores, recuperando el mensaje m: In: cc=C.decode_to_code(y,'Syndrome') cc Out: (1, 0, 1, 0, 0, 1, 1) In: mm=C.decode_to_message(cc,'Syndrome') mm 48 CAPÍTULO 3. SAGEMATH Out: (1, 0, 0, 1) También podemos calcular simultáneamente tanto la corrección de errores como su descodificación para obtener directamente el mensaje mde partida: In: mm=C.decode_to_message(y,'Syndrome') mm Out: (1, 0, 0, 1) Capítulo 4 Códigos de Goppa 4.1. Introducción En 1970, V.D. Goppa creó unos códigos que actualmente tienen bastante interés en la criptografía, los cuales eran conocidos por muchos autores como códigos casi aleatorios aunque son normalmente llamados códigos de Goppa en su honor. Algunas de sus propiedades son que hay una gran cantidad de códigos de Goppa con parámetros fundamentales muy parecidos, que son difíciles de distinguir de otros códigos lineales aleatorios, se conocen algoritmos tanto de codificación como de descodificación para dichos códigos y son relativamente sencillos de construir. Es por ello que McEliece eligió los códigos de Goppa para introducir su criptosistema en 1978, el cual mostraremos en el capítulo 5. En este tema definiremos dichos códigos y un algoritmo de descodificación para ellos entre otras propiedades. Definición 4.1. Sea L= (α0, ..., αn−1)∈Fn qmcon αi6=αj∀i6=jyg(x)un polinomio de grado tcon coeficientes en Fqm, de forma que g(αi)6=0∀αi∈L. Llamaremos código de Goppa correspondiente a Lyg(x), denotado por Γ(L,g), al código corrector de errores formado por todos los vectores c= (c0, ..., cn−1)∈Fqque cumplen que: Rc(x) = n ∑ i=1 ci−1 x−αi−1≡0 mod g(x) Nota 4.2. Si el polinomio de Goppa, g(x), es irreducible entonces el código de Goppa Γ(L,g)se dice que es irreducible y se verifica de forma trivial que g(αi)6=0 ya que si αifuera una raíz de g(x), entonces g(x)sería reducible. Nota 4.3. Si g(x)yf(x)son polinomios de Goppa de cierto grado con coeficientes en Fqmde los códigos Γ(L,g)yΓ(L,f)respectivamente. Se verifica que si f(x)|g(x) 49 56 CAPÍTULO 4. CÓDIGOS DE GOPPA iterar=RR(len(mensajecodificado))/RR(self._n); if iterar.is_integer(): for iin range(iterar): indices =range(self._n); for jin range(cantidad): nn=indices.pop(randint(0,len(indices)-1)); mensajecodificado[i*self._n+nn]+= 1; return mensajecodificado; Podemos observar, que los dos parámetros que debe introducir el usuario se corresponden con mensajecodi f icado, que es el vector binario sobre el que queremos introducir los errores y cantidad donde indicamos la cantidad de errores que deseamos introducir por cada bloque de tamaño nsobre el vector binario. Para la corrección de los errores producidos, vamos a introducir los conceptos de síndrome y polinomio localizador y evaluador de errores para los códigos de Goppa. Definición 4.7. Llamamos síndrome del vector y= (y0,..., yn−1)para el código de Goppa Γ(L,g)y lo denotamos s(x)al valor: s(x) = n−1 ∑ i=0 yi x−αi (mod g(x)) = n−1 ∑ i=0 ei x−αi (mod g(x)) donde e= (e0, ..., en−1)hace referencia al vector de errores. En Sage, al final de la ejecución del constructor hemos guardado en una variable de tipo matriz llamada SyndromeC el conjunto de valores 1 x−αi (mod g(x)), para evitar realizar su cálculo cada vez que vayamos a obtener un síndrome distinto. Ademas, dicha variable es de tipo matriz en lugar de ser un vector para que cuando lo multipliquemos por un vector se realice automáticamente la suma de todos ellos. In: SyndromeC =matrix(PolRing,1,len(L)); for iin range(len(L)): SyndromeC[0,i] =(PolRing.gen()-L[i]).inverse_mod(g); Definición 4.8. Llamamos polinomios localizador y evaluador de errores, denotados respectivamente por L(x)yE(x)a los polinomios dados de la forma: L(x) = ∏ i|ei6=0 (x−αi),E(x) = ∑ i|ei6=0 ei∏ j|ej6=0,j6=i (x−αj) 4.3. DESCODIFICACIÓN 57 Nota 4.9. Como vamos a emplear solo los códigos de Goppa binarios, basta con calcular el polinomio localizador de errores, L(x), ya que una vez calculadas las posiciones en que se encuentra el error, como los únicos valores posibles son 0 y 1, simplemente habría que cambiar en dichas posiciones el valor que tenemos. Para la obtención del polinomio localizador de errores que nos permite corregir los errores producidos, vamos a explicar el algoritmo de Patterson, cuyo uso es exclusivo para códigos de Goppa binarios. 4.3.1. Algoritmo de Patterson Dado un código de Goppa binario, Γ(L,g), tenemos que g(x)es un polinomio con coeficientes en F2myL= (α0, ..., αn−1)∈Fn 2m. El algoritmo consiste primero en calcular el síndrome del vector yvisto en la definición 4.7 y a partir del síndrome, calculamos el polinomio localizador de errores L(x), para ello: 1) Tenemos que buscar el polinomio f(x)que cumpla que s(x)f(x)≡1 mod g(x). Si dicho polinomio es la identidad, es decir, f(x) = xtendríamos que L(x) = x y hemos terminado. Si esto no ocurre, seguimos realizando los pasos siguientes. 2) Calculamos el polinomio h(x)tal que h2(x)≡f(x) + xmod g(x). 3) Buscamos los polinomios a(x)yb(x)de grado mínimo que cumplan que h(x)b(x)≡a(x)mod g(x). 4) El polinomio localizador de errores será L(x) = a2(x) + xb2(x). Ahora, con el polinomio localizador de errores que hemos calculado procedemos a obtener las posiciones en que hay errores (i|ei6=0). Para ello, calculamos las raíces del polinomio L(x), las cuales, deben ser elementos del vector L. Entonces, las posiciones de errores se corresponden con las posiciones que ocupan en el vector Llos elementos que son raices del polinomio localizador de errores, L(x). Por tanto, una vez que conocemos el vector de errores e= (e0, ..., en−1), ya podemos obtener la palabra codificada sin errores: c=y−e=y+e. 4.3.2. Funciones auxiliares Para poder realizar todos los pasos del algoritmo en Sage, es necesario implementar un conjunto de funciones adicionales que permitan realizar cada paso mas fácilmente. 58 CAPÍTULO 4. CÓDIGOS DE GOPPA En el paso 2), es necesario calcular la raíz cuadrada de un polinomio con coeficientes en F2m[x], lo cual es difícil de obtener en la mayoría de casos. Sin embargo, podemos observar que todas las raíces que deseamos hallar, son elementos de la forma f(x) + x. Para este tipo de elementos, en el artículo [28] se muestra un método, el cual denotamos _dividir_polinomio(sel f ,p), que permite obtener dichas raíces fácilmente. In: def _dividir_polinomio(self,p): Phi =p.parent() p0 =Phi([sqrt(c) for cin p.list()[0::2]]); p1 =Phi([sqrt(c) for cin p.list()[1::2]]); return (p0,p1); Como podemos ver, dicho método consiste en dividir el polinomio, f(x) + xdel cual queremos calcular su raíz cuadrada, en los polinomios cuyos coeficientes son las raíces cuadradas de los coeficientes de los términos con exponente impar, f0(x)y par, f1(x). Al realizar esto, se verifica que f(x) + x=f0(x)2+x f1(x)2. Debido a esto tenemos que pf(x) + x=f0(x) + √x f1(x)ya que en cuerpos binarios sabemos que se verifica que a(x)2+b(x)2= (a(x) + b(x))2con a(x),b(x)∈ F2m[x]. Por tanto, si conseguimos calcular la raíz cuadrada de x, seremos capaces de calcular cualquier raíz cuadrada del tipo que necesitamos. Para su obtención, vamos a mostrar una técnica semejante a la explicada antes, ya que tenemos que aplicar también la función _dividir_polinomio(sel f ,p)ahora sobre el polinomio de Goppa g(x) obteniendo de igual forma g(x) = g0(x)2+xg1(x)2. A partir de ello, tenemos que √x=g0(x)g−1 1(x)ya que podemos ver que g(x)−g0(x)2=xg1(x)2y aplicando ahora modulo g(x)y obteniendo el polinomio inverso de g1(x)2tenemos que x≡g0(x)2g1(x)−2. Para el paso 3) en lugar de implementar una función del algoritmo de Euclides extendido como se indica en el artículo [28], vamos a implementar un método mas sutil explicado por Bernstein en el artículo [29], al permitir este método incorporar el elemento nulo de F2m, con lo que podemos alcanzar la máxima longitud que puede tener un código sobre un determinado cuerpo finito. Para la introducción del método, vamos a introducir dos definiciones dadas por Bernstein en el artículo [29] de dos conceptos necesarios. Definición 4.10. Llamamos norma de un polinomio f∈F2m[x], que denotamos |f|, al valor |f|=2degfsi f6=0 y |f|=0 si f=0. Definición 4.11. Llamamos longitud de un vector (a,b)∈F2m[x]2, que denotamos |(a,b)|, a la norma del polinomio a2+xb2, es decir, |(a,b)|=|a2+xb2|. 4.3. DESCODIFICACIÓN 59 Por tanto, definimos en Sage una función que calcule la longitud de dos polinomios dados a partir de la norma explicada en la definición 4.10. In: def _longitud_norma(self,a,b): X=self._g.parent().gen(); return 2**((a**2+X*b**2).degree()); El principal problema del paso 3) se encuentra en que los valores que tenemos que calcular los cuales cumplen la congruencia, deben tener grado mínimo. Sin embargo, este problema desaparece rápidamente mediante este método ya que únicamente existen un par de polinomios a,bque verifican la congruencia y su longitud es menor que 2t, siendo tla capacidad correctora del correspondiente código de Goppa binario. Esta propiedad también es probada por Bernstein en [29]. Por último, la técnica básica empleada por el método implementado es semejante a la del algoritmo de Euclides extendido, donde vamos reduciendo los polinomios mediante el empleo de la función quo_rem() ya implementada en Sage, la cual te devuelve tanto el cociente como el resto de una división dada. Para ello, tenemos que partir de los vectores (h(x),1)y(g(x),0), donde vemos que únicamente varía el polinomio h(x), por ello es el único parámetro que se debe introducir en la función _reduccion_base() implementada para realizar el método explicado. In: def _reduccion_base(self, s): g=self._g; t=g.degree(); a=[]; b=[]; a.append(0); b.append(0); (q,r) =g.quo_rem(s); (a[0],b[0]) =simplify((g -q*s, 0-q)) if self._longitud_norma(a[0],b[0]) > 2**t: a.append(0); b.append(0); (q,r) =s.quo_rem(a[0]); (a[1],b[1]) =(r, 1 - q*b[0]); else: return (a[0], b[0]); i= 1; while self._longitud_norma(a[i],b[i]) > 2**t: a.append(0); b.append(0); if a[i]==0: return (a[i-1],b[i-1]); 60 CAPÍTULO 4. CÓDIGOS DE GOPPA else: (q,r) =a[i-1].quo_rem(a[i]); (a[i+1],b[i+1]) =(r, b[i-1]-q*b[i]); i+=1; return (a[i],b[i]); Para que este método funcione correctamente es necesario que la cantidad de errores introducida en el vector sea mayor que 2 y por tanto que la capacidad correctora del código empleado sea de al menos 3. Esto no supone una limitación excesiva ya que los códigos considerados actualmente con buenos parámetros fundamentales tienen una capacidad correctora mucho mayor a 3. Además, cuando empleemos estos códigos en el criptosistema de McEliece que veremos en el capítulo 5, siempre se suele introducir la máxima cantidad de errores posibles para realizar el proceso de cifrado, por lo que tampoco supone ningún problema. 4.3.3. Función de descodificación Una vez introducidas las funciones necesarias, vamos a mostrar la parte esencial de la función implementada llamada descodi f icar(sel f,mensaje,ASCII,decodi f icarV). En dicha función tenemos 3 parámetros, donde mensaje hace referencia al vector binario codificado que tiene o no errores, y los parámetros ASCII ydecodi f icarV son ambos de tipo booleano, en los cuales debemos indicar respectivamente si queremos que se transforme el vector obtenido en caracteres o no, y si queremos que solo se realice la corrección de errores o también que se descodifique el mensaje. Tras indicar los parámetros de la función, en primer lugar se divide el vector en bloques de tamaño n, al ser este el tamaño correspondiente de las palabras del código que estamos empleando. Hacemos hincapié en que esta vez la división en bloques de tamaño ndebe ser exacta, ya que el vector debe estar formado por un conjunto de palabras del código, con o sin errores. Una vez realizamos dicha división, calculamos el síndrome de cada bloque, donde tenemos que diferenciar dos posibles casos. El primero es que el síndrome obtenido sea el elemento nulo, lo cual significa que dicho bloque es una palabra del código y por tanto no se han producido errores. Por otro lado, si este no es nulo entonces dicho bloque presenta errores, por lo que aplicamos los pasos del algoritmo de Patterson para corregirlos: In: if(sindrome<>0): pol_sindrome =sindrome[0,0]; (g0,g1)=self._dividir_polinomio(self._g); w=g0*g1.inverse_mod(self._g); T=pol_sindrome.inverse_mod(self._g) 4.3. DESCODIFICACIÓN 61 if T== self._g.parent().gen(): sigma=self._g.parent().gen(); else: (T0,T1)=self._dividir_polinomio(T+self._g.parent().gen()); R=(T0 +w*T1).mod(self._g); (a,b)=self._reduccion_base(R); sigma=a**2+self._g.parent().gen()*b**2; j=Integer(0); for ain self._L: if sigma(a)==0: trozomensaje[j]+= 1; j+=1; Para encontrar el polinomio fdel paso 1), tenemos que calcular el inverso del polinomio del síndrome, s(x), modulo g(x), para ello Sage cuenta con una función ya implementada para elementos de distintos tipos, entre ellos polinomios con coeficientes en un cuerpo finito, llamada inverse_mod(), empleada como podemos ver en la línea 5 del código mostrado. Para realizar el paso 2), hacemos uso de la función auxiliar privada _dividir_polinomio() vista en la sección 4.3.2, la cual empleamos para obtener la raíz cuadrada según el procedimiento explicado. Después llamamos a la función privada _reduccion_base() para obtener los polinomios aybque nos permiten calcular el polinomio localizador de errores. Por último, las 5 filas del final del código permiten obtener las raíces del polinomio localizador de errores, de forma que cuando obtengamos una raíz, cambiamos el valor de esa posición del bloque de mensaje, recuperando el bloque sin errores. Una vez que recuperamos todo el mensaje sin errores, procedemos a descodificarlo si el usuario lo ha indicado mediante el parámetro booleano decodi f icarV: In [ ]: if decodificarV==True: Gcuadrada=matrix(GF(2),self._k); while Gcuadrada.rank()<> self._k or Gcuadrada.ncols()<>self._k: columnas=[]; totalcolumnas=range(self._n); Gcuadrada=self._Gbin; for iin range(self._k): aleatorio=randint(0,len(totalcolumnas)-1); columnas.append(totalcolumnas.pop(aleatorio)); columnas.sort(); 62 CAPÍTULO 4. CÓDIGOS DE GOPPA Gcuadrada=transpose(matrix(GF(2),[self._Gbin.column(a) for ain columnas])); partemensaje=vector(GF(2),[trozomensaje[j] for jin columnas]); mensajedescifrado=partemensaje*Gcuadrada.inverse(); lista=lista+[a for ain mensajedescifrado]; Como podemos observar, para realizar la descodificación calculamos una matriz cuadrada, M, que sea no singular formada por kcolumnas de la matriz generatriz del código. Entonces, mediante la multiplicación del vector formado por las coordenadas del bloque de mensaje correspondientes con las columnas que forman la matriz M, y la inversa de la matriz Mnos permiten recuperar el mensaje descodificado. Para finalizar la ejecución de la función, si el usuario desea su conversión a caracteres ASCII, en caso de que haya indicado en adicción que se realizara la descodificación, se emplean las siguientes sentencias: In [ ]: if ASCII==True and decodificarV==True: h=RR(len(lista))/RR(8); i=0; continuar=True; ascii=''; while i<h.ceil() and continuar: if i<>(h.ceil()-1): caracterbin=lista[i*8:(i+1)*8]; if vector(GF(2),caracterbin)==0: continuar=False; else: ascii+=bin_to_ascii(caracterbin); else: if h.is_integer(): caracterbin=lista[i*8:(i+1)*8]; ascii+=bin_to_ascii(caracterbin); i+=1; return ascii; else: return vector(GF(2),lista); Tenemos que destacar que al realizar el proceso de descodificación, recuperamos el mensaje junto con los elementos nulos que hemos tenido que añadir en caso de que la longitud del mensaje no fuera un múltiplo de k, como vimos en la sección 4.2. Si hemos partido de un conjunto de caracteres ASCII, podemos identificar fácilmente la cantidad de elementos nulos que se han incorporado al mensaje, ya que la longitud del 4.4. OTRAS FUNCIONES 63 mensaje debe ser un múltiplo de 8 y además no existe ningún carácter ASCII que se identifique con el bloque formado por 8 elementos nulos. Por tanto, en cuanto tengamos un bloque de longitud 8 formado únicamente por elementos nulos o si llegamos al bloque final del mensaje y su longitud no es 8, paramos la conversión y por tanto, eliminamos exitosamente todos los elementos nulos introducidos. Sin embargo, en caso de que se realice la descodificación del mensaje y no su conversión a caracteres ASCII, no seremos capaces de identificar los elementos nulos introducidos, al no conocer el tamaño original del mensaje. Esto en realidad no supone ninguna limitación extra respecto a cualquiera de los códigos implementados en Sage que ya hemos visto en el capítulo 3, ya que para realizar la codificación en dichos códigos era necesario introducir un mensaje cuya longitud fuera la dimensión del código. 4.4. Otras funciones Ademas de las funciones que hemos explicado hasta el momento, también hemos implementado un conjunto de funciones que nos permiten obtener propiedades fundamentales del código creado: minimum_distance() es una función que devuelve la distancia mínima del código de Goppa. generator_matrix_nobin() es una función que nos proporciona la matriz generatriz formada por elementos de F2mdel código de Goppa binario creado. parity_check_matrix_nobin() es una función que nos proporciona la matriz de control formada por elementos de F2mdel código de Goppa binario creado. generator_matrix() es una función que nos proporciona la matriz generatriz formada por elementos de F2del código de Goppa binario creado. parity_check_matrix() es una función que nos proporciona la matriz de control formada por elementos de F2del código de Goppa binario creado. cuerpo_f inito() es una función que nos proporciona el cuerpo F2. polinomio_g() es una función que nos permite saber cual es el polinomio de Goppa empleado para la generación del código. dimension() es una función que nos proporciona la dimensión del código de Goppa generado a partir de la matriz generatriz formada por elementos de F2. length() es una función a partir de la cual obtenemos la longitud del código de Goppa. 64 CAPÍTULO 4. CÓDIGOS DE GOPPA base_f ield() es una función que nos devuelve el cuerpo F2msobre el que se ha construido el código de Goppa. is_Goppa() es una función que nos permite diferenciar un código de Goppa de otro código cualquiera, devolviendo en caso de que sea de Goppa el valor booleano True. Podemos observar que muchas de estas funciones se llaman de igual forma y devuelven el mismo resultado que funciones de otros códigos ya implementados en Sage vistos en el capítulo 3. Esto permite que se puedan emplear las mismas sentencias de código independientemente del código que estemos empleando, por ejemplo, cuando realicemos la implementación del criptosistema de McEliece con diferentes códigos en el capítulo 5. Para finalizar el capítulo, vamos a mostrar la construcción de un código de Goppa, así como la codificación y correspondiente descodificación, tras incorporar una cantidad de errores, de un mensaje formado por caracteres ASCII. Ejemplo 4.1. En este ejemplo, vamos a construir un código de Goppa sobre el cuerpo F24, con máxima longitud, es decir, n=16 y que sea capaz de corregir t=3 errores. Para ello, fijamos de antemano el polinomio de Goppa a g(x) = x3+a2x+a, siendo a un elemento primitivo de F24, el cual podemos ver también que es irreducible: In: K.<a>=GF(2); F.<a>=GF(2**4); PolRing=PolynomialRing(F,'x'); x=PolRing.gen(); polinomiogoppa=x^3+F.gen()^2*x+F.gen(); polinomiogoppa Out: x3 + a2*x + a In: polinomiogoppa.is_irreducible() Out: True Llamamos a la clase Goppa e introducimos los parámetros para realizar la construcción del código Goppa, que almacenamos en la variable codigo_goppa: In: codigo_goppa=Goppa(2**4,4,polinomiogoppa); Obtenemos directamente las matrices generatriz y de control del código de Goppa formadas por elementos de F2: 4.4. OTRAS FUNCIONES 65 In: G=codigo_goppa.generator_matrix() G Out: [1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 1] [0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1] [0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1] [0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1] In: H=codigo_goppa.parity_check_matrix() H Out: [1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1] [0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0] [0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0] [1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 1] [1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0] [0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0] [0 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0] [0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0] [0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0] [1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0] [0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0] [0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0] Como la matriz generatriz Gtiene cuatro filas es claro que la dimensión del código es k=4. A pesar de ello, podemos llamar a la función dimension() para comprobarlo: In: codigo_goppa.dimension() Out: 4 Ahora vamos a realizar la codificación de un mensaje formado por caracteres ASCII. Para que no sea muy extenso, codificaremos simplemente una palabra: In: codificado=codigo_goppa.codificar('Hola') codificado Out: (0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1) 72 CAPÍTULO 5. CRIPTOSISTEMAS DE MCELIECE base_K=[] while q>=dividir: (q,r) =q.quo_rem(dividir); base_K+=[r] if q<dividir: (q,r) =q.quo_rem(dividir); base_K+=[r] if(len(base_K)<mm): incrementar_ceros=mm-len(base_K) for jin range(incrementar_ceros): base_K+=[0] base_K.reverse() else: base_K.reverse() Ahora, en los casos en que el cuerpo empleado para la construcción del criptosistema, Fpm, no tengamos que m=1, es decir, que el cuerpo no se construye directamente a partir de un número primo, luego es una extensión, es necesario transformar el vector que tenemos actualmente sobre el cuerpo Fpa un vector sobre el cuerpo Fpmpara poder realizar el cifrado, ya que la matriz pública G0esta formada por elementos del cuerpo Fpm. Por tanto, es necesario ir realizando la transformación de un vector de longitud msobre el cuerpo Fpa su identificación de un elemento de Fpm. Si ocurre que la longitud del vector sobre Fpno es un múltiplo de m, añadimos la cantidad de elementos nulos necesarios para que lo sea, los cuales podremos identificar en el descifrado fácilmente. In: if iterar1.is_integer(): for iin range(iterar1): bb=vector(self.K.base_ring(),[a for ain vector_base_K[i*self.pp:(i+1)*self.pp]]) listacuerpoascen+=[self.K(bb)] else: for iin range(iterar1.ceil()): if i<>(iterar1.ceil()-1): bb=vector(self.K.base_ring(),[a for ain vector_base_K[i*self.pp:(i+1)*self.pp]]) listacuerpoascen+=[self.K(bb)] else: tamrest=len(vector_base_K)-i*self.pp numeroceros=self.pp-tamrest; listrest=list(vector_base_K[len(vector_base_K) 5.4. DESCIFRADO 73 -tamrest:len(vector_base_K)]); listrest+=[0for iin range(numeroceros)]; listrest=vector(self.K.base_ring(),listrest) listacuerpoascen+=[self.K(listrest)] vectorCC=vector(self.K,listacuerpoascen) Una vez realizado todo este proceso de conversión, para realizar ahora el cifrado simplemente tenemos que aplicar el proceso que hemos explicado en la sección 5.3.1, del cual ya hemos mostrado su implementación al comienzo de esta sección. Para ello, tenemos que ir dividiendo nuestro vector total en vectores de longitud k. De igual forma, si la longitud del vector total no es múltiplo de k, añadimos la cantidad de elementos nulos necesarios para que lo sea. Si la cadena de caracteres ASCII se ha leído desde un fichero de texto, el correspondiente cifrado de dicha cadena de caracteres se almacena en un nuevo fichero creado, cuyo nombre se obtiene de la concatenación del nombre del fichero de texto que ciframos y la cadena de caracteres ” −ci f ”. 5.4. Descifrado 5.4.1. Proceso de descifrado Para realizar el descifrado del mensaje c0= (c0 1, ..., c0 n)recibido, podemos observar que como tenemos c0=c+e=mG0+e, entonces si multiplicamos dicho vector por la matriz inversa de la matriz de permutación, P−1obtenemos: c∗=c0P−1= mSG +eP−1. Siempre es posible realizar el paso anterior ya que toda matriz de permutación es invertible. Ahora podemos emplear el algoritmo eficiente de descodificación de terrores, ϑ, para obtener mSG. El algoritmo se puede emplear ya que la matriz SG es también una matriz generatriz del código de Goppa y tanto el vector ecomo el vector eP−1tienen el mismo peso. Después, obtenemos mS resolviendo el sistema de ecuaciones correspondiente a realizar la descodificación de los códigos de Goppa, ya que mS se corresponde con otro posible mensaje. Por último, obtenemos el bloque descifrado ma partir de la inversa de la matriz S: m=mSS−1. 74 CAPÍTULO 5. CRIPTOSISTEMAS DE MCELIECE 5.4.2. Implementación en Sage Hemos construido una función llamada desci f rado(sel f ,mensaje,ASCII = True,f ichero =False)también dentro de la clase McEliece para poder realizar el descifrado de las formas implementadas en la sección 5.3.2. Para ello, en dicha función, si el parámetro opcional f ichero es False, cuyo valor viene dado por defecto, debemos introducir en el parámetro mensaje el vector cifrado que queremos descifrar. En el parámetro booleano ASCII, el cual también es opcional, de forma que si no se indica ningún valor para este se asignará automáticamente el valor True, debemos indicar si deseamos transformar el mensaje descifrado a la cadena de caracteres correspondiente. Por tanto, si queremos descifrar un mensaje y no queremos convertirlo a caracteres ASCII, debemos indicar en la variable ASCII el valor False. En caso contrario, debemos indicar el valor True o no indicar ningún valor. De igual forma, si queremos leer un fichero de texto que contiene el mensaje cifrado que queremos descifrar, tenemos que indicar en el parámetro f ichero el valor True y en el parámetro mensaje el nombre del fichero. Entonces se guarda el vector almacenado en el fichero y se realiza su descifrado, donde dependiendo del parámetro ASCII se recupera una cadena de caracteres o el vector descifrado, que se almacena en otro fichero nuevo cuyo nombre se obtiene de concatenar del nombre del fichero de texto que desciframos y la cadena de caracteres ” −des”. Dicha función, divide el vector cifrado en bloques de tamaño n, donde en este caso si debe ocurrir que el tamaño del vector total sea un múltiplo de n, ya que se supone que esta formado por un conjunto de vectores cifrados de longitud n. Después, tenemos que realizar el proceso explicado en la sección 5.4.1, para lo cual, distinguimos entre si el código empleado por el criptosistema de McEliece es de Goppa, en cuyo caso tenemos que emplear el algoritmo de descodificación de Patterson que ya implementamos en la sección 4.3.3, si es un código de producto de matrices, donde empleamos un algoritmo de descodificación que explicaremos e implementaremos en la sección 7.3 y si es cualquier otro código lineal que hemos visto en el capítulo 3, donde emplearemos como algoritmo de descodificación la función decode_to_message() ya implementada en Sage. Hay que destacar como vimos en la sección 3.2, que si en la descodificación realizada por dicha función tenemos que obtener un vector cuyas últimas coordenadas se corresponden con elementos nulos, la función nos devuelve el vector obtenido a partir de la eliminación de dichas últimas coordenadas nulas. Por tanto, en estos casos es necesario la introducción de nuevo de dichas coordenadas nulas para obtener un descifrado total del mensaje correcto: In: for iin range(iterar): trozomensaje=vector( self.K ,[a for ain 5.4. DESCIFRADO 75 mensaje[i*filas:(i+1)*filas]*self.P.inverse()]); if not self.is_Goppa: if trozomensaje==0: trozomensaje1=vector( self.K ,[0for iin range(self.S.nrows())]); else: if self.is_MPC: trozomensaje1=vector( self.K ,[a for ain self.codigo.decodificar_MPC(trozomensaje,True)]); else: trozomensaje1=vector( self.K ,[a for ain self.codigo.decode_to_message(trozomensaje)]); if len(trozomensaje1)<>self.S.nrows(): listatrozo=list(trozomensaje1); cantidad_ceros=self.S.nrows()-len(listatrozo); for kin range(cantidad_ceros): listatrozo+=[0] trozomensaje1=vector( self.K ,listatrozo); trozomensaje =vector( self.K ,[a for ain trozomensaje1 *self.S.inverse()]); lista += [a for ain trozomensaje]; if self.is_Goppa: vec=vector(self.K.base_ring(),lista); vec=self.codigo.decodificar(vec,False,True); men=[]; filas=self.S.nrows(); iterar1=RR(len(vec))/RR(filas); for iin range(iterar1.floor()): trozovec =vec[i*filas : (i+1)*filas]*self.S.inverse(); men+=[a for ain trozovec]; men=vector(self.K,men) else: vec=[] men=vector(self.K,lista); Una vez realizado el proceso anterior, ya hemos descifrado el mensaje, por tanto, si el parámetro booleano ASCII es False devolvemos el resultado obtenido. Sin embargo, si el parámetro ASCII tiene como valor True es necesario realizar el proceso contrario al implementado en la sección 5.3.2, es decir, convertir el mensaje descifrado, que se puede encontrar en el caso mas complejo en el cuerpo Fpm, al vector correspondiente sobre el cuerpo F2, para poder realizar su posterior conversión a los caracteres ASCII 76 CAPÍTULO 5. CRIPTOSISTEMAS DE MCELIECE correspondientes. Para realizar este proceso, en primer lugar tenemos que comprobar si el código empleado por el criptosistema no es de Goppa y que no se esta empleando un cuerpo construido directamente sobre un número primo, es decir, si estamos empleando un código construido sobre Fpm. En caso afirmativo, tenemos que convertir cada elemento Fpmdel vector descifrado en un vector de tamaño mrealizando un descenso del cuerpo. Para ello, recurrimos de nuevo a la clase implementada por Sage llamada embedding() dentro de un tipo de códigos implementados denotados como codes.SubfieldSubcode(). Dicha clase nos permite obtener la conversión que buscamos de un elemento de Fpmal correspondiente vector formado por elementos de Fpempleando la función relative_f ield_representation(): In: if self.pp<>1 and not self.is_Goppa: C=codes.random_linear_code(self.codigo.base_field() ,self.matriz_publica.ncols(),self.matriz_publica.ncols()-1) Csubfield=codes.SubfieldSubcode(C, C.base_field().base_ring()) E=Csubfield.embedding() menSF=[] for iin range(len(men)): elemento=E.relative_field_representation(men[i]) menSF+=[a for ain elemento] menSF=vector(self.codigo.base_field().base_ring(),menSF) else: menSF=men Ahora ya tenemos el vector descifrado sobre el cuerpo Fp, por tanto, tenemos que realizar su conversión a un vector sobre el cuerpo F2, si aun no se encuentra en este. Para ello, dividimos el vector en bloques cuya longitud vale mm, donde mm era la variable que almacenaba la longitud necesaria para guardar un caracter ASCII mediante elementos de Fp. Después, realizamos la conversión de cada bloque de longitud mm a su valor numérico y seguidamente transformamos dicho número a su representación binaria mediante el empleo de un bloque de longitud 8: In: if mm<>8: menbin=[] iterar4=RR(len(menSF))/RR(mm); continuar1=True; i=0; while i<iterar4.ceil() and continuar1: entra=False; if i<>(iterar4.ceil()-1): 5.4. DESCIFRADO 77 entra=True; else: if iterar4.is_integer(): entra=True if entra: trozovector=menSF[i*mm : (i+1)*mm]; if vector(GF(self.K.characteristic()) ,[a for ain trozovector])==0: continuar1=False; else: numero=ZZ(0); for kin range(mm): numero+= ZZ(trozovector[k]) *self.K.characteristic()**(mm-k-1) q=ZZ(numero) base_bin=[] while q>=2: (q,r) =q.quo_rem(2); base_bin+=[r] if q<2: (q,r) =q.quo_rem(2); base_bin+=[r] if(len(base_bin)<8): incrementar_ceros=8-len(base_bin) for jin range(incrementar_ceros): base_bin+=[0] base_bin.reverse() else: base_bin.reverse() menbin+=base_bin i+=1; else: menbin=menSF Para finalizar, tenemos que convertir el vector que se encuentra ya sobre el cuerpo F2a los caracteres ASCII correspondientes, para ello, tras dividir el vector total obtenido en bloques de longitud 8, empleamos la función bin_to_ascii() para convertir cada bloque en el carácter correspondiente y después ya devolvemos el mensaje completo: In: h=RR(len(menbin))/RR(8); i=0; 78 CAPÍTULO 5. CRIPTOSISTEMAS DE MCELIECE continuar=True; ascii=''; while i<h.ceil() and continuar: if i<>(h.ceil()-1): caracterbin=menbin[i*8:(i+1)*8]; if vector(GF(2),[a for ain caracterbin])==0: continuar=False; else: ascii+=bin_to_ascii(caracterbin); else: if h.is_integer(): caracterbin=menbin[i*8:(i+1)*8]; ascii+=bin_to_ascii(caracterbin); i+=1; return ascii; Es importante remarcar que el lenguaje de programación de Sage utiliza un formato de codificación interno a partir del cual no es capaz de reconocer caracteres especiales ASCII. Por tanto, si ciframos una cadena de caracteres ASCII que contenga algún carácter especial, como por ejemplo la letra "ñ", tras realizar su descifrado no obtendremos estos caracteres especiales. Sin embargo, al tratarse de un problema interno de Sage, cuando realizamos el cifrado de un fichero de texto que puede contener distintos caracteres especiales y después su correspondiente descifrado, como almacenamos dicho mensaje descifrado en otro fichero de texto, al abrirlo de forma externa a Sage si que se reconocerán los distintos caracteres especiales. 5.5. Otras funciones Además de las funciones de cifrado, descifrado e introducir errores que hemos explicado hasta el momento, también hemos implementado un conjunto de funciones que nos permiten obtener propiedades fundamentales del criptosistema de McEliece creado: code_mceliece() es una función que nos proporciona el código empleado para la construcción del criptosistema. matriz_invertible() es una función que nos devuelve la matriz aleatoria invertible generada para la construcción del criptosistema. 5.6. VENTAJAS Y DESVENTAJAS DEL CRIPTOSISTEMA 79 matriz_permutacion() es una función que nos proporciona la matriz aleatoria de permutación generada para la construcción del criptosistema. public_matrix() es una función a partir de la cual obtenemos la matriz pública del criptosistema, G0. capacidad_correctora() es una función que nos devuelve el valor tintroducido, el cual nos indica el número de errores que se introducen durante el proceso de cifrado. dimension() es una función que nos proporciona la dimensión del código empleado en el criptosistema. base_f ield() es una función a partir de la cual obtenemos el cuerpo sobre el que trabaja tanto el código como el criptosistema. 5.6. Ventajas y desventajas del criptosistema El criptosistema de McEliece presenta como una de las principales ventajas, un rápido proceso de codificación y descodificación, los cuales son mas rápidos que los procesos que realizan actualmente muchos de los sistemas mas empleados, como es el caso del sistema RSA. Otra de sus ventajas es que, como ya hemos comentado, es un criptosistema postcuántico, es decir, es resistente a ataques realizados mediante ordenadores cuánticos que emplean el algoritmo de Shor. El algoritmo de Shor, es un algoritmo cuántico que fue desarrollado en 1994 y permite factorizar un número entero en factores primos en tiempo polinomial. Por ello, dicho algoritmo nos permitiría romper el criptosistema RSA y el del logaritmo discreto entre otros, los cuales, son los mas empleados actualmente a la hora de realizar cualquier cifrado asimétrico. A pesar de esto, aunque el criptosistema presenta pocas desventajas, la mas importante es que el tamaño de las claves, tanto pública como privada es muy grande, al ser matrices de elevadas dimensiones. Por ejemplo, los tamaños de parámetros sugeridos por McEliece fueron n= 1024, k=524, t=50, los cuales dan lugar a una clave pública de tamaño cercano a 219 bits. Sin embargo, debido al avance tecnológico producido en estos años, el tamaño de los parámetros sugerido ha sido elevado a n=2048, k=1750, t=27, de esta forma 80 CAPÍTULO 5. CRIPTOSISTEMAS DE MCELIECE podemos obtener 80 bits de seguridad, es decir, es necesario realizar 280 operaciones para ”romper” el criptosistema. Esto permite evitar ataques realizados por fuerza bruta con los ordenadores actuales. Sin embargo, para resistir ataques realizados mediante ordenadores cuánticos, el tamaño de estos parámetros se debe elevar hasta n=6960, k=5400, t=119, los cuales nos proporcionan un tamaño de clave pública cercano a 223 bits. Incrementar el tamaño de los parámetros esta relacionado con el incremento de los tamaños de las claves pública y privada empleadas para el criptosistema. Entonces, como estos parámetros se han incrementado notablemente en relación a los sugeridos en la versión original, la cual ya presentaba un tamaño de claves alto, tenemos como resultado un tamaño de claves muy elevado. Otro inconveniente que presenta este criptosistema es que no se puede emplear para producir firmas digitales, aunque este problema ha sido solventado empleando el criptosistema Niederreiter, el cual es un criptosistema dual al criptosistema de McE- liece que mostramos en [1, Sección 5.2] del trabajo fin de grado de matemáticas, que permite la realización de firmas digitales [7]. 5.7. Posibles ataques Consideramos un criptosistema de McEliece construido a partir del código Cde parámetros [n,k,d]y matrices SyP. Vamos a mostrar muy brevemente los dos posibles ataques que se pueden realizar contra el criptosistema de McEliece, al ser un criptosistema que emplea códigos para su construcción: Ataques genéricos de descodificación: Se trata de intentar recuperar el mensaje original, m, que hemos cifrado obteniendo el vector y, mediante el empleo del código C0que se obtiene al considerar la matriz pública del criptosistema, G0, como matriz generatriz para dicho código. Para ello, los mejores resultados se obtienen empleando algoritmos que mejoran la descodificación del conjunto de información. Esta descodificación trata de encontrar kcoordenadas del vector yque no presenten ningún error. Entonces, tomando dichas coordenadas del vector yy la matriz inversa formada por las k columnas seleccionadas de la matriz G0podemos recuperar el mensaje original m. Uno de los algoritmos de descodificación del conjunto de información mas conocido es el de Lee-Brickell [36]. Ataques contra la estructura del código: En este caso se trata de intentar recuperar, las matrices G,SyPa partir de las cuales se ha realizado la construcción del 5.7. POSIBLES ATAQUES 81 criptosistema de McEliece empleado. Para este tipo de ataques los criptosistemas de McEliece que emplean códigos de Goppa son los que presentan una elevada seguridad. Por otro lado, el ataque por filtración que mostramos en el capítulo 6, es un ejemplo de ataque contra la estructura del código cuando se emplean los códigos Reed-Solomon generalizados, ya que permite recuperar en este caso los parámetros del código C0. También existen otros tipos de ataques contra la estructura del código para otros códigos, como Reed-Muller, BCH, cuasi-cíclicos entre otros. Para finalizar el capítulo, vamos a realizar la construcción de un criptosistema de McEliece que emplea un código de Goppa para su construcción. Ejemplo 5.1. Para la construcción del criptosistema, realizamos en primer lugar la construcción del código de Goppa empleando unos parámetros muy pequeños en comparación con los sugeridos, para poder mostrar de esta forma las matrices que obtenemos. Por tanto, generamos el código de Goppa sobre el cuerpo F25, con máxima longitud n=32 y capaz de corregir t=5 errores: In: goppa=Goppa(2**5,5,5) El polinomio de Goppa empleado para su construcción es: In: goppa.polinomio_g() Out: x5 + (a3 + a2 + 1)*x2 + (a2 + a + 1)*x + a4 + a2 Ahora obtenemos la matriz generatriz del código de Goppa obtenido: In: goppa.generator_matrix() Out: [1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1] [0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1] [0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1] [0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0] [0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1] [0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1] [0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0] Mediante este código de Goppa, construimos el criptosistema de McEliece, donde indicamos que se introduzcan t=5 errores durante el proceso de cifrado, que se corresponden con la capacidad correctora del código de Goppa: 88 CAPÍTULO 6. ATAQUE CONTRA LOS CÓDIGOS GRS 6.2. Ataque por filtración a códigos GRS 6.2.1. Ataque estándar En un principio, para el ataque estándar vamos a considerar que conocemos los códigos Reed-Solomon generalizados de dimensión kyk−1, GRSk(a,b)yGRSk−1(a,b) respectivamente, donde aybson elementos de Fn qy veamos que si disponemos de estos códigos, es posible obtener el código Reed-Solomon generalizado de dimensión k−2 construido a partir de los vectores ayb, lo cual es un paso clave para nuestro ataque. Proposición 6.9. Dados los códigos GRSk(a,b)y GRSk−1(a,b), es posible calcular el código GRSk−2(a,b). Nota 6.10. Para la obtención de forma práctica del código GRSk−2(a,b), tenemos que calcular una base del código (GRSk−1(a,b)?2)⊥y después resolver el sistema construido a partir de las ecuaciones que tienen la forma gi?hj, donde gihace referencia a la fila i-esima de una matriz generatriz de GRSk(a,b)yhjhace referencia a la fila jesima de una matriz de control, H, de GRSk−1(a,b)?2. Esto es debido a que se cumple en primer lugar que (c?gi)∈GRSk−1(a,b)?2si y solo si (c?gi)·HT=0, es decir, (c?gi)·hj=0, y en segundo lugar, se verifica que (c?gi)·hj=c·(gi?hj). Por tanto, a partir de la proposición 6.9, podemos reiterar el proceso con los dos códigos Reed-Solomon generalizados que tengamos de dimensión mas baja hasta obtener el código GRS1(a,b). Como GRS1(a,b) = {λb|λ∈Fq}=hbidebido a que sus elementos se obtienen evaluando en constantes y multiplicándolas por el elemen- to b, a partir de este proceso, conocido como proceso de filtración, podemos obtener el elemento b. Para ello, hemos implementado en Sage una función llamada reducir_codigos(C,C1,reC =False), la cual va obteniendo los códigos Reed-Solomon generalizados con dimensiones menores a la del código C1 aplicando la proposición 6.9, donde la implementación se ha realizado según la forma expuesta en la nota 6.10, es decir, primero obtenemos el código cuadrado del código C1 empleando el siguiente código: In: baseC1cuadrado=[]; n=C1.generator_matrix().row(0).length(); for iin range(C1.generator_matrix().nrows()): for jin range(i,C1.generator_matrix().nrows()): baseC1cuadrado+=[vector(F,[C1.generator_matrix().row(i)[h]* C1.generator_matrix().row(j)[h] for hin range(n)]) ]; V=VectorSpace(F,n) 6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 89 subV=V.subspace(baseC1cuadrado) Gcuadrada=subV.basis_matrix() C1cuadrado=codes.LinearCode(Gcuadrada); if C1cuadrado.dimension() <> (2*C1.dimension()-1): raise TypeError('Deben emplearse códigos GRS para realizar el ataque') Podemos observar que una vez obtenemos el código cuadrado de C1, también validamos que su dimensión se corresponda con los visto en la proposición 6.6. Después resolvemos el correspondiente sistema de ecuaciones a partir de las siguientes líneas de código: In: n=len(C1.random_element()); lista=[] for iin range(C.generator_matrix().nrows()): for jin range(C1cuadrado.parity_check_matrix().nrows()): lista+=[list(vector(F,[F(C.generator_matrix().row(i)[h]* C1cuadrado.parity_check_matrix().row(j)[h]) for hin range(n)]))] AAA=matrix(F,lista) matrizG_codigo=AAA.right_kernel().basis_matrix() C2=codes.LinearCode(matrizG_codigo) Todo el proceso mostrado anteriormente se repite con los dos códigos de menor dimensión que tengamos hasta obtener un código de dimensión 1, cuya matriz generatriz se corresponde con el vector λb. El parámetro opcional recG se emplea únicamente para saber si la función debe devolver solo el vector λbo también la parte de la matriz generatriz, del código de dimensión 2 calculado, en forma estándar que no se corresponde con la matriz identidad. Su utilidad la veremos mas adelante. Si ahora obtenemos el elemento a, tendríamos determinado por completo el código Reed-Solomon generalizado y por tanto un ataque exitoso contra dicho código. Para la obtención del elemento a, vamos a emplear el código Reed-Solomon de dimensión 2, que ya tenemos calculado por la filtración realizada. A partir de este código, calculamos una matriz generatriz para él, donde nhace referencia al tamaño de los elementos codificados, que es conocido: G=g11 g12 ··· g1n g21 g22 ··· g2n 90 CAPÍTULO 6. ATAQUE CONTRA LOS CÓDIGOS GRS Como sabemos por la sección 3.25 otra matriz generatriz de GRS2(a,b)es G0=b1b2··· bn a1b1a2b2··· anbn Entonces, como la matriz generatriz en forma estándar es única, ambas matrices generatrices del mismo código deben ser equivalentes a la misma matriz generatriz en forma estándar. Por tanto, realizando eliminación de Gauss-Jordan sobre ambas matrices, tenemos que rre f (G) = rre f (G0), donde rre f (A)hace referencia a la forma escalonada reducida de la matriz A. Conocemos completamente rre f (G). Ademas, rre f (G0)tiene la siguiente forma: G0=  1 0 (a2−a3)b3 (a2−a1)b1··· (a2−an)bn (a2−a1)b1 0 1 (a3−a1)b3 (a2−a1)b2··· (an−a1)bn (a2−a1)b2   donde el elemento bya lo tenemos calculado. Por tanto igualando ambas matrices, obtenemos un sistema de 2n−4 ecuaciones lineales con nincógnitas, donde al menos n−2 ecuaciones serán linealmente independientes. Además, como sabemos que en un código Reed-Solomon generalizado siempre se pueden fijar tres puntos del vector asegún [27], entonces se puede resolver dicho sistema y por tanto obtener un único vector que se corresponde con el vector aque nos quedaba por calcular. En Sage hemos implementado la función ataque_estandar(CCC,CCC1), la cual llama en primer lugar a la función reducir_codigos(CCC,CCC1, True)para obtener el vector λby la parte de la matriz rre f (G)que no se corresponde con la matriz identidad. Después se realiza la resolución del sistema, el cual siempre presenta la misma estructura: In: def ataque_estandar(CCC,CCC1): [bb,G]=reducir_codigos(CCC,CCC1,True) F=CCC.base_ring() AA=matrix(F,G.ncols()*2,bb.ncols()) for iin range(AA.nrows()): for jin range(AA.ncols()): if j==0 and i<G.ncols(): AA[i,j]=bb[0,0]*G[0,i] if j==1 and i<G.ncols(): AA[i,j]=bb[0,i+2]-bb[0,0]*G[0,i] if j==i+2 and i<G.ncols(): AA[i,j]=-bb[0,i+2] if j==0 and i>(G.ncols()-1): 6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 91 AA[i,j]=bb[0,1]*G[1,i-G.ncols()]-bb[0,i+2-G.ncols()] if j==1 and i>(G.ncols()-1): AA[i,j]=-bb[0,1]*G[1,i-G.ncols()] if j==i+2-G.ncols() and i>(G.ncols()-1): AA[i,j]=bb[0,i+2-G.ncols()] A=matrix(F,[[AA[i,j] for jin range(2,AA.ncols())] for iin range(G.ncols())]) z=vector(F,[-AA[i,0]*1-AA[i,1]*2 for iin range(G.ncols())]); aa=A.inverse()*z a=vector(F,[1,2]+[aaa for aaa in aa]) b=vector(F,[bb[0,i] for iin range(bb.ncols())]) return [a,b]; Podemos observar que siempre se fijan las dos primeras posiciones del vector a con los mismos valores, a1=1 y a2=2, y se resuelve un sistema de ecuaciones muy simple que nos permite recuperar el vector a Ejemplo 6.1. Vamos a emplear los mismos códigos que utilizamos para mostrar el ataque estándar de forma teórica en [1, Ejemplo 6.3] del trabajo fin de grado de matemáticas. Por tanto, vamos a construir los códigos GRS4(a,b)yGRS3(a,2b), con valores a= (1,2,9,3,10,8,5,4)∈F11 yb= (3,10,5, 9,9,10,5, 2)∈F11. Únicamente suponemos que conocemos una matriz generatriz de cada código, por ello empleamos el siguiente código para realizar la construcción de los códigos y mostrar las matrices que empleamos: In: F=GF(11); a=[F(i) for iin [1,2,9,3,10,8,5,4]]; #3,9...... b=[F(i) for iin [3,10,5,9,9,10,5,2]]; b1=[F(i)*2 for iin [3,10,5,9,9,10,5,2]]; k=5 C=codes.GeneralizedReedSolomonCode(a, k, b); C.generator_matrix() Out: [ 3 10 5 9 9 10 5 2] [39152338] [379492410] [33412597] [36339716] In: C1=codes.GeneralizedReedSolomonCode(a, k-1, b1); C1.generator_matrix() 92 CAPÍTULO 6. ATAQUE CONTRA LOS CÓDIGOS GRS Out: [ 6 9 10 7 7 9 10 4] [ 6 7 2 10 4 6 6 5] [63787489] [ 6 6 8 2 4 10 7 3] Ahora empleamos la función ataque_estandar() que hemos implementado para obtener los valores de los vectores aybu otros valores que también nos permiten reconstruir el código de partida: In: parametros=ataque_estandar(C,C1) parametros Out: [(1, 2, 9, 3, 10, 8, 5, 4), (1, 7, 9, 3, 3, 7, 9, 8)] Por tanto, en este ejemplo podemos observar que recuperamos el mismo vector a, aunque no tiene porque ocurrir. En cuanto al vector bobtenido, podemos observar que es 4b. Entonces, aunque en este caso se ve claramente, al tener el mismo vector a, que los valores obtenidos van a generar el mismo código del que partíamos ya que sabemos que GRSk(a,b) = GRSk(a,λb), vamos a comprobar que la matriz generatriz estándar del código de partida y el obtenido son iguales: In: C.systematic_generator_matrix() Out: [1 0 0 0 0 2 2 7] [0 1 0 0 0 7 8 4] [0 0 1 0 0 8 9 9] [0 0 0 1 0 6 7 1] [0 0 0 0 1 3 1 7] In: CCCC=codes.GeneralizedReedSolomonCode([F(a1) for a1 in parametros[0]], k, [ F(b1) for b1 in parametros[1]]); CCCC.systematic_generator_matrix()==C.systematic_generator_matrix() Out: True 6.2.2. Ataque al criptosistema de McEliece Ahora vamos a explicar un ataque de filtración que funciona correctamente contra criptosistemas de McEliece construidos a partir de códigos Reed-Solomon generalizados y también directamente contra códigos Reed-Solomon generalizados de los cuales conocemos únicamente una matriz generatriz. Dicho ataque fue mostrado en el año 2014 en [32]. 6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 93 Para ello, partimos del código GRSk(a,b)y suponemos que la dimensión del código es menor o igual que la mitad de la longitud del código, n, es decir, k≤n 2. Si esto no ocurre, por la proposición 3.23 podemos aplicar el procedimiento sobre el código dual, que si cumplirá nuestra restricción y después recuperar, a partir de los del dual, los vectores aybde partida. En Sage hemos implementado una función llamada ataque_f iltracion(G_pub), que realiza el ataque que vamos a explicar, donde el parámetro G_pub se corresponde con la matriz generatriz del código GRSk(a,b)o la matriz pública de un criptosistema de McEliece construido a partir de GRSk(a,b). Dicha función recurre también al dual si es necesario, de forma que su implementación permite realizar el ataque a códigos GRSk(a,b)de cualquier dimensión. Comenzamos fijando las dos primeras coordenadas del vector acon valores 0 y 1 respectivamente, lo cual es posible ya que por [27] sabemos que se pueden fijar 3 puntos del vector a. Debido a esto, todos los polinomios con 0 como raíz tendrán una codificación con primera coordenada nula. De igual forma ocurre con los polinomios que tengan a 1 como raíz, cuya codificación tendrá la segunda coordenada nula. Entonces, si construimos un subcodigo de GRSk(a,b)formado únicamente a partir de las codificaciones de polinomios con una raíz de cierta multiplicidad en 0, dicho subcodigo se corresponde con el código recortado en la primera posición a partir de GRSk(a,b). De igual forma ocurre con la raíz en 1. Denotamos por C(i,j)el subcodigo de GRSk(a,b), con i,j>0 y i+j≤k−1 formado solamente a partir de las codificaciones de polinomios, f(x), que tengan a 0 como raíz con multiplicidad al menos iy a 1 como raíz con multiplicidad al menos j, es decir, xi(x−1)j|f(x). Por tanto, se cumple que C(1,0) = S1(GRSk(a,b)),C(0,1) = S2(GRSk(a,b)), C(1,1) = S{1,2}(GRSk(a,b)) y denotamos C(0,0) = GRSk(a,b). A partir de esto, vamos a probar una proposición muy parecida a la proposición 6.9, que nos permitía realizar el ataque estándar, la cual también nos proporciona el método clave para comenzar el ataque por filtración. Proposición 6.11. Sea k ≤n 2y el código GRSk(a,b), entonces ∀i,j>0tales que i +j≤ k−2se verifica que C(i+1, j)?C(i−1, j) = C(i,j)?2(6.1) Nota 6.12. Todos los códigos C(i,j)son Reed-Solomon generalizados ya que se obtienen mediante la proposición 6.11 a partir de los códigos C(1,0),C(0, 1),C(1,1)y 94 CAPÍTULO 6. ATAQUE CONTRA LOS CÓDIGOS GRS C(0,0), los cuales sabemos que son Reed-Solomon generalizados y por tanto a partir de la ecuacion (6.1) y la proposición 6.9 estamos calculando los mismos códigos. 6.2.2.1. Ataque Una vez mostrada la proposición 6.11 y la notación empleada, vamos a explicar el ataque, mostrando también el código empleado para la realización de cada paso. 1) En primer lugar, empleamos los códigos C(0,0)yC(1,0)para obtener, aplicando la ecuación (6.1) k−2 veces, el código C(k−1, 0), cuya dimensión es 1 y por tanto su matriz generatriz, G(k−1)0se corresponde solamente con un vector. El código empleado para su realización es: In: C_Lin1=codes.LinearCode(G_pub) F=C_Lin1.base_field() n=C_Lin1.length() k=C_Lin1.dimension() k1=C_Lin1.dimension() if k>(n/2): C_Lin=codes.LinearCode(C_Lin1.parity_check_matrix()) k1=C_Lin.dimension() else: C_Lin=codes.LinearCode(G_pub) C_10=C_Lin.shortened([0]) CC=C_Lin.punctured([0]) c=reducir_codigos(CC,C_10) ccc=vector(F,[c[0,i] for iin range(1,c.ncols())]) Obviamente, tenemos que el código C(k−1,0)esta formado mediante la codificación de polinomios de la forma λxk−1, ya que por definición solo se codifican polinomios que tengan en 0 una raíz de multiplicidad al menos k−1 y como la dimensión es kel grado de los polinomios no puede ser superior a k−1. Entonces, si denotamos c=G(k−1)0, tenemos que c=λ(ak−1?b). 2) Por otro lado, calculamos el código C(k−2,1)de nuevo aplicando la ecuación (6.1) k−3 veces a partir de los códigos C(0,1)yC(1,1). Para ello, empleamos las siguientes líneas de código: In: C_01=C_Lin.shortened([1]) C_11=C_Lin.shortened([0,1]) CC_01=C_01.punctured([0]) c_1=reducir_codigos(CC_01,C_11) ccc_1=vector(F,[c_1[0,i] for iin range(c_1.ncols())]) 6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 95 De nuevo el código C(k−2,1)tiene dimensión 1 y denotando c0=G(k−2)1, siendo G(k−2)1su matriz generatriz, tenemos que el vector c0es de la forma αak−2?(a−1)?b. 3) Entonces, el vector ctiene únicamente su primera coordenada nula y el vector c0tiene solo las dos primeras coordenadas nulas. Por tanto, esta bien definida la división c0 cpara todas las coordenadas excepto las dos primeras, la cual se corresponde con β(a−1) a. Ahora, como solo hemos fijado las dos primeras coordenadas del vector ay por [27] sabemos que se pueden fijar 3 elementos, podemos seleccionar un valor arbitrario para βque denotamos por β0. Entonces tenemos que la aplicación f:Fq\{0,1} −→ Fq x7−→ β0(x−1) x es una biyección que representa las distintas coordenadas obtenidas a partir del cociente de cyc0mediante la evaluación de la correspondiente coordenada de a. Por tanto, si calculamos la función inversa f−1:Fq\{β0} −→ Fq y7−→ β0 β0−y=1 1−1 β0y y evaluamos en las coordenadas de c0 cpodemos recuperar todas las coordenadas del vector aexcepto las dos primeras, lo cual no supone ningún problema ya que las hemos fijado al comienzo del ataque. Hay que tener en cuenta que puede ocurrir que alguna coordenada de c0 ctenga el valor β0y por tanto no se podría aplicar el paso anterior. Sin embargo, como nosotros elegimos el valor de β0, siempre podremos seleccionar un cierto valor de β0de forma que la función f−1este bien definida realizando su evaluación en todas las coordenadas de c0 c. Esto se debe a que todos las coordenadas del vector adeben ser distintas y por tanto también lo deben ser las de c0 c, luego existirá al menos un elemento del cuerpo empleado que no sea una coordenada de c0 cy por tanto, dicho elemento sería un valor posible para β. El código empleado para la obtención del vector a, una vez que conocemos los vectores cyc0, siguiendo los pasos mostrados es: In: division=vector(F,[F(ccc_1[h]/ccc[h]) for hin range(n-2)]) division1=vector(F,[a for ain division]) 96 CAPÍTULO 6. ATAQUE CONTRA LOS CÓDIGOS GRS numero=ZZ(1) while 1in division1: division1=vector(F,[a*F.list()[numero] for ain division]) numero+=1 aa=vector(F,[F(1/(1-division1[h])) for hin range(n-2)]) aaa=vector(F,[0,1]+[ff for ff in aa]) 4) Para finalizar, una vez que tenemos el vector apodemos recuperar fácilmente el vector bya que sabemos que c=λ(ak−1?b). Por tanto, si realizamos la división por coordenadas del vector centre ak−1recuperamos todas las coordenadas de bexcepto la primera, ya que a1=0 y por tanto la división no esta definida. Entonces para recuperar la coordenada restante, podemos ir asignándola distintos elementos del cuerpo Fqempleado hasta obtener un vector que sea una palabra del código GRSk(a,b)de partida. El código implementado para la obtención del vector bes: In: bbb=vector(F,[F(c[0,h]/aaa[h+1]**(k1-1)) for hin range(n-1)]) obtener_bbb1=0 for iin range(1,F.cardinality()): obtener_bbb=vector(F,[F.list()[i]]+[a for ain bbb]) if C_Lin.syndrome(obtener_bbb)==0: obtener_bbb1=vector(F,[a for ain obtener_bbb]) break Por tanto, ahora que ya conocemos los vectores aybdel código empleado, también disponemos del algoritmo de corrección de errores del código. Entonces, si una persona realiza el cifrado de un mensaje mobteniendo y, nosotros aplicamos el algoritmo de corrección de errores que conocemos y nos permite recuperar c, ahora obteniendo una matriz cuadrada invertible de la matriz pública de partida, podemos recuperar el mensaje mde partida. En Sage también construimos una función llamada recuperar_mensaje(G_pub,codigo,y), donde el parámetro G_pub hace referencia a la matriz pública que emplea el criptosistema de McEliece construido, codigo se corresponde con el código obtenido mediante el empleo de la función ataque_f iltraciom(), del cual podemos emplear su algoritmo de corrección de errores, y por último el parámetro yhace referencia al vector cifrado que queremos descifrar para recuperar el mensaje. Para el descifrado del vector y, dicha función se construye mediante el siguiente código: In: def recuperar_mensaje(G_pub,codigo,y): F=G_pub.base_ring() y_sin_err=codigo.decode_to_code(y) 6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 97 columnas=[] G_escalonada=G_pub.echelon_form() for iin range(G_escalonada.nrows()): pos=0 while G_escalonada[i,pos]==F(0): pos+=1 columnas+=[pos] Gcuadrada=transpose(matrix(F,[G_pub.column(a) for ain columnas])) y1_sin_err=vector(F,[y_sin_err[i] for iin columnas]) return y1_sin_err*Gcuadrada.inverse() Nota 6.13. Destacamos que en el paso 3 el valor de βno siempre puede ser 1, como sugiere el artículo [32], ya que puede ocurrir que el vector c0 ctenga alguna coordenada con valor 1 y entonces la función f−1no estaría bien definida. Por ejemplo, si realizamos el ataque de filtración sobre el código GRS4(a,b)construido en F17, con a= (0, 1,2,3,4,5,6,7,8,9)yb= (2, 3,4,5,6, 7,8,9,10, 11), obtendremos como vector c0 c= (7,15,2,1,6,12,8,3)si tomamos β=1. En cambio, tomando 1 β=2 si se puede realizar ya que β=1 2=9 no se corresponde con ninguna coordenada de c0 c. Ejemplo 6.2. Vamos a construir un criptosistema de McEliece empleando un código Reed-Solomon generalizado GRS4(a,b)sobre el cuerpo F17, donde el valor de los vectores a= (0,1,2,3,4,5,6,7,8,9)yb= (2,3,4,5,6,7,8,9,10,11)es desconocido. Para ello construimos en primer lugar el código GRS4(a,b): In: F=GF(17); a=[F(i) for iin [F.list()[i] for iin range(10)]]; #3,9...... b=[F(i) for iin [F.list()[i] for iin range(2,12)]]; k=4; C=codes.GeneralizedReedSolomonCode(a, k, b); C Out: [10, 4, 7] Generalized Reed-Solomon Code over GF(17) Ahora, cargamos el fichero que contiene la clase McEliece para poder construir el criptosistema: In: load("./McEliece.sage"); Entonces, construimos el criptosistema indicando que queremos introducir 3 errores por cada bloque que ciframos, lo cual se corresponde con la capacidad correctora del código GRS4(a,b)que estamos empleando: 104 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES Obviamente se verifica que toda matriz no singular por columnas es también una matriz no singular, sin embargo el reciproco no es cierto en muchas ocasiones, por ejemplo, si consideramos la matriz A=  1 0 1 0 1 1 1 1 1   es evidente que es no singular ya que det(A) = −1, y no es NSC ya que es necesario que en la primera fila todos sus elementos sean no nulos. En Sage empleamos el siguiente código para validar si una matriz dada es no singular por columnas dentro de la clase MatrixProductCodes. In [ ]: validar=True; for iin range(1,A.nrows()+1): if validar: for orden in Subsets(A.ncols(),i): AA=matrix(A.base_ring(),[[ A[h,j-1]for jin orden] for hin range(i)]) print(AA) if not AA.is_invertible(): validar=False; break; En la sección 7.3 se muestra el funcionamiento de la función Subsets() Definición 7.6. Diremos que un código de producto de matrices es NSC si la matriz A asociada al código es NSC. Definición 7.7. Diremos que una matriz Aes triangular si existe alguna permutación por columnas, π, que transforma la matriz en una matriz triangular superior, es decir, si aiπ(j)=0∀i>π(j) Proposición 7.8. Una matriz triangular NSC A de tamaño M ×N tiene exactamente i −1 ceros en la i-esima fila, con 1≤i≤M. Ahora vamos a introducir la proposición que nos permitirá conocer la distancia mínima de un código de producto de matrices, pero antes de ello, denotamos Ri= (ai1,..., aiN)∈FN q, es decir, Ries un vector de tamaño Nformado por los elementos de la i-esima fila de la matriz A, los cuales pertenecen a Fq. A partir de ello, construimos ahora los códigos CRigenerados a partir de los vectores Rjcon j=1, ..., i, es decir, generados por las iprimeras filas de la matriz A. Por tanto, CRi=hR1,..., Rii, y denotamos por Dila distancia del código CRi. 7.1. INTRODUCCIÓN 105 Proposición 7.9. Dado un código de producto de matrices C = [C1···CM]·A, entonces se cumple la siguiente desigualdad para la mínima distancia: d(C)≥min{d1·D1,d2·D2, ..., dM·DM} donde dihace referencia a la distancia del código Ciy Dia la distancia del código CRi. Nota 7.10. Como CRiesta generado a partir de los vectores R1,..., Ri, es decir, a partir de las iprimeras filas de la matriz A, es evidente que CRi⊂CRi+1y por tanto también que Di≥Di+1. Por tanto, para obtener un código de producto de matrices con buenos parámetros es conveniente elegir los códigos Cjde manera que la distancia mínima de estos se vaya incrementando o al menos sea igual, es decir, dj+1≥dj, para obtener de esta forma la mayor distancia posible en el código de producto de matrices a partir de los códigos que lo generan, lo cual sabemos que permite corregir una mayor cantidad de errores. También es aconsejable coger Cj+1con una dimensión menor o igual que la de Cj. Por tanto, para que pueda ocurrir lo descrito anteriormente será necesario que C1 tenga una dimensión grande y que el último de los códigos tenga una distancia mínima grande. Ademas de intentar maximizar la distancia mínima del código de producto de matrices, como esta viene delimitada a partir de una desigualdad, es importante también saber exactamente como de grande es la distancia mínima del código, para conocer de esta forma, la cantidad máxima exacta de errores que podemos corregir. Por ello, vamos a ver a continuación dos formas de obtener la igualdad en la desigualdad que tenemos de la distancia. Para la primera forma, consideramos que los códigos C1,..., CMson encajados, es decir, CM⊂CM−1⊂ ··· ⊂ C1. Estos códigos verifican que dM≥dM−1≥ ··· ≥ d1, luego no estamos restringiendo de forma excesiva el conjunto de códigos a escoger al ser del tipo deseado para maximizar la distancia del código de producto de matrices. Para los conjuntos de códigos con esta propiedad se verifica el siguiente teorema, con la igualdad deseada para la distancia mínima del código de producto de matrices. Teorema 7.11. Dado un código de producto de matrices C = [C1··· CM]·A donde Cicon i=1,..., M son códigos que verifican CM⊂CM−1⊂ ··· ⊂ C1y A es una matriz de tamaño M×N. Entonces se cumple que d(C) = min{d1∗D1,d2∗D2, ..., dM∗DM} En cuanto a la segunda forma, imponemos que la matriz Asea NSC y triangular, lo cual nos permite obtener la igualdad en la desigualdad de la distancia para los códigos de producto de matrices que tenemos como podemos ver en el siguiente teorema. 106 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES Teorema 7.12. Si A es una matriz M ×N NSC y el código NSC es C = [C1···CM]·A, entonces se cumple que: 1) |C|=|C1|···|CM| 2) d(C) ≥d∗=min{Nd1,(N−1)d2, ..., (N−M+1)dM} 3) Si ademas A es también una matriz triangular entonces d(C)=d∗ En Sage construimos una función que nos proporciona la distancia mínima del código de producto de matrices construido llamada minimum_distance(), la cual se obtiene según lo visto en el teorema 7.11, al cumplirse para todos los códigos de producto de matrices que construimos las hipótesis del teorema. In: for iin range(self._A.nrows()): G=matrix(self._A.base_ring(),[[self._A[j,k] for kin range(self._A.ncols())] for jin range(i+1)]) D.append(codes.LinearCode(G).minimum_distance()) d.append(self._lista_codigos[i].minimum_distance()) if(d[i]*D[i]<distancia): distancia=d[i]*D[i]; return distancia; 7.2. Codificación Para realizar el proceso de codificación de los códigos de producto de matrices, al igual que hacíamos para codificar los códigos lineales en la sección 3.2, simplemente tenemos que multiplicar un mensaje, m, con longitud la dimensión del código, k, por la matriz generatriz del código, G, es decir, c=mG, donde chace referencia al mensaje codificado. En Sage creamos una función llamada encode(sel f,mensaje)que realiza dicho proceso para codificar el parámetro mensaje: In: def encode(self, mensaje): if mensaje.length()==self._k and mensaje.base_ring()==self._G.base_ring(): return mensaje*self._G; Además de la forma clásica para codificar un mensaje, para los códigos de producto de matrices también se podría dividir cada trozo del mensaje en bloques de tamaño correspondiente a la dimensión de cada código empleado dentro del MPC y codificar por separado cada bloque. Después si ponemos las palabras codificadas de cada uno de los subcodigos como columnas y los multiplicamos por la matriz Asegún vimos en la definición 7.1 obtendríamos el mensaje codificado. 7.3. DESCODIFICACIÓN 107 7.3. Descodificación Después de mostrar los códigos de productos de matrices así como la obtención de sus parámetros, de forma exacta, si empleamos una matriz Ano singular por columnas y triangular gracias al teorema 7.12, o si utilizamos códigos incrustados para la generación de los códigos de producto de matrices según lo visto en el teorema 7.11. Ahora nos preguntamos si podemos emplear los códigos de productos de matrices para realizar la construcción de criptosistemas de McEliece. Por tanto, lo que nos falta por obtener es como realizar una descodificación para dichos códigos. Por ello, vamos a mostrar un algoritmo que permita realizar la descodificación de los códigos de producto de matrices, para el cual es necesario que los códigos que empleamos para la obtención de los códigos de producto de matrices sean encajados, así como que la matriz Asea no singular por columnas, lo cual, vimos anteriormente que no es una condición tan restrictiva ya que queremos formar códigos de producto de matrices con la mayor mínima distancia posible. También es necesario que los códigos empleados para generar el código de producto de matrices dispongan cada uno de ellos de un algoritmo de descodificación. Teniendo en cuenta lo anterior, consideramos, C= [C1···CM]·A, un código de producto de matrices formado por la matriz Ano singular por columnas y por los códigos C1,...,CMencajados y de longitud n, donde cada código Ci, con i=1,..., M, posee un algoritmo de descodificación, que denotamos por DCi, el cual es capaz de corregir hasta un máximo de ti=di−1 2errores de una palabra del código Ci. Vamos a mostrar un método de descodificación que nos permita corregir siempre la máxima capacidad correctora del código, es decir, t=d(C)−1 2, siendo d(C)la distancia del código de producto de matrices C, obtenida a partir del teorema 7.11 o el teorema 7.12. Antes de mostrar el método de descodificación, mostramos la función implementada en Sage llamada introducir_errores(sel f ,mensajecodi f icado,cantidad), la cual realiza un proceso muy semejante a la función introducir_errores() de los códigos de Goppa que vimos en la sección 4.3, con la diferencia de que en dicha función solo se introducian errores en vectores binarios, mientras que en esta función se introducen errores en vectores que se encuentran en cualquier cuerpo finito. Por tanto, en este caso tenemos que generar elementos aleatorios para las distintas posiciones del vector de errores. Esta generación de elementos aleatorios lo hacemos empleando la función random_element() ya implementada en Sage sobre distintos cuerpos, entre ellos los cuerpos finitos que nosotros empleamos. In: if mensajecodificado.is_vector() and boolG and 108 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES mensajecodificado.base_ring()== self._F and len(mensajecodificado)>= cantidad and len(mensajecodificado)>= self._n and cantidad>2: entrar=True; while entrar: mensajeerror=vector(self._F,[mensajecodificado[p] for p in range(len(mensajecodificado))]); indices =range(len(mensajeerror)); posiciones_error=[]; for iin range(cantidad): error=self._F(0); while error==self._F(0): error=self._F.random_element(); posicion=indices.pop(randint(0,len(indices)-1)); mensajeerror[posicion]+= error; posiciones_error.append(posicion) bloque_longitud=self._n/self._A.nrows() nosale=False for iin range(self._A.nrows()): contar=0; for ain posiciones_error: if i*bloque_longitud <= aand a<(i+1)*bloque_longitud: contar+=1; if contar<>0 and contar<3: nosale=True if not nosale: entrar=False; return mensajeerror; elif mensajecodificado.is_vector() and mensajecodificado.base_ring()== self._F and len(mensajecodificado)>= cantidad and len(mensajecodificado)>= self._n: mensajeerror=vector(self._F,[mensajecodificado[p] for p in range(len(mensajecodificado))]); indices =range(len(mensajeerror)); for iin range(cantidad): error=self._F(0); while error==self._F(0): error=self._F.random_element(); mensajeerror[indices.pop(randint(0,len(indices)-1))]+= error; return mensajeerror; 7.3. DESCODIFICACIÓN 109 Podemos observar también en las sentencias mostradas que distinguimos entre los códigos de producto de matrices construidos a partir de al menos un código de Goppa y los construidos sin emplear ningún código de Goppa, empleando la función is_Gopppa() que implementamos en dichos códigos cuyo valor es almacenado en la variable boolG que utilizamos. El motivo de esta distinción se encuentra como vimos en 4.3.2, que el algoritmo de descodificación implementado en los códigos de Goppa no es capaz de corregir únicamente uno o dos errores. Por tanto, en este caso tenemos que restringir las posiciones aleatorias de los errores, de forma que en cada bloque que pertenezca a un código de Goppa haya o cero errores o mas de dos. Con respecto al método de descodificación, vamos a emplear los algoritmos de descodificación de los Mcódigos que generan el código de producto de matrices. Mostramos a continuación el algoritmo que permite descodificar una palabra recibida y=c+edonde c∈Cyees un vector de errores de longitud nN con un peso menor o igual a la capacidad correctora del código, es decir, ω(e)≤t. Para ello, dicho algoritmo debe recibir como parámetros tanto la matriz Acomo los Mcódigos junto con sus algoritmos de descodificación, además de la palabra yque queremos descodificar. Para la función implementada en Sage llamada decodi f icar_MPC(sel f ,y1, decodi f icarV = True), únicamente es necesario la introducción de la palabra yen el parámetro llamado y1, al estar el resto de datos almacenados en la propia clase del código de producto de matrices construido. Además, dicha función también tiene el parámetro booleano opcional decodi f icarV que nos permitirá indicar si queremos descodificar el vector introducido o únicamente corregir los errores de dicho vector. Si no se indica ningún valor al parámetro decodi f icarV, este recibirá automáticamente el valor True y por tanto, realizará la descodificación del vector introducido. Algoritmo 7.13. 1 : y0=y; 2 : A0=A; 3 : f or {i1,..., iM} ⊂ {1,..., N}: 4 : y=y0; 5 : A=A0; 6 : f or j =1,..., M: 7 : yij=DCj(yij); 8 : i f yij=”fallo” : 9 : break #Rompemos el for y tomamos otro {i1,...,iM}en la linea 2 10 : f or k =j+1,..., M: 11 : yik=yik−ajik ajij yij; 110 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES 12 : columnaik(A) = columnaik(A)−ajik ajij columnaij(A); 13 : Recuperamos (c1, ..., cM); 14 : y= [c1, ..., cM]·A; 15 : i f y ∈Cand ω(y−y0)≤[d(C)−1 2]: 16 : return y; Si yes la palabra recibida, el algoritmo considera {i1,...,iM} ⊂ {1,..., N}un subconjunto ordenado de indices, de forma que el vector de errores e= (e1, ..., eN)satisfaga que ω(eij)≤tj∀j∈ {1, ..., M}. Si el subconjunto ordenado de indices no verifica esto en todos los indices, por ejemplo, supongamos que no se cumple para el indice ij0, entonces el correspondiente algoritmo de descodificación DCj0no es capaz de corregir todos los errores que tiene ese bloque, y por tanto, puede ocurrir que no encuentre ninguna palabra del código Cj0que se encuentre a distancia menor que tj0del bloque yij0y en ese caso, podemos suponer que devuelve una respuesta de "fallo", o que por el contrario si encuentre una palabra que pertenezca al código Cj0y entonces el algoritmo nos devolverá como resultado una palabra del código que no es la correcta. En esta situación, si no existe otro indice para el que el respectivo algoritmo de descodificación proporcione como respuesta "fallo", podemos percatarnos de que la descodificación realizada es errónea comprobando si la palabra descodificada, constituida por todos los bloques descodificados, es una palabra del código de producto de matrices Cy comprobando también que no se han corregido mas de terrores. En cualquiera de los dos casos, habría que considerar otro subconjunto distinto de indices y realizar el mismo procedimiento. Además, podemos observar que es suficiente con tomar un subconjunto de indices de Melementos dentro de los Nposibles ya que como la matriz Aes no singular por columnas, de las Ncolumnas, Mson linealmente independientes y las N−M restantes se pueden obtener como combinación lineal de las otras. Para ir tomando todos los posibles subconjuntos de indices de un conjunto dado de mayor tamaño, Sage tiene implementada ya dos funciones, la primera se llama Permutations(a,b), la cual nos proporciona todos los subconjuntos posibles de tamaño ba partir de los elementos que componen la lista a, o también apuede denotar un entero, que indica desde el uno, todos los enteros que constituyen el conjunto a considerar. También presenta otro tipo de parámetros para realizar otras construcciones, pero no los vemos ya que no es necesario emplearlos. En cuanto a la segunda función, se llama Subsets(a,b), la cual nos proporciona de igual forma que la función Permutations(), todos los subconjuntos posibles de tamaño ba partir de los elementos que componen la lista a, o también apuede denotar un entero, que indica desde el uno, todos los enteros que constituyen el conjunto a con- 7.3. DESCODIFICACIÓN 111 siderar, de forma que dichos subconjuntos presenten sus elementos ordenados de forma creciente. Por tanto, la diferencia se encuentra en que mientras que con la función Permutations() podemos tener los subconjuntos [1, 2]y[2,1], con Subsets() únicamente tendríamos el subconjunto {1, 2}. Por tanto, nosotros necesitamos emplear ahora la función Permutations(), de forma que genere todas las posibles permutaciones de tamaño Msobre el conjunto de tamaño Nque empleamos. In: ordenes=Permutations(self._A.ncols(),self._A.nrows()) for orden in ordenes: Si denotamos para cada i=1,..., Npor yi=∑M j=1ajicj+eiel i-esimo bloque de la palabra recibida y. Entonces, como el bloque i1tiene un vector de error menor que la capacidad correctora del código C1y además al ser códigos incrustados sabemos que cualquier bloque de ces una palabra del código C1. Empleando el algoritmo de descodificación DC1podemos obtener el bloque i1sin errores, ademas del bloque i1 del vector de errores. Por tanto, realizamos una distinción entre si el bloque que vamos a descodificar pertenece a un código de Goppa u otro código lineal de los que vimos en el capítulo 3, ya que las funciones de descodificación se denotan de distinta forma: In: try:boolG=self._lista_codigos[j-1].is_Goppa(); except: boolG=False; yy[(orden[j-1]-1)]=y[(orden[j-1]-1)*tam:(orden[j-1])*tam]; try:if boolG: y[(orden[j-1]-1)*tam:(orden[j-1])*tam]=self._lista_codigos[j-1] .decodificar(y[(orden[j-1]-1)*tam:(orden[j-1]) *tam], False,False); else: y[(orden[j-1]-1)*tam:(orden[j-1])*tam]=self._lista_codigos[j-1] .decode_to_code(y[(orden[j-1]-1)*tam:(orden[j-1])*tam]); except: salir=True; if salir: break; Podemos observar que la descodificación la realizamos dentro de la sentencia try, de modo que si la función de descodificación nos devuelve algún error, salimos del bucle para escoger otra permutación posible. 112 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES Para eliminar los errores en el resto de bloques vamos tomando el vector yk), con k=2,..., M, formado por las componentes yk) i=yk−1) i−ak−1) (k−1)i ak−1) (k−1)ik−1 (yk−1) ik−1−eik−1) = M ∑ j=k ak) ji cj+ei∀i6=i1, ..., ik−1 donde ak) ji =ak−1) ji −ak−1) (k−1)i ak−1) (k−1)ik−1 ak−1) jik−1 y yk) i1=yk−1) i1,..., yk) ik−2=yk−1) ik−2,yk) ik−1=yk−1) ik−1−eik−1 Por tanto, en Sage empleamos las siguientes sentencias para actualizar la matriz A y el vector y: In: for kin [j+1..len(self._lista_codigos)]: y[(orden[k-1]-1)*tam:(orden[k-1])*tam]=y[(orden[k-1]-1) *tam:(orden[k-1])*tam]-(A[j -1,orden[k-1]-1] /A[j -1,orden[j-1]-1]*y[(orden[j-1]-1) *tam:(orden[j-1])*tam]); columna=A.column(orden[k-1]-1)-(A[j -1,orden[k-1]-1] /A[j -1,orden[j-1]-1]*A.column(orden[j-1]-1)); for hin range(A.nrows()): A[h,orden[k-1]-1]=columna[h]; Como por construcción, si i∈ {1,..., M}\{i1,...,ik−1}, tenemos que el bloque iesimo de yk)es una palabra del código Ckmas el i-esimo bloque del vector error, por tanto, usando el algoritmo de descodificación DCksobre el ik-esimo bloque, obtenemos el bloque de error iky∑M j=kak) jikcj. Ahora, como tenemos los bloques de error ei, con i∈ {i1,..,iM}, podemos recuperar los bloques de la palabra de código ∑M j=kak) ji cj, con i∈ {i1,..,iM}, y por tanto, tenemos el vector (∑M j=kak) ji1cj, ..., ∑M j=kak) jiMcj)sin errores, el cual es igual al resultado que se obtiene al multiplicar [c1···cM]·A(i1, ..., iM), siendo A(i1,...,iM)la submatriz de tamaño Mde la matriz Aformada a partir de las columnas i1, ..., iMde la matriz A. Como la matriz A(i1, ..., iM)es invertible al tener rango máximo por ser Ano singular por columnas, podemos obtener los vectores c1, ..., cM. 7.3. DESCODIFICACIÓN 113 Por ultimo, realizando la multiplicación [c1···cM]·Apodemos recuperar los N− Mbloques restantes del vector c, es decir, los N−Mbloques restantes del vector ysin errores, como queríamos. Obviamente, si nos encontramos en el caso particular en que N=Mobtenemos directamente todo el mensaje codificado csin errores, por lo que no es necesario realizar lo visto en los dos últimos párrafos. En cambio si N6=Msi es necesario realizarlos para obtener la palabra entera sin errores: In: for pin range(len(ee)): ee[p]=yy[p]-y[p*tam:(p+1)*tam]; devolver[p*tam:(p+1)*tam]=devolver[p*tam:(p+1)*tam]-ee[p]; if self._A.ncols()<> self._A.nrows(): devolver1=vector(devolver.base_ring(),[a for ain devolver]) orden_ordenado=[] for ain [1..self._A.ncols()]: if ain orden: orden_ordenado+=[a]; Acuadrada=transpose(matrix(self._F,[self._A.column(a-1)for a in orden_ordenado])); partemensaje=transpose(matrix(self._F,[[ a for ain devolver1[(p-1)*tam:(p)*tam]] for pin orden_ordenado])); partemensajedescifrado=partemensaje*Acuadrada.inverse(); corregidoerrores=partemensajedescifrado*self._A lista=[] for ain range(corregidoerrores.ncols()): lista+=[ corregidoerrores.column(a)[p] for pin range(len(corregidoerrores.column(a)))] devolver=vector(self._F,lista) error_r=devolver2-devolver Para finalizar la ejecución de la función decodi f icar_MPC(), en caso de que el valor booleano introducido en el parámetro decodi f icarV sea True y que la palabra sobre la que hemos corregido los errores, sea una palabra del código de producto de matrices y la cantidad de errores menor que la capacidad correctora, se realiza la descodificación de forma semejante a la vista en los códigos de Goppa en la sección 4.3.3: In: if self._H*devolver==0 and error_r.hamming_weight()<=tt: if decodificarV: Gcuadrada=matrix(self._F,self._k); while Gcuadrada.rank()<> self._k or Gcuadrada.ncols()<>self._k: columnas=[]; 120 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES      G0 10··· 0 0G0 2··· 0 . . .. . ..... . . 0 0 ··· G0 M           a11 a12 ··· a1M a21 a22 ··· a2M . . .. . ..... . . aM1aM2··· aMM      =    G1a11 G1a12 ··· G1a1M . . .. . ..... . . GMaM1GMaM2··· GMaMM   =G0 donde A= (aij)1≤i,j≤My hemos empleado un abuso de la notación al realizar una multiplicación de un elemento perteneciente a F2,aij, por una matriz, Gi. Entonces, una vez obtenida la matriz G0simplemente multiplicamos el mensaje por dicha matriz para obtener su codificación, es decir, c=m·G0. Ahora a partir de la capacidad correctora de errores del código producto de matrices empleado, t, introducimos un vector de errores ede igual longitud que el vector c y con peso de Hamming inferior o igual a t. Por tanto obtenemos el mensaje cifrado tras sumar dicho vector de errores con el mensaje codificado, y=c+e. 7.4.3. Descifrado Para realizar el descifrado del vector y, empleamos las matrices de la clave privada para generar una matriz de permutación cuadrada, Π, de tamaño n∗My una matriz invertible S, las cuales se construyen como se muestra a continuación: Π=     π0··· 0 0π··· 0 . . .. . ..... . . 0 0 ··· π      ,S=     S10··· 0 0S2··· 0 . . .. . ..... . . 0 0 ··· SM      , donde πes la matriz de permutación cuadrada de tamaño nySies la matriz invertible cuadrada de tamaño ki. Para la construcción de estas matrices ΠyS, así como para la construcción de la matriz generatriz pública total, G0, que mostramos en la sección 7.4.2, también hemos implementado en Sage una función llamada McEliece_publica_privada(sel f ,S_bloques,P_bloques)dentro de la clase MatrixProductCodes, la cual construye las matrices a partir de la introducción de las Mmatrices invertibles Si, con 1 ≤i≤M,y la matriz de permutación π: 7.4. NUEVO CRIPTOSISTEMA DE MCELIECE 121 In: def McEliece_publica_privada(self,S_bloques,P_bloques): S=matrix(S_bloques[0].base_ring(),self._k); P=matrix(P_bloques.base_ring(),self._n); B=identity_matrix(self._A.nrows()); for iin range(self._k): principio=0; fin=0; for hin range(len(S_bloques)): if h==0: fin += S_bloques[h].nrows(); else: principio =fin; fin += S_bloques[h].nrows(); for jin range(fin-principio): if i<fin and i>=principio: S[i,j+principio] =S_bloques[h][i-principio,j]; h=-1; n=P_bloques.nrows(); for iin range(B.ncols()): for kin range(n): h+=1; for jin range(B.ncols()*n): P[h,j]=B[i,floor(j/n)]*P_bloques[k,j%n]; return [S,P,S*self._G*P]; A partir de estas matrices podemos realizar ya la descodificación de forma semejante a la versión original presentada por McEliece, visto en la sección 5.4.1, es decir, multiplicando el mensaje cifrado por la matriz de permutación inversa, Π−1, obteniendo que y·Π−1=m·S·G+e·Π−1. Como e·Π−1sigue siendo un vector de peso de Hamming inferior o igual a t y además tenemos impuestas todas las condiciones necesarias para poder emplear el algoritmo de descodificación de los códigos de producto de matrices visto en la sección 7.3, aplicamos dicho algoritmo de descodificación y obtenemos m·S·G. Ahora realizamos la descodificación obteniendo el vector m·Sy aplicando la matriz inversa de Ssobre dicho vector recuperamos el mensaje. De esta forma, hemos mostrado una versión del criptosistema de McEliece que reduce notablemente el tamaño de las claves pública y privada, manteniendo la seguridad de dicho criptosistema. Por tanto, se elimina de esta forma la principal desventaja que presentaba dicho criptosistema. En cuanto a los códigos empleados para la construcción del código de producto de 122 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES matrices, se expone en esta versión el empleo de códigos de Goppa binarios debido a las buenas propiedades que hemos visto que presentan. Sin embargo, es posible emplear cualquier otro tipo de códigos con el nuevo criptosistema presentado siempre que podamos garantizar, en cierta medida, que la seguridad no resulta comprometida al emplearlos. Por último, se recomienda escoger los códigos de Goppa de forma que se maximice la distancia del código producto de matrices vista en la proposición 7.9, y que los polinomios que generan dichos códigos de Goppa sean separables, para que de esa forma, la capacidad correctora de dicho código sea lo mas grande posible por lo visto en la proposición 4.6. Ejemplo 7.2. Vamos a mostrar un ejemplo para el cual generamos las claves pública y privada de tamaño reducido y las comparamos con el mismo sin realizar el proceso de reducción de claves. Para ello, emplearemos la misma matriz Ay los dos códigos de Goppa construidos en [1, Ejemplo 9.1] del trabajo fin de grado de matemáticas. Por tanto, empleamos la matriz Asiguiente: In: A=matrix(GF(2),[[1,1],[0,1]]); A Out: [1 1] [0 1] Ahora construimos el código de Goppa C1generado a partir del vector Lformado por todos los elementos del cuerpo F25y el polinomio irreducible g1(x) = x3+ (α4+ α2+1)x+α3+α2+α+1, siendo αun elemento primitivo de F25: In: F.<a>=GF(2**5); a=F.gen(); PolRing.<x>=PolynomialRing(F) x=PolRing.gen() g1=PolRing(x^3 + (a^4 + a^2 + 1)*x+a^3 + a^2 + a+ 1) ; C1=Goppa(2**5,5,g1); De igual forma, construimos el código de Goppa C2a partir del mismo vector L y de un polinomio separable, g2, que verifique que g1|g2, para obtener de esta forma que C2sea un subcodigo de C1. Por tanto tomamos g2(x) = x6+ (α3+α2)x4+ (α2+ α)x3+ (α4+α3+α+1)x2+ (α4+α3+α2+α+1)x+α4+α3: In: F.<a>=GF(2**5); g2=x^6 + (a^3 + a^2)*x^4 + (a^2 + a)*x^3 + (a^4 + a^3 + a+ 1)*x^2 +(a^4 + a^3 + a^2 + a+ 1)*x+a^4 + a^3 ; 7.4. NUEVO CRIPTOSISTEMA DE MCELIECE 123 In: C2=Goppa(2**5,5,g2) Obtenemos las matrices generatrices tanto del código C1como del código C2: In: C1.generator_matrix() Out: [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1] [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1] [0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 1] [0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0] [0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0] [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1] [0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0] [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1] [0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1] [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0] [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 0 1] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0] In: C2.generator_matrix() Out: [1 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0] [0 1 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1] [0 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 0 1] A partir de estas matrices, obtenemos que los parámetros fundamentales de C1y C2son respectivamente [32, 17,7]y[32,3,13]. Con los códigos C1yC2, junto con la matriz Aconstruimos el código de producto de matrices y obtenemos su matriz generatriz, pero debido al gran tamaño de esta, Sage solo nos indica sus dimensiones y el cuerpo al que pertenecen sus elementos: In: codigo_MPC=MatrixProductCodes(A,[C1,C2]); In: codigo_MPC.generator_matrix() Out: 20 x 64 dense matrix over Finite Field of size 2 124 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES Con esto, obtenemos que los parámetros fundamentales de codigo_MPC son [64,20,13], lo cual coincide con lo visto a lo largo de la teoría. Si queremos que Sage nos muestre la matriz generatriz habría que incorporar, como ya hemos comentado anteriormente, la función str() después de la función generator_matrix(). Ahora llamamos a la función McEliece_publica_privada_reducida() y almacenamos en la variable claves_reducidas el conjunto de valores que nos proporciona la función. Por tanto, en esta variable tenemos en claves_reducidas[0]las matrices invertibles cuadradas aleatorias de tamaños 17 y 3 respectivamente: In: claves_reducidas=codigo_MPC.McEliece_publica_privada_reducida(); claves_reducidas[0] Out: [ [0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1] [0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1] [0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0] [0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1] [1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1] [0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0] [0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1] [0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1] [1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1] [1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0] [1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0] [0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1] [1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1] [0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1] [1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1] [1 1 1] [0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0] [1 1 0] [0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1], [1 0 1] ] En claves_reducidas[1]la matriz de permutación cuadrada aleatoria de tamaño 32: In: claves_reducidas[1] Out: 32 x 32 dense matrix over Finite Field of size 2 En claves_reducidas[2]la matriz Ay en claves_reducidas[3]las dos matrices generatrices enmascaradas de tamaños 17 ×32 y 3 ×32 respectivamente: In: claves_reducidas[3] 7.4. NUEVO CRIPTOSISTEMA DE MCELIECE 125 Out: [ [1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1] [0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0] [0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1] [0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1] [1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1] [1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1] [0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1] [0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1] [0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0] [1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0] [0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1] [1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0] [1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1] [1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0] [1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 0 1] [0 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0] [1 1 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1], [1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0] [1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0] [1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1] ] Por último, empleando los valores de claves_reducidas[0]yclaves_reducidas[1]obtenemos las matrices S,PyG0en ese orden en las posiciones 0,1 y 2 de la variable claves mediante la ejecución de la función McEliece_publica_privada(): In: claves=codigo_MPC.McEliece_publica_privada(claves_reducidas[0], claves_reducidas[1]) In: claves[0] Out: 20 x 20 dense matrix over Finite Field of size 2 In: claves[1] Out: 64 x 64 dense matrix over Finite Field of size 2 In: claves[2] Out: 20 x 64 dense matrix over Finite Field of size 2 126 CAPÍTULO 7. CÓDIGOS DE PRODUCTO DE MATRICES Por tanto, podemos reducir el tamaño de la clave que tenemos que almacenar ya que de tener que guardar una matriz de tamaño 20 ×64 en este caso, tenemos que almacenar una matriz de tamaño 17 ×32 y otra de tamaño 3 ×32 correspondientes a cada uno de las matrices generatrices de los códigos de Goppa enmascarados, junto con la matriz A de tamaño 2 ×2 para este ejemplo. Entonces, de la primera forma tendríamos que almacenar un total de 1280 bits o 160 bytes mientras que en la segunda forma tenemos que almacenar un total de 544 +96 +4=644 bits o [80,5] = 81 bytes lo que reduce prácticamente a la mitad el tamaño de la clave pública que se debe transmitir y almacenar, además vemos que esto sucede en el peor de los casos, es decir, como mínimo se reducirá a la mitad el tamaño de la clave, ya que si tomamos una matriz A que admita una mayor cantidad de códigos obtendremos una clave pública total de gran tamaño mientras que cada matriz generatriz enmascarada de cada código que compone el MPC resultará muy pequeña en comparación a la matriz total. En cuanto a la clave privada, tenemos que almacenar las matrices G,SyPjunto con el algoritmo de descodificación del código, el cual ocupa el mismo espacio en ambas formas. En cuanto a la matriz Gel tamaño se reduce de igual forma que en la clave pública al corresponderse con matrices de iguales tamaños, es decir, 1280 bits de la primera forma y 644 bits de la segunda. Además, en cuanto a las matrices SyP, su tamaño de la primera forma es de 400 bits y 4096 bits respectivamente. Sin embargo, a partir de la reducción de las claves es necesario solamente almacenar 289 bits de S1 y 9 bits de S2obteniendo un tamaño total de 298 bits a almacenar para las matrices invertibles. En cuanto a la matriz de permutación reducida son necesarios almacenar 1024 bits, donde podemos observar que también se produce una reducción drástica de los tamaños a almacenar. Capítulo 8 Pruebas del código implementado En este capítulo vamos a realizar un análisis del conjunto de funciones implementadas en Sage que presentan una gran relevancia y complejidad, donde para cada una de ellas comprobaremos que su ejecución es la esperada mediante la ejecución de distintos ejemplos, midiendo el tiempo de ejecución que emplean. Construiremos 3 ejemplos para cada tipo de código, donde intentaremos que los parámetros fundamentales de estos códigos sean n=4096, 2048, 1024, k= 2660, 1750, 524 en los distintos tipos. Se han escogido estos tamaños debido a que eran aproximadamente los aconsejados para construir el criptosistema de McEliece en distintos periodos de tiempo que vimos en la sección 5.6. En cuanto a los dos ataques de filtración contra los códigos Reed-Solomon generalizados, únicamente realizamos una medición del tiempo de ejecución que emplean las funciones implementadas para realizar el ataque contra un criptosistema de McEliece construido con un código Reed-Solomon generalizado, ya que se trata del ataque que tendremos que realizar siempre en una situación real. Además, reducimos los parámetros fundamentales del código Reed-Solomon generalizado empleado an=256, 128, 64 ya que su complejidad es mas elevada que todas las funciones medidas anteriormente, por tanto, el tiempo que necesitan emplear es bastante mas elevado. Además de los ejemplos que mostramos en este capítulo y los mostrados a lo largo de los capítulos anteriores, en los archivos con formato ”.ipynb” donde se encuentra el código implementado, se encuentran también otros ejemplos adicionales que se han realizado para comprobar el correcto funcionamiento de todas las funciones. 127 128 CAPÍTULO 8. PRUEBAS DEL CÓDIGO IMPLEMENTADO 8.1. Goppa Comenzamos con la clase que permite realizar la construcción de los códigos de Goppa. Para realizar la medición del tiempo de ejecución que emplea cada función, empleamos la función time() de Sage. Para ello es necesario incorporar la librería time que la contiene empleando la sentencia: ”from time import time” Ahora vamos a construir los códigos de Goppa empleando los parámetros que ya hemos dicho, para ello vamos a separar el tiempo necesario para calcular el polinomio irreducible necesario para la construcción de cada uno de ellos: Para el cálculo del polinomio irreducible de grado 119 sobre el cuerpo F212 se han necesitado 36,54 segundos. Para el cálculo del polinomio irreducible de grado 27 sobre F211 se han necesitado 0,39. Por último, para calcular el polinomio irreducible de grado 50 sobre F210 se han necesitado 1,09 segundos. Podemos observar una notable reducción del tiempo empleado para el cálculo de los polinomios irreducibles a medida que disminuimos el grado del polinomio a generar, así como el cuerpo Fqsobre el que vamos a construir cada código, donde únicamente tenemos un tiempo algo elevado en parámetros cercanos a los necesarios para resistir ataques cuánticos. Una vez calculados los polinomios irreducibles de los grados deseados vamos a generar los correspondientes códigos de Goppa: Para el código de Goppa de parámetros [4096,2668,239], que denotamos C1, se han necesitado 219,24 segundos Para el código de Goppa de parámetros [2048, 1751,55], que denotamos C2, se han necesitado 46,74 segundos Para el código de Goppa de parámetros [1024, 524,101], que denotamos C3, se han necesitado 12,14 segundos Ahora vamos a realizar la codificación y descodificación de un vector formado por elementos de F2cuyo tamaño sea justamente la dimensión de los tres tipos de códigos construidos. 8.2. CÓDIGOS DE PRODUCTO DE MATRICES 129 En cuanto a los tiempos de codificado, obtenemos unos resultados de 0,07, 0,04 y 0,18 para C1,C2yC3respectivamente los cuales son muy pequeños, pero esto es de esperar ya que únicamente tenemos que realizar la multiplicación de un vector por una matriz sobre le cuerpo F2. Ahora, realizamos en primer lugar la descodificación sin introducir errores: Para el código de Goppa C1, se han necesitado 50,95 segundos Para el código de Goppa C2, se han necesitado 21,19 segundos Para el código de Goppa C3, se han necesitado 2,12 segundos Por último, introducimos la máxima cantidad de errores posible sobre cada mensaje codificado, es decir, 119, 27 y 50 respectivamente y ejecutamos la función de descodificación: Para el código de Goppa C1, se han necesitado 56,83 segundos Para el código de Goppa C2, se han necesitado 21,53 segundos Para el código de Goppa C3, se han necesitado 2,68 segundos Obviamente los tiempos de descodificación al introducir errores son mayores, ya que es necesario corregirlos. Además, realizando la resta de los tiempos obtenidos para ambos casos, podemos obtener una referencia del tiempo empleado aproximadamente por el algoritmo de Patterson en cada descodificación realizada. Dichos tiempos son 5,88, 0,34 y 0,56 segundos para los códigos C1,C2yC3respectivamente. Vemos que el tiempo de aplicación del algoritmo de Patterson es muy pequeño para los códigos C2 yC3en comparación con el de C1, debido al incremento del cuerpo finito empleado. 8.2. Códigos de producto de matrices Para la construcción de estos códigos mediante el empleo de la clase MatrixProductCodes vamos a realizar la construcción de seis de ellos empleando parámetros parecidos a los de Goppa, y realizando su construcción mediante el empleo de códigos de Goppa y también Reed-Solomon generalizados. Para construir los códigos de producto de matrices con Goppa separamos al igual que antes la ejecución necesaria para obtener los polinomios irreducibles que empleamos para construir los códigos de Goppa: Para el cálculo de los polinomios irreducibles de grado 40 y 70 sobre el cuerpo F211 se han necesitado 25,79 segundos. 136 CAPÍTULO 8. PRUEBAS DEL CÓDIGO IMPLEMENTADO han necesitado 21694,64 segundos, es decir, 6 horas, 1 minuto y 34,65 segundos. Para realizar el ataque al criptosistema de McEliece construido a partir de un código Reed-Solomon generalizado con longitud n=128 y dimensión k=64, se han necesitado 1045,59 segundos, es decir, 17 minutos y 25 segundos. Para realizar el ataque al criptosistema de McEliece construido a partir de un código Reed-Solomon generalizado con longitud n=64 y dimensión k=32, se han necesitado 55,27 segundos. En estos resultados podemos apreciar como se va incrementando rapidamente el tiempo, a medida que vamos incrementando los parámetros nykdel código empleado, debido a la complejidad que hemos visto que presenta el ataque, O(k2n3+k3n2). Por último indicamos que para la medición de todos los tiempos de ejecución realizados a lo largo del capítulo se ha empleado un procesador intelCorei7−4712MQ que funciona a una velocidad de hasta 2,30 GHz pero cuyo rendimiento en el cálculo de operaciones de Sage esta limitado al 20% de su capacidad para cada proceso ejecutado. Debido a esto, podemos observar que aunque hayamos obtenido algunos tiempos elevados, si empleáramos otro procesador mas potente que funcionará con el 100% de rendimiento o incluso emplearemos un conjunto de procesadores que trabajaran interconectados, los resultados se reducirían notablemente, posibilitando por ejemplo la realización del ataque por filtración a criptosistemas con parámetros cuyo tamaño se emplea actualmente. Capítulo 9 Conclusiones En este proyecto nos hemos centrado en realizar un estudio tanto teórico como práctico de una serie de códigos, los cuales empleamos después para realizar la construcción del criptosistema de McEliece. En adicción, realizamos un posible ataque contra el criptosistema de McEliece construido a partir de los códigos Reed-Solomon generalizados y por último, realizamos una fase de investigación mediante la cual somos capaces de crear un nuevo método que nos permite reducir el tamaño de las claves del criptosistema de McElice. Debido al desarrollo del proyecto, se ha despertado un gran interés en el ámbi- to relacionado con la seguridad de la información de las comunicaciones debido a su gran importancia, ya que actualmente cualquier persona realiza comunicaciones diarias empleando algún dispositivo electrónico, las cuales contienen en ocasiones información muy personal, donde la mayoría desconoce la seguridad de estas comunicaciones. Con el he tenido la oportunidad de poner en práctica los conocimientos adquiridos a lo largo de la carrera relacionados principalmente con la teoría de grupos, seguridad informática y manejo de distintos lenguajes de programación. También se realizó una pequeña introducción el segundo año de la carrera a la teoría de códigos, aunque los conocimientos adquiridos mediante la asignatura eran mucho mas elementales que los necesarios para el desarrollo del proyecto. En adicción, ha permitido adquirir el aprendizaje necesario tanto del lenguaje de programación de Sage como el de Python, que no se habían estudiado a lo largo de la carrera, así como un incremento en el aprendizaje del lenguaje de edición de textos latex, lo cual era un objetivo que intentábamos alcanzar una vez finalizado el presente documento. Si tenemos en cuenta el resto de objetivos prefijados en la sección 1.2 a conseguir tras la realización del proyecto, podemos observar que se han alcanzado prácticamente en su totalidad. 137 138 CAPÍTULO 9. CONCLUSIONES En primer lugar, hemos realizado tanto un estudio teórico como práctico de los códigos lineales, códigos Reed-Solomon y Reed-Solomon generalizados, códigos cíclicos, códigos punteados y recortados a lo largo de todo el capítulo 3. Después, también se realiza un estudio tanto de los códigos de Goppa como de los códigos de producto de matrices y para ambos se realiza una implementación completa empleando Sage que nos permite realizar su construcción, así como las operaciones elementales empleando dichos códigos. También se estudia detalladamente el criptosistema de McEliece de forma teórica en el capítulo 5, para el cual hacemos relevancia a la elevada seguridad que parece presentar dicho criptosistema ya que, a pesar de ser uno de los mas antiguos sigue siendo resistente la versión original que emplea códigos de Goppa a la gran cantidad de critoanalisis que se le han intentado realizar, principalmente en estos últimos años debido a la gran importancia adquirida por ser un sistema resistente al algoritmo de Shor. En relación con el criptosistema de McEliece, también se implementa un criptoanalisis cuando se realiza su construcción empleando códigos Reed-Solomon y Reed- Solomon generalizados, a partir de lo cual se intenta mostrar que aunque dicho criptosistema parece ser seguro frente ataques realizados por un ordenador cuántico, debemos tener especial cuidado en realizar su construcción empleando códigos que le permitan ser seguro frente a los distintos ataques conocidos actualmente contra ciertos tipos de códigos. En adicción, no se ha realizado un análisis de seguridad mediante el empleo de otros códigos, frente a los dos tipos de ataques posibles contra el criptosistema que vimos brevemente en la sección 5.7. Para finalizar, volvemos a destacar el nuevo criptosistema de McEliece desarrollado, que nos permite reducir el tamaño de las claves del criptosistema manteniendo en un principio la seguridad que presentaba mediante el empleo de los códigos de Goppa. 9.1. Trabajo futuro Para terminar el capítulo, mostramos a continuación una serie de aspectos que serían convenientes realizar mas adelante para completar aún mas el proyecto desarrollado: Realizar un estudio profundo acerca de la seguridad del criptosistema de McE- liece, así como de los posibles ataques existentes para distintas variantes del criptosistema, que nos permitan adquirir una serie de conocimientos a partir de los cuales podamos identificar cuales son las mayores debilidades del criptosistema. 9.1. TRABAJO FUTURO 139 Incrementar la implementación desarrollada para la construcción de los códigos de Goppa de forma que no se restrinjan dichos códigos únicamente a los construidos sobre cuerpos binarios. Para ello, solo sería necesario implementar un algoritmo de descodificación eficiente válido para todos ellos, como por ejemplo el algortimo de Berlekamp-Massey o el de Euclides extendido que se pueden analizar en [24] [26] y [23] [25] respectivamente. También se podría crear un fichero que contenga una gran cantidad de polinomios irreducibles cuyo grado coincida con los parámetros mas empleados y de elevado tamaño, de forma que a la hora de generar la construcción de un código de Goppa se reduzca su tiempo de obtención, al tener ya calculados previamente los polinomios irreducibles. Obviamente, sería necesario ir actualizando los polinomios irreducibles almacenados en el fichero para no generar siempre construcciones de códigos de Goppa mediante el mismo polinomio. Esto en principio, volvería a suponer el incremento del tiempo para la generación de los códigos, sin embargo podemos observar que dicho proceso se podría realizar en instantes de tiempo en que no se este empleando el procesador, de forma que no suponga un incremento del tiempo de generación de las claves. Con respecto a la nueva versión del criptosistema de McEliece presentada, para los códigos de producto de matrices podemos observar que la matriz Ay los códigos se deben encontrar en el mismo cuerpo, entonces solo es posible realizar la construcción del nuevo criptosistema actualmente empleando la matriz correspondiente a la construcción de Plotkin. Por tanto, aunque para esta construcción vimos que se reducía notablemente el tamaño de las claves del criptosistema, una vez implementado el algoritmo de descodificación de los códigos de Goppa sobre cualquier cuerpo, habría que analizar la reducción de las claves ocasionada empleando códigos de producto de matrices que empleen una matriz Ade mayor tamaño, donde se prevee que dicha reducción será aún mayor que para la construcción de Plotkin, aunque habría que realizar un análisis acerca de si merece la pena incrementar mas la reducción de las claves, ya que al tener que emplear códigos de Goppa no binarios, se pierde la mitad de la capacidad correctora del código como vimos en la proposición 4.6. Otro aspecto importante que faltaría por analizar, es si la seguridad del criptosistema de McEliece se ha visto mermada mediante el empleo del nuevo método desarrollado. Para ello, habría que realizar un estudio comparativo acerca de todos los posibles ataques conocidos hasta el momento contra el criptosistema de McEliece, así como los posibles ataques nuevos que podrían surgir al criptosistema debido al empleo de los códigos de producto de matrices. 140 CAPÍTULO 9. CONCLUSIONES Bibliografía [1] DAVID MORENO CENTENO,Análisis de la teoría de códigos: McEliece y una nueva versión, Trabajo fin de grado matemáticas 2019. [2] SHAMIR A, A polynomial time algoritm for breaking the basic Merckle-Hellman cryptosystems, IEEE trans on inform 1984. [3] MERKLE, R. C., A digital signature based on a conventional encryption function, Conference on the Theory and Application of Cryptographic Techniques 1987. [4] NICOLAS COURTOIS, ALEXANDER KLIMOV, JACQUES PATARIN Y ADI SHAMIR, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in cryptology—EUROCRYPT 2000. [5] JUSTESEN JØRN, HØHOLDT TOM., A Course in Error-Correcting Codes, European Mathematical Society Publishing House 2004. [6] YUAN XING LI, ROBERT H. DENG,AND XIN MEI WANG,On the equivalence of McElieces and Niederreiters public-key cryptosystems, IEEE Transactions on Information Theory 1994. [7] NICOLAS COURTOIS, MATTHIEU FINIASZ,AND NICOLAS SENDRIER,How to achie- ve a mceliece-based digital signature scheme, Advances in Cryptology, ASIACRYPT 2001. [8] V. M. SIDELNIKOV AND S. O. SHESTAKOV,On the insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Math. Appl 1992. [9] FAUGÈRE, J., GAUTHIER-UMANA, V., OTMANI, A., PERRET, L., TILLICH, J., A distinguisher for high rate McEliece cryptosystems, Proceedings IEEE Information Theory Workshop 2011. [10] P. GABORIT,Shorter keys for code based cryptography, International Workshop on Coding and Cryptography 2005. 141 142 BIBLIOGRAFÍA [11] SAN LING,On the algebraic structure of quasi-cyclic codes .I. Finite fields, Proceedings IEEE Information Theory Workshop 2001. [12] T.A. GULLIVER, V.K. BHARGAVA,A binary quasi-cyclic code, Appl. Math. Lett. 1995. [13] KRISTINE LALLY Y PATRICK FITZPATRICK,Algebraic structure of quasicyclic codes, Workshop on Coding and Cryptography 1999. [14] JACQUES STERN,A method for finding codewords of small weight, Lecture Notes in Computer Science 1989. [15] A. OTMANI, J.P. TILLICH,AND L. DALLOT,Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, preprint 2008. [16] T. P. BERGER, P. CAYREL, P GABORIT,AND A. OTMANI,Reducing Key Length of the McEliece Cryptosystem, AFRICACRYPT 2009. [17] J.-C. FAUGÈRE, A. OTMANI, L. PERRET,AND J.-P. TILLICH,Algebraic cryptanalysis of McEliece variants with compact keys, Proc. Adv. Cryptol. 2010. [18] V. G. UMAÑA AND G. LEANDER,Practical key recovery attacks on two McEliece variants, Association Cryptol. Res. (IACR) 2009. [19] J.-C. FAUGÈRE, A. OTMANI, L. PERRET, F. DE PORTZAMPARC,AND J.-P. TILLICH,Structural cryptanalysis of McEliece schemes with compact keys, Designs codes Cryptography 2016. [20] J.-C. FAUGÈRE, A. OTMANI, L. PERRET, F. DE PORTZAMPARC,AND J.-P. TILLICH,Folding alternant and Goppa Codes with non-trivial automorphism groups, IEEE Trans. Inf. Theory 2016. [21] BLACKMORE, T., NORTON, G.H., Matrix-product codes over Fq, Appl. Algebra Eng. Commun. Comput 2001. [22] MACWILLIAMS, F.J., SLOANE, N.J.A.,The Theory of Error-Correcting Codes, North- Holland Mathematical Library 1977. [23] J. GATHEN,AND J. GERHARD,Modern computer algebra, Cambridge University 2013. [24] —, Algebraic Coding Theory, New York: McGraw-Hill 1968. [25] SHOUP AND, VICTOR,A Computational Introduction to Number Theory and Algebra, Cambridge University 2008. BIBLIOGRAFÍA 143 [26] E. R. BERLEKAMP,Goppa codes, IEEE Trans. Inform. Theory 1973. [27] R. PELLIKAAN, X. WU, S. BULYGIN AND, R. JURRIUS,Codes, Cryptology and Curves with computer algebra, Cambridge University 2018. [28] R. THOMAS,How sage helps to implement Goppa codes and McEliece PKCSs, 2011. [29] D. J. BERNSTEIN,List decoding for binary Goppa codes, Third International Workshop 2011. [30] Post-Quantum Cryptography | CSRC, Computer Security division, Information Technology Laboratory, National Institute of Standars and Technology,. URL: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography [31] Página web Indeed URL: https://www.indeed.es/salaries/ [32] A. COUVREUR, P. GABORIT, V. GAUTHIER-UMAÑA, A. OTMANI Y, J-P. TILLICH, Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes, 2014. [33] I. MÁRQUEZ-CORBELLA, N. SENDRIER Y,M. FINIASZ,Attack against GRS codes, France université numérique, FUN-MOOC 2013. URL: https://www.fun-mooc.fr/courses/course-v1:inria+41006+ archiveouvert/about [34] A. COUVREUR, A. OTMANI Y, J-P. TILLICH,POLYNOMIAL TIME ATTACK ON WILD MCELIECE OVER QUADRATIC EXTENSIONS, IEEE Transactions on Information Theory 2016. [35] C. MUNUERA Y, J. TENA,Codificación de la Información, Universidad de Valladolid 1997. [36] P. J. LEE Y, E. F. BRICKELL,An observation on the security of McEliece’s public-key cryptosystem, Advances in cryptography- EUROCRYPT 88 1988. 144 BIBLIOGRAFÍA Apéndice A Contenido del CD El CD con formato -R que se encuentra junto con el presente documento contiene como podemos ver en la imagen A.1 la memoria del mismo en formato .pd f así como una carpeta llamada ”codigo Sage” que contiene todo el código que hemos implementado para la realización del proyecto. Imagen A.1: Contenido global del CD Después, si entramos dentro de la carpeta ”codigo Sage” se encuentran todos los ficheros que hemos empleado en el proyecto. Por un lado, tenemos los ficheros con formato .ipynb que podemos ver en la imagen A.2, los cuales contienen todo el código implementado y comentado, así como un conjunto de pruebas y ejemplos realizados para validar su correcto funcionamiento. 145