Метод «грубої сили»: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
№№3 (обговорення | внесок)
Створена сторінка: Повний перебір (або метод «грубої сили» від англ. Brute force) - метод рішення задачі шляхом пер...
 
StripedM (обговорення | внесок)
м стильові правлення , вікіфікація, оформлення
Рядок 1:
'''Брутфорс''' — Повний перебір (або метод «грубої сили» від англ. Brute force) - метод рішення криптографічної задачі шляхом перебору всіх можливих варіантів ключа. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже велике, то повний перебір може не дати результатів протягом декількох років або навіть століть.
 
Будь-яка задача з класу NP може бути вирішена повним перебором. При цьому, навіть якщо обчислення цільової функції від кожного конкретного можливого рішення задачі може бути здійснена за поліноміальний час, в залежності від кількості всіх можливих рішень повний перебір може зажадати експоненціального часу роботи.
 
У криптографії на обчислювальній складності повного перебору грунтуєтьсяґрунтується оцінка криптостійкості шифрів. Зокрема, шифр вважається криптостійкі, якщо не існує методу «злому» істотно більш швидкого ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі повного перебору, є найбільш універсальними, але і самими долгімітривалими.Содержаніе [очистити]
1 Методи оптимізації повного перебору
1.1 Метод гілок і меж
1.2 Розпаралелювання обчислень
2 Приклад тривалості підбору паролів
3 см. також
4 Примітки
 
1== Методи оптимізації повного перебору ==
[Ред]
Методи оптимізації повного перебору
[Ред]
Метод гілок і меж
Основна стаття: Метод гілок і меж
 
1.1=== Метод гілок і меж ===
Для прискорення перебору метод гілок і меж використовує відсів підмножин допустимих рішень, свідомо не містять оптимальних рішень.
[Ред]
Розпаралелювання обчислень
Основна стаття: Паралельні обчислення
 
Для прискорення перебору метод гілок і меж використовує відсів підмножин допустимих рішень, свідомо не містять оптимальних рішень.
Для збільшення швидкості підбору ключа використовується розпаралелювання обчислень. Існує два підходи до розпаралелювання:
 
1.2=== Розпаралелювання обчислень ===
 
Для збільшення швидкості підбору ключа використовується розпаралелювання обчислень. Існує два підходи до розпаралелювання:
Перший підхід - побудова конвеєра. Нехай алгоритм співвідношення можна уявити у вигляді ланцюжка найпростіших дій (операцій):. Візьмемо процесорів, задамо їх порядок і покладемо, що - ий процесор виконує три однакові за часом операції:
отримання даних від - го процесора;
Рядок 29 ⟶ 20:
Тоді конвеєр з послідовно з'єднаних, паралельно і синхронно працюючих процесорів працює зі швидкістю, де - швидкість виконання однієї операції одним процесором.
Другий підхід полягає в тому, що безліч всіх можливих ключів розбивається на непересічні підмножини. Система з машин перебирає ключі так, що - а машина здійснює перебір ключів з безлічі. Система припиняє роботу, якщо одна з машин знайшла ключ. Найважче - це розділення ключового безлічі. Але якщо кожен процесор почне обчислення з якогось довільного ключа, то час перебування збільшиться, а схема значно спроститься. Середнє число кроків у цьому випадку становить, де - число елементів у безлічі ключів, а - число процесорів.
 
[Ред]
Приклад тривалості підбору паролів
 
У таблиці представлено оціночне час повного перебору паролів в залежності від їх довжини. Передбачається, що в паролі можуть використовуватися 36 різних символів (латинські літери одного регістру цифри), а швидкість перебору складає 100 000 паролів в секунду. Кількість знаків Кількість варіантів Час перебору
1 36 менше секунди
2 1296 менше секунди
Рядок 47 ⟶ 38:
 
 
Таким чином, паролі довжиною до 6 символів у загальному випадку не є надійними.
 
[Ред]
См== Див. також ==
* [[Перебір дільників]]
* [[Метод гілок і меж]]