ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

1

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO. FACULTAD DE INGENIERÍA. CRIPTOGRAFÍA ALGORTIMOS DE CRIPTOGRAFÍA CLÁSICA. PROFESOR: MARÍA JAQUELINA LÓPEZ BARRIENTOS. ALUMNOS: DOMÍNGUEZ ESPINOZA EDGAR URIEL. PACHECO GÓMEZ LEONARDO. ENTREGA: MARTES, 10 DE ABRIL DE 2007 GRUPO: 1

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

2

ÍNDICE. I. II. III. IV.

INTRODUCCIÓN. CONCEPTOS BÁSICOS. RESÚMEN HISTÓRICO. CLASIFICACIÓN DE LOS CRIPTOSISTEMAS. – TRANSPOSICIÓN INVERSA. – TRANSPOSICIÓN SIMPLE. – TRANSPOSICIÓN DOBLE. – TRANSPOSICIÓN POR GRUPOS. – TRANSPOSICIÓN POR SERIES. – MÁSCARA ROTATIVA. – SUSTITUCIÓN POR DESPLAZAMIENTO. – ALGORITMO DE VIGENERE. – ALGORITMO DE VERNAM. – INSTRUCCIONES DE LOS PROGRAMAS EJEMPLO. – DIAGRAMAS DE PROGRAMAS. V. CONCLUSIONES. VI. REFERENCIAS.

3 4 5 6 7 8 8 8 8 9 9 10 11 11 12 13 13

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

3

INTRODUCCIÓN.

Antes de empezar a hablar de los algoritmos de criptografía clásica, tenemos que aclarar que parte de este trabajo esta basado en la historia de la criptografía, historia que bien si se ha asistido a un curso de criptografía es posible que ya el lector tenga este conocimiento y si considera prudente, podrá omitirlo. En resumen, son los escolares, y no los eruditos en la materia de criptografía, quienes ocupan el interés de este texto. No ha sido escrito con afanes de originalidad, ni de demostrar un acucioso trabajo teorético. No; su formulación ha estado animada por el empeño de ofrecer a los alumnos, un medio de fácil comprensión y de sencillo manejo, en las tareas que tienen frente a si, como es aprender sobre los sistemas criptográficos. Este documento, trata de significar una aportación para aligerar la búsqueda de información relacionada con la criptografía clásica, tratando de abarcar la historia y los principales, sencillos y didácticos sistemas criptográficos que corresponden a este tema y así encontrar un documento interesante e informativo.

Edgar U. Domínguez Espinoza Leonardo Pacheco G.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

4

