TEMA PROPIO: Historia de la Criptografía
yo mismo
19-ene-2004 22:14
#1
Partiendo de la idea de Chus y viendo que habia gente interesada os pongo un trabajo sobre la historia de la criptografía, como vereis es de nivel basico-medio, si alguien esta interesado en temas pues debatimos  HISTORIA DE LA CRIPTOGRAFIA Introducción - El propósito de la criptografía es que sólo las personas autorizadas puedan entender el mensaje. En la actualidad se utilidad para transmitir información entre empresas, bancos, persona, etc. Cuando alguien que quiere mandar información confidencial aplica técnicas criptográficas para poder “esconder” el mensaje (codificar), manda el mensaje por una línea de comunicación que se supone insegura y después solo el receptor autorizado pueda leer el mensaje “escondido” (descodificar). - La criptografía se divide en dos grandes ramas: Criptografía de clave privada o simétrica. Criptografía de clave pública o asimétrica - La criptografía se encuentra implementada dentro del modelo OSI en Nivel de Presentación Criptología La criptología está formada por dos técnicas: - Criptografía: Definición según el D.R.A.E: “Arte de escribir con clave secreta o de un modo enigmático”. Definimos criptosistema como una quíntupla (M, C, K, E, D), donde: M: conjunto de todos los mensajes sin cifrar C: conjunto de todos los posibles mensajes cifrados K: conjunto de claves que se pueden emplear en el criptosistema. E: conjunto de transformaciones de cifrado o familia de funciones que se aplica a cada elemento de M para obtener un elemento de C: Existe una transformación diferente Ek para cada valor posible de la clave k. D es el conjunto de transformaciones de descifrado, análogo a E. - Criptoanálisis: El criptoanálisis consiste en comprometer la seguridad de un criptosistema. El criptoanálisis normalmente, se realizar estudiando grandes cantidades de pares mensaje-criptograma generados con la misma clave y sistemas de aproximación matemática. Los tipos pueden ser analisis, fuerza bruta, suplantación de identidad... Criptografía Clásica Son algoritmos simetricos, osea, la misma clave es usada tanto para encriptar como para desencriptar. algoritmos de cifrado por sustitución: Monoalfabeticos: Consiste en reemplazar una símbolo (letra) o un grupo de símbolos del mensaje original por otro símbolo o grupo de símbolos. Por ejemplo el algoritmo del cesar de los romanos: B -> E Y -> A LLEGUE VI VENCI -- se cifra como --> OOHJXH YL YHQFL Modelización matemática ? C = (M + 3) mod 26 Polialfabéticos: la sustitución aplicada a cada carácter varía en función de la posición que ocupe éste dentro del texto plano. Ejemplo el Cifrado de Vigenère: Ejemplo para CLAVE (K): ADIOS Texto en claro : E S T O E S C R I P T O L O G I A Clave : A D I O S A D I O S A D I O S A D Criptograma : E V B D W S F Z W H T R T C Y I D algoritmos de cifrado por Transposición: Este tipo de mecanismos de cifrado cambia el orden de los símbolos dentro del texto. Mensaje : El perro de San Roque no tiene rabo con n = 5 y la permutación { 3, 2, 5, 1, 4 } como clave. texto cifrado: Osonealr r irednu eoere et p aqonb Máquinas de Rotores. La Máquina ENIGMA Ver grafico 1 más abajo... Historia En el año 1923, Arthur Scherbius inventó una máquina diseñada para facilitar las comunicaciones seguras. Se trataba de un instrumento de apariencia simple, parecido a un máquina de escribir. La clave la constituían las posiciones iniciales de tres tambores o rotores que el maquina posee en su parte frontal. La máquina ENIGMA fue utilizada por el ejército alemán en la II Guerra Mundial. El primero en conseguir avances significativos fue el servicio de inteligencia polaco, se recibió accidentalmente en ese país un ejemplar por correo ordinario. Un equipo polaco de tres matemáticos (Marian Rejewski), elaboro varios mecanismos para aprovechar sendas debilidad en el protocolo empleado por el ejército alemán enviar los mensajes codificados. Aprovechaba una debilidad esencial en ENIGMA: un mensaje no puede codificarse en sí mismo. Funcionamiento Se tecleaba el mensaje y las letras correspondientes al mensaje cifrado se iluminaban en un panel. El destinatario copiaba dichas letras en su propia máquina y el mensaje original aparecía de nuevo. La clave la constituían las posiciones iniciales de tres tambores o rotores que el maquina posee en su parte frontal. Cuestiones teoricas Un rotor no es más que una permutación dentro del alfabeto de entrada. El cableado hace que cada una de las letras se haga corresponder con otra. Todas las letras tienen imagen y no hay dos letras con la misma imagen. Si notamos una permutación como r, podemos escribir que la permutación resultante de combinar todos los rotores en un instante dado es: r total = ( r 0, r 1, r 2, r 3, r 2 -1, r 1 -1, r 0 -1 ) La permutación r 3 corresponde al reflector, y debe cumplir que r 3 = r 3 -1, que aplicada dos veces nos dé lo mismo que teníamos al principio. De esta forma se cumple la propiedad de que, para una misma posición de los rotores, la codificación y la decodificación son simétricas. Tras codificar cada letra se giran los rotores, lo cual hace que la permutación que se aplica a cada letra sea diferente, y que esa permutación además no se repita hasta que los rotores recuperen su posición inicial Cada vez que se pulsa una tecla el primer rotor avanza una posición, el segundo avanza cuando el anterior ha dado una vuelta completa y así sucesivamente. El reflector no existía en los primeros modelos, se introdujo posteriormente para permitir que la misma máquina sirviera tanto para cifrar como para descifrar. Ver grafico adjunto 2... Actualizaciones de Enigma Se incluyo un pequeño sistema previo de permutación de letras, llamado Stecker, hacía que los rotores fueran intercambiables (se podían elegir y colocar en cualquier orden tres de entre cinco disponibles). Debilidades en el protocolo El protocolo empleado por el ejército alemán para colocar los rotores al principio de cada mensaje consistía en escoger una posición de un libro de claves, y enviar dos letras cualesquiera dos veces, para evitar posibles errores al incluir una redundancia en el mensaje se permitía obtener sin demasiados problemas la clave empleada. El siguiente paso fue enviar tres letras repetidas. El ataque se basa en buscar ordenaciones de los rotores que llevan dos letras consecutivas iguales a la misma letra. Estas configuraciones especiales daban una información vital sobre la posición inicial de los rotores para un mensaje concreto. El siguiente paso fue añadir dos rotores adicionales, lo cual obligaba a emplear sesenta bombas simultáneamente para romper el sistema. Polonia carecía de medios económicos para afrontar su construcción. Debilidades en la maquina Enigma Un mensaje no puede codificarse en sí mismo, lo cual implica que ninguna de las letras del texto claro puede coincidir con ninguna del texto cifrado. Se partía de una palabra adivinada (la mayoría de los mensajes que enviaba el ejército alemán comenzaban de igual forma), y buscaba un emparejamiento con el mensaje cifrado tal que el supuesto texto claro y el fragmento de criptograma asociado no coincidieran en ninguna letra. A partir de ahí se realizaba una búsqueda exhaustiva de la configuración inicial de la máquina para decodificar el mensaje. Otras máquinas de rotores La máquina SIGABA, empleada por el ejército norteamericano, de la cual apenas se conoce nada por razones de secretismo americano. Las máquina japonesas empleadas en la II Guerra Mundial, que se denominaron PURPLE y RED, cuyas características son secretas o desconocidas. De hecho los norteamericanos declararon no haber tenido nunca ocasión de capturar nada más que un ejemplar, en la embajada japonesa tras la toma de Berlín. Criptografia Simetrica Pues partimos de conceptos previo propuestos por shanon: - Confusión (sustitución): Trata de ocultar la relación entre el texto plano y el texto cifrado - Difusión (transposición). Reparte la redundancia del texto plano repartiéndola a lo largo de todo el texto cifrado. Gracias a los 2 podemos hacer algoritmos robustos. Red de Feistel: Se dividen un bloque de longitud n en dos mitades, L y R. Se realiza un cifrado de producto (según función f) iterativo en el que la salida de cada ronda se usa como entrada para la siguiente. Cumple que es reversible independientemente de f. (ver grafico adjunto 3...) Algoritmo DES 1971: IBM crea un algoritmo de encriptación simétrico aplicando todas las teorías existentes sobre criptografía. 1973: la NBS (oficina nacional de estandares) convoca el primer concurso para un sistema de encriptación estándar. Fue ganado en 1977 por los inventores del LUCIFER con una versión mejorada, el Data Encryption Standard (DES). No se ha podido romper el sistema DES desde el punto de vista teórico, pero con fuerza bruta se pudo romper en Enero de 1999. Está considerado como secreto nacional en los EE.UU., por lo tanto, no se puede comercializar en HW ni SW fuera de USA sin permiso. El algoritmo DES está anticuado ya que usa claves demasiado cortas y no permite claves variables. Presenta algunas claves débiles aunque el número de claves de este tipo es muy pequeño. El algoritmo DES codifica bloques de 64 bits empleando claves de 56 bits. Es una Red de Feistel de 16 rondas, más dos permutaciones, una que se aplica al principio (Pi) y otra que se aplica al final (Pf ), tales que Pi = Pf -1. Se calcula en total de 16 valores de Ki, uno para cada ronda, efectuando primero una permutación inicial EP1 sobre la clave de 64 bits, llevando a cabo desplazamientos a la izquierda de cada una de las dos mitades resultantes, y realizando finalmente una elección permutada (EP2) de 48 bits en cada ronda, que será la Ki. Para entender este pedazo de parrafo ver grafico adjunto 4... Algoritmo Simetrico IDEA El algoritmo IDEA (International Data Encryption Algorithm) es un algoritmo más moderno que DES, fecha de 1992. Características: - Bloques de 64 bits de longitud y clave de 128 bits. - Algoritmo de libre distribución, libre de restricciones- - Bastante seguro, resistente a multitud de ataques, al no presentar claves débiles, su longitud de clave hace imposible en la práctica un ataque por la fuerza bruta. IDEA utiliza, las operaciones elementales XOR, Suma módulo 216 y Producto módulo 216 + 1. Algoritmo AES En 1996 el NIST dio los primeros pasos para consolidar un Estándar de Cifrado Avanzado (Advanced Encryption Standard). En septiembre de 1997, se realizó la convocatoria para la presentación de algoritmos. Requisitos mínimos de aceptación: - Ser público. - Ser un algoritmo de cifrado en bloque simétrico - Diseño que permita aumentar la longitud de clave. - Ser implementable tanto en hardware como en software. - Ser gratuita, o estar disponible bajo los términos de la política de patentes de ANSI (Instituto Nacional Americano de Estándares). -Deben soportar una longitud de bloque de 128 bits y una longitud de clave de 128, 192 y 256, además de otras longitudes posibles El 2 de octubre de 2000, el NIST anunció el algoritmo ganador: Rijndael, propuesto por los belgas Vincent Rijmen y Joan Daemen. Rijndael es un cifrador de bloque que opera con bloques y claves de longitudes variables, pueden ser especificadas independientemente a 128, 192 ó 256 bits. Criptografia Asimetrica En 1976 Whitfield Diffie y Martin Hellman publicaron el artículo “New directions in cryptography”. Nace la criptografía asimétrica. La criptografía asimétrica utiliza pares de claves distintas para codificar y descodificar, una de ellas se hace pública y la otra es privada de cada usuario. Características: - Longitudes de clave mucho mayores que los simétricos. - Mayor complejidad de calculo de los algoritmos. - Mas lentos que los algoritmos cifrados por bloque - Basado en funciones matemáticas fáciles de resolver, pero muy complicadas de realizar la inversa. - Poseen 2 claves denominadas clave privada y clave pública. Una de ellas se emplea para codificar, mientras que la otra se usa para decodificar. - Dependiendo de la aplicación que le demos al algoritmo, la clave pública será la de cifrado o viceversa. Que nos permite la criptografia asimetrica: 1. Información segura: ver grafico 5 2. Firma digital 3. Autentificación: ver grafico 6. Algoritmo RSA Nombre debido a sus inventores: Ron Rivest, Adi Shamir y Leonard Adleman. RSA se basa en la dificultad para factorizar grandes números. Nadie ha conseguido probar o rebatir su seguridad. Las claves pública y privada se calculan a partir de un número que se obtiene como producto de dos primos grandes. El atacante se enfrentará a un problema de factorización, que es el problema inverso a la multiplicación. ¿Cómo se generan las claves?: en primer lugar se escogen al azar dos números primos grandes, p y q, y calculamos su producto: n=pq Escogeremos ahora un número e primo relativo con (p - 1)(q - 1). (e, n) será la clave pública. Se debe de cumplir de = 1 (mod (p – 1)(q – 1)) donde d es la inversa de e módulo (p – 1)(q – 1). (d, n) será la clave privada. La codificación es la expresion: c = m "elevado a" e (mod n) la decodificación es la expresion: m = c "elevado a" d (mod n) Firma Digital Por autentificación entenderemos cualquier método que nos permita comprobar de manera segura alguna característica sobre un objeto. Firmas Digitales, Funciones Resumen Las firmas digitales autentifican los mensajes y se usan para validar compras, transferencias de fondos y otras transacciones de negocios. Para que sea segura, la función resumen r(m), donde m es el mesaje, debe cumplir ciertas características: r(m) es de longitud fija, independientemente de la longitud de m. Dado m, es fácil calcular r(m). Dado r(m), es computacionalmente intratable recuperar m. Dado m, es computacionalmente intratable obtener un m’ tal que r(m) = r(m’). Ver grafico 7... Estructura de una Función Resumen Las función de resumen se basan en la idea de funciones de compresión, que dan como resultado bloques de longitud n a partir de bloques de longitud m. Estas funciones se encadenan de forma iterativa, la entrada en el paso i sea función del i-ésimo bloque del mensaje y de la salida del paso i – 1 Algoritmo MD5: Diseñado en 1992 por Ron Rivest. Procesa los mensajes de entrada en bloques de 512 bits, y produce una salida de 128 bits. El algoritmo SHA: Fue desarrollado en 1994, por la NSA. Produce firmas de 160 bits, a partir de bloques de 512 bits del mensaje original. Certificados digitales Un certificado es esencialmente una clave pública y un identificador, firmados digitalmente por una autoridad de certificación. Usado para verificar que una clave pública pertenece a un usuario concreto. El estándar X.509 sólo define la sintaxis de los certificados. Estos certificados se estructuran de forma jerárquica, de tal forma que nosotros podemos verificar la autenticidad de un certificado comprobando la firma de la autoridad que lo emitió, que a su vez tendrá otro certificado expedido por una entidad de rango superior. ---------------------------------------------------------------------------------- ---------------------------------------------------------------------------------- Señores y pedazo de foreras muchas gracias a los pocos que llegareis aquí. Si querias más info pues os dire lo poco mas que sé  Y si no busca por la web, que es increible todo lo tiene... :d |
Editado: 19-ene-2004 22:55 -
de Gilead
19-ene-2004 22:43
#7
Gran tema la criptografía. Es algo que me gusta bastante, aunque ni de coña se puede decir que sea un experto  Respecto a la máquina enigma hay otro hilo que trata exclusivamente del aparato. El hilo en cuestión es este: Histora de la 2ªGM: La máquina Enigma.Un saludo, Gorgias. |
Club de Fans de Mädchen - Vicepresidente y acaparador 
Die Geschrei wuchsen wortlos 
yo mismo
19-ene-2004 22:52
#11
|
Gorgias tema interesante si señor. Muy bueno tu tema en su momento lo lei pero no me acordaba de él.
|
Del clan del conturbenio
19-ene-2004 23:51
#12
 Interesante, habra que felicitar a Chus por todos los Post que estan saliendo.Un saludo, Cunaxa |
