Об одной оптимизации подбора пароля
Решил-таки написать про одну, на мой взгляд, интересную оптимизацию перебора. Постораюсь доступным языком. Вопросы, уточнения - в комменты.
Итак, ситуация: есть архив, на архиве пароль. У нас есть программа, которая генерирует случайные пароли и мы точно знаем, что на архиве стоит пароль полученный этой программой. Задача - подобрать пароль.
В ходе исследования программы становится известно, что длина пароля - 10 символов, алвафит - латинские буквы в нижнем регистре и цифры, то есть 36 символов. Число возможных вариантов пароля - 36^10, то есть порядка 2^51 (если я не ошибся).
Дальнейшее исследование программы показало, что для генерации пароля используется линейный конгруэнтный метод из GNU. Для таких генераторов псевдослучайных чисел (ГПСЧ) число состояний ограничено, в нашем случае - 2^32, что МНОГО меньше 2^51. Теперь следует рассказать о свойствах этих ГПСЧ и привести первый вариант кода.
Каждый следующий результат ГПСЧ производит на основании предыдущего: X_n = X_{n-1} * a + c. То есть, для каждого X_0 будет своя последовательность результатов. Поскольку вычисления производятся на компьютере, имеется ограничение на максимальное значение переменной. В нашем случае это 2^32, то есть возможно всего 2^32 вариантов X_0 и такое же число последовательностей результатов. Из этого следует такой код для решения задачи.
Для каждого i в пределах от 0 до 2^32 выполнить:{
Проинициализировать ГПСЧ с X_0 равным i
Сбросить текущий пароль
Для каждого l в пределах от 0 до 10 выполнить:{//10 - длина пароля
Получить результат ГПСЧ
Добавить результат к текущему паролю
}
Проверить пароль на правильность
}
Очевидно, что число операций "Получить результат ГПСЧ" равно 10*2^32, то есть число_состояний_ГПСЧ*длина_пароля. Порядок - 2^32, что не страшно, но можно оптимизировать еще.
Для использования некоторой гипотезы (о ней позже) нужно было показать, что для данных a и c и любом X_0 наш ГПСЧ примет все возможные состояния, причем в начальное состояние он придет только после того, как побывает во всех остальных. Подобная проверка, я верю, возможна аналитическим путем, но я не знаю как это делать. Поэтому был применен следующий подход: ГПСЧ был проинициализирован с X_0=0, было получено 2^32 результата работы ГПСЧ, значения X_n фиксировались и проверялись: появление X_n, которое уже было, должно происходить не ранее, чем через 2^32 отсчета с момента первого появления. После прохождения полного цикла была проведена проверка, что все возможные X_n были получены.
Кто-то уже мог догадаться, что ГПСЧ для задачи полного перебора состояний достаточно инициализировать только один раз. И в самом деле, поскольку для любого X_0 ГПСЧ пройдет все свои состояния и нам не важно, в каком порядке они будут следовать, достаточно только одной инициализации! Но приведенный выше код при выносе инициализации из цикла работать не будет. Перейдем, наконец, к сути метода!
Представим "дурной" ГПСЧ у которого a и c равны единице. Инициализируем его с X_0 равным нулю и получим такую последовательность: 1, 2, 3, 4, 5, 6... ну и так далее. Допустим, нам нужны пароли из 3 значений. Для X_0=0 это будет "123", для X_0=1 - "234". Тут можно (и нужно!) заметить тот факт, что X_1 прямо получается из X_0 и что результаты для двух последовательных начальных состояний ГПСЧ отличаются только на 1 значение! То есть, нужно как угодно инициализировать ГПСЧ, получить первый пароль, а потом добавлять к паролю только одно новое значение! В нашем примере: первый пароль "123", добавили к нему новое значение - "1234", убрали первое - получили "234" - именно то, что нам и нужно. То есть, на 2 пароля нам понадобилось не 6 результатов ГПСЧ и 2 инициализации, а 4 и 1, соответственно. Поскольку все состояния будут перебраны это то, что нам нужно! И количество результатов ГПСЧ, очевидно, будет равно длина_пароля+число состояний! Сравним с результатами приведенного кода и возрадуемся: от длины пароля время подбора теперь вообще практически не зависит!
Итак, ситуация: есть архив, на архиве пароль. У нас есть программа, которая генерирует случайные пароли и мы точно знаем, что на архиве стоит пароль полученный этой программой. Задача - подобрать пароль.
В ходе исследования программы становится известно, что длина пароля - 10 символов, алвафит - латинские буквы в нижнем регистре и цифры, то есть 36 символов. Число возможных вариантов пароля - 36^10, то есть порядка 2^51 (если я не ошибся).
Дальнейшее исследование программы показало, что для генерации пароля используется линейный конгруэнтный метод из GNU. Для таких генераторов псевдослучайных чисел (ГПСЧ) число состояний ограничено, в нашем случае - 2^32, что МНОГО меньше 2^51. Теперь следует рассказать о свойствах этих ГПСЧ и привести первый вариант кода.
Каждый следующий результат ГПСЧ производит на основании предыдущего: X_n = X_{n-1} * a + c. То есть, для каждого X_0 будет своя последовательность результатов. Поскольку вычисления производятся на компьютере, имеется ограничение на максимальное значение переменной. В нашем случае это 2^32, то есть возможно всего 2^32 вариантов X_0 и такое же число последовательностей результатов. Из этого следует такой код для решения задачи.
Для каждого i в пределах от 0 до 2^32 выполнить:{
Проинициализировать ГПСЧ с X_0 равным i
Сбросить текущий пароль
Для каждого l в пределах от 0 до 10 выполнить:{//10 - длина пароля
Получить результат ГПСЧ
Добавить результат к текущему паролю
}
Проверить пароль на правильность
}
Очевидно, что число операций "Получить результат ГПСЧ" равно 10*2^32, то есть число_состояний_ГПСЧ*длина_пароля. Порядок - 2^32, что не страшно, но можно оптимизировать еще.
Для использования некоторой гипотезы (о ней позже) нужно было показать, что для данных a и c и любом X_0 наш ГПСЧ примет все возможные состояния, причем в начальное состояние он придет только после того, как побывает во всех остальных. Подобная проверка, я верю, возможна аналитическим путем, но я не знаю как это делать. Поэтому был применен следующий подход: ГПСЧ был проинициализирован с X_0=0, было получено 2^32 результата работы ГПСЧ, значения X_n фиксировались и проверялись: появление X_n, которое уже было, должно происходить не ранее, чем через 2^32 отсчета с момента первого появления. После прохождения полного цикла была проведена проверка, что все возможные X_n были получены.
Кто-то уже мог догадаться, что ГПСЧ для задачи полного перебора состояний достаточно инициализировать только один раз. И в самом деле, поскольку для любого X_0 ГПСЧ пройдет все свои состояния и нам не важно, в каком порядке они будут следовать, достаточно только одной инициализации! Но приведенный выше код при выносе инициализации из цикла работать не будет. Перейдем, наконец, к сути метода!
Представим "дурной" ГПСЧ у которого a и c равны единице. Инициализируем его с X_0 равным нулю и получим такую последовательность: 1, 2, 3, 4, 5, 6... ну и так далее. Допустим, нам нужны пароли из 3 значений. Для X_0=0 это будет "123", для X_0=1 - "234". Тут можно (и нужно!) заметить тот факт, что X_1 прямо получается из X_0 и что результаты для двух последовательных начальных состояний ГПСЧ отличаются только на 1 значение! То есть, нужно как угодно инициализировать ГПСЧ, получить первый пароль, а потом добавлять к паролю только одно новое значение! В нашем примере: первый пароль "123", добавили к нему новое значение - "1234", убрали первое - получили "234" - именно то, что нам и нужно. То есть, на 2 пароля нам понадобилось не 6 результатов ГПСЧ и 2 инициализации, а 4 и 1, соответственно. Поскольку все состояния будут перебраны это то, что нам нужно! И количество результатов ГПСЧ, очевидно, будет равно длина_пароля+число состояний! Сравним с результатами приведенного кода и возрадуемся: от длины пароля время подбора теперь вообще практически не зависит!