“ESTUDIO MONOGRÁFICO SOBRE TÉCNICAS DE CRIPTOGRAFÍA” TRABAJO DE GRADUACIÓN PREPARADO PARA LA FACULTAD DE INGENIERÍA PARA OPTAR AL GRADO DE: INGENIERÍA EN CIENCIAS DE LA COMPUTACIÓN POR: NURY MERCEDES MARTÍNEZ SILVA JUNIO DE 2004 SOYAPANGO – EL SALVADOR – AMÉRICA CENTRAL UNIVERSIDAD DON BOSCO RECTOR ING. FEDERICO MIGUEL HUGUET RIVERA SECRETARIO GENERAL LIC. MARIO RAFAEL OLMOS DECANO DE LA FACULTAD DE INGENERÍA ING. ERNESTO GODOFREDO GIRÓN ASESOR DEL TRABAJO DE GRADUACIÓN ING. OSCAR DURÁN VIZCARRA JURADO EVALUADOR LIC. SANTIAGO ABARCA ING. EDUARDO RIVERA ING. CARLOS GIOVANNI VÁSQUEZ TUTOR DEL TRABAJO DE GRADUACIÓN LIC. JORGE MAURICIO COTO UNIVERSIDAD DON BOSCO FACULTAD DE INGENIERÍA ESCUELA DE INGENIERÍA EN CIENCIAS DE LA COMPUTACIÓN JURADO EVALUADOR DEL TRABAJO DE GRADUACIÓN LIC. SANTIAGO ABARCA ING. EDUARDO RIVERA JURADO JURADO ING. CARLOS GIOVANNI VÁSQUEZ JURADO ING. OSCAR DURÁN VIZCARRA LIC. JORGE MAURICIO COTO ASESOR TUTOR AGRADECIMIENTOS Gracias a Dios y a la Virgen María por haberme dado fuerzas para poder finalizar este trabajo, uno de mis tantos sueños, y a las personas que a lo largo de mi camino, de una u otra forma, contribuyeron a este logro: A mi madre, Quien estoy segura siempre ha seguido mis trabajos, esfuerzos, dificultades y progresos. A mis hermanos, Por ser ejemplo de superación y porque esos recuerdos de infancia, y esos niños que aún queremos conservar dentro de nosotros, nos permiten reunirnos y creer que el tiempo no ha pasado. A la familia Silva, Mi abuelita Herminia, y mis tías Yolanda y Elsa, por su cariño, comprensión y por su permanente apoyo. A la familia Acuña, Mis tíos Carlos, Arnoldo, Agenor y mi primo Carlos, por brindarme siempre ese cariño tan especial y sus palabras de aliento. A mi tía Carmen por esa dulzura y sencillez con las que siempre me animó a superarme. A Oscar Durán y Margot de Durán, Por haberme permitido invadir su casa mientras trabajaba en este proyecto, por brindarme su confianza y cariño e incentivarme a seguir adelante. A Oscar Durán Vizcarra, Por creer en mí y en el proyecto, por exigirme y enseñarme a trabajar con calidad, por ser un gran amigo, por su apoyo y ayuda incondicional. A mis amigos y compañeros de trabajo, Cecyl, Ernesto, Luis y Nixon, por esa amistad tan bonita que nos une y porque desinteresadamente realizaron mis tareas mientras yo me encontraba dedicada a finalizar este proyecto. A mi jefe, Carlos Gómez, por todo el tiempo que me permitió tomarme para dedicarme a concluir esta ardua tarea. A la familia Thumann, Por sus palabras de aliento, cariño, colaboración y apoyo. A mi amiga Carmen Aida Mojica, Quien tanto me apoyó para concretar esta meta y quien ahora desde el cielo se regocija al verla finalizada. DEDICATORIA A mi padre, Francisco Javier Martínez, Por haberme enseñado a luchar, a vivir la vida con optimismo, y a creer en mí y en mis propias fuerzas. Por haberme corregido a tiempo para luego dejarme tomar mis propias decisiones, y sentirse orgulloso de ellas. Por nunca haber escatimado esfuerzos para instruirme. Por contagiarme de ese espíritu de superación y esas ganas infinitas de vivir que él mismo ha mostrado. Por enseñarme el significado de la palabra sacrificio. Por señalar mis errores con el único afán de hacerme crecer como persona. Por enseñarme que aun en la peor de las situaciones siempre la vida deja una lección y que por lo tanto la palabra derrota no existe. Por el cariño, la comprensión, el respeto y confianza que siempre ha tenido hacia mí. Porque un día el soñó con que su única hija se graduara de la Universidad y porque dedicó su vida a guiarme por ese camino. Porque me dio lo que nunca tuvo. Papá, este triunfo es, sobre todo, para tí. INDICE INTRODUCCIÓN.......................................................................................................................... i OBJETIVOS.................................................................................................................................. ii ALCANCES...................................................................................................................................iv LIMITACIONES.......................................................................................................................... v 1 ASPECTOS INTRODUCTORIOS......................................................................................1 1.1 RAMAS DE LA CRIPTOGRAFÍA..............................................................................................5 1.1.1 Esteganografía.....................................................................................................................5 1.2 CODIFICACIÓN......................................................................................................................6 1.2.1 Ruptura de códigos..............................................................................................................7 1.3 CIFRADO................................................................................................................................8 1.3.1 Sustitución y transposición.................................................................................................8 1.3.1.1 Sustitución monoalfabética monográmica.......................................................................9 1.3.1.2 Sustitución monoalfabética poligrámica..........................................................................9 1.3.1.3 Sustitución monoalfabética tomográmica........................................................................9 1.3.1.4 Sustitución polialfabética.................................................................................................9 1.3.1.5 Sustitución polialfabética con clave progresiva.............................................................10 1.3.1.6 Sustitución polialfabética con palabra clave..................................................................10 1.3.1.7 Sustitución polialfabética con clave automática............................................................10 2 EVOLUCIÓN HISTÓRICA...............................................................................................11 2.1 ERA ARTESANAL................................................................................................................12 2.1.1 Métodos artesanales..........................................................................................................18 2.1.1.1 Atbash............................................................................................................................18 2.1.1.2 Método de Escítalo.........................................................................................................19 2.1.1.3 Método de César............................................................................................................19 2.1.1.4 El Kama Sutra................................................................................................................19 2.1.1.5 Nomenclator...................................................................................................................20 2.1.1.6 Método de Alberti..........................................................................................................20 2.1.1.7 Método de Trithemius....................................................................................................20 2.1.2 Sistema de autoclave.........................................................................................................20 2.1.2.1 Método de Porta.............................................................................................................21 2.1.2.2 Método de Vigenère.......................................................................................................22 2.1.2.3 Método de Playfair.........................................................................................................23 2.1.2.4 Caracterización de la era artesanal.................................................................................24 2.1.2.5 Criptosistema de Vernam...............................................................................................24 2.1.2.6 ADFGVX.......................................................................................................................25 2.1.3 Otros métodos...................................................................................................................26 2.2 ERA TÉCNICA......................................................................................................................27 2.2.1 Modelos de máquinas de cifrado.......................................................................................27 2.2.1.1 Aparato de discos codificadores de Alberti....................................................................27 2.2.1.2 El cilindro de Jefferson..................................................................................................27 2.2.1.3 El cilindro de ruedas codificadas M-94/CSP-488..........................................................28 2.2.1.4 La máquina ENIGMA....................................................................................................29 2.2.1.5 Las máquinas de Hebern................................................................................................30 2.2.1.6 El convertidor M-209 (CSP-1500) de Hagelin..............................................................30 2.2.1.7 La máquina Khrya..........................................................................................................31 2.2.1.8 Las máquinas TYPEX y SIGABA.................................................................................31 2.2.1.9 La máquina NEMA........................................................................................................32 2.2.2 Caracterización de la era técnica.......................................................................................33 2.3 ERA DIGITAL.......................................................................................................................33 2.3.1 Los aportes de Shannon....................................................................................................33 2.3.2 Surgimiento de los conceptos de complejidad, clave pública y zero-knowledge.............35 3 MÉTODOS MODERNOS DE CRIPTOGRAFÍA DIGITAL.........................................40 3.1 SISTEMAS DE CIFRADO DE BLOQUE...................................................................................40 3.1.1 Sistemas de cifrado de bloque simétrico...........................................................................40 3.1.2 Modos de cifrado de bloque..............................................................................................41 3.1.2.1 ECB - Electronic codebook............................................................................................41 3.1.2.2 CBC – Cipher block chaining........................................................................................42 3.1.2.3 CFB – Cipher-Feedback.................................................................................................43 3.2 SISTEMA DE CIFRADO DE FLUJO........................................................................................43 3.2.1 Sistemas de cifrado de flujo síncrono...............................................................................44 3.2.2 Sistemas de cifrado de flujo asíncrono o autosincronizante..............................................45 3.2.3 Diferencia básica entre el cifrado de flujo síncrono y el autosincronizante......................45 3.3 MODOS DE CIFRADO DE FLUJO..........................................................................................46 3.3.1.1 OFB – Output feedback.................................................................................................46 3.3.1.2 CTR – Counter...............................................................................................................46 4 ALGORITMOS DE LLAVE PRIVADA..........................................................................49 4.1 ELEMENTOS ESTRUCTURALES DE USO FRECUENTE.........................................................49 4.1.1 Redes de Feistel................................................................................................................49 4.1.2 Cajas de sustitución...........................................................................................................50 4.2 LUCIFER..............................................................................................................................51 4.2.1 La función F......................................................................................................................53 4.2.2 Cajas de sustitución y transposición.................................................................................53 4.2.3 Ataques a Lucifer..............................................................................................................54 4.3 DATA ENCRYPTION STANDARD (DES)....................................................................54 4.3.1 Establecimiento del estándar.............................................................................................56 4.3.2 Descripción del DES.........................................................................................................56 4.3.3 Estructura interna del algoritmo........................................................................................57 4.3.4 La permutación inicial.......................................................................................................59 4.3.5 La transformación de la llave............................................................................................60 4.3.6 La permutación de expansión............................................................................................61 4.3.7 Las cajas de sustitución.....................................................................................................62 4.3.8 Las cajas de permutación..................................................................................................64 4.3.9 La permutación final.........................................................................................................65 4.3.10 Proceso de descifrado del DES.......................................................................................65 4.3.11 Modos de operación del DES..........................................................................................65 4.3.11.1 ECB (Electronic Code Book).......................................................................................65 4.3.11.2 CBC (Cipher Block Chaining).....................................................................................66 4.3.11.3 CFB (Cipher Feedback)...............................................................................................66 4.3.11.4 OFB (Output Feedback)...............................................................................................67 4.3.12 Seguridad del DES..........................................................................................................68 4.3.13 Llaves débiles del DES...................................................................................................68 4.3.14 Longitud de la llave.........................................................................................................69 4.3.15 Críticas al diseño del DES...............................................................................................69 4.3.16 Resultados adicionales....................................................................................................70 4.3.17 Variantes del DES...........................................................................................................71 4.3.17.1 Triple DES...................................................................................................................71 4.3.17.2 DES con sub-llaves independientes.............................................................................73 4.3.17.3 DESX...........................................................................................................................73 4.3.17.4 CRYPT(3)....................................................................................................................73 4.3.17.5 DES generalizado.........................................................................................................73 4.3.17.6 DES con cajas de sustitución alternativas....................................................................74 4.3.17.7 RDES...........................................................................................................................74 4.3.17.8 SnDES...........................................................................................................................74 4.3.17.9 DES con cajas dependientes de llaves..........................................................................74 4.3.18 ¿Qué tan seguro es DES ahora?......................................................................................75 4.4 INTERNATIONAL DATA ENCRYPTION ALGORITHM (IDEA)............................................75 4.4.1 Proceso de cifrado.............................................................................................................77 4.5 MADRYGA........................................................................................................................78 4.5.1 Descripción del algoritmo.................................................................................................79 4.6 SKIPJACK.........................................................................................................................81 4.7 BLOWFISH........................................................................................................................82 4.7.1 El funcionamiento de Blowfish.........................................................................................82 4.7.2 La seguridad de Blowfish..................................................................................................85 4.8 RIJNDAEL.........................................................................................................................85 4.8.1 Especificaciones del algoritmo.........................................................................................86 4.8.1.1 Los Estados, las llaves y el número de vueltas..............................................................86 4.8.1.2 Número de vueltas..........................................................................................................88 4.8.1.3 Operaciones en cada vuelta............................................................................................88 4.8.1.4 Transformación BytesSub.............................................................................................89 4.8.1.5 La transformación ShiftRow..........................................................................................90 4.8.1.6 La transformación MixColumn......................................................................................91 4.8.1.7 La adición de las sub llaves - AddRoundKey................................................................92 4.8.1.8 Gestión de llaves............................................................................................................93 4.8.1.9 Expansión de la llave.....................................................................................................93 4.8.1.10 Selección de llave en cada vuelta - Round Key Selection...........................................94 4.8.2 Aspectos de implementación.............................................................................................94 4.8.2.1 Procesadores de 8 bits....................................................................................................94 4.8.2.2 Procesadores de 32 bits..................................................................................................95 4.8.2.3 Paralelismo.....................................................................................................................95 4.8.2.4 Adaptación de hardware.................................................................................................95 4.8.3 Proceso de descifrado........................................................................................................95 4.8.4 Implementación del descifrador Rijndael.........................................................................96 4.8.4.1 Adaptabilidad al hardware.............................................................................................96 4.8.5 Incremento del número de vueltas....................................................................................96 4.8.6 Llaves débiles....................................................................................................................97 4.8.7 Fortaleza estimada.............................................................................................................97 4.8.8 Metas de seguridad............................................................................................................98 4.8.8.1 Seguridad K....................................................................................................................98 4.8.8.2 Cifradores de bloque herméticos....................................................................................98 4.8.8.3 Metas..............................................................................................................................98 4.8.9 Ventajas y limitaciones de Rijndael..................................................................................99 4.9 COMPARACIÓN ENTRE EL DES Y EL RIJNDAEL.............................................................100 4.9.1 Ámbitos de uso................................................................................................................100 4.9.2 Llaves de cifrado.............................................................................................................101 4.9.3 Tamaño de bloque de datos.............................................................................................103 4.9.4 Aumento en la seguridad.................................................................................................103 4.9.4.1 Variación de la velocidad.............................................................................................104 4.9.5 Estructura interna de los algoritmos................................................................................104 4.9.5.1 Representación de la información................................................................................104 4.9.5.2 Permutaciones empleadas............................................................................................104 4.9.5.3 Estructura de la red.......................................................................................................105 4.10 RESISTENCIA FRENTE A LOS PRINCIPALES ATAQUES...................................................106 4.10.1.1 Criptoanálisis diferencial...........................................................................................106 4.10.1.2 Criptoanálisis lineal....................................................................................................106 4.10.1.3 Ataques por análisis temporal (Timing attacks).........................................................107 4.10.1.4 Ataque mediante la existencia de llaves débiles........................................................107 4.11 DE LA CRIPTOGRAFÍA SIMÉTRICA A LA ASIMÉTRICA...................................................107 5 ALGORITMOS DE LLAVE PÚBLICA.........................................................................109 5.1 EL PROTOCOLO DIFFIE HELLMAN PARA INTERCAMBIO DE LLAVES............................109 5.2 RSA....................................................................................................................................110 5.2.1 Seguridad del RSA..........................................................................................................111 5.2.2 Firmas digitales y RSA...................................................................................................111 5.2.3 Firmando un documento utilizando RSA........................................................................112 5.3 USOS DEL RSA..................................................................................................................112 5.4 CIFRADO UTILIZANDO ALGORITMOS DE LLAVE PÚBLICA.............................................112 5.5 SISTEMAS DE CIFRADO HÍBRIDOS....................................................................................114 5.5.1 Cifrado con sistemas de cifrado híbridos........................................................................114 5.5.2 El sistema híbrido de cifrado más importante: PGP.......................................................114 5.5.3 Cifrado utilizando sistemas de cifrado híbrido...............................................................116 5.6 FUNCIONES RESUMEN (HASH).........................................................................................117 5.6.1 MD4 – Message Digest 4................................................................................................119 5.6.2 MD5 – Message Digest 5................................................................................................119 5.6.3 El SHA como estándar....................................................................................................119 5.6.4 Seguridad del algoritmo SHA.........................................................................................119 5.6.5 SHA-256, SHA-384 y SHA-512.....................................................................................120 5.7 ¿CUÁL FUNCIÓN RESUMEN SE DEBE UTILIZAR?.............................................................120 5.8 FIRMAS DIGITALES...........................................................................................................120 5.9 PGP PRETTY GOOD PRIVACY.........................................................................................125 5.9.1 Debilidades de PGP.........................................................................................................126 CONCLUSIONES BIBLIOGRAFIA ANEXOS ANEXO I – Criptoanálisis ANEXO II – Ejemplo de la primera iteración de un texto al que se aplica el algoritmo DES ANEXO III – Tabla comparativa entre cifrado de llave secreta y cifrado de llave pública ANEXO IV – Tabla comparativa de estructuras de algunos algoritmos de cifrado de bloques ANEXO V – Tabla comparativa del rendimiento de algunos algoritmos de cifrado de bloque ANEXO VI – El Modelo OSI ANEXO VII – SSL - Secure Socket Layer ANEXO VIII – Kriptonita - Aplicación para cifrado y descifrado de datos