Entre unos y otros he terminado por animarme a escribir este post sobre criptosistemas y criptoanalisis que resultará bastante entretenido para la gente curiosa que guste de estos temas.
Primero unas formalidades para centrar el asunto sin enrollarnos demasiado: definiremos criptologia como la suma de dos ciencias que se complementan: criptografia y criptoanálisis.
La criptografia diseña algoritmos que permiten comunicaciones secretas entre un emisor y un destinatario. En la criptografia clasica intervienen dos factores: un algoritmo de cifrado y una clave secreta, K.
----cifrado(K)---->
Mensaje en claro Mensaje cifrado
<--descifrado(K)---
El criptoanálisis se encarga de elaborar tecnicas que permiten descubrir tanto el algoritmo de cifrado utilizado como la clave secreta involucrada en el proceso de encriptado.
Mensaje cifrado --- ¿algoritmo + K? ---> Mensaje en claro
Vamos a explicar como funciona un criptosistema muy sencillo, conocido como método de Cesar (usado hace unos cuantos años en las campañas militares romanas), y tambien vamos a ver lo facil que resulta atacarlo mediante una sencilla técnica de criptoanálisis conocida como el análisis de frecuencias.
El algoritmo de cifrado es muy sencillo. Cada caracter del mensaje en claro es sustituido por el situado K > 0 posiciones mas adelante en el alfabeto. Por ejemplo, asumiendo K=3, el criptosistema reemplaza la A por la D, la B por la E, y así sucesivamente. El descifrado es igual de facil, ya que consiste en sustituir cada caracter del mensaje cifrado por el situado K posiciones atras en el alfabeto.
Ejemplo de cifrado de Cesar con K = 4
Mensaje: E L P E R R O D E S A N R O Q U E T I E N E R A B O
Clave: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
Cifrado: I P T I V V S H I W E R V S U Y I X M I R I V E F S
Aqui teneis un codigo escrito en C cesar.c que os permitira encriptar y desencriptar cualquier documento con la clave K que paseis como argumento de entrada:
/* Algoritmo de Cesar con clave k */
int main (int argc, char **argv)
{
/* argumentos de entrada */
if (argc != 3) {
printf("syntax: %s -[e|d] key\n", argv[0]);
printf("example: %s -e 3\n", argv[0]);
exit(0);
}
if (argv[1][1] != 'e' && argv[1][1] != 'd') {
printf("syntax: %s -[e|d] key\n", argv[0]);
exit(0);
}
/* inicializaciones */
char ed = argv[1][1]; /* encode o decode */
int k = atoi(argv[2]); /* key */
if (k > 255)
k = k % 256;
char c;
/* encoding ... */
if (ed == 'e') {
while (read(0, &c, sizeof(unsigned char)) > 0)
printf("%c", (c + k) % 256);
}
/* decoding ... */
if (ed == 'd') {
while (read(0, &c, sizeof(unsigned char)) > 0)
printf("%c", (c - k) % 256);
}
return 0;
}
El criptosistema de Cesar es facilmente atacable usando una tecnica de criptoanalisis conocida como analisis de frecuencias, ya que la frecuencia de aparicion de cada letra en el mensaje en claro se refleja exactamente en el texto cifrado. Conociendo la letra de mayor frecuencia en el alfabeto utilizada, queda automaticamente establecida la correspondencia.
Vamos a atacar un mensaje cifrado con Cesar usando analisis de frecuencias. Sea por ejemplo el siguiente texto en castellano cifrado con una clave K, de momento desconocida. Nuestro objetivo es averiguar la clave K para descifrar el contenido del siguiente mensaje:
hqxqoxjdughodpdqfkdghfx|rqrpeuhqrtxlhurdfrugduphylyldxqorfrpdfduudtxhwrfdedodjxlwduud
Saber que el texto está en castellano es una pista muy clara de que debemos usar una tabla de frecuencias en castellano. En esta direccion teneis la tabla completa de la frecuencia de aparición de cada carácter en el idioma que mas os interese. En la tabla de castellano podremos encontrar que el caracter mas usado en nuestro idioma es el caracter 'e'.
Ahora necesitamos un programa que calcule la frecuencia de aparicion de cada caracter ASCII en el texto cifrado. Para ello hemos desarrollado este pequeño programa freq.c en C.
/* Frecuencia de cada caracter ASCII */
int main(int argc, char **argv)
{
/* inicializaciones */
unsigned long int total = 0;
float freq = 0;
int i;
int ascii[256]; /* numero de apariciones de cada ascii[i] */
for (i = 0; i < 256; i++)
ascii[i] = 0;
unsigned char c;
/* actualizacion de la tabla ascii y de la variable total */
while (read(0, &c, sizeof(unsigned char)) > 0 ) {
ascii[c]++;
total++;
}
close(0);
/* visualizacion resultados tabla ASCII */
for (i = 0; i < 256; i++) {
if (ascii[i]) {
freq = ((float) ascii[i]) / ((float) total);
printf("ASCII[%d] = %d\tfreq = %f\n", i, ascii[i], freq);
}
}
/* visualizacion total */
printf("\nTotal of characters: %lu", total);
printf("\n");
return(0);
}
El resultado aplicado sobre el texto cifrado es el siguiente:
| ASCII[100] = 15 freq = 0.176471 ASCII[117] = 9 freq = 0.105882 ASCII[114] = 8 freq = 0.094118 ASCII[104] = 7 freq = 0.082353 ASCII[120] = 7 freq = 0.082353 ASCII[102] = 6 freq = 0.070588 ASCII[113] = 6 freq = 0.070588 ASCII[108] = 4 freq = 0.047059 ASCII[111] = 4 freq = 0.047059 ASCII[112] = 4 freq = 0.047059 ASCII[103] = 3 freq = 0.035294 ASCII[101] = 2 freq = 0.023529 ASCII[106] = 2 freq = 0.023529 ASCII[116] = 2 freq = 0.023529 ASCII[119] = 2 freq = 0.023529 ASCII[121] = 2 freq = 0.023529 ASCII[107] = 1 freq = 0.011765 ASCII[124] = 1 freq = 0.011765 Total of characters: 85 |
Si el caracter mas frecuente en español es la letra 'e' (ascii 101), sabemos que alguno de los caracteres mas frecuentes del texto cifrado corresponde con la letra 'e'. Solo nos queda ir probando en secuencia las posibles claves hasta dar con una que decodifique el texto cifrado y nos deje ver con claridad el contenido del texto cifrado. Por tanto, debemos ir probando con esta secuencia de claves K:
MAX 'e'
------------------
K = 100 - 101 = -1
K = 117 - 101 = 16
K = 114 - 101 = 13
K = 104 - 101 = 3
K = 120 - 101 = 19
...
Ningun texto cumple al pie de la letra con las frecuencias características del lenguaje (es un tema estadístico), aunque podeis estar seguros que la probabilidad de que el caracter 'e' sea uno de los caracteres mas frecuentes, es muy alta.
¿Quien será el primero en dejarme un comentario con el resultado del texto en claro?
Existen varios concursos planteados por distintos organismos oficiales como la CIA y conocidísimas empresas todopoderosas como Google con el proposito de cazar talentos dispersos por esos mundos...
En los exteriores de las oficinas de la CIA en Langley (Virgina) se encuentra una escultura enorme de bronce, de unos cuatro metros de altura, conocida como kryptos, en la que se esconden cuatro mensajes cifrados escritos en ingles. La primera persona que anunció publicamente haber resuelto los tres primeros fue James Gillogly, y por lo que se sabe, la cuarta parte continua sin resolver.
En las paredes del MIT aparecieron carteles de Google con este críptico mensaje acompañado del texto "si puedes averiguar esto, puedes tener futuro en Google". El mensaje encriptado contiene un número de teléfono al que llamar en caso de acertarlo.
Para resolver estos criptosistemas, necesitareis investigar por vuestra cuenta sobre otros criptosistemas por trasposicion como el Vigenere, una variante del metodo de Cesar que usa cadenas de texto como clave. Y tambien los criptosistemas por sustitucion, que unicamente reordenan la posicion de los mensajes en el texto. Y sobre variantes de unos y otros, incluso combinadas entre si. Asi que manos a la obra... ¿Os veis con ganas de intentar trabajar... en Google ... o en la CIA? Yes you can! Why not! :-)
2 comentarios:
Hola Angel, aquí tienes la frase:
"en un lugar de la mancha de cuyo nombre no quiero acordarme vivia un loco macarra que tocaba la guitarra"
Eres el primero en dar un resultado, es el correcto. Enhorabuena Anónimo! Como has visto, era sencillo pero había que ponerse. Espero que lo hayas pasado bien, ese era el objetivo principal. Gracias por pasar por el blog.
Publicar un comentario