-[ 0x06 ]-------------------------------------------------------------------- -[ Criptografia Practica ]--------------------------------------------------- -[ by blackngel ]----------------------------------------------------SET-35-- ^^ *`* @@ *`* HACK THE WORLD * *--* * ## by blackngel || * * * * (C) Copyleft 2008 everybody _* *_ 1 - Prologo 2 - Introduccion 3 - Sistema Hayhanen (Simple) 4 - Prueba de Concepto 5 - Algoritmos Basicos 6 - Analisis de Frecuencias 7 - CrypTool - CrypTooLinux 8 - Conclusion 9 - Referencias ---[ 1 - Prologo Estas sentand@ en el sofa de tu casa, tu cabeza vacila entre el monitor de television y la pantalla del portatil. Desechas el primero y abres el nuevo manual de criptografia que te acabas de descargar de tu repositorio habitual. Lees pagina tras pagina, 10, 20, 30 y zas. Cierras la tapa del portatil y te dedicas nuevamente a ver esa telebasura que acabara destruyendo tu mente, esa carcoma que te consumira poco a poco hasta dejarte reducido en la mas profunda de las ineptitudes. Pero, por que? Muy facil, llevas toda tu vida leyendo teoria (sobre todo cuando hablamos de criptografia). Las representaciones graficas son un apoyo que te ayudan a avanzar; pero no es suficiente. Lo que te falta es decir: 1 - Puedo hacerlo. 2 - Voy a hacerlo. Pues hazlo... ---[ 2 - Introduccion Vamos a meterle mano al codigo. Tomaremos de la mano un e-book titulado: - Una introduccion a la Criptografia [1]. El libro es muy bueno. Con el podras empezar a entender la criptografia desde lo mas basico hasta los metodos y algoritmos mas complejos y actuales. Todo se explica de forma educativa y con numerosos graficos. Pero hay algo que le falta, y esto no se le puede reprochar a este libro, pues muchos mas (y haberlos hailos) siguen el mismo camino. EL CODIGO. El ejercicio que vamos a tratar en este texto versa precisamente de como implementar uno de los primeros ejemplos de criptografia basica que se presentan en el libro. Con ello conseguiremos ver por donde se mueve este mundo. El objetivo es que cuando termines este articulo tengas el valor suficiente como para seguir aprendiendo a base de practica y esfuerzo. Y ahora solo planteate lo siguiente: if (TIEMPO_LECTURA_Y_OCIO > TIEMPO_PRACTICA_Y_EJERCICIO) { printf("\nTu jamas seras un hacker\n"); exit(LIFE_ERROR); } else printf("\nEstas en el camino correcto\n"); ... ... ... ---[ 3 - Sistema Hayhanen (Simple) El sistema critografico que se presenta al principio del libro (deberias leerlo), es en realidad una version totalmente simplificada del utilizado por el espia ruso mencionado en el titulo de esta seccion. Basicamente viene a hacer lo siguiente: Se escoge un texto plano a cifrar en el que se sustituyen los espacios por puntos. Algo como: ESTAMOS.ENTRANDO.EN.LA.NASA Despues, con la ayuda de una contrase~a y las letras del abecedeario se genera una tabla tal como la siguiente: tabla[3][10]; 1 2 3 4 5 6 7 8 9 0 - - - - - - - - - - 0| S E C R T O . A 1|B D F G H I J K L M 2|N ~ P Q U V W X Y Z Es muy sencillo: 1 - Los dos primeros valores de la tabla quedan vacios. 2 - Se coloca la contrase~a sin repetir las letras. 3 - Se coloca el punto '.' que hace de sustituto al espacio. 3 - Se coloca el resto del abecedario por orden y sin repetir. Se cambian las letras del mensaje por los valores correspondientes en la tabla: E S T A M O S . E N T R A N D O . E N . L A . N A S A 4 3 7 0 10 8 3 9 4 21 7 6 0 21 12 8 9 4 21 9 19 0 9 21 0 3 0 Y aqui la razon de porque los elementos 'tabla[0][1]' y 'tabla[0][2]' se dejan vacios. A la hora de descifrar el mensaje y leer esta secuencia de numeros, si nos encontramos un 1 o un 2 querra decir que debemos tener en cuenta la siguiente cifra. Y esta condicion siempre se cumple, pues ninguna letra de las que ocupan la primera fila poseen este valor individualmente. Pero no hemos acabado. Ahora entra en juego el valor de la clave. Le damos un valor desde '1' hasta 'x' (la longitud de la clave) por orden alfabetico y teniendo en cuenta que las repeticiones tienen un valor superior segun se encuentren hacia la derecha. Veamoslo en este ejemplo: S E C R E T O 6 2 1 5 3 7 4 Repetimos esta cadena de numeros hasta completar la longitud del mensaje y sumamos los valores uno a uno (descartando las decenas) de la siguiente manera: 6215374621537462153746215374621537 4370108394217602112894219190921030 + ---------------------------------- 0585472915744064265530424464542567 -> Cifrado Y esta cadena es definitivamente nuestro mensaje cifrado. El proceso inverso para descifrar es sencillo: 1 - Crear la tabla con la clave para descifrar. 2 - Obtener los valores de la clave y restarselos al mensaje cifrado. 3 - Buscar en la tabla los caracteres correspondientes a los valores que se~alan esta nueva cadena resultante. Ej.: Si nos encontramos un '4' -> Accedemos a tabla[0][4] que es una 'E' Si nos encontramos un '2' -> Leemos el siguiente digito |-> Ej.: Si es un '1' -> tabla[2][1] = 'N' Todo esto nos lo explica igual de bien e incluso muchisimo mejor el libro con el que contamos. Y nosotros podriamos pasar al siguiente tipo de cifrado pensando que esto es facil y que ya sabemos como hacerlo. Pero hay algo que en el 'hacking' se tiene muy en cuenta, y es lo siguiente: - AUN NO LO HAS DEMOSTRADO ---[ 4 - Prueba de Concepto Este titulo suena a 'exploit' pero nada que se le parezca... Los que habeis leido hasta aqui (solo requiere unos minutos) ya sabeis de que va el tema. Asi que lo que viene a continuacion es el tipico chapuzon a la piscina del codigo fuente. Pense, en un principio, colocar todo el programa de un golpe y explicarlo en los comentarios; pero alguno podria desistir a la primera de cambio. Es por ello que lo explicare por fases (procedimientos/funciones en este caso) y asi sera mas facil seguir la logica de los pasos que se explicaron en la seccion anterior. Cuando juntes las piezas podras compilarlo con el comando super-secreto de toda la vida: $gcc bcrypt.c -o bcrypt Empezamos por lo sencillo: **-------------------------------------------------------------------------** #include #include #include int is_diferent(char, int); /* COMPRUEBA REPETICIONES EN LA TABLA */ void crear_tabla(void); /* GENERA LA TABLA 3 X 10 */ void imprimir_tabla(void); /* IMPRIME TABLA PARA PRUEBAS */ void leer_password(void); /* GENERA VALORES PARA LA CONTRASE~A */ void cifrar(void); /* CIFRA MENSAJE */ void descifrar(void); /* DESCIFRA MENSAJE */ char matrix[3][10]; /* TABLA PARA GENERAR CODIGOS */ int *valores_c; /* VALORES CORRESPONDIENTES A LAS LETRAS EN LA TABLA */ int *valores_d; /* VALORES CIFRADOS QUE VAN A SER DESCIFRADOS */ int *pass_val; /* VALORES CORRESPONDIENTES A LA CONTRASE~A */ char *password; /* CONTRASE~A */ char *mensaje; /* MENSAJE */ static int len_pass; /* LONGITUD CONTRASE~A */ static int len_msg; /* LONGITUD MENSAJE */ static int val = 0; /* CANTIDAD DE VALORES EN '*valores_c' */ char alfabeto[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N', '~','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; **-------------------------------------------------------------------------** 1 - Archivos de cabecera. 2 - Declaraciones de funciones. 3 - Declaraciones de variables y matrices (*). (*) No te preocupes, iras viendo que hacen las diferentes variables muy poco a poco en cada funcion. Cada una tiene una mision especifica. **-------------------------------------------------------------------------** int main(int argc, char *argv[]) { int cifrado = 0; if (argc < 4) { fprintf(stderr, "\nUsage: ./bcrypt [-c|-d] message password\n"); exit(0); } /* COMPROBAMOS ARGUMENTOS Y USO DEL PROGRAMA */ if (strncmp(argv[1], "-c", 2) == 0) cifrado = 1; else if (strncmp(argv[1], "-d", 2) != 0) { fprintf(stderr, "\nUsage: ./bcrypt [-c|-d] message password\n"); exit(0); } asprintf(&mensaje, "%s", argv[2]); /* ALMACENAMOS MENSAJE */ len_msg = strlen(mensaje); /* LONGITUD DEL MENSAJE */ asprintf(&password, "%s", argv[3]); /* ALMACENAMOS CONTRASE~A */ len_pass = strlen(password); /* LONGITUD DE LA CONTRASE~A */ if (len_pass >= 10) { /* EMPEZAREMOS POR LO SENCILLO */ printf("\nUtilice una contrase~a de 9 caracteres como maximo"); exit(0); } leer_password(); /* CONSEGUIMOS LOS VALORES NUMERICOS DE LA CONTRASE~A */ crear_tabla(); /* GENERAMOS LA TABLA CORRESPONDIENTE A ESTA CONTRASE~A */ if (cifrado) /* CIFRAR O DESCIFRAR ? */ cifrar(); else descifrar(); puts("\n\n"); free(password); /* DE VEZ EN CUANDO HAY QUE SACAR LA BASURA !!! */ free(mensaje); free(pass_val); free(valores_c); free(valores_d); pass_val = NULL; valores_c = NULL; valores_d = NULL; password = NULL; mensaje = NULL; return 0; } **-------------------------------------------------------------------------** Lo mas importante: 1 - Almacenamos mensaje y contrase~a. 2 - Obtenemos valores de la contrase~a y generamos tabla 3 - Llamamos a la funcion cifrar() o descifrar(). Continuemos: **-------------------------------------------------------------------------** void leer_password(void) { int i, w; int t = 1; char *ptr; pass_val = (int *) calloc((len_pass), sizeof(int)); /* PEDIMOS MEMORIA */ if (pass_val == NULL) { fprintf(stderr, "\nNo hay suficiente memoria\n"); exit(-1); } ptr = password; /* PUNTERO TEMPORAL PARA TRABAJAR */ for (i = 0; i < len_pass; i++) { for (w = 0; w < len_pass; w++) { /* COMPARAMOS CADA CARACTER CON EL */ if (ptr[i] > ptr[w]) /* RESTO, SI ES MAYOR AUMENTAMOS SU */ t += 1; /* VALOR EN 1 */ } for (w = 0; w < i; w++) { /* SI ADEMAS HABIA ALGUN CARACTER */ if (ptr[i] == ptr[w]) /* IGUAL ANTES QUE ESTE, AUMENTAMOS */ t += 1; /* SU VALOR EN 1 */ } pass_val[i] = t; /* GUARDAMOS EL VALOR EN LA MATRIZ */ t = 1; /* RESTAURAMOS EL VALOR MINIMO */ } } **-------------------------------------------------------------------------** Este codigo seguramente podria mejorarse. Pero los 3 bucles muestra bien el cometido: 1 - El bucle exterior recorre del primer al ultimo caracter de la contrase~a. 2 - El primer bucle interno establece un valor segun el orden alfabetico. 3 - El segundo bucle interno dice que si ya habia una letra igual antes de la que se analiza, esta ultima tendra un valor superior en una unidad. * Fijate bien en el segundo bucle para no llevarte a confusiones. Solo recorre los caracteres que hay antes del que se analiza. Es decir. Para la primera de la contrase~a el bucle no se ejecuta (no hay letras anteriores), para la segunda solo se ejecuta una iteracion y asi sucesivamente... Ahora vamos con una de las partes mas interesantes y la base del algoritmo: **-------------------------------------------------------------------------** void crear_tabla(void) { int i = 3; int j = 0; int z = 0; matrix[0][1] = ' '; /* DOS PRIMEROS ELEMENTOS VACIOS, METEMOS */ matrix[0][2] = ' '; /* ESPACIOS PARA IMPRIMIR LA TABLA CORRECTAMENTE */ while (*password) { /* RECORREMOS LA CONTRASE~A Y MIRAMOS */ if (is_diferent(*password, 0)) { /* SI EL CARACTER YA ESTA EN LA TABLA */ if (i == 10) { /* DE ULTIMO SE RELLENA EL ELEMENTO */ matrix[j][0] = *password++; /* '0' DE CADA FILA DE LA TABLA */ j += 1; /* RECUERDA: 1-2-3-4-5-6-7-8-9-0 */ i = 1; /* Y PASAMOS A LA SIGUIENTE FILA */ } else { /* SINO */ matrix[j][i] = *password++; /* ESCRIBIMOS EL CARACTER SIN MAS */ i += 1; } } else /* SI EL CARACTER YA ESTABA GUARDADO EN LA TABLA */ *password++; /* PASAMOS DIRECTAMENTE AL SIGUIENTE */ } matrix[j][i] = '.'; /* DESPUES DE LA CONTRASE~A ALMACENAMOS EL PUNTO */ i += 1; for (z = 0; z < 27; z++) { /* Y AHORA METEMOS EL RESTO DE */ if (is_diferent(alfabeto[z], 0)) { /* LAS LETRAS DEL ALFABETO */ if (i == 10) { /* UTILIZANDO PRACTICAMENTE LA */ matrix[j][0] = alfabeto[z]; /* MISMA TECNICA QUE ANTES. */ j += 1; i = 1; } else { matrix[j][i] = alfabeto[z]; i += 1; } } } imprimir_tabla(); /* SOLO PARA LA ETAPA DE PRUEBAS */ } **-------------------------------------------------------------------------** Entre los comentarios y el ejemplo anteriormente presentado tienes mas que de sobra para entender lo que acabamos de hacer. Lo siguiente queda bonito en el proceso de pruebas. Comprobaremos asi si las tablas se crean correctamente. **-------------------------------------------------------------------------** void imprimir_tabla(void) { printf("\n1 2 3 4 5 6 7 8 9 0"); printf("\n- - - - - - - - - -"); printf("\n%c %c %c %c %c %c %c %c %c %c\n", matrix[0][1], matrix[0][2], matrix[0][3], matrix[0][4], matrix[0][5], matrix[0][6], matrix[0][7], matrix[0][8], matrix[0][9], matrix[0][0]); printf("\n%c %c %c %c %c %c %c %c %c %c\n", matrix[1][1], matrix[1][2], matrix[1][3], matrix[1][4], matrix[1][5], matrix[1][6], matrix[1][7], matrix[1][8], matrix[1][9], matrix[1][0]); printf("\n%c %c %c %c %c %c %c %c %c %c\n", matrix[2][1], matrix[2][2], matrix[2][3], matrix[2][4], matrix[2][5], matrix[2][6], matrix[2][7], matrix[2][8], matrix[2][9], matrix[2][0]); puts("\n"); } **-------------------------------------------------------------------------** Bueno, lo anterior no requiere mas explicacion no? Bien ordenadita ademas para que podais seguir el ejemplo de la seccion anterior. Ahora vamos a ver una porcion de codigo interesante. En realidad tiene dos cometidos, pero he utilizado la estructura para no repetir mas codigo. Sus funciones tienen que ver con el metodo anterior y el que le sigue, por eso lo he situado en este lugar. **-------------------------------------------------------------------------** int is_diferent(char c, int op) { int i, j; static int x = 0; for (i = 0; i < 3; i++) { for (j = 0; j < 10; j++) { if (matrix[i][j] == c) /* ENCONTRAMOS UN CARACTER EN LA TABLA */ if (op) { if (i == 0) { /* SI ESTA EN LA PRIMERA FILA EL VALOR */ valores_c[x] = j; /* ES EL CORRESPONDIENTE A LA COLUMNA */ x += 1; val += 1; } else { /* SI ESTA EN LA PRIMERA O SEGUNDA FILA */ valores_c[x] = i; /* EL VALOR DE LA LETRA ES EL NUMERO DE */ x += 1; val += 1; /* LA FILA SEGUIDO POR EL NUMERO DE LA */ valores_c[x] = j; /* COLUMNA */ x += 1; val += 1; } } else return 0; /* FALSE - HEMOS ENCONTRADO UN CARACTER IGUAL */ } } return 1; /* TRUE - SI LLEGAMOS AL FINAL DECIMOS QUE ES DIFERENTE */ } **-------------------------------------------------------------------------** Para aclararnos, vamos a separar las dos acciones de este metodo: 1 - Cuando OP = 0: -> Comprueba si un caracter se encuentra ya almacenado dentro de la tabla ('matrix[][]'), asi nunca los repetiremos. 2 - Cuando OP = 1: -> Buscamos los caracteres del mensaje a cifrar en la tabla y si los encontramos guardamos el valor correspondiente a su posicion. Ejemplo anterior: Si buscamos una 'E' la encontramos en la pirmera fila y guardamos su numero de columna: '4'. Si buscamos una 'N' la encontramos en la ultima fila y guardamos su numero de fila y columna: '21'. Y aqui una de las esperadas funciones. Se encarga de hacer la suma entre los valores del mensaje a cifrar y la contrase~a e imprime el resultado por pantalla. **-------------------------------------------------------------------------** void cifrar(void) { int i; int tmp; valores_c = (int *) calloc((len_msg), sizeof(int)); if (valores_c == NULL) { fprintf(stderr, "\nNo hay suficiente memoria\n"); exit(-1); } for (i = 0; i < len_msg; i++) { /* SEGUNDA FUNCION DE is_diferent() */ is_diferent(mensaje[i], 1); /* OBTENEMOS LOS VALORES NUMERICOS DEL MSG */ } printf("\n-----BEGIN BLACK-CRYPT MSG-----\n"); for (i = 0; i < val; i++) { tmp = valores_c[i] + pass_val[i % len_pass]; /* MODULO LONGITUD MSG */ printf("%d", tmp % 10); /* IMPRIMIMOS SOLO LAS UNIDADES */ } printf("\n------END BLACK-CRYPT MSG------\n"); } **-------------------------------------------------------------------------** Si hay algo a destacar en la funcion anterior es la utilizacion del 'operador modulo (%)'. Gracias a el nos evitamos crear una cadena igual de larga que el mensaje con los valores de la contrase~a repetidos; pues hace esta misma funcion, vulgarmente reinicia cada vez que alcanza el final. Seguidamente nos vuelve a servir de ayuda para tomar solo las unidades en caso de que el resultado de la operacion anterior sea 10 o superior a esta cantidad. Nos quitamos de encima asi la necesidad de utilizar algo como: if (tmp >= 10) /* SI LA SUMA ES SUPERIOR A 9 */ printf("%d", tmp - 10); /* IMPRIMIMOS SOLO LAS UNIDADES */ else /* EN CASO CONTRARIO */ printf("%d", tmp); /* IMPRIMIMOS EL RESULTADO */ Y ya por ultimo, como obtener el mensaje a partir de una cadena cifrada: **-------------------------------------------------------------------------** void descifrar(void) { int i, j; valores_c = (int *) calloc((len_msg), sizeof(int)); /* PEDIMOS MEMORIA */ valores_d = (int *) calloc((len_msg), sizeof(int)); /* PUEDO REPETIR ? */ if (valores_c == NULL || valores_d == NULL) { fprintf(stderr, "\nNo hay suficiente memoria\n"); exit(-1); } for (i = 0; i < len_msg; i++) { /* CUTRE - PASAMOS LA CADENA CIFRADA */ valores_d[i] = mensaje[i] - 48; /* A UNA MATRIZ DE VALORES NUMERICOS */ } for (i = 0; i < len_msg; i++) { /* RESTAMOS A LA MATRIZ DE VALORES */ j = pass_val[i % len_pass]; /* LOS VALORES PROPIOS DE LA CONTRASE~A */ if (j > valores_d[i]) /* NOS ASEGURAMOS DE OBTENER */ valores_c[i] = valores_d[i] + 10 - j; /* SIEMPRE UN VALOR POSITIVO */ else valores_c[i] = valores_d[i] - j; } printf("\n-----BEGIN BLACK-DECRYPT MSG-----\n"); for (i = 0; i < len_msg; i++) { if (valores_c[i] == 1) { /* SI ENCONTRAMOS UN '1' */ printf("%c", matrix[1][valores_c[i + 1]]); /* TENEMOS EN CUENTA EL */ i += 1; /* SIGUIENTE DIGITO */ } else if (valores_c[i] == 2) { /* SI ENCONTRAMOS UN '2' */ printf("%c", matrix[2][valores_c[i + 1]]); /* TENEMOS EN CUENTA EL */ i += 1; /* SIGUIENTE DIGITO */ } else /* EN CASO CONTRARIO */ printf("%c", matrix[0][valores_c[i]]); /* IMPRIMIMOS EL CARACTER*/ } /* EN ESA POSICION */ printf("\n------END BLACK-DECRYPT MSG------\n"); } **-------------------------------------------------------------------------** Pues nada, lo visto. Ya hemos explicado suficientemente el metodo. Los pasos son los contrarios al proceso de cifrado. No ha sido tan dificil verdad? ERRORES A CONSIDERAR: --------------------- Uno de los errores principales de este programa es que podria fallar de una forma catastrofica si utilizamos e~es en la contrase~a. No siempre tiene que ocurrir, pero no es recomendable usarlas, y la razon es la siguiente: -> Al no ser un caracter ASCII estandar, el programa lo interpretara en realidad como dos valores que son '-61' y '-111'. Esto provoca errores en la tabla de 3 x 10 y ya de entrada interpreta mal la longitud de la contrase~a pensando (que pensara un PC?) que es mayor. Por otro lado, prueba a permitir longitudes de clave mas grandes y observa los resultados. EN RESUMEN: ----------- - ANALIZA EL CODIGO - ESTUDIA EL CODIGO - Y ADAPTA EL CODIGO ---[ 5 - Algoritmos Basicos Ahora mostrare algunos de los algoritmos mas basicos de la criptografia antigua. El motivo de situarlos aqui es muy sencillo, de haberlos colocado al principio, el articulo hubiera perdido todo su interes. CIFRADO DEL CESAR ----------------- **-------------------------------------------------------------------------** #include #include #include int main(int argc, char *argv[]) { int i, tmp; int clave; int cifrado = 0; int longitud; char *mensaje; if (argc < 4) { fprintf(stderr, "\nUsage: ./cesarcrypt [-c|-d] mensaje clave\n"); exit(0); } if (strncmp(argv[1], "-c", 2) == 0) cifrado = 1; else if (strncmp(argv[1], "-d", 2) != 0) { fprintf(stderr, "\nUsage: ./cesarcript [-c|-d] mensaje clave\n"); exit(0); } mensaje = argv[2]; clave = atoi(argv[3]); longitud = strlen(mensaje); if (cifrado) { printf("\n-----BEGIN CESAR-CRYPT MSG-----\n"); for (i = 0; i < longitud; i++) { tmp = mensaje[i] + clave; printf("%c", tmp); } printf("\n------END CESAR-CRYPT MSG------\n"); } else { printf("\n-----BEGIN CESAR-DECRYPT MSG-----\n"); for (i = 0; i < longitud; i++) { tmp = mensaje[i] - clave; printf("%c", tmp); } printf("\n------END CESAR-DECRYPT MSG------\n"); } puts("\n"); return 0; } **-------------------------------------------------------------------------** EXPLICACION: Lo de toda la vida, desplazamos las letras en el alfabeto tantas posiciones como indique la clave y realizamos la sustitucion. En este caso logramos lo mismo sumando o restando la clave a cada uno de los caracteres ASCII que componen el mensaje. CIFRADO XOR ----------- **-------------------------------------------------------------------------** #include #include #include int main(int argc, char *argv[]) { int car; FILE *fin, *fout; if (argc < 4) fprintf(stderr, "\nUsage: ./xorcript filein.txt fileout.txt clave\n"); exit(0); } if ((fin = fopen(argv[1], "rb")) == NULL) { printf("\nNo se pudo abrir: %s.\n", argv[1]); } if ((fout = fopen(argv[2], "wb")) == NULL) { printf("\nNo se pudo abrir: %s.\n", argv[2]); } while ((car = getc(fin)) != EOF) { car ^= *argv[3]; /* MAGIA */ putc(car, fout); } printf("\nLa operacion XOR se ha completado correctamente\n"); printf("\nResultado XOR guardado en %s.\n", argv[2]); fclose(fin); fclose(fout); return 0; } **-------------------------------------------------------------------------** EXPLICACION: El cifrado mas simple y famoso de la historia. Un xor '^' podria definirse como una funcion asi: xor(texto_claro, clave); /* CIFRAR */ xor(texto_cifrado, clave); /* DESCIFRAR */ Pero por suerte lo tenemos todo junto en un operador. Un mensaje cifrado con una clave mediante XOR se descifra ejecutando otro XOR con la misma clave. Es toda una funcion de cifrado en miniatura. ---[ 6 - Analisis de Frecuencias En el libro ya mencionado anteriormente se expone un metodo acerca de como descifrar un texto que ha sido cifrado mendiante un algoritmo de sustitucion. Se entiende muy clarito y se pueden seguir los pasos manualmente sin mayor problema. Pero nosotros tenemos otro objetivo: - AUTOMATIZAR UNA PARTE DE LA TAREA Para ello trataremos de implementar en un lenguaje de programacion cualquiera la primera parte del criptoanalisis, que es precisamente el analisis de frecuencias para averiguar en que idioma esta escrito un texto cifrado por sustitucion. En mi caso "C" para seguir con la tradicion. Pero vamos al asunto. Copiare aqui el texto cifrado que se expone en el libro para que no tengas que acudir a el continuamente interrumpiendo la explicacion: HS2BHF7JT7207HS2B9C722SJ47JT72MP7BN77JMP7H92BS2926 929J6SNMP72FMP7JS17N7B7H967J96SJ7NN7170FS9J9097J7H 070SK9NS29TS0S2CP19J3HS2192170FT9J92SH922S8N7H926S 8N729198H727JTN9K98H72BS292MP7H72HH7J9JSH72Q9BF9JH 9QF097JT7N9D93MPF7J6SJ79H2FH7JBFSPJ90719J2SK90SN07 F16N7BF29N7BSN09BFSJ3D93T918F7JMPF7JD9B7171SNF9BSJ H9B9N9982SNT937JH9B9N96FJT90S7H472TS07H9872TF9NPFJ 07H991SNS292P6HFB9JT7872TF9B9J2909H919JS2P57T9J0SH 9CN7JT737H1FN9NHH7JS07919N4PN9BS1SPJ19N7JB9H190S (*) En el texto original las 'T's son 'e~es' pero las he sustituido para evitar el problema que ya hemos comentado. Puedo permitirme este lujo gracias a que es un cifrado por sustitucion monoalfabetico. En otro caso podria destrozar por completo el mensaje. Bien, lo que se nos pide es que analicemos la frecuencia de los caracteres que componen el texto y que comparemos los porcentajes resultantes con las tablas de frecuencia correspondientes a los idiomas: - ESPA~OL, INGLES, FRANCES Y ALEMAN Podrian ser tantos como quisieras, pero para el ejemplo que nos toca son mas que suficientes. El codigo es bruto (todo en main(...)) y no esta depurado, pero aqui lo teneis. Esta es la implementacion correspondiente: **-------------------------------------------------------------------------** #include #include #include float car_val[26][2]; /* NUMERO DE APARICIONES DE CADA CARACTER */ float freq[26][2]; /* FRECUENCIA DE APARICION DE CADA CARACTER */ float frecuencias[4][26][2] = { /* LAS FRECUENCIAS DE LOS 4 IDIOMAS */ /* ESPA~OL */ { {69, 13.676}, {65, 12.529}, {79, 8.684}, {83, 7.980}, {82, 6.873}, {78, 6.712}, {73, 6.249}, {68, 5.856}, {76, 4.971}, {67, 4.679}, {84, 4.629}, {85, 3.934}, {77, 3.150}, {80, 2.505}, {66, 1.420}, {71, 1.006}, {89, 0.895}, {86, 0.895}, {81, 0.875}, {72, 0.704}, {70, 0.694}, {90, 0.523}, {74, 0.443}, {88, 0.221}, {87, 0.023}, {75, 0.004} }, /* INGLES */ { {69, 13.105}, {84, 10.468}, {65, 8.151}, {79, 7.995}, {78, 7.098}, {82, 6.832}, {73, 6.345}, {83, 6.101}, {72, 5.259}, {68, 3.788}, {76, 3.389}, {70, 2.924}, {67, 2.758}, {77, 2.536}, {85, 2.459}, {71, 1.994}, {89, 1.982}, {80, 1.982}, {87, 1.539}, {66, 1.440}, {86, 0.919}, {75, 0.420}, {88, 0.166}, {74, 0.132}, {81, 0.121}, {90, 0.077} }, /* FRANCES */ { {69, 17.564}, {65, 8.147}, {83, 8.013}, {73, 7.559}, {84, 7.353}, {78, 7.322}, {82, 6.291}, {85, 5.991}, {76, 5.783}, {79, 5.289}, {68, 4.125}, {67, 3.063}, {77, 2.990}, {80, 2.980}, {86, 1.557}, {81, 1.361}, {71, 1.051}, {70, 0.959}, {66, 0.876}, {72, 0.721}, {74, 0.598}, {88, 0.350}, {89, 0.116}, {90, 0.072}, {75, 0.041}, {87, 0.020} }, /* ALEMAN */ { {69, 16.693}, {78, 9.905}, {73, 7.812}, {83, 6.765}, {84, 6.742}, {82, 6.539}, {65, 6.506}, {68, 5.414}, {72, 4.064}, {85, 3.703}, {71, 3.647}, {77, 3.005}, {67, 2.837}, {76, 2.825}, {66, 2.566}, {79, 2.285}, {70, 2.044}, {75, 1.879}, {87, 1.396}, {86, 1.096}, {90, 1.002}, {80, 0.944}, {74, 0.191}, {81, 0.055}, {89, 0.032}, {88, 0.022} } }; int main(int argc, char *argv[]) { char car; /* Caracteres leidos del archivo */ int bytes; /* Tama~o del texto cifrado */ int tmp1, tmp2; /* Para el algoritmo de la burbuja, valores temporales */ int i = 0; int j = 0; /* Variables para bucles */ int w = 0; float cdif; /* Distancias entre frecuencias del texto cifrado */ float esp_freq, eng_freq, fra_freq, ale_freq; FILE *fin; if (argc < 2) { fprintf(stderr, "\nUsage: ./freq archivo_cifrado\n"); exit(0); } /* UTILIZAMOS UN ARCHIVO CON TEXTO CIFRADO COMO ARGUMENTO */ fin = fopen(argv[1], "r"); if (fin == NULL) { fprintf(stderr, "\nError en la apertura del fichero\n"); exit(0); } /* BUSCAMOS NUMEROS EN EL TEXTO Y CUANTAS VECES APARECEN */ for (i = 48; i < 58; i++) { car_val[w][0] = i; while ((car = fgetc(fin)) != EOF) { if ( car == (char)i) j += 1; } if (j) { car_val[w][1] = j; w += 1; } fseek(fin, 0, 0); j = 0; } /* BUSCAMOS LETRAS EN EL TEXTO Y CUANTAS VECES APARECEN */ /* APROVECHAMOS PARA OBTENER EL TAMA~O DEL TEXTO CIFRADO */ int docount = 1; for (i = 65; i < 91; i++) { car_val[w][0] = i; while ((car = fgetc(fin)) != EOF) { if (docount) { if (car != '\n' && car != '\r') bytes += 1; } if (car == (char)i) j += 1; } docount = 0; if (j) { car_val[w][1] = j; w += 1; } fseek(fin, 0, 0); j = 0; } fclose(fin); /* AL FINAL, EN LA PRIMERA COLUMNA DE car_val[][] QUEDAN ALMACENADOS LOS */ /* CARACTERES ENCONTRADOS Y EN LA SEGUNDA EL NUMERO DE VECES QUE APARECEN */ printf("\n-----------"); printf("\nAPARICIONES"); printf("\n-----------\n"); /* APLICAMOS EL ALGORITMO DE LA BURBUJA PARA ORDENAR DE MAYOR A MENOR */ for (j = 0; j < 26; j++) { for (i = j+1; i < 26; i++) { if (car_val[j][1] < car_val[i][1]) { tmp1 = car_val[j][0]; tmp2 = car_val[j][1]; car_val[j][0] = car_val[i][0]; car_val[j][1] = car_val[i][1]; car_val[i][0] = tmp1; car_val[i][1] = tmp2; } } if (car_val[j][1] > 0) { printf("\n- %c - tiene: %d apariciones", (int)car_val[j][0], (int)car_val[j][1]); } } printf("\n\nPulse [INTRO] para analizar frecuencias\n"); getchar(); printf("\n-----------"); printf("\nFRECUENCIAS"); printf("\n-----------\n"); /* UNA REGLA DE 3 SIMPLE PARA OBTENER LOS PORCENTAJES */ /* SI EN 'LONGITUD FICHERO' HAY 70 CARACTERES '9' EN 100 HAY ... */ for (i = 0; i < 26; i++) { freq[i][0] = car_val[i][0]; freq[i][1] = (car_val[i][1] * 100.0) / bytes; if (freq[i][1] > 0.0) { printf("\n- %c - tiene freq: %f", (int)freq[i][0], freq[i][1]); } } /* Y POR ULTIMO CALCULAMOS LA DISTANCIA ENTRE LAS FRECUENCIAS DEL TEXTO */ /* CIFRADO Y LAS DE LAS TABLAS DE FRECUENCIA PARA CADA UNO DE LOS IDIOMAS */ for (j = 0; j < 4; j++) { for (i = 0; i < 26; i++) { /* FORMULA MAGICA: SUMA DE LOS CUADRADOS DE LAS DIFERENCIAS */ if (freq[i][1] > 0.0){ cdif = cdif + pow((freq[i][1] - frecuencias[j][i][1]), 2); } else { cdif = cdif + pow((0.0 - frecuencias[j][i][1]), 2); } } switch (j) { /* Esto se vuelve extremadamente ineficiente */ case 0: /* a cuantos mas idiomas sean analizados. */ esp_freq = cdif; /* Se ha realizado de este modo para que sea */ break; /* didacticamente mas comprensible, pero el */ case 1: /* 'modus operandi' debe ser rediseņado. */ eng_freq = cdif; break; case 2: fra_freq = cdif; break; case 3: ale_freq = cdif; break; default: break; } cdif = 0; } printf("\n\nDISTANCIA DE FRECUENCIAS"); printf("\n------------------------"); printf("\nESPA~OL: %f", esp_freq); printf("\nINGLES: %f", eng_freq); printf("\nFRANCES: %f", fra_freq); printf("\nALEMAN: %f", ale_freq); puts("\n\n"); return 0; } **-------------------------------------------------------------------------** Observaras algo interesante si has leido el libro. Las frecuencias que nosotros obtenemos son las siguientes: ESPA~OL: 10.815223 INGLES: 25.101366 FRANCES: 39.845760 ALEMAN: 24.572540 Las del libro son: ESPA~OL: 10.815 INGLES: 25.108 FRANCES: 39.837 ALEMAN: 24.545 Vemos pues que acertamos de pleno para el espa~ol; pero existe una diferencia en los decimales de las frecuencias de los otros tres idiomas. Apenas son significativas pero: - Hemos cometido un error o los autores hicieron las cuentas a mano? Bueno, y a partir de aqui podeis seguir automatizando tareas, incluso con un poco de cabeza podriais lograr un codigo que os acercase practicamente a la solucion. Fijate que todavia puedes: - REALIZAR BUSQUEDAS DE BIGRAMAS (En espa~ol) -> ES EN EL DE LA OS UE AR RA RE ON ER AS ST AL AD TA CO OR (En ingles) -> TH HR IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE IE OF HE - REALIZAR BUSQUEDAS DE TRIGRAMAS (En espa~ol) -> QUE EST ARA ADO AQU CIO DEL NTE EDE OSA PER NEI IST SDE (En ingles) -> THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH HIS Ya sabes... si te ha gustado tienes deberes. De todos modos siempre puedes (y debes) implementar lo hasta aqui descrito segun tu manera de ver las cosas. Y ahora, dos apuntes. Si quieres aprender mas acerca del criptoanalisis practico de varios metodos de cifrado, te recomendaria echases un vistazo a la siguiente presentacion, de la mano de P. Caballero Gil [3]. La primera parte resultara interesantisima para aquellos que hayan gozado con la lectura de los "Relatos" de Edgar Allan Poe (libro que yo aprovechaba para leer en clase de matematicas };-D ). Y segundo, para los mas vagos, no ocultare que este trabajo ya ha sido realizado con anterioridad. Que esperabais? Podeis obtener una lectura interesantisima visitando el siguiente enlace [4]. En el texto mencionado se citan dos programas que han sido realizados hace tiempo para analizar el idioma en que esta escrito un texto. Son los siguientes: - TEXTCAT [5] -> Identifica 76 idiomas. (1) - LEXTEXT LANGUAGE IDENTIFIER [6] -> Identifica 260 idiomas. (2) (1) TextCat esta escrito en 'perl', puedes bajarte el codigo fuente. Comprobaras asi que utiliza un metodo bastante diferente del que nosotros modestamente hemos diseņado. (2) Este segundo programa va mucho mas alla, ya que nos proporciona un API mediante el cual podemos agregar a nuestros programas la capacidad de identificacion de lenguajes sin apenas realizar el mas minimo esfuerzo. En la misma web encontraras una buena documentacion acerca del SDK para realizar tus desarrollos. Con solo 7 funciones, el mundo a tus pies... Si ahora se te ocurre preguntar porque diablos hemos llevado el esfuerzo de realizar el trabajo a mano, entonces es que no sabes en que mundo te has metido, y todavia necesitas recapacitar si te encuentras en el lugar idoneo. Tu querias aprender, no es cierto? ---[ 7 - CrypTooL - CripTooLinux Si lo que de verdad necesitas es una herramienta para probar algoritmos criptograficos, entonces lo que necesitas es CrypTool [2]. Para definirla tomare una breve descripcion de Kriptopolis[7]: "CrypTool, un software destinado a facilitar el aprendizaje de la Criptologia, que viene siendo desarrollado desde 1998 por Bernhard Esslinger, aunque tras el proyecto estan Deutsche Bank, la Universidad de Siegen y TU Darmstadt. Es software libre, pero de momento solo funciona bajo Windows, aunque ya se trabaja en una nueva version 2.0 basada en Java y que -por tanto- sera multiplataforma. No obstante, existe tambien CrypTooLinux, un port para Linux, basado en QT4... El software esta disponible en ingles, aleman y polaco. Dispone de ayuda interactiva y abundantes presentaciones 3D sobre criptologia clasica y moderna, teori­a de numeros, etc. Segun el autor no se necesitan grandes conocimientos matematicos ni criptograficos para utilizarlo. Solo el documento de presentacion[8] (mas de 100 paginas, pdf) ya vale su peso en oro." El mejor consejo: Descargatelo y pruebalo. Y SI, has leido bien, es SOFTWARE LIBRE, que para empezar viene a decir que puedes aburrirte a leer codigo fuente hasta el fin de los dias. ---[ 8 - Conclusion Y hasta aqui te ofrezco de momento. Ya has visto que todo en este mundo se consigue paso a paso, es la causalidad (causa y efecto), primero el concepto y despues la realidad. Toda idea puede convertirse en algo tangible, o al menos en algo que puedas sentir. Cuando seas capaz de sentir el software, cuando levantes la cabeza del monitor y te des cuenta que hay dos realidades diferentes que intentan fundirse en una y cuando te resulte practicamente imposible decidirte por una de ellas, entonces estaras preparad@ para ver mas alla. Y recuerda: - La seguridad de un sistema criptografico no debe depender del secreto del algoritmo. La seguridad solo debe depender del secreto de la clave. ---[ 9 - Referencias [1] Una Introduccion a la Criptografia http://www.criptored.upm.es/descarga/UnaIntroduccionCriptografia.zip [2] CrypTool http://www.cryptool.com [3] Criptoanalisis http://webpages.ull.es/users/cryptull/Cripto/Apuntes/Criptoanalisis.pdf [4] Criptologia, Entropia y Evolucion http://www.criptored.upm.es/guiateoria/gt_m720a.htm [5] TextCat http://odur.let.rug.nl/~vannoord/TextCat/ [6] Lextek Language Identifier http://www.lextek.com/langid/ [7] Kriptopolis http://www.kriptopolis.org [8] Documento de Presentacion CrypTool http://www.cryptool.com/downloads/CrypToolPresentation_1_4_10_en.pdf *EOF*