Progetto ‘combina’

21 giugno 2006 admin Nessun commento

Project combina is also now on freshmeat.net!

New release: combina 0.4.1!

“combina” è un generatore di password che utilizza quattro diversi algoritmi che si basano sul calcolo combinatorio implementando le Disposizioni Semplici o Permutazioni, Disposizioni con ripetizione (il famoso Brute Force), e le Combinazioni con e senza ripetizione! Supporta un numero illimitato di caratteri in input e restituisce l’hash MD5 e SHA1 delle password. Questa nuova release apporta le seguenti modifiche:

1 – aggiunta la man page;
2 – possibilità di installare il programma con il ‘# make install’;
3 – pacchetti Ubuntu (Dapper) disponibili;

Buon divertimento!

Vai alla sezione di download oppure continua leggendo la seguente breve introduzione al funzionamento:

Combinazioni…

…matematiche oppure no hanno sempre suscitato grande interesse e curiosità in tutte le situazioni in cui si sono presentate. Dal classico caso che capita quando cambi percorso per tornare a casa ed incontri un vecchio amico, al calcolo delle probabilità di fare un full quando scarti tre carte e mantieni in mano una coppia di donne.

Mondo matematico

C’è chi dice che il mondo è matematico ¹, come dargli torto se tutto intorno a noi è soggetto a leggi fisiche e matematiche che si fondono per spiegarci il perchè di tutto. Io sono dell’opinione che le cose che non
riusciamo a capire oggi saranno oggetto di future scoperte scientifiche un domani e che non accade mai niente per caso. Bene, ora vediamo che tipo di combinazioni possono attirare la nostra attenzione e perchè sono spesso protagoniste nella nostra vita quotidiana. Parlavo, senza ombra di dubbio, di quelle che abbiamo conosciuto durante l’ora di matematica. Si, proprio quelle che ricordiamo sotto il nome di Calcolo Combinatorio.
Applicando quei teoremi e definendo un algoritmo logico, descriveremo la logica funzionale del programma che metteno in pratica quelle nozioni, a volte tediose e ripetitive, sicuramemte per colpa dell’insegnante .

Al cinema

Quante volte abbiamo visto sul grande schermo quelle scene di intere videate piene di caratteri alfanumerici che freneticamente rincorrono e braccano una password? Come fanno miliardi di combinazioni ad uscire dal cilindro di un mago-programmatore che al posto della bacchetta magica usa la tastiera e pronuncia i suoi #include come “Abracadabra”?

E’ proprio questo l’argomento che andiamo scoprire, come creare un generatore di password!

Refresh

I programmi generano quelle combinazioni seguendo dei principi che hanno radici molto lontane rispetto all’ avvento dei computer. Iniziamo quindi, rivisitando quelle definizioni matematiche del calcolo combinatorio che ci forniranno il motore di tutto il nostro lavoro:

Dati n elementi distinti, si chiama “disposizione semplice” degli n elementi, presi a k a k, ( k<=n ), o della classe k, un gruppo ordinato dik degli n elementi dati. Esempio:

Per n elementi distinti = a,b,c
di classe k = 2, abbiamo

ab
ac
ba
bc
ca
cb

in totale 6 combinazioni;

Dati n elementi distinti, si chiama “disposizione conripetizione” degli n elementi, presi a k a k (con k numero intero qualunque), un gruppo ordinato formato con k degli n elementi, potendo uno stesso elemento figurare nel gruppo fino a kvolte.
Esempio:

Per n elementi distinti = a,b,c
di classe k = 2, abbiamo

aa
ab
ac
ba
bb
bc
ca
cb
cc

in totale 9 combinazioni;

Si chiamano “permutazioni semplici“ degli n elementi distinti le disposizioni semplici degli n elementi presi ad n ad n.
Esempio:

Per n elementi distinti = a,b,c , abbiamo

abc
acb
bac
bca
cab
cba

in totale 6 combinazioni;

