Per scopo didattico, mi è stato più volte richiesto di realizzare un metodo che calcoli tutte le permutazioni di un insieme di caratteri dati come input. Per chi non lo sapesse, le permutazioni sono un modo di ordinare in successione n oggetti distinti.

Ad esempio abbiamo che le permutazioni dell’insieme di caratteri { ‘A’, ‘B’ } sono:

  • AA
  • AB
  • BA
  • BB

Il numero di permutazioni è molto alto in caso si considerino insiemi di ordine elevato. Questo genere di permutazioni, sono usate spesso negli attacchi a Forza Bruta, o Brute Force, per cercare di violare o rubare password. Con questo breve articolo, non vi invito a provarci, ma bensì a convincervi che questo tipo di attacco, il Brute Force puro, non vi porterà mai al successo… soprattutto se lo volete in tempi brevi…


Dopo questa piccola premessa, vi mostro il codice che ho usato per realizzare questa piccola classe, da usare ogniqualvolta avrò la necessità di usare permutazioni di un insieme di caratteri.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class BruteForce
{
    private char            alfabeto[];
    private char            alfabeto_default[]  = {'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'};
    private StringBuffer    corrente;
    private boolean         prima_permutazione  = true;
    private int             lunghezza;

    public BruteForce (char alfabeto[], String inizio, int lunghezza)
    {
        // La lunghezza delle stringhe da generare deve essere nota
        this.lunghezza = lunghezza;
       
        // Se non viene fornito un alfabeto, uso quello di default
        if (alfabeto == null) this.alfabeto = alfabeto_default;
        else this.alfabeto = alfabeto;

        // Se non viene fornita una stringa iniziale, uso quella con tutti primi simboli dell'alfabeto
        if (inizio == null) impostaStringaIniziale();
        else this.corrente = new StringBuffer(inizio);
    }

    private void impostaStringaIniziale ()
    {
        // Creo la stringa della giusta lunghezza
        StringBuffer tmp = new StringBuffer();
        tmp.setLength(this.lunghezza);

        // Imposto ogni carattere della stringa come primo carattere dell'alfabeto
        for (int i = 0 ; i < tmp.length() ; ++i) tmp.setCharAt(i, this.alfabeto[0]);

        corrente = tmp;
    }

    public String prossimaPermutazione ()
    {
        // Verifico se devo ancora restituire la prima permutazione
        if (this.prima_permutazione)
        {
            this.prima_permutazione = false;

            return corrente.toString();
        }

        // Incremento la stringa
        boolean continua = prossimoCarattere(corrente.length() - 1);

        // Se non ho finito, restituisco la stringa
        if (continua) return corrente.toString();
        else return null;
    }

    private boolean prossimoCarattere (int posizione)
    {
        // Se posizione == -1, significa che la stringa corrente è l'ultima generabile
        if (posizione == -1) return false;

        // Se il carattere LSB della stringa non è l'ultimo dell'alfabeto, lo incremento
        if (corrente.charAt(posizione) != alfabeto[alfabeto.length - 1])
        {
            // Cerco il prossimo carattere nell'alfabeto e lo imposto
            char prossimo_carattere = trovaProssimoCarattere(corrente.charAt(posizione));
            corrente.setCharAt(posizione, prossimo_carattere);

            return true;
        }
        // Se invece è l'ultimo dell'alfabeto, lo cambio con il primo, ed incremente il carattere precedente
        else
        {
             corrente.setCharAt(posizione, alfabeto[0]);

             return prossimoCarattere(posizione - 1);
         }
    }

    private char trovaProssimoCarattere(char carattere_attuale)
    {
        // Cerco il carattere che segue quello attuale nell'alfabeto
        for (int i = 0 ; i < alfabeto.length ; ++i) if (carattere_attuale == alfabeto[i]) return alfabeto[i + 1];

        // Istruzione per tacitare il compilatore
        return ' ';
    }
}

Il codice non sarà sicuramente dei migliori per questo scopo, ma ho puntato più alla chiarezza che all’estrema efficienza, non dimenticando che è stato realizzato puramente per scopo didattico. Questo è un possibile metodo main per utilizzare la classe di sopra:

1
2
3
4
5
6
7
public static void main(String[] args)
{
    BruteForce bf = new BruteForce(null, null, 4);

    String s;
    while ((s = bf.prossimaPermutazione()) != null) System.out.println(s);
}

Per ora sto usando questa classe senza aver rilevato errori o malfunzionamenti. Sono comunque a disposizione per modifiche e miglioramenti.