CONCEPTOS BÁSICOS. La criptografía, es la ciencia que estudia los métodos y procedimientos, mediante algoritmos matemáticos, para modificar los datos de tal manera que solamente las personas que tengan la llave adecuada puedan: a) Tener acceso a la versión original de los mismos (confidencialidad). b) Asegurar que estos datos no fueron modificados entre el remitente y el destinatario (integridad). La criptografía hoy día involucra varias formas de cifrado y descifrado, así como diferentes métodos de autenticación. Aunque sus métodos y aplicaciones siguen siendo cada vez más complejos, la criptografía como tal sigue girando fundamentalmente alrededor de problemas matemáticos difíciles de solucionar. Un problema puede ser difícil de resolver porque su solución requiere de cierto conocimiento secreto, como la llave para descifrar un mensaje cifrado o para firmar un documento digital. También puede ser que sea intrínsecamente difícil de solucionar, en términos de los requerimientos matemáticos o de cómputo necesarios para solucionar o decodificar el mensaje cifrado. En el medio de la criptografía se reconocen dos tipos de personajes fundamentales para su existencia, criptógrafos y cripto-analistas. Los primeros se ocupan de desarrollar algoritmos de criptografía mientras los cripto-analistas se ocupan de romper los métodos de cifrado para obtener información de manera no autorizada. Ambas actividades van de la mano y favorecen el desarrollo de la criptografía. En criptografía, la información original que debe protegerse se denomina mensaje en claro. El cifrado es el proceso de convertir el mensaje en claro en un texto ilegible, denominado mensaje cifrado o criptograma – En el argot, a veces abreviado solo como cripto –. Por lo general, la aplicación concreta del algoritmo de cifrado se basa en la existencia de una clave: información secreta que adapta el algoritmo de cifrado para cada uso distinto. Las dos técnicas más básicas de cifrado en la criptografía clásica son la sustitución – que supone el cambio de los elementos básicos del mensaje – y la transposición – que supone una re ordenación de los elementos –; la gran mayoría de los algoritmos clásicos son combinaciones de estas dos operaciones básicas. El descifrado es el proceso inverso que recupera el mensaje en claro a partir del criptograma y la clave. El protocolo criptográfico especifica los detalles de cómo se utilizan los algoritmos y las claves para conseguir el efecto deseado. El conjunto de protocolos, algoritmos de cifrado, procesos de gestión de claves y actuaciones de los usuarios, en su globalidad es lo que constituyen un criptosistema, que es con lo que el usuario final trabaja e interactúa. Existen dos grandes grupos de criptosistemas: los algoritmos que utilizan una única clave tanto en el proceso de cifrado como en el de descifrado y los que utilizan una clave para cifrar mensajes y una clave distinta para descifrarlos. Los primeros se denominan sistemas simétricos o de clave simétrica y son la base de los algoritmos de cifrado clásico. Los segundos se denominan sistemas asimétricos, de clave asimétrica o de clave pública y clave privada y forman el núcleo de las técnicas de cifrado modernas. Con frecuencia los procesos de cifrado y descifrado se encuentran en la literatura como encriptado y desencriptado, aunque ambos son neologismos -anglicismos de los términos ingleses encrypt y decrypt- todavía sin reconocimiento académico. Hay quien hace distinción entre "cifrado/descifrado" y "encriptado / desencriptado" según esté hablando de criptografía simétrica o asimétrica, pero la mayoría de los expertos en el mundo académico prefiere evitar ambos neologismos. Por otro lado, podríamos haber de cifrado y descifrado como acciones legales o correctas, mientras la palabra desencriptado podemos entenderla como una acción no autorizada, propia de un cripto-analista.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

5

