Многопоточный алгоритм взлома паролей

Question

Я создал многопоточную программу на C ++, чтобы взламывать пароли длиной 7 символов (только символы нижнего регистра), используя алгоритм перебора.

Мой алгоритм в основном состоит из 7 вложенных циклов for, идущих от a до z и проверяющих каждую возможную комбинацию.

Прямо сейчас я делю свою работу следующим образом:
Если у меня 3 рабочих темы,
Поток 1: от xxxxxx до ixxxxxx
Поток 2: от jxxxxxx до rxxxxxx
Тема 3: от sxxxxxx до zxxxxxx

Таким образом, 3 потока будут продолжать и циклически повторяться, пока не найдут совпадение.

Основной поток будет ожидать возврата первого потока.

Мой вопрос: это лучший способ разделить работу между моими потоками? У вас есть идеи о том, как я мог бы быть более эффективным?

Кроме того, даже если это не основная часть моего допроса, можете ли вы придумать лучший способ, чем итерация 7 for-loop?

(Обратите внимание, что эта программа предназначена для школьного проекта, а не для взлома паролей)

Answer 1

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

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

В шаблоне производитель / потребитель есть некоторые издержки, но он более гибкий.

Answer 2

Я бы взглянул на intel TBB

Я бы использовал конструкцию parallel_for на внешней петле и имел бы атомную переменную, чтобы сигнализировать о ее обнаружении.

Это довольно тривиально, используяlambdas.

tbb::blocked_range<char> rng('a', 'z');
tbb::parallel_for(rng, [&](tbb::blocked_range<char> rng){ 
     for(char a=rng.begin(); a!=rng.end(); ++a)
     {
         //a is your top level character
     }
}); 

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

Answer 3

Вы должны использовать шаблон потребителя производителя.Наличие (потокобезопасной) очереди для создания кандидата на пароль и потребительских потоков. Это должно быть более гибким.

В создании паролей нет ничего плохого в вашем методе, но это может быть утомительно с более длинным паролем.

Вы можете использовать рекурсивную схему для ее создания.или итеративная схема с одним циклом, символы az в таблице ascii являются последовательными, поэтому вы можете использовать преобразование base 26 для получения вашего кандидата.