Dati n elementi distinti, si chiama “combinazione semplice” degli n elementi, presi a k a k, (k <=n ), o della classe k, un qualunque gruppo formato da k degli n elementi dati.
Esempio:

Per n elementi distinti = a,b,c
di classe k = 2, abbiamo

ab
ac
bc

in totale 3 combinazioni;

detto questo non rimane altro che costruire un algoritmo in linguaggio C che implementi tali combinazioni.

Considerazioni generali

Dalle definizioni che abbiamo elencato si nota che le “disposizioni conripetizione” rappresentano l’insieme più completo di tutte le combinazioni. Le altre definizioni danno origine a dei sottoinsiemi di quest’ultimo, per questo motivo analizzeremo nel particolare solo il metodo della costruzione delle disposizioni con ripetizione.
Gli elementi che verranno utilizzati per creare le combinazioni sono i caratteri delle stringhe di cui vogliamo trovare tutte le combinazioni, in modo da imitare uno dei più famosi attacchi, cioè il brute force.
Il programma che svilupperemo si utilizzerà da riga di comando nella shell di Linux o dal prompt del dos, ricevendo come argomento dall’utente la stringa da combinare, la classe e il tipo di combianzione da impiegare.

Esempi:

$ combina -ra
aaa
aab
aac
aad
aae
aaf
…
zzz

$ combina -dA -k4
ABCD
ABCE
ABCF
ABCG
ABCH
…
ZYXW

$ combina -cn -k6
012345
012346
012347
012348
012349
…
456789

$ combina -r -k6 –user=danilo –md5
980ac217c6b51e7dc41040bec1edfec8 : dddddd
a6aa9df36c6a68ecb3eeb31a0770b6bc : ddddda
129341643219785e0175eb6e1d65edf6 : dddddn
e6591d381d486cd050f4ecdb0fb9ce88 : dddddi
699956cefc6bd6c84495f8add5d0e417 : dddddl
…
9982b2a7fceaaee2c8444b5086aee008 : oooooo

$ combina -dn -p 4 -k 6
0123
…
9876
01234
…
98765
012345
…
987654

$ combina -da -p3 -k5 –md5 | grep cf8595b8eecec82ad07aa16c818fea7c
cf8595b8eecec82ad07aa16c818fea7c : dcia
per trovare un hash MD5 tra quelli generati

$ combina -ca -k4 –sha1
81fe8bfe87576c3ecb22426f8e57847382917acf : abcd
…
a0d8a72797b5185f097a4f0f8cc7b19d98b72a5e : wxyz

$ combina -r -k 4 –user=01 –add-before=bin_
bin_0000
bin_0001
bin_0010
bin_0011
bin_0100
bin_0101
bin_0110
bin_0111
bin_1000
bin_1001
bin_1010
bin_1011
bin_1100
bin_1101
bin_1110
bin_1111

Note :

1: “Perchè il mondo è matematico?” di J.D. Barrow.

Screenshots :

Screenshot nr. 01

Download :

combina (GNU/Linux binaries)

combina (Windows binaries)

Codice sorgente (Platform Indipendent)

Codice sorgente (Progetto Dev-C++)

Sono necessarie le librerie di argtable2.x e openssl 0.9.x e per Dev-C++ seguono i relativi pacchetti:

DevPak Argtable

OpenSSL devpak from repository

GNU/Linux Packages:

pacchetto .deb per Ubuntu i386

combina_0.4.1-0ubuntu1_i386.changes

pacchetto .deb per Ubuntu AMD64

combina_0.4.1-0ubuntu1_amd64.changes

combina_0.4.1.orig.tar.gz

combina_0.4.1-0ubuntu1.diff.gz

combina_0.4.1-0ubuntu1.dsc

I pacchetti .deb con i relativi sorgenti (qui sopra) sono stati realizzati da Giuseppe Borzì al quale vanno la mia stima e ringraziamenti.

Links :

en.wikipedia.org/wiki/Combinatorial

it.wikipedia.org/wiki/Calcolo_combinatorio