Повышение эффективности перестановок ArrayList

Question

В качестве небольшого проекта я делаю взломщик «паролей», который просто перебирает все перестановки алфавита, цифр и символов, пока пароль не будет угадан.

Это, конечно, ужасно неэффективно, и я ищу способы сделать это немного быстрее.

Моя идея состоит в том, чтобы перестановки происходили в порядке их размера. Итак, прямо сейчас, оно начнется с первого символа в ArrayList и будет непрерывно добавлять следующий символ, и предположение становится все больше и больше и больше. Так например ..

ArrayList со значениями (A, B, C, D), моя текущая программа создаст перестановки, подобные этой:

(A), (A, B), (A, B, C), (A, B, C, D), (A, B, D), (A, B, D, C)

но более эффективным способом (так как большинство паролей не длиннее 60 символов) было бы пройти через такие перестановки, как этот

(A), (B), (C), (D), (A, B), (A, C), (A, D), (B, A), (B, C) и т. Д.

Вот как выглядит моя текущая программа:

import java.util.ArrayList;
import java.util.Arrays;

public class BruteForce
{

    public static String password = "rand1";

    public static void main(String[] args) {
        ArrayList<Character> characters = new ArrayList<>(Arrays.asList('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', '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', '_', '-', '!', '$'));

        initialPermutations(characters);
    }

    public static void initialPermutations(ArrayList<Character> characters) {
        ArrayList<Character> sub = new ArrayList<>();
        finalPermutations(sub, characters);
    }

    public static void finalPermutations(ArrayList<Character> sub, ArrayList<Character> a) {
        int L = a.size();
        char[] cs = new char[sub.size()];
        for(int i = 0; i < cs.length; i++) {
            cs[i] = sub.get(i);
        }

        String output = new String(cs);

        if(output.equals(password)) {
            System.out.println("The password is " + output);
            System.exit(-1);
        }

        if (L == 0) {
            System.out.println(output);
        }else {

            System.out.println(output);
            for (int i = 0; i < L; i++) {
                ArrayList<Character> ab = new ArrayList<>(sub);
                ab.add(a.get(i));
                ArrayList<Character> bc = new ArrayList<>(a);
                bc.remove(i);
                finalPermutations(ab, bc);
            }
        }
    }
}

Есть идеи, как улучшить этот метод до более «эффективного» (на самом деле не более эффективного, чуть более полезного для более коротких паролей) метода?

Answer 1

public class BruteForce{

    public static String password = "CBA";

    public static Character[] characters = {'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', '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', '_', '-', '!', '$'};

    public static Integer count = 0;

    public static void main(String[] args) {
        int deep = characters.length;//password deep,default value is from one to characters.length
        rmark:
        for (int i = 1; i <= deep; i++) {
            for (int j = 0; j < characters.length; j++) {
                if(test(i,characters[j].toString())) {
                    break rmark;
                }
            }
        }
    }

    public static boolean test(int deep,String parent) {
        if(deep <= 1) {
            count++;
            System.out.println(parent);
            if(parent.equals(password)) {
                System.out.println("after generating "+count+" strings,we find the password!");
                return true;
            }
            return false;
        }else {
            for (int j = 0; j < characters.length; j++) {
                if(test(deep-1,parent+characters[j].toString())) {
                    return true;
                }
            }
        }
        return false;
    }
}

Answer 2

Просто начните считать в базе x, где x - количество символов, которое у вас есть. Например, если вам нужны только цифры, вы должны использовать обычную систему Base 10. Это довольно тривиально, так как что-то вроде 50045 никогда не наступит раньше 5.

Сделать это очень просто, просто возьмите массив, который вначале содержит 0, а затем каждый раз, когда вам нужен новый пароль, увеличивайте первый элемент на единицу. Если оно превышает количество имеющихся у вас символов, просто установите его на ноль и добавьте один к следующему (если это последний, нажмите новый элемент).

Вы можете сделать это немного проще, просто используя простой long (или BigInteger для больших чисел, long не сможет содержать более 10 символов для вашей настройки), а затем получить символы из этого, просто рекурсивно возьмите модуль числа и базу, в которой вы работаете, затем разделите на базу. Это будет выглядеть примерно так:

for (long i = 0; i < maxNum; i++) {
    long temp = i;
    String pass = ""; // Use a StringBuilder here when actually attempting this
    // This would eat your memory faster than 6 chrome tabs
    do {
        pass += charset[temp % base];
        temp /= base;
    }  while (temp > 0);
}