singlepost

Помогите создать алгоритм. << На главную или назад  

Дорго времени суток.
Нужна помощь в составлении алгоритма.
Требуется генерировать строки, содержащие символы A-Z,1-0.Строки, начиная с одного символа до 32. Требуется сгенерировать строку, проверить её на соответсвие определенному условию. В случае не соответсвии условию, сгенерировать следующую и проверить снова. Нужно перебрать все возможные строки заданной длины и содержащие заданые символы.

51 ответов в теме “Помогите создать алгоритм.”

  1. 25
    Павел Гордый ответил:

    Ох и много всего наговорили!

    Тут нужен простой перебор, просто то как он должен работать. Я понял что неважно чколько ЭТО будет работать.

    Для реальных задач (например паролей) вполне хватает словарей!

  2. 24
    Антон Кононов ответил:

    одних тока строк будет сгенерено сколько? для 10-символьного пароля при 36 буквах получаем 36 в 10 степени вариантов :)

  3. 23
    Владимир Нннннн ответил:

    >#7 Почему-то статей по оптимизации брутфорса нашел достаточно, а вот о самом алгоритме подбора нигде не слова.
    Это пиздец. Оптимизируется как алгоритм так и реализация перебора, причем жестко привязаны эти вещи друг к другу. 32 символа – из стандартных алгоритмов на md5 похоже. вот и думай как лучше реализовать исходя из тех данных что у тебя есть.

    >Все, смог реализовать на С, с помощью рекурсивной функции. Теперь осталось немного оптимизировать под динамически меняющийся размер строки. Всем спасибо!
    А ты уверен что компилятор тебе эту рекурсию реализовал через циклы, а не через обычный вызов со стеком?Если не уверен – прога очень интересно будет себя вести ;) Все врут! Даже компиляторы! Дизассемблер в руки и смотри что тебе наворотил компилер, либо самостоятельно через циклы.

  4. 22
    Нгамдкхе Кверос ответил:

    сложность подбора хеша зависит от битности хеша и вычислительной сложности функции, если взять банально младший байт суммы байт строки то быстро должно подобрать что для случайного алгоритма что для перебора. если взять crc16 уже 64к варианта вот мат ожидание экспериментов будет лежать где-то в районе 64к расчётов что на нынешних процах вполне подбирается. вот с 4 байтовым хешем начнутся заметные тормоза. для 32-ух байт можно курить бамбук.
    но это же лаба, там просто хеш будет фиговый вот и всё.

  5. 21
    Павел Гордый ответил:

    Где проблема?

  6. 20
    Алексей Крикунов ответил:

    Да, именно такой алгоритм. Пока ещё есть проблемы с длинной массива (строки), но это уже другая проблема.

  7. 19
    Антон Кононов ответил:

    рекурсию? типа вот так:

    Функция ДайСимвол(уровень, строкаНаВходе)
    для счетчик=0 по количествоРазныхБукв-1 Цикл
    Если уровень=последнийУровень Тогда ПроверитьХэш(строкаНаВходе+ПолучитьСимволПоНомеру(счетчик));
    Иначе
    ДайСимвол(уровень+1, строкаНаВходе+ПолучитьСимволПоНомеру(счетчик));
    КонецЕсли;
    КонецЦикла;
    КонецФункции;

    Запуск этой херни вот так:
    последнийУровень=10; // это длина пароля
    количествоРазныхБукв = 36; // это сколько символов используется для пароля (10 цифр+26 букв, например)
    ДайСимвол(0, ""); // передаем ноль и пустую строку – это запуск

    Примечание:
    функция ПолучитьСимволПоНомеру – возвращает символ по номеру, где номер 0 – это 0, 1=1,…,9=9,А=10,B=11,…,Z=36

    Переберет все пароли заданной длины и все их засунет в ПроверитьХэш()

  8. 18
    Сергей Старовой ответил:

    Собсна получаем в итоге
    36 +36^2 +36^3 +36^4 +… +36^32 возможных вариантов строк…

    Может стоит покопать в сторону более продуктивного алгоритма поиска коллизий у данной хешфункции? )

  9. 17
    Андрей Щипцов ответил:

    да дело не в результате, а в алгоритме, как я понял…
    что касается автора: первым делом надо исключить повторы

  10. 16
    Алексей Крикунов ответил:

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

  11. 15
    Павел Гордый ответил:

    Но это будет НЕРЕАЛЬНО ДОЛГО!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    Иначе вскрыли давно хэши всех паролей до 32 символов!

  12. 14
    Павел Гордый ответил:

    Походу, полностью работоспособный. На Перле.
    Осталось только понять что вычислять для строки)))

    #!/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);

  13. 13
    Алексей Крикунов ответил:

    #8 С генерацией отдельного символа проблем не возникло. Возникла другая проблема – генерация строки этих символов.
    Появились идейки копать в сторону рекурсии…

  14. 12
    Алексей Вишняков ответил:

    Андрей [Sn0Xx] Щипцов Не забудь про цифры
    И не совсем понятно как твой алгоритм будет делать строки длиной меньше 32 символов?

  15. 11
    Андрей Щипцов ответил:

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

  16. 10
    Андрей Щипцов ответил:

    Алексей Aka~Android Вишняков, я просто показал как сгенерить числа или символ вот и все… а что касается строки, то тут и размером строки надо оперировать… т.е. пробегать по символам строки и присваивать свой сгенерированный символ

  17. 9
    Андрей Щипцов ответил:

    Алексей 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-строка))
    думаю принцип понятен…

  18. 8
    Алексей Крикунов ответил:

    #6 Эм…. а где тут автоматизация процесса? Если нумеровать все строки от 1го до даже 10 символов уйдет очень-очень много времени.
    #7 Почему-то статей по оптимизации брутфорса нашелдостаточно, а вот о самом алгоритме подбора нигде не слова.

  19. 7
    Андрей Щипцов ответил:

    кстати, если ты на си пишешь, если на паскале, то там надо вызывать функцию.. вроде ord, если я не ошибаюсь)) пьяненький просто))

  20. 6
    Андрей Щипцов ответил:

    а есть лимит по времени?))) в любом случае, как я понял, генерировать надо…

  21. 5
    Алексей Крикунов ответил:

    #3-Ага, они самые. В универе дали задание написать брутфорсер Хэшей, при известном алгоритме получения ХЭШа. По времени ограничений не давали). Другого варианта, как перебор строк просто не вижу(

    #2- Есл бы строки состояли бы из одного символа, проблемы бы не было.

  22. 4
    Алексей Вишняков ответил:

    Ну пронумеруй все буквы и перебирай их в цикле от 0 до 36^32
    тогда
    0 = A
    1 = B

    36 = AA
    37 = AB
    и так далее

  23. 3
    Павел Гордый ответил:

    на перле 10 минут писать
    много (очень много) времени работать будет.
    На что проверять-то надо?
    Только проверку во время генерации, иначе оперативки пережрёт всё это многообразие хранить!

  24. 2
    Андрей Щипцов ответил:

    дык генерируй число от A до Z или 1 или 0 и пиши в строку…
    или ты генерируешь из всех символов и проверяешь на условие?

  25. 1
    Павел Гордый ответил:

    Интерсно сколько это времени займёт? Ты пароли вскрываешь? :)

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.