Aguililla
20-ene-2004 00:01
#13
|
Gracias sansie... pero ufff, se me escapa por completo. Hace falta una base de telecomunicaciones y en parte de matemáticas que no tengo. dos dudas, ¿qué quiere decir: "un mensaje no puede codificarse en sí mismo" ? ¿qué son los métodos de análisis y fuerza bruta para transgredir un sistema criptográfico? saludos y gracias. P.D. Si hombre, Cunaxa, pues sólo faltaría..... |
ForoCoches: Miembro
20-ene-2004 00:34
#15
|
Aupa!! Uf! hace ya algunos años que aprobé la asignatura de "Criptofobia" de la carrera asi que todo esto lo tengo un pelin olvidado. Si digo alguna burrada... me lo hagan saber! En respuesta a algunas de las preguntas de Chus. Un ejemplo muy sencillo... Imaginemos que has cifrado mediante el "Cifrado del Cesar" un texto (recordemos que consiste en "sumar" a cada letra una cifra... es decir, que si la clave fuera 3, la letra A se codifica como una A+3 = D) Suponte tambien que tú sólo tienes el texto cifrado y por alguna extraña razon, sabes que la codificacion se ha realizado mediante el "Cifrado del Cesar". Lo que quieres, evidentemente es obtener el texto original. Un ataque por fuerza bruta consistiría en probar todas las posibles claves una a una sobre el texto cifrado, hasta que encuentres la que te proporciona el texto original. Empezarias por una clave 1, luego 2, luego 3, 4, 5... En este caso no es muy complicado... solo hay veintitantas letras. Un ataque por analisis... pues eso, es mas "fisno". Una forma de romper el cifrado del ejemplo anterior podría ser la siguiente. Se sabe por estadística, que la letra que aparece con mayor frecuencia en un texto es la "e" (tambien depende del idioma... en castellano es la "e" seguro) Basta con analizar al frecuencia de cada letra en el texto cifrado. Supongamos que la letra que mas veces aparece es la "F". Pues ya esta hecho... podemos suponer que la letra "E" en el texto original, ha pasado a ser la "F" en el texto cifrado, luego la clave "podria" ser F - E = 1. Pues se prueba a descifrar el texto con esa clave. Si obtenemos el texto original ya esta. Si no fuera asi, se puede probar el mismo procedimiento, pero esta vez no con la letra que mayor frecuencia tenga en el texto cifrado, sino la segunda. Por supuesto.. con este segundo tipo de ataque... cuanto mayor sea el texto, más probabilidades tenemos de acertar ya que la frecuencia de aparición de la letra buscada se ajustará en mayor medida a la calculada estadisticamente. Tambien se podria hacer este ultimo tipo de ataque, ya no con una letra, sino con varias. Si sabemos que, estadisticamente, el par de letras que aparece con mas frecuencia en el lenguaje español es "en" pues lo mismo pero con dos letras... Por supuesto, esto es un ejemplo muy basico... no penseis que los datos de vuestra tarjeta de credito van codificados con el "cifrado del cesar" cuando viajan por internet.... o si? xDDD En definitiva, el ataque por fuerza bruta trata de encontrar la clave de cifrado (o de descifrado) probando una por una todas las posibles, mientras que el ataque por analisis busca el punto debil del algoritmo de cifrado utilizado reduciendo así el numero de posibles claves utilizadas en el cifrado. Eso es todo. Saludetes ;-) Aitor. |
Aguililla
20-ene-2004 00:39
#17
|
gracias Aitor. Lo he entendido perfectamente. Pero como dices partimos de la base que conocemos el metodo de cifrado. Supongo que las pruebas se basan en eso... saludos. |
FC Premium™
20-ene-2004 00:41
#18
|
Aghhhh el año pasado en la asignatura de redes 2 me empapé de esto hasta las cejas...mola mucho sí, mientras no te tengas que examinar de ello en junio Saludos. |
yo mismo
20-ene-2004 00:51
#19
|
Bueno chus ya te han respondido a tu preguntas... Os pongo un ejemplo muy sencillo que pille de como codifica y descodifica el RSA, que es algoritmo que usais constatemente cuando entrais en una web https: Elegimos 2 primos p y q: p=7 y q =11, por lo que n=p*q=77 (p – 1)(q – 1) = 60, escogemos primo relativo a esta funcion, e =17 Para calcular d hay que encontrar numero x que cumpla: d = (x (p - 1)(q - 1) + 1)/e, los calculos salen d =53 y x =15 (esta formula es un truquito  )Para encriptar el “5”: C = 5^17 mod 77, esto nos da C = 3. Para desencriptar: M = 3^53 mod 77, esto nos da M = 5, useasé el mensaje original Saludos. |
Aguililla
20-ene-2004 00:59
#20
|
ok sansie, gracias. y lo de "un mensaje no puede codificarse en sí mismo"? saludos. |
yo mismo
20-ene-2004 00:59
#21
|
y lo de: "Un mensaje no puede codificarse en sí mismo" quiere decir que ninguna de las letras del texto claro (se llaman así a los textos no cifrados) puede coincidir con ninguna del texto cifrado. Osea que siempre hay una transformación. |
yo mismo
20-ene-2004 01:03
#23
|
Por eso el siguiente parrafo pone: "Se partía de una palabra adivinada (la mayoría de los mensajes que enviaba el ejército alemán comenzaban de igual forma), y buscaba un emparejamiento con el mensaje cifrado tal que el supuesto texto claro y el fragmento de criptograma asociado no coincidieran en ninguna letra. A partir de ahí se realizaba una búsqueda exhaustiva de la configuración inicial de la máquina para decodificar el mensaje. " Lo que quiere decir que con fuerza bruta con las posibles conbinaciones. |
yo mismo
20-ene-2004 01:06
#25
|
Oye te molo lo de "Aguililla" que te dije en la comida en Segovia?? jeje
|
Aguililla
20-ene-2004 01:16
#26
|
jejejjeje, alguno con un S3 no deja de nombrármelo, xDD es curioso mas que nada. saludos. |
Prisas las justas
20-ene-2004 01:32
#27
|
Sobre esto estaría interesante complementarlo explicando un poco el tema de la codificación que se usa en UMTS, las técnicas de espectro ensanchado, CDMA, jamming y todo eso... es una técnica de codificación prácticamente insuperable... e indetectable. Es un tema precioso, a ver si os puedo escribir un poco sobre ello, lo que pasa es que para meter las fórmulas... |
Prisas las justas
20-ene-2004 01:33
#28
|
Por cierto, Chus, tu proposición sobre los temas ha sido genial: muchas gracias por la idea.
|
Aguililla
20-ene-2004 01:34
#29
|
jeje, te digo lo que a cunaxa, gracias a vosotros por hacerme caso. Espero que no caiga en el olvido y todos aprendamos. saludos! |
Català i culé
20-ene-2004 11:37
#30
|
jeje, yo cuando era crio, inventé un lenguaje encriptado, cifrado o como sea, ya me perdonareis, con una de esas novias infantiles que todos hemos tenido por si sus padres pillaban las cartas que le daba en el cole y viceversa. Se trataba de partir las letras por la mitad y escribir solo la parte superior, la verdad es que era una chorrada, pero quedaba muy guay, años despues encontre una que había escondido dentro de un radiador, imaginaos, y se la di a unos colegas y no fueron capaces de descifrarlo hasta que no les dije la clave. Me ha gustado el post Gracias |