RESUMEN HISTÓRICO. La historia de la criptografía es larga y está llena de anécdotas. Ya las primeras civilizaciones desarrollaron técnicas para enviar mensajes durante las campañas militares de forma que si el mensajero era interceptado la información que portaba no corriera el peligro de caer en manos del enemigo. Posiblemente, el primer criptosistema que se conoce fuera documentado por el historiador griego Polibio: un sistema de sustitución basado en la posición de las letras en una tabla. También los romanos utilizaron sistemas de sustitución, siendo el método actualmente conocido como César, porque supuestamente Julio César lo utilizó en sus campañas, uno de los más conocidos en la literatura – según algunos autores, en realidad Julio César no utilizaba este sistema de sustitución, pero la atribución tiene tanto arraigo que el nombre de éste método de sustitución ha quedado para los anales de la historia –. Otro de los métodos criptográficos utilizados por los griegos fue la escitala espartana, un método de transposición basado en un cilindro que servía como clave en el que se enrollaba el mensaje para poder cifrar y descifrar. En 1465 el italiano Leon Battista Alberti inventó un nuevo sistema de sustitución polialfabética que supuso un gran avance de la época. Otro de los criptógrafos más importantes del siglo XVI fue el francés Blaise de Vigenere que escribió un importante tratado sobre "la escritura secreta" y que diseñó un algoritmo que ha llegado a nuestros días asociado a su nombre. A Selenus se le debe la obra criptográfica "Cryptomenytices et Cryptographiae" (Lüneburg, 1624). Durante los siglos XVII, XVIII y XIX, el interés de los monarcas por la criptografía fue notable. Las huestes de Felipe II utilizaron durante mucho tiempo un algoritmo con un alfabeto de más de 500 símbolos que los matemáticos del rey consideraban inexpugnable. Cuando el matemático francés François Viète consiguió cripto-analizar aquel sistema para el rey de Francia, a la sazón Enrique IV, el conocimiento mostrado por el rey francés impulsó una queja de la corte española ante del papa Pío V acusando a Enrique IV de utilizar magia negra para vencer a sus ejércitos. Por su parte, la reina María Estuardo, reina de los Escoceses, fue ejecutada por su prima Isabel I de Inglaterra al descubrirse un complot de aquella tras un criptoanálisis exitoso por parte de los matemáticos de Isabel. Desde el siglo XIX y hasta la Segunda Guerra Mundial las figuras más importantes fueron la del holandés Auguste Kerckhoffs y la del prusiano Friedrich Kasiski. Pero es en el siglo XX cuando la historia de la criptografía vuelve a presentar importantes avances. En especial durante las dos contiendas bélicas que marcaron al siglo: la Gran Guerra y la Segunda Guerra Mundial. A partir del siglo XX, la criptografía usa una nueva herramienta que permitirá conseguir mejores y más seguras cifras: las máquinas de cálculo. La más conocida de las máquinas de cifrado, posiblemente sea la máquina alemana Enigma: una máquina de rotores que automatizaba considerablemente los cálculos que era necesario realizar para las operaciones de cifrado y descifrado de mensajes. Para vencer al ingenio alemán, fue necesario el concurso de los mejores matemáticos de la época y un gran esfuerzo computacional. No en vano, los mayores avances tanto en el campo de la criptografía como en el del cripto-análisis no empezaron hasta entonces. Tras la conclusión de la Segunda Guerra Mundial, la criptografía tiene un desarrollo teórico importante; siendo Claude Shannon y sus investigaciones sobre teoría de la información esenciales hitos en dicho desarrollo. Además, los avances en computación automática suponen tanto una amenaza para los sistemas existentes como una oportunidad para el desarrollo de nuevos sistemas. A mediados de los años 70 el Departamento de Normas y Estándares norteamericano publica el primer diseño lógico de un cifrador que estaría llamado a ser el principal sistema criptográfico de finales de siglo: el Estándar de Cifrado de Datos o DES. En esas mismas fechas ya se empezaba a gestar lo que sería la, hasta ahora, última revolución de la criptografía teórica y práctica: los sistemas asimétricos. Estos sistemas supusieron un salto cualitativo importante ya que permitieron introducir la criptografía en otros campos que hoy día son esenciales, como el de la firma digital.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

6

CLASIFICACIÓN DE LOS CRIPTOSISTEMAS. El algoritmo de cifrado es una técnica para ocultar un mensaje y evitar que sea legible si éste es interceptado por una persona no autorizada. Por lo tanto, el objetivo básico es mantener seguros unos datos dentro de un entorno como puede ser una línea de transmisión o un sistema de almacenamiento que ya hemos visto es inseguro. Como protección utilizaremos métodos o algoritmos para cifrar la información. En una primera aproximación, en este caso bajo el punto de vista histórico, clasificaremos estos métodos de cifra como Criptosistemas Clásicos y Criptosistemas Modernos. En este documento solo veremos Criptosistemas Clásicos. MÉTODOS DE CIFRA CLÁSICOS

TRANSPOSICIÓN

SUSTITUCIÓN

GRUPOS Escítala

MONOALFABÉTICA

SERIES

POLIALFABÉTICA

COLUMNAS/FILA MONOGRÁMICA ALFABETO ESTÁNDAR Cifrador del César

POLIGRÁMICA

DIGRÁMICA

N-GRÁMICA

Cifrador de Playfair

Cifrador de Hill

ALFABETO MIXTO TRANSFORMACIÓN Cifrador sustitución afín

ALFABETOS PROGRESIVOS Máquina Enigma

NO PERIÓDICA

PERIÓDICA

Cifrador de Vernam

ALFABETOS LINEALES

ALFABETO ESTÁNDAR Cifrador de Vigenère

ALFABETO MIXTO

