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"

12 comments:

Alejandro said...

Este codigo esta erroneo, he intentado sacar una contraseña de vigenere y me da siempre una excepcion de punto flotando en la funcion kassiski_get_pass. Por cierto, tambien se te ha olvidado postear los include.

beck said...

Es probable, lo hice hace 3 anios :p
En su tiempo me funciono perfectamente...
mandame tu texto cifrado y te lo descifro con el programa maniana o pasado maniana si tengo un rato libre.



Saludos

beck said...

Sirve de que corrijo el programa , los includes no salen porque los tags en html se pierden o se escapan...

pero pues como ves , no debe de ser nada del otro mundo, todas las funciones estan autocontenidas.

Saludos

Alejandro said...

Lo que estoy intentando descifrar es parte de un juego en el que tu tambien estas. A ver si adivinas cual? jejeje Por cierto perdona por tardar en contestar pero deje la criptografia unos dias. Gracias por la ayuda y un saludo :)

beck said...

De donde nos conocemos o que onda?

Alejandro said...

Estoy en el juego de elhacker.net

Anonymous said...

Me podrías decir cuales son los includes que faltan???

Es que me gustaría utilizar el programa para unas tareas de clase... :)

beck said...

Ha de ser stdlib.h , stdio.h y string.h

Saludos

Anonymous said...

Muchisimas gracias :)
Algun compilador especial que tenga que utilizar??

Jose said...

