Criptografía. 1. Definición. Una persona, el transmisor, quiere enviar un mensaje a un receptor y desea que su mensaje viaje de manera segura, y que ningún escucha ajeno pueda conocer el mensaje. El mensaje se conoce como el texto plano o en claro (M). El proceso de elaborar un mensaje que esconde su contenido es la encripción o cifrado. Un mensaje encriptado o cifrado se conoce como el texto cifrado (C) El proceso de tomar un texto cifrado y convertirlo de nuevo a un texto claro se denomina desencriptar o descifrar. El arte y ciencia de guardar un mensaje seguro es la criptografía. Un criptografo es quien practica esta ciencia. El arte y ciencia de romper textos cifrados se denomina criptoanálisis. La rama de las matemáticas que agrupan la criptografía y criptoanálisis se denomina criptología. La criptografía es una herramienta que se utiliza para proveer los siguientes servicios de seguridad Confidencialidad Autenticación Integridad No repudiación 2. Elementos de la criptografía. El mensaje (M) a ser cifrado. El algoritmo criptográfico o cifrador, es una función matemática (f) que se usa para cifrar o descifrar. La seguridad del algoritmo no debe basarse en guardar el secreto de como es. Si el algoritmo es conocido no implica que sea posible descifrar un texto plano. Una llave, K, se debe utilizar como la entrada al algoritmo para poder asegurar la confidencialidad. Dicha llave se toma de un espacio de llaves, que debe ser grande, para evitar que dos o mas personas coincidan en llaves. Si la llave K no es conocida, debe ser computacionalmente intratable el descifrar un texto cifrado. El algoritmo criptografico puede tener la siguiente propiedad E(K,M) = C , donde E() es una función matemática, con dos argumentos, la llave K y el mensaje M y origina un mensaje cifrado C. D(K,C) = M, donde D() es una función matemática, con dos argumentos, la llave K y el mensaje cifrado C y origina un mensaje en claro M. D(K,E(K,M))=M Este tipo de algorimos se denominan simétricos. Otro tipo de algorimos es aquel en el que se cumple E(K1,M)= C D(K2,C)= M D(K2,E(K1,M))=M este tipo de algoritmos se denomina asimétrico. 3. Algoritmos de sustitución y transposición. Antes de que se utilizaran computadoras para cifrar, la criptografía eran algoritmos basados en caracteres. Un cifrado de sustitución consiste en que cada caracter en el texto en claro es sustituido por otro caracter. El receptor invierte la sustitución en el texto cifrado para recuperar el texto en claro. Un sistema muy simple, usado siglos atras, CAESAR,permite mostar las propiedades y relaciones de un sistema criptografico. Para encriptar un texto (donde se supone que la letra 'a' es el caracter 1 y la 'z' el caracter 26) se toma una llave (la letra 'a' es 0 y la 'z' 25) Se aplica la siguiente función para encriptar C=E(M,K) = (M+K) mod 26 y para desencriptar D(C,K) = (C-K) mod 26 Otro mecanismo para encriptar consiste en utilizar matrices Se propone una matriz cuadrada A= ( a b ) ( c d ) , de tal manera que ad - bc = 1 o -1 Se separa el texto en grupo de 2 palabras bloque = ( t1 ) ( t2 ) Encriptado(bloque,A) = A x bloque (donde x representa el producto cruz) ( c1 ) ( c2 ) Luego se determina la inversa de la matriz (B = inversa A) y para recuper el texto Desencriptado(cifado,B) = (t1) (t2) Un sistema basado en permutación es aquel en el cual se cambia el orden de los caracteres. Por ejemplo, se pueden tomar en bloques de tres y cambiar su orden (el caracter 1 ocupa la posicion 3, el caracter 2 ocupa la posicion 1 y el caracter 3 ocupa la posicion 2) Los métodos anteriores tienen un problema. Si el mensaje encriptado es expuesto o publicado puede ser sometido a un criptoanálisis. Existen algoritmos mas elaborados que utilizan la transformación y permutación, uno de ellos es DES. 4. Aritmetica modular, XOR, números primos Los criptosistemas se basan en el uso de una aritmetica finita (la aritmetica no finita es aquella en la que al sumar una unidad a un numero n, se genera un nuevo numero), la cual se basa en definir operaciones que lleven a los numeros minimos (cero o unidad) Por ejemplo, un sistema de aritmetica modular no permite que se rebase mas alla del modulo Por ejemplo, para un sistema con modulo 3 se pueden definir tablas de sumar y multiplicar, de tal manera que 2+1 = 0. Para aritmetica modular 2, la tabla de suma es equivalente a la operación de XOR. Una operacion XOR tiene la propiedad de ( M XOR K ) XOR K = M Para tres numeros enteros a,b y m, a es congruente con b modulo m si (a-b) es divisible por m. es decir (a-b) mod m = 0 Si a es congruente con b modulo m , y c es congruente con d modulo m se cumple que a+c es congruente con (b+d) modulo m Factorización entera consiste en descomponer un número en el producto de otros numeros enteros menores o factores (por ejemplo 120= 1*2*3*2*2*5, y sus factores son 1,2,3,5) Un número primo es aquel que tiene como factores la unidad y el mismo. El numero 17 solo se puede descomponer en 1*17 5. Criptografía Asimétrica La filosofía de este método reside en que el transmisor y receptor comparten dos llaves distintas. Se puede lograr aprovechando las propiedades de los numeros enteros. Un ejemplo es el siguiente + Elegir dos números primos aleatorios, que se mantengan en secreto + Calcular n=p*q y f=(p-1)*(q-1) + Seleccionar un numero entero aleatorio entre 1 y f-1, denominado e (se conoce como que es relativamente primo a f) + Calcular el inverso,d, de tal manera que e*d sea congruente con 1 modulo f (e*d-1) mod f = 0 + Encriptar con C=E(M,e,n) = M^e modulo n +Desencriptar con M=D(C,d,n)= C^d modulo n Este metodo es el que utiliza el algoritmo de RSA (Rivest, Shamir y Adleman) En este caso, el par denumeros e y n se denomina la llave publica y es utiizada para encriptar. El numero d es llamado la llave privada y es utilizada para desencriptar, usando n. Se cumple entonces M=D(E(M,e,n),d,n) Si M y d son desconocidos, debe ser computacionalmente complejo el obtener el mensaje claro 6. Clasificación de técnicas criptográficas Existen diversas clasificaciones Sistemas clasicos basados en sustitución y transposición Cifrado en bloques, que consiste en dividir al mensaje M en bloques M1,M2, de tal manera E(M,K) = E(M1,K)E(M2,K) el texto cifrado es la concatenacion de bloques cifrados Un cifrado en flujo aplica la encripción a digitos individuales del texto en claro. El cifrado usa una secuencia de digitos denominados el flujo de llaves que son los digitos de la llave. De tal manera que C[n] = M[n] XOR K[n] y M[n] = C[n] XOR K[n] Retroalimentación del cifrado. Encadenamiento de bloques cifrados. El resultado de cifrados anteriores son combinados con el texto plano A = Bloque XOR C[i-1] y el resultado es encriptado Esta tecnica evita que dos bloques identicos den el mismo resultado Funciones de un solo sentido. Una función de un solo sentido implica que se aplica sobre un mensaje pero no es posible encontrar una función inversa. Funciones de resumen. Dado un mensaje, se calcula un número único y que no debe repetirse para otro mensaje distinto Si M1 es el mensaje , MD la función de resumen y R1 el resumen R1 = MD(M1) Si M2 es un mensaje que difiere de M1 (inclusive por un bit) R2 = MD(M2) debe cumplirse que R1 y R2 son completamente diferentes. 7. Algoritmos criptográficos comunes. Existen una gran variedad de algoritmos, pero los mas utilizados son Criptografía Simétrica DES (Data Encryption Standard) Es un algoritmo de cifrado de bloques con llaves de 56 bits. IDEA (International Data Encruption Algorithm) Es un algoritmo de cifrado de bloques con llave de 128 bits RC4 - Usa llaves de 128 bits BlowFish - Usa llaves hasta de 448 bits Criptografía Asimétrica. RSA - Inventado por Rivest-Shamir-Adleman y está basado en la dificultad de factorizar enteros de gran longitud y usa llaves de 512, 1024 bits DSA - Algoritmos de Firma Digital y se basa en la dificultad de calcular un logarimto discreto sobre un campo modular de números Acuerdo de llaves de Diffie-Hellman. Define como dos partes pueden compartir una llave segura sobre un canal compartido. Funciones de Resumen MD5 - Dado un mensaje produce un número de resumen de 128 bits SHA-1 - Produce un numero de resumen de 160 bits 8. PGP. Pretty Good Privacy es un módulo de software que utiliza criptografía de llave simétrica y asimétrica. Fue creado por Phil Zimmerman y permite encriptar archivos, autenticar usuarios y generar firmas digitales. Usa sistemas de criptografía simétrica como DES, IDEA, Blowfish para encriptar datos y asimétrica como RSA, DSA para intercambiar llaves y firmas digitales y algoritmos de resumen como MD5 y SHA-1. PGP provee los siguientes servicios: Confidencialidad: Para enviar un mensaje confidencial, el usuario debe crear un archivo que contiene el mensaje. PGP comprime el archivo antes de encriptarlo. Por cada mensaje enviado, una llave de de sesión para cifrado simétrico es generada de manera aleatoria. La llave de sesión es encriptada con un algoritmo de llave asimétrica, usando la llave pública del receptor. La llave de sesión se envia con el mensaje. La llave asimétrica privada se usa para desencriptar la llave de sesión y con ésta ultima se descifra el mensaje aplicando el algoritmo simétrico de cifrado. Sea M el mensaje en claro y C el mensaje cifrado Sea ACS el algoritmo de cifrado simétrico Sea ACA el algoritmo de cifrado asimétrico Sea SK la llave de sesión y CSK la misma llave pero encriptada con ACA Sea K1 la llave pública del receptor y K2 la llave privada del receptor Entonces, PGP aplica lo siguiente para proveer la confidencialidad + Generar aleatoriamente SK + Encriptar el mensaje con la llave de sesión y usando un algoritmo simétrico C= ACS(M,SK,ENCRIPTAR) + Encriptar la llave de sesión usando la llave publica del receptor y aplicando un algoritmos asimétrico CSK = ACA(SK,K1) + Se envia C y CSK por el medio compartido + El receptor toma C y CSK + El receptor descifra CSK para obtener la llave de sesión, usando su llave privada asimétrica y un algoritmo asimétrico SK = ACA(CSK,K2) + El receptor descifra el mensaje, usando la llave de sesión SK y un algoritmo simétrico M= ACS(C,SK,DESENCRIPTAR) Firmas Digitales: Un usuario puede firmar un mensaje con su llave secreta. PGP usa un algoritmos de resumen que se aplica sobre el mensaje, y el número de resumen que resulta es encriptado con la llave privada del emisor usando un algoritmo asimétrico. Una firma digital se produce así y se anexa al mensaje en claro. El receptor obtiene el mensaje en claro y la firma digital. Se puede verificar la firma, de tal manera que el receptor usa la llave publica del emisor para desencriptar con un algoritmo asimétrico a la firma digital y así conocer el algoritmo de resumen calculado por el emisor; y el receptor calcula el algoritmo de resumen sobre al mensaje que obtuvo y checa que el número de resumen enviado y el calculado coincidan. De esa manera se puede asegurar que el mensaje se recibió integró y autenticar la identidad del emisor Sea M el mensaje en claro Sea ACA el algoritmo de cifrado asimétrico Sea K1 la llave pública del emisor y K2 la llave privada del emisor Sea MD el algoritmo de resumen Sea R el numero de resumen Sea F la firma Entoces PGP aplica los siguientes pasos para generar y validar la firma digital + Calcular el número de resumen del mensaje, usando un algoritmo de resumen R=MD(M) + Cifrar con un algoritmo asimétrico y la llave privada del emisor, al algoritmo de resumen, generando la firma digital F F= ACA(R,K2) + Enviar M y F en el medio compartido + El receptor recibe M y F + El receptor descifra F, usando la llave pública del emisor y el algoritmo de llave asimétrica ACA(F,K1) + El receptor calcula el número de resumen del mensaje obtenido, con MD(M) + El mensaje es valido si ACA(F,K1) igual a MD(M) Llaves y llaveros: PGP provee dos llaveros * Un llavero de llaves privadas para que el usuario almacene su par de llaves * Un llavero de llaves publicas para almacenar las llaves públicas de otras personas. Cada llavero contiene certificados de las llaves. A petición del usuario, PGP genera un par de llaves secreto-público, el usuario selecciona el tamaño de llave, el identificador del usuario (basado en su nombre, correo electrónico) y una frase secreta (passphrase) que es usada para proteger a la llave secreta. Un certificado de llave es construido para que incluya el nombre del usuario, una estampa de tiempo y el identificador de la llave, que toma de los bits de bajo orden de la llave pública. Antes de que la llave privada se coloque en el llavero privado, se encripta con una llave simétrica, generado con un número de resumen sobre la frase secreta. Eso implica que el usuario debe proveer dicha frase secreta para obtener su llave privada asimétrica. Llave Pública Asimétrica =====> Certificado Llave Llave Privada en llavero privado =====> CifradoSimétrico(Llave Privada Asimétrica,MD(Frase Secreta),ENCRIPTAR) Administración de llaves públicas. Los usuarios de PGP deciden en que usuarios confiar. Las llaves públicas de los usuarios se depositan en repositiorios de llaves PGP y de ahí se toman. Cuando un usuario decide ingresar una llave pública a su llavero, debe otorgar un grado de confianza a la misma y debe verificar el certificado de la llave. El certificado de la llave lo puede tomar como un numero que encuentre publicado en algún lado o inclusive puede tener comunicación directa con el usuario que posee la llave y ambos confirmar el número. El objetivo de PGP es construir una red de confianza de llaves públicas que sea descentralizada y tolerante a fallas. Actualmente, el dominio público tomo las definiciones de PGP y creo un software denominado GnuPG - The GNU Privacy Guard, disponible en http://www.gnupg.org