Wednesday, November 29, 2006

Hice un programa que rompe vigenere... o por lo menos hace una estadistica rapida,
y te arroja una clave posible.
Si la contrasenia que te arroja no sirve, de todos modos sirve que te dice las distancias y el factor mas repetido usando Kasiski, hice algunas pruebas, el password es BORGES en el siguiente ejemplo , mi programa arrojo DORGLS , si hiciera mas probabilidades de password con combinaciones de letras mas frecuentes tal vez seria mas eficiente pero 'la talacha' del algoritmo ya esta hecha por si les interesa... mas o menos asi funciona..., lo hice analizando de 3 en 3 palabras , tiene que pegarme el criptotexto en el argumento del programa y al final ponerle un numero , en este caso fue el "3" , que significa que analizara kasiski con palabras de 3 letras, les dejo el codigo si lo quieren, se le puede hacer una modificacion si gustan para que en vez de sacarlo de linea de comandos el criptotexto , mejor lo sacara de un archivo.. pero si lo necesitan con mucho gusto comenten.

dirichlet@beck /home/dirichlet/cryptanalysis/bvigenere $ ./bvigenere DIVTXSOELKIDDC
EJSJMSYGFABRZILGBZQUVJPJRGLSCSIARSGWVYXSFBVRGAFZFKPRPFIUHWTSRHENFFPRIVJXFGPUPBU
UVNBAFYNMOHFYRGUSMUCSMZVBEJQCIWYWOCMGWSBULGRLBFVRLSNPIKPWDCEZIKUCVRGGORFXTWSCVR
DGSFFKBYMODURGNSMUCSNCIOVVFVRSFJFSEZSFDSJKPUPBUUVDFZCKZGIOJZEWMQZKPGBZCGpSHSEZI
KFDIKKMOHRHEIVSRTMEBZVYIKUSVRDGSFFVIJNOEKGAPSEARJJBTURWTHRHEJPMVTHGMCJNYWTCJJIT
BXFJIDBGDKWSTSCISFECIYIVFGVTXWORZUHWMNFXVGZGVLYWESJVYWTSCFSJSCSAWUPOCISFECIEEDO
CVTGGOHIGVDPGLVPADCRRPGSCGGVSRIVRSDMSMGWWFGKKPWQWUOSIVSRRMKUOJKQMDVRYSYBOCGGSCO
IKPRPFIUPWEWAULWSARTSQBVZIIDBGFME 3
Distancias obtenidas
354,138,210,349,102,426,426,426,426,426,294,312,186,234,357,126,126,126,126,126,
156,78,78,78,318,59,342,306,96,96,120,12,252,108,108,108,108,108,241,42,48,198,1
72,198,60,180,180,42,54,54,54,54,54,53,49,
Multiplos obtenidos de las distancias
49,49,17,5,48,12,5,23,5,2,16,6,10,5,3,3,23,4,11,2,5,6,10,5,2,2,2,8,6,10,2,3,2,3,
2,2,10,2,4,6,2,5,6,2,2,2,2,5,6,5,2,2,2,5,5,
Prioridad 1 para posible tamanio de password es 6
Prioridad 2 para posible tamanio de password es 6
Prioridad 3 para posible tamanio de password es 3
Posible Clave: DORGLS
dirichlet@beck /home/dirichlet/cryptanalysis/bvigenere $

Eduardo Ruiz Duarte

Codigo, si gustan que lo comente , diganme... esto es con propositos estrictamente personales para poder hacer mi tarea sin tener que andar contando , en efecto la hice y tarde en hacer este codigo un par de horas y la tarea era como para 140 horas.
me pusieron 12 de calificacion de hecho por haberla entregado unas horas despues....
pero si gustan ... con mucho gusto les comento el codigo , pero quiero saber que esto no sera en vano.

Saludos

/*
bvigenere 0.01 beta
Programa que 'adivina' password de sistema cifrado con vigenere.
si este no fuera el password , de todos modos puede ser util
porque imprime en pantalla las distancias y los multiplos y calcula cual es el que se repite mas , asi como obviamente proporcionar un posible password
esta muy sucio , debe tener algunos memory leaks , y hasta heap overflows...
pero bueno... lo siento... solo que esto lo utilice para hacer mi tarea...
un poco mas interesante y fue lo que me salio a la primera.
Eduardo Ruiz Duarte
rduarte@ciencias.unam.mx
*/
#include
#include
#include
typedef struct kasiski_offsets_t
{
char *word;
int *offsets;
int n;
} kasiski_offsets;

