:: Игры Разума
Подбор пароля перебором значений
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
Собственно, вопрос навеяла вот эта тема

SYS(2007)

Сформулирую задачу так:

====================
Есть "слово" из 30 символов. Каждая "буква" этого слова может быть: цифрой, буквой русского алфавита, буквой латинского алфавита. Регистр букв имеет значение.

"Слово" было "зашифровано" через некий известный алгоритм. Результат этого "шифрования" известен.

Необходимо подобрать все возможные варианты исходного не зашифрованного пароля.
====================

Собственно, способ шифрования значения не имеет. Просто надо как-то исхитрится найти перебором заранее известное "слово".

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

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

* Список используемых (доступных) символов
LOCAL lcAvailable
lcAvailable = "0123456789"+;
"abcdefghijklmnopqrstuvwxyz"+;
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"+;
"абвгдеёжзийклмнопрстуфхцчшщъыьэюя"+;
"АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"
* Количество "букв" в пароле
#DEFINE MAX_LETTER 30
* Генерация пароля
LOCAL lnNext, lnI, lnPassword
RAND(-1)
lnPassword = ""
FOR m.lnI = 1 TO MAX_LETTER
lnNext = CEILING(RAND() * LEN(m.lcAvailable))
if m.lnNext = 0
m.lnNext = 1
endif
lnPassword = m.lnPassword + SubStr(m.lcAvailable,m.lnNext,1)
ENDFOR
?m.lnPassword
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
А может все-таки про алгоритм что-то известно? А то уже с элементарным алгоритмом, который возращает 0, если количество ненулевых битов в строке четно, и 1 - если нечетно, будет трудно справиться. Он должен будет вернуть 2^209 значений. Насколько мне помнится, число элементарных частиц в видимой части вселенной меньше. Написать перебор можно, но Солнце погаснет раньше, чем мы дождемся ответа.
Если же рассматривать задачу чисто теоретически, как организацию перебора, то решение приаттачено (не привел тут, чтобы и другие могли бы получить удовольствие от решения)
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
Про пароль - это так, к слову. Меня, конечно интересовал именно сам алгоритм перебора при заранее не известном количестве символов в слове и количестве допустимых значений в каждой букве. И именно универсальный алгоритм. Просто "пароль" - наглядно поясняет что именно нужно.

Недостаток решения с рекурсией - это физический предел уровня вложенности. В данном случае, ограничением является количество букв в слове.

Разумеется, в VFP9 он даже по умолчанию достаточно большой (Maximum # of nested DO calls = 128). И можно увеличить до 64`000. Тем не менее, лично мне не кажется, что это можно отнести к универсальному решению. Как частное решение - да, сгодится.
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Что-то мне кажется, что если длина слова 128, даже если различных символов всего 2, ни на каком современном компьютере ни за какое разумое время их все равно перебрать нельзя никаким способом. Ну ладно, подумаю, как можно без рекурсии.
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
ssa

Сообщений: 12999
Откуда: Москва
Дата регистрации: 23.03.2005
Эх, ребята... Сия задача давным давно решена.
Наводка - системы счисления. Владимир Максимов описал цыфры системы с основанием 69.


------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Вот еще вариант, без рекурсии.
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Да, есть такая наука - комбинаторика
Существуют фомулы, позволяющие найти количество вариантов.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive
Re: Подбор пароля перебором значений
Igor Korolyov
Автор

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi Влад!

Да, и после беглого ознакомления с этими формулами становится понятно почему Леонид говорит о бесперспективности подобного перебора. Brute force attack это последнее оружие взломщика - так сказать шаг отчаяния


------------------
WBR, Igor
Ratings: 0 negative/0 positive


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

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика