Criptografía post-cuántica: Análisis de McEliece y una nueva versión con MPC
Abstract
Grado en Matemáticas
Full text
Facultad de Ciencias Trabajo Fin de Grado Grado en Matemáticas Criptografía Post-cuántica: Análisis de McEliece y una nueva versión con MPC Autor: David Moreno Centeno Tutor: Diego Ruano Benito
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. También, mostramos el método empleado por Gaborit para intentar eliminar la principal desventaja del criptosistema de McEliece preservando la seguridad, el gran tamaño de las claves. 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. Also, it is shown the method used by Gaborit to try to eliminate the main disadvantage of the McEliece cryptosystem while preserving security,the large size of the keys. 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.................................... 5 1.2. Objetivos..................................... 5 2. Teoría de los códigos lineales 7 2.1. Introducción................................... 7 2.2. Descodificación ................................. 14 2.3. Códigodual ................................... 18 3. Códigos RS y GRS 21 3.1. Introducción................................... 21 3.2. Matriz generatriz y de control . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3. Codificación y descodificación . . . . . . . . . . . . . . . . . . . . . . . . . 24 4. Códigos de Goppa 31 4.1. Introducción................................... 31 4.2. Descodificación ................................. 34 4.2.1. Algoritmo de Patterson . . . . . . . . . . . . . . . . . . . . . . . . 36 5. McEliece y Niederreiter 41 5.1. Criptosistema de McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.1.1. Introducción............................... 41 5.1.2. Descripción del criptosistema . . . . . . . . . . . . . . . . . . . . . 42 5.1.3. Cifrado y descifrado del McEliece . . . . . . . . . . . . . . . . . . 42 5.1.4. Ventajas y desventajas del criptosistema . . . . . . . . . . . . . . . 47 5.2. Criptosistema Niederreiter . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2.1. Introducción............................... 48 5.2.2. Descripción del criptosistema . . . . . . . . . . . . . . . . . . . . . 48 5.2.3. Cifrado y descifrado del Niederreiter . . . . . . . . . . . . . . . . 49 5.3. Posiblesataques................................. 50 VII
VIII ÍNDICE GENERAL 6. Ataque contra códigos GRS 53 6.1. Introducción................................... 53 6.2. Ataque por filtración a códigos GRS . . . . . . . . . . . . . . . . . . . . . 62 6.2.1. Ataqueestándar ............................ 62 6.2.2. Ataque incompleto al criptosistema de McEliece . . . . . . . . . . 67 6.2.3. Ataque correcto al criptosistema de McEliece . . . . . . . . . . . . 68 7. Reducción de claves de Gaborit 75 7.1. Introducción................................... 75 7.2. Método de reducción de claves . . . . . . . . . . . . . . . . . . . . . . . . 78 7.2.1. Generación de claves . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2.2. Cifrado.................................. 80 7.2.3. Descifrado................................ 80 7.2.4. Tipo de códigos sugeridos . . . . . . . . . . . . . . . . . . . . . . . 81 7.3. Criptoanálisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8. Códigos de productos de matrices 85 8.1. Introducción................................... 85 8.2. Descodificación ................................. 95 9. McEliece con MPC 105 9.1. Introducción...................................105 9.2. El nuevo criptosistema de McEliece . . . . . . . . . . . . . . . . . . . . . . 106 9.2.1. Generacion de claves . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.2.2. Cifrado..................................107 9.2.3. Descifrado................................108 Bibliografía 113
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 permitan 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 obtenga 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 2. TEORÍA DE LOS CÓDIGOS LINEALES In: C=codes.random_linear_code(GF(2),7,4); Definición 2.4. Una matriz generatriz Gde un código lineal [n,k], es una matriz k×n cuyas filas son vectores linealmente independientes del código lineal que además lo generan, es decir, dichas filas forman una base del código lineal como espacio vectorial. Nota 2.5. Podemos observar de la definición 2.4 que un código lineal C, al igual que puede tener distintas bases, también puede tener distintas matrices generatrices, aunque todas ellas son semejantes, y por tanto, existirá una matriz invertible que nos permita obtener una matriz generatriz a partir de la otra. Aun así, hay que destacar que distintas matrices generatrices de un código generan distintas codificaciones, ya que C={aG |a∈Fk q}. Nota 2.6. También podemos relacionar a cada matriz generatriz Gde un código Ccon una aplicación lineal inyectiva, f, que llamaremos aplicación de codificación: f:Fk q−→ C⊂Fn q Definición 2.7. Dados dos códigos lineales C1yC2de igual longitud, n, sobre Fq, decimos que son códigos equivalentes, si existe una permutación πdel conjunto de indices {1, · · · ,n}de forma que C2={π(c)|c∈C1} Definición 2.8. Dado un código lineal C, diremos que es un código sistemático si y solo si su matriz generatriz Ges de la forma G= (Ik|A), siendo Ikla matriz identidad de tamaño k×k. Nota 2.9. La matriz generatriz de un código sistemático se llama matriz generatriz en forma estándar. Cuando el código es sistemático, al realizar la codificación de un vector se obtiene como resultado una palabra del código formada por el vector sin codificar seguido, hasta completar la longitud de la palabra del código, de coordenadas llamadas de control. Las palabras de un código lineal [n,k]en forma sistemática tienen ksímbolos de información y n−ksímbolos redundantes, los cuales permiten validar que los ksímbolos de información obtenidos son correctos y por tanto, no tienen errores. Esto facilita la obtención de la información de forma correcta a pesar de que dicha información, bien durante su transmisión a través del canal de comunicación o cualquier otra circunstancia, haya sufrido una cierta cantidad de errores. Proposición 2.10. Dado un código lineal, C, de parámetros [n,k], es equivalente a un único código sistemático.
2.1. INTRODUCCIÓN 9 Demostración. Sea Guna matriz generatriz del código de tamaño k×n. Entonces G posee kcolumnas linealmente independientes. Realizando una permutación de forma que tengamos las kprimeras columnas linealmente independientes obtenemos un código equivalente que tiene como matriz generatriz G0= (A|B), siendo Auna matriz regular. Ahora aplicando el método de Gauss podemos transformar la matriz Aen la matriz identidad Iky por tanto, obtenemos un código sistemático como queríamos. Ademas, como la forma escalonada reducida de una matriz es única y las matrices generatrices del código Cson equivalentes, entonces tenemos que el código sistemático debe ser único. Definición 2.11. Una matriz de control, H, de un código lineal [n,k],C, es una matriz (n−k)×npara la cual se cumple que c∈C⇔Hct=0, ∀c∈Fn q. Debido a ello, es claro que si Ges la matriz generatriz y Hes la matriz de control de un código lineal Centonces tenemos que GHt=HGt=0 Ejemplo 2.2. Continuando con el ejemplo 2.1, utilizando la sentencia: In: G=C.generator_matrix() Sagemath nos proporciona una matriz generatriz de dicho código, cuyas filas hacen referencia a una base del código: G= 0010011 0011101 1101100 1001011 La aplicación lineal asociada a esta matriz generatriz viene definida de la siguiente forma: f:F4 2−→ C⊂F7 2 a= (a1,a2,a3,a4)7−→ c= (a3+a4,a3,a1+a2,a2+a3+a4,a2+a3,a1+a4,a1+a2+a4) Según lo que hemos visto en la proposición 2.10, existe un código equivalente al de partida cuya matriz generatriz se encuentra en forma estándar, para su obtención empleamos el siguiente código en Sagemath: In: G ' =C.systematic_generator_matrix() y obtenemos la matriz, G0, correspondiente a la matriz generatriz en forma estándar:
10 CAPÍTULO 2. TEORÍA DE LOS CÓDIGOS LINEALES G0= 1000101 0100111 0010011 0001110 La aplicación lineal asociada a esta matriz generatriz en forma estándar viene definida de la siguiente forma: f:F4 2−→ C⊂F7 2 a= (a1,a2,a3,a4)7−→ c= (a1,a2,a3,a4,a1+a2+a4,a2+a3+a4,a1+a2+a3) Esto es debido a que cualquier palabra de código, c, se forma multiplicando el bloque de mensaje por la matriz generatriz: aG =c∈C. En adicción, podemos observar que el código generado a partir de la matriz G0se corresponde con el código de Hamming [7,4]. Dichos códigos fueron creados por Richard Hamming en el siglo XX, los cuales se caracterizan por ser de los primeros en la teoría de codificación y por ser capaces de detectar y corregir un único error pero no de detectar ni siquiera dos errores. En cuanto al cálculo de la matriz de control según lo visto en la definición 2.11, calculamos la matriz tal que tras multiplicar la matriz generatriz por la matriz calculada obtengamos la matriz nula y entonces la matriz de control se corresponde con la traspuesta de la matriz calculada. El código empleado para ello es: In: H=G.right_kernel_matrix(); y la matriz de control, H, obtenida para el código Ces: H= 1001011 0100111 0011101 Vimos que los códigos lineales eran capaces de corregir cierta cantidad de errores, pero para saber la cantidad de errores que es capaz un código lineal de corregir es necesario introducir los conceptos de peso y distancia mínima del código. Dichos conceptos también fueron descubiertos por Richard Hamming, por lo que son conocidos añadiendo su nombre.
2.1. INTRODUCCIÓN 11 Definición 2.12. El peso de Hamming de un vector c= (c1, ..., cn)∈Fn q, denotado por ω(c), es el numero de coordenadas no nulas del vector, es decir, ω(c) = #{i|ci6= 0, 1 ≤i≤n}. Nota 2.13. Una vez definido el peso de Hamming de un vector, podemos deducir que el peso mínimo de un código lineal Csera el mínimo de los pesos de Hamming de las palabras del código, es decir, ω(C) = min{ω(c)|c∈Cr{0}} Definición 2.14. La distancia de Hamming entre dos vectores a,b∈Fn q, denotado por d(a,b), es el número de coordenadas donde ambos vectores no coinciden, es decir, d(a,b) = #{i|ai6=bi, 1 ≤i≤n}. Nota 2.15. Es fácil comprobar que la distancia de Hamming es una distancia y por tan- to el espacio vectorial Fn qes un espacio métrico con dicha distancia. También podemos observar que ω(c) = d(0, c)∀c∈Fn q. De igual forma que ocurría con el peso, la distancia mínima de un código lineal C sera la mínima distancia de Hamming entre cualquier par de palabras del código distintas. Además, para los códigos lineales, existe una relación entre la distancia mínima y peso mínimo de un código: Proposición 2.16. Dado un código lineal [n,k], C, la distancia mínima de C es igual a el peso mínimo de C. Demostración. Sea c∈C, una palabra de código de peso mínimo. Entonces tenemos que ω(c) = d(0, c), y como 0 ∈Cpor ser un subespacio vectorial, deducimos que d(C)≤ω(C). Por otro lado, sean a,b∈C, palabras del código de distancia mínima. Tenemos que d(a,b) = d(a−b,0) = d(0, a−b) = ω(a−b)y como a−b∈Cdebido a que Ces un subespacio vectorial, entonces tenemos que ω(C)≤d(C)y por tanto la igualdad es cierta. Según la definición de distancia mínima de un código que hemos dado, tenemos que comparar cada par de palabras del código o el peso de cada palabra del código. Es- to en general es difícil de realizar, ya que cuando tengamos códigos con gran cantidad de palabras hay que realizar multitud de comprobaciones. A pesar de ello, se puede emplear la matriz de control del código, la cual nos facilita el trabajo como podemos observar a partir de la siguiente proposición: Proposición 2.17. Dado un código lineal, C, con matriz de control, H, y distancia mínima d. Si r es un numero entero positivo, tenemos que d >r⇔cualquier combinación de r columnas de la matriz de control H son linealmente independientes.
12 CAPÍTULO 2. TEORÍA DE LOS CÓDIGOS LINEALES Demostración. ⇒)Para ello veamos el contrarreciproco: Si existen rcolumnas linealmente dependientes en la matriz de control, entonces existirá un vector c, con coordenadas que proporcionan dicha combinación lineal y por tanto, tenemos que Hct=0, es decir, c∈C, y como ω(c)≤rentonces d≤r ⇐)Ahora si partimos de que cualquier combinación de rcolumnas de Hson independientes, entonces ningún vector cpuede tener coordenadas que generen una combinación lineal a partir de solamente esas columnas. Por tanto, para ese caso tendríamos que Hct6=0 y entonces c/∈C. Debido a esto, si c∈C, necesariamente ω(c)>rcomo queríamos. Corolario 2.18. Dado un código lineal C, con matriz de control H. La mínima distancia de C, d(C), es igual al mínimo numero de columnas igualmente dependientes de H. La proposición anterior también nos proporciona una cota superior para la distancia mínima de cualquier código lineal, conocida como cota de Singleton: Corolario 2.19. (cota de Singleton) Dado un código lineal [n,k], C, cuya mínima distancia es d, se cumple que d ≤n−k+1 Demostración. Sea Hla matriz de control de C. Entonces el rango de Hes n−ky por tanto n−k+1 columnas de Hson linealmente dependientes y por la proposición anterior obtenemos 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. Nota 2.20. A partir de los conceptos de distancia y peso mínimo definidos, los cuales son válidos para cualquier tipo de código, podemos observar que estos son los que nos permiten detectar cierta cantidad de errores, siendo 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. En esta situación, si obtenemos una palabra con menos de derrores, esta no pertenecerá al código que estamos empleando y por tanto podremos percatarnos que en esa palabra hay errores. Además, si dicho error tiene peso suficientemente pequeño como para que exista una única palabra del código con menor distancia de Hamming a la palabra obtenida, seremos capaces de identificar el error, siendo la única palabra con menor distancia de Hamming la palabra sin errores.
2.1. INTRODUCCIÓN 13 Por otro lado, si el error tiene peso ω(e)≥d, entonces una palabra de código, c, con dicho error, puede dar lugar a otra palabra del código, c0=c+e, y por tanto provoca que en ocasiones no nos percatemos del error producido. Debido a esto, 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: Definición 2.21. 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 2.22. Un código [n,k]es corrector de t errores ⇔t<d 2, siendo d la distancia mínima de dicho código. Demostración. ⇒)Realizaremos una reducción al absurdo: Supongamos que t≥d 2. Tomamos una palabra del código, c, tal que ω(c) = d. Ahora cambiamos [d 2]posiciones no nulas a nulas en cobteniendo y. Se cumple entonces que ω(y) = d(0, y)≤d−[d 2]≤t yω(y−c) = d(c,y)≤[d 2]≤t. Como el código es corrector de terrores entonces se cumple por definición que para cualquier par de palabras de código distintas, a los que introducimos errores de peso menor que tdeben seguir siendo distintas. Por ello, llegamos a contradicción, ya que 0 y cpertenecen al código y se cumple que 0+y=c+ (y−c). ⇐)Realizamos de nuevo otra reducción al absurdo: Supongamos que t<d 2y que el código no es corrector de terrores, es decir, existen dos palabras de código, ayb, con errores, eayeb, ambos de peso menor que t, tal que a+ea=b+eb. Entonces se cumple que a−b=eb−eay por tanto ω(a−b) = ω(eb−ea)≤2t<d. Por ello, llegamos a una contradicción al ser a−botra palabra de código cuyo peso es inferior al peso mínimo del código. Ejemplo 2.3. Siguiendo con el ejemplo 2.2, Sagemath tiene ya definida la función hamming_weight(), que proporciona el peso de Hamming de una palabra de código determinada y minimum_distance(), que proporciona la mínima distancia del código. Empleamos dicho código:
14 CAPÍTULO 2. TEORÍA DE LOS CÓDIGOS LINEALES In: C.minimum_distance() Out: 3 Por tanto obtenemos que el peso mínimo del código es, ω(C) = 3, el cual también podíamos obtener observando en la matriz de control que a partir de la suma de la cuarta y quinta columnas obtenemos la sexta. Por la cota de Singleton obtenemos que 3 ≤7−4+1=4 y por tanto no es un código MDS. Además, es claro que nuestro código Ces capaz de corregir un único error, ya que por el teorema 2.22, los tque lo cumplen son 0 y 1. Una vez que sabemos la distancia mínima y capacidad correctora de un código lineal, vamos a ver una forma de corregir dichos errores mas eficiente que la introducida en la nota 2.20, lo cual se debe a la estructura algebraica que presentan los códigos lineales. 2.2. Descodificación En primer lugar vamos a introducir el concepto de síndrome de un código lineal, el cual, proporcionará información esencial sobre el error producido en una palabra de código transmitida. Definición 2.23. Dado un código lineal [n,k],C, con matriz de control Hey∈Fn q. Diremos que el síndrome de y, denotado por s(y), viene dado por el vector obtenido de la multiplicación de la matriz de control con y, es decir, s(y) = Hyt De esta definición, vemos que s(y)∈Fn−k q. También, que el síndrome de yserá el vector nulo si y solo si y∈C. Por ello, las palabras de código no aportan ninguna información al síndrome, pero si definimos el síndrome como la siguiente aplicación: s:Fn q−→ Fn−k q y7−→ Hyt Podemos observar que es una aplicación lineal al estar definido como el producto de una matriz por un vector. Por ello, si tenemos una palabra del código, c∈C, con
2.2. DESCODIFICACIÓN 15 una cantidad de errores, donde ees el vector de errores, la palabra resultante, y=c+e, tiene el mismo síndrome que el vector de errores ya que s(y) = Hyt=s(c+e) = H(c+e)t=Hct+Het=Het=s(e). Esto nos facilita la corrección de errores en el proceso de descodificación como podemos ver a continuación. Definición 2.24. Dado un código lineal [n,k],C, y un elemento a∈Fn q. Llamamos cogrupo que contiene a a, al conjunto dado por: a+C={a+c|c∈C} Proposición 2.25. Dos elementos de Fn qestán en el mismo cogrupo si y solo si tienen el mismo síndrome. Demostración. ⇒)Sean x,ypertenecientes al mismo cogrupo (a+C). Entonces x=a+ccon c∈Cyy=a+c0con c0∈C. Por tanto ambas palabras tendrán el mismo síndrome ya que si Hes la matriz de control del código, tenemos que s(x) = Hxt=H(a+c)t= Hat=H(a+c0)t=s(y) ⇐)Si x,ytienen el mismo síndrome se cumple que Hxt=Hyty entonces H(x− y)t=0, lo cual se cumple si y solo si x−y∈C. Por tanto, como x=x+0 e y= x+ (y−x), se cumple que ambas están en el mismo cogrupo. Definición 2.26. Llamaremos líder de un cogrupo al elemento de menor peso dentro de dicho subconjunto, el cual debe ser único. Por tanto, es posible que algunos cogrupos no posean líder. A partir de esto, tenemos un método para la corrección de errores: Si partimos de una palabra del código, c, la cual ha sufrido cierta cantidad de errores convirtiéndose en el vector y=c+e, es claro que tanto ycomo epertenecen al mismo cogrupo y por ello tienen el mismo síndrome. Entonces calculamos el síndrome de yy si posee un líder, se podrá realizar la descodificación restando a yel líder del cogrupo, que será el error cometido. Si no posee líder no se podrá realizar la descodificación. Proposición 2.27. Cada cogrupo tiene como máximo un elemento de peso menor o igual que t. Demostración. Realizamos una reducción al absurdo, supongamos que existen x,y, pertenecientes al mismo cogrupo, distintas, no nulas y con ω(x),ω(y)≤t. Entonces, sabemos que x−y∈Cy como ω(x−y)≤2t, tendríamos que existe una palabra
16 CAPÍTULO 2. TEORÍA DE LOS CÓDIGOS LINEALES del código no nula cuyo peso es inferior a la distancia mínima del código, lo cual es absurdo. Proposición 2.28. Dado un código lineal [n,k], diremos que corrige t errores si y solo si todas las palabras de peso menor o igual que t son lideres de subconjuntos. La demostración de la proposición 2.28 se puede encontrar en [5]. Ejemplo 2.4. Siguiendo con el ejemplo 2.3, vamos a emplear el código lineal [7,4] obtenido en forma sistemática, el cual, vimos que permite la corrección de un error. Ahora vamos a obtener las 24=16 posibles palabras del código usando la siguiente función de Sagemath: In: C.list() Por tanto, el código Cesta constituido por: C={(0,0,0,0,0,0,0),(1,0, 0,0,0,1,1),(0,1,0,0, 1,0,1),(1,1,0,0,1,1,0), (0,0,1,0,1,1,0),(1,0, 1,0,1,0,1),(0,1,1,0, 0,1,1),(1,1,1,0,0,0,0), (0,0,0,1,1,1,1),(1,0, 0,1,1,0,0),(0,1,0,1, 0,1,0),(1,1,0,1,0,0,1), (0,0,1,1,0,0,1),(1,0, 1,1,0,1,0),(0,1,1,1, 1,0,0),(1,1,1,1,1,1,1)} Como el síndrome pertenece a el cuerpo finito F3 2, hay un total de 23=8 síndromes. Emplearemos una función generada en Sagemath que nos proporcione, si existe, el líder de cada síndrome, para ello emplearemos la función syndrome() ya implementada en los códigos lineales en Sagemath, la cual proporciona el síndrome de un vector dado como parámetro: In: def lidersindrome(C): q=C.base_ring().cardinality(); n=C.random_element().length(); k=C.dimension(); j=q^(n-k); #tamaño de la lista de los posibles sindromes lider=[(n+1)for iin [1..j]]; peso=[("")for iin [1..j]]; for iin VectorSpace(IntegerModRing(q),n).list(): s=C.syndrome(i); posicion=0; for jin range(n-k): posicion=posicion+ZZ(s[j])*q**(n-k-1-j); if peso[posicion]>i.hamming_weight(): lider[posicion]=i;
2.2. DESCODIFICACIÓN 17 peso[posicion]=i.hamming_weight(); elif peso[posicion]==i.hamming_weight(): lider[posicion]="null"; for hin lider: print ('sindrome: ', C.syndrome(h), 'lider: ', h); Para nuestro ejemplo podemos observar en la tabla 2.1 los siguientes lideres para cada posible síndrome obtenidos a partir de la función lidersindrome() creada. Síndrome Líder (0,0,0) (0, 0,0,0,0,0,0) (0,0,1) (0, 0,0,1,0,0,0) (0,1,0) (0, 1,0,0,0,0,0) (0,1,1) (0, 0,0,0,0,1,0) (1,0,0) (1, 0,0,0,0,0,0) (1,0,1) (0, 0,0,0,1,0,0) (1,1,0) (0, 0,1,0,0,0,0) (1,1,1) (0, 0,0,0,0,0,1) Tabla 2.1: Lideres y sindromes. Si introducimos ahora un error en una de las palabras del código C, podemos corregir dicho error según lo visto en la proposición 2.28 ya que el código tiene una capacidad correctora de t=1. Por ejemplo, tomamos la palabra c= (1,0,1, 1,0,1,0)y añadimos un error en la primera coordenada obteniendo y= (0,0, 1,1,0,1,0). Ahora obtenemos el síndrome de y, el cual es, s(y) = (1,0,0). Mirando ahora la tabla 2.1 tenemos que el líder de ese síndrome es (1,0,0,0, 0,0,0). el cual coincide con el error introducido. A partir de este método es posible realizar la descodificación de cualquier código lineal. Ademas es mas eficiente que la descodificación de códigos vista en la nota 2.20, ya que en lugar de tener que comparar con todas las palabras simplemente hay que buscar el líder del síndrome correspondiente. Sin embargo, podemos observar que este método sigue siendo poco eficiente ya que en cuanto trabajemos con códigos de dimensión y longitud extensa, como tenemos que almacenar un total de qn−ksíndromes y lideres, es necesario emplear una gran cantidad de memoria para su almacenamien- to. Es por esto, que para los códigos que veremos mas adelante, para realizar su descodificación, primero localizaremos las posiciones donde se encuentran los errores y
24 CAPÍTULO 3. CÓDIGOS RS Y GRS 3.2. Matriz generatriz y de control de los códigos Reed- Solomon y Reed-Solomon generalizados Una base para Lknos proporciona una base del código RSk(a)yGRSk(a,b)al ser estos códigos lineales. Si tomamos al igual que antes, {1, x,..., xk−1}como base de Lk, tenemos que la matriz generatriz se obtiene evaluando cada polinomio de la base sobre las coordenadas del vector a(y si se trata del caso generalizado, multiplicando además por la coordenada correspondiente de b), lo cual nos proporciona una fila de la matriz generatriz. Por tanto la 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 Como hemos dicho, si el elemento b∈Fn qes b= (1,..., 1)entonces tenemos que GRSk(a,b) = RSk(a). Por tanto la matriz generatriz de un Reed-Solomon será igual que la matriz generatriz del Reed-Solomon generalizado, tomando en dicha matriz el valor 1 en todas las coordenadas del vector b, es decir, bi=1∀i=1, ..., n. En cuanto a la matriz de control de los códigos de Reed-Solomon y Reed-Solomon generalizados, al ser dichos códigos lineales, se obtiene según lo visto en la definición 2.11 3.3. Codificación y descodificación de los códigos Reed- Solomon y Reed-Solomon generalizados 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 2.4, para cualquier código lineal, realizando simplemente la multiplicación del mensaje por la matriz generatriz, es decir, c=mG.
3.3. CODIFICACIÓN Y DESCODIFICACIÓN 25 Para el proceso de descodificación, suponemos que se envía el bloque de mensaje c∈GRSk(a,b)y recibimos el mensaje y=c+e, donde el peso del vector de error es menor que la mitad de la distancia del código GRSk(a,b),d, es decir, ω(e)≤t=d−1 2. Vamos a explicar un método general válido para cualquier código Reed-Solomon y Reed-Solomon generalizado conocido como algoritmo de Berlekamp-Welch y otro método válido solamente para códigos Reed-Solomon y Reed-Solomon generalizados que sean cíclicos, el cual presenta un coste computacional menor ya que, a pesar de tener que calcular n−ksíndromes, resolver dos sistemas con ω(e)incógnitas cada uno y obtener ω(e)raíces, como veremos a continuación, tenemos que tener en cuenta que siempre el parámetro ω(e)será notablemente inferior al parámetro ny existen técnicas que permiten obtener rápidamente los síndromes cuando trabajamos con códigos cíclicos. En primer lugar explicamos el método de Berlekamp-Welch y en segundo lugar el método exclusivo para códigos Reed-Solomon y Reed-Solomon generalizados cíclicos: 1 Para el primer método, denotamos por I={i∈ {1, ..., n} | bif(ai)6=yi}las posiciones donde existen errores, podemos suponer que |I|=t, y E(x) = ∏i∈I(x− ai)es el polinomio mónico de grado t. Entonces E(ai)bif(ai) = E(ai)yi∀i= 1, ..., n, ya que E(ai) = 0 si i∈Iy si no se puede simplificar la ecuación obteniendo bif(ai) = yi∀i/∈I. Podemos expresar los polinomios como E(x) = xt+At−1xt−1+... +A0yE(x)f(x) = Bt+k−1xt+k−1+... +B0donde Ai,Bj∈Fq son desconocidas ∀i=0, ..., t−1j=0, ..., t+k−1. Por tanto, resolviendo el sistema anterior, formado por necuaciones y 2t+kincógnitas (que tiene solución al ser t<d−1 2) obtendríamos el polinomio E(x)y por tanto las posiciones donde se encuentra el error, junto con su valor tras obtener las raíces de E(x). 2 Para el segundo método, denotamos y= (y1,..., yn)y entonces tenemos y(x) = ynxn−1+... +y2x+y1. Ahora vamos a calcular el síndrome S= (S1, ..., Sn−k) sabiendo que si Hes la matriz de control del código entonces, S=HyT, o lo que es igual al ser un código cíclico, que Si=y(βi) = e(βi)∀i=1, ..., n−k, siendo β un elemento primitivo de Fq. Una vez calculados los valores del síndrome, tenemos que calcular el polinomio localizador de errores, L(x)y para ello emplearemos el siguiente teorema: Teorema 3.8. Sea L(x)un polinomio localizador de errores de un código Reed-Solomon. Entonces L(x) = Lt+1xt+... + +L2x+L1se puede obtener resolviendo el siguiente sistema:
26 CAPÍTULO 3. CÓDIGOS RS Y GRS S1S2· · · St+1 S2S3· · · St+2 . . .. . ..... . . StSt+1· · · S2t L1 L2 . . . Lt+1 = 0 0 . . . 0 Una vez que tenemos calculado el polinomio localizador de errores, L(x), tenemos que obtener sus raíces, para lo cual, si el cuerpo finito no es muy extenso se puede probar con todos los elementos del cuerpo, donde para reducir su costo computacional, se puede aplicar el método de Chien, el cual consiste en tomar cada elemento del cuerpo expresado en forma de potencia de un generador de dicho cuerpo. Aun así, si el cuerpo finito es demasiado extenso, dichas raíces se pueden obtener a partir de un algoritmo probabilístico eficiente conocido como Equal-degree factorization cuyo funcionamiento se puede ver en [23] . Entonces, dichas raíces serán una cierta potencia de nuestro elemento primitivo, β. Si βi1,..., βitson estas raíces, tenemos que el polinomio del error será e(x) = ei1xi1+... +eitxit, cuyos valores podemos calcular resolviendo el sistema S= HyT=HeT, siendo Hla matriz de control del código. Una vez que hemos obtenido el bloque de mensaje libre de errores, c∈GRSk(a,b), para obtener la descodificación de dicho bloque, m, tenemos que resolver el sistema c=mG, donde conocemos todo salvo m. Ejemplo 3.1. Consideramos el cuerpo finito F16 =F24y tomamos n=q−1=16 − 1=15 para obtener la máxima longitud posible para el código y que este sea cíclico. Para este ejemplo vamos a considerar que el código es capaz de corregir hasta 3 errores, es decir, la capacidad correctora del código, t, es 3. Como hemos visto que los Reed- Solomon son MDS, tenemos que n−k=2t=d−1, luego la dimension del código, k, para los parámetros propuestos tiene que ser k=n−2t=9. Tomamos como polinomio primitivo para generar F24ap(x) = x4+x+1 (Se podría razonar de igual forma con los otros polinomios primitivos de grado 4: p(x) = x4+x3+1 ó p(x) = x4+x3+x2+x+1). Vamos a buscar un elemento primitivo de F24,α, para ello, consideramos primero x=αy veamos que tiene orden 15: El orden de un elemento tiene que dividir al orden del grupo, entonces ord(α) tendría que ser 1, 3, 5, o 15 y como el orden de αno es ni 1 ni 3 ni 5 ya que α6=1, α36=1 y α5=α4α= (1+α)α=α+α26=1, necesariamente su orden es 15 y por tanto es un elemento primitivo de F24.
3.3. CODIFICACIÓN Y DESCODIFICACIÓN 27 Entonces los elementos del cuerpo se pueden representar como {0, 1, α,..., α14}. Calculando todas las potencias, podemos obtener los elementos del cuerpo también como sumas de elementos λαi, con i∈ {0,1,2,3}yλ∈F2: α6=α3+α2,α7=α4+α3= (1+α) + α3=1+α+α3,α8=α2+1, α9=α3+α, α10 =α2+x+1, α11 =α3+α2+α,α12 =α3+α2+α+1, α13 =α3+α2+1, α14 = α3+1, α15 =1. Entonces tomando como vector a= (1, α,α2, ..., α14), tenemos que el código Reed- Solomon que vamos a emplear es RS9(a). Si tomamos m= (1,0,0, 0,1,0,0,0,1)como el bloque de mensaje que queremos codificar, calculamos su polinomio, fm(x) = x8+x4+1, entonces su codificación es: C(m) = (fm(1),fm(α),..., fm(α14) . Vamos a obtener estos valores: fm(1) = 1+1+1=1 fm(α) = α8+α4+1=α2+1+α+1+1=α2+α+1=α10 fm(α2) = α16 +α8+1=α+α2+1+1=α2+α=α5 fm(α3) = α24 +α12 +1=α+α3+1+α+α2+α3+1=α2 fm(α4) = α32 +α16 +1=α2+α+1=α10 fm(α5) = α40 +α20 +1=1+α+α2+α+α2+1=0 fm(α6) = α48 +α24 +1=α3+α+α3+1=α+1=α4 fm(α7) = α56 +α28 +1=α+α2+α3+1+α2+α3+1=α fm(α8) = α64 +α32 +1=1+α+α2+1=α+α2=α5 fm(α9) = α72 +α36 +1=1+α+α2+α3+α2+α3+1=α fm(α10) = α80 +α40 +1=α+α2+1+α+α2+1=0 fm(α11) = α88 +α44 +1=1+α2+α3+1+α3+1=α2+1=α8 fm(α12) = α96 +α48 +1=α2+α3+α3+1=α2+1=α8 fm(α13) = α104 +α52 +1=1+α3+1+α+α3+1=1+α=α4 fm(α14) = α112 +α56 +1=α11 +α7+1=α3+α2+α+α3+α+1+1=α2 A partir de estos valores obtenemos el bloque de mensaje codificado, el cual es C(m) = (1, α10,α5,α2,α10, 0, α4,α,α5,α, 0, α8,α8,α4,α2). Una vez que hemos obtenido el bloque de mensaje codificado, suponemos que enviamos dicho bloque y durante su transmisión se producen tres errores, ω(e) = 3, cuyas posiciones son 0,7 y 14: y=c+e= (α,α10,α5,α2,α10, 0, α4,α3,α5,α,0, α8,α8,α4,α10)
28 CAPÍTULO 3. CÓDIGOS RS Y GRS Vamos a calcular el síndrome para poder corregir los errores: Escribimos yen forma polinomica y obtenemos y(x) = α+α10x+α5x2+α2x3+ α10x4+α4x6+α3x7+α5x8+αx9+α8x11 +α8x12 +α4x13 +α10x14. A partir de y(x) vamos a obtener todos los valores del síndrome S= (S1, ..., S6): S1=y(α) = α+α11 +α7+α5+α14 +α10 +α10 +α13 +α10 +α4+α5+α2+α9= 1+x3=α14 S2=y(α2) = α+α12 +α9+α8+α18 +α16 +α17 +α21 +α19 +α30 +α32 +α30 + α38 =x=α S3=y(α3) = α+α13 +α11 +α11 +α22 +α22 +α24 +α29 +α28 +α41 +α44 +α43 + α52 =0 S4=y(α4) = α+α14 +α13 +α14 +α26 +α28 +α31 +α37 +α37 +α52 +α56 +α56 + +α66 =1+x3=α14 S5=y(α5) = α+α15 +α15 +α17 +α30 +α34 +α38 +α45 +α46 +α63 +α68 +α69 + α80 =1+x=α4 S6=y(α6) = α+α16 +α17 +α20 +α34 +α40 +α45 +α53 +α55 +α74 +α80 +α82 + α94 =x=α Una vez obtenidos todos los valores del síndrome, vamos a utilizar estos valores para obtener el polinomio localizador de errores, L(x) = L4x3+L3x2+L2x+L1, resolviendo el siguiente sistema: α14 α0α14 α0α14 α4 0α14 α4α L1 L2 L3 L4 = 0 0 0 Obtenemos, sin tener en cuenta la solución idénticamente nula, Li=0∀i= 1,2,3,4, que L1=α6,L2=α11,L3=α4yL4=1. Luego L(x) = x3+α4x2+α11x+α6y sus raíces son x=1, x=α7yx=α14 Por tanto, el polinomio de error es e(x) = e3x14 +e2x7+e1. Ahora resolvemos el siguiente sistema para obtener los valores e1,e2,e3: 1α7α14 1α14 α13 1α6α12 e1 e2 e3 = α14 α 0 Obtenemos que e1=α4,e2=α9,e3=α4, luego e(x) = α4x14 + α9x7+α4y entonces podemos recuperar el mensaje codificado sin errores: c=y+e= (α+α4,α10,α5,α2,α10, 0, α4,α3+α9,α5,α,0, α8,α8,α4,α10 +α4) = (1, α10,α5,α2,α10, 0, α4,α,α5,α, 0, α8,α8,α4,α2).
3.3. CODIFICACIÓN Y DESCODIFICACIÓN 29 Por ultimo, resolvemos el siguiente sistema que nos permite recuperar el polinomio, f(x) = a15x14 +... +a2x+a1, que se corresponde con el mensaje descodificado: (a1,a2,· · · ,a9) 1 1 · · · 1 1α· · · α14 . . .. . ..... . . 1α9· · · (α9)14 =1, α10,· · · ,α2 Para resolver dicho sistema basta con emplear en este caso 9 columnas linealmente independientes de la matriz generatriz. Los valores que se obtiene al resolver este sistema son a1=1, a5=1, a9=1 y ai=0∀i=2,3,4,6,7,8 y por tanto el mensaje sería m= (1,0,0,0,1,0,0, 0,1), que se corresponde con el mensaje del que partíamos. La principal desventaja se encuentra en que la longitud de los códigos de Reed- Solomon y Reed-Solomon generalizados (sobre el cuerpo Fq) es de un máximo de q−1 y por ello no existen códigos de Reed-Solomon y Reed-Solomon generalizados sobre el cuerpo F2. Como dicha longitud se encuentra condicionada al tamaño del cuerpo finito, es necesario emplear cuerpos finitos grandes. Debido a esto, surgen códigos alternativos que emplean cuerpos finitos pequeños y mantienen las mismas buenas características que tenían los códigos de Reed-Solomon y Reed-Solomon generalizados, como por ejemplo los códigos de Goppa.
30 CAPÍTULO 3. CÓDIGOS RS Y GRS
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 es 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)∈Fn qque 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 polinomio de Goppa de cierto grado con coeficientes en Fq de los códigos Γ(L,g)yΓ(L,f)respectivamente. Se verifica que si f(x)|g(x)entonces 31
32 CAPÍTULO 4. CÓDIGOS DE GOPPA Γ(L,g)⊆Γ(L,f). Esto es evidente ya que si c∈Γ(L,g)se tiene que Rc(x)≡0 mod g(x)y como f(x)|g(x)entonces Rc(x)≡0 mod f(x). Nota 4.4. Sea pi(x) = pi,0 +pi,1x+... +pi,t−1xt−1congruente con 1 x−αi modulo g(x) ∀i=0, ..., n−1, entonces un vector c= (c0, ..., cn−1)∈Γ(L,g)si y solo si tenemos que ∑n i=1ci−1pi−1,j=0∀j=1, ..., t−1. Además, tenemos que pi(x)≡ −g(αi)−1g(x)−g(αi) x−αi mod g(x)porque: 1) Si denotamos di(x) = g(x)−g(αi)yg(x) = g0+g1x+...+gtxt, podemos observar que αies raíz de di(x)y como también lo es de x−αientonces x−αi|di(x) ∀i=0, ..., n−1 2) Multiplicando por x−αitenemos que: pi(x)(x−αi) = −(g(x)−g(αi))g(αi)−1=1−g(x)g(αi)−1≡1 mod g(x) Proposición 4.5. Según las consideraciones vistas en la nota 4.4, una matriz de control para un código de Goppa Γ(L,g)es: H0=g(α0)−1d0 x−α0,..., g(αn−1)−1dn−1 x−αn−1 Nota 4.6. Como en la matriz H0tenemos que cada término g(αi)−1di x−αi hace referencia a una columna de la matriz, es decir, calculando di x−αi =gt(xt−1+xt−2αi+... + αt−1 i) + ... +g2(x+αi) + g1tenemos que dicha matriz es: H0= g(α0)−1gt· · · g(αn−1)−1gt g(α0)−1(gt−1+gtα0)· · · g(αn−1)−1(gt−1+gtαn−1) . . .. . . g(α0)−1(g1+g2α0+... +gtαt−1 0)· · · g(αn−1)−1(g1+g2αn−1+... +gtαt−1 n−1) Ahora si denotamos las matrices EyHcomo: E= gt0· · · 0 gt−1gt· · · 0 . . .. . .. . . g1g2· · · gt ,H= g(α0)−1· · · g(αn−1)−1 g(α0)−1α0· · · g(αn−1)−1αn−1 . . .. . . g(α0)−1αt−1 0· · · g(αn−1)−1αt−1 n−1
4.1. INTRODUCCIÓN 33 Podemos ver que nuestra matriz H0se puede expresar como H0=E·H. Como la matriz Ees invertible, al ser det(E) = gt t6=0, ya que si gtfuera 0 nuestro polinomio g(x)tendría grado t−1 y por definición sabemos que tiene grado t. Entonces Hes también una matriz de control para Γ(L,g). Proposición 4.7. Sea el código de Goppa Γ(L,g). Tenemos que: a) Γ(L,g)es un código lineal. b) La longitud de las palabras de código c ∈Γ(L,g)es n =|L|. c) La dimension del código Γ(L,g)sobre Fqes k ≥n−mt d) La distancia mínima de Γ(L,g)es d ≥t+1 Demostración. a) Sean a= (a0, ..., an−1),b= (b0, ..., bn−1)∈Γ(L,g). Entonces tenemos que Ra(x) = ∑n i=1 ai−1 x−αi ≡0 mod g(x)yRb(x) = ∑n i=1 bi−1 x−αi ≡0 mod g(x)y como para el vector c=a+btenemos que Rc(x) = n ∑ i=1 ai−1+bi−1 x−αi = n ∑ i=1 ai−1 x−αi + n ∑ i=1 bi−1 x−αi ≡0 mod g(x) al ser tanto Ra(x)como Rb(x)congruentes a 0 modulo g(x)su suma también y entonces c∈Γ(L,g). De igual forma, si tomamos d∈Fqtenemos que, se cumple también de forma trivial, que para el vector c= (da0, ..., dan−1)tenemos que Rc(x)≡0 y por tanto también c∈Γ(L,g). b) Evidente. c) Como tanto los αicomo los g(αi)−1son elementos de Fqm, si sustituimos cada uno de estos por el vector correspondiente de tamaño mformado por elementos de Fqtendremos la matriz Hformada por elementos de Fqcon mt filas. Por ello, k=n−mt si todas las filas son linealmente independientes. Si no son linealmente independientes, tenemos que k>n−mt. d) Como sabemos que tcolumnas de la matriz Hson linealmente independientes tenemos que la distancia será al menos t+1 por lo visto en la proposición 2.17 .
40 CAPÍTULO 4. CÓDIGOS DE GOPPA a(x) = (α2+α)x+1, b(x) = αx+α3+α+1 Por tanto el polinomio localizador de errores resultante es: L(x) = α2x3+ (α2+α+1)x2+ (α3+1)x+1 Obteniendo entonces las raíces del polinomio L, las cuales se corresponden a los valores α5,α9yα14, obtenemos las posiciones en que ha ocurrido un error. Entonces, resolviendo ahora un sistema para cada bloque c1,c2, teniendo en cuenta la definición 2.4, ya que conocemos tanto Gcomo c1yc2podemos recuperar el mensaje m= (0,1,0,0,1,0,0,0)correspondiente con el carácter ASCII 0H0del cual partíamos.
Capítulo 5 Criptosistemas de McEliece y Niederreiter 5.1. Criptosistema de McEliece 5.1.1. Introducción El criptosistema McEliece es un criptosistema de clave pública el cual fue desarrollado por Robert McEliece en 1978. Aunque dicho criptosistema se olvido durante años al tener poca aceptación debido principalmente a los tamaños de las claves que necesita, actualmente ha ganado importancia al ser uno de los criptosistemas resistente a ataques de ordenadores cuánticos. El criptosistema se basa en la teoría de codificación y su seguridad se encuentra principalmente en que la matriz generatriz del código parece aleatoria y en la dificultad de descodificación de un código lineal del que no conocemos su estructura, al tratarse este de un problema computacionalmente difícil (NP-Hard) cuando el tamaño del código es grande (si es pequeño, encontrar la palabra del código con distancia menor o igual que la enviada no supondría ningún problema). Para algunos tipos de códigos existen algoritmos de descodificación, los cuales tienen complejidad polinómica y por ello, nos permiten eliminar el error de una palabra del código de forma eficiente. Por ejemplo, los códigos de Reed-Solomon y los códigos de Goppa que hemos visto en los capítulos 3 y 4. Para el criptosistema de McEliece emplearemos los códigos de Goppa clásicos binarios, debido a que son seguros, sencillos de construir y emplear y presentan mejores propiedades que los códigos de Goppa construidos sobre otros cuerpos finitos según lo visto en la proposición 4.8. 41
42 CAPÍTULO 5. MCELIECE Y NIEDERREITER En cuanto a los códigos Reed-Solomon y Reed-Solomon generalizados, no los emplearemos para la construcción del criptosistema de McEliece ya que, como veremos mas adelante, estos se pueden criptoanalizar de forma exitosa. 5.1.2. Descripción del criptosistema Para realizar la construcción del criptosistema primero escogemos un polinomio separable con coeficientes en F2mde grado ty un vector L∈Fn 2ma partir de los cuales obtenemos un código de Goppa con matriz generatriz, G, de tamaño k×n. Para estos códigos hemos visto el algoritmo de Patterson en las sección 4.2.1, a partir del cual podemos realizar la descodificación de hasta terrores de forma eficiente. A partir de la matriz generatriz G, calculamos la matriz G0, que tiene el mismo tamaño que Gy se obtiene mediante el producto de tres matrices: G0=SGP donde S es una matriz no singular cuadrada de tamaño k, es decir, una matriz que es invertible yPes una matriz cuadrada de tamaño npermutacional, es decir, una matriz con todos sus elementos nulos salvo un elemento por cada columna y fila que vale 1. Analizando la multiplicación de matrices realizada, podemos ver que la matriz SG es también una matriz generatriz del código de Goppa que teníamos, y al multiplicarla por la matriz Ptenemos que la matriz G0es la matriz generatriz de un código equivalente al que teníamos, y por ello ambas matrices tienen la misma capacidad correctora. Dicha matriz G0debe caracterizarse por ser una matriz que no revele la estructura del código de Goppa del que partimos, es decir, debe ser una matriz que oculte el código de Goppa inicial. Entonces las claves pública, κp, y privada, κs, del criptosistema de McEliece son respectivamente: κp= (G0,t)yκs= (G,S,P,ϑ) donde ϑdenota el algoritmo de descodificación de hasta terrores del código de Goppa de partida. 5.1.3. Cifrado y descifrado del McEliece En cuanto al proceso de comunicación entre dos personas mediante el empleo del criptosistema de McEliece, procedemos a explicar tanto el cifrado de un mensaje como su correspondiente descifrado: Para realizar el cifrado de un mensaje m= (m1,..., mk), de tamaño k, dirigido a un usuario con clave publica κp= (G0,t), tenemos que multiplicar el mensaje m por la matriz G0y obtenemos el vector cde tamaño n:c=mG0= (c1,..., cn).
5.1. CRIPTOSISTEMA DE MCELIECE 43 Ahora añadimos una cantidad de errores, de tamaño menor o igual a t, al vector c, es decir, tomamos e= (e1,..., en)con ω(e)≤ty realizamos la suma de ambos vectores, c0=c+e. Normalmente se escoge un vector de errores cuyo peso sea el máximo. 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. Como el criptosistema que hemos definido emplea códigos de Goppa binarios, dicho algoritmo de descodificación puede ser el visto en la sección 4.2.1. El algoritmo se puede emplear ya que la matriz SG es también una matriz generatriz del código de Goppa y que tanto el vector ecomo el vector eP−1tienen el mismo peso. Después, obtenemos mS resolviendo el sistema de ecuaciones correspondiente a realizar el descifrado 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. Ejemplo 5.1. Utilizaremos el código de Goppa que construimos en el ejemplo 4.1. Comenzamos generando las claves pública y privada del criptosistema que emplea dicho código de Goppa. En dicho ejemplo ya mostramos la matriz Gde tamaño 4 ×16, la cual emplearemos para el calculo de la matriz G0, necesaria para la clave pública del criptosistema. Para ello, necesitamos obtener tanto una matriz de permutación cuadrada de tamaño 16, P, como una matriz invertible cuadrada de tamaño 4, S. Para conseguir dichas matrices, emplearemos el código desarrollado en Sagemath, el cual se muestra junto con el resto del código generado para la construcción del criptosistema de McEliece en [1, 5.2] del trabajo fin de grado de informática. Las matrices generadas son: S= 0 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1
44 CAPÍTULO 5. MCELIECE Y NIEDERREITER P= 0001000000000000 0000100000000000 0000000000000100 1000000000000000 0100000000000000 0000000001000000 0000001000000000 0000000000001000 0000000010000000 0000000000100000 0000000000010000 0000010000000000 0000000100000000 0000000000000001 0000000000000010 0010000000000000 Entonces obtenemos la matriz G0como el producto de las matrices S,GyP: G0=S·G·P= 0010010000101111 1101100011010100 1000111001011001 1100001101101101 Por tanto, ya tenemos todos los elementos necesarios para generar las claves publica y privada, κpyκsrespectivamente. Ahora vamos a realizar tanto el cifrado como el correspondiente descifrado de un mensaje. Supongamos que una persona desea enviar el carácter 0H0a otra persona que tiene como clave pública κp. Ya vimos en el ejemplo 4.1, que dicho carácter ASCII se corresponde con el vector binario m= (0,1,0, 0,1,0,0,0). Para realizar el cifrado del vector mprimero dividimos el mensaje men dos bloques de longitud 4 cada uno: m1= (0,1,0,0),m2= (1,0, 0,0) Entonces multiplicamos cada bloque por la matriz G0que obtenemos de su clave pública y como resultado tenemos los bloques codificados: c1= (1,1, 0,1,1,0,0,0,1, 1,0,1,0,1,0,0) c2= (0,0, 1,0,0,1,0,0,0, 0,1,0,1,1,1,1)
5.1. CRIPTOSISTEMA DE MCELIECE 45 Ahora, obtenemos a partir de la clave pública, que la capacidad correctora del código empleado es t=3. Por tanto, para cada bloque codificado introducimos 3 errores. Para el primer bloque, introducimos los errores en las posiciones 5, 10 y 14 y para el segundo bloque, los introducimos en las posiciones 0, 1 y 13. Entonces, el vector cifrado, c0, para el cual ya se han concatenado los dos bloques cifrados se corresponde con: c0= (1,1,0,1,1,1,0,0,1, 1,1,1,0,1,1,0, 1,1,1,0,0,1,0, 0,0,0,1,0,1,0, 1,1) Entonces, se envía el mensaje c0a la persona, con quien se quería realizar la comunicación, a la que pertenecía la clave pública. En cuanto al proceso de descifrado, seguimos también los pasos de la sección 5.1.3. Por tanto, primero tenemos que calcular la matriz inversa de Py después multiplicamos cada bloque de c0de longitud 16 por dicha matriz, obteniendo como resultado: c∗ 1= (1,1,1,1,1,1,0,0,1, 1,1,1,0,0,1,0) c∗ 2= (0,0,0,1,1,0,0,1,0, 1,0,1,0,1,1,1) Ahora, para ambos bloques tenemos que aplicar el algoritmo de descodificación de Patterson de igual forma que vimos en el ejemplo 4.1. Por tanto, nos limitaremos simplemente a mostrar los resultados obtenidos por el programa realizado en Sagemath en [1, 4.3.2] y [1, 4.3.3] del trabajo fin de grado de informática. Calculamos el síndrome de ambos bloques según lo visto en la definición 4.9: s(c∗ 1) = 15 ∑ i=0 c∗ 1i x−li ≡(α3+α)x2+x+α3mod g(x) s(c∗ 2) = 15 ∑ i=0 c∗ 2i x−li ≡(α3+α2+1)x2+ (α3+α2)x+α3mod g(x) donde lihace referencia a la coordenada i-esima del vector Lcorrespondiente al código de Goppa, Γ(L,g), empleado. Ahora calculamos los polinomios f1(x)yf2(x), los cuales obtenemos a partir del inverso del síndrome s(c∗ 1)ys(c∗ 2)módulo grespectivamente: f1(x) = α3x2+ (α3+α+1)x+α2 f2(x) = (α2+α)x+α3+α2+1
46 CAPÍTULO 5. MCELIECE Y NIEDERREITER Como f1(x)6=xyf2(x)6=xtenemos que continuar con los pasos restantes del algoritmo en ambos casos. Por ello, ahora calculamos hi(x)de forma que h2 i(x)≡ fi(x) + xmod g(x), con i=1,2: h1(x) = (α+1)x2+ (α3+α2)x+α h2(x) = (α3+α2+α+1)x2+ (α3+α2+1)x+α3+1 Ahora obtenemos los polinomios ai(x)ybi(x)de menor grado para cada polinomio hi, con i=1,2: a1(x) = α3x+α3+α+1, b1(x) = (α3+α2+α)x+α3+α2+1) a2(x) = α2x+α3+α,b2(x) = α3x+α+1 Por tanto el polinomio localizador de errores resultante para cada bloque es: L1(x) = (α3+α+1)x3+ (α3+α2)x2+ (α3+α2+α)x+α3+1 L2(x) = (α3+α2)x3+ (α+1)x2+ (α2+1)x+α3 Por último, obtenemos las tres raíces de cada polinomio Li, con i=1,2, evaluando sobre cada polinomio cada elemento del vector L. Para el primer bloque, obtenemos que las raíces son los elementos α10,α12 y 1. Por tanto, los errores se encuentran en las posiciones 9, 11 y 14. En cuanto al segundo bloque, obtenemos que las raíces son los elementos α3,α4y α5y por tanto los errores se encuentran en las posiciones 2, 3 y 4. Entonces, los dos vectores obtenidos una vez corregidos las posiciones de error se corresponden con cada bloque de mensaje multiplicado por la matriz Sy codificado, es decir: m1·S·G= (1,1,1,1,1,1,0,0,1, 0,1,0,0,0,0,0) m2·S·G= (0,0,1,0,0,0,0,1,0, 1,0,1,0,1,1,1) Realizando la descodificación de cada bloque mi, obtenemos como resultado los bloques miS: m1·S= (1,1,1,1)
5.1. CRIPTOSISTEMA DE MCELIECE 47 m2·S= (0,0,1,0) Por ultimo, calculando S−1, la matriz inversa de Sy después multiplicando cada uno de los bloques mi·Spor S−1recuperamos las coordenadas del mensaje enviado: m1=m1·S·S−1= (0,1, 0,0) m2=m2·S·S−1= (1,0, 0,0) Entonces juntando los dos bloques de mensaje, recuperamos el mensaje m= (0,1,0,0,1,0,0, 0)correspondiente con el carácter ASCII 0H0que habíamos enviado. 5.1.4. 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 es un criptosistema post-cuá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 numero 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 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
48 CAPÍTULO 5. MCELIECE Y NIEDERREITER 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 version 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 explicamos a continuación, que permite la realización de firmas digitales [7]. 5.2. Criptosistema Niederreiter 5.2.1. Introducción El criptosistema Niederreiter es un criptosistema dual al de McEliece el cual surgió en 1986, donde se emplea la matriz de control para realizar tanto el cifrado y descifrado. Para dicho criptosistema fueron propuestos en su primera version códigos GRS (Reed-Solomon generalizados). Mas adelante se descubrió que dicho criptosistema se criptoanalizaba exitosamente si se empleaban códigos Reed-Solomon generalizados, como mostramos mas adelante. Sin embargo, si se emplean en su lugar códigos de Goppa clásicos su seguridad hasta el momento no se ha visto comprometida, de igual forma que para el criptosistema de McEliece. Esto es debido a que los critosistemas de Niederreiter y McEliece son equivalentes en términos de seguridad, lo cual, fue probado por Yuan Xing en el año 1994 en [6]. 5.2.2. Descripción del criptosistema Para su construcción, se realiza un proceso semejante al realizado en el sistema de McEliece, es decir, se elige un polinomio separable y un vector L, que se emplean para generar un código de Goppa capaz de corregir terrores a partir de un algoritmo de descodificación eficiente, y ahora se calcula la matriz de control del código, H, que tiene un tamaño (n−k)×n. Una vez calculada dicha matriz de control debemos enmascararla, de igual forma que se enmascaraba la matriz generatriz del código para el criptosistema de McEliece como vimos en la sección 5.1.2. Por tanto, se eligen S, una
5.2. CRIPTOSISTEMA NIEDERREITER 49 matriz no singular cuadrada de tamaño n−kyP, una matriz cuadrada de tamaño n de permutación. Entonces calculamos la matriz H0=S·H·Py la clave pública, κp, y la clave privada, κs, del criptosistema son respectivamente: κp= (H0,t)yκs= (H,S,P,ϑ) donde ϑdenota un algoritmo decodificador por sindromes, similar al visto en la sección 2.2, eficiente de hasta terrores del código de Goppa de partida. 5.2.3. Cifrado y descifrado del Niederreiter En cuanto al proceso de cifrado y descifrado del criptosistema se realiza un procedimiento semejante al realizado en McEliece en la sección 5.1.3. Para el cifrado se emplea la matriz H0en lugar de la matriz G0y únicamente se pueden cifrar palabras de peso menor o igual a t, las cuales, se corresponden con los lideres de los cogrupos que vimos en la sección 2.2. Para el descifrado el procedimiento a realizar es el mismo pero empleando en primer lugar la matriz inversa de Sy no la de P. Ejemplo 5.2. Vamos a construir un criptosistema de Niederreiter empleando su propuesta original, es decir, a partir de un código Reed-Solomon generalizado. Por ello, consideramos el código GRS3(a)sobre F7, donde a= (0,1,2,3,4,5,6), luego los parámetros fundamentales del código son [7, 3,5]. Una matriz de control, H, de GRS3(a) es H= 6666666 0654321 0635536 0661611 A partir de la matriz H, construimos el criptosistema de Niederreiter empleando para ello una matriz aleatoria cuadrada invertible, S, de tamaño 4 y una matriz aleatoria de permutación cuadrada, P, de tamaño 7: S= 4 0 2 2 0 3 1 0 1 6 3 2 0 6 5 5
56 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS 1) ⊆)Sean a∈GRSk(x,y)yb∈GRSk0(x,y0)elementos cualesquiera. Dichos elementos tendrán la forma siguiente: a= (y1p(x1), ..., ynp(xn)) yb= (y0 1q(x1), ..., y0 nq(xn)) donde pyqson ambos polinomios de grado menor que kyk0respectivamente. Ahora, calculamos el producto estrella de los vectores ayb: a?b= (y1y0 1p(x1)q(x1), ..., yny0 np(xn)q(xn)) = (y1y0 1r(x1), ..., yny0 nr(xn)) donde res un polinomio de grado menor que k+k0−1 y por tanto es un elemento de GRSk+k0−1(x,y?y0). ⊇)Dado un elemento a∈GRSk+k0−1(x,y?y0), tenemos que a= (y1y0 1r(x1), ..., yny0 nr(xn)) siendo run polinomio de grado menor que k+k0−1. Dicho polinomio se podrá obtener como combinación lineal de productos de dos polinomios de grado menor que kyk0y por tanto el vector asera el producto estrella de un elemento de GRSk(x,y)y otro de GRSk0(x,y0). 2) Es evidente su demostración a partir de 1)al ser un caso particular tomando y=y0yk=k0. Nota 6.7. Si tenemos que la dimension del GRS verifica que 2k−1>n, la segunda parte de la proposición 6.6 también se cumple ya que, considerando su código dual, sabemos por la proposición 3.6 que la dimension sera k0=n−ky entonces como k>n+1 2se tiene que −k≤−n−1 2y por tanto k0≤n−1 2≤n+1 2. Para la primera parte de la proposición 6.6 también se puede realizar un razonamiento similar teniendo en cuenta tanto la dimensión kcomo k0, pero este caso no lo mostramos debido a que no lo necesitaremos emplear después. Por tanto, como principal conclusión obtenemos que la dimension de un código cuadrado de un GRS de dimension kes 2k−1. Ahora que sabemos la dimension del código cuadrado de un GRS, vamos a introducir una definición y proposición que necesitaremos para demostrar una importante proposición, la cual nos permite conocer con alta probabilidad la dimensión del cuadrado de un código lineal aleatorio. Definición 6.8. Sea Cun código lineal de parámetros [n,k]sobre Fq, el cual tiene como base a los vectores g1,.., gk. Llamaremos segunda potencia simétrica o producto tensorial simétrico de Ccon el mismo, y lo denotamos por S2(C), al código que tiene como
6.1. INTRODUCCIÓN 57 base {gi⊗gj|1≤i≤j≤k}, donde ⊗hace referencia al operador producto tensorial. Por tanto, la dimension de S2(C)es (k+1 2). Considerando ahora la aplicación lineal σ:S2(C)−→ C?2 gi⊗gj7−→ gi?gj tenemos por el primer teorema del isomorfismo, al ser C?2la imagen de σ, que dim K2(C) + dim C?2=dim S2(C) = k+1 2(6.1) siendo K2(C)el núcleo de la aplicación σ, es decir, K2(C) = Ker(σ) Por tanto, tenemos que K2(C)es el espacio de soluciones del conjunto de ecuaciones dadas por ∑ 1≤i≤i0≤k gijgi0jxii0=0|1≤j≤n Proposición 6.9. Sea C un código lineal de parámetros [n,k]y sea G una matriz generatriz de C, que tomamos en forma sistemática, es decir, G = (Ik|P)siendo P una matriz de tamaño k×(n−k). Entonces se cumple que dim K(LP) = dim K2(C⊥) donde K(LP)es el núcleo de LP, que hace referencia al sistema asociado a la matriz P, formado por k ecuaciones y (n−k 2)variables, xjj0con k <j<j0≤n, es decir LP=(∑ k<j<j0≤n pij pij0xjj0=0|1≤i≤k) Demostración. Consideramos G, matriz generatriz de Cen forma sistemática, entonces la matriz de control de Ces H= (PT| − In−k). Sea hila fila i-esima de la matriz de control H,eila i-esima fila de la matriz identidad In−kyqila i-esima fila de la matriz PT. Entonces se cumple que qij =pj i+ky hi= (qi| − ei). Por tanto hj?hj0es (qj?qj|ei)si j=j0y(qj?qj0|0)si j<j0.
58 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS Sea M1la matriz de tamaño k×(n−k 2)formada por los elementos pij pij0con 1 ≤i≤ kyk<j<j0≤n. Entonces se tiene que dim K(LP) = n−k 2−rg(M1) donde rg(M1)hace referencia al rango de la matriz M1. Consideramos ahora M2, la matriz de tamaño (n−k+1 2)×nformada por los elementos hijhi0jcon 1 ≤i≤i0≤n−ky 1 ≤j≤n. Entonces se tiene que dim (C⊥)?2=rg(M2) = n−k+rg(M1) Por tanto, tenemos que dim K(LP) = n−k 2+n−k−dim (C⊥)?2 y por la igualdad de la ecuación (6.1) tenemos que dim K(LP) = n−k 2+n−k−(n−k+1 2−dim K2(C⊥)) y como (n−k 2)+n−k=(n−k+1 2)entonces tenemos que dim K(LP) = dim K2(C⊥) como queríamos. Corolario 6.10. Sea C un código lineal de parámetros [n,k]sobre el cuerpo Fq. Se verifica que dim C?2≤min n,k+1 2 Ahora vamos a probar lo que realmente buscábamos, que la igualdad en la desigualdad del corolario 6.10 se da con una alta probabilidad si las entradas de la matriz Pson independientes e igualmente distribuidas. Proposición 6.11. Sea C un código lineal aleatorio de parámetros [n,k]sobre el cuerpo Fqtal que n >(k+1 2). Entonces se verifica que Pr dim(C?2) = k+1 2=1 donde Pr(S)indica la probabilidad de que ocurra el suceso S.
6.1. INTRODUCCIÓN 59 Demostración. Sea Cun código lineal que verifica las hipótesis de la proposición. Si G es una matriz generatriz de C, la cual tomamos en forma sistemática, es decir, G= [Ik|P], donde Ikhace referencia a la matriz identidad cuadrada de tamaño kyPal resto de la matriz, la cual tiene tamaño k×(n−k). Sabemos que H= [PT| − In−k] es una matriz de control de Cy por tanto, también es una matriz generatriz de C⊥. Si denotamos por LPTa el sistema lineal obtenido a partir de la matriz PT LPT=(∑ 1≤j<j0<k pij pij0xjj0=0|1≤i≤n−k) el cual tiene n−kecuaciones lineales y (k 2)incógnitas, donde pij hace referencia a el elemento de la fila iy columna jde la matriz PTyxjj0a una incógnita. La dimensión del espacio de soluciones de LPTes 0 con una alta probabilidad debido a un resultado probado por Faugère en [9]. Por ello, empleando la ecuación (6.1) tenemos con una alta probabilidad que dim(C?2) = (k+1 2)como queríamos. Debido a esto, tenemos que la dimensión del código cuadrado de un código aleatorio lineal debe encontrarse en torno al min{(k+1 2),n}. Por tanto, esta técnica nos permite diferenciar un código GRS de un código lineal aleatorio, lo cual es muy útil ya que, si por ejemplo, tenemos la clave pública de un criptosistema de McEliece, podremos conocer si dicho criptosistema esta empleando códigos de GRS y por tanto aplicar el ataque por filtración que veremos mas adelante para criptoanalizar dicho criptosistema de McEliece. Ahora vamos a introducir los códigos punteados y recortados de códigos lineales debido a una propiedad que cumplen los códigos GRS, sobre la cual también nos apoyaremos para realizar el ataque de filtración. Definición 6.12. Dado un código lineal Cde parámetros [n,k], y sea (J,J0)una partición de {1, ..., n}la cual verifica que J∪J0={1,..., n}y que J∩J0=∅. Diremos que el código punteado de Cen J, denotado por PJ(C), es el código, también lineal, cuyas palabras se obtienen a partir de las palabras del código de Crestringidas a las posiciones de J0: PJ(C) = {(ci)i∈J0|c∈C} Nota 6.13. Si Ges una matriz generatriz para C, una matriz generatriz para PJ(C)se obtiene eliminando de la matriz Gel conjunto de Jcolumnas y omitiendo, en caso de que ocurra, las filas con todos los elementos nulos, filas duplicadas y linealmente dependientes.
60 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS Ejemplo 6.1. Sea Cun código lineal de parámetros [7,3,3]sobre F2dado por la matriz generatriz G= 1001111 0100101 0011100 El código punteado en J={5}es el código lineal formado por las palabras del código que se obtienen de eliminar la quinta coordenada de las palabras del código C, y la matriz generatriz es G0= 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 Definición 6.14. Dado un código lineal Cde parámetros [n,k], y sea (J,J0)una partición de {1, ..., n}la cual verifica que J∪J0={1,..., n}y que J∩J0=∅. Diremos que el código recortado de Cen J, denotado por SJ(C), es el código cuyas palabras se obtienen a partir de las palabras del código de Cque verifican que sus coordenadas son nulas en las posiciones de J, restringidas a las posiciones de J0: SJ(C) = {(ci)i∈J0|c∈C,cj=0∀j∈J} Nota 6.15. Los códigos recortados son un subconjunto de los códigos punteados. Nota 6.16. Si una matriz generatriz de Ces G, una matriz generatriz para SJ(C)se obtiene moviendo las columnas de las posiciones de Ja las |J|primeras columnas de la matriz y aplicando después eliminación Gaussiana sobre estas para obtener la matriz identidad en las |J|primeras filas y ceros en la submatriz k− |J|×|J|, es decir, obteniendo G=I|J|T O G0 donde I|J|es la matriz identidad cuadrada de tamaño |J|,Tes una matriz cualquiera, Oes una matriz con todas sus coordenadas nulas de tamaño k− |J|×|J|yG0es la matriz generatriz del código SJ(C). Nota 6.17. Si el conjunto Jse reduce únicamente a un valor, es decir, J={j}, escribiremos Pj(C)ySj(C)en lugar de escribir P{j}(C)yS{j}(C)respectivamente. Ejemplo 6.2. Sea Cun código lineal de parámetros [7, 3,3]sobre F2dado por la misma matriz generatriz que el ejemplo 6.1. El código recortado en la quinta coordenada, S5(C), es el código formado por las palabras del código que se obtienen de eliminar la quinta coordenada de las palabras del código Cy que su quinta coordenada sea nula.
6.1. INTRODUCCIÓN 61 Moviendo la quinta columna hacia la primera y realizando eliminación Gaussiana obtenemos G= 1110011 0101001 0010111 y por tanto, obtenemos que la matriz generatriz de S5(C)es G0=1 0 1 0 0 1 0 1 0 1 1 1 Proposición 6.18. Dado C un código GRSk(a,b), se cumple que el código recortado de C es también un código GRS y se tiene que: SJ(C) = GRSk−|J|(PJ(a),b0) donde las coordenadas de b0vienen dadas por: b0 i=bi∏ j∈J (ai−aj) Demostración. Sea Jel conjunto de posiciones que emplearemos para el código recortado y Gla matriz generatriz de Cdada por G= b1b2· · · bn b1a1b2a2· · · bnan . . .. . ..... . . b1ak−1 1b2ak−1 2· · · bnak−1 n Moviendo las columnas de las posiciones de Ja las |J|primeras columnas de la matriz y aplicando después eliminación Gaussiana obtenemos la matriz G=I|J|T O G0 donde G0es la matriz generatriz de SJ(C), la cual tiene la forma G0= b0 |J|+1· · · b0 n . . ..... . . b0 |J|+1ak−|J|−1 |J|+1· · · b0 nak−|J|−1 n siendo b0 i=bi∏j∈J(ai−aj)debido a las operaciones necesarias para obtener la matriz identidad, I|J|y la matriz cuyos elementos son todos nulos, O. Ademas, vemos que al ser b0 i∈Fq∀i=2, ..., n, se tiene que G0es una matriz también de un código GRS.
62 CAPÍTULO 6. ATAQUE CONTRA 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.19. Dados los códigos GRSk(a,b)y GRSk−1(a,b), es posible calcular el código GRSk−2(a,b). Demostración. Sabemos por la proposición 6.6 que GRSk−2(a,b)?GRSk(a,b) = GRSk−1(a,b)?2(6.2) y por tanto, si vemos que dicho código de Reed-Solomon generalizado es GRSk−2(a,b) = {c∈GRSk−1(a,b)|c?GRSk(a,b)⊆GRSk−1(a,b)?2} estaría probado. Para ello, veamos la doble contención: ⊆)Sea c∈GRSk−2(a,b), como GRSk−2(a,b)⊂GRSk−1(a,b)entonces c∈ GRSk−1(a,b)y por (6.2) la contención esta demostrada. ⊇)Sea c∈GRSk−1(a,b), entonces puede ocurrir que: 1) c∈GRSk−2(a,b). 2) c∈GRSk−1(a,b)c∈GRSk−2(a,b). En este caso, existe un polinomio fde grado k−2 tal que c= (b1f(a1),..., bnf(an)) ∀c. Entonces el código obtenido a partir de c?GRSk(a,b)esta formado por polinomios cuyo grado es hasta k−2+k−1= 2k−3, luego es un código con dimensión 2k−2, el cual tiene que estar contenido por hipótesis, según la proposición 6.6, en un código de dimensión 2k−3, lo cual es absurdo y por tanto este caso no puede ocurrir. Entonces, tendríamos que solo puede ocurrir que c∈GRSk−2(a,b)que es lo que queríamos. Nota 6.20. 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
6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 63 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.19, 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. Si ahora obtenemos el elemento a, tendríamos determinado por completo el código Reed-Solomon 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 dimension 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 Como sabemos por la sección 3.2 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 lo visto en la proposición 2.10. 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
64 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS 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. Ejemplo 6.3. Sean 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 que suponemos desconocidos, los códigos Reed- Solomon generalizados de los cuales conocemos una matriz generatriz que denotamos GyG0respectivamente, cuyos valores son G= 3 10 5 9 9 10 5 2 3 9 1 5 2 3 3 8 3 7 9 4 9 2 4 10 3 3 4 1 2 5 9 7 G0= 6 9 10 7 7 9 10 4 6 7 2 10 4 6 6 5 6 3 7 8 7 4 8 9 Como GRS3(a,2b) = GRS3(a,b)podemos aplicar la proposición 6.19 para comenzar a realizar la filtración. En primer lugar, calculamos GRS2(a,b)y para ello es necesario realizar el cálculo del código GRS3(a,b)?2que según la nota 6.3, nos podemos restringir a construir el espacio generado a partir de todos los productos de las filas de la matriz G0. Como tiene 3 filas, se necesita realizar un total de 6 multiplicaciones: (6,9,10,7,7,9,10, 4)?(6, 9,10,7,7,9,10,4) = (3,4,1,5, 5,4,1,5) (6,9,10,7,7,9,10, 4)?(6, 7,2,10,4,6,6,5) = (3,8,9,4, 6,10,5,9) (6,9,10,7,7,9,10, 4)?(6, 3,7,8,7,4,8,9) = (3,5,4,1, 5,3,3,3) (6,7,2,10,4,6,6, 5)?(6, 7,2,10,4,6,6,5) = (3,5,4,1, 5,3,3,3) (6,7,2,10,4,6,6, 5)?(6, 3,7,8,7,4,8,9) = (3,10,3,3, 6,2,4,1) (6,3,7,8,7,4,8, 9)?(6, 3,7,8,7,4,8,9) = (3,9,5,9, 5,5,9,4) A partir de los 6 vectores obtenidos, tenemos que quedarnos solo con una combinación linealmente independiente para calcular una base, la cual se tiene que obtener a partir de 5 vectores según la proposición 6.6, y como el tercer y cuarto vector son iguales ya tenemos los 5 vectores que forman una base y por tanto, que se corresponden con las filas de la matriz generatriz del código GRS3(a,b)?2.
6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 65 A partir de esto, vamos a obtener una matriz generatriz de GRS2(a,b). Para ello realizaremos los pasos de la nota 6.20, es decir, calculamos una matriz de control, H1, de GRS3(a,b)?2 H1= 1 0 0 1 9 3 4 6 0 1 0 4 1 7 7 7 001110812 y ahora tenemos que resolver el sistema formado por 3 ∗4=12 ecuaciones obtenidas tras realizar el producto estrella de cada fila de Gcon cada fila de H1. Si denotamos c= (c1, ..., c8)como la incógnita que tenemos que obtener, el sistema se corresponde con A·cT=0 siendo Ala matriz 12 ×8 siguiente: A= 3 0 0 9 4 8 9 1 0 10 0 3 9 4 2 3 0 0 5 9 2 3 5 4 3 0 0 5 7 9 1 4 0 9 0 9 2 10 10 1 0 0 1 5 9 2 3 5 3 0 0 4 4 6 5 5 0 7 0 5 9 3 6 4 0 0 9 4 2 5 4 9 3 0 0 1 7 4 3 9 0 3 0 4 2 2 8 5 0 0 4 1 9 7 9 3 Lo resolvemos empleando Sage, obteniendo como resultado el espacio vectorial que tiene como base los vectores (1,0,3,8,9,2, 6,6)y(0, 1,4,4,7,7,2,5), los cuales se corresponden con las filas de una matriz generatriz, G000, de GRS2(a,b)que necesitábamos. Ahora a partir de GRS3(a,b)yGRS2(a,b)tenemos que realizar el mismo procedimiento, es decir, comenzamos calculando GRS2(a,b)?2donde tenemos que realizar 3 multiplicaciones: (1,0,3,8,9,2,6, 6)?(1, 0,3,8,9,2,6,6) = (1,0,9,9, 4,4,3,3) (1,0,3,8,9,2,6, 6)?(0, 1,4,4,7,7,2,5) = (0,0,1,10, 8,3,1,8) (0,1,4,4,7,7,2, 5)?(0, 1,4,4,7,7,2,5) = (0,1,5,5, 5,5,4,3) Claramente, los tres vectores son linealmente independientes y por tanto constituyen una base que se corresponde con las filas de una matriz generatriz de GRS2(a,b)?2.
72 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS Ahora realizamos el cifrado de un mensaje cualquiera, m= (8,0,5, 5,2,3), para ello introducimos sobre el codificado 2 errores, correspondientes a la máxima capacidad correctora del código GRS6(a,b), obteniendo y= (4,5, 10,7,11,10,9,5,10, 10). Vamos a recuperar dicho mensaje tras realizar el ataque de filtración contra la estructura del código, es decir, después de recuperar el código GRS6(a,b)de partida. En primer lugar tenemos que observar que para este caso, la dimensión es mayor que la mitad de la longitud y por tanto tenemos que recurrir al código dual GRS6(a,b)⊥=GRS4(a,b0). Para ello, empleamos como matriz generatriz, Gdual, la matriz de control correspondiente al código con matriz generatriz Gp, la cual expresamos en forma estándar para facilitar el resto de cuentas: Gdual = 1 0 0 0 9 8 7 6 10 9 0 1 0 0 11 2 1 4 10 1 0 0 1 0 4 3 12 11 11 9 0 0 0 1 3 5 12 8 2 11 Ahora calculamos la matriz generatriz del código recortado en la primera posición, Gs10, en la segunda posición, Gs01, y en ambas posiciones, Gs11, las cuales tienen los siguientes valores: Gs10 = 1 0 0 11 2 1 4 10 1 0 1 0 4 3 12 11 11 9 0 0 1 3 5 12 8 2 11 Gs01 = 1 0 0 9 8 7 6 10 9 0 1 0 4 3 12 11 11 9 0 0 1 3 5 12 8 2 11 Gs11 =1 0 4 3 12 11 11 9 0 1 3 5 12 8 2 11 También calculamos las matrices generatrices que denotamos Gp10 yGp10s01, del código punteado en la primera posición a partir del código GRS6(a,b)⊥y del código punteado en la primera posición a partir del código que se construye empleando la matriz Gs01 como generatriz: Gp10 = 1 0 0 0 11 4 1 5 3 0 1 0 0 11 6 4 8 5 0 0 1 0 11 1 6 3 8 0 0 0 1 11 8 5 4 1
6.2. ATAQUE POR FILTRACIÓN A CÓDIGOS GRS 73 Gp10s01 = 100116485 010111638 001118541 Ahora a partir de los códigos con matrices generatrices Gp10 yGs10, realizando un proceso semejante al del ejemplo 6.3, el cual no mostramos, obtenemos el código con dimensión 1 cuya matriz generatriz nos proporciona los valores de las coordenadas del vector c:c= (1,7,12, 10,5,8,8,7,1). De igual forma, a partir de los códigos con matrices generatrices Gp10s01 yGs11, realizando también el proceso anterior obtenemos el vector c0= (1,7,12,12,5,2, 12,8). Después de la obtención de los vectores cyc0, realizamos la división por coordenadas de c0entre c1, donde c1se corresponde con el vector cal que eliminamos la primera coordenada. De esta forma obtenemos c0 c1= (2,6, 9,5,12,10,11,8)y como 1 /∈c0 cpodemos tomar el valor β0=1 y realizar la evaluación de cada una de sus coordenadas sobre y7−→=1 1−ypara recuperar todas las coordenadas del vector aexcepto las dos primeras, lo cual no supone ningún problema al estar estas posiciones fijados sus valores. Por tanto obtenemos el vector a= (0,1,12,5,8, 3,7,10,9,11)y ahora realizando la división de centre a3recuperamos todas las coordenadas del vector b0excepto b0 1, es decir, b0= (b0 1,1,6,8,2,5,12, 5,7,8). Para recuperar la primera coordenada, vamos dando valores a b0 1hasta obtener un vector b0que se encuentre en el código GRS4(a,b0) de partida. Para finalizar, nos falta calcular el vector bque nos permita recuperar el código GRS6(a,b)de partida. Para ello, simplemente construimos el código GRS9(a,b0), y su matriz de control se corresponde con el vector bque buscamos. Entonces, calculando ahora el código GRS6(a,b)y aplicando su algoritmo de corrección de errores sobre el vector y, obtenemos c= (2,5,10, 7,11,4,9,5,10,10)y realizando la descodificación a partir de una matriz cuadrada invertible construida mediante columnas de Gprecuperamos el mensaje de partida, m= (8,0, 5,5,2,3).
74 CAPÍTULO 6. ATAQUE CONTRA CÓDIGOS GRS
Capítulo 7 Reducción de claves propuesta por Gaborit 7.1. Introducción Sabemos que el criptosistema McEliece es resistente frente a ataques realizados mediante ordenadores cuánticos, por lo que podría ser un criptosistema que sustituya en un futuro a el RSA, logaritmo discreto o cualquier otro sistema de seguridad criptográfica actual. Sin embargo, el gran tamaño de la clave pública del criptosistema de McEliece supone un gran problema, debido a que la memoria necesaria para guardar las claves se incrementa notablemente según vamos empleando criptosistemas mas extensos. Por ello, en esta parte vamos a ver un método para reducir la clave pública del sistema de McEliece, el cual fue descrito por Gaborit en el artículo expuesto en 2004 [10] y aunque dicho método fue criptoanalizado de forma exitosa, tiene importancia al ser el primero en intentar reducir la clave empleando la estructura de los códigos cíclicos y cuasiciclicos. Estos y otros códigos están siendo empleados actualmente con ciertas mejoras para crear un criptosistema estándar de McEliece en un concurso organizado por el NIST (National Institute of Standars and Technology) llamado "Post-Quantum Cryptography Standardization Process"[30]. En este documento, presentamos en el capítulo 9 una versión innovadora del criptosistema de McEliece que trata de reducir el tamaño de las claves empleando la idea principal que describimos en este capítulo pero usando códigos de producto de matrices que veremos en el capítulo 8. Antes de empezar, comenzamos introduciendo los códigos cíclicos y cuasiciclicos junto con sus propiedades mas elementales y necesarias para la explicación del método realizado por Gaborit. Si se desea conocer mas acerca de este tipo de códigos se recomiendan las referencias [12] y [13]. 75
76 CAPÍTULO 7. REDUCCIÓN DE CLAVES DE GABORIT Definición 7.1. 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: Proposición 7.2. 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. Demostración. ⇒)Sea Cun código cíclico, la aplicación ϕnos permite identificar Ccomo un subconjunto de Fq[x]/hxn−1i. Ademas, Ces un subespacio lineal cerrado para las operaciones de suma y producto por escalares. Si vemos que si c∈Cyx∈Fq[x]/hxn−1i entonces cx ∈Ctenemos demostrado que Ces un ideal, ya que tenemos entonces que si f(x) = a1+a2x+... +anxn−1∈Fq[x]/hxn−1ies un polinomio cualquiera de grado menor que n,ai∈Fq∀i=1, ..., n, se tiene que c f ∈Cporque al tener que cx ∈Ctenemos que cx2∈Cy de forma sucesiva tenemos que cxi∈C∀i=0, ..., n−1. Ademas, también tenemos que ai+1cxi∈Cpor ser Ccerrado para el producto por escalares y entonces c f (x) = a1c+a2cx +... +an+1cxn∈Cal ser Ccerrado para la suma de palabras del código C. Empleando el isomorfismo ϕtenemos que cx =c1x+...cnxn=c1x+...cn(xn−1) + cn=cn+... +cn−1xn−1∈C que es lo que faltaba por demostrar para tener que Ces un ideal de Fq[x]/hxn−1i. ⇐)Sea Cun ideal de Fq[x]/hxn−1i, es evidente que es un subespacio lineal, debido a la definición de ideal. Ademas, sea c= (c1, ..., cn)∈C, sabemos que cx ∈Cpor ser Cun ideal y razonando igual que en la otra implicación, tenemos que cx = (cn,c1,..., cn−1)y por tanto Ces un código cíclico como queríamos. Ahora definimos los códigos cuasi-cíclicos, que son mas generales que los códigos cíclicos. Definición 7.3. Sea Cun código lineal de parámetros [n,k], diremos que Ces un código cuasi-cíclico de orden s, donde ses un divisor de n, si todo cambio cíclico de s coordenadas es de nuevo una palabra del código, es decir, si (c1, ..., cn)∈Centonces se tiene que (cn−s+1, ..., cn,c1, ..., cn−s)∈C.
7.1. INTRODUCCIÓN 77 Nota 7.4. Si el orden del código cuasi-cíclico es s=1 entonces se corresponde con un código cíclico. Nota 7.5. Si Ces un código cíclico de longitud n, entonces Ctambién es cuasi-cíclico de orden s, para cualquier sque divida n. Lema 7.6. Si C es un código cuasi-cíclico de orden s, entonces C⊥también es un código cuasicíclico de orden s. Proposición 7.7. Sea C un código cuasi-cíclico de parámetros [n,k]de orden s con n =rs. Entonces existe una matriz G de tamaño k0×n, donde k0≥k, que genera el código C y es de la forma G= A1A2· · · Ar ArA1· · · Ar−1 . . .. . ..... . . A2A3· · · A1 donde Aies una matriz de tamaño k0 r×s∀i=1,...,r. Demostración. Sea c= (c1, ..., cn)∈Cuna palabra del código Carbitraria. Como Ces cuasi-cíclico de orden s, separamos cen r=n spartes iguales obteniendo (c1, ..., cs),(cs+1,..., c2s),..., (cn−s+1,..., cn). Llamamos A1 i= (cs(i−1)+1, ..., cis)con 1≤i≤ry consideramos la matriz G1definida de la forma G1= A1 1A1 2· · · A1 r A1 rA1 1· · · A1 r−1 . . .. . ..... . . A1 2A1 3· · · A1 1 la cual, genera un código, que llamamos C1. Si C1=Centonces estaría probado y sabemos cuales son los Ai. Si C16=Cconsideramos otra palabra del código c0∈Ccualquiera que cumpla que c0/∈C1. Separando c0en rpartes iguales de igual forma que hemos realizado para cy tomando las matrices A2 iformadas respectivamente por la matrices A1 i(en este primer caso son vectores) a las que se añade una fila formada por cada una de las partes en que hemos dividido el vector c0, es decir A2 i=A1 i c0i donde c0i= (c0 s(i−1)+1, ..., c0 is)con 1 ≤i≤rhace referencia a la parte i-esima en que hemos dividido el vector c0.
78 CAPÍTULO 7. REDUCCIÓN DE CLAVES DE GABORIT A partir de estas matrices, A2 ipodemos construir la matriz G2que genera un código C2. Realizando la misma comprobación que antes, continuamos realizando este proceso iterativo. Ademas, como el rango de las matrices Gjva incrementándose de forma estricta según incrementa j, esto nos garantiza que podemos parar el proceso en la iteración j0, la cual verifica que k0=rj0≥kya que la matriz Gj0genera el código C. Nota 7.8. Obviamente, para conocer la matriz Gdescrita en la proposición 7.7, la cual nos permite conocer el código C, es suficiente con conocer las matrices A1,..., An. Nota 7.9. La matriz Ggenera el código Cpero no tiene porque cumplirse que sea una matriz generatriz del código C, ya que esto solo ocurrirá en el caso particular en que k0=k. Proposición 7.10. Sea C un código cuasi-cíclico de parámetros [n,k]y orden s, con n = rs, entonces existen subcódigos cuasi-cíclicos contenidos estrictamente en C, de orden s con dimensión mayor o igual a k −r=k−n s Demostración. Sea C⊥el código dual de C, que por el lema 7.6 sabemos que es también un código cuasi-cíclico y de orden s. Tomamos un vector xen Fn q\C⊥y construimos la matriz Gxformada por la matriz generatriz de C⊥a la que añadimos rfilas, que son el vector xjunto con las r−1 posibles permutaciones de orden sque se realizan al vector x. Llamamos Cxal código generado por la matriz Gxel cual es por construcción un código cuasi-cíclico de orden sy de dimension a lo sumo n−k+r. Tomando ahora el código dual de Cxtenemos entonces que es también un código cuasi-cíclico de orden sy con dimensión mayor o igual a k−rcomo queríamos ver. Proposición 7.11. Sea C un código cuasi-cíclico de parámetros [n,k]entonces al menos 2k−r códigos distintos pueden ser construidos por la proposición 7.10, donde r =n s. Demostración. Según la demostración realizada en la proposición 7.10, es evidente que la cantidad de los distintos subcodigos es equivalente a la cantidad de los distintos códigos duales de estos subcodigos. Como la unión de todos los posibles duales debe ser todo el espacio y cada código tiene dimension a lo sumo de n−k+r, entonces hay al menos 2n−(n−k+r)=2k−r subcodigos cuasi-cíclicos distintos 7.2. Método de reducción de claves A partir de las propiedades descritas, es evidente que si partimos de un código cuasi-cíclico Cde parámetros [n,k]y orden s, podemos obtener una matriz generadora,
7.2. MÉTODO DE REDUCCIÓN DE CLAVES 79 G, de la forma vista en la proposición 7.7, la cual se puede obtener con las matrices Ai descritas, y por tanto el tamaño de la clave pública se reduce de forma notable. Si consideramos ademas una permutación de scoordenadas, la cual es semejante a considerar una matriz de permutación de tamaño sque denotamos por π. Aplicamos dicha permutación sobre cada fila de las k0 rposibles de cada una de las matrices Ai, que tienen scoordenadas cada una, i=1,..., r. Obtenemos entonces una matriz enmascarada que llamamos G0, la cual se sigue pudiendo obtener únicamente del conocimiento de las matrices Aiy la matriz de permutación π: G0= A1πA2π· · · Arπ ArπA1π· · · Ar−1π . . .. . ..... . . A2πA3π· · · A1π Por tanto, nuestra clave pública será el conjunto de matrices Aisobre las que se ha aplicado la permutación π, a partir de las cuales podemos obtener la matriz G0. Obviamente, esta matriz no siempre nos permite realizar el cifrado de los mensajes, ya que k0≥k. Por tanto, tenemos que obtener una matriz generatriz (enmascarada) y única del código cuasi-cíclico que estamos empleando, que denotaremos M, para poder realizar el cifrado. Para su obtención, consideramos el vector v1formado por las coordenadas de la primera fila de la matriz G0, es decir, por las coordenadas de la primera fila de todas las matrices Aiπ. Por tanto, el vector v1tiene longitud n=rs. Ahora consideramos la matriz M1(para este primer caso es un vector) formada por el vector v1. Entonces tomamos el vector v0 1obtenido al realizar una permutación de scoordenadas aplicada a las rdivisiones del vector v1de scoordenadas cada una. Si el vector v0 1no pertenece al código generado por M1entonces se considera la matriz M2obtenida por la adicción de la fila v0 1a la matriz, M1que teníamos anteriormente. Repitiendo este proceso de permutación de scoordenadas sobre el vector v1rveces obtenemos la matriz Mr obtenida a partir del vector v1. Repetimos el mismo proceso ahora para el vector v2 formado por las coordenadas de la segunda fila de G0, teniendo en cuenta en adicción que para cada vector v0 2obtenido al realizar una permutación, debe cumplir que es independiente de las filas que tenemos en la matriz Mractualmente. Reiterando este proceso para las k0 rprimeras filas de la matriz G0, que se corresponden con todas las filas de las matrices Ai, obtenemos como resultado la matriz M, que es única y cumple que tiene un total de kfilas, ncolumnas y genera el código cuasi-cíclico enmascarado. Esta matriz es la que emplearemos para cifrar los mensajes. En conclusión, tenemos que el método de criptosistema de McEliece descrito pre-
80 CAPÍTULO 7. REDUCCIÓN DE CLAVES DE GABORIT senta las siguientes propiedades: 7.2.1. Generación de claves La clave publica consiste en las primeras k0 rfilas de la matriz G0correspondientes con las matrices Aiπcon i=1,..., r, es decir, el conjunto de matrices, Ai, que generan la matriz Gsobre las que se ha aplicado la matriz de permutación, π. Ademas, la clave pública también consta del numero de errores que es capaz de corregir el código, t, así como del orden del código cuasi-cíclico que estamos empleando. La clave privada consiste simplemente en la matriz de permutación πque hemos empleado para enmascarar las matrices Aicon i=1, ...,r. 7.2.2. Cifrado El proceso de cifrado de un mensaje xse realiza calculando la matriz Ma partir de la matriz G0que se obtiene de la clave pública. Una vez que poseemos la matriz M, el cifrado consiste simplemente en calcular c=xM +e, donde ees un vector de errores de peso máximo t, siendo tla capacidad correctora del código que estamos empleando. Entonces el vector ces el mensaje cifrado, y es por tanto el vector que enviamos al receptor. 7.2.3. Descifrado El proceso de descifrado de un mensaje cse realiza también calculando la matriz M a partir de la matriz G0que se obtiene de la clave pública. Entonces mediante la clave privada, calculamos la matriz de permutación inversa total, Π−1, siendo Πla matriz que realiza la misma permutación cada scolumnas un total de rveces: Π= π0· · · 0 0π· · · 0 . . .. . ..... . . 0 0 · · · π Entonces obtenemos cΠ−1=xMΠ−1+eΠ−1. Ahora, aplicamos el algoritmo de corrección de hasta terrores del código que estamos empleando obteniendo xMΠ−1, y entonces recuperamos el mensaje original, x.
7.3. CRIPTOANÁLISIS DEL MÉTODO 81 7.2.4. Tipo de códigos sugeridos Una vez descrito el criptosistema, tenemos que encontrar una familia densa de códigos que sean cuasi-cíclicos de orden s, resistentes a los ataques conocidos en la actualidad como por ejemplo, el ataque de filtración que hemos explicado en el capítulo 6, el ataque de Sidelnikov y Shestakov [8] o el ataque de Stern [14] entre otros existentes. También deben ser códigos que se puedan codificar y descodificar rápidamente. Para ello Gaborit propuso en [10] usar la familia de códigos BCH, los cuales verifican las condiciones impuestas, y en especial, el uso de códigos BCH primitivos de longitud n=2m−1 ya que obtenemos códigos con mejores parámetros que los códigos BCH que no son primitivos. Por tanto, se utilizaban el conjunto de subcódigos cuasi-cíclicos de orden sde un código BCH, los cuales se construían como se mostró en la proposición 7.10 7.3. Criptoanálisis del método El desarrollo del criptosistema de McEliece aplicando el método visto en la sección 7.2 habría supuesto un gran avance para el empleo del McEliece, debido a que solventa su principal problema, que es el elevado tamaño de las claves. Sin embargo, en 2010 Otmani, Tillich y Dallot presentan un artículo[15] en el que criptoanalizan exitosamente el criptosistema que utiliza dicho método y emplea los subcodigos de un código BCH primitivo, ademas de otro criptoanalisis que emplea códigos cuasi-cíclicos con matrices de control de baja densidad (LDPC). Nosotros nos centraremos en mostrar el criptoanalisis realizado sobre los subcódigos de un código BCH primitivo, cuya debilidad se encuentra en la obtención de una gran cantidad de ecuaciones lineales que tienen que cumplir las entradas de la matriz de permutación secreta debido a que se emplea como código secreto subcódigos de un código BCH, el cual puede considerarse conocido aunque en principio no lo sea como veremos mas adelante. A partir de esto, es posible recuperar la matriz secreta de permutación, Π, que se esta empleando en dicho criptosistema y por tanto obtenemos la clave privada del criptosistema. Veamos el método que hay que emplear para obtener la matriz de permutación Π. Sea C0un código BCH primitivo cuasi-cíclico de orden s, de longitud n=rs y dimension k=rk0, el cual admite una matriz de control, H0, de tamaño (n−k)×nla cual puede considerarse que es conocida. Esto es debido a que hay muy pocos códigos BCH primitivos para un conjunto de parámetros establecidos, [n,m,t]a priori, en
88 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES c5= (0,0,0, 1,0,0, 1,0,0) c6= (1,1,1, 0,1,1, 0,1,1) c7= (1,1,1, 1,1,1, 0,1,0) c8= (0,0,0, 1,0,0, 0,0,1) c9= (1,1,1, 0,1,1, 1,1,0) c10 = (0,0, 0, 0,0,0, 0,1,1) c11 = (1,1, 1, 1,1,1, 1,0,0) c12 = (0,0, 0, 1,0,0, 1,1,1) c13 = (1,1, 1, 0,1,1, 0,0,0) c14 = (1,1, 1, 1,1,1, 0,0,1) c15 = (0,0, 0, 1,0,0, 0,1,0) c16 = (1,1, 1, 0,1,1, 1,0,1) Ahora vamos a realizar el cálculo de una matriz generatriz de C,G. Para ello, tomamos una matriz generatriz de cada uno de los códigos Ci,i=1,2,3 G1=1 1 1 G2=1 0 0 G3=1 0 1 0 1 1 Entonces, a partir de las matrices G1,G2yG3, la matriz generatriz de Ces G= 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 Definición 8.3. Sea Auna matriz M×N, denotamos A(j1,..., jt)a la matriz cuadrada de tamaño tformada a partir de las tprimeras filas de la matriz Ay las columnas j1,..., jt, donde 1 ≤j1<· · · <jt≤Ncon 1 ≤t≤M. Nota 8.4. Si A(1,..., M)es no singular, la matriz N×Mcuyas Mprimeras filas son las de la matriz A(1, ..., M)−1y las N−Multimas filas son nulas, es una matriz inversa de la matriz A. Proposición 8.5. Sean C1,...,CMcódigos lineales y A una matriz M ×N.
8.1. INTRODUCCIÓN 89 1) Si Aπes una matriz obtenida al realizar una permutación de las filas de la matriz A, entonces se tiene que [C1· · · CM]·A es un código equivalente a [Cπ(1)· · · Cπ(M)]·Aπ. 2) Si Aρes una matriz obtenida al realizar una permutación de las columnas de la matriz A, entonces se tiene que [C1· · · CM]·A es un código equivalente a [C1· · · CM]·Aρ Demostración. 1) Si πes la permutación realizada, como las palabras del código de C1,...,CMse corresponden con columnas para el código de producto de matrices, las cuales se multiplican por la matriz Aπque ha sufrido las mismas permutaciones para las filas de la matriz A. Por tanto se realizan las mismas multiplicaciones y sumas tanto en [C1· · · CM]·Acomo en [Cπ(1)· · · Cπ(M)]·Aπ, obteniendo palabras del código equivalentes al tener únicamente cambiado el orden de las coordenadas y por tanto son códigos equivalentes. 2) Si ρes una permutación sobre las columnas de A, tenemos que únicamente se cambia el orden de las coordenadas de las palabras del código de producto de matrices y por tanto, obtenemos que [C1· · · CM]·Ay[C1· · · CM]·Aρson también códigos equivalentes. Proposición 8.6. Sea A una matriz M ×N. Si tenemos una matriz formada por M columnas de A que es no singular entonces se verifica que |[C1· · · CM]·A|=|C1| · · · |CM| Demostración. Podemos suponer sin perdida de generalidad que A(1, ..., M)es no singular, por el resultado obtenido en la proposición 8.5. Consideramos la aplicación φ:C1× · · · × CM→[C1· · · CM]·A (c1, ..., cM)7−→ [c1· · · cM]·A Si vemos que φes una biyección estaría probado. Claramente φes sobreyectiva según la construcción realizada de la aplicación y la definición del código de producto de matrices. En cuanto a la inyectividad, consideramos que [c1· · · cM]·A= [c0 1· · · c0 M]·A. Como A(1,..., M)es no singular, existe A(1,..., M)−1y también existe la matriz A−1, de tamaño N×M. Por tanto, Aes no singular y entonces multiplicando a ambos lados por A−1ob- tenemos que [c1· · · cM] = [c0 1· · · c0 M]. Por ello, tenemos que (c0 1, ..., c0 M) = (c1, ..., cM) como queríamos.
90 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES A partir de lo que hemos visto hasta ahora, podemos observar que hemos obtenido tanto la longitud del código [C1· · · CM]·A, como su cardinalidad y dimensión. Sin embargo, para obtener la distancia mínima de dicho código vamos a introducir primero el concepto de matriz no singular por columnas y matriz triangular, que nos será útil mas adelante. Definición 8.7. Dada una matriz Ade tamaño M×N, diremos que Aes una matriz no singular por columnas (NSC) si A(j1,..., jt)es no singular para cada 1 ≤t≤My 1≤j1<· · · <jt≤N. 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. Otro ejemplo de matriz no singular que no es NSC sería la matriz Aempleada en el ejemplo 8.1. Definición 8.8. Diremos que un código de producto de matrices es NSC si la matriz A asociada al código es NSC. Para enunciar la siguiente proposición es necesario indicar la construcción de los códigos CRi, con i=1,..., M. Fijado un i, el código CRies el que tiene como matriz generatriz, que denotaremos por Ai, la formada por las iprimeras filas de la matriz A. Proposición 8.9. Dada una matriz A de tamaño M ×N, verifica que es NSC si y solo si los códigos CRison MDS ∀i=1,..., M. Demostración. Si la matriz Aes NSC sabemos por definición que A(j1,..., jt)es no singular para cada 1 ≤t≤My 1 ≤j1<· · · <jt≤N. Por otro lado, fijado r∈ {1,..., M}, consideramos la matriz generatriz Ar, correspondiente al código CRr. Como la matriz Aes NSC, es evidente que todos los determinantes correspondientes a las matrices de los menores principales de Arson distintos de cero, luego la matriz Ares no singular. Esto nos permite concluir que el código CRr es MDS, ya que al ser Arno singular es de máximo rango y por tanto sus columnas son linealmente independientes. Sabemos por [22, Corolario 3, capítulo 11] que las
8.1. INTRODUCCIÓN 91 columnas de Arson linealmente independientes si y solo si el código CRres MDS. Como esta demostración es válida para r∈ {1, ..., M}se tiene entonces lo que se quería demostrar. Definición 8.10. 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 8.11. Una matriz triangular NSC A de tamaño M ×N tiene exactamente i −1 ceros en la i-esima fila, con 1≤i≤M. Demostración. Obviamente, al ser una matriz triangular, en la fila i-esima debe tener al menos i−1 ceros. Veamos ahora que no puede tener mas que i−1 ceros. Supongamos que existe una fila, i, que tiene mas de i−1 ceros. Si consideramos la matriz A(j1,..., ji), donde las posiciones j1,..., jison las posiciones que hacen referencia a un termino nulo dentro de la fila i, es decir, aij1=... =aiji=0. Tenemos que dicha matriz tiene una fila nula y por tanto det(A(j1,..., ji)) = 0, lo cual es absurdo ya que por hipótesis la matriz Aes NSC. 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 Acomo hemos definido anteriormente. Por tanto, CRi=hR1,..., Rii, y denotamos por Dila distancia del código CRi. Proposición 8.12. 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. Demostración. Tomamos cuna palabra cualquiera del codigo C, entonces podemos escribir c= [c1· · · cM]·Adonde cihace referencia a un vector columna de tamaño n. Consideramos que ci6=0∀i=1, ...,ryci=0∀i=r+1,..., Mentonces tenemos que
92 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES c= c11 c12 · · · c1r0· · · 0 c21 c22 · · · c2r0· · · 0 . . .. . ..... . .. . ..... . . cn1cn2· · · cnr 0· · · 0 a11 a12 · · · a1N a21 a22 · · · a2N . . .. . ..... . . aM1aM2· · · aMN = c11a11 +· · · +c1rar1· · · c11a1N+· · · +c1rarN . . ..... . . cn1a11 +· · · +cnrar1· · · cn1a1N+· · · +cnrarN Entonces podemos observar que los elementos de cestán formados por componentes de la matriz Adesde la primera fila hasta la fila Rr. Por tanto si denotamos (ch1, ..., chM)la fila hde [c1· · · cM], tenemos que (ch1, ..., chM)·A∈CRr∀h=1, ..., n. Como ci6=0∀i=1,...,rentonces debe tener al menos drcoordenadas distintas de cero. A partir de esto consideramos ciur6=0 siendo u=1, ..., drentonces tenemos que (ciu1, ..., ciuM)·Apertenece a CRry es distinto de cero, ya que la única opción de que fuera 0 sería si la matriz Ano tiene rango máximo, entonces el peso mínimo debe ser mayor o igual que Dry como Crtiene distancia mínima drentonces se tiene que d(c)≥dr∗Dr. Por tanto, variando el r, obtenemos que d(C)≥min{d1∗D1,d2∗ D2,..., dM∗DM}como queríamos. Nota 8.13. 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. Además 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 exacta de errores máxima que podemos corregir.
8.1. INTRODUCCIÓN 93 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 8.14. 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} Demostración. Por la proposición 8.12 sabemos que se cumple que d(C)≥min{d1∗D1,d2∗D2, ..., dM∗DM} Por tanto, si vemos que existe una palabra del código de producto de matrices verificando la igualdad, obtendremos la igualdad para la distancia del código de producto de matrices. Por ello, tomamos c∈C, la cual, es de la forma [c1· · · cM]·Acumpliendo, para un r∈ {1, ..., M}fijo, que c1=c2=... =cr, con ω(c1) = drycr+1=... =cM=0. La hipótesis de c1=c2=... =cres valida al ser los códigos encajados. Si tomamos ahora una palabra, b, del código CRrde peso Dr, podemos expresar bcomo combinación lineal de los vectores Ricon i=1,...,r, es decir, b=∑r i=1wiRi, siendo wi∈Fq. Tomando c0 i=wicitenemos que ( M ∑ i=1 ai1c0 i,..., M ∑ i=1 aiNc0 i) = ( M ∑ i=1 ciai1wi,..., M ∑ i=1 ciaiNwi) Ahora teniendo en cuenta que c1=c2=... =cr,cr+1=... =cM=0 podremos sacar factor común a c1y el sumatorio esta limitado superiormente por rya que los siguientes términos serían nulos. Además como Ri= (ai1,..., aiN)tenemos que ( M ∑ i=1 ciai1wi,..., M ∑ i=1 ciaiNwi) = c1( r ∑ i=1 ai1wi,..., r ∑ i=1 aiNwi) = c1( r ∑ i=1 wiRi) = c1b que es una palabra del código Ccon peso drDr
94 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES 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. Teorema 8.15. 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∗ Demostración. 1) Es evidente a partir de la proposición 8.6 ya que sabemos que si Aes una matriz NSC entonces Aes una matriz no singular. 2) Como Aes una matriz NSC, sabemos por la proposición 8.9 que los códigos CRison MDS ∀i=1, ..., My por tanto sabemos por la cota de Singleton que la distancia es Di=N−i+1 y entonces por la proposición 8.12 tenemos lo que queríamos. 3) Sea Auna matriz triangular. Entonces como sabemos por la proposición 8.5 que permutaciones de las columnas de la matriz Aproporcionan códigos de produc- to de matrices equivalentes, podemos suponer, sin perdida de generalidad que Aes una triangular superior. Sea (N−t+1)dtel valor mas pequeño de los valores (N−i+1)diy sean c,c0∈ Ccon ct,c0 t∈Cttal que d(ct,c0 t) = dtyci=c0 i∀i6=t. Entonces d(c,c0)≤ d(ctatt,c0 tatt) + d(ctatt+1,c0 tatt+1) + · · · +d(ctatN,c0 tatN)≤(N−t+1)dt. Luego hemos encontrado dos palabras del código Cque tienen como distancia mínima a lo sumo d∗. Entonces por la parte 2)del teorema tenemos la igualdad. Ejemplo 8.2. Consideramos los códigos C1,C2,C3y la matriz Adel ejemplo 8.1. Claramente, vemos que la matriz Aes triangular, sin necesidad de realizar ninguna permutación. Sin embargo, no es NSC al existir un determinante de orden 2 que es nulo. Por tanto, la desigualdad obtenida en la proposición 8.12 no es igualdad según lo visto en el teorema 8.15.
8.2. DESCODIFICACIÓN 95 Las distancias de los códigos considerados se obtienen en este caso fácilmente a partir del mínimo peso de Hamming de las palabras de cada código, las cuales son respectivamente d1=3, d2=1, d3=2. Por tanto, si reordenamos los códigos de la forma C0 1=C2,C0 2=C3yC0 3=C1 obtenemos que d0 1≤d0 2≤d0 3y la distancia del código de producto de matrices C= [C0 1C0 2C0 3]·Aes d(C)≥d∗=min{3∗1, 2 ∗2,1 ∗3}=3, donde d∗es el máximo valor que se puede alcanzar a partir de los códigos C1,C2,C3dados, lo cual se puede verificar rápidamente en el ejemplo, ya que si tomamos otra ordenación de los códigos donde C1no sea el último código escogido, tendremos que la última multiplicación dentro del mínimo a realizar para obtener la distancia vale o 2 o 1 y por tanto la distancia obtenida es menor. Se puede razonar de forma semejante para el código intermedio, lo cual nos lleva a la ordenación elegida al comienzo para tener la máxima distancia posible del código de producto de matrices generado a partir de los códigos C1,C2,C3considerados. De hecho podemos observar, que no existe ninguna matriz cuadrada de tamaño 3 formada por elementos de F2que sea NSC ya que, según la proposición 8.11, la primera fila de la matriz no puede tener ningún elemento nulo y la segunda fila solo puede tener un cero, por tanto, siempre existirá un determinante de orden dos formado únicamente por elementos con valor 1, es decir, su determinante será nulo. 8.2. 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 8.15, o si utilizamos códigos encajados para la generación de los códigos de producto de matrices según lo visto en el teorema 8.14. Ahora nos preguntamos si podemos emplear los códigos de productos de matrices en el criptosistema de McEliece. Hasta el momento, hemos visto como obtener una matriz generatriz para estos códigos, así como realizar una codificación. 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
96 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES 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 Si tomamos ahora una palabra del código producto de matrices c∈C, se cumple que c= (∑M j=1aj1cj, ..., ∑M j=1ajNcj)donde cj∈Cj∀j=1,..., M. Como los elementos de la matriz Apertenecen a Fqtenemos que ∑M j=1ajhcj, con h= 1,..., N, es una combinación lineal de una palabra de cada código Ci, con i=1,..., M, y como CM⊂ · · · ⊂ C2⊂C1, todas son palabras del código C1, por tanto, ∑M j=1ajhcj, con h=1,..., N, también es una palabra del código C1. Debido a esto, es evidente que podríamos emplear el algoritmo de descodificación DC1sobre los Nbloques que constituyen la palabra de código c. Pero como tenemos que C1⊃ · · · ⊃ CMse verifica que d1≤d2≤ · · · ≤ dMy entonces también se cumple que t1≤t2≤ · · · ≤ tM. Por tanto, seriamos capaces de corregir como máximo t1errores en cada bloque de una palabra del código, es decir, t1Nerrores en total. Sin embargo, estos errores deben están distribuidos de forma que haya a lo sumo t1 errores en cada bloque, si esto no ocurre, la descodificación fallaría. Por tanto, de esta forma para poder garantizar que la descodificación siempre se realiza exitosamente, el número máximo de errores que tenemos que tomar es de t1y por tanto, la capacidad correctora del código producto de matrices es de t1errores. Por ello, 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 8.14 o el teorema 8.15. Para este método 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∈Cye es un vector de errores de longitud nN con un peso menor o igual a la capacidad máxima 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, ademas de la palabra yque queremos descodificar. Algoritmo 8.16. 1 : y0=y;
8.2. DESCODIFICACIÓN 97 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; 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. Ademas, 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.
104 CAPÍTULO 8. CÓDIGOS DE PRODUCTOS DE MATRICES Ahora a partir de los distintos bloques obtenidos podemos recuperar el vector de error ea partir de la unión de los bloques e1,e2ye3: e1=y3) 1−y4) 1= (0,3, 0,2,0,0,6,0,0, 7,0,11) e2=y2−y2) 2= (0,0,0,0,0,0,0,0,0, 0,0,0) e3=y2) 3−y3) 3= (0,0,0,0,0,0,0,0,0, 0,0,0) A partir del error podemos recuperar ya el mensaje codificado sin errores, c, y después recuperar el mensaje mresolviendo, al igual que hemos hecho en los ejemplos de otros códigos lineales, un sistema.
Capítulo 9 McEliece con codigos de productos de matrices 9.1. Introducción En el capítulo 8, hemos introducido los códigos de producto de matrices, para los cuales hemos indicado como obtener sus distintos parámetros. Además, es posible construir el criptosistema de McEliece visto en la sección 5.1 empleando en lugar de los códigos de Goppa binarios, los códigos de producto de matrices gracias al algoritmo de descodificación de dichos códigos visto en la sección 8.2, los cuales deben cumplir unas restricciones para que se pueda emplear dicho algoritmo. De todas formas, usaremos códigos de Goppa para la construcción del código de producto de matrices que emplearemos para generar el criptosistema de McEliece, ya que sabemos que los códigos de Goppa no han sido criptoanalizados exitosamente en la actualidad y por lo tanto son seguros. Sin embargo, podemos observar que si empleamos los códigos de producto de matrices utilizando la matriz generatriz obtenida a partir de la forma vista en la nota 8.2, seguimos teniendo la principal desventaja del criptosistema de McEliece que tenemos independientemente del código que empleemos para su construcción, correspondiente al tamaño de las claves pública y privada. Sin embargo, vamos a presentar a continuación una nueva versión del criptosistema de McEliece, la cual permite reducir el tamaño de las claves pública y privada cuando empleamos para la construcción del criptosistema de McEliece un código de producto de matrices. En el capítulo 7 y en [10] vimos como Gaborit realizó una reducción en las claves del criptosistema de McEliece mediante el empleo de códigos cuasi-cíclicos. Para 105
106 CAPÍTULO 9. MCELIECE CON MPC ello, generaba la matriz generatriz a partir de pequeñas submatrices. La versión que presentamos ahora trata de reducir las claves del criptosistema empleando una idea parecida a la empleada por Gaborit pero utilizando los códigos de productos de matrices, lo cual permite evitar el ataque mostrado en [15] como vemos a continuación en la nota 9.1. Vimos que la matriz generatriz del código de producto de matrices se generaba a partir de las matrices generatrices de los subcodigos empleados y la matriz A. A partir de esto, vamos a ver como es posible generar la clave pública a partir de dicha matriz Ay las matrices generatrices enmascaradas de los subcodigos. Para ocultar dichas matrices generatrices, emplearemos para cada matriz generatriz, una matriz invertible aleatoria S0y una matriz de permutación π. Dicha matriz de permutación coincide para todas las matrices generatrices, y por tanto es una matriz de permutación similar a la empleada por el método de Gaborit vista en la sección 7.2.3, lo cual es posible al tener todos los subcodigos empleados en el código de producto de matrices la misma longitud. Sin embargo, las matrices invertibles S0son distintas incluso en el tamaño, ya que son matrices cuadradas cuyo tamaño debe coincidir con la dimensión del código cuya matriz generatriz queremos ocultar. Nota 9.1. Aunque la propuesta presentada por Gaborit fue criptoanalizada exitosamente, permitiendo recuperar la matriz de permutación Πempleada para ocultar la matriz generatriz del código cuasi-cíclico, para los códigos de productos de matrices es posible evitar dicho ataque empleando subcodigos que no sean los códigos BCH, los cuales eran los que presentaban la debilidad que permitía realizar dicho ataque. Para la presentación del nuevo criptosistema de McEliece empleamos para los subcodigos códigos de Goppa. Por tanto, es posible mostrar el criptosistema ocultando la matriz generatriz del código de producto de matrices únicamente con la matriz de permutación Πde igual forma que en la versión mostrada por Gaborit, pero sin poder realizar el ataque que lo hace vulnerable. Sin embargo, nosotros emplearemos además de la matriz de permutación Π, una matriz invertible Sconstruida a partir de todas las matrices invertibles empleadas para cada matriz generatriz de los subcodigos empleados, para preservar el esquema original del criptosistema de McEliece. Aunque obviamente, tomando como matriz invertible Sla matriz identidad, obtenemos como caso particular la versión que solo emplea la matriz de permutación. 9.2. El nuevo criptosistema de McEliece Vamos a introducir ahora como realizar la generación de claves, así como el proceso a seguir para realizar el cifrado y descifrado.
9.2. EL NUEVO CRIPTOSISTEMA DE MCELIECE 107 9.2.1. Generacion de claves Para la generación de las claves, vamos a emplear un código producto de matrices [C1· · · CM]·Aformado por una matriz Ano singular por columnas cuadrada de tamaño MyMcódigos de Goppa binarios encajados, todos ellos de longitud n, de los cuales conocemos un algoritmo de descodificación que hemos visto en la sección 4.2.1. Los códigos de Goppa encajados, ademas de haber una gran cantidad de ellos, son fáciles de conseguir, ya que para obtenerlos, según la nota 4.3, solo hay que estudiar la divisibilidad entre los polinomios de Goppa de los distintos códigos. Ahora obtenemos una matriz generatriz, Gi, de cada uno de los Mcódigos de Goppa. Generamos una matriz de permutación aleatoria cuadrada de tamaño n,π, la cual emplearemos para permutar las ncolumnas de todas las matrices generatrices. También generamos para cada matriz generatriz Gi, una matriz invertible aleatoria cuadrada de tamaño ki,Si, donde kihace referencia a la dimensión del código de Goppa Ci. A partir de las matrices Gi,Siyπobtenemos la clave pública, que constará de la matriz A, las Mmatrices obtenidas al enmascarar las matrices Gi, es decir, las matrices G0 i=Si·Gi·π, con 1 ≤i≤My la capacidad correctora del código de producto de matrices C,t. En cuanto a la clave privada, estará formada por la matriz de permutación π, las M matrices generatrices, las Mmatrices invertibles Siy el algoritmo de descodificación del código de producto de matrices, ϑ, por tanto, consta de los algoritmos de descodificación de los Msubcodigos. En resumen, tenemos que las claves pública y privada, denotadas respectivamente por κpyκsestán constituidas por: κp= (A,G0 1, , · · · ,G0 M,t)yκs= (G1,· · · ,GM,π,S1,· · · ,SM,ϑ) Por tanto, podemos observar que el tamaño de dichas claves es inferior en cuanto trabajemos con códigos con parámetros elevados al tener que almacenar matrices de tamaño inferior respecto a la matriz generatriz enmascarada, G0, del código de producto de matrices y las matrices SyPque es necesario emplear en el criptosistema original de McEliece. 9.2.2. Cifrado Para realizar el cifrado de un mensaje empleando dicho criptosistema tenemos que emplear las distintas matrices que nos proporcionan a partir de la clave pública para generar una matriz que se corresponde con la matriz generatriz enmascarada G0.
108 CAPÍTULO 9. MCELIECE CON MPC Para ello simplemente construimos la matriz de igual forma que se realizaba la construcción de la matriz generatriz de los códigos producto de matrices visto en la nota 8.2 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 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. 9.2.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∗M, similar a la empleada por Gaborit en la versión vista en la sección 7.2.3, y 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. A partir de estas matrices podemos realizar ya la descodificación de forma semejante a la versión original presentada por McEliece, que vimos en la sección 5.1.3, es decir, multiplicando el mensaje cifrado por la matriz de permutación inversa, Π−1, obteniendo que y·Π−1=m·S·G+e·Π−1.
9.2. EL NUEVO CRIPTOSISTEMA DE MCELIECE 109 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 8.2, 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 el criptosistema de McEliece original. En cuanto a los códigos empleados para la construcción del código de producto de matrices, se expone en esta versión el empleo de códigos de Goppa binarios ya que, ademas de la facilidad de obtener códigos de Goppa binarios encajados y la gran cantidad que existe de ellos, presentan una buena seguridad, al ser códigos que todavía no han sido criptoanalizados exitosamente con la version original del criptosistema de McEliece. 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 8.12, 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.8. Vamos a mostrar a continuación un ejemplo para el cual implementaremos el nuevo criptosistema de McEliece y lo compararemos con un criptosistema de McEliece que emplee un código de Goppa binario para su construcción. Ejemplo 9.1. Para este ejemplo emplearemos la construcción de Plotkin como código de producto de matrices. Por tanto, tenemos que la matriz Aes: A=1 1 0 1 En cuanto a los códigos que utilizamos para la construcción del código producto de matrices, tomamos dos códigos de Goppa, ambos de longitud 25=32, donde el vector Lesta formado por todos los elementos del cuerpo F25en ambos casos. Junto con el vector L, tenemos que el código C1se forma a partir del polinomio de grado 3, g1(x) = x3+ (α4+α2+1)x+α3+α2+α+1 y C2a partir del polinomio de grado 6, g2(x) = x6+ (α3+α2)x4+ (α2+α)x3+ (α4+α3+α+1)x2+ (α4+α3+α2+α+ 1)x+α4+α3, siendo αun elemento primitivo de F25.
110 CAPÍTULO 9. MCELIECE CON MPC Ahora formamos el código de producto de matrices, C, a partir de los códigos C1yC2y la matriz A. Entonces, el código Ctiene como parámetros fundamentales [64,20,13]ya que los parámetros fundamentales de C1yC2son respectivamente [32,17,7]y[32,3,13] Como g1|g2entonces se cumple que C2⊂C1y por tanto podemos emplear el algoritmo de descodificación visto en la sección 8.2. Obviamente, la matriz generatriz del código C1,G1, tiene tamaño 17 ×32 y la matriz generatriz del código C2,G2, tiene tamaño 3 ×32, luego la matriz generatriz, G, de Ctiene tamaño 20 ×64. Generamos ahora una matriz de permutación, π, cuadrada de tamaño 32 y dos matrices invertibles cuadradas S1yS2de tamaño 17 y 3 respectivamente. Entonces, a partir de todas las matrices anteriores, podemos construir las matrices G0 1=S1·G1·πyG0 2=S2·G2·π. Con ellas, tenemos todas las matrices que, junto con la capacidad correctora de C, que es t=6, y la matriz Anos permiten obtener la clave pública. De igual forma tenemos tanto las matrices como el algoritmo de descodificación necesarios para la clave privada. Ahora vamos a realizar una comparación entre el criptosistema de McEliece que acabamos de construir y otro construido empleando la versión clásica explicada en la sección 5.1. Para ello emplearemos un código de Goppa binario, C0, cuyos parámetros fundamentales sean semejantes a los que tiene el código de producto de matrices empleado, para ver que, empleando códigos con longitudes y dimensiones semejantes, y por tan- to con una redundancia del código, k n, similar, podemos construir un criptosistema de McEliece dotado de una seguridad semejante y con una importante reducción del tamaño de las claves pública y privada que tenemos que almacenar. Por tanto, consideramos C0con longitud 26=64, luego el vector Lesta formado por todos los elementos de F26. En cuanto al polinomio empleado para la construcción de C0, empleamos un polinomio irreducible de grado 7: g(x) = x7+α5+α3+α, donde α es un elemento primitivo de F26. De esta forma, obtenemos el código C0con dimensión k0=22 ≈20 =ky distancia mínima d0=15 ≈13 =d. Entonces, tenemos una matriz generatriz, G0, de tamaño 22×64, luego necesitamos una matriz de permutación, P0, cuadrada de tamaño 64 y una matriz invertible, S0, cuadrada de tamaño 22 para enmascarar la matriz G0. Por tanto, podemos observar que se reduce el tamaño de las claves pública y privada que tenemos que almacenar, ya que, de tener que guardar en la clave pública, la
9.2. EL NUEVO CRIPTOSISTEMA DE MCELIECE 111 matriz generatriz enmascarada del código C0de tamaño 22 ×64 en este caso, tenemos que almacenar una matriz de tamaño 17 ×32 y otra de tamaño 3 ×32 correspondientes a las matrices generatrices enmascaradas de los códigos C1yC2, junto con la matriz Ade tamaño 2 ×2. Entonces, realizando la construcción del criptosistema de McEliece empleando el código de Goppa binario C0, tendríamos que almacenar un total de 1408 bits o 176 bytes, mientras que empleando el código de producto de matrices para la construcción del nuevo criptosistema explicado tenemos que almacenar un total de 544 +96 +4= 644 bits o b80,5c=81 bytes, lo cual reduce prácticamente a la mitad el tamaño de la clave pública que tenemos que transmitir y almacenar. Ademas, vemos que estos resultados se obtienen a partir de un ejemplo que emplea una matriz Acuadrada de tamaño 2, es decir, que nuestro código de producto de matrices empleado se construye únicamente a partir de 2 códigos. Si empleamos en su lugar una matriz Ade mayor tamaño, de forma que el código de producto de matrices que se emplee se construya a partir de una mayor cantidad de códigos, obtendremos una clave pública total de gran tamaño, mientras que las matrices generatrices enmascaradas correspondientes a los códigos empleados para la construcción del código de producto de matrices serán bastante mas pequeñas en comparación con la matriz generatriz enmascarada total. Por tanto, para esos casos la reducción del tamaño es mayor que para el ejemplo que hemos considerado. En cuanto a la clave privada, si empleamos para la construcción del criptosistema el código de Goppa binario, C0, tenemos que almacenar las matrices G0,S0yP0junto con el algoritmo de descodificación del código. Para la matriz G0, el tamaño se reduce de igual forma que en la clave pública al corresponderse con matrices de iguales tamaños, es decir, 1408 bits con la construcción del criptosistema mediante el código de Goppa y 644 bits con la construcción mediante el código de producto de matrices. Por último, vemos que las matrices S0yP0ocupan un espacio de 484 bits y 4096 bits respectivamente, mientras que las matrices S1yS2ocupan un espacio total de 298 bits, y la matriz πocupa 1024 bits. Debido a esto, vemos que se produce una reducción de los tamaños que ocupan todas las matrices que debemos almacenar a prácticamente la mitad, lo cual nos permite emplear el criptosistema de McEliece evitando, como ya mencionamos, su principal inconveniente. Nota 9.2. Respecto a la nueva versión del criptosistema de McEliece presentada en este capítulo, podemos observar que para los códigos de producto de matrices, la matriz
112 CAPÍTULO 9. MCELIECE CON MPC Ay los subcódigos empleados se deben encontrar en el mismo cuerpo. Por tanto, actualmente solo es posible realizar la construcción del nuevo criptosistema empleando la matriz correspondiente a la construcción de Plotkin, ya que vimos en el ejemplo 8.2 que no existe ninguna matriz cuadrada de tamaño 3 o superior formada únicamente por elementos de F2que sea no singular por columnas. Aunque para esta construcción hemos visto que se reduce notablemente el tamaño de las claves del criptosistema, habría que analizar la reducción de las claves ocasionada empleando el nuevo método a partir de códigos de producto de matrices que se construyan con subcodigos de Goppa sobre cuerpos no binarios y una matriz A de mayor tamaño, donde prevemos, como hemos dicho en el ejemplo 9.1, que dicha reducción será aun mayor que para la construcción de Plotkin. Sin embargo, habría que analizar 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.8. Otro aspecto importante que faltaría por analizar detenidamente, 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 ataques nuevos que podrían surgir al criptosistema debido al empleo de los códigos de producto de matrices.
Bibliografía [1] DAVID MORENO CENTENO ,Implementación de la teoría de códigos: McEliece y una nueva versión, Trabajo fin de grado informática, 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. 113