Clasificación de los métodos clásicos de cifrado y algunos ejemplos. Los métodos clásicos son aquellos en los que, además de las máquinas dedicadas para cifrar, se usan por separado técnicas de sustitución y transposición aplicadas a los caracteres del mensaje en claro. Las técnicas criptográficas utilizadas en este caso son en su totalidad orientadas a sistemas de clave secreta, generalmente manteniendo también en secreto el algoritmo, incluso en el caso en que el cifrador cuente con una clave secreta. El cifrado se realiza sobre caracteres alfanuméricos, por lo general alfabéticos, y en ese mismo formato se transmiten o almacenan. La Figura de esta sección muestra una clasificación de los sistemas clásicos, en donde se incluyen algunos cifradores típicos a modo de ejemplo. Estos sistemas se clasificarán, básicamente, en aquellos que utilizan

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

7

técnicas de sustitución y aquellos que utilizan técnicas de transposición sobre los caracteres de un mensaje en claro, ambas técnicas propuestas por Shannon para lograr la confusión y difusión, respectivamente. TRANSPOSICIÓN INVERSA. Es nuestro algoritmo más simple. Lo requerido para poder ejecutar el algoritmo, se debe saber donde inicia y donde termina nuestro mensaje. Se trata de invertir el inicio y el final de nuestro mensaje, cabe destacar que el algoritmo de cifrado es igual al de descifrado. Ejemplo: Mcla: hola mundo Cripto: odnumaloh Esto es sencillo de lograr y programar, por ejemplo en Java: //Es la clase que tiene el algoritmo, recibe el Mcla public String Cifrado(String mensaje){ //Convertimos el mensaje a arreglo de caracteres char arr[] = mensaje.toCharArray(); String cripto = "";//Cadena que contendrá el criptograma mensaje = ""; /*Del arreglo reescribimos el mensaje * sin los espacios */ for (int i = 0; i < arr.length; i++){ if(arr[i] != ' '){ mensaje+= arr[i]; } } //Vaciamos el arreglo arr = null; //Convertimos de nuevo el mensaje en arreglo arr = mensaje.toCharArray(); //Obtenemos el tamaño del arreglo int count = arr.length; //Contador auxiliar /*Formamos la cadena cripto con el ciclo * while y la integramos del último elemento del * arreglo al primero */ while(count != 0){ cripto+= (arr[count - 1]); count = count - 1; } //Retornamos la cadena cripto return ("El resultado es:\n"+cripto); } } Este texto tiene adjunto los algoritmos mencionados programados en JAVA, por lo que se sugiere ver los códigos fuente y probar su funcionamiento. Debido a eso, se procurará no añadir aquí dichos códigos y facilitar así la lectura del documento. Sin embargo se mostraran los diseños de estos programas, en este caso corresponden, diagramas de clase.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

8

TRANSPOSICIÓN SIMPLE. El algoritmo divide un mensaje en claro símbolo por símbolo, si el número de símbolos es impar, el primer grupo de símbolos tendrá un elemento más. Podemos ver el algoritmo como si numeráramos los elementos, en el primer bloque tendremos los elementos impares mientras en el segundo estarán los elementos pares. Para finalizar concatenamos los bloques y así tendremos el criptograma. Ejemplo: Mcla: Hola mundo Bloque1: hlmno Bloque2: oaud Cripto: hlmnooaud El proceso de descifrado, es similar, dividimos el criptograma en dos partes iguales, la primera mitad del criptograma será el primer bloque. Teniendo ambos bloques, se intercalan uno a uno los elementos de cada bloque, puede leerse el ejemplo de abajo hacia arriba, para ver la operación. TRANSPOSICIÓN DOBLE. Supone una transposición simple, después aplica nuevamente una transposición simple al criptograma, esto nos dará nuestro criptograma final. Es un algoritmo sencillo si se conoce la transposición simple. Es de utilidad principalmente para despistar a un cripto-analista que intente descifrar nuestro criptograma suponiendo que este fue cifrado mediante transposición simple. TRANSPOSICIÓN POR GRUPOS. Utiliza la técnica de permutación de forma que los caracteres del texto se reordenan bloques de n caracteres pero reordenados (permutados) éstos de forma que su posición en el criptograma sea, por ejemplo, 43521; es decir, el cuarto carácter del bloque en claro se transmite primero, a continuación el tercero, después el quinto, luego el segundo y, por último, el primero. Esta operación se repetirá en cada bloque de 5 caracteres del mensaje. Por lo tanto, la transposición implica que los caracteres del criptograma serán exactamente los mismos que los del texto en claro. Ejemplo: La Clave será: 43521. Mcla: Al grito de Viva Zapata se armó una Gorda. Dividido en bloques: ALGRI TODEV IVAZA PATAS EARMO UNAGO RDAXX Cripto: RGILA EDVOT ZAAVI ATSAP MROAE GAONU XAXDA Para descifrar se seguirá el mismo algoritmo, reordenando la clave en el orden original en este caso 54213. TRANSPOSICIÓN POR SERIES. En este algoritmo debemos ordenar el mensaje de tal manera que el criptograma esta formado por la secuencia de mensajes que se haya considerado para conformarlo. Cada cadena sigue una función específica.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

