Рассчитать все комбинации данного набора символов, для сравнения грубой силы? - PullRequest
Новая
       5

Рассчитать все комбинации данного набора символов, для сравнения грубой силы?

2 голосов
/ 30 апреля 2011

Практикуя многопоточность, я хотел просто создать приложение, которое могло бы вычислять все возможные комбинации набора символов (т. Е. Взломать / сопоставлять грубой силой) и распределять работу между потоками, чтобы действительно измерить и собственными глазами увидеть, какПотоки могут влиять на время работы алгоритма в разных системах.

Алгоритм для вычисления этого до сих пор был для меня большой проблемой.В недавнем потоке ( Каким был бы эффективный способ добавить многопоточность к этому простому алгоритму? ), я, кажется, понял, что мне нужно было сделать (легко передать определенные части каждого диапазона символов для распределения работы), хотяалгоритм просто не работал, и я не достаточно понимал сложность, чтобы исправить это в моем приложении.

Простым итеративным способом, как я мог вычислить каждую комбинацию данного набора символов с определеннымдлина (т. е. 5 в длину?)

в примере: 

unsigned char range[] = "abcdefghijklmnopqrstuvwxyz0123456789";
brute_force(range, len); //character set, length of string to compute all combinations of
//...

Я был бы очень благодарен, чтобы снять некоторое напряжение при поиске подходящих концепций для этого.

Ответы [ 2 ]

2 голосов
/ 30 апреля 2011

Один подход: void brute_force(String range, int len) { for (int i = 0; i < range.length(); ++i) { final String x = "" + range.charAt(i); Thread t = new Thread(){ public void run() { brute_force(x, range[].replace(x, ""), len); }; }; t.start(); } }

Где brute_force(String, String, int) будет генерировать комбинации.

0 голосов
/ 30 апреля 2011

итеративный брутфорс для 5 элементов: 

for c1 in set {
for c2 in set {
for c3 in set {
for c4 in set {
for c5 in set {
    test(c1,c2,c3,c4,c5);
}}}}}

Чтобы разделить работу между потоками, просто создайте отдельную «начальную часть» для каждого потока. Таким образом, первая нить обрабатывает все палаты, начинающиеся с «а», вторая - «б» и так далее. (Если у вас более 26 потоков, то первый получает 'aa', второй 'ab' и так далее ...

Если вам нужно решение, которое лучше масштабируется по длине, то лучше сформулировать проблему рекурсивно (при желании это можно преобразовать в версию, используя вместо этого явные стеки): 

unsigned char charset = /**/
unsigned int setsize = sizeof charset;

bool test(combination);   

function bruteforce(output, n){
  /* Goes through all character combinations of length n,
     writing them in output and calling test on them afterwards */
  if(n == 0){
    test(output);
  }else{
    for(int i=0; i<setsize; i++){
      output[n-1] = charset[i];
      bruteforce(output, n-1);
    }
  }
}

unsigned char my_output[final_length];
bruteforce(my_output, final_length);
...