UNIDAD 2 .

- CRIPTOGRAFIA
Criptografa viene del griego y significa escritura secreta.

2.1 Definicin de criptografa.

Llamamos as a todos los sistemas de cifrado anteriores a la II Guerra Mundial, o lo que es lo mismo, al nacimiento de los ordenadores. Se basa en algoritmos sencillos y claves muy largas para la seguridad. Perdieron su eficacia, debido a que son fcilmente criptoanalizables por los ordenadores. Todos los algoritmos criptogrficos clsicos son simtricos

Cifradores e informacin en Web

Existe una gran cantidad de sistemas y cifradores de los denominados clsicos. En esta unidad estudiaremos : Esctala, Polybios, Csar, Afn, Vigenre, Playfair, Hill y Vernam, as como los ataques segn mtodos de Kasiski y Gauss Jordan.

Clasificacin histrica de criptosistemas

La clasificacin actual de los sistemas de cifra se basa en el tratamiento de la informacin (cifrado en bloque vs cifrado en flujo) o bien en el tipo de clave utilizada en la cifra (sistemas de clave secreta v/s sistemas de clave pblica), pero segn su relacin con la historia de la criptografa podramos clasificarlos como: Sistemas de Cifra Clsicos versus Sistemas de Cifra Modernos Esta no es ni mucho menos la mejor clasificacin desde el punto de vista de la ingeniera y la informtica ... pero permitir comprobar el desarrollo de estas tcnicas de cifra, hoy en da rudimentarias y simples, desde una perspectiva histrica y culturalmente interesante para un ingeniero. Adems, nos permitir criptoanalizar con cierta facilidad prcticamente todos estos sistemas y comprobar tambin las teoras de Shannon sobre las estadsticas del lenguaje.

Una primera aproximacin histrica

El uso de tcnicas criptogrficas es casi tan antiguo como las culturas de los primeros pueblos de nuestro planeta. Ya en el siglo V antes de J.C. un pueblo griego usaba tcnicas elementales de cifra para proteger su informacin. Se pretenda garantizar en aquellos das slo la confidencialidad y la autenticidad de los mensajes. A finales del siglo XX se han aadido la disponibilidad y, ltimamente, el no repudio. Los mayores avances se logran en la Primera y Segunda Guerra Mundiales, especialmente durante y despus de esta ltima. Los pases en conflicto posean verdaderas empresas con un gran nmero de matemticos, cuya funcin era romper los mensajes cifrados de los teletipos intercambiados por sus enemigos.

Herramientas de la criptografa clsica

Tanto mquinas, artilugios de cifra, como los algoritmos que trabajaban matemticamente dentro de un cuerpo finito, hacen uso de dos tcnicas bsicas orientadas a caracteres y que, muchos siglos despus, las propondr Shannon como herramientas para fortalecer la cifra:
Tcnicas de sustitucin: Los caracteres o letras del mensaje en claro se modifican o sustituyen por otros elementos o letras en la cifra. El criptograma tendr entonces caracteres distintos a los que tena el mensaje en claro. Tcnicas de transposicin o permutacin: los caracteres o letras del mensaje en claro se redistribuyen sin modificarlos y segn unas reglas, dentro del criptograma. El criptograma tendr entonces los mismos caracteres del mensaje en claro pero con una distribucin o localizacin diferente.

Clasificacin de los criptosistemas clsicos

TRANSPOSICIN
GRUPOS ESCTALA SERIES MONOGRMICA POLIGRMICA NO PERIDICA VERNAM DIGRMICA N-GRMICA LINEALES ALFABETO ESTNDAR CSAR AFN PLAYFAIR ALFABETO MIXTO OTROS HILL ALFABET O ESTNDA R VIGENRE ALFABETO MIXTO OTROS PROGRESIVOS ENIGMA PERIDICA MONOALFABTICA

SUSTITUCIN

y algunos ejemplos...
POLIALFABTICA

COLUMNAS FILAS

Hitos histricos en la criptografa

La criptografa clsica abarca desde tiempos inmemoriales hasta la mitad del siglo XX. El punto de inflexin en esta clasificacin la marcan tres hechos relevantes:
En el ao 1948 se publica el estudio de Claude Shannon sobre la Teora de la Informacin. En 1974 aparece el estndar de cifra DES. Y en el ao 1976 se publica el estudio realizado por Whitfield Diffie y Martin Hellman sobre la aplicacin de funciones matemticas de un solo sentido a un modelo de cifra, denominado cifrado con clave pblica.

C I F R A D O

D I G I T A L

Cifrados por sustitucin