9

En nuestro programa tomamos en cuenta funciones muy sencillas como en este ejemplo se muestra. Mcla: hola mundo f(1) = números primos = 1,2,3,5 = holm f(2) = números pares = 4,6,8 = aud f(3) = números impares = 9 = o Cripto: holmaudo Para descifrar solo debemos saber el orden en el que están las funciones y cuales son, así podremos tener el número correspondiente a cada símbolo y reordenar el mensaje sin problemas. MÁSCARA ROTATIVA. En este algoritmo se crea una matriz A de nxn, A cada Aij le corresponderá un símbolo que puede o no, pertenecer al mensaje. Se crea una matriz B de nxn donde se escogen ciertos componentes de la matriz que corresdonderán a los elementos de la matriz A que pertenecen al mensaje, de tal manera que estos elementos queden seleccionados cada vez que la matriz B se sobrepone a la matriz A, en cualquiera de sus 4 lados, tomando como referencia inicial uno de sus lados. Ejemplo de como gira la matriz B:

Los espacios en blanco corresponden a los elementos del mensaje, y cada posición de la matriz se lee de arriba a abajo y de derecha a izquierda. Este algoritmo también esta en los programas elaborados para este trabajo, sin embargo se encuentra programado en Flash. SUSTITUCIÓN POR DESPLAZAMIENTO. Este algoritmo es muy popular debido a un caso particular llamado “Algoritmo del César”, que se citará como ejemplo y cuya clave se conforma solo por la letra C. Este algoritmo desplaza los símbolos del mensaje en claro ciertos espacios en el alfabeto usado. A cada letra se le asigna un valor, y se desplaza el número de veces que le corresponda según la clave usada, puede ser una sola letra, o una frase entera. Ejemplo, Usando el alfabeto común, la A es el 1 y la Z es el 26, la Ñ no existe en esta ocasión: Mcla: Mcla: Clave: Clave: Cripto: Cripto:

L 12 C 3 15 O

U 21 C 3 24 X

N 14 C 3 17 Q

E 5 C 3 8 H

S 19 C 3 22 V

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

10

Este algoritmo puede verse como si se estuviera haciendo la operación suma dándole valor a las letras, si alguna de las sumas tiene un valor mayor que N se le resta N para obtener el resultado, donde N es el máximo número asignado. Así, el descifrado se puede ver como la operación resta, siguiendo la misma mecánica. ALGORITMO DE VIGENERE. El principal elemento de este sistema es la llamada Tabla de Vigenère, una matriz de caracteres cuadrada.

Tabla de Vigenère. Nos posicionamos en el carácter del mensaje en claro a cifrar en la primera fila de la tabla y buscamos la letra de la clave en cuestión en la primera columna de la tabla. El elemento Ci del criptograma será la letra de la retícula de intersección entre fila y columna. Por ejemplo la letra E cifrada con la clave C nos dará el criptograma G. En términos matemáticos puede expresarse como: Yi = (Xi + Zi)modT con Zi = L,O,U,P, alternativamente, siendo T el número de letras del alfabeto. Se observa que a una misma letra en el texto claro le pueden corresponder diferentes letras en el texto cifrado. Ejemplo: Mcla: P A R I S clave: L O U P L cripto:A O L X D

