Алгоритм, необходимый для генерации комбинаций сдвинутых символов

Question

Я знаю точную последовательность и длину пароля моего раздела TrueCrypt, но я не могу вспомнить, какие символы были сдвинуты вверх с помощью клавиши Shift. Я написал Perl-скрипт (например, CrackTC), который просто пробует все пароли из файла, но я ищу алгоритм для быстрой генерации файла паролей. Пароль состоит из 42 символов, поэтому любые советы будут вам полезны.

Я понял, что у меня будут только сдвинутые цифры и знаки препинания, поэтому нужно изменить только 17 символов.

Обратите внимание, что это не домашнее задание.

Answer 1

Быстрый скрипт на Python:

def isShiftable(c):
    return not c in "123456789"

def generate(str, i=0):
    if len(str) <= i:
        print "".join(str)
    else:
        if isShiftable(str[i]):
            str[i]=str[i].upper()
            generate(str, i+1)
            str[i]=str[i].lower()
            generate(str, i+1)
        else:
            generate(str, i+1)

generate(list("testit123"))

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

Для 17 перемещаемых символов должно быть 131072 возможностей. Кроме того, вам нужно определить свою собственную "верхнюю" / "нижнюю" функцию для смещения знаков препинания.

Answer 2

Поскольку каждый символ может быть верхним или нижним, это эквивалентно одному биту. У вас есть 42 бита. Посчитайте в двоичном формате и установите символ в верхний или нижний регистр в соответствии с шаблоном двоичных битов. 2 до степени 42 это очень большое число! Слишком большой, чтобы найти грубой силой! Удачи!

Answer 3

Предполагая, что вам нужно попробовать все комбинации, и что каждая попытка пароля отделяется одним символом, файл пароля для всех возможных прописных букв 42-символьного пароля будет иметь длину 189 терабайт. Вы, вероятно, не хотите работать напрямую из файла.

Алгоритм, который я выбрал бы, является двоичным алгоритмом подсчета, но вместо переключения одного бита, переключайте заглавные буквы одного символа. Я бы настоятельно рекомендовал сузить пул с эмпирическими правилами, которые вы помните (например: определенно было более 5 прописных и менее 40 прописных).

Answer 4

Не совсем ответ, но это может уменьшить ваше пространство поиска:

• Минимум и максимум заглавных букв (может быть 4 и 10)
• Минимальная и максимальная последовательность прописных букв (также может быть 1 и 1)
• Минимальная и максимальная последовательность строчных букв (может быть 2 и 15)
• Некоторые комбинации более вероятны, чем другие, и должны быть проверены в первую очередь. Например, групповые комбинации по максимальной последовательности заглавных букв и сначала проверьте те из них, у которых минимальное значение.

Answer 5

42 буквенный пароль, и вы знаете буквы, то есть 2^41 (то есть: 2 199 023 255 552) уникальные комбинации. Если бы вы могли проверить 10 м из них за 1 секунду, то вы могли бы перебором - и это заняло бы по крайней мере: 61 час 5 минут 2 секунды.

Скорее всего, вам не придется много работать. Пусть х будет количеством заглавных букв:

• Если у тебя есть 7 > x заглавные буквы: (42!)/(6! 36!)+(42!)/(5! 37!)+(42!)/(4! 38!)+(42!)/(3! 39!)+(42!)/(2! 40!)+(42!)/(1! 41!) = 6 220 767 комбинации.
• Если у тебя есть 6 < x < 9 заглавные буквы: (42!)/(8! 34!)+(42!)/(7! 35!) = 145 008 513 комбинации.

Если вы можете автоматизировать процесс проверки и проверить 2000 элементов в секунду, то в худшем случае:

• Если у тебя есть 7 > x заглавные буквы, это займет: 51,84 минут
• Если у тебя есть 6 < x < 9 заглавные буквы: 20,14 часа

Скорее всего, вам нужен какой-то особый алгоритм перестановки для эффективного поиска уникальных элементов. Это довольно сложная проблема, но я не вижу другого пути, так как итерации по 2 ^ 41 элементам - чокнутые.