Se basa en la sustitucin de cada letra por otra letra para disfrazarla pero conservan el orden de los smbolos de texto normal. Entre ellos cabe destacar los siguientes: - algoritmo de Csar, - mtodos de cifrado monoalfabticos, - polialfabticos..

Primer cifrador por transposicin: esctala

La esctala era usada en el siglo V a.d.C. por el pueblo griego de los lacedemonios. Consista en un bastn en el que se enrollaba una cinta de cuero y luego se escriba en ella el mensaje de forma longitudinal. Al desenrollar la cinta, las letras aparecern desordenadas. Para descifrar el criptograma y recuperar el mensaje en claro habr que enrollar dicha cinta en un bastn con el mismo dimetro que el usado en el extremo emisor y leer el mensaje de forma longitudinal. La clave del sistema se encuentra en el dimetro del bastn. Se trata de una cifra por transposicin pues los caracteres del criptograma son los mismos que en el texto en claro pero estn distribuidos de otra forma dentro del criptograma.

Mtodo de cifra de la esctala

Bastn y cinta para cifrar
A A C N I S C T I O A C N L I L A F A R E A S B

En ese bastn resida la fortaleza de un pueblo.

El texto en claro es:

Por ello, y como smbolo de poder, el bastn de mando que se le entrega al alcalde de una ciudad en la ceremonia de su nombramiento, proviene de estos tiempos tan remotos.

M = ASI CIFRABAN CON LA ESCITALA El texto cifrado o criptograma ser: C = AAC SNI ICT COA INL FLA RA AE BS

El cifrador del Csar

En el siglo I a.d.C., Julio Csar usaba este cifrador. El algoritmo consiste en el desplazamiento de tres espacios hacia la derecha de los caracteres del texto en claro. Es un cifrador por sustitucin monoalfabtico en el que las operaciones se realizan mdulo n, siendo n el nmero de elementos del alfabeto (en aquel entonces el latn).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Mi Ci

ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC

Alfabeto de cifrado del Csar para castellano mod 27

Ejemplo de cifra del Csar en mod 27

Mi Ci
A B CDE FG H IJK L MNO PQ RS TUVW X YZ DE FG HIJK L MNO PQ RS TUVW XYZA B C

Cifrado: Ci = Mi + 3 mod 27

Descifrado: Mi = Ci - 3 mod 27

M = EL PATIO DE MI CASA ES PARTICULAR

C = H

SDWLR GH OL FDVD HV SDUWLFXDU

Cada letra se cifrar siempre igual. Es una gran debilidad y hace que este sistema sea muy vulnerable y fcil de atacar, simplemente usando las estadsticas del lenguaje. Puede ver la tabla de frecuencias tpicas del lenguaje castellano en el captulo 21 de este libro.

- Mtodos de cifrado monoalfabticos

Sustituyen cada letra por otra que ocupa la misma posicin en un alfabeto desordenado y esta correspondencia se mantiene a lo largo de todo el mensaje. As se consiguen tantas claves como posibilidades de alfabetos hay. El problema est en cmo recordar la clave (el alfabeto desordenado). El procedimiento es el siguiente: 1. Se busca una palabra (clave) fcil de recordar y se le quitan las letras duplicadas. SEGURIDAD SEGURIDA 2. Se aaden al final de la palabra las restantes letras del alfabeto (sin duplicar letras). SEGURIDABCFH..................XYZ 3. Se ordenan en una matriz cuya primera fila es la palabra clave SEGUR I DA BCFH JK LM NOPQTVWX YZ 4. El nuevo alfabeto se lee por columnas: SBNYECOZGFPUHQRJTIKVDLWAMX Ejemplo: el mensaje ataque se convertira en SVSTDE
El sistema de criptoanlisis mejor para romper el algoritmo es el estadstico.

Criptografa clsica
Llamamos as a todos los sistemas de cifrado anteriores a la II Guerra Mundial, o lo que es lo mismo, al nacimiento de los ordenadores. Se basa en algoritmos sencillos y claves muy largas para la seguridad. Perdieron su eficacia, debido a que son fcilmente criptoanalizables por los ordenadores. Todos los algoritmos criptogrficos clsicos son simtricos

Cifrados por sustitucin

Se basa en la sustitucin de cada letra por otra letra para disfrazarla pero conservan el orden de los smbolos de texto normal. Entre ellos cabe destacar los siguientes: - algoritmo de Csar, - mtodos de cifrado monoalfabticos, - polialfabticos..