kasiski_offsets *
kasiski_alloc (int s, int w)
{
kasiski_offsets *ptr;
int i;
ptr = calloc (s, sizeof (struct kasiski_offsets_t));
ptr->offsets = calloc (s, sizeof (int));
ptr->n = s;
for (i = 0; i < s + 1; i++)
{
ptr[i].word = calloc (w, sizeof (char));
ptr[i].offsets = calloc (s, sizeof (int));
ptr[i].n = 0;
}
return ptr;
}
void
kasiski_free (kasiski_offsets * ptr)
{
int i;
for (i = 0; i < ptr[0].n; i++)
{
free (ptr[i].word);
free (ptr[i].offsets);
}
// free (ptr);
return;
}
int
is_allocated (char *str, int w, kasiski_offsets * words, int index)
{
int i = 0;
char *t = calloc (w, sizeof (char));
memcpy (t, str, w);
for (i = 0; i < index; i++)
{
if (strcmp (t, words[i].word) == 0)
{
free (t);
return 1;
}
}
free (t);
return 0;
}
void
give_me_distances (kasiski_offsets * w, unsigned int *d, int slen)
{
int i, j, k, t, c = 0;
for (i = 0; i < slen; i++)
for (j = 0; j < w[i].n; i++)
for (k = 0; k < w[i].n; k++)
{
t = abs (w[i].offsets[j] - w[i].offsets[k]);
if ((t != 0) || (j < k))
d[c++] = t;
}
printf ("Distancias obtenidas\n");
for (i = 0; i < c; i++)
printf ("%d,", d[i]);
printf ("\n");
return;
}
int
max (unsigned int *x, int l)
{
int i, t = 0;
for (i = 0; i < l; i++)
if (t > x[i])
t = x[i];
return t;
}
char
max_index (char *x, int l)
{
int i, t = 0, r;
for (i = 0; i < l; i++)
{
if (t < x[i])
{
t = x[i];
r = i;
}
}
return r;
}
#define MAX_FACTORS 8112
#define MAX_POSIBLES 3
int
usual_factor (int *x, int xlen, int *pos)
{
int i, t = 0, r, j, m = 0;
printf ("Multiplos obtenidos de las distancias\n");
for (i = 0; i < xlen; i++)
{
if (x[i] > 1)
printf ("%d,", x[i]);
}
printf ("\n");
for (j = 2; j < xlen; j++)
{
for (i = j; i < xlen; i++)
{
if (x[i] > 1)
if (t < x[i])
{
t = x[i];
r = i;
}
}
pos[m] = r;
m++;
if (m > MAX_POSIBLES)
return 0;
t = 0;
}
return 0;
}
int *
kasiski_analize_passlen (int *distances, int slen)
{
int i = 0, c = 0, r, k = 0;
static int posibles[MAX_POSIBLES];
unsigned int *factors = calloc (4096, sizeof (unsigned int));
while (distances[i] != 0)
{
for (c = 2; c <= distances[i]; c++)
{
if (distances[i] % c == 0)
{
factors[c] += 1;
k++;
}
}
i++;
}
r = usual_factor (factors, k, (int *) &posibles);
for (i = 0; i < MAX_POSIBLES; i++)
printf ("Prioridad %d para posible tamanio de password es %d \n", i + 1,
posibles[MAX_POSIBLES - i]);
free (factors);
return (int *) &posibles;
}
#define MAX_PASSLEN 32
#define MAIN_LETTER 'E'
char
get_letter (char *buf, int blen)
{
int i;
char alfa[26];
buf[blen] = 0;
memset (&alfa, 0, sizeof (alfa));
for (i = 0; i < blen; i++)
alfa[buf[i] - 'A']++;
return abs (max_index ((char *) &alfa, 26) + 'A' - MAIN_LETTER) + 'A';
}
void
calc_pass (char alfa[MAX_PASSLEN][256], int len, char *pass, int alen)
{
int i;
memset (pass, 0x0, MAX_PASSLEN);
for (i = 0; i < len; i++)
pass[i] = get_letter (alfa[i], alen);
printf ("Posible Clave: %s\n", pass);
}
void
kasiski_get_pass (char *buf, int blen, int *plen, int pnum, char *pass)
{
int i, j, k = 0, m;
char alfa[MAX_PASSLEN][256];
m = plen[MAX_POSIBLES - 1];
memset (&alfa, 0, sizeof (alfa));
for (j = 0; j < m; j++)
{
for (i = j; i < blen; i += m)
{
alfa[j][k] = buf[i];
k++;
}
k = 0;
}
calc_pass (alfa, m, pass, blen / m);
return;
}
void
kasiski_attack (char *str, int s, int w, kasiski_offsets * words,
unsigned int *distances)
{
char *tmp = calloc (w + 1, sizeof (char));
char *tmp2 = calloc (w + 1, sizeof (char));
char pass[MAX_PASSLEN];
int *plen;
int i, j, k = 0, m = 0, strcount = 0, d_alloc = 0;
for (j = 0; j < s; j++)
{
words[j].n = 0;
if (!is_allocated ((str + j), w, words, s))
{
memcpy (words[strcount].word, str + j, w);
for (i = 0; i < s; i++)
{
memcpy (tmp2, str + i, w);
if (strcmp (words[strcount].word, tmp2) == 0)
{
words[strcount].offsets[m++] = i;
words[strcount].n += 1;
d_alloc++;
}
}
strcount++;
}
m = 0;
}

k = 0;
distances = calloc (d_alloc, sizeof (int));
give_me_distances (words, distances, d_alloc);
plen = kasiski_analize_passlen (distances, d_alloc);
kasiski_get_pass (str, s, plen, MAX_POSIBLES, (char *) &pass);
free (tmp);
return;
}
int
main (int argc, char **argv)
{
int *distances;
if(argc < 3) {
fprintf(stderr,"ERROR: Necesitas proporcionar el criptotexto en argv[1] y en argv[2] el numero (tamanio de palabra) con el cual vas a analizar usando kasiski para las distancias (recomendados: 2,3,4 o 5)\n");
}
kasiski_offsets *shit = kasiski_alloc (strlen (argv[1]), atoi (argv[2]));
kasiski_attack (argv[1], strlen (argv[1]), atoi (argv[2]), shit, distances);
kasiski_free (shit);
return 0;
}

"Education is a system of imposed ignorance"