Дорго времени суток.
Нужна помощь в составлении алгоритма.
Требуется генерировать строки, содержащие символы A-Z,1-0.Строки, начиная с одного символа до 32. Требуется сгенерировать строку, проверить её на соответсвие определенному условию. В случае не соответсвии условию, сгенерировать следующую и проверить снова. Нужно перебрать все возможные строки заданной длины и содержащие заданые символы.
25 сентября 2009 в 18:01
Ох и много всего наговорили!
Тут нужен простой перебор, просто то как он должен работать. Я понял что неважно чколько ЭТО будет работать.
Для реальных задач (например паролей) вполне хватает словарей!
25 сентября 2009 в 16:02
одних тока строк будет сгенерено сколько? для 10-символьного пароля при 36 буквах получаем 36 в 10 степени вариантов
25 сентября 2009 в 15:05
>#7 Почему-то статей по оптимизации брутфорса нашел достаточно, а вот о самом алгоритме подбора нигде не слова.
Это пиздец. Оптимизируется как алгоритм так и реализация перебора, причем жестко привязаны эти вещи друг к другу. 32 символа – из стандартных алгоритмов на md5 похоже. вот и думай как лучше реализовать исходя из тех данных что у тебя есть.
>Все, смог реализовать на С, с помощью рекурсивной функции. Теперь осталось немного оптимизировать под динамически меняющийся размер строки. Всем спасибо!
Все врут! Даже компиляторы! Дизассемблер в руки и смотри что тебе наворотил компилер, либо самостоятельно через циклы.
А ты уверен что компилятор тебе эту рекурсию реализовал через циклы, а не через обычный вызов со стеком?Если не уверен – прога очень интересно будет себя вести
25 сентября 2009 в 15:02
сложность подбора хеша зависит от битности хеша и вычислительной сложности функции, если взять банально младший байт суммы байт строки то быстро должно подобрать что для случайного алгоритма что для перебора. если взять crc16 уже 64к варианта вот мат ожидание экспериментов будет лежать где-то в районе 64к расчётов что на нынешних процах вполне подбирается. вот с 4 байтовым хешем начнутся заметные тормоза. для 32-ух байт можно курить бамбук.
но это же лаба, там просто хеш будет фиговый вот и всё.
25 сентября 2009 в 15:01
Где проблема?
25 сентября 2009 в 14:02
Да, именно такой алгоритм. Пока ещё есть проблемы с длинной массива (строки), но это уже другая проблема.
25 сентября 2009 в 8:00
рекурсию? типа вот так:
Функция ДайСимвол(уровень, строкаНаВходе)
для счетчик=0 по количествоРазныхБукв-1 Цикл
Если уровень=последнийУровень Тогда ПроверитьХэш(строкаНаВходе+ПолучитьСимволПоНомеру(счетчик));
Иначе
ДайСимвол(уровень+1, строкаНаВходе+ПолучитьСимволПоНомеру(счетчик));
КонецЕсли;
КонецЦикла;
КонецФункции;
Запуск этой херни вот так:
последнийУровень=10; // это длина пароля
количествоРазныхБукв = 36; // это сколько символов используется для пароля (10 цифр+26 букв, например)
ДайСимвол(0, ""); // передаем ноль и пустую строку – это запуск
Примечание:
функция ПолучитьСимволПоНомеру – возвращает символ по номеру, где номер 0 – это 0, 1=1,…,9=9,А=10,B=11,…,Z=36
Переберет все пароли заданной длины и все их засунет в ПроверитьХэш()
24 сентября 2009 в 23:05
Собсна получаем в итоге
36 +36^2 +36^3 +36^4 +… +36^32 возможных вариантов строк…
Может стоит покопать в сторону более продуктивного алгоритма поиска коллизий у данной хешфункции? )
24 сентября 2009 в 23:05
да дело не в результате, а в алгоритме, как я понял…
что касается автора: первым делом надо исключить повторы
24 сентября 2009 в 23:01
Все, смог реализовать на С, с помощью рекурсивной функции. Теперь осталось немного оптимизировать под динамически меняющийся размер строки. Всем спасибо!
24 сентября 2009 в 22:05
Но это будет НЕРЕАЛЬНО ДОЛГО!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Иначе вскрыли давно хэши всех паролей до 32 символов!
24 сентября 2009 в 22:04
Походу, полностью работоспособный. На Перле.
Осталось только понять что вычислять для строки)))
#!/usr/bin/perl
use strict;
my @array = ('a'..'z');
push @array, (0..9); #создание масива всех значений
my $result = &search(0,'');#Первичный вызов
print "result: $result\n";
sub search
{
my ($num,$str) = @_;
return 0 if ($num > 32);
my $ok = 0;
my $local_num = $num + 1;
foreach my $dig (@array)
{
my $line = $str.$dig;
my $res = &hash_algo($line);
$res = &search($local_num,$line) unless $res;
return $res if $res;
}
return 0;
}
sub hash_algo #Алгоритм проверки. Что тут должно быть незнаю. В данном случае возвращет false, или для теста true при заданном значении
{
my $str = shift;
warn "$str\n";
return $str if ($str eq 'aaaaaaaaaaaaaaaaaaaaaaaaaaaqaabc');
return 0;
}
exit(0);
24 сентября 2009 в 22:03
#8 С генерацией отдельного символа проблем не возникло. Возникла другая проблема – генерация строки этих символов.
Появились идейки копать в сторону рекурсии…
24 сентября 2009 в 22:03
Андрей [Sn0Xx] Щипцов Не забудь про цифры
И не совсем понятно как твой алгоритм будет делать строки длиной меньше 32 символов?
24 сентября 2009 в 22:03
ты думаешь генерировать строку до тех пор, пока не будет совпадения?))) если так, то удачи… хэш код подобрать очень сложно… не для наших компов….
Хотя алгоритм(тупо генерации, для препода) – то потянет, рекурсию тут использовать, имхо,смысла нету… можно просто бесконечный цикл
24 сентября 2009 в 22:03
Алексей Aka~Android Вишняков, я просто показал как сгенерить числа или символ вот и все… а что касается строки, то тут и размером строки надо оперировать… т.е. пробегать по символам строки и присваивать свой сгенерированный символ
24 сентября 2009 в 22:02
Алексей Aka~Android Вишняков, не морочь человеку голову, у каждого символа есть ASCII код…. 'A' = 65, Z = '90'. автор, генерируй такие символы…
ну что нить типа так…
int gen(int min, int max)
{
тут генерируешь число
}
и в проге:
k = 0;
for (int i := 0; i < 32; i++)
{
if (gen(65,92) == 91) s[i] = 0; else
if (gen(65,92) == 92) s[i] = 1; else
s[i] = gen(65,92);
}
ну что – то типа того))) там разберешься, s-строка))
думаю принцип понятен…
24 сентября 2009 в 22:02
#6 Эм…. а где тут автоматизация процесса? Если нумеровать все строки от 1го до даже 10 символов уйдет очень-очень много времени.
#7 Почему-то статей по оптимизации брутфорса нашелдостаточно, а вот о самом алгоритме подбора нигде не слова.
24 сентября 2009 в 22:02
кстати, если ты на си пишешь, если на паскале, то там надо вызывать функцию.. вроде ord, если я не ошибаюсь)) пьяненький просто))
24 сентября 2009 в 22:01
а есть лимит по времени?))) в любом случае, как я понял, генерировать надо…
24 сентября 2009 в 22:01
#3-Ага, они самые. В универе дали задание написать брутфорсер Хэшей, при известном алгоритме получения ХЭШа. По времени ограничений не давали). Другого варианта, как перебор строк просто не вижу(
#2- Есл бы строки состояли бы из одного символа, проблемы бы не было.
24 сентября 2009 в 22:01
Ну пронумеруй все буквы и перебирай их в цикле от 0 до 36^32
тогда
0 = A
1 = B
…
36 = AA
37 = AB
и так далее
24 сентября 2009 в 22:01
на перле 10 минут писать
много (очень много) времени работать будет.
На что проверять-то надо?
Только проверку во время генерации, иначе оперативки пережрёт всё это многообразие хранить!
24 сентября 2009 в 22:00
дык генерируй число от A до Z или 1 или 0 и пиши в строку…
или ты генерируешь из всех символов и проверяешь на условие?
24 сентября 2009 в 22:00
Интерсно сколько это времени займёт? Ты пароли вскрываешь?