випадкові паролі

Delphi. Синтаксис. паролі

Давайте домовимося, що ми маємо алфавіт з 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 знаків в довжину, включати літери (не тільки англійські, але і мов локалізації), цифри, а також спеціальні символи ( "

Спробуємо відповісти на найцікавіше запитання - як кількість варіантів залежить від розмірності алфавіту і довжини пароля? І що взагалі важливіше - збільшувати розмірність алфавіту або використовувати пароль максимальної довжини? Формули цих залежностей ми вже отримали, для наочності тепер намалюємо пару картинок. Знову беремо 80 символів алфавіту і 15 символів пароля.

Малюнок 1: Залежність кількості "звичайних" варіантів від розмірності алфавіту і довжини пароля.

Малюнок 2: Залежність кількості "унікальних" варіантів від розмірності алфавіту і довжини пароля.

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

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