Автор: Archer

Тут поговорим случайных паролях с точки зрения математики. Конкретнее - как количество возможных вариантов пароля зависит от его длины и размерности используемого при генерации "алфавита". Тема не новая, но ни в одной статье на эту тему (во всяком случае из тех, что я читал) вопрос не рассматривается достаточно подробно. Частенько просто отделываются утверждением, что возможных вариантов паролей "огромное количество". Но это понятие растяжимое - современный ПК тоже выполняет "огромное количество" операций в секунду. Так сколько ему понадобится времени, чтобы при переборе вариантов добраться до нашего пароля? Особо продвинутые авторы пугают читателя огромными числами. Не будем верить на слово - если мы пишем программу, в которой предусмотрены пароли, надо самим уметь оценить их надежность. Не вдаваясь в строгое математическое доказательство, посмотрим, откуда берутся эти зверские числа и как их рассчитать для каждого конкретного случая.

Давайте договоримся, что мы имеем алфавит из n возможных символов, а наш пароль k символов в длину. Надо узнать, сколько вариантов пароля может быть в принципе, и дополнительно посмотрим, сколько будет вариантов паролей из неповторяющихся символов - иногда встречаются утверждения, что такой пароль лучше. Не ручаюсь за точность терминологии, лень было искать:), просто для себя назовем такие пароли соответственно "обычными" и "уникальными".

Обычные пароли

Как мы только что договорились, обычными называем пароли, которые могут содержать повторяющиеся символы. То есть это полное количество комбинаций длиной k, которые мы можем составить из n элементов. Слишком сильно в математику вдаваться не будем, а рассмотрим несколько простых примеров. Начнем как положено, с самого начала.

Пример 1: У нас есть элементы "А" и "В". Сколько комбинаций длиной 1 можно из них сотворить? Очевидно, две. Попутно отмечаем на будущее, что это равно nk.

Пример 2: У нас есть элементы "А", "В" и "С". Сколько имеем комбинаций длиной в 2 символа? Давайте считать. Перебираем по принципу "каждый с каждым". Получаем "АА", "АВ", "АС", "ВА", "ВВ", "ВС", "СА", "СВ", "СС", всего 9. Занятное совпадение - снова nk :)

Дальше предлагаю просто принять на веру, что их nk, поскольку так оно и есть, строго доказывать будет длинновато. Интересующиеся могут обратиться к разделу алгебры "Комбинаторика". Это называется размещения с повторениями. Рассмотрим более практический пример. Число букв английского алфавита 26. Составляем всевозможные пароли длиной в 9 символов. Их у нас 269=5 429 503 678 976 штук. Для начала неплохо:)

Уникальные пароли

Снова вернемся к примерам. Уникальные пароли не содержат повторяющихся символов, потому первый пример оставляет нам оба варианта. Из второго примера мы должны вычеркнуть "АА", "ВВ" и "СС", то есть имеем шесть случаев. В математике это называется размещениями. Количество размещений (без повторения) рассчитываем по формуле n*(n-1)*(n-2)*...*(n-k+1) = n! / (n-k)! (что такое факториал, надеюсь, все помнят). Сразу видим, что для наших примеров получаем соответственно 2 и 6, то есть все правильно. Снова тот же более практический пример - на этот раз имеем 26! / (26 - 9)! = 26! / 17! = 1 133 836 704 000 вариантов. Даже без "куркулятора" понятно, насколько мы сузили диапазон возможных паролей наложением условия неповторяемости символов. Это к вопросу об использовании "уникальных" паролей:)

Реальный пример

Давайте перейдем к практическим вещам. Например, рассмотрим пароли MS Office. Они могут быть до 15 знаков в длину, включать буквы (не только английские, но и языков локализации), цифры, а также специальные символы ("{", "#", "!" и т.п.). Кроме того, учитывается регистр символов, то есть английских букв реально можем использовать 52. Надо отметить, что MS Office ничего не имеет против пароля, состоящего из букв разных языков, но я бы не стал такого делать - легко самому запутаться. Потому прикидываем для английского - 52 буквы, 10 цифр, еще пару десятков надо накинуть на спецсимволы... Для круглого счета определим наш алфавит в 80 символов. Максимальное количество паролей максимальной длины при таком допущении будет примерно 3,5 * 1028. А если не допускать повторения символов? 8,6 * 1027. Снова вариантов в несколько раз меньше.

Зависимости

Попробуем ответить на самый интересный вопрос - как количество вариантов зависит от размерности алфавита и длины пароля? И что вообще важнее - увеличивать размерность алфавита или использовать пароль максимальной длины? Формулы этих зависимостей мы уже получили, для наглядности теперь нарисуем пару картинок. Снова берем 80 символов алфавита и 15 символов пароля.

Рисунок 1: Зависимость количества "обычных" вариантов от размерности алфавита и длины пароля.	Рисунок 2: Зависимость количества "уникальных" вариантов от размерности алфавита и длины пароля.

К сожалению, "рисовалка" немного не дотягивает до максимальных значений, но все закономерности налицо. На мой взгляд, рисунки показывают, что минимально приемлимый пароль имеет от 10 символов в длину и от 25 символов использованного алфавита, и что количество вариантов сильнее зависит от размерности алфавита.

Так сколько же компьютеру понадобится времени для взлома нашего документа? Давайте оценим. Специально заходил на сайты нескольких утилит для "восстановления забытых паролей", но сведений о скорости перебора там благоразумно не приводилось:) Единственное, что удалось откопать в сети - упоминание о том, что одна из таких программ, написанная несколько лет назад, перебирает 85000 вариантов в секунду на Pentium III. В алгоритмах с тех пор вряд ли что-то существенно изменилось. Давайте введем поправку на возросшие компьютерные мощности, например, помножим на пять. Для 9-ти значного пароля и для алфавита в 26 символов получится около 145 суток. Это для обычных паролей. Для паролей из неповторяющихся символов получается ровно месяц. Конечно, эти расуждения относятся к взлому пароля прямым перебором вариантов - относительно иных способов не берусь подсчитать.