Avatar
Dan
Člen
Avatar
Dan:

Ahoj,

dělám projekt pro vzdělávací účely. Jeho účelem je za pomoci brute force odhalit heslo ( uložené ve Stringu pouhým porovnáváním .equals)

zatím se mi podařilo přijít na tyto algoritmy:

String choices = "abcdefghijklmnopqrstuvwxyz";
String[] arr = new String[choices.length() + 1];
for (int i = 1; i < choices.length() + 1; i++) {
arr[i] = choices.substring(i - 1, i);
}
arr[0] = "";
String guess = "";
boolean success = false;
first_loop:
        for (int i = 0; i < choices.length() + 1; i++) {
            for (int j = 0; j < choices.length() + 1; j++) {
                for (int k = 0; k < choices.length() + 1; k++) {
                    for (int l = 0; l < choices.length() + 1; l++) {
                        for (int m = 0; m < choices.length() + 1; m++) {
                            guess = arr[i] + "" + arr[j] + "" + arr[k] + "" + arr[l] + "" + arr[m];
                            tries++;
                            if (guess.equals(password)) {
                                success = true;
                                break first_loop;
                            }
                        }
                    }
                }
            }
        }

Tahle metoda funguje a je pro mne dostatečně jednoduchá, na začátek. Nyní bych chtěl vytvořit nějaký další způsob, který by přinesl rychlejší a efektivnější vyřešení problému. Jeden z problémů je například ten, že u některých kombinací, jako třeba "ab" dojde k jejich vyzkoušení 10x, neboť algoritmus zkouší kombinace "nic+nic+a+b+nic" i "nic+a+nic+nic+b" ikdyž jsou vlastně naprosto totožné.

Po té mě napadlo ještě jedno řešení:

static char[] list = new char[]{'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',
        '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',
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '.', '*'};
public static void main(String[] args) {

        String password = "*C0c";
        boolean pwcracked = false;
        double start = System.currentTimeMillis();
        for (long i = 0; !pwcracked; i++) {
            String attempt = numberToText(i, list.length);
            if (attempt.equals(password)) {
                pwcracked = true;
                System.out.println("Number of attempts: " + i);
                System.out.println("Password cracked. Your password is: " + attempt);
            }
        }
        double end = System.currentTimeMillis();
        double result = (end - start) / 1000;
        System.out.println("Time needed: " + result + " seconds");

    }

    public static String numberToText(long number, long base) {
        long divide = number / (base);
        long remain = number % (base);
        int remain2 = (int) remain;
        if (divide != 0) {
            divide = divide - 1 ;
            return numberToText(divide, base) + Character.toString(list[remain2]);
        } else {
            return Character.toString(list[remain2]);
        }
    }

Podstatou tohoto řešení je jeden cyklus, se zvyšující se hodnotou proměnné i. Číslo i se poté převádí na kombinaci písmen jednoduše tak že při kombinaci 65 znaků znamená 66 "aa". Čísla ale převádím pomocí rekurze (jednoduše zbytek po dělení 65 pořád dokola, dokud to jde), což se ve výsledku ukázalo ještě pomalejší než 5 vnořených cyklů s opakováním některých kombinací.

Uvítám jakoukoliv radu, jak zrychlit tyhle algoritmy nebo jakýkoli nápad na jiné, efektivnější řešení. Nechci celé řešení, budu vám neskonale vděčný když mi napovíte, předestřete jinou, rychlejší cestu jak vyřešit tento problém

Editováno 20. února 21:17
 
Odpovědět 20. února 21:15
Avatar
Michal Žůrek (misaz):

řešení tohoto problému je obecně dost časově náročné ať je algoritmus jakýkoliv.

Nahoru Odpovědět  +1 20. února 21:25
Nesnáším {}, proto se jim vyhýbám.
Avatar
Dan
Člen
Avatar
Dan:

To chápu, vím kolik kombinací je, ale všiml jsem si že ty rozdíly v čase potřebném k řešení se už u takto jednoduchých algorismů značně liší, čím víc znaků na výběr a znaků v hesle, tím znatelnější rozdíl. Vím, že brute force má svoje meze, nechci přijít na nějaké převratné a zázračné řešení. Rád bych ale něco málo o této problematice odprezentoval ve škole a rád bych to pojal jako analýzu s praktickou ukázkou ke zkoumanému problému. Ptám se tedy na jakékoliv řešení, které je rychlejší než tohle, chci prostě jenom zlepšovat řešení dokud to půjde.

 
Nahoru Odpovědět 20. února 21:40
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.