NAMEZRBTEZNNIVNSKLIFYOZSXJMGWHABAMBLEWPBEBUIBQAMOBQPPWGCJIWRGIWWBDFKSFJMTMFKMYYQÑXZIOCBAXNPZMVEYAWIXAXTMZNNIVNAFMVGYPXSFGYPOUBXLIFBFAXULQIWPCFUXQPNZIGYZPSZBBSPHLAWOBQCPOBQMNSFBBSEECXSMZERPWGGZIYEYIWEXRXPGNCKSEOSXSIXAMUGQÑQWHQQRQIGNBAIXÑBWVPCPIVENISEPNJPVNPXUGBLDZEZÑOWFNZFSMPYALIXKRUHBBBTEZCOIHUDBZIZRBYYQJMAMZBMÑIEKXUSFNJCWHJJIQQQVSSFCKKSZROIVQKMAIZQBUHNQAPWGGKBEFYIIWPCBAXBQBSLQAEPDBBBLIGCOTMZYAIWRSKKMBLBAKEYJIXUAXSIFCPMQPCCPQURFDEQJEMGTGWWHQHRPGUNPLIIYIWVRGPPSXNDPGBQVLIONKLMOGMUIFPXKMNJBAXBBMMWGNNIVNPBNYGYOSEFSNMVRGZPEXGAIHPCIWGWCBUOBPBNIECKBINJXXVBABLIZAFIHQJXAMPCXAONAXCWNQRPGNSPIHQQFTMFKMMWXYJMNBPXCXBAMUXEYAPGOGMUIKAMÑMGYAILNQQIETNOIYZYBATQAFMHQTFWONAFWQLYZBSONKBVNLXBYEYIWKUAMATQPMMOPCPMQRPBUEPNMZKHJIWHQJEWPÑPBSITYISIIYAWEQLOMHNPPMHQKXUIEYNZSRSKLELFMZVUZIMNHQQWIZCPMWULPMQGGAWONYPXMEYZPSZYIIOUZBZXNBAMONTMSYZRXLIZRBUHUBXMQNORMOFCKBMPNJMXNDFAMONVAYCCOSEGGSWUHCNWVPCPÑVNAFIGBLQPQHYAWPULXUHBCKSEFAXJIMYPLIXNPAIYGFUWGPRPHBQIIEFÑFZEOGMUEOYOÑEESKWPUQJWGBLIIVQQNWQFYYPOUBXLXBRXSCHJQPPNBBAYFYZKMBLBACNBBAGNPDIVPCBSONYAPSFYITYZBMIOBQXUXQÑXAEPNPIONXXZEXYPWGUCAIHQORPZNJBMQQDBKXBLXLEYCKWWDSBIWQPNZIOGPIPQLQMEDSBSONAXCWNQRKEHQXLIFGJPWYNVIWNAXZWQYPPPUQJWHQJXKMQLXÑEPCIIQNBXGEFYIPVNJXMBUQQMQOGXIFNQBLIGGOIVFCAMOBQZIFQJIWWONKCQNRBTIEGAIHNSKTELNOYYQJXLIYSKKLTYRAIZQRXSZGBUHBORMEXERPIZJIMKHCXAMNBXZWQARMQGYAMONPRAXUAXAMYÑIMDNBBMWQDXTSFNZWQOCNBSPCIIZBJRUXNBIPFECVAIXNYWVECAMONAXJIMYVWOQPRMKBCKBSZABAUHCAMYZÑXASYYPMQFSFSYFROIGUNKGWQZMZVQRXTFUCKLIXYZIFQXXSSONKBVNPFWHQYÑCIXKMUWGPRWWBAMUGQÑQWHQJXDSXSKBEPJFJVQKBZIRGBZSNJXDSXSKBEPLMSMÑPBYYQYYWGNYRUYFNBZVBLBWHQAXCWNWBNIORMUSPCYMPBQZWWUDFKEECÑCMINZIHNKBUXQAXCWNWBNIORMKSYNEIGQLIWWULSMWGGDIHBPBAHQJXUEGSOIOQXXGUHGBUGBKMMOXNPUEGSOIOUXXOSLCKMOCCKAEECKKSZDMZPUBXLGBLBSHBKFUEZRBKVQRFUMFKMTIOYKPGUQQIIXARIOPCGIUHCIIGNSPITECPPSZCVMPCSGMLNQQIUHCNZSPSZMIXCCMGGNAMFQKMAWQPSPVZNPXVQAFAEYCKBIPCIIGNSPIHQJBNIORMUEPYJIWDSBKSYNAMGBLZMTGNPXYENPMWPCZPVRGZKMBLBAGBLSMQOGMUEXCPKSZDFUIFBBLIFGDUEOGMUHQCKBIZBFTMQLQWTQPMUSPCBFTXGZIGUNKMQXNBUWULMOELJXHSFAXCWNJBAQULBKIFGAIHZGKWOUZBZXNBNAMONIWKUAXIOXGKWWUERMIXCCMGGNXSEOYRAENJIPQBEMJMQPKIOQWKPQSSKIQBQMBVBQPWPBQIWWHLFKSFORMLQKMAMZTBUXNBMSEFAXCWNQIIWHABAMBLIIVQAFXVBAFLEPJXZIXYQPZUBXLONAMIGOGMUIXLRTIENIIOQWIIOUZBZXNBBSPBRFDSXYCPQNJFLEPWPPIYÑOMUHCXMWGCJCQPNAMWUEKWWXNFUXENACGUKMAJUAQPGUYJMQGCVSSQLQZIYCWKONKMAGBKMAMRSBZEHLBUWUCKSEFAMAEFAMUXULRIPBQXKXHYKLSPCFÑYNJJIQQPXYYQFBTSFYZBYNBMAMQKNZINQXJIEBBTEZCOIPURMSSSGZIONTMSYZRXLQBJFJVQCPTMGNIWKUYBUONTFLEECXSQBFXGPNQÑCIINICQGYANYQPQMCINICQGYALIÑGIKSZQQPXHWBKEFGPPIYÑOMCNSKAMZRMTEPCIWUHCXCQCCKAEPNOSIRYIBEQJEMGTNAMUHCBUXBBXKSZCUPSZAXCWNJVMQGNAIQQABAMPYAXWUAMSSSGZIXQLDIIXQBUXUKFMQGNAMEXEMLIONXKGUNKLIZCZMWUBXLHQQRKIFGMUSÑJFÑEPYAMTECPPSZBBNEXRXLIXGYMVGYAMOGCKMVCPBKMFYJMQGCBAIFCKBMYGBUXBPBAYXRXLIXYQWVXYNMVFNKIWQBBSEGYXAMYGPTELCKÑIZCOIOFGJPWBZPMVIYZPSZCPASZAMZVQAQIWXYKWOUZBZXNBAMONTMSYZRXLWQ

Jose said...