- Algoritmo de Csar:
Debe su nombre a que era usado por Julio Csar para enviar mensajes secretos Consiste en sumar 3 al nmero de orden de cada letra. De esta forma a la A le corresponde la D, a la B la E, y as sucesivamente. Este algoritmo no posee clave, puesto que la transformacin siempre es la misma. Para descifrar basta con restar 3 al nmero de orden de las letras del criptograma. Ejemplo: el mensaje ataque se convertira en DWDTXH

- Mtodos de cifrado monoalfabticos

Sustituyen cada letra por otra que ocupa la misma posicin en un alfabeto desordenado y esta correspondencia se mantiene a lo largo de todo el mensaje. As se consiguen tantas claves como posibilidades de alfabetos hay. El problema est en cmo recordar la clave (el alfabeto desordenado). El procedimiento es el siguiente:
1. Se busca una palabra (clave) fcil de recordar y se le quitan las letras duplicadas. SEGURIDAD SEGURIDA 2. Se aaden al final de la palabra las restantes letras del alfabeto (sin duplicar letras). SEGURIDABCFH..................XYZ 3. Se ordenan en una matriz cuya primera fila es la palabra clave SEGUR I DA BCFH JK LM NOPQTVWX YZ 4. El nuevo alfabeto se lee por columnas: SBNYECOZGFPUHQRJTIKVDLWAMX

Ejemplo: el mensaje ataque se convertira en SVSTDE El sistema de criptoanlisis mejor para romper el algoritmo es el estadstico.

- Mtodos de cifrado polialfabticos

Corresponde a la aplicacin cclica de n cifrados monoalfabticos, (de varios abecedarios desordenados). Un ejemplo tpico es el Cifrado de Vignere: - Dada una tabla con un alfabeto por cada letra del abecedario - Mtodo: Se busca una palabra clave fcil de recordar. Se escribe la palabra debajo del texto en claro, repitindose tantas veces como sea necesario. Cada letra del texto en claro se codifica con el alfabeto de la tabla marcado por la letra inferior, o sea, la letra de la clave que corresponde. - Ejemplo:
CLAVE: ADIOS Texto en claro : E S T O E S C R I P T O L O G I A Clave: ADIO SA DIOSADIOSAD Criptograma EVBD WS FZWHTRTCYID

Cifrados por transposicin

Se basa en la reordenacin de las letras de un texto de acuerdo a una palabra clave escogida que no contiene letras repetidas. Mtodo:

Se puede criptoanalizar efectuando un estudio estadstico sobre la frecuencia de aparicin de pares y tripletas de smbolos

- Con la clave se numera las columnas, estando la columna 1 bajo la letra de la clave ms cercana al inicio del alfabeto, y as sucesivamente. - El texto normal se escribe horizontalmente en filas. - El texto cifrado se lee por columnas, comenzando por la columna cuya letra clave es ms baja

 Ejemplo:
- Texto normal: Este es un trabajo para la asignatura de Redes" - Clave: Video - Texto cifrado: T ROAAA E EUA STDD SSTJR NAR NBPLIUEE EE AAAGR S

V 5 E e

I 3 s s t

D 1 t

E 2 e u

O 4

n b p l

r o a a

a a a g r

j r

s t d

i u e e

n a R

Rellenos de una sola vez

El mtodo consistira en:
Escoger una clave al azar, Por otro lado se convierte el texto normal en una cadena de bits Se calcula el XOR de estas dos cadenas

El texto cifrado es indescifrable ya que no proporciona ninguna informacin. Problemas:

La clave no puede memorizarse La cantidad de datos que se puede transmitir est limitada a la cantidad de clave disponible Es sensible a la perdida o insercin de caracteres si se pierde la sincrona entre receptor y emisor

Algoritmos de clave simtrica

Tambin se le denomina critografa privada o cifrado por bloques. Se caracteriza por usar la misma clave para encriptar y desencriptar.

Toda la seguridad est basada en la privacidad de esta clave

Cifrado de producto
Se apoyan en dos conceptos:
Confusin: tratar de ocultar la relacin que existe entre el texto normal, el texto cifrado y la clave, es decir, realizar sustituciones simples Difusin: trata de repartir la influencia de cada bit del mensaje original lo ms posible en el mensaje cifrado, es decir, realizar permutaciones

Estas tcnicas consisten en trocear el mensaje en bloques de tamao fijo, y aplicar la funcin de cifrado a cada uno de ellos. Destacar que la confusin por s sola sera suficiente, pero ocupara mucha memoria, por lo que sera inviable.

