Метод «грубої сили»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод «грубої сили» (від англ. Brute force; або повний перебір) — метод рішення криптографічної задачі шляхом перебору всіх можливих варіантів ключа. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже великий, то повний перебір може не дати результатів протягом декількох років або навіть століть.

Будь-яка задача з класу NP може бути вирішена повним перебором. При цьому, навіть якщо обчислення цільової функції від кожного конкретного можливого рішення задачі може бути здійснена за поліноміальний час, в залежності від кількості всіх можливих рішень повний перебір може зажадати експоненціального часу роботи.

У криптографії на обчислювальній складності повного перебору ґрунтується оцінка криптостійкості шифрів. Зокрема, шифр вважається криптостійким, якщо не існує методу «злому» істотно більш швидкого ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі повного перебору, є найбільш універсальними, але водночас і найбільш повільними.

Методи оптимізації повного перебору[ред.ред. код]

Метод гілок і меж[ред.ред. код]

Для прискорення перебору метод гілок і меж використовує відсів підмножин допустимих рішень, про які наперед відомо що вони не містять оптимальних рішень.

Розпаралелювання обчислень[ред.ред. код]

Для збільшення швидкості підбору ключа використовується розпаралелювання обчислень. Існує два підходи до розпаралелювання:

  • побудова конвеєра. Нехай алгоритм співвідношення можна уявити у вигляді ланцюжка найпростіших дій (операцій). Візьмемо  N\ процесорів, задамо їх порядок,  i\ -ий процесор виконує три однакові за часом операції:
    1. отримання даних від -  (i - 1)\ -го процесора;
    2. виконання операції;
    3. передача даних  (i + 1)\ -му процесору.

Тоді конвеєр з  N\ послідовно з'єднаних, паралельно і синхронно працюючих процесорів працює зі швидкістю  v/3\ , де  v\ - швидкість виконання однієї операції одним процесором.

  • Другий підхід полягає що множина  K\ всіх можливих ключів розбивається на непересічні підмножини. Система з  Q\ машин перебирає ключі так, що  i\ -та машина здійснює перебір ключів з множини  K_i\ , i = 1 .. Q . Система припиняє роботу, якщо одна з машин знайшла ключ. Найважче - це розділення вихідної множини. Але якщо кожен процесор почне обчислення з якогось довільного ключа, то час перебору збільшиться, але схема значно спроститься. Середнє число кроків у цьому випадку становить  |K|/N\ , де  |K|\ - число елементів у множині ключів, а  N\ - число процесорів.

Приклад тривалості підбору паролів[ред.ред. код]

У переліку представлено оцінний час повного перебору паролів в залежності від їх довжини. Передбачається, що в паролі можуть використовуватися 36 різних символів (латинські літери одного регістру та цифри), а швидкість перебору становить 100 000 паролів в секунду (порядок представлених даних в рядку: Кількість знаків - Кількість варіантів - Час перебору):

Кількість знаків Кількість варіантів Час перебору
1 36 менше секунди
2 1296 менше секунди
3 46 656 менше секунди
4 1 679 616 17 секунд
5 60 466 176 10 хвилин
6 2 176 782 336 6 годин
7 78 364 164 096 9 днів
8 2,821 109 9×1012 11 місяців
9 1,015 599 5×1014 32 роки
10 3,656 158 4×1015 1162
11 1,316 217 0×1017 41 823 роки
12 4,738 381 3×1018 1 505 615 років

Таким чином, паролі довжиною до 6 символів у загальному випадку не є надійними.

Див. також[ред.ред. код]


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.