Aplicaciones de los autómatas celulares a los criptosistemas de cifrado en flujo

Aplicaciones de los Aut´matas Celulares a los o Criptosistemas de Cifrado en Flujo
Sara Hoya White Trabajo parcialmente subvencionado por la Fundaci´n o “Memoria Samuel Sol´rzano Barruso” o Grado de Salamanca, 2002

1

Departamento de Matem´tica Aplicada a Universidad de Salamanca

Aplicaciones de los Aut´matas Celulares o a los Criptosistemas de Cifrado en Flujo

Sara Hoya WhiteGrado de Salamanca Trabajo parcialmente subvencionado por la Fundaci´n o “Memoria Samuel Sol´rzano Barruso”. o

Director: Dr. D. Gerardo Rodr´ ıguez S´nchez a Departamento de Matem´tica Aplicada a Escuela T´cnica Superior de Ingenier´ Industrial de B´jar e ıa e Universidad de Salamanca Codirector: ´ Dr. D. Angel Mart´ del Rey ın Departamento de Matem´tica Aplicada a Escuela T´cnica Superior deIngenier´ Industrial de B´jar e ıa e Universidad de Salamanca

2

Agradecimientos

Este trabajo, que se presenta para la obtenci´n del Grado de Salamano ca, ha sido parcialmente subvencionado por la Fundaci´n “Memoria Samuel o Sol´rzano Barruso”. o Agradezco al resto de mis compa˜eros del Grupo GIACA su apoyo en la n elaboraci´n de esta memoria. o A mi familia. A Carlos. B´jar, Junio 2002. e3

´ Indice
Agradecimientos ´ Indice 1. Introducci´n o 1.1 Resumen 1.2 Clasificaci´n o 1.3 Or´ ıgenes del problema 1.4 Resumen de los contenidos 2. Criptolog´ ıa 2.1 Introducci´n o 2.2 Criptograf´ ıa 2.2.1 Criptosistemas de clave secreta 2.2.2 Criptosistemas de clave p´blica u 2.3 Criptoan´lisis a 3. Secuencias Pseudoaleatorias 3.1 Introducci´n o 3.2 Generadores de n´meros pseudoaleatorios u3.3 Conocimientos previos de Estad´ ıstica 3.3.1 Variables aleatorias 3.3.2 Distribuci´n normal y distribuci´n de Pearson o o 3.4 Los tests estad´ ısticos 3.4.1 Definiciones previas 3.4.2 Los postulados de Golomb 3.4.3 Los tests estad´ ısticos 4. Aut´matas Celulares o 4.1 Conceptos generales 4.2 Representaci´n gr´fica de los ACs o a 4.3 Los aut´matas celulares de Wolfram o 5. Generaci´n desecuencias de bits o 5 5 7 7 8 9 9 11 15 19 25 27 27 29 31 31 34 36 37 38 40 43 45 53 55 63

4 5.1 Los ACWs como generadores de bits 5.2 Selecci´n de los ACWs generadores o 5.2.1 Implementaci´n en Mathematica o 5.2.2 Criba n 1 5.2.3 Criba no 2 5.2.4 Criba n 3 5.2.5 Criba n 4 5.2.6 Criba no 5 5.2.7 Seguridad criptogr´fica a 5.3 Aplicaci´n de los ACWs al cifrado en flujo o 6. Conclusiones y desarrollosfuturos Bibliograf´ ıa Ap´ndice 1 e
o o o

63 65 66 69 79 80 81 83 92 98 107 111 115

Cap´ ıtulo 1 Introducci´n o
1.1. Resumen

El objeto de esta memoria es el estudio de las propiedades pseudoaleatorias y de seguridad criptogr´fica de los aut´matas celulares de Wolfram y su a o aplicaci´n a los criptosistemas de cifrado en flujo. o Con el cada vez mayor aumento de las comunicaciones, lademanda de seguridad y privacidad en las mismas se ha convertido en una necesidad primordial. La criptograf´ es, por tanto, un requisito esencial en la sociedad ıa de hoy en d´ Existen dos grandes tipos de m´todos de cifrado de la inforıa. e maci´n seg´n el uso que se hace de las claves utilizadas: los criptosistemas o u de clave secreta (el emisor y el receptor poseen las mismas claves para cifrar ydescifrar y, consecuentemente, se mantienen secretas para terceras personas) y los criptosistemas de clave p´blica (en los que cada usuario posee una u clave para cifrar —conocida por el resto de los usuarios—, y otra clave para descifrar —conocida unica y exclusivamente por el propio usuario—). Dentro ´ de los primeros podemos destacar otros dos tipos de m´todos: los m´todos e e de cifrado enbloque y los m´todos de cifrado en flujo. En los primeros el e mensaje se rompe en bloques, los cuales son cifrados usando una o m´ltiples u claves; como ejemplos de los mismos podemos destacar el criptosistema DES, IDEA, Triple-DES, Rijndael, etc. Por otra parte, en los m´todos de cifrado en flujo, el mensaje es codificado e en una cadena de bits, la cual es cifrada usando como clave una secuencia...