Algoritmo DES
Es el algoritmo simtrico ms extendido mundialmente. Codifica bloques de 64 bits empleando claves de 56 bits. Consta de 16 rondas, ms dos permutaciones, una que se aplica al principio (Pi) y otra al final (Pf ), tales que la ltima es la inversa de la primera. Para descifrar basta con usar el mismo algoritmo empleando el orden inverso. Ventajas del algoritmo:
Es muy rpido y fcil de implementar.

Desventajas:
Emplea una clave demasiado corta, lo cual hace que con el avance actual de los ordenadores, los ataques por la fuerza bruta se puedan llevar a cabo.

Variantes del DES

Se han propuesto variantes de este algoritmo para as aprovechar gran parte de las implementaciones por hardware existentes de DES. De ellos el que cabe destacar es: DES Mltiple:
Consiste en aplicar varias veces el algoritmo DES con diferentes claves al mensaje original. El ms comn de todos ellos es el Triple-DES, que responde a la siguiente estructura:
Codificar con la subclave k1, decodificar con k2 y volver a codificar con k1. La clave resultante es la concatenacin de k1 y k2, con una longitud de 112 bits.

Idea (International Data Encryption Algorithm)

Codifica bloques de 64 bits empleando una clave de 128 bits. Como en el caso de DES, se usa el mismo algoritmo tanto para cifrar como para descifrar. Es un algoritmo bastante seguro, y hasta ahora se ha mostrado resistente a los ataques. Su longitud de clave hace imposible en la prctica un ataque por la fuerza bruta como se poda hacer en el DES.

 Consta de ocho rondas. Dividiremos el bloque X a codificar, de 64 bits, en cuatro partes X1, X2, X3 y X4 de 16 bits. Denominaremos Zi a cada una de las 52 subclaves de 16 bits que vamos a necesitar. Las operaciones que llevaremos a cabo en cada ronda, se pueden apreciar en la figura:

X1

X2

X3

X4

X1

X2

X3

X4

Algoritmo de Rijndael (AES)

Es considerado el sucesor de DES. Este algoritmo se adopt oficialmente en octubre del 2000 como nuevo Estndar Avanzado de Cifrado (AES) por el NIST (National Institute for Standards and Technology) para su empleo en aplicaciones criptogrficas. Su nombre se debe a dos autores belgas Joan Daemen y Vincent Rijmen.

 Como peculiaridad tiene que todo el proceso de seleccin, revisin y estudio tanto de este algoritmo como de los restantes candidatos, se efectu de forma pblica y abierta, por lo que, toda la comunidad criptogrfica mundial ha participado en su anlisis, lo cual convierte a Rijndael en un algoritmo perfectamente digno de la confianza de todos. AES es un sistema de cifrado por bloques, diseado para manejar longitudes de clave y de bloque variables, ambas comprendidas entre los 128 y los 256 bits.

 Se basa en aplicar un nmero determinado de rondas a un valor intermedio que se denomina estado y que se representar en una matriz rectangular, que posee cuatro filas, y Nb columnas. A[4,Nb] La clave tiene una estructura anloga a la del estado, y se representar mediante una tabla con cuatro filas y Nk columnas. K[4,Nk] El bloque que se pretende cifrar o descifrar se traslada a la matriz de estado y anlogamente, la clave se copia sobre la matriz de clave Siendo B el bloque que queremos cifrar, y S la matriz de estado, el algoritmo AES con n rondas queda como sigue:

1. Calcular K0,K1, Kn subclaves a partir de la clave K. 2. S B K0 3. Para i = 1 hasta n hacer 4. Aplicar ronda i-sima del algoritmo con la subclave Ki. Puesto que AES permite emplear diferentes longitudes tanto de bloque como de clave, el nmero de rondas requerido en cada caso es variable Siendo S la matriz de estado, y Ki la subclave correspondiente a la ronda i-sima, cada una de las rondas posee la siguiente estructura: 1. S ByteSub(S) 2. S DesplazarFila(S) 3. S MezclarColumnas(S) 4. S Ki S

 Funciones DesplazarFila y MezclarColumnas permiten obtener un alto nivel de difusin a lo largo de varias rondas. Funcin ByteSub consiste en la aplicacin paralela de s-cajas. La capa de adicin de clave es un simple or-exclusivo entre el estado intermedio y la subclave correspondiente a cada ronda. La ltima ronda es igual a las anteriores, pero eliminando el paso 3.
El algoritmo de descifrado consistir en aplicar las inversas de cada una de las funciones en el orden contrario Es un algoritmo resistente al criptoanlisis tanto lineal como diferencial y uno de los ms seguros en la actualidad.