V A U T O U P L J U J E

B I E N O U P L P C T Y

U N E O U P I H T

M E S S E L O U P L X S M H P

Para descifrar, se localiza el criptograma en la parte central de la matriz, y el renglón que corresponda a la clave, después se buscara la parte del mensaje que le corresponda.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

11

ALGORITMO DE VERNAM. Este último método usa el mismo algoritmo para cifrar y para descifrar el mensaje. Usa una clave constituida por una sucesión de símbolos (bits o caracteres), operando XOR cada símbolo de ésta con el correspondiente del texto en claro. Debido a la definición de la función XOR, el descifrado se realiza, igualmente, operando con dicha función cada bit de la misma serie cifrante con el correspondiente del texto cifrado. Si la serie cifrante no se repite, es aleatoria, y de longitud igual, al menos, al texto a cifrar éste cifrado alcanza el secreto perfecto. Además, es el único que verifica tal condición. INSTRUCCIONES DE LOS PROGRAMAS EJEMPLO. Los programas ejemplo están en el disco, en la carpeta “Criptografía Clásica en JAR”. Para poder ver el sistema que contiene todos los programas basta con ejecutar el archivo “iniciar.bat” y se abrirá una consola donde solo se tendrá que seguir un menú muy simple. Existe una manera alternativa de ejecutar el sistema, es con la instrucción “java -jar prueba.jar” esto es recomendable si se usa un sistema tipo *NIX. Es importante que no se modifique el contenido de la carpeta “Criptografía Clásica en JAR”, pues todos los archivos ahí son importantes para que el sistema funcione. También procure verificar que tenga instalado la máquina de virtual de Java, en caso de que no este instalada puede descargarla gratuitamente de http://www.java.com/es/download/ Para observar las fuentes de los programas debe ir a la carpeta “Criptografía Clásica”, en la subcarpeta “src” encontrará las fuentes de los programas, separados correctamente según método y operación. En la subcarpeta “bin” puede encontrar los programas con extensión “class” de estas fuentes divididos de la misma manera. Para poder ejecutar estos archivos “class” es necesario que en una consola de su sistema operativo ejecute la instrucción “java nombre_archivo” ejemplo: Para ejecutar el archivo “desplazamiento.class” ejecutar : java desplazamiento Hay otro programa ejemplo, que se encuentra en la carpeta “Mascara Rotativa”, corresponde a este algoritmo. Fue programado en Flash y basta con ejecutar el archivo “mascara.exe” para interactuar con el programa.

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA Tabla de Diagramas de clase usados para los programas ejemplo.

12

ALGORITMOS DE CRIPTOGRAFÍA CLÁSICA

13

CONCLUSIONES. Hemos estudiado los principales algoritmos de la criptografía clásica, hemos visto como se cifran y descifran mensajes en claro y también nos dimos idea de como ha evolucionado la criptografía a lo largo del tiempo. Sin embargo lo más importante es que logramos entender los algoritmos y programarlos, así podemos dar ejemplos de como funcionan y también podemos adelantar un poco el estudio de los sistemas criptográficos, debido a que seguramente mientras revisábamos los criptosistemas clásicos también pensamos en como hacer combinaciones con los algoritmos para hacerlos más eficientes. En medida de como se evolucionó el texto, logramos hacer un resumen completo y sencillo de la criptografía clásica y así facilitar su estudio y posterior revisión del conocimiento aquí contenido. REFERENCIAS. – – – –

–

www.wikipedia.org http://www.criptored.upm.es/software/sw_m001c.htm https://www.ccn-cert.cni.es/guia_401/es/c/n1669.htm Aplicaciones Criptográficas, segunda edición de junio de 1999, ISBN 83-87238-57-2, publicado por el departamento de Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España. leibniz.iimas.unam.mx/~yann/Crypto/Clase01.pdf