AMUGUZBKSYNNZSÑJBTEPCPLIPNPSEPNPKSYÑIMXNKBUXQNNCIFRMATQPMAMQKNZIPCRUEYYKMVNFMUHNKBUXQÑBZWBLXSOBQRUSFLMYYUCOMQECKCQOGXZEZGKÑYZÑOMGUNXAYECPXSZQXJMXGAIHNJXNIQLPPPUQJWWNJAMVQAEWTQPPWQNJXAYYCOPXBJXAVNXXAZNLFLSFYPAIQLZCIZROIQQLBAXQJXLSXNPWXENPIONGKDIEQXUSDSFMVQLPIOUPOMWCNKAEÑJBAHQLXLEGCKMVOSIXEPCKIHNWXATUPXUHQQAMYZYRBSPCPXVQAFWMZRFTSNÑMLIECZOEEQRKEEEXASÑPBKYNJÑCMQPZWWNCPBSFSIBMYNPKYNLAWIFAOPFQLIPFENPAYQJBUEFSJPVTNVSEPCCMQFYAMOBQZZMYGKIOQQRUEQQNMGUCAMGBKNIWUNKASOGXSMFRXMWFSAPWRPXHPNQXÑVNBXJOQWAMLQAEWIXDXBEXGPTSPCIWWPCYPOQQAMZBJRUXNBPMIYZBSOQABLIYNAWWBPNZIZBBUXQARIQPNPIFQÑOMWQLQIVFCXAMYGPTSONJWONPBSMSGMUHQJXASHDCZEZABOYYYFUIXYOMOUEFWQPCIAYRPFTMQLQWLHKXUSQQBMWFSYCIZERAXBÑBZHBLBAIYCBSUHCVWGBKMDMQHMNMXNIWKBORMQBÑRMHQBBQEEQRTEXGZPEFCLIOQAMUIXBBLSXYPTEXYPIVGCPLIULQMVCPBBEOGMUTQPMMWDSBMWNPBÑYXYOPHNBAMONLXBYEYIMDNBBYYQTMASGPMAOBQCPWUAMALNZIIMFAMUXNLQWSEERSOBAMTSFGKWIKGPBIYYPYYQEOIGUYPIZHCPBVNGKBIEÑOMXNAFWQLYSCIFROIPNJXNMXNIWKUYBSONLMMWHLEMGTNKWIFSKBIKRMIQGCPJMQLBAXNLPWOBSKIPNMMGYZYAPWGNOAMBLFUKQLRIPQLQMLHKXUMGYOPSFBBSWQLQPHBAMUOBQÑCIONJXONABPWÑYPBEZRBIOBQFUWGGKBSFBBTSOPXBMONPLIXYITEYNAMVZYBUXBBXATNPQMWUERIOPYAIQGCIIOQWIIQNRRZEXCWIQBQBMQOSBUXEYBUIFRBXYZRMMQONKLMOGMUIFBFAXULQIWZGJMNBPBAUHCKWWBROWWSPXKMBQXZIGGZMQOGXKSZJXKYNJPMIZKXAGNPXCQNTBHPNQIILBQQPOUBXLHQJMALBKYZIFBBSECJBJIONKBVNRMLSXNNZMIGIMKUYAWCFNYMVNLMGEFGJPWYNRUWQERUHBWJIWFSQPONRBPWYNKPHUCRUMYYFBVQLFLMBQKPEYNQIPÑGBUZBQMBVBQÑCIECFAIFNVXSECISSIGSIONJBGQNRRZEXYKWIFTBZHNBNMVBAMTSTCJWWPGZOSQQQWIFGKBIEÑOMXNAFWQZNQMBGNVXSPPFIZQLFZEXERPIZORMGBLRUEULQMQOGMUCHLXZXQGKBIEÑOMXNRFDSNLQPXQRFKSFQRXMQQBAEOYOLIXYIMGGSOIHQCPIPUQJIQNRRZEXCWICQLOMONAFWQNJMAPUQJWWRCKWPQLMAGNZXSPQLQMIXROPYZDMBMEYKPGBBBATUYAIHBCFUIKNOIFXCAMTECQMQFGMUIFBBXSPCOCQULQMVCPBBIDSBWWCSPPIFCAMXNJJWHBYKBIXNPWNBQIIYZGSMVFYIPHNBBPQONKLMOGMUEXGAIHIGDMQGCPMQGNAIZBJRUXNBAMTBBBZUHCZIWURMLECYIIFEYEIWGYIITENNPECYIIFEYQPVNLFIEOYYIWQÑXZIOGBUHBGKCXUJFHEÑJBWYZYJMXNDMZEPCYPOURXUXQWPCEIGWIHBPXIOSNAMPNQFIHBFRTEZNVYYQQFUIYZXZKBYCPVYYPMEOCOKEPCBAXQKRUHBCKNMZBBKYQLQIWXNJPWYNÑCIINPWXENPIJUPJIMFYPIFQPÑCIGGBUIHLZCVFNKMGQQXZMBWZIOOSIIFXCNMVBLMXSEORMIZCILSYGKMQXCVMWFGKWTBPÑCIRYIBEZYYASXSQIPQLQMONQIMCQQVBSPNNWHQPPIGNCKKEPYFUWGYKBIFSRSXUKXKSZQBKYQLZPEFSNWQUCKLSDSBBEYZFMQQQQWWQYKIHNKXAUHCFUXQPNZIG

¿Podrías decirme el texto obtenido? Es vigenère (junta los dos mensajes)

Gracias

Anonymous said...

DEBERIAS DEJAR EL PROGRAMA, CON EL CODIGO FUENTE!!!!!