Copy Link
Add to Bookmark
Report

SET 036 0x07

  

-[ 0x07 ]--------------------------------------------------------------------
-[ Criptografia Practica 02 ]------------------------------------------------
-[ by blackngel ]----------------------------------------------------SET-36--


^^
*`* @@ *`* HACK THE WORLD
* *--* *
## by blackngel <blackngel1@gmail.com>
|| <black@set-ezine.org>
* *
* * (C) Copyleft 2009 everybody
_* *_


1 - Prologo
2 - Introduccion
3 - Bigramas y Trigramas
4 - Algoritmos de Calculo
5 - Algoritmos de Ordenacion
6 - Cifrados Polialfabeticos
6.1 - Cifrado de Vigenere
6.2 - Analisis
7 - Conclusion
8 - Referencias



---[ 1 - Prologo

Si estas aqui, es porque tu intencion es llegar todavia mas lejos. Mi unica
intencion es liberarte. Tu ya sabes:

"Una prision que no puedes ver, oler, ni tocar,
una prision... para tu mente."
[ Matrix ]

Tomame como un guia, como un compa~ero. Quizas no alcance la sabiduria del
Oraculo, pero juntos podremos alcanzar la meta.

Y recuerda, lo importante siempre es el camino recorrido.


---[ 2 - Introduccion

Esta es la segunda parte de un articulo sobre "criptografia practica" publicado
en el numero anterior de este mismo e-zine. Con el dabamos nuestros primeros
pasos en la generacion de algoritmos criptograficos y tomabamos ciertos apuntes
de temas interesantes en el mundo de la escritura oculta.

Pero unas cuantas cosas fueron dejadas en el tintero, otras tantas no fueron
rematadas y muchas otras ni siquiera fueron mencionadas para no engrosar un
articulo cuya pretension era que probaseis en vuestra propia experiencia los
simples aspectos que alli se trataron.

Es por ello que en esta segunda parte vamos a terminar el trabajo que dejamos a
medias e incluiremos sobre todo mas codigo que te pueda ayudar a continuar con
tus experimentos criptograficos.



---[ 3 - Bigramas y Trigramas

En la seccion 6 (Analisis de Frecuencias) de la primera parte de este articulo,
habiamos dejado como deberes el resolver el problema de la busqueda de los
bigramas y trigramas mas frecuentes en un texto, ya sea cifrado o no (aunque
aqui ya sabemos con lo que tratamos).

Para el que haya leido el libro de criptografia sobre el que nos basamos en su
momento [1], sabra que lo que buscamos son los grupos de 2 y 3 caracteres mas
frecuentes de un texto para, una vez averiguado el idioma del texto plano
original, sustituir por los grupos mas frecuentes que se correspondan en este
mismo idioma.

Expondre aqui el codigo de mis sencillas implementaciones para que asi puedas
comparar tu codigo:

ANALISIS DE BIGRAMAS
--------------------

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>

struct bigramas {
char par[2]; /* LOS DOS CARACTERES QUE COMPONEN UN BIGRAMA */
int count; /* NUMERO DE VECES QUE SE REPITEN EN EL TEXTO */
} pp[1024];

char text[1024]; /* CAMBIALO!! -> TRABAJA CON MEMORIA DINAMICA */

/* ESTA FUNCION DETECTA SI UN BIGRAMA
YA HA SIDO BUSCADO ANTERIORMENTE */


int is_diferent(char a, char b) {

int i;

for (i = 0; i < 1024; i++) {
if (pp[i].par[0] == a && pp[i].par[1] == b)
return 0; /* FALSE */
}
return 1; /* TRUE*/
}

int main(int argc, char *argv[]) {

char car; /* CARACTERES LEIDOS DEL ARCHIVO */
int bytes; /* TAMA~O DEL TEXTO CIFRADO */
int mfreq; /* FRECUENCIA MINIMA PARA FILTRAR */
int i = 0; /* */
int j = 0; /* VARIABLES PARA BUCLES */
int w = 0; /* */
FILE *fin; /* MANEJADOR DE ARCHIVO */

if (argc < 3) {
fprintf(stderr, "\nUsage: ./bigramas archivo_cifrado filtro\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);
}

mfreq = atoi(argv[2]); /* FILTRO PARA LIMITAR EL RESULTADO */
/* SEGUN EL NUMERO DE APARICIONES */

while ((car = fgetc(fin)) != EOF) {
if (car != '\n' && car != '\r') {
text[i] = car;
i += 1;
}
}
bytes = i;

for (i = 0; i < bytes; i++){
if (is_diferent(text[i], text[i+1])) {
pp[i].par[0] = text[i];
pp[i].par[1] = text[i+1];
pp[i].count = 0;

for (j = 0; j < bytes; j++){
if (pp[i].par[0] == text[j] && pp[i].par[1] == text[j+1])
pp[i].count += 1;
}

if ((pp[i].count - 1) >= mfreq)
printf("\nBigrama (%c%c) -> %d apariciones", pp[i].par[0],
pp[i].par[1],
pp[i].count - 1);
}
}

fclose(fin);

return 0;
}


**-------------------------------------------------------------------------**

Su uso no tiene ningun misterio. Dos argumentos:

- El fichero a analizar.
- El numero minimo de veces que se tiene que repetir un
bigrama para que sea mostrado en los resultados.

Como puedes observar, este ultimo parametro es un burdo filtro para evitar
soltar por pantalla aquellos bigramas que solo aparecen una vez (no se repiten)
y aquellos cuya frecuencia es tan infima que no tendran correspondiente en
el idioma original para ser reemplazados.

He compilado el codigo bajo Windows con el entorno de desarrollo "Dev-C++" [2]
(version 4.9.9.2).

Un ejemplo de ejecucion bajo estas circunstancias seria el siguiente:

o------------------------------------o
| C:\Dev-Cpp>Bigramas.exe freq.txt 9 |
| |
| Bigrama (S2) -> 9 apariciones |
| Bigrama (7J) -> 17 apariciones |
| Bigrama (72) -> 12 apariciones |
| Bigrama (7H) -> 10 apariciones |
| Bigrama (N7) -> 9 apariciones |
| Bigrama (H9) -> 11 apariciones |
| Bigrama (92) -> 9 apariciones |
| Bigrama (9J) -> 11 apariciones |
o------------------------------------o

La misma salida que lo que se muestra en la Tabla 1.6 de la pagina 20 (28 en pdf)
para el analisis de bigramas.

Fijaros que no he ordenado la salida por numero de apariciones, pero vosotros
mismos podreis hacerlo si de deberes (mas todavia cuando hayais leido la seccion
sobre "Algoritmos de Ordenacion" que encontrareis mas adelante).

*_*_IMPORTANTISIMO!!!_*_*-----------------------------------------------------o
|Esta implementacion al igual que la siguiente han sido hechas de forma |
|especifica para analizar el texto cifrado propuesto en el articulo anterior. |
|Es por ello por lo que establecemos limites arbitrarios en los buffers de |
|almacenamiento. Pero esto es peligroso; de modo que trabaja con memoria |
|dinamica y manten la precaucion necesaria a la hora de manejar datos de que |
|que provengan de fuentes no seguras. |
o-----------------------------------------------------------------------------o

ANALISIS DE TRIGRAMAS
---------------------

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>

struct trigramas {
char trio[3]; /* LOS TRES CARACTERES QUE COMPONEN UN TRIGRAMA */
int count; /* NUMERO DE VECES QUE SE REPITEN EN EL TEXTO */
} pp[1024];

char text[1024]; /* CAMBIALO!! -> TRABAJA CON MEMORIA DINAMICA */

/* ESTA FUNCION DETECTA SI UN TRIGRAMA
YA HA SIDO BUSCADO ANTERIORMENTE */


int is_diferent(char a, char b, char c) {

int i;

for (i = 0; i < 1024; i++) {
if (pp[i].trio[0] == a && pp[i].trio[1] == b && pp[i].trio[2] == c)
return 0; /* FALSE */
}
return 1; /* TRUE*/
}

int main(int argc, char *argv[]) {

char car; /* CARACTERES LEIDOS DEL ARCHIVO */
int bytes; /* TAMA~O DEL TEXTO CIFRADO */
int mfreq; /* FRECUENCIA MINIMA PARA FILTRAR */
int i = 0; /* */
int j = 0; /* VARIABLES PARA BUCLES */
int w = 0; /* */
FILE *fin; /* MANEJADOR DE ARCHIVO */

if (argc < 3) {
fprintf(stderr, "\nUsage: ./Trigramas archivo_cifrado filtro\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);
}

mfreq = atoi(argv[2]);

while ((car = fgetc(fin)) != EOF) {
if (car != '\n' && car != '\r') {
text[i] = car;
i += 1;
}
}
bytes = i;

for (i = 0; i < bytes; i++){
if (is_diferent(text[i], text[i+1], text[i+2])) {
pp[i].trio[0] = text[i];
pp[i].trio[1] = text[i+1];
pp[i].trio[2] = text[i+2];
pp[i].count = 0;

for (j = 0; j < bytes; j++){
if (pp[i].trio[0] == text[j] && pp[i].trio[1] == text[j+1]
&& pp[i].trio[2] == text[j+2])
pp[i].count += 1;
}

if ((pp[i].count) >= mfreq)
printf("\nTrigrama (%c%c%c) -> %d apariciones", pp[i].trio[0],
pp[i].trio[1],
pp[i].trio[2],
pp[i].count);

}
}

fclose(fin);
return 0;
}

**-------------------------------------------------------------------------**

Exacto, el procedimiento es el mismo. Simplemente modificamos la estructura
principal y agregamos un nuevo parametro a la funcion 'is_diferent()'.

Si quieres obtener el resultado de los trigramas que se muestran en la Taba 1.6
que mencionamos anteriormente, ejecuta esta orden:

o-------------------------------------o
| C:\Dev-Cpp>Trigramas.exe freq.txt 4 |
| |
| Bigrama (F7J) -> 4 apariciones |
| Bigrama (7JT) -> 5 apariciones |
| Bigrama (JT7) -> 5 apariciones |
| Bigrama (MP7) -> 5 apariciones |
| Bigrama (7H9) -> 5 apariciones |
| Bigrama (S29) -> 4 apariciones |
| Bigrama (H72) -> 4 apariciones |
o-------------------------------------o

Si tratamos conjuntos de mayor longitud, este metodo se vuelve ineficiente.
Esto sera demostrado mas adelante y se vera como aplicamos otro algoritmo para
encontrar conjuntos de 4, 5 o mas caracteres, tratandolos como cadenas y no
como letras individuales.



---[ 4 - Algoritmos de Calculo

En esta peque~a seccion veremos algunos algoritmos que nos ayudaran a realizar
ciertas operaciones matematicas que no encontramos en las librerias estandar
de nuestro lenguaje de programacion favorito y que, por otro lado, siempre son
utiles a la hora de realizar todo tipo de funciones criptograficas.

Empezaremos por algo que, como habras visto en el libro recomendado, se utiliza
en varias ocasiones para obtener cierta clase de informacion. Nada mas y nada
menos que como calcular el "maximo comun divisor" entre dos numeros.

MAXIMO COMUN DIVISOR
--------------------

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>

int mcd(int dividendo, int divisor) {

int resto;

while (resto = dividendo % divisor) {
dividendo = divisor;
divisor = resto;
}

return divisor;
}

int main(int argc, char *argv[])
{
int maxcd;
int n1, n2;

if (argc < 3) {
fprintf(stderr, "\nUsage: ./mcd n1 n2\n");
exit(0);
}

n1 = atoi(argv[1]);
n2 = atoi(argv[2]);

maxcd = mcd(n1, n2);
printf("\nMCD(%d,%d) = %d\n", n1, n2, maxcd);

return 0;
}

**-------------------------------------------------------------------------**

Aprovechando la funcion creada en el programa anterior, podemos hallar de una
forma muy sencilla el "minimo comun multiplo", multiplicando los dos numeros
introducidos por el usuario y dividiendo el resultado por el "maximo comun
divisor"
. Lo vemos a continuacion.

MINIMO COMUN MULTIPLO
---------------------
**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>

int mcd(int dividendo, int divisor) {

int resto;

while (resto = dividendo % divisor) {
dividendo = divisor;
divisor = resto;
}

return divisor;
}

int mcm(int n1, int n2, int n3) {

return ((n1 * n2) / n3);
}

int main(int argc, char *argv[])
{
int maxcd, mincm;
int n1, n2;

if (argc < 3) {
fprintf(stderr, "\nUsage: ./mcd n1 n2\n");
exit(0);
}

n1 = atoi(argv[1]);
n2 = atoi(argv[2]);

maxcd = mcd(n1, n2);
mincm = mcm(n1, n2, maxcd);
printf("\nMCM(%d,%d) = %d\n", n1, n2, mincm);

return 0;
}

**-------------------------------------------------------------------------**

Para seguir mostraremos como reorganizar los elementos de un array desplazando
cada uno de ellos un lugar a la izquerda, pasando de este modo el 2º a ser el
1º y a su vez el 1º a ser el ultimo elemento del aray.

Hacerlo tambien en la otra direccion seria algo trivial e incluso con un poco
mas de codigo podrian organizarse a partir de un elemento elegido por el usuario
y los demas a partir de este. Pero empezaremos por las cosas faciles.

REORGANIZACION DE UN ARRAY
--------------------------

**-------------------------------------------------------------------------**

void reorg_cars(char array[], int n) {

int i;
char *org;

org = (char *) malloc(n * sizeof(char));

for(i = 1; i < n; i++){
org[i-1] = array[i];
}
org[i-1] = cars[0];

for(i = 0; i < n; i++){
array[i] = org[i];
}

free(org);
}

**-------------------------------------------------------------------------**

El primer parametro de la funcion es el array que deseamos reorganizar y el
segundo el numero de elementos que lo componen. De esta manera podemos trabajar
con un buffer temporal manejado con memoria dinamica.

Y ya por ultimo un codigo que toma como argumento un numero cualquiera y da
como resultado todos sus factores primos. Esto es muy util cuando deseamos
descomponer un numero muy grande.

**-------------------------------------------------------------------------**

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

/* Determina si un numero es primo */
int es_primo(int N)
{
int k, raiz;

raiz = (int) sqrt(N);

/* N es un numero primo si solo es divisible por N o por la unidad. */
for (k = 2; (N % k) && (k <= raiz); k++);

/* Si se llego a dividir N entre todos los numeros */
/* menores que su raiz cuadrada entonces es un primo */
if(k == (raiz + 1))
return 1; /* Es primo */

return 0; /* No es primo */
}

int main(int argc, char *argv[])
{
int i;
int num;

if (argc < 2) {
fprintf(stderr, "\nUso: ./nprimos numero\n");
exit(0);
}

num = atoi(argv[1]);

printf("\n\nLos factores primos son: ");

for (i = 1; i <= num; i++) {
if ((num % i) == 0 && es_primo(i))
printf("[%d] ", i);
}

printf("\n");
return 0;
}

**-------------------------------------------------------------------------**

Este ultimo deberias compilarlo con la libreria de funciones matematicas. Tal
como esto:

$ gcc nprimos.c -lm -o nprimos


"Los agujeros negros son los lugares del
Universo donde Dios dividio por cero"
.



---[ 5 - Algoritmos de Ordenacion

En esta seccion mostrare los algoritmos de ordenacion mas conocidos, que seran
de mucha ayuda cuando tu meta sea obtener la clasificacion ascendente o
descendente de los elementos de un vector o matriz con la que estes tratando.

El codigo fuente ha sido extraido del siguiente documento [3], del cual me
permito recomendar ampliamente su lectura. Lo he hecho de este modo para no
reinventar la rueda y porque asi nos lo permite explicitamente su autor.

Encontraras alli explicacion a todos los metodos, el porque de su eficiencia
y cuando deberas elegir uno u otro dependiendo de tus circunstancias concretas.


Ordenacion por insercion
------------------------

**-------------------------------------------------------------------------**

void ordenacion_insercion(Dato * A, int N)
{
int p, j;
Dato tmp;

for (p = 1; p < N; p++) {
tmp = A[p];
j = p - 1;

while ((j >= 0) && (tmp < A[j])) {
A[j + 1] = A[j];
j--;
}

A[j + 1] = tmp;
}
}


**-------------------------------------------------------------------------**

Ordenacion por Seleccion
------------------------

**-------------------------------------------------------------------------**

void intercambiar(Dato * A, int i, int j)
{
Dato tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}

void ordenacion_seleccion(Dato * A, int N)
{
int i, j, k;

for (i = 0; i < N - 1; i++) {
for (k = i, j = i + 1; j < N; j++)
if (A[j] < A[k])
k = j;
if (k != i)
intercambiar (A, i, k);
}
}

**-------------------------------------------------------------------------**

Ordenacion de Shell
-------------------

**-------------------------------------------------------------------------**

void ordenacion_shell(Dato * A, int N)
{
int incr = N / 2, p, j;
Dato tmp;

do {

for (p = incr + 1; p < N; p++) {
tmp = A[p];
j = p - incr;

while ((j >= 0) && (tmp < A[j])) {
A[j + incr] = A[j];
j -= incr;
}

A[j + incr] = tmp;
}
incr /= 2;

} while (incr > 0);
}

**-------------------------------------------------------------------------**

Ordenacion por Monticulos
-------------------------

**-------------------------------------------------------------------------**

void filtrado_desc(Dato * A, int i, int N)
{
/* Queremos que se respete el orden MAX del monticulo */
Dato tmp = A[i];
int hijo = 2 * i;

if ((hijo < N) && (A[hijo + 1] > A[hijo]))
hijo++;

while ((hijo <= N) && (tmp < A[hijo])) {

/* Elijo bien el hijo */
if ((hijo < N) && (A[hijo + 1] > A[hijo]))
hijo++;

A[i] = A[hijo];
i = hijo;
hijo = 2 * i;
}

A[i] = tmp;
}

void intercambiar(Dato * A, int i, int j)
{
Dato tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}

void heapsort(Dato * A, int N)
{
int i;
/* Meto los datos en el monticulo (ordeno) */

for (i = N / 2; i >= 0; i--)
filtrado_desc(A, i, N);

/* saco los datos y los meto al final para obtener el array ordenado */
for (i = N - 1; i > 0; i--) {
intercambiar (A, 0, i);
filtrado_desc (A, 0, i - 1);
}
}

**-------------------------------------------------------------------------**

Ordenacion por Intercalacion
----------------------------

**-------------------------------------------------------------------------**

void mergesort(Dato * A, int N)
{
Dato *tmp = crear (N); /* Array auxiliar del mismo tamaño que A */
ord_intercalacion (A, tmp, 0, N - 1);
}

void ord_intercalacion(Dato * A, Dato * tmp, int izq, int der)
{
if (izq < der) {

/* este if comprueba el caso base que es cuando la particion
pasada no tiene elementos. */


/* dividimos a la mitad el subarray [A[izq],...,A[der]] */
int centro = (izq + der) / 2;

/* aplicamos la recursion en ambas mitades */
ord_intercalacion (A, tmp, izq, centro);
ord_intercalacion (A, tmp, centro + 1, der);

/* a este punto ambas mitades deberian estar ordenadas por lo que */
/* las intercalamos para unirlas en una sola secuencia ordenada. */
intercalar (A, tmp, izq, centro + 1, der);
}
}

void intercalar(Dato * A, Dato * tmp, int izq, int centro, int der)
{
/* mis particiones seran [izq,...,centro-1] y [centro,...,der] */
/* contadores para la primera mitad, la segunda */
/* y para la intercalacion respectivamente. */

int ap = izq, bp = centro, cp = izq;

while ((ap < centro) && (bp <= der)) {

if (A[ap] <= A[bp]) {
tmp[cp] = A[ap];
ap++;
}
else {
tmp[cp] = A[bp];
bp++;
}
cp++;
}

/* terminamos de intercalar, ahora metemos los elementos restantes */
/* de la lista que aun no ha terminado de ser procesada. */

while (ap < centro) {
tmp[cp] = A[ap];
cp++;
ap++;
}

while (bp <= der) {
tmp[cp] = A[bp];
cp++;
bp++;
}

/* ahora que tenemos la intercalacion finalizada en tmp, la pasamos a A */
for (ap = izq; ap <= der; ap++)
A[ap] = tmp[ap];
}

**-------------------------------------------------------------------------**

Ordenacion Rapida
-----------------

**-------------------------------------------------------------------------**

void quicksort(Dato * A, int N)
{
ord_rapida (A, 0, N - 1);
}

void ord_rapida(Dato * A, int izq, int der)
/* se trabaja en el subarray [A[izq],...,A[der]] */
{
if (der - izq > 1) { /* caso base de la recursion */

{ /* elegimos el pivote y lo ponemos en A[der-1] */
int centro = div2 (izq + der);
if (A[izq] > A[centro])
intercambiar (A, izq, centro);

if (A[izq] > A[der])
intercambiar (A, izq, der);

if (A[centro] > A[der])
intercambiar (A, centro, der);

intercambiar (A, centro, der - 1);
}

{ /* "particionamos" */
int i = izq, j = der - 1;
Dato pivote = A[der - 1];

do {

do
i++;
while (A[i] < pivote);

do
j--;
while (A[j] > pivote);

intercambiar (A, i, j);

} while (j > i);

/* deshacemos el ultimo intercambio el */
/* cual se efectuo sin cumplirse i < j */
intercambiar(A, i, j);

/* ponemos el pivote en el medio de ambas particiones */
intercambiar(A, i, der - 1);

/* aplicamos la recursion en las particiones halladas */
ord_rapida(A, izq, i - 1);
ord_rapida(A, i + 1, der);
}
}
}

**-------------------------------------------------------------------------**

Recomendar por ultimo leer la tabla de velocidades que puede serte util
cuando tomes tu decision.



---[ 6 - Cifrados Polialfabeticos

Si quieres saber exactamente todo lo referente a este tipo de cifrados, te
remito nuevamente al libro con el que llevamos trabajando hasta el momento.

Solo decir, a modo de descripcion, que se trata de un algoritmo en el que cada
caracter del texto en claro es cifrado con un alfabeto diferente al anterior.

Cuantos alfabetos seran usados es algo que viene definido por la longitud de
la clave. Y ese es el problema principal para romper este clase de cifrado.

En la seccion 6.2 se daran todas las explicaciones pertinentes a este respecto.



---[ 6.1 - Cifrado de Vigenere

Un cifrado del tipo Vigenere es muy facil de implementar. Lo primero que se
hace es crear una tabla en la que cada fila contiene las 26 letras del alfabeto
pero desplazadas una posicion a la izquierda cada una de ellas. Algo asi:

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
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 A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
. . .
. . .

Y asi hasta completar todas las filas de la A a la Z.

Ahora imagina que quieres cifrar un mensaje como el que utilizamos en la
primera parte de este articulo publicado en SET-35. Y que utilizamos la
misma clave:

E S T A M O S E N T R A N D O E N L A N A S A
S E C R E T O S E C R E T O S E C R E T O S E

Para obtener el caracter cifrado correspondiente a la primera letra del texto
en claro, vamos a la columna de la tabla correspondiente a la letra 'E' y en
la intersecion con la fila correspondiente a la letra de la clave 'S' nos
encontraremos con el caracter 'W' que es nuestro correspondiente cifrado. Asi
obtenemos el siguiente resultado:

W W V R Q H G W R V I E G R G I P C E G O K E

Bueno, aqui tienes el codigo que implementa este algoritmo. Es mi diseño, que
sin saber si es el correcto o no, funciona perfectamente.

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char cars[26] = { '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' };

char table[26][26];

int len_msg;
int len_pass;
char *mensaje;
char *password;

void cifrar(void);
void descifrar(void);
void reorg_cars(void);
void gen_table(void);
void print_table(void);

/* DESPLAZA LOS CARACTERES DE UNA FILA UNA POSICION */
/* HACIA LA IZQUIERDA PARA IR GENERANDO LA TABLA */
void reorg_cars(void) {

int i, j;
char org[26];

j = 0;
for(i = 1; i < 26; i++){
org[j] = cars[i];
j += 1;
}
org[25] = cars[0];

for(i = 0; i < 26; i++){
cars[i] = org[i];
}
}

/* CREA LA TABLA DE VIGENERE DE 26 x 26 */
void gen_table(void) {

int i, j;
int z = 0;

for (i = 0; i < 26; i++) {
for (j = 0; j < 26; j++) {
table[i][j] = cars[j];
}
reorg_cars();
}
}

/* IMPRIME LA TABLA EN ETAPA DE DESARROLLO */
void print_table(void) {

int i, j;

for (i = 0; i < 26; i++) {
for (j = 0; j < 26; j++) {
printf("%c ", table[i][j]);
}
printf("\n");
}
}

/* ALGORITMO DE CIFRADO */
void cifrar(void) {

int i, j;
int fila, col;

printf("\n-----BEGIN VIGENERE-CRYPT MSG-----\n");

for (i = 0; i < len_msg; i++) {

if (i % 50 == 0) /* CADA 50 CARACTERES SALTAMOS DE LINEA */
printf("\n"); /* PARA MANTENER UNA BUENA PRESENTACION */

for (j = 0; j < 26; j++){
if (table[0][j] == mensaje[i])
col = j; /* LA COLUMNA DONDE SE ENCUENTRA EL CARACTER DEL MENSAJE */
}

for (j = 0; j < 26; j++) {
if (table[j][0] == password[i % len_pass])
fila = j; /* LA FILA DONDE SE ENCUENTRA EL CARACTER DE LA CLAVE */
}

/* EN LA INTERSECION DE LA FILA Y LA COLUMNA ESTA EL CARACTER CIFRADO */
printf("%c", table[fila][col]);
}

printf("\n\n------END VIGENERE-CRYPT MSG------\n");
}

/* ALGORITMO DE DES-CIFRADO */
void descifrar(void) {

int i, j;
int fila, col;

printf("\n-----BEGIN VIGENERE-DECRYPT MSG-----\n");

for (i = 0; i < len_msg; i++) {

if (i % 50 == 0) /* CADA 50 CARACTERES SALTAMOS DE LINEA */
printf("\n"); /* PARA MANTENER UNA BUENA PRESENTACION */

for (j = 0; j < 26; j++){
if (table[j][0] == password[i % len_pass])
fila = j; /* FILA DONDE SE ENCUENTRA EL CARACTER DE LA CLAVE */
}

for (j = 0; j < 26; j++) {
if (table[fila][j] == mensaje[i])
col = j; /* EN LA FILA ANTERIOR BUSCAMOS EL CARACTER CIFRADO */
}

/* EL PRIMER ELEMENTO DE LA COLUMNA HALLADA ES EL CARACTER ORIGINAL */
printf("%c", table[0][col]);
}

printf("\n\n------END VIGENERE-DECRYPT MSG------\n");
}

int main(int argc, char *argv[])
{
int i;
int cifrado = 0;

/* FORMA DE USO HABITUAL */
if (strncmp(argv[1], "-c", 2) == 0)
cifrado = 1;
else if (strncmp(argv[1], "-d", 2) != 0) {
fprintf(stderr, "\nUsage: ./vigenere-crypt [-c|-d] message password\n");
exit(0);
}

asprintf(&mensaje, "%s", argv[2]);
len_msg = strlen(mensaje);

asprintf(&password, "%s", argv[3]);
len_pass = strlen(password);

puts("\n\n");
gen_table();
print_table(); /* COMENTA ESTO EN EL DISEÑO FINAL */

if (cifrado)
cifrar();
else
descifrar();

return 0;
}

**-------------------------------------------------------------------------**

Si todavia necesitas una prueba mas de que cumple su tarea correctamente,
podemos probar con la tercera linea del mensaje cifrado que propuso el equipo
de Hispasec [4] en el reto del decimo aniversario de "Una-al-dia".

El texto era el siguiente:

OCDENSKOVZKCKNYCSAESOBOCZBYXYCDSMKBOVPEDEBY
EXBOQKVYOCDKOCZOBKXNYXYDKBNOCOXOXFSKBOCDYIK
HRXQMHXWQTGQLSPIXOESTIFCUMQIFVLWRIESFHQBOCP

Las dos primeras lineas estaban cifradas mediante el algoritmo del Cesar con
un desplazamiento de 10 posiciones. La segunda se trataba precisamente de un
cifrado Vigenere cuya clave resultaba ser "decimo" (refente al aniversario
claro esta).

Si probamos nuestro programa obtener algo asi:

o------------------------------------------------------------------------o
| blackngel@linux:~/Pruebas$ ./vigenere -d HRXQMHXWQTGQLSPIXOESTIFCUMQIF |
| VLWRIESFHQBOCP DECIMO |
| |
| -----BEGIN VIGENERE-DECRYPT MSG----- |
| |
| ENVIATUSOLUCIONALABORATORIOATHISPASECDOTCOM |
| |
| ------END VIGENERE-DECRYPT MSG------ |
o------------------------------------------------------------------------o



---[ 6.2 - Analisis

A continuacion copio el texto que trataremos de analizar en esta seccion y
seguidamente pasare a dar las explicaciones oportunas:

IMCAPYFIEHIKIZERBPNHIBCLSRNUOVIMWDYMDZBEGNZQEVLMAS
LZUHGLNBVIQOWDYIUQIMETVUMHZTTSHDTBWHDTNRDZMAEWSQYP
IQWNHEQONERSQTYEQWPMRETNGSXONPKNKBVVDLBVYMIBPPZLRE
PFWZEWUIPEUTMPEVMMESWZTCMGNVYEWLIFRSBPRWHTMYSWXYHI
FQIAXSRTBWWZJNHSRTRRXDRNWPNAIMIQVRWEKOHRTZTBQMMWQI
EZINHMCCEEPNAQSQHVTSWBWAWYLQNRPZAGVIRKHEVSIFTEQBRW
HDAHLEBQRRHZ

Bien, habiamos quedado, cuando definiamos que era en realidad un cifrado
polialfabetico, que el problema para resolverlos era hallar la longitud de
la clave. La imposibilidad de obtener este dato fue lo que mantuvo por
mucho tiempo a este algoritmo como seguro...

...pero llego Kasiski para fastidiarla (gracias, gracias), e investigando se
dio cuenta de que en el texto habia diversos conjuntos de caracteres que se
repetian a lo largo del mismo. Luego averiguo que si estos conjuntos se repetian
en el texto cifrado, tambien deberian hacerlo en el texto en claro. Y se
percato, ya por ultimo, de que la distancia entre estas repeticiones era un
multiplo de la longitud de la clave.

Lo que viene a decir es que, si encontramos en el texto conjuntos repetidos,
y calculamos el maximo comun divisor entre sus distancias, la clave resulta
ser esta cifra o uno de sus factores primos (uno de sus divisores).

Bien... saber la longitud de la clave no es obtener la clave en si misma;
pero luego veremos como utilizar esto para continuar con el analisis.

Ahora lo que muestro aqui es mi pequeña implementacion para hallar el posible
tamaño de la clave para un texto al que se le ha aplicado el cifrado Vigenere:

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int values[64];
char text[1024]; /* CAMBIALO!! -> TRABAJA CON MEMORIA DINAMICA */

void reorg_val(void) {

int j, k = 0;
int org[64];

for(j = 1; j < 64; j++){
org[k++] = values[j];
}
org[k] = 0;

for(j = 0; j < 64; j++){
values[j] = org[j];
}
}

int mcd(int op) {

int resto;
int dividendo = values[0];
int divisor = values[1];

while (resto = dividendo % divisor) {

dividendo = divisor;
divisor = resto;
}

values[1] = divisor;

if (op)
return values[1];

reorg_val();

if (values[2] == 0)
mcd(1);
else
mcd(0);
}

int main(int argc, char *argv[]) {

int maxcd; /* RESULTADO MAXIMO COMUN DIVISOR */
int bytes; /* TAMA~O DEL TEXTO CIFRADO */
int j, i = 0; /* VARIABLES PARA BUCLES */
int count = 0; /* CONTADOR DE DISTANCIAS */
int longitud = 3; /* LONGITUD MINIMA PARA CONJUNTOS */
char car; /* CARACTERES LEIDOS DEL ARCHIVO */
char *ptr; /* PUNTERO AL TEXTO CIFRADO */
char *tmp; /* RESULTADO DE STRSTR() */
char *rword; /* PALABRAS REPETIDAS EN EL TEXTO */
FILE *fin; /* MANEJADOR DE ARCHIVO */

if (argc < 2) {
fprintf(stderr, "\nUsage: ./lonkey archivo_cifrado [longitud]\n");
exit(0);
}

if (argc == 3)
longitud = atoi(argv[2]);

rword = malloc((longitud + 1) * sizeof(char));

/* 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);
}

/* LEEMOS EL ARCHIVO Y LO METEMOS EN UN BUFFER */
while ((car = fgetc(fin)) != EOF) {
if (car != '\n' && car != '\r') {
text[i] = car;
i += 1;
}
}
text[i] = '\0';
bytes = i;

fclose(fin);

/*AQUI EL ALGORITMO PRINCIPAL*/
ptr = text;
for (i = 0; i < bytes - longitud; i++) {
strncpy(rword, ptr, longitud);
rword[longitud] = '\0';
ptr++;

if (tmp = strstr(ptr, rword)) {
if ((i - j) > longitud) {
printf("\nCadena <%s> en (%d) se repite en posicion (%d)", rword,
i, tmp - text);
values[count] = ((tmp - text) - i);
count += 1;
j = i;
}
}
}

/* SI POR LO MENOS TENEMOS 2 DISTANCIAS, HAYAMOS EL MAXIMO COMUN DIVISOR */
if (count >= 2) {
maxcd = mcd(0);
}
else { /* DE OTRO MODO SUGERIMOS BUSCAR CONJUNTOS MAS PEQUEÑOS */
printf("\nNo existen repeticiones de longitud: %d", longitud);
printf("\nPruebe con un valor inferior como: %d\n\n", longitud - 1);
free(rword);
exit(0);
}

printf("\n\n");
printf("La clave tiene una longitud de -%d- caracteres\n", maxcd);
printf("o uno de sus divisores.\n\n");

free(rword); return 0;
}

**-------------------------------------------------------------------------**

El programa necesita un parametro obligatorio, que es el archivo conteniendo
el texto cifrado que deseamos estudiar. Opcionalmente podemos indicarle la
longitud de los conjuntos de caracteres cuyas repeticiones seran buscadas.

Aqui explicare mas o menos el metodo que utilizo:

Si por ejemplo le indicamos buscar conjuntos de longitud 5, lo que el programa
hace es coger los 5 primeros caracteres del texto y tratarlos como si de una
palabra se tratase para buscar seguidamente si esta se repite alguna vez en
alguna otra parte del texto. Aqui pueden pasar dos cosas:

1 - Caso de no encontrar repeticiones, el puntero se desplaza una posicion
hacia adelante y volvemos a coger otro conjunto de 5 caracteres para
realizar una nueva busqueda.

2 - Caso de encontrar una repeticion, almacenamos en el array 'values[]'
la distancia que hay entre el conjunto escogido y la repeticion que
acabamos de encontrar.

Como habras comprobado, la funcion 'mcd()' difiere en parte de la que mostramos
en la seccion de "Algoritmos de Calculo". El motivo es que para calcular el
maximo comun divisor de varios numeros se me ha ocurrido operar de la siguiente
manera:

1 - LISTA DE NUMEROS: [215][110][5][30][10][35]

2 - Calculo el maximo comun divisor de los 2 primeros
numeros y almaceno el resultado en el elemento values[1]
quedando asi: [215][5][5][30][10][35]
|_mcd(215,110)

3 - Reordeno el array moviendo los elementos una posicion a la
izquierda y borrando el ultimo de ellos. Nos queda algo
como esto: [5][5][30][10][35][0]

4 - Repito este proceso hasta que se haya el maximo comun divisor
del ultimo par y todos los demas elementos son 0's. Entonces
lo que me queda es el resultado final que 'mcd()' retorna.

Hay un condicional que podria parecerte algo raro pero cuya funcion tiene una
importancia bastante relativa. Se trata de este:

if ((i - j) > longitud) { };

Imaginese que nosotros buscamos grupos de 5 caracteres y el programa encuentra
que el conjunto "XAHRI" en la posicion 'x' se repite nuevamente en la posicion
'y'. Hasta ahi todo bien, pues eso es lo que buscamos; pero hay un problema. Si
ese conjunto forma parte de otro mayor, como podria ser "XAHRIVO", el programa
le dira que otro conjunto llamado "AHRIV" se repite y despues le dira que el
conjunto "HRIVO" tambien se repite. El tema es que almacenaremos 3 distancias
en el array 'values[]' cuando unicamente estamos tratando con un unico conjunto
(aunque mayor al que esperabamos).

Lo que hago con el condicional, es que una vez que encuentre la repeticion de
un conjunto, no nos informe de mas hasta haber pasado tantas posiciones como
la longitud de ese conjunto. Es bastante sucio, lo se, pero funciona.

En un principio pense que era mas sencillo realizar simplemente una operacion
como: "ptr += longitud" cada vez que encontrase una repeticion, pero solo logre
bastantes fallos con ese metodo. Si alguien sabe como realizar la misma tarea
de una forma mas limpia, que me contacte directamente a mi direccion de correo.

Vamos a probar el programa con el texto que queremos analizar. Buscaremos
conjuntos de 4 caracteres que se repitan en el texto.

o------------------------------------------------o
| blackngel@linux:~/Pruebas$ ./lonkey quij.txt 4 |
| |
| No existen repeticiones de longitud: 4 |
| Pruebe con un valor inferior como: 3 |
o------------------------------------------------o

Bueno, esta salida no es muy comun, pues normalmente incluso podrias encontrar
conjuntos de 7 caracteres o mas largos todavia repetidos en el texto; pero ya
que no es el caso, obedeceremos a las indicaciones.

En una segunda prueba obtenemos:

o---------------------------------------------------o
| blackngel@linux:~/Pruebas$ ./lonkey quijote.txt 3 |
| |
| Cadena <WDY> en (32) se repite en posicion (62) |
| Cadena <HDT> en (80) se repite en posicion (85) |
| Cadena <WHD> en (84) se repite en posicion (299) |
| Cadena <RWH> en (188) se repite en posicion (298) |
| Cadena <SRT> en (205) se repite en posicion (215) |
| Cadena <PNA> en (225) se repite en posicion (260) |
| |
| La clave tiene una longitud de -5- caracteres |
| o uno de sus divisores. |
o---------------------------------------------------o

Genial, esta es una buena respuesta, pues el 5 no tiene factores primos
(divisores) mas que la unidad, y no creemos que la contraseña tenga tan
solo un caracter de longitud.

En la prueba de otro texto, el programa me dijo que la longitud era de
'28' y resulto ser que la clave era precisamente de 7 caracteres (divisor
de este). Pues 7 x 4 = 28.

Vale, ahora llegamos a un punto muy importante. Segun Kasiski (aunque
resulta obvio para cualquiera) el siguiente paso era dividir el texto
cifrado en bloques iguales a la longitud de la clave. De esta manera
obtendriamos filas de caracteres que fueron cifrados con el mismo
alfabeto. Nuestro texto quedaria asi:

BLOQUE 1 -> IYIRIRIMGVLLQIEHHHDWIERERSKVYPPWUVWGWSHWFSWSXPIETMEMPQWYPIVEHEH

BLOQUE 2 -> MFKBBNMDNLZNOUTZDDZSQQSQEXNDMZFUTMZNLBTXQRZRDNQKZMZCNHBLZRSQDBZ

BLOQUE 3 -> CIIPCUWZZMUBWQVTTTMQWOQWTOKLILWIMMTVIPMYITJTRAVOTWICAVWQAKFBAQ

BLOQUE 4 -> AEZNLODBQAHVDIUTBNAYNNTPNNBBBRZPPECYFRYHABNRNIRHBQNEQTANGHFRHR

BLOQUE 5 -> PHEHSVYEESGIYMMSWREPHEYMGPVVPEEEESMERWSIXWHRWMWRQIHESSWRVETWLR

Puedes conseguir esta ordenacion con este codigo:

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
int i, j;
int len;
int len_msg;

if (argc < 3) {
printf("\nUso: ./chord mensaje longitud");
}

len = atoi(argv[2]);
len_msg = strlen(argv[1]);

printf("\n");
for(j = 0; j < len; j++){
for (i = 0; i < len_msg; i += len) {
printf("%c", argv[1][i + j]);
}
printf("\n\n");
}

printf("\n\n");
return 0;
}

**-------------------------------------------------------------------------**

Y ahora solo quedaria realizar el analisis clasico de frecuencias para cada
uno de los bloques, pues es como si a cada uno de ellos se le hubiese aplicado
un cifrado monoalfabetico. Su estudio, no obstante, resulta algo mas complicado,
y es aqui donde nosotros nos separaremos del libro para tomar otro camino y
buscar otra solucion.

Una vez hemos obtenido la longitud de la clave, utilizaremos tres cosas para
romper este algoritmo:

1 - El Indice de Coincidencia
2 - Un diccionario de palabras
3 - Aplicacion de la fuerza bruta

En Indice de Coincidencia, tal y como se describe en el libro, resulta ser
la suma de los cuadrados de las frecuencias de las letras que componen el
texto.

Para el "español" el IC resulta ser de '0.0755'. Cuando un texto en este idioma
se cifra mediante un algoritmo monoalfabetico, este IC se conserva puesto que
las frecuencias tambien lo hacen. Cuando se cifra mediante un algoritmo
polialfabetico, el IC decrece hasta aproximarse a '0.037' dado que los letras
tieden a repartirse mas uniformemente.

Lo que quiero decir con esto, es que si intentamos descifrar el texto con una
clave cualquier y erramos, el resultado seguira teniendo un IC cercano a '0.037'
mientras que si conseguimos acertar con la clave correcta, el resultado deberia
tener un IC proximo a '0.0755'.

Valiendome de esta premisa, he diseñado un programa que prueba todas las claves
de 5 caracteres de longitud posibles, y calcula para cada descifrado su "Indice
de Coincidencia"
. Se supone entonces, que en el momento que suba hasta '0.0755'
habremos dado con la clave.

Hasta aqui hemos hecho uso del Indice de Coincidencia y de la Fuerza Bruta,
pero entonces, para que el diccionario de palabras?

El motivo es que probando el programa anteriormente obtuve varios resultados
en los que el IC se acercaba demasiado al correspondiente al "español" y se
producian entonces falsos positivos.
La solucion que me vino a la cabeza fue comparar el texto descifrado de estas
alertas con un diccionario de palabras en español en la busqueda de alguna
coincidencia. Con esto se limita practicamente el rango de posibilidades y los
falsos positivos decrecen hasta casi anularse.

Presento aqui el programa para dar a posteriori las explicaciones sobre su
funcionamiento:

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define IC_ES 0.0755

float car_val[26][2];
float freqs[26];

char cars[26] = { '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' };

char table[26][26];

int len_msg;
int len_pass;
char *mensaje;
char *descmsg;
char *password;

FILE *dic;

void reorg_cars(void);
void gen_table(void);
void descifrar(void);
int analizar(void);

void reorg_cars(void) {

int i, j;
char org[26];

j = 0;
for(i = 1; i < 26; i++){
org[j] = cars[i];
j += 1;
}
org[25] = cars[0];

for(i = 0; i < 26; i++){
cars[i] = org[i];
}
}

void gen_table(void) {

int i, j;
int z = 0;

for (i = 0; i < 26; i++) {
for (j = 0; j < 26; j++) {
table[i][j] = cars[j];
}
reorg_cars();
}
}

void descifrar(void) {

int i, j;
int fila, col;

descmsg = malloc(len_msg * sizeof(char));

for (i = 0; i < len_msg; i++) {

for (j = 0; j < 26; j++){
if (table[j][0] == password[i % len_pass])
fila = j;
}

for (j = 0; j < 26; j++) {
if (table[fila][j] == mensaje[i])
col = j;
}

descmsg[i] = table[0][col];
}
}

int analizar(void) {

char car;
char *ptr;
int i = 0 , j = 0;
int w = 0 , k = 0;
float ic = 0.0;
char *word;
size_t tam = 0;
ssize_t ret;

ptr = descmsg;

for (i = 65; i < 91; i++) {
car_val[w][0] = i;
for (k = 0; k < len_msg; k++) {
if (descmsg[k] == (char)i)
j += 1;
}
if (j) {
car_val[w][1] = j;
w += 1;
}
j = 0;
}

for (i = 0; i < 26; i++) {
ic += (pow(((car_val[i][1] * 100.0) / len_msg) / 100.0, 2));
}

if ((IC_ES - ic) < 0.002) {

while ((ret = getline(&word, &tam, dic)) != -1) {
word[strlen(word) - 1] = '\0';
if (strstr(ptr, word)) {
printf("\n\n");
printf("o---------------------o\n");
printf("| CONTRASEÑA CORRECTA |\n");
printf("o---------------------o\n\n");
while (*ptr) {
printf("%c", *ptr++);
}
printf("\n\n[+] IC = %f", ic);
printf("\n\n[+] Palabra encontrada: %s\n", word);
return 1;
}
}
fseek(dic, 0, 0);
free(word);
word = NULL;
}
return 0;
}

int main(int argc, char *argv[])
{
int a, b, c, d, e;

if (argc < 3) {
fprintf(stderr, "\nUsage: ./desvigen mensaje diccionario\n");
exit(0);
}

asprintf(&mensaje, "%s", argv[1]);
len_msg = strlen(mensaje);
len_pass = 5;

gen_table();

dic = fopen(argv[2], "r");
if (dic == NULL) {
printf("\nEl diccionario de comprobacion no existe\n");
exit(0);
}

for (a = 'A'; a <= 'Z'; a++)
for (b = 'A'; b <= 'Z'; b++)
for (c = 'A'; c <= 'Z'; c++)
for (d = 'A'; d <= 'Z'; d++)
for (e = 'A'; e <= 'Z'; e++) {
asprintf(&password, "%c%c%c%c%c", a,b,c,d,e);

if (count % 25000 == 0)
printf("\nProbando clave: %s", password);

descifrar();
if ( analizar() ) {
printf("\n[+] Claves probadas: [%d]\n", count);

printf("\n[+] Ha sido utilizada la clave: [ %c%c%c%c%c ]",
a,b,c,d,e);
printf("\n\n");
free(password);
free(descmsg);
free(mensaje);
password = NULL;
descmsg = NULL;
mensaje = NULL;
fclose(dic);
exit(0);
}
free(password);
free(descmsg);
password = NULL;
descmsg = NULL;
}
free(mensaje)
mensaje = NULL;
fclose(dic);
return 0;
}

**-------------------------------------------------------------------------**

Yo, personalmente, utilizo un diccionario en español de 800 Kb (bastante
ligero), que contiene palabras de todos los tamaños. Puedes decargartelo
desde nuestro mirror [5] en la seccion "Cracking". Luego utilizo un pequeño
programa para crear otros a partir de este, indicandole la longitud minima
que deseo para sus palabras. Aqui lo teneis:

**-------------------------------------------------------------------------**

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
FILE *fin;
int len;
char *word;
size_t tam = 0;
ssize_t ret;

if (argc < 3) {
fprintf(stderr, "\nUso: ./gendic diccionario longitud-minima\n");
exit(0);
}

fin = fopen(argv[1], "r");
if (fin == NULL) {
printf("\nError al abrir el diccionario\n");
exit(0);
}

len = atoi(argv[2]) + 1;

while ((ret = getline(&word, &tam, fin)) != -1) {
if (strlen(word) >= len)
printf("%s", word);
}
}

**-------------------------------------------------------------------------**

Si por ejemplo el diccionario original se llama "spain.lst", entonces para
crear otro cuyas palabras al menos tengan un minimo de 4 caracteres, ejecuto
lo siguiente:

blackngel@linux:~/Pruebas$ ./gendic spain.lst 4 > spain4.lst

Y una vez tengo este nuevo diccionario ya puedo probar mi analizador de
cifrados Vigenere. Aqui teneis la ejecucion (lo hago por medio del comando
time para que veais que tiempos conseguimos).

o------------------------------------------------------------------------o
| blackngel@lin:~/Pruebas$ time ./desvigen IMCAPYFIEHIKIZERBPNHIBCLSRNUO |
| VIMWDYMDZBEGNZQEVLMASLZUHGLNBVIQOWDYIUQIMETVUMHZTTSHDTBWHDTNRDZMAEWSQY |
| PIQWNHEQONERSQTYEQWPMRETNGSXONPKNKBVVDLBVYMIBPPZLREPFWZEWUIPEUTMPEVMME |
| SWZTCMGNVYEWLIFRSBPRWHTMYSWXYHIFQIAXSRTBWWZJNHSRTRRXDRNWPNAIMIQVRWEKOH |
| RTZTBQMMWQIEZINHMCCEEPNAQSQHVTSWBWAWYLQNRPZAGVIRKHEVSIFTEQBRWHDAHLEBQR |
| RHZ spain4.lst |
| |
| o---------------------o |
| | CONTRASEÑA CORRECTA | |
| o---------------------o |
| |
| IRYRPYKEVHIPEQERGLEHIGYCSRSQFVIRSUYMIVSEGSVHEVQIRS |
| LEQYGLSXMIQTSUYIZMZMEYRLMHEPKSHIPSWHIPERDEIREWXMPP |
| IVSEHEVKEERXMKYEVSGMRJPEGSCKEPKSGSVVIHSVYRESPPEHIE |
| PKSQEWZEGEUYIGEVRIVSWEPTMGSRPEWQEWRSGLIWHYIPSWCUYI |
| FVERXSWPSWWEFEHSWPIRXINEWPSWZMIVRIWEPKYRTEPSQMRSHI |
| EEEEHMHYVEPSWHSQMRKSWGSRWYQMERPEWXVIWGYEVXEWTEVXIW |
| HIWYLEGMIRHEWPNA |
| |
| [+] IC = 0.078854 |
| |
| [+] Palabra encontrada: HIPER |
| |
| [+] Ha sido utilizada la clave: [ AVEJA ] |
| |
| real 0m42.646s |
| user 0m42.475s |
| sys 0m0.048s |
o------------------------------------------------------------------------o

Algo ha fallado, pero tranquilos, es normal, estamos buscando en los textos
descifrados palabras de longitud 4 o superior, y es comun encontrar ciertas
combinaciones de caracteres que formen una palabra conocida en nuestro
lenguaje. Dado que la palabra que ha encontrado es "HIPER" y ademas no es de
4 sino de 5 caracteres, la solucion pasa por crear un nuevo diccionario con
palabras mas largas. Probaremos con 6:

blackngel@mac:~/Pruebas$ ./gendic spain.lst 6 > spain6.lst

Hagamos la prueba nuevamente:

o------------------------------------------------------------------------o
| blackngel@lin:~/Pruebas$ time ./desvigen IMCAPYFIEHIKIZERBPNHIBCLSRNUO |
| VIMWDYMDZBEGNZQEVLMASLZUHGLNBVIQOWDYIUQIMETVUMHZTTSHDTBWHDTNRDZMAEWSQY |
| PIQWNHEQONERSQTYEQWPMRETNGSXONPKNKBVVDLBVYMIBPPZLREPFWZEWUIPEUTMPEVMME |
| SWZTCMGNVYEWLIFRSBPRWHTMYSWXYHIFQIAXSRTBWWZJNHSRTRRXDRNWPNAIMIQVRWEKOH |
| RTZTBQMMWQIEZINHMCCEEPNAQS spain6.lst |
| |
| o---------------------o |
| | CONTRASEÑA CORRECTA | |
| o---------------------o |
| |
| ENUNLUGARDELAMANCHADECUYONOMBRENOQUIEROACORDARMENOHAMUCHOTIEMPOQUEVIVI |
| AUNHIDALGODELOSDELANZAENASTILLEROADARGAANTIGUAROCINFLACOYGALGOCORREDOR |
| UNAOLLADEALGOMASVACAQUECARNEROSALPICONLASMASNOCHESDUELOSYQUEBRANTOSLOS |
| SABADOSLENTEJASLOSVIERNESALGUNPALOMINODEAAAADIDURALOSDOMINGOSCONSUMIAN |
| LASTRESCUARTASPARTESDESUHACIENDA |
| |
| [+] IC = 0.075269 |
| |
| [+] Palabra encontrada: ACORDAR |
| |
| [+] Ha sido utilizada la clave: [ EZINE ] |
| |
| real 4m23.204s |
| user 4m22.124s |
| sys 0m1.092s |
o------------------------------------------------------------------------o

HEMOS DADO CON LA CLAVE!! Saltemos, vayamos a la nevera por un refresco y
congratulemonos durante un momento.

OK, vale, ya esta, ahora a lo serio nuevamente. Las pruebas fueron realizadas
en un "Intel Core 2 - 2,16 Ghz".

Habras visto, que en este ultimo caso, incluso el Indice de Coincidencia esta
mucho mas proximo al del español que en el falso positivo que obtuvimos antes.
Podrias jugar con la instruccion que deja pasar a unos y a otros, cambiandolo
por ejemplo de esto:

if ((IC_ES - ic) < 0.002) {}

a esto otro:

if ( ((IC_ES - ic) < 0.001) && (ic < IC_ES) ) {

De este modo bajamos mucho mas el limite de posibilidades y evitamos tambien
aquellos IC que pasen por encima del establecido para el Español. Podrias
probar con un valor de '0.0005' (hubiera valido porque en nuestro resultado
el texto descifrado se encontraba exactamente a '0,000231' lo que entra dentro
del limite).


-----------
| DEBERES |
-----------

Creias haberte librado, pero de eso nada, esta muy bien aprenderse la leccion,
pero mas todavia saber hacer las cosas por uno mismo.

Bueno, el problema es el siguente. El programa anterior funcionara en algunas
ocasiones y en otras no lo hara. Porque???

Bueno, el problema radica tambien en el Indice de Coincidencia. Este valor nos
orientaria mucho si desconociesemos totalmente la longitud de la clave, pero al
conocerla ocurre lo siguiente:

Tenemos un texto cifrado con Vigenere: QHVBQFQMRWFKIPORFMY
Cuyo texto en claro resulta ser: MINOMBREESBLACKNGEL

El problema esta en que, aunque no sepamos exactamente cual es la clave, para
cualquier otra aleatoria que utilicemos y tenga la misma longitud que la buena,
el texto se partira en bloques de ese tamaño.

Si la contraseña tiene longitud 6, el cifrado se partiria asi:

BLOQUE 1 -> Q F F R
BLOQUE 2 -> H Q K F
BLOQUE 3 -> B R P Y
BLOQUE 4 -> Q W O

Llegados a este punto, como ya hemos dicho antes, cada bloque individual ha sido
cifrado con un mismo alfabeto, lo que quiere decir, que aun desconociendo la
clave verdadera, estos bloques ya poseen la misma frecuencia que el texto en
claro. Por tanto, si tienen la misma frecuencia, deberian tener tambien el mismo
Indice de Coincidencia.

Por todo esto, el programa anterior deja pasar a muchas claves como posibles
porque su indice de coincidencia se acerca mucho al del español aun cuando no
son las que descifran correctamente el mensaje. Ese fue uno de los motivos
principales para utilizar un diccionario secundario.

Ademas, cuanto mas pequeño sea el texto, mas irreales seran estos valores y
el programa podria incluso dejar pasar de largo la contraseña correcta.
Pero para esto hay una posible solucion. Centrarnos unicamente en realizar un
ataque de diccionario sin fuerza bruta.

No os voy a mentir, para romper un cifrado propuesto en un reto de los wargames
propuestos pos "warzone.elhacker.net", utilice el codigo anterior simplmente
borrando las comprobaciones del IC. Es decir, fuerza bruta pura y dura, y
funciono! };-D

Tu mision es coger el codigo del programa anterior y modificarlo para que
solicite dos diccionarios. Uno es el que ya estamos utilizando, y el otro
sera el que contenga las palabras que se utilizaran como claves posibles
para descifrar el texto. Un bucle ira recorriendo todas las palabras del
diccionario de claves, y para cada descifrado buscara en su interior las
que se encuentren en el diccionario de español. Si encuentra alguna, lo da
como correcto.

Apenas hay que agregar unas cuantos lineas de codigo para lograr este objetivo.
Si te fijas bien, y eres listo, podrias incluso utilizar el mismo diccionario
para los dos propositos. Eso si, una pista, si intentas esto acuerdate todo
el tiempo de la funcion 'fseek( , , );', de otro modo podrias quedarte atrapado
en un bucle indefinido o no realizar todas las comprobaciones correctamente.

Y acuerdate que si vas a buscar claves que sean de una longitud fija, debes
utilizar un diccionario cuyas palabras no tengan ni menos ni excedan de esta
longitud. Modifica la sentencia de "gendic":

if (strlen(word) >= len){} -> if (strlen(word) == len) {}



---[ 7 - Conclusion

Desconozco si habra una tercera parte de esta sencilla saga, no obstante,
existe algo mucho mas alla de estos articulos, y esa parte eres TU.

TU debes explotar tus conocimientos, TU debes desarrollar tus aptitudes,
TU y solo TU puedes hackear el mundo.

Hazlo, no tengas miedo, estamos contigo!



---[ 8 - Referencias

[1] Una Introduccion a la Criptografia
http://www.criptored.upm.es/descarga/UnaIntroduccionCriptografia.zip

[2] Dev-C++ (version 4.9.9.2)
http://prdownloads.sourceforge.net/dev-cpp/devcpp-4.9.9.2_setup.exe

[3] Algoritmos de Ordenacion - por Sebastian Gurin (Cancerbero)
http://es.tldp.org/Tutoriales/doc-programacion-algoritmos-ordenacion/
alg_orden.pdf

[4] Hispasec Sistemas
http://www.hispasec.com

[5] SET-Ezine (SET mirror)
http://set.diazr.com

*EOF*

← previous
next →
loading
sending ...
New to Neperos ? Sign Up for free
download Neperos App from Google Play
install Neperos as PWA

Let's discover also

Recent Articles

Recent Comments

Neperos cookies
This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.

By pressing OK you agree to the Terms of Service and acknowledge the Privacy Policy

By pressing REJECT you will be able to continue to use Neperos (like read articles or write comments) but some important cookies will not be set. This may affect certain features and functions of the platform.
OK
REJECT