Обзор генетического алгоритма на примере подбора пароля по MD5-хешуПростейший метод подбора пароля по md5-хешу заключатся в переборе всевозможных вариантов парольных фраз и сравнении их md5-хешей с хешом искомого пароля. Для этого составляется словарь всех возможных символов, используемых в пароле, и из него составляются все возможные парольные фразы. Главный минус данного алгоритма заключается в том, что необходимо перебирать все возможные комбинации парольных фраз и неизвестно, на каком шаге md5-хеш очередной комбинации символов совпадет с md5-хешем искомой парольной фразы. Для сокращения времени подбора парольной фразы можно использовать другие методы, например, генетический алгоритм. Суть генетического алгоритма заключается в следующем: задается начальная выборка из случайных парольных фраз — популяция размером N фраз, где каждая фраза шифруется в геном — цепочку, состоящей из генов. Геном представляет собой двоичный код — одномерный массив фиксированной или динамической длинны, где элемент массива — ген принимает значение 1 или 0. Таким образом, изначальная популяция генерируется случайным образом из словаря — набора всех возможных символов, используемых в пароле и представляет собой набор геномов. На первом этапе алгоритма происходит скрещивание геномов - кроссинговер, для этого случайным образом выбираются два генома из популяции, выбирается случайным образом точка деления генома на две или более части, и затем происходит обмен генами между двумя геномами. Способы обмена генами могут быть разнообразными - например, гены, идущие до точки деления первого генома, становятся на место генов во втором геноме, идущих до точки деления. Возможен вариант, когда выбираются несколько точек деления генома - тогда происходит обмен цепочками генов в произвольном или выбранном порядке. В результате скрещивания получаются новые геномы — потомки с новым набором генов, а при расшифровке их — новые парольные фразы. На втором этапе алгоритма происходит мутация — выборочное изменение генов в геноме. Мутации подвергается к% геномов в популяции. Это означает, что случайным образом выбирается к% геномов из новой популяции, состоящей из геномов-предков и геномов-потомков, получившихся на предыдущем этапе, и происходит изменение случайно выбранных генов на противоположные (1 на 0, 0 на 1) с определенной вероятностью, например 10%. Вероятность мутации выбирается в настройках алгоритма. На третьем этапе алгоритма происходит естественный отбор — отсекаются геномы не удовлетворяющие условиям. Для этого вводится функция выживания, которая вычисляет коэффициент выживания генома в популяция. На примере подбора пароля по md5-хешу, это может быть количество совпавших символов в хеше парольной фразы и хеше искомого пароля. На этапе отбора, оставляется N геномов из новой популяции, максимально удовлетворяющих условиям выживания. Далее происходит кроссинговер, мутация и отбор в новой популяции. Алгоритм заканчивает работу, если найдена искомая парольная фраза, т.е. совпали все символы md5-хеша парольной фразы с символами md5-хеша пароля соответственно. Также условиями остановки алгоритма может быть истечение определенного времени на поиск фразы или прохождения алгоритмом определенного количества поколений. В результате работы генетического алгоритма происходит поиск пароля постепенным приближением (идентичностью) - увеличению количества совпадающих символов на соответствующих местах в md5-хэше парольных фраз и md5-хеша искомой фразы. При определенных условиях: правильной подборке размера популяции, метода кроссинговера (скрещивания) и процентном соотношении мутации, эффективность метода подбора пароля по md5-хешу возрастает, а время поиска сокращается.
|