Появилась интересная идея полного перебора паролей, но не в лексикографическом, а в другом порядке. Хочу услышать чужие комментарии по этой теме.

Для подбора паролей часто используется метод полного перебора всех вариантов, поэтому и советуют использовать как можно более длинные пароли. Чем больше символов, тем сложнее такой пароль будет подобрать. Обычно перебор паролей осуществляется в лексикографическом порядке, начиная с "аааааа", заканчивая "яяяяяя", если мы перебираем шестибуквенный пароль, состоящий, предположительно, из маленьких русских букв.
Пароль из 7 символов подобрать будет уже существенно сложнее, чем из 6. Википедия (http://ru.wikipedia.org/wiki/Брутфорс) приводит пример того, что для подбора пароля из 12 символов в определенных условиях нужно до полутора миллионов лет, в то время как пароль из 7 символов при таких же условиях будет раскрыт не более чем за 9 дней.
Лексикографический порядок перебора паролей не является оптимальным в этом случае. Он, наверное, является даже наихудшим вариантом, которым только стоит воспользоваться для подбора пароля, поскольку он не учитывает факт, что пароли создает человек, который придумывает их в соответствии со своим знанием языка. Человек использует в таких паролях одни буквы чаще других (например, “о” чаще “э”), и одни буквосочетания чаще других (так, "ка" и "ый" является куда более вероятными вариантами в пароле, чем "кк" и "ыэ"). Возникает желание перебирать более "правильные" пароли ранее, чем "неправильные". Так, пароль "нудиратор" хоть и представляет из себя выдуманное слово, которого, скорее всего, нет ни в одном словаре, однако он более вероятен, чем такой длинны "чфхпрцшсч".
Почему пароль "нудиратор" более прост для человека, чем "чфхпрцшсч"? Потому что он удовлетворяет представлению человека о том, что может быть словом в русском языке. На самом деле пароль "нудиратор" не так случаен, как хотелось бы пользователю и в этом его главная уязвимость. Если пароль придуман человеком, то он, скорее всего, поддается общей языковой логике образования слов и содержит в себе избыточную информацию.
Информация о языке общеизвестна и избыточна, поэтому реально пароли имеют меньшую сложность, чем хочется их обладателю. Как определить избыточность информации о языке в пароле? Избавляться от избыточной информации умеют алгоритмы сжатия данных. Выпишем несколько паролей и попробуем сжать их неким алгоритмом сжатия. Тот пароль, что сожмется сильнее других — более прост, чем другие и содержит меньше информации.
В качестве алгоритма архивации я предлагаю использовать модифицированный алгоритм Хаффмана. Классический алгоритм определяет частоту использования букв в слове и перекодирует слово использую для более частых букв меньше бит, чем для более редких. Но распределение букв в слове зависит не только от того, что это за буква, но и от ее позиции в слове и, гораздо больше, от предыдущих букв. Поэтому для сжатия нам будет важна не частота букв в тексте, а отдельно —

частоты первых букв в словах,

частоты вторых букв после буквы 'а',
частоты вторых букв после буквы 'б',
..
частоты вторых букв после буквы 'я'

частоты букв после букв 'аа',
частоты букв после букв 'аб',
..
частоты букв после букв 'яя',

В основном алгоритм будет повторять алгоритм сжатия Хаффмана, только в нем будет использоваться не одно общее дерево, а множество деревьев, которые будут выбираться в зависимости от предыдущих букв. В этих деревья хранится "информация о языке". Для их построения я выбрал "Войну и мир" Толстого.
Любое русское слово этот алгоритм может сжать в битовую последовательность. Эта битовая последовательность уже содержит гораздо меньше закономерностей, чем исходное слово, слабо поддается сжатию, ее мы будем называть чистой информацией о пароле. Если для хранения каждой буквы использовать 5 бит (32 буквы без 'ё'), то слово “нудиратор” занимает 5*9 = 45 бит, однако в сжатом виде он выглядит как “110010100101101010011111101110” — 30 бит вместо 46. Я был сильно удивлен, когда узнал, что мой 7ми символьный пароль ужимается с 35 до 19 бит и требует только 200 тысяч итераций для подбора, то есть всего несколько секунд. Если перед началом перебора сгенерировать слова в лексикографическом порядке, а затем сжать их по длине сжатой последовательности, можно перебирать слова уже в порядке их "естественности". Но я предлагаю еще
более простой вариант — создавать эти слова на лету от более простых к более сложным. Более простые имеют меньшую длину в сжатом виде, так давайте просто подавать на вход деархиватору все возможные последовательности нулей и единиц начиная с длинны 1, постепенно увеличивая длину.
так мы получим
1110000 все
1101000 нат
0101100 что
1011100 сво
0000110 был
...
00001100 было
01111100 это
10000010 гра
01100010 каза
...
111110101101 впеч
011001101101 кбо
010101101101 хоч
110101101101 нашн
101101101101 совы
000011101101 быка
...
001100000111110010 интер
000010000111110010 бойди
110010000111110010 никотра
001010000111110010 такотра
101010000111110010 сеи
011010000111110010 ковсел
111010000111110010 водного
...
101100101011100100110 спрядол
011100101011100100110 мотане
111100101011100100110 выратали
000010101011100100110 брядол
100010101011100100110 ееэлед
001110101011100100110 изворав
011110101011100100110 люденийс
000001101011100100110 улюдит
001001101011100100110 деталаз
111001101011100100110 вратали

В этой последовательности нет повторов и в ней рано или поздно встретится любое слово. Так, 541901334-ым номером будет сгенерировано "нудиратор", в то время как в лексикографеческом порядке его номер 16086012579313. Таким образом перебор потребует в 30 тысяч (более точно 29684) раз меньше итераций. При скорости 100000 паролей в секунду 9ти символьный пароль "нудиратор" будет подобран за 90 минут. Перебор в лексикографическом порядке при такой скорости займет более 5 лет. Один из проверенных мною 12 символьных паролей имел сжатую длину 33 бита, номер 4.5 миллиардный по списку, соответственно, для его нахождения при аналогичной скорости понадобится примерно 12 с половиной часов, а совсем не миллион лет.

Описание приложения
Приложение к статье находится по ссылке http://shutov.org.ru/bruteforcer.zip
dict/rus.txt – “Война и Мир” Л.Н. Толстого
dict/eng.txt — “Война и Мир” Л.Н. Толстого, перевод на английский язык
bruteforcer_eng.exe – программа, скомпилированная для английского языка
bruteforcer_rus.exe – программа, скомпилированная для русского языка
main.cpp – исходный текст программы
test.sln, test.vcproj – файлы проекта Microsoft Visual Studio 2003

bruteforcer_rus.exe и bruteforcer_eng.exe принимает 1 входной параметр. Если это число, то программа генерирует данное число слов в порядке “логичности” и пишет их в output. Если это слово, то сначала вычисляется его сжатая длина, а после запускается перебор и в итоге вычисляется порядковый номер этого слова, равный количеству итераций нужных для подбора этого пароля. Так как русская кодировка консоли не совпадает со стандартной Windows 1251, в русской версии программы вывод русских слов на экран происходит некорректно, поэтому выводить результат программы лучше не на экран, а в файл. Например:
bruteforcer_rus.exe